Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits

Alekh Agarwal; Daniel Hsu; Satyen Kale; John Langford; Lihong Li; Robert E. Schapire

Source-linked AI summary

Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits

Alekh Agarwal, Daniel Hsu, Satyen Kale, John Langford, Lihong Li, Robert E. Schapire

arXiv:1402.0555v2Feb 4, 2014cs.LGstat.ML

TL;DR

Contextual bandit algorithms must choose actions from context while observing rewards only for selected actions, and general policy classes create computational barriers. The paper develops an oracle-based algorithm that builds sparse policy distributions and updates them infrequently. It retains statistically optimal regret with sublinear total oracle calls and shows strong empirical performance in a proof-of-concept experiment.

Problem
General-policy contextual bandit methods can have computational complexity linear in |Π|, while Randomized UCB has prohibitive oracle-call scaling.
Method
The algorithm uses a cost-sensitive classification optimization oracle, coordinate descent for sparse policy distributions, and epoch-based infrequent updates.
Results
The algorithm attains a statistically optimal regret guarantee with a sublinear total number of oracle calls over T rounds and shows strong empirical performance relative to several baselines.
Takeaways & Limitations
The approach provides a practical, computationally efficient solution for contextual bandits with general policy classes.
Takeaways & Limitations
The method accesses the policy class through an optimization oracle, and the implemented Online Cover variant remains to be directly analyzed.

Abstract

from arXiv · show

We present a new algorithm for the contextual bandit learning problem, where the learner repeatedly takes one of $K$ actions in response to the observed context, and observes the reward only for that chosen action. Our method assumes access to an oracle for solving fully supervised cost-sensitive classification problems and achieves the statistically optimal regret guarantee with only $\tilde{O}(\sqrt{KT/\log N})$ oracle calls across all $T$ rounds, where $N$ is the number of policies in the policy class we compete against. By doing so, we obtain the most practical contextual bandit learning algorithm amongst approaches that work for general policy classes. We further conduct a proof-of-concept experiment which demonstrates the excellent computational and prediction performance of (an online variant of) our algorithm relative to several baselines.

1 Introduction

Contextual bandits combine context-dependent action selection with incomplete feedback, creating a computational challenge for large policy classes. The paper introduces an oracle-based algorithm using sparse policy distributions and infrequent updates to achieve optimal regret with sublinear oracle calls and strong empirical performance.

Problem: Contextual bandits reveal rewards only for the chosen action, despite decisions depending on current context and previous feedback.The setting appears in applications including online recommendation and clinical trials.
Problem: Optimal-regret algorithms can compete with very large policy classes, but their computational complexity is linear in the number of policies.This makes them tractable only for simple policy classes.
Related work: Randomized UCB achieves optimal regret with oracle access, but requires ˜O(T^5) oracle calls over T rounds, making its runtime prohibitive.The oracle provides an exponential speed-up over earlier optimal-regret methods, but the T^5 scaling remains costly.
Method: Epoch structures update the policy distribution infrequently, allowing different trade-offs between concentrated and distributed computation.The paper considers variants ranging from concentrating computation on O(log T) rounds to spreading it across rounds.
Results: The algorithm requires only sublinear total oracle calls in T while retaining an optimal regret guarantee with high probability.The paper also reports a proof-of-concept online variant with low computational complexity and high reward relative to natural baselines.
Method: The proposed algorithm uses coordinate descent to construct a sparse distribution over policies through a small number of optimization-oracle calls.Each iteration obtains a policy from the oracle, and the resulting sparse distribution can be efficiently sampled.

2 Preliminaries

The paper formalizes the i.i.d. contextual bandit setting, policy rewards, regret, inverse-propensity estimates, and oracle-based access to policies. It also specifies smoothed action sampling to control IPS variance.

