2021/06/09 by Semih Cayci, Semih Çaycı, Yilin Zheng +5 · 1 citation
Computer Science · Decision Sciences · Mathematics · #Advanced Bandit Algorithms Research #Artificial intelligence #Auction Theory and Applications #Budget constraint #Chaotic #Computer science #Constraint (computer-aided design) #Economics #Lyapunov exponent #Lyapunov function #Lyapunov optimization #Lyapunov redesign #Mathematical optimization #Mathematics #Nonlinear system #Optimization and Search Problems #Regret #Scheduling (production processes) #Stochastic optimization #cs.LG #math.OC #stat.ML
paper · pdf · doi:10.48550/arxiv.2106.05165
published in arXiv (Cornell University) (Cornell University)
openalex publication_date 2021/06/09 · arxiv created 2022/01/23 · arxiv updated 2022/01/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/06
In a wide variety of applications including online advertising, contractual hiring, and wireless scheduling, the controller is constrained by a stringent budget constraint on the available resources, which are consumed in a random amount by each action, and a stochastic feasibility constraint that may impose important operational limitations on decision-making. In this work, we consider a general model to address such problems, where each action returns a random reward, cost, and penalty from an unknown joint distribution, and the decision-maker aims to maximize the total reward under a budget constraint B on the total cost and a stochastic constraint on the time-average penalty. We propose a novel low-complexity algorithm based on Lyapunov optimization methodology, named \tt LyOn, and prove that for K arms it achieves O(√(K Blog B)) regret and zero constraint-violation when B is sufficiently large. The low computational cost and sharp performance bounds of \tt LyOn suggest that Lyapunov-based algorithm design methodology can be effective in solving constrained bandit optimization problems.