A Lyapunov-Based Methodology for Constrained Optimization with Bandit Feedback


  • Semih Cayci University of Illinois at Urbana-Champaign
  • Yilin Zheng The Ohio State University
  • Atilla Eryilmaz The Ohio State University




Constraint Satisfaction And Optimization (CSO)


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 LyOn, and prove that for K arms it achieves square root of KBlog(B) regret and zero constraint-violation when B is sufficiently large. The low computational cost and sharp performance bounds of LyOn suggest that Lyapunov-based algorithm design methodology can be effective in solving constrained bandit optimization problems.




How to Cite

Cayci, S., Zheng, Y., & Eryilmaz, A. (2022). A Lyapunov-Based Methodology for Constrained Optimization with Bandit Feedback. Proceedings of the AAAI Conference on Artificial Intelligence, 36(4), 3716-3723. https://doi.org/10.1609/aaai.v36i4.20285



AAAI Technical Track on Constraint Satisfaction and Optimization