Efficient Optimal Learning for Contextual Bandits

Miroslav Dudik; Daniel Hsu; Satyen Kale; Nikos Karampatziakis; John Langford; Lev Reyzin; Tong Zhang

Source-linked AI summary

Efficient Optimal Learning for Contextual Bandits

Miroslav Dudik, Daniel Hsu, Satyen Kale, Nikos Karampatziakis, John Langford, Lev Reyzin, Tong Zhang

arXiv:1106.2369v1Jun 13, 2011cs.LGcs.AIstat.ML

TL;DR

Contextual bandit learning must compete with a policy class when only the chosen action’s reward is observed. The paper uses a cost-sensitive classification oracle to obtain optimal regret with polylog(N) running time and develops additive dependence on feedback delay.

Problem
Existing contextual-bandit algorithms either have suboptimal regret or require computation linear in the number of policies.
Method
The paper reduces contextual bandit learning to cost-sensitive classification and uses an oracle-based RandomizedUCB algorithm that does not require knowledge of the context distribution.
Results
The algorithm achieves regret O(T K ln N) with running time polylog(N), where N is the number of policies, K the number of actions, and T the number of time steps.
Takeaways & Limitations
The modular oracle formulation lets improvements in cost-sensitive learning apply directly to contextual bandit learning.
Takeaways & Limitations
PolicyElimination is computationally intractable and requires exact knowledge of the context distribution, motivating RandomizedUCB.

Abstract

from arXiv · show

We address the problem of learning in an online setting where the learner repeatedly observes features, selects among a set of actions, and receives reward for the action taken. We provide the first efficient algorithm with an optimal regret. Our algorithm uses a cost sensitive classification learner as an oracle and has a running time $\mathrm{polylog}(N)$, where $N$ is the number of classification rules among which the oracle might choose. This is exponentially faster than all previous algorithms that achieve optimal regret in this setting. Our formulation also enables us to create an algorithm with regret that is additive rather than multiplicative in feedback delay as in all previous work.

1 INTRODUCTION

Contextual bandits reveal only the reward of the chosen action, creating an exploration problem between supervised learning and reinforcement learning. The paper reduces this problem to cost-sensitive classification, achieving optimal regret with running time polylog(N) and extending the analysis to additive delay dependence.

Only the chosen action’s reward is revealed, so contextual bandits require exploration while avoiding full reinforcement learning’s credit-assignment difficulty.
Existing methods either have suboptimal regret or computation linear in the number of policies, despite regret guarantees scaling logarithmically with policy-space size.
The algorithm reduces contextual bandit learning to cost-sensitive classification and uses an oracle to search large policy spaces efficiently.
polylog(N) running time accompanies regret O(T K ln N), where N is the number of policies, K the number of actions, and T the number of time steps.
With delayed feedback, the paper derives regret additive in the delay τ rather than multiplied by a delay-dependent factor.
PolicyElimination provides the basic regret analysis but is computationally intractable and requires exact knowledge of the context distribution.
RandomizedUCB removes the context-distribution requirement, uses an ellipsoid-based oracle subroutine, and retains polylogarithmic dependence on the number of policies.

2 SETTING AND DEFINITIONS

The setting draws contexts and reward vectors i.i.d., reveals only the selected action’s reward, and evaluates the learner against the best policy in a finite policy set. Policies can be accessed by enumeration or through an argmax oracle corresponding to cost-sensitive learning.

2.1 THE SETTING: The policy class Π is a finite set of mappings from contexts X to actions A, with cardinality N.
2.1 THE SETTING: Each round samples a context and reward vector from D, reveals the context, selects one of K actions, and reveals only that action’s reward.
2.1 THE SETTING: Policy access is available either by enumerating all policies or through an argmax oracle that selects the best policy on supplied examples.
2.1 THE SETTING: The argmax oracle is a cost-sensitive classification oracle because rewards can be interpreted as negative costs.
2.2 EXPECTED AND EMPIRICAL REWARDS: Using action-selection probabilities from history, the learner forms an unbiased estimate of every policy’s value.
2.2 EXPECTED AND EMPIRICAL REWARDS: The learner’s goal is to achieve small regret relative to the expected cumulative reward of the best policy in Π over T rounds.

3 POLICY ELIMINATION

PolicyElimination constructs distributions over policies that control estimator variance, enabling reliable policy elimination, but its feasibility step is computationally intractable and assumes the context distribution is known.

Core approach: PolicyElimination finds distributions over policies that induce low-variance estimates for every policy’s value.The distribution is obtained through a minimax argument, while later elimination uses the resulting variance control to estimate policy values accurately.
Core approach: The algorithm initializes with all policies and repeatedly solves a feasibility problem before updating its policy set.The feasibility problem is formulated as a game between a prover selecting a distribution and a falsifier seeking violating policies.
Core approach: The minimax feasibility constraints are valid because the objective is linear in the falsifier’s choice and convex in the prover’s choice.Smoothing ensures reciprocal action probabilities remain bounded, so the expectations are well defined.
Analysis: The feasible set of distributions is non-empty, establishing that the algorithm’s variance-control step can be carried out.This existence result underpins the subsequent concentration and regret analysis.
Analysis: With high probability, empirical policy-value estimates remain close enough to their expectations to support elimination of sufficiently suboptimal policies.The analysis uses concentration and a union bound over policies and time steps; policies sufficiently below the best policy are eliminated.
Limitations: PolicyElimination is computationally intractable and requires exact knowledge of the context distribution.These limitations motivate the RandomizedUCB algorithm introduced in the following section.

