# Algorithms with Logarithmic or Sublinear Regret for Constrained Contextual Bandits

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

## Key facts

- Cited by 29 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Apr 2015.

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

- [Distributionally Robust Learning](https://mlsanity.com/paper/2108.08993/) (2021)
- [An Efficient Pessimistic-Optimistic Algorithm for Stochastic Linear Bandits with General Constraints](https://mlsanity.com/paper/2102.05295/) (2021)
- [On Kernelized Multi-Armed Bandits with Constraints](https://mlsanity.com/paper/2203.15589/) (2022)
- [Restless Bandits with Many Arms: Beating the Central Limit Theorem](https://mlsanity.com/paper/2107.11911/) (2021)
- [Safe Exploration for Efficient Policy Evaluation and Comparison](https://mlsanity.com/paper/2202.13234/) (2022)
- [Bandit Algorithms for Precision Medicine](https://mlsanity.com/paper/2108.04782/) (2021)
- [Learning to be Fair: A Consequentialist Approach to Equitable Decision-Making](https://mlsanity.com/paper/2109.08792/) (2021)
- [Optimal Regularized Online Allocation by Adaptive Re-Solving](https://mlsanity.com/paper/2209.00399/) (2022)
- [Directional Optimism for Safe Linear Bandits](https://mlsanity.com/paper/2308.15006/) (2023)
- [Fairer LP-based Online Allocation via Analytic Center](https://mlsanity.com/paper/2110.14621/) (2021)
- [Best of Many Worlds Guarantees for Online Learning with Knapsacks](https://mlsanity.com/paper/2202.13710/) (2022)
- [Price of Safety in Linear Best Arm Identification](https://mlsanity.com/paper/2309.08709/) (2023)
- [Contextual Decision-Making with Knapsacks Beyond the Worst Case](https://mlsanity.com/paper/2211.13952/) (2022)
- [Contextual Bandits with Budgeted Information Reveal](https://mlsanity.com/paper/2305.18511/) (2023)
- [WISERouter: LLM Routing with Workload Budget Constraint](https://mlsanity.com/paper/2607.23765/) (2026)
- [Dynamic Budget Throttling in Repeated Second-Price Auctions](https://mlsanity.com/paper/2207.04690/) (2022)
- [Spatio-temporal Incentives Optimization for Ride-hailing Services with Offline Deep Reinforcement Learning](https://mlsanity.com/paper/2211.03240/) (2022)
- [Adapter-Augmented Bandits for Online Multi-Constrained Multi-Modal Inference Scheduling](https://mlsanity.com/paper/2603.06403/) (2026)
- [Interactive Learning with Pricing for Optimal and Stable Allocations in Markets](https://mlsanity.com/paper/2212.06891/) (2022)
- [A Re-solving Heuristic for Dynamic Assortment Optimization with Knapsack Constraints](https://mlsanity.com/paper/2407.05564/) (2024)
- [BGTplanner: Maximizing Training Accuracy for Differentially Private Federated Recommenders via Strategic Privacy Budget Allocation](https://mlsanity.com/paper/2412.02934/) (2024)
- [Constrained Online Decision-Making: A Unified Framework](https://mlsanity.com/paper/2505.07101/) (2025)
- [Leveraging User-Triggered Supervision in Contextual Bandits](https://mlsanity.com/paper/2302.03784/) (2023)
- [Semi-Infinitely Constrained Markov Decision Processes and Efficient Reinforcement Learning](https://mlsanity.com/paper/2305.00254/) (2023)
- [Clustered Linear Contextual Bandits with Knapsacks](https://mlsanity.com/paper/2308.10722/) (2023)
- [Budgeted Recommendation with Delayed Feedback](https://mlsanity.com/paper/2405.11417/) (2024)
- [A Simple Reduction Scheme for Constrained Contextual Bandits with Adversarial Contexts via Regression](https://mlsanity.com/paper/2602.05019/) (2026)
- [Multi-Task Representation Learning for Conservative Linear Bandits](https://mlsanity.com/paper/2605.12176/) (2026)
- [Safe Bayesian Optimization with Counterfactual Policies](https://mlsanity.com/paper/2607.05620/) (2026)

## Abstract (arXiv)

We study contextual bandits with budget and time constraints, referred to as constrained contextual bandits.The time and budget constraints significantly complicate the exploration and exploitation tradeoff because they introduce complex coupling among contexts over time.Such coupling effects make it difficult to obtain oracle solutions that assume known statistics of bandits. To gain insight, we first study unit-cost systems with known context distribution. When the expected rewards are known, we develop an approximation of the oracle, referred to Adaptive-Linear-Programming (ALP), which achieves near-optimality and only requires the ordering of expected rewards. With these highly desirable features, we then combine ALP with the upper-confidence-bound (UCB) method in the general case where the expected rewards are unknown it a priori. We show that the proposed UCB-ALP algorithm achieves logarithmic regret except for certain boundary cases. Further, we design algorithms and obtain similar regret analysis results for more general systems with unknown context distribution and heterogeneous costs. To the best of our knowledge, this is the first work that shows how to achieve logarithmic regret in constrained contextual bandits. Moreover, this work also sheds light on the study of computationally efficient algorithms for general constrained contextual bandits.