2.1 Learning Setting: A policy maps contexts to actions, and regret compares its expected reward with that of the highest-reward policy in Π.
2.1 Learning Setting: In each round, contexts and reward vectors are drawn independently, the agent observes the context, chooses an action, and receives only that action’s reward.
2.2 Inverse Propensity Scoring: Inverse propensity scoring transforms interaction records into fictitious reward vectors that assign the chosen action r(a)/p(a) and zero to other actions.
2.2 Inverse Propensity Scoring: The resulting IPS estimate is unbiased for any policy’s expected reward, although estimated regret relative to the empirical maximizer is generally not unbiased for regret relative to π⋆.
2.3 Optimization Oracle: The algorithm accesses Π through an arg max oracle called AMO rather than enumeration, then samples policies and smooths their induced action distribution so every action has probability at least µ.
2.3 Optimization Oracle: Weights over policies may sum to less than one, so remaining mass is assigned to a default policy before smoothed action sampling.

3 Algorithm and Main Results

ILOVETOCONBANDITS combines epoch-based updates with coordinate descent to construct sparse policy distributions satisfying exploitation and exploration requirements. Its oracle implementation achieves strong reductions in oracle calls, while a warm-start variant further lowers computation and a lower bound shows these call bounds are unimprovable under the access model.

Algorithm: ILOVETOCONBANDITS updates the policy distribution only on an epoch schedule while solving the optimization problem (OP) to obtain sampling distributions.The schedule requires epoch lengths satisfying τm+1 − τm = O(τm), with the simplifying condition τm+1 ≤ 2τm.
Algorithm: The optimization problem balances exploitation, by favoring policies with low estimated regret, against exploration, by controlling reward-estimate variance through action coverage.The exploration constraint permits more adaptive exploration than uniform exploration because good policies receive more accurate reward estimates than bad policies.
Oracle complexity: A doubling epoch schedule runs the optimization procedure only O(log T) times and reduces total oracle calls compared with running it every round.Running the procedure every round yields ˜O(KT^3/ln(|Π|/δ)) calls, whereas the more careful schedule substantially reduces this total.
Warm start: Warm-starting from the previous epoch’s weights and using a different schedule guarantees ˜O(√T) calls to Algorithm 2.The warm-start variant uses Qinit := Qm−1, with schedule (τ1,τ2)=(3,5) and τm=m^2 for m≥3.
Lower bound: The lower bound shows that substantially sparser distributions cannot generally satisfy the low-variance constraint, making the oracle-call bounds unimprovable under this access model.The number of oracle calls is at least the support size of the distribution in the paper’s mode of access to the policy class.

4 Regret Analysis

The analysis controls deviations in policy reward estimates through variance constraints and relates true regret to estimated regret. Summing the resulting per-round bounds with martingale concentration yields the final regret guarantee.

Variance constraints control deviations of policy reward estimates after replacing empirical context expectations with expectations over the context distribution.Deviation bounds resolve the mismatch, with worse right-hand-side constants.
High-probability analysis bounds each policy’s expected regret by twice its estimated regret plus O(Kµ_m) within sufficiently large epochs.The condition is τ_m ≥ ˜O(K log |Π|).
The estimated-regret constraint on the epoch’s policy weights combines with the regret comparison lemma to bound conditional expected regret in each round.
Summing the per-round bounds over T rounds and applying martingale concentration gives the final regret bound in Theorem 2.

5 Analysis of the Optimization Algorithm

The optimization algorithm uses a potential function to construct policy weights satisfying regret and variance constraints. Warm starts and epoch scheduling reduce the total number of updates and oracle calls across T rounds.

