Practical Contextual Bandits with Regression Oracles

Dylan J. Foster; Alekh Agarwal; Miroslav Dudík; Haipeng Luo; Robert E. Schapire

Source-linked AI summary

Practical Contextual Bandits with Regression Oracles

Dylan J. Foster, Alekh Agarwal, Miroslav Dudík, Haipeng Luo, Robert E. Schapire

arXiv:1803.01088v1Mar 3, 2018cs.LGstat.ML

TL;DR

Contextual-bandit algorithms must balance generality, computational practicality, and theoretical guarantees. This paper develops regression-oracle algorithms that generalize realizability-based methods, achieve low regret under favorable distributional assumptions, and usually match or outperform agnostic and realizability-based baselines empirically.

Problem
Contextual-bandit methods must combine the flexibility of agnostic approaches with the computational and theoretical advantages of realizability-based methods.
Method
The paper develops RegCB algorithms that maintain predictor version spaces, compute confidence bounds through a squared regression oracle, and choose actions by elimination or optimism.
Results
The algorithms achieve low regret under bounded distributional quantities and give comparable or superior results in nearly all empirical comparisons.
Takeaways & Limitations
Regression-oracle methods provide a practical route to oracle-efficient contextual bandits over expressive model classes while retaining theoretical guarantees under stated assumptions.
Takeaways & Limitations
The disagreement-based analysis depends on product-class structure, and efficiently computing disagreement sets for general non-product classes remains an open challenge.

Abstract

from arXiv · show

A major challenge in contextual bandits is to design general-purpose algorithms that are both practically useful and theoretically well-founded. We present a new technique that has the empirical and computational advantages of realizability-based approaches combined with the flexibility of agnostic methods. Our algorithms leverage the availability of a regression oracle for the value-function class, a more realistic and reasonable oracle than the classification oracles over policies typically assumed by agnostic methods. Our approach generalizes both UCB and LinUCB to far more expressive possible model classes and achieves low regret under certain distributional assumptions. In an extensive empirical evaluation, compared to both realizability-based and agnostic baselines, we find that our approach typically gives comparable or superior results.

1. Introduction

The paper seeks contextual-bandit algorithms that combine the practical flexibility of agnostic methods with the computational and theoretical benefits of realizability-based approaches. It introduces regression-oracle algorithms with low-regret guarantees under distributional assumptions and comparable or superior empirical performance in nearly all tested cases.

The approach addresses limitations of both method families: realizability-based algorithms have been restricted to specific models, while agnostic methods often require computationally intractable policy oracles.
A squared regression oracle enables practical realizability-based algorithms for arbitrary model classes, avoiding the typically harder cost-sensitive classification oracle.The authors describe regression as a milder computational assumption because it often reduces to standard learning problems.
The algorithms achieve low regret when distributional quantities such as disagreement coefficients or generalized exploration coefficients are bounded.The analysis also yields nearly dimension-free guarantees for sparse linear bandits in high dimensions.
Across extensive evaluations against realizability-based and agnostic baselines, the approach gives comparable or superior results in nearly all cases and validates the required distributional assumptions on the tested datasets.

2. Preliminaries

The paper formalizes a stochastic contextual-bandit problem in which the learner chooses actions from observed contexts and seeks high cumulative reward relative to a predictor class. It assumes realizability and contrasts the regression-oracle formulation with the computational cost of generic policy-based methods.

In each round, the learner observes a context, selects one of finitely many actions, receives only that action’s reward, and competes with predictors of expected rewards.The predictor class can include linear predictors or regression trees.
Realizability assumes that the predictor class contains a function f⋆ exactly matching each action’s conditional expected reward.
A predictor induces a policy by selecting the action with the highest predicted reward, with π⋆ denoting the policy induced by f⋆.
Exp4 has regret of order O(√(TK ln|F|)) for finite predictor classes but incurs computational complexity linear in |F|.
The algorithms use a weighted least-squares regression oracle over the predictor class, an assumption described as mild because regression tasks are common in machine learning practice.

3. Algorithms