4 THE RANDOMIZED UCB ALGORITHM

RandomizedUCB addresses PolicyElimination’s explicit policy tracking and distributional-knowledge requirements by using all policies in its optimization and empirical context history instead.

Algorithm design: RandomizedUCB avoids explicit tracking of the good-policy set, allowing its optimization step to consider the full policy space.The method is designed to be implemented with an argmax oracle rather than maintaining a version space.
Algorithm design: RandomizedUCB randomizes over actions according to empirical policy performance rather than selecting the action with the highest upper-confidence bound.This UCB-inspired randomization decreases the frequency of suboptimal policies through a non-uniform variance constraint.
Algorithm design: For each round, RandomizedUCB approximately solves an optimization problem, samples an action from the induced distribution, and observes its reward.The action distribution is smoothed before sampling, supporting importance-weighted reward estimation.
Algorithm design: The algorithm uses previously observed contexts instead of assuming exact knowledge of the context distribution.The approximation’s effect is quantified in Theorem 6.
Results: Theorem 5 gives RandomizedUCB a high-probability regret guarantee for distributions over contexts and reward vectors with K actions and N policies.The supplied passage states the theorem’s setting and guarantee but does not include the complete bound.
Analysis: Theorem 6 establishes that empirical variance estimates are close to their population counterparts uniformly over distributions, policies, and sufficiently large time steps.The guarantee holds with probability at least 1 −δ for all distributions P, policies π, and t ≥ 16K log(8KN/δ).
Analysis: Lemma 7 bounds each round’s optimization value, ensuring distributions focus mostly on policies with low estimated regret while controlling variance for good policies.This makes the optimization objective a surrogate for minimizing regret.

5 USING AN ARGMAX ORACLE

The paper solves RandomizedUCB’s optimization problem through a convex formulation, separation oracles, the ellipsoid method, and repeated calls to an argmax oracle.

Results: The resulting runtime depends on the policy representation size through log N rather than scaling linearly with the number of policies.This implements the paper’s efficient search over large policy spaces using a cost-sensitive classification oracle.
Oracle implementation: The ellipsoid method decides convex-program feasibility by querying a separation oracle and performing polynomial additional processing.Its iteration bound depends on the dimension and the ratio between outer and inner radii.
Convex formulation: The optimization problem is transformed into a convex program over the convex hull of policy vectors.A distribution over policies corresponds to a point in this convex hull, and the induced action probabilities are obtained from that point.
Oracle implementation: An argmax oracle performs linear optimization over the policy-vector convex hull using one oracle invocation.The oracle query encodes the relevant context sequence and reward vector from the linear objective.
Oracle implementation: The separation oracle checks linear and convex constraints, using AMO to identify violated policy constraints and the perceptron algorithm to test convex-hull membership.Violations yield separating hyperplanes through subgradients of the relevant convex functions.
Results: Theorem 11 provides an iterative procedure that either declares infeasibility or outputs a policy distribution satisfying the required constraints.Each iteration uses one AMO call and O(t^2K^2) processing time, while the iteration count is O(t^5K^4 log^2(tK/δ)).

6 DELAYED FEEDBACK

The delayed-feedback setting reveals rewards after a τ-step delay, so Algorithm 3 modifies the original procedure to handle delayed observations. The resulting theorem shows that delay affects regret additively.

A τ-step delay means the learner observes reward r_t−τ for action a_t−τ under context x_t−τ.
The delayed procedure processes each round by observing x_t, selecting a_t, and observing reward r_t.
Algorithm 3 incorporates delay by suitably modifying Algorithm 1.
Theorem 12 gives a high-probability regret bound for DelayedPE over distributions, policy sets, action counts, and delay intervals.
The proof preserves the variance bound because it depends only on the context distribution.
The analysis uses a Freedman-style inequality controlling cumulative conditional variances and one-sided deviations of reward-related random variables.

B Minimax Theorem

This section states a continuous version of Sion’s Minimax Theorem for compact convex sets and a function with opposing convexity and concavity conditions.

The theorem assumes W and Z are compact, convex sets and f: W × Z → R is continuous.
For every fixed Z, f is convex and continuous in W, while for every fixed W, f is concave and continuous in Z.

C Empirical Variance Bounds

The analysis controls empirical variance estimates by approximating arbitrary policy distributions with sparse sampled distributions and establishing uniform convergence over policies and times.