The potential combines divergence from uniform action distributions with an estimated expected-regret term, so minimizing it promotes exploration and low regret.The induced action distributions may not sum to one, and the divergence is unnormalized relative entropy.
The potential’s partial derivative is tied to each policy’s variance constraint, while coordinate updates increase weights whose derivatives are large and negative.The minimizing weight vector also satisfies the low-regret constraint and has total weight at most one.
When the algorithm halts, its output satisfies the variance and low-regret constraints, with total policy weight at most 1.
Each update decreases the potential, while its initial value and nonnegativity bound the number of Step 8 executions by 4 ln(1/(Kµ))/µ.Step 4 does not increase the potential.
The average number of arg-max oracle calls is ˜O(√(K/(T ln(|Π|/δ)))) per round, so calls occur at a vanishingly low rate.
Warm starts initialize each epoch from the previous epoch’s weights, and the doubling trick bounds the total combined iterations over the first T rounds by ˜O(√(KT/ln(|Π|/δ))).The epoch-to-epoch potential increase is at most ˜O(T ln(|Π|/δ)/K), while each update decreases it by at least ˜Ω(ln(|Π|/δ)/K).

6 Experimental Evaluation

The evaluation compares an online variant of the algorithm with several contextual-bandit baselines on an RCV1-derived task. It reports near-supervised prediction performance alongside substantially lower computational cost than LinUCB.

The overall computational complexity remains at least ˜O((KT)^1.5) plus the total cost of oracle calls, exceeding the typical O(1)-complexity update of ordinary supervised learning.
The online cost-sensitive classification oracle uses stateful one-example updates, reducing each invocation’s complexity to O(1).The implementation reduces CSC to squared-loss regression and is included in Vowpal Wabbit.
The experiment transforms the supervised RCV1 CCAT classification task into a contextual bandit problem with 781265 examples, 47152 TF-IDF features, class-label actions, and reward equal to one minus 0/1-loss.Evaluation uses progressive validation on 0/1 loss.
LinUCB required 59 hours after reducing the representation to 1000 dimensions, whereas a diagonal covariance approximation ran in approximately 1 hour with error 0.137.
The algorithm achieves the best reported loss of 0.0530, with the minimum occurring for a cover set of size 1.Prediction performance is similar with a larger cover set.
The fully supervised reference reaches an error rate of 0.051, while the algorithm is less than 2.3 times slower and nearly achieves this bound.The supervised result is treated as a lower bound on the loss achievable under partial information.

7 Conclusions

The paper presents a practical algorithm for general policy classes that attains statistically optimal regret while using a sublinear total number of oracle calls. An online variant shows promise as a scalable contextual-bandit solution, though its direct analysis is left for future work.

The paper claims the first practical algorithm, to the authors’ knowledge, that is computationally efficient for general policy classes while attaining a statistically optimal regret guarantee.
The total number of oracle calls over all T rounds is sublinear, improving substantially over previous work in this setting.
The implemented online variant is presented as having the practical flavor of a scalable contextual-bandit solution.
Direct analysis of the Online Cover algorithm is identified as future work.

B.3 Reward Estimates

The analysis fixes an epoch schedule and defines reward-estimation quantities using epoch weights and a selected policy distribution. Freedman’s inequality and union bounds then provide simultaneous high-probability control over estimation deviations.

Q_m−1 contains non-negative policy weights computed at the end of epoch m−1.
eQ_m−1 is the distribution formed from Q_m−1 and the policy with the highest reward estimate through epoch m−1.
V_t(π) selects the largest fictitious-reward quantity over earlier epochs for policy π.
With probability at least 1−δ, the stated reward-estimation inequalities hold for every policy, epoch, and round under admissible λ_m−1 values.
Freedman’s inequality and a union bound control the martingale sums because reward-estimation deviations are bounded and conditionally mean-zero.

C Regret Analysis

The regret analysis fixes the failure probability and epoch schedule, then defines a high-probability event collecting the required uniform inequalities. Epoch weights are required to satisfy the optimization constraints at epoch ends.

The analysis fixes δ∈(0,1) and an increasing epoch schedule 0=τ_0<τ_1<τ_2<⋯.
The sequences d_t/t and μ_m are non-increasing in t and m, respectively.
The event E collects the stated uniform bounds over policies, epochs, and rounds, and holds with probability at least 1−δ/2.
At each epoch end, Q_m is computed as a solution to the optimization problem satisfying constraints Eq. (2) and Eq. (3).
The parameter settings require θ_2≥8ρ, ensured by the chosen value of ψ under the stated bound on ρ.