The algorithms maintain low-loss version spaces, derive action-wise confidence bounds through regression-oracle calls, and use those bounds either to randomize among plausible best actions or to act optimistically. Their reward-range computation is especially efficient for convex predictor classes.

3. Algorithms: The method maintains a version space of predictors with small observed squared loss and constructs upper and lower reward bounds for each action.Actions are then selected using either uniform randomization among plausible best actions or optimism based on upper bounds.
3. Algorithms: The algorithms update version spaces on a doubling-epoch schedule, with the optimistic variant using initial uniform exploration as a warm start.
3. Algorithms: The two procedures include an elimination algorithm that samples uniformly from plausible actions and an optimistic algorithm that selects the action with the highest upper reward bound.
3. Algorithms: Confidence bounds are computed efficiently by augmenting the history with a weighted out-of-range reward example and repeatedly querying the regression oracle.Upper bounds use reward 2, lower bounds use reward −1, and increasing the added example’s weight pushes the prediction in the desired direction.
3.1. Efficient Reward-Range Computation: For convex predictor classes, reward-range computation requires O(log(1/α)) oracle calls, an exponential improvement over O(1/α); nonconvex classes retain the latter bound.

4. Regret Guarantees

RegCB’s regret guarantees depend on structural or distributional conditions, while the paper also identifies pathological cases and scope limitations. Disagreement- and moment-based analyses provide favorable rates in appropriate settings, including sparse models, but the guarantees are not uniformly optimal.

RegCB can suffer regret of at least (1 −ϵ)·min{N,̃Ω(T)} on a class with |F| = N + 1, showing confidence-based strategies are not minimax optimal.The paper contrasts this pathological construction with strong empirical performance on practical datasets.
Disagreement-based Analysis: Under bounded disagreement coefficients, the analysis gives low-regret guarantees, with logarithmic-in-T rates available under the Massart noise condition.The disagreement coefficient measures how often predictors fitting historical data can disagree on new examples.
Disagreement-based Analysis: The disagreement analysis relies critically on product classes because efficient computation of disagreement sets is unresolved for general predictor classes.Under the product-class assumption, disagreement-set size can be checked empirically.
Moment-based Analysis: The paper introduces surprise bounds and implicit exploration coefficients to analyze regret under distributional properties tailored to i.i.d. contextual-bandit settings.The implicit exploration coefficient relates error under optimal-policy actions to worst-case context-action error.
Moment-based Analysis: Algorithm 1 has better regret bounds than Algorithm 2 because Algorithm 2 requires a warm-start period and uses L2,λ with λ > 0.Algorithm 1 depends on L2,0, while Algorithm 2’s analysis requires λ > 0.
Moment-based Analysis: For sparse high-dimensional settings, discretization yields log |F| = O(s log d)^2 and a near dimension-independent regret bound, though the standard LinUCB setting can remain better by a factor of K.The sparse result improves on moment-matrix conditions but is efficient only in the oracle model.

5. Experiments

The experiments compare RegCB variants with regression-oracle and classification-oracle baselines across 18 datasets, using Linear and GB5 predictors. RegCB generally performs competitively, with the strongest aggregate results using Linear oracles and close competition with Bootstrap under GB5.

The evaluation uses 18 datasets, replicated by random permutations and, for noisy UCI, regenerated rewards, with holdout validation and tuned parameters.
RegCB outperforms all baselines on unmodified UCI datasets, while Bootstrap slightly leads on noisy UCI variants and has similar ordering on yahoo.
Across datasets, RegCB and Bootstrap generally dominate; RegCB is almost always within 20% of the best, while its elimination variant slightly leads its optimistic variant in aggregate.
Figure 2 aggregates normalized relative loss across datasets at 1,000 examples and final rounds, with solid GB5 and dashed Linear curves.
With GB5 oracles, RegCB always beats ϵ-Greedy and ILTCB but sometimes loses to Bootstrap, whose advantage may reflect fixed-ensemble approximation.
With Linear oracles, both RegCB variants dominate all baselines, including Bootstrap, across all datasets.

6. Conclusion and Discussion

The paper concludes that RegCB combines strong empirical performance with theoretical properties, while identifying unresolved questions about optimal regret, Bootstrap analysis, and action randomization.

