RECORD
Algorithms with Logarithmic or Sublinear Regret for Constrained Contextual Bandits
Machine Learning · Submitted 27 Apr 2015
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim To the best of our knowledge, this is the first work that shows how to achieve logarithmic regret in constrained contextual bandits.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
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.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | 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. | background 0.97 | 0.15 | 0.03 | asserted 1.00 |
| s1 | To gain insight, we first study unit-cost systems with known context distribution. | method 0.79 | 0.70 | 0.02 | asserted 0.60 |
| s2 | 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. | method 0.54 | 0.96 | 0.06 | asserted 1.00 |
| s3 | 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}. | method 0.92 | 0.91 | 0.05 | asserted 0.88 |
| s4 | We show that the proposed UCB-ALP algorithm achieves logarithmic regret except for certain boundary cases. | result 1.00 | 0.96 | 0.61 | asserted 1.00 |
| s5 | Further, we design algorithms and obtain similar regret analysis results for more general systems with unknown context distribution and heterogeneous costs. | contribution 0.89 | 0.95 | 0.10 | asserted 1.00 |
| s6 | To the best of our knowledge, this is the first work that shows how to achieve logarithmic regret in constrained contextual bandits. | contribution 0.69 | 0.81 | 0.58 | asserted 0.98 |
| s7 | Moreover, this work also sheds light on the study of computationally efficient algorithms for general constrained contextual bandits. | interpretation 0.98 | 0.78 | 0.10 | asserted 0.62 |
What was examined, and what was not
- arXiv listing abstract v3
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
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.
Human review
How the literature uses it
4 arXiv papers cite this in 4 sentences
Papers citing it · 3 sentences without a confident label
Cites it as background 1 paper
-
In the special cases of KB, such as multi-armed bandits (MAB) and linear bandits (e.g., KB with a linear kernel), there is a large body of work on bandits with different types of constraints, including knapsack bandits [ref] , conservative bandits [ref] , bandits with fairness constraints [ref] , bandits with hard safety constraints [ref] , and bandits with cumulative soft constraints [ref] .
On Kernelized Multi-Armed Bandits with Constraints · Related Work · 1.00
What it cites · 1 sentence without a confident label
Compares with 2 papers
-
However, [ref] focuses on static contexts[After the online publication of our preliminary version, two recent papers [ref] extend their previous work [ref] to the dynamic context case, where they focus on possibly infinite contexts and achieve $O(√(T))$ regret, and [ref] restricts to a finite policy set as [ref] .] and achieves $O(√(T))$ regret in our setting since it uses a fixed budget constraint in each round.
An efficient algorithm for contextual bandits with knapsacks, and an extension to concave objectives · Introduction · 0.92
-
However, [ref] focuses on static contexts[After the online publication of our preliminary version, two recent papers [ref] extend their previous work [ref] to the dynamic context case, where they focus on possibly infinite contexts and achieve $O(√(T))$ regret, and [ref] restricts to a finite policy set as [ref] .] and achieves $O(√(T))$ regret in our setting since it uses a fixed budget constraint in each round.
Linear Contextual Bandits with Knapsacks · Introduction · 0.92
Cites as background 1 paper
-
The contextual bandit problem [ref] is an important extension of the classic multi-armed bandit (MAB) problem [ref] , where the agent can observe a set of features, referred to as context, before making a decision.
A Survey on Contextual Multi-armed Bandits · Introduction · 1.00
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.