Sparse[m] contains distributions represented as averages of m delta functions over policies.
An arbitrary distribution P is approximated by independently sampling policies from P to form a sparse distribution eP.
Lemma 15 provides a high-probability uniform convergence statement over times, policies, and sparse distributions.
The variance comparison for the sparse distribution is expressed as V_eP,π,t ≤ (1 + λ) · bV_eP,π,t.
Lemma 16 guarantees a sparse eP whose true and empirical variance-related quantities remain close to those of P under a γ-dependent bound.
The proof uses concentration for Bernoulli averages, Chernoff bounds, Jensen’s inequality, AM/GM, and union bounds.
Combining the approximation inequalities yields the main uniform convergence result in Theorem 6.
For t ≥ 16K log(8KN/δ), the analysis bounds the relevant variance expression by (1 + ǫ) · bV_P,π,t + (7500/ǫ^3) · K.

D Analysis of RandomizedUCB

The RandomizedUCB analysis develops concentration and variance bounds using algorithm-specific quantities, time thresholds, slack allowances, and Freedman’s inequality. These components support the treatment of policy estimates over time.

The analysis introduces constants and algorithm-specific quantities, including a non-increasing exploration parameter µ_t and time indices t_0 and t_1.
Theorem 6 contributes a factor ǫ^3 to the relevant bound, while the constant ≥5 is central to a lemma controlling optimal-policy reward-estimate variance.
The threshold t_1 is ⌈16K log(8KN/δ)⌉ and is associated with a high-probability bound holding for all policies at later rounds.
The analysis uses empirical expectations over previously observed contexts and defines policy-dependent variance quantities.
The allowance of slack K in the optimization constraints is arbitrary up to O(K), provided other constants are adjusted.
Lemma 18 bounds the quantities associated with policy reward-estimate variance before and after t_1.
The deviation bound for η_t(π) is stated in terms of the variance quantities introduced in the analysis.
Lemma 19 gives a high-probability bound simultaneously for policy pairs and times after t_0, using Freedman’s inequality and a union bound.

D.3 Variance Analysis

The variance analysis establishes bounds under Condition 1 that control estimated variance for the optimal and selected policies, and relate large variance to policy gaps. These results support bounding the optimization value and subsequent regret.

Assumptions: Condition 1 requires deviation bounds (D.1) and (D.2) to hold after specified rounds for individual policies and policy pairs.The bounds apply for t ≥ t1 and t ≥ t0, respectively.
Variance bounds: If a policy’s variance exceeds θK, Lemma 20 constrains the optimization distribution so that the policy receives sufficient probability mass.This follows from the optimization constraint and the slack condition used in Lemma 17.
Variance bounds: Lemma 21 bounds the maximum variance of the optimal policy and the policy selected at each round by θK.The proof uses induction, Lemma 20, deviation bounds, and contradiction arguments.
Consequences: Corollary 22 follows from Lemma 21 and deviation bounds, providing the corresponding high-probability control for all t ≥ t0.The corollary is stated under the assumptions of Lemma 21.

D.4 Regret Analysis

The regret analysis bounds the optimization value through a structured feasible solution and relates that value to instantaneous regret. It then sums these bounds and applies concentration to obtain the main regret guarantee.

Optimization value: The optimization program is constructed through convex sets and weighted components, yielding a feasible solution for the non-uniform constraints.The construction uses sets C_i, weights w_i, and bounds on Δ_t−1(W_i).
Instantaneous regret: Lemma 25 relates the optimization value OPT_t to the expected instantaneous regret of a policy drawn from P_t.The relationship holds for all t > t1 and is used in the final summation.
Main regret bound: The main proof bounds regret through the first t1 rounds by t1 and then applies the variance condition for every t ≥ t1.The result is stated for arbitrary context-reward distributions, K actions, and N policies with probability at least 1 − δ.
Main regret bound: Summing the per-round bound from t = t1 + 1 through T and applying Azuma’s inequality produces the high-probability regret result.A final union bound also accounts for failure of Condition 1.

E Details of Oracle-based Algorithm

The oracle-based implementation solves relaxed convex programs with the ellipsoid method, using AMO calls to separate constraints and construct approximate distributions over policies. A perceptron-based rounding step converts solutions into explicit policy distributions.

Relaxed program: The algorithm drops time subscripts for exposition and applies the ellipsoid method to a relaxed program A′ with perturbation parameter δ.The relaxation ensures a feasible region with non-negligible volume and uses δ ∈ (0, b/4).
Rounding: After solving the relaxed program, the perceptron-based rounding step yields an explicit distribution P whose induced point is within 2δ of the relaxed solution.Lemma 26 then supplies the stated bounds for the rounded distribution.
Running time: The implementation requires O(t2K2 · log(tK/δ)) ellipsoid iterations in the stated worst-case bound.Each iteration makes one AMO call and uses additional O(t2K2) processing time.
Separation oracles: AMO computes linear optima over C, allowing the algorithm to test difficult constraints and generate separating hyperplanes.Corollary 28 obtains arg max_{Z∈Cδ} w · Z with one AMO invocation.
Separation oracles: If a candidate lies outside C2δ, Lemma 29 constructs a separating hyperplane; otherwise it produces an explicit policy distribution within distance 2δ.The perceptron procedure finds policies whose convex hull approximates the candidate point.