RegCB achieves strong empirical performance and favorable theoretical properties, motivating further research on oracle-efficient realizability-based contextual bandits.
The paper leaves open whether regression-oracle algorithms can attain optimal Õ(√(KT log |F|)) regret, including through an oraclized regressor-elimination strategy.
The analysis does not establish comparable distributional guarantees for Bootstrap, despite its competitive empirical performance.
The paper asks whether better randomization schemes among plausibly optimal actions could yield stronger regret guarantees.

A.1. Proofs from Section 3.1

The proof analyzes binary search for an upper confidence value through a convex auxiliary error function. It establishes approximation accuracy and logarithmic oracle-search complexity under bounded or unbounded predictor settings.

The unbounded variant handles predictors outside [0,1], although realized rewards remain bounded in [0,1] under realizability.
Algorithm 4 returns z within α of min{z⋆,1} after O(log(1/α) + log(max{2 − z0,1})) iterations.
For predictors bounded in [0,1], Algorithm 4 returns z within α of z⋆ after O(log(1/α)) iterations.
The proof defines φ(z) as the minimum empirical squared error among predictors constrained to output z at the queried context-action pair.
Convexity and lower semicontinuity of φ support attainment of its minimum and make the confidence-value search well-defined.
Binary search over the weight w tracks a non-decreasing predicted value z_w while maintaining an interval containing the target confidence value.

A.2. Proof of Proposition 1

The proposition constructs a realizable contextual-bandit instance where unseen contexts induce ambiguity among zero-loss regressors. Consequently, the algorithms repeatedly choose the wrong action on first encounters with new contexts.

The instance has two actions, noiseless rewards 1 − ϵ and 0, and a uniform distribution over N contexts.
The regressor class contains the ground-truth predictor plus one predictor per context that reverses the action values only at that context.
Each alternative predictor has population reward (1 − 1/N)(1 − ϵ), hence expected regret (1 − ϵ)/N.
For an unseen context, the version space assigns incompatible high and low values to the two actions, whereas observed contexts make all surviving regressors agree.
The algorithm incurs instantaneous regret 1 − ϵ whenever one of N contexts is encountered for the first time, yielding regret at least min{N, Ω̃(t)}.

A.3. Proofs from Section 4.1

The proofs establish regret guarantees for Algorithm 1 using concentration, covering-number, and disagreement-based arguments, with faster rates under Massart noise. They also clarify that the bounds are high-probability empirically in general but only in expectation under Massart conditions.

Finite predictor classes yield regret bounds expressed through class size, while infinite classes use covering numbers and associated uniform-convergence bounds.The proof handles finite classes by union bounds and infinite classes through covering-number results.
The proof maintains nested confidence sets across epochs and uses uniform exploration over plausible actions to connect prediction error with instantaneous regret.The epoch schedule and confidence-set inclusions support the disagreement-based analysis.
Algorithm 1 achieves regret bounds under disagreement- or covering-based distributional conditions, with improved rates under the Massart noise condition.The analysis uses disagreement coefficients, empirical covering numbers, and margin-dependent probabilities to control regret.
An additional empirical-regret conversion incurs an extra O(√T) term, which may dominate the Massart-case bound.Consequently, the general case has a high-probability empirical bound, whereas the Massart result is stated in expectation.
Under Massart noise, choosing the margin parameters to match γ makes the near-tie probabilities Pη and Pη′ equal zero.This removes the corresponding distributional-error terms from the regret analysis.

A.4. Proofs from Section 4.2

The Section 4.2 proofs extend the confidence-set and concentration analysis to general predictor classes and Algorithm 2. They derive moment-condition regret bounds, while warm-start exploration creates a trade-off relative to Algorithm 1.

Algorithm 2 obtains regret guarantees for general predictor classes through concentration inequalities, covering arguments, and epoch-wise confidence sets.The proof extends the finite-class analysis using empirical covering numbers and uniform bounds over predictors and time intervals.
The general-class proof controls predictor-action deviations by summing action-wise concentration bounds and applying a final infimum argument.This extends the action-specific estimates to the full predictor class.
Under the Massart condition, selecting η = γ makes Pη = 0 and yields faster logarithmic-rate bounds for the analyzed algorithms.The same margin condition removes the near-tie contribution from the regret decomposition.
Algorithm 2 can achieve zero regret after warm start when λ ≤ γ, leaving only the warm-start contribution.The result follows because every context lies in the uncertainty region of the optimal action after the warm-start threshold.

