Source-linked AI summary
Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles
Dylan J. Foster, Alexander Rakhlin
TL;DR
Contextual bandits need practical, provably efficient algorithms for rich function classes, including instance-dependent guarantees. The paper reduces contextual bandits to online square-loss regression, characterizes minimax rates, and shows the reduction can attain optimal rates under suitable oracle performance. Its analysis relies on adaptively chosen actions and an online regression oracle, leaving offline-oracle reductions unresolved.
Problem
The paper addresses practical, provably efficient contextual-bandit algorithms for rich, potentially nonparametric function classes and asks whether they can achieve gap-dependent regret guarantees.
Method
SquareCB uses an online regression oracle with value class F and the induced policy class Π={π_f ∣ f∈F} to design contextual-bandit algorithms.
Results
SquareCB is an optimal reduction: with a suitable oracle, it attains minimax-optimal rates for every function class, including rates characterized by metric entropy for infinite classes.
Takeaways & Limitations
Online oracles provide a computationally and statistically efficient primitive for contextual bandits and clarify minimax and gap-dependent limits for RichCBs.
Takeaways & Limitations
The guarantee critically requires an online regression oracle whose regret bound holds under adaptively chosen actions; whether optimal regret follows from an offline oracle remains open.
Abstract
from arXiv · showhide
A fundamental challenge in contextual bandits is to develop flexible, general-purpose algorithms with computational requirements no worse than classical supervised learning tasks such as classification and regression. Algorithms based on regression have shown promising empirical success, but theoretical guarantees have remained elusive except in special cases. We provide the first universal and optimal reduction from contextual bandits to online regression. We show how to transform any oracle for online regression with a given value function class into an algorithm for contextual bandits with the induced policy class, with no overhead in runtime or memory requirements. We characterize the minimax rates for contextual bandits with general, potentially nonparametric function classes, and show that our algorithm is minimax optimal whenever the oracle obtains the optimal rate for regression. Compared to previous results, our algorithm requires no distributional assumptions beyond realizability, and works even when contexts are chosen adversarially.
1 Introduction
The paper develops SquareCB, a practical reduction from contextual bandits to online regression that preserves oracle efficiency while requiring only realizability. It establishes optimality for rich function classes and addresses computational, statistical, and deployment limitations of prior methods.
- Contextual bandits seek flexible algorithms for arbitrary policy classes while retaining strong performance guarantees across models such as trees, kernels, and neural networks.
- Prior oracle-based methods suffer from difficult or intractable supervised-learning oracles, strong assumptions, or memory requirements that scale with the dataset.
- SquareCB converts any online regression oracle into a contextual-bandit algorithm requiring no data-generating assumptions beyond realizability and inheriting the oracle’s runtime and memory requirements.
- The reduction is optimal for every function class when paired with a suitable regression oracle, including minimax-optimal rates for finite and potentially nonparametric classes.
- SquareCB uses a simple score-to-probability mapping, extends to continuous action spaces, and provides guarantees for linear, generalized linear, and kernel classes.
- For RichCBs, the paper characterizes minimax rates through metric entropy and shows that logarithmic gap-dependent regret can be impossible for general finite classes.
2 The reduction: SquareCB
SquareCB reduces contextual bandits to online square-loss regression by converting oracle predictions into an exploration distribution. Its regret depends on the oracle’s regression regret, while inheriting the oracle’s computational requirements up to action-related factors.
- Oracle assumptions: The reduction requires an online regression regret guarantee for adaptively chosen context-action sequences, with a weaker realizability-specific assumption also sufficient.The relaxed condition can be satisfied by algorithms tailored to realizable problems.
- Algorithm: SquareCB receives context, queries the online regression oracle for each action, assigns exploration probabilities inversely related to prediction gaps, samples an action, and updates the oracle.The oracle is updated with the observed loss for the selected context-action pair.
- Regret guarantees: For fast log T-type regression rates, SquareCB obtains logarithmic-horizon contextual-bandit regret, including finite classes and linear functions with regret dlog(T/d).The linear-class instantiation uses the Vovk-Azoury-Warmuth forecaster with RegSq(T) ≤ dlog(T/d).
- Computational requirements: SquareCB inherits the oracle’s runtime and memory requirements up to lower-order terms, with per-round runtime O(TSqAlg ⋅K) and memory O(MSqAlg ⋅K).The action factor is described as near-optimal for algorithms working uniformly over all oracles.
- Examples: For kernels, SquareCB gives O(T 3/4) regret without effective-dimension assumptions, trading worse horizon dependence for broader distributional robustness.The guarantee assumes bounded RKHS norm and bounded diagonal kernel values.
- Reduction guarantee: SquareCB converts the oracle’s square-loss regret into contextual-bandit regret through a probability-selection strategy whose analysis ignores the structure of the function class.The per-round minimax interpretation bounds immediate regret using squared prediction error plus a constant.
3 Optimality and universality
The paper characterizes minimax regret for realizable contextual bandits through metric entropy and shows SquareCB can attain the resulting rate with a suitable regression oracle. The framework recovers rates for linear, Lipschitz, Hölder, and neural-network classes, with explicit scope boundaries.
- Optimality and universality: The paper proves a minimax lower bound for RichCBs and shows SquareCB is universal, attaining it up to dependence on the number of actions.Universality means some choice of the base regression algorithm achieves the lower bound’s dependence on T.
- Scope and limitations: The main optimality characterization assumes i.i.d. contexts and tensorized regression classes, while broader adversarial-context results cover only parts of the entropy range.Without tensorization, the discussion identifies separate regimes and leaves the optimal dependence on K unresolved.
- Complexity characterization: The upper and lower bounds are expressed through the metric entropy of a base class G, a complexity measure linked to standard learnability measures.The empirical entropy of G is used to characterize rates under Assumption 3.
- Complexity characterization: Under Assumption 3, where entropy grows as ε^-p for i.i.d. contexts and losses, the paper characterizes optimal RichCB regret as a function of p.The lower-bound construction uses a modified class with matching entropy growth.
- Examples: For linear classes, the general theorems recover √dT and T 3/4 regret rates.These rates follow from the entropy behavior of linear function classes.
- Examples: For 1-Lipschitz functions over [0,1]^d, the theorems recover the known nonparametric optimal rate; Hölder-smooth classes yield rates determined by p = d/β.The Lipschitz and Hölder examples instantiate the entropy-based characterization.
- Examples: For suitably norm-bounded neural networks, the theorems imply that Θ̃(T 3/4) is optimal.The result uses entropy growth proportional to ε^-2.
- Relation to prior work: Unlike policy-complexity-based guarantees, these bounds depend on regression-function complexity and require realizability.The comparison concerns infinite policy classes and induced policy classes.
4 On gap-dependent regret bounds
The paper asks whether gap-dependent regret guarantees can extend from multi-armed bandits to rich contextual bandits. Its lower bound shows that such guarantees are fundamentally limited for general function classes.
- The section asks whether SquareCB can recover O(K log T / ∆) regret and extend it to rich function classes.
- The analysis assumes a uniform gap ∆ separating the optimal and second-best action for every context.
- An information-theoretic lower bound rules out the hypothesized instance-dependent regret bounds for SquareCB and any contextual bandit algorithm.
- At best, instance-dependent regret for rich function classes must scale with |F|, making such dependence unacceptable in RichCBs.
- Gap-dependent logarithmic regret remains achievable under stronger structural assumptions such as bounded eluder dimension, which the theorem shows are qualitatively required.
5 Extensions
The paper extends SquareCB beyond exact realizability and finite action sets. These extensions preserve efficient oracle-based guarantees while quantifying misspecification costs and matching known rates in an infinite-action linear setting.
- 5 Extensions: SquareCB is generalized to approximately realizable settings and infinite action sets.
- 5.1 Misspecified models: Under misspecification, SquareCB’s performance degrades by an additive ε√KT term when the learning rate is adjusted appropriately.
- 5.1 Misspecified models: The misspecified guarantee applies against any policy and extends to contextual bandits with an adaptive adversary.
- 5.1 Misspecified models: For adaptive adversaries, approximate prediction error is bounded uniformly by ε through the stated assumption, which suffices for the same guarantee as Theorem 5.
- 5.1 Misspecified models: For finite-action linear contextual bandits, the Vovk–Azoury–Warmuth forecaster yields an efficient regret guarantee using RegSq(T) ≤ d log(T/d).
- 5.2 Infinite action sets: In the infinite-action extension, the action space is the d_A-dimensional unit ℓ2 ball and the linear rate matches OFUL.
6 Discussion
The discussion presents online regression oracles as a computationally and statistically efficient foundation for contextual bandits, while identifying open limitations for reinforcement learning, adaptivity, and broader action sets.
- The paper’s main reduction is described as the first optimal reduction from contextual bandits to online square loss reduction.
- Online oracles support contextual bandit algorithms with computational and statistical efficiency, while the paper also characterizes minimax and gap-dependent limits.
- Reinforcement learning: Adapting SquareCB to reinforcement learning is left open because the strategy is not optimistic, which may matter more in full reinforcement learning.
- Adaptivity and further technical directions: The paper identifies adaptive, data-dependent guarantees and extensions to arbitrary action sets as further open directions.
A Basic technical results
The supplied technical result introduces Freedman’s inequality for bounded martingale difference sequences, providing a concentration tool for the analysis.
- Freedman’s inequality applies to a real-valued martingale difference sequence adapted to a filtration.
- The sequence increments must be almost surely bounded by R.
- The inequality gives a high-probability bound parameterized by η and δ.
B.1 Proof of Theorem 1
The proof reduces contextual-bandit regret to online square-loss regret through a per-round probability construction, then establishes the required high-probability bounds under the stated assumptions.
- Reduction and concentration: Lemma 2 relates conditional contextual-bandit regret and square-loss regret to their conditional-expectation counterparts with high probability.The argument uses filtrations, bounded martingale differences, and Azuma-Hoeffding concentration.
- Per-round reduction: SquareCB maps regression predictions to an action distribution satisfying a per-timestep inequality for every value vector f⋆.The proof analyzes the distribution using a free parameter η and separate cases for the selected optimal and comparison actions.
- Parameter choice: Choosing η = γ/4 and the prescribed γ yields the theorem’s regret bound after summing the per-round inequality over all rounds.The final step combines the accumulated bound with Lemma 3 and tunes γ to the theorem statement.
- Regression-oracle guarantees: Gradient-descent and online-Newton variants of GLMtron provide slow- and fast-rate online prediction guarantees, respectively.The fast-rate proposition assumes σ′ ≥ cσ > 0 and uses appropriate η and ε.
C.1 Proof of Theorem 2
The lower-bound proof converts metric-entropy growth into fat-shattering and embeds independent two-arm bandit problems across shattered contexts.
- Function-class construction: Entropy growth implies a fat-shattered set of m =̃ Θ(γ^-p) distinct contexts with independently realizable sign patterns.The construction augments the class while preserving metric entropy up to the stated order.
- Hard-instance distribution: The hard distribution samples contexts uniformly over the shattered set and assigns each sign pattern a corresponding Bayes regression function.Losses are Bernoulli random variables whose conditional means equal the constructed function values.
- Bandit decomposition: The resulting process decomposes the contextual problem into independent two-arm Bernoulli bandit instances indexed by contexts.Context-count sets and bandit instances are independent under the constructed distribution.
- Occupancy control: For each context, the number of visits has expectation T/m and second moment at most (T/m)^2, enabling a constant-probability occupancy interval.Markov’s inequality and Paley-Zygmund provide constants c1 < c2 with c1 T/m < Ni < c2 T/m with constant probability.
- Rate selection: Choosing γ ∝ T^(-1/(2+p))/polylog(T) produces the lower-bound scale through the number of shattered contexts and the embedded bandit regret.The construction selects m through γ and obtains the desired growth after summing over contexts.
C.2 Proof of Theorem 3
The proof builds an epoch-based square-loss oracle from empirical covers and exponential weights, then transfers its regret bound to contextual bandits.
- Oracle construction: SqAlg doubles epoch lengths, constructs an empirical L2 cover of the regression class, and predicts with exponential weights over that cover.At each epoch, the cover uses all previously collected data and remains fixed during the epoch.
- Within-epoch prediction: Exponential weights over a finite cover supplies a log∣F∣ regret term for adaptively chosen example-label sequences.The method uses squared loss and a uniform prior with learning rate η = 1/2.
- Cover accuracy: Empirical L2 distances concentrate around population distances under i.i.d. contexts, making the epoch covers accurate on future examples.This concentration is the bridge between covers formed from past data and prediction performance during later epochs.
- High-probability analysis: Square-loss concentration and self-bounding martingale arguments control the excess loss of each fixed cover function with high probability.The proof applies bounded-difference lemmas within each epoch before combining the resulting events.
- Final rate: Choosing ε ∝ (KT)^(-1/(2+p)) gives RegSq(T) ≤̃ O((KT)^(1−2/(2+p)) + K log(δ^-1)) after simplifying the bound.The proof then invokes Theorem 1 and a union bound to obtain the contextual-bandit guarantee.
D Proofs from Section 4
The lower-bound proof uses noiseless, block-structured contexts and indistinguishable instances to force contextual-bandit regret for algorithms that cannot identify the active context’s better arm.
- Hard-instance design: The hard family uses N contexts, two actions, noiseless losses, and contexts presented in consecutive blocks of length T/N.Each instance has a uniform gap parameter ∆ and differs in the optimal action associated with a context.
- Algorithm model: The construction models randomized contextual-bandit algorithms through measurable action functions driven by histories and an independent random seed.Under the noiseless instances, expectation reflects only the algorithm’s action randomization.
- Rare exploration: A deterministic context block i is selected where the algorithm rarely plays the second arm under the baseline instance.Partitioning the rounds into context blocks yields an index i⋆ with the required low visitation property.
- Indistinguishability: The probability of never playing the informative arm in block i is identical under the baseline and corresponding alternative instance.Lemma 10 establishes this equality because the observed history is unchanged until the informative action is selected.
- Regret consequence: Consequently, some alternative instance incurs expected regret at least 1/2 ∆T/N.The lower bound follows when the algorithm receives no distinguishing feedback throughout the relevant block.
E.1 Proofs from Section 5.1
The proofs bound regret through conditional expectations, squared prediction error, and assumptions controlling the resulting terms. Choosing γ appropriately converts intermediate inequalities into the stated theorem bounds.
- Theorem 5 fixes a policy and filtration, then begins by bounding the sum of conditional expected immediate regrets relative to that policy.
- Theorem 6 applies Lemma 3 round by round, sums the resulting inequalities, and uses total expectation to obtain a marginal bound.
- Strong convexity of square loss relates per-round prediction error to a comparator, and summing gives a sequence-wide bound.
- The proof handles the adversary’s obliviousness through independence of f⋆ from the outcome sequence and applies AM-GM before taking expectations.
- Intermediate bounds include 2(RegSq(T) + 2ε2T) + 2KT γ + 2εT and 4(ε2T + RegSq(T)) + 2KT γ, after which γ is chosen as in the theorem.
- Assumptions 2a and 5 provide pointwise bounds that can be combined with earlier inequalities and transferred to expectations.
E.2 Proofs from Section 5.2
Theorem 7 analyzes the action distribution through its moments and separates the proof according to αt. In the nondegenerate case, a negative contribution is used to cancel another term, yielding the final per-round bound.
- Theorem 7: Theorem 7 conditions the action distribution on the preceding filtration and uses Lemma 2 to establish a high-probability regret analysis.
- Final bound: Combining the case-specific calculations with equations (33), (34), and (29) produces the final per-round bound regardless of which case holds.
- Basic properties of the action distribution: The first moment of the action distribution is µt = −(1 − αt)ỹt, obtained by combining the exploitation and exploration components.
- Basic properties of the action distribution: The analysis uses a weighted Euclidean norm and divides into two cases based on αt, including a degenerate regime where ỹt is small.
- Case 2: αt = β ∥ŷt∥2: In the interesting case, defining 𝑓̃t from f⋆ allows the first regret term to contribute negatively up to an additive error β.
- Case 2: αt = β ∥ŷt∥2: Hölder’s inequality and AM-GM bound the second term, while η2 is chosen so that the first term is cancelled by E1 using the lower bound on Σt.