C.3 Proof of Theorem 2

The proof of Theorem 2 uses induction across epochs to convert estimated-regret and variance controls into uniform policy guarantees, then sums these bounds and applies martingale concentration to obtain cumulative regret control.

V_t(π) is large only if policy π had large estimated regret in some previous round.
The probability distribution eQ_m satisfies the required inequalities, with the proof using its construction and optimization constraints.
Lemma 13 compares true and estimated regret for all sufficiently late rounds and epochs under event E.
Induction handles the base epoch and later epochs using bounds on μ_m, d_t/t, and prior-epoch guarantees.
The inductive step combines earlier inequalities and parameter conditions to establish the claimed epoch-wise bound.
Lemma 14 transfers the low estimated-regret optimization constraint into a low regret guarantee for policies.
Summing the per-round guarantee over epochs and applying martingale concentration yields a high-probability cumulative regret bound.
Theorem 2 follows from Lemma 17 and the epoch-schedule relation τ_m(T)≤2(T−1).

D.4 Proof of Lemma 8

This proof bounds changes in the potential function by decomposing them into separate terms. Monotonicity, telescoping sums, regret bounds, and Azuma’s inequality combine to control the total change with high probability.

The potential change is decomposed into separate pieces whose sums are bounded individually.
The analysis assumes the policy-weight vectors satisfy Σ_π Q(π)≤1 and uses this property in subsequent bounds.
Because τ_mμ_m is non-decreasing, one potential term can be essentially disregarded through a telescoping sum.
The parameter condition Kμ_M+1≤1/2 is used in bounding the final-epoch terms.
The proof defines auxiliary variables for the second potential component and controls their deviations with Azuma’s inequality.
Combining the component-wise bounds and applying a union bound gives the stated result with probability at least 1−2δ.

D.5 Proof of Lemma 3

The proof bounds oracle complexity by tracking decreases and increases in a positive potential, including the warm-start initialization at Q0 = 0.

Warm-start potential: Q0 = 0 initializes the algorithm with objective Φ0(Q0) = 0 because τ0 = 0.For small τm, the proof considers the regime µ = 1/(2K), where Lemma 7 gives a decrease of ˜O(τ/K^2).
Potential accounting: N oracle calls decrease the objective by at least Ndτm/(4K), while the net increase is bounded by ˜O(TdT/K).This combines the per-call decrease from Lemma 7 with the bound on the total potential increase.
Oracle-complexity conclusion: Because the potential is always positive, the decrease and increase bounds upper-bound the number of oracle calls.The supplied passage states that this yields an ˜O bound, but its displayed final expression is truncated.

E Proof of Theorem 4

The proof establishes high-probability low-variance constraints for every relevant epoch and policy, then constructs a uniform-context instance showing that satisfying these constraints requires broad policy support. The experimental implementation uses online cost-sensitive oracles, exploration, and doubly robust reward estimation.

Proof of Theorem 4: The constructed instance has N uniformly distributed contexts, action K rewarding 1, all other actions rewarding 0, and (K −1)N policies.Each policy πij takes action j on context i and action K otherwise; under the uniform context distribution, all policies obtain identical reward and zero expected regret.
Proof of Theorem 4: Each πij is uniquely responsible for action j on context i, so any feasible Q must assign positive support to every such policy.If Q assigns no support to πij, the smoothed action probability is µm, violating Eq. (37); this completes the proof.
Experimental implementation: The experimental algorithm sets µ to 0.05 min(1/K, 1/√(tK)) and passes cost vectors to loss-minimization oracles.It initializes n online cost-sensitive minimization oracles controlling n policies and samples actions using U and µ.
Experimental implementation: The implementation uses a doubly robust estimate with an online-trained linear reward function after observing the selected action's reward.The procedure observes xt, samples and selects at, receives rt(at), and updates each oracle.