B.1. Datasets

The evaluation uses large learning-to-rank and UCI multiclass datasets, converting full-feedback examples into contextual bandit problems with simulated or withheld rewards.

The benchmark contains two learning-to-rank datasets and eight UCI classification datasets evaluated under simulated bandit feedback.The learning-to-rank datasets are MSLR-WEB30K and Yahoo! Learning to Rank Challenge V2.0.
Learning-to-rank instances treat documents as actions and relevance scores in {0,...,4} as rewards, so the learner seeks the most relevant document.The MSLR and Yahoo! datasets contain more than 30,000 queries each.
UCI classification instances use the class index as the action and assign reward 1 for a correct prediction and 0 otherwise.These datasets were previously used for contextual-bandit evaluation.
Validation simulates predictions on held-out examples without allowing the algorithm to incorporate those examples.The resulting validation error approaches instantaneous expected reward according to uniform convergence for the model class.
The study also constructs noisy classification variants with real-valued rewards using reward matrices whose diagonal entries are one and off-diagonal entries are random values in [0,1].This tests performance beyond binary correct-versus-incorrect feedback.

B.2. Benchmark algorithms

The experiments compare RegCB variants with ϵ-Greedy, ILOVETOCONBANDITS, Bootstrap, and supervised-oracle configurations across tuned model classes and confidence parameters.

The benchmark includes ϵ-Greedy, ILOVETOCONBANDITS, Bootstrap, and RegCB variants, with each supplied a model class and optimization oracle.The compared methods use epoch-based updates or bootstrap predictors, depending on the algorithm.
Bootstrap fits a collection of predictors on bootstrap replicates and selects actions using prediction means, variances, and an upper confidence bound.Its confidence parameter β is tuned on the resulting predictions.
The comparison therefore varies both the algorithm and the model-oracle configuration rather than treating the benchmark methods as fixed implementations.The model class and optimization oracle are explicitly described as hyperparameters.
RegCB variants tune β by epoch, while confidence-based methods and exploration baselines are evaluated over logarithmically spaced parameter grids.The grids span 10^2 to 10^-8 for confidence-interval methods and 10^-1 to 10^-8 for ϵ-Greedy and ILOVETOCONBANDITS.

B.3. Oracle implementation

The implementation supports several optimization-oracle formulations, including weighted regression and multiclass classification, for importance-weighted contextual-bandit histories. Benchmark algorithms use different oracle combinations, while predictor classes and incremental RegCB optimization are instantiated with scikit-learn models.

Oracle implementation: Importance-weighted histories can be optimized through weighted multiclass classification or, under realizability, several principled regression reductions.The reductions include importance-weighted regression and regression with importance-weighted targets.
Oracle choices for benchmark algorithms: ϵ-Greedy, Bootstrap, and ILOVETOCONBANDITS require different oracle configurations, with ILOVETOCONBANDITS additionally needing cost-sensitive classification on artificial rewards.ϵ-Greedy uses an importance-weighted argmax, Bootstrap can use a realizable regression oracle, and ILOVETOCONBANDITS requires two oracles.
Label-dependent features: Predictors use either label-dependent feature maps with one base oracle or label-independent features with one predictor class instance per action.The label-dependent construction maps context-action pairs into a shared base feature space, whereas the label-independent construction sets F = G^A.
Predictor class and base oracle implementation: The experiments use real-valued scikit-learn predictors, including GradientBoostingRegressor(max depth=5, n estimators=100), fitted directly through each class’s fit() function.A single oracle is used for label-dependent features; label-independent features require |A| oracle instances.
Incremental implementation for RegCB: For RegCB with gradient boosting, each epoch fixes the regression-tree structure while re-optimizing ensemble and leaf weights within the epoch.The tree ensemble is selected from the data accumulated before the epoch begins.