# A Lyapunov-Based Methodology for Constrained Optimization with Bandit Feedback

arXiv: https://arxiv.org/abs/2106.05165 · HTML: https://mlsanity.com/paper/2106.05165/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 42 references that are in the map.
- First posted on arXiv 9 Jun 2021.

## Builds on (most cited first, 9 of 9)

- [Bandits with Knapsacks](https://mlsanity.com/paper/1305.2545/) (2013)
- [Bandits with concave rewards and convex knapsacks](https://mlsanity.com/paper/1402.5758/) (2014)
- [Upper Confidence Primal-Dual Reinforcement Learning for CMDP with Adversarial Loss](https://mlsanity.com/paper/2003.00660/) (2020)
- [An Efficient Pessimistic-Optimistic Algorithm for Stochastic Linear Bandits with General Constraints](https://mlsanity.com/paper/2102.05295/) (2021)
- [Thompson Sampling for Budgeted Multi-armed Bandits](https://mlsanity.com/paper/1505.00146/) (2015)
- [Budget-Constrained Bandits over General Cost and Reward Distributions](https://mlsanity.com/paper/2003.00365/) (2020)
- [Logarithmic regret bounds for Bandits with Knapsacks](https://mlsanity.com/paper/1510.01800/) (2015)
- [POND: Pessimistic-Optimistic oNline Dispatching](https://mlsanity.com/paper/2010.09995/) (2020)
- [Group-Fair Online Allocation in Continuous Time](https://mlsanity.com/paper/2006.06852/) (2020)

## Built on by (most cited first, 4 of 4)

- [Think Smarter not Harder: Adaptive Reasoning with Inference Aware Optimization](https://mlsanity.com/paper/2501.17974/) (2025)
- [Online Learning for Multi-Layer Hierarchical Inference under Partial and Policy-Dependent Feedback](https://mlsanity.com/paper/2603.04247/) (2026)
- [Efficient Online Conformal Selection with Limited Feedback](https://mlsanity.com/paper/2605.14953/) (2026)
- [Learning When to Automate: Queue Control in Human-AI Service Systems](https://mlsanity.com/paper/2607.06017/) (2026)

## Abstract (arXiv)

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.