Bypassing the Monster: A Faster and Simpler Optimal Algorithm for Contextual Bandits under Realizability

David Simchi-Levi; Yunzong Xu

Source-linked AI summary

Bypassing the Monster: A Faster and Simpler Optimal Algorithm for Contextual Bandits under Realizability

David Simchi-Levi, Yunzong Xu

arXiv:2003.12699v5Mar 28, 2020cs.LGmath.STstat.MLstat.TH

TL;DR

Existing contextual-bandit approaches can be theoretically suboptimal or rely on restrictive online-regression access. The paper presents a simple epoch-scheduled algorithm and reduction; its theorem gives optimal regret for batched stochastic contextual bandits with general function classes using O(log log T) batches.

Problem
A prior contextual-bandit algorithm can incur eΩ(T) worst-case regret, while online-regression access is a stronger, relatively restrictive assumption.
Source: §1 · p. 2
Method
The authors present a simple algorithm and reduction with an epoch schedule that naturally handles delayed and batched feedback.
Source: §2.1 · p. 13, §3.2 · p. 21
Results
O(log log T) batches suffice for the optimal regret rate in batched stochastic contextual bandits with general function classes.
Source: §3.2 · p. 21
Takeaways & Limitations
The epoch schedule also accommodates delayed feedback.
Source: §3.2 · p. 21
Online-regression access is stronger and relatively restrictive compared with offline-regression access.
Source: §1 · p. 2

Abstract

from arXiv · show

We consider the general (stochastic) contextual bandit problem under the realizability assumption, i.e., the expected reward, as a function of contexts and actions, belongs to a general function class $\mathcal{F}$. We design a fast and simple algorithm that achieves the statistically optimal regret with only ${O}(\log T)$ calls to an offline regression oracle across all $T$ rounds. The number of oracle calls can be further reduced to $O(\log\log T)$ if $T$ is known in advance. Our results provide the first universal and optimal reduction from contextual bandits to offline regression, solving an important open problem in the contextual bandit literature. A direct consequence of our results is that any advances in offline regression immediately translate to contextual bandits, statistically and computationally. This leads to faster algorithms and improved regret guarantees for broader classes of contextual bandit problems.

1. Introduction

The introduction presents a fast, simple realizability-based reduction from contextual bandits to offline regression for general function classes, motivated by limitations of prior approaches and the hurdles to optimal regret. It outlines the bypassing idea and the analysis, from finite classes to general settings.

1.1. Our Contributions

For general finite F, the algorithm achieves optimal regret with O(log T) offline least-squares regression-oracle calls, reducible to O(log log T) when T is known.The paper describes this as a fast and simple algorithm.Source: §1.1 · p. 3
The algorithm implicitly satisfies sufficient conditions for optimal contextual-bandit learning, reducing computational cost under realizability; the paper notes applications to neural-network and heavy-tailed-reward problems.Its analysis uses a dual interpretation as maintaining a dense distribution over policies and establishes uniform-convergence-type results despite the universal policy space’s potentially huge capacity.Source: §1.1 · pp. 4–5

1.2. Learning Model

Under realizability, the true expected reward function belongs to a general predictor class F, and its reward-maximizing policy is globally optimal.F may contain parametric or nonparametric functions, regression trees, or neural networks; realizability enables stronger performance guarantees.Source: §1.2 · p. 6

1.3.1. Agnostic Approaches

Practicability of these algorithms is heavily restricted because their cost-sensitive classification oracle is computationally intractable even for simple policy classes and typically involves solving NP-hard problems (Klivans and Sherstov 2009, Agrawal and Devanur 2016).They are also memory hungry because they feed augmented versions of the dataset, rather than the original dataset, into the oracle (Bietti et al. 2018).Source: §1.3.1 · p. 7
Agarwal et al. (2012)'s Regressor Elimination achieves optimal regret, but enumerates the whole function class and incurs Ω(|F|) computational cost per round; RegCB is not minimax optimal.An offline-regression-oracle-based algorithm remained unknown in the literature.Source: §1.3.1 · p. 8

1.4. Technical Challenges and Our Approach

An offline regression oracle cannot directly replace the complex optimization over the surviving function set, whose objective is not a sum of squares.This computational hurdle distinguishes square-loss regression from the offline cost-sensitive classification oracle.Source: §1.4 · p. 9
Confidence-bound methods face a statistical hurdle because general-function-class offline regression guarantees average over contexts and cannot generally provide effective per-context guarantees.Foster et al. (2018)'s offline weighted-least-squares confidence-bounds algorithm has guarantees only under strong distributional assumptions.Source: §1.4 · p. 9
Offline regression assumes i.i.d. data, but bandit actions become dependent through exploration and exploitation, complicating analysis with an offline oracle.Online regression oracles handle arbitrary, potentially adaptively generated sequences; Foster and Rakhlin (2020) rely on that stronger guarantee.Source: §1.4 · pp. 9–10

1.4.1. Our Resolution

The authors access the offline oracle in a mostly naive way, avoiding explicit optimization and confidence bounds, then use a dual interpretation to analyze dependent actions and prove statistical optimality.They establish sufficient conditions for optimal contextual-bandit learning under this analysis framework.Source: §1.4.1 · p. 10
The authors introduce “bypassing” based on their understanding of realizability, making their algorithm essentially a consequence of a new classification oracle under realizability.Source: §1.4.1 · p. 10
Their approach also makes new contributions beyond the research lines discussed above, which the authors say are necessary for their arguments.Source: §1.4.1 · p. 11

1.5. Organization and Notations

For pedagogical reasons, the paper presents results first for finite F, then extends them to the general setting, analyzes regret and algorithmic ideas, and concludes.The proofs are deferred to the appendix.Source: §1.5 · p. 11

2. Algorithm and Guarantees

This section presents FALCON, an epoch-based algorithm using offline least-squares regression for finite function classes, and notes its extension to generic function classes and regression oracles. It gives statistically optimal regret guarantees with few oracle calls, including a further reduction in oracle calls when the horizon is known and a regret guarantee that changes by a log log T factor.

2.1. The Algorithm

FALCON combines an epoch schedule, a greedy offline least-squares predictor, and probabilistic action selection with an epoch-varying learning rate—a combination not previously considered.The authors note that the effectiveness of this combination for general contextual bandits is not obvious.Source: §2.1 · pp. 12–13
The epoch schedule yields O(log T) epochs for possibly unknown T and O(log log T) epochs when T is known in advance.Source: §2.1 · p. 12
At each epoch, it uses a greedy predictor from the least-squares oracle directly on contexts, without augmented data, maintained weights, or extra optimization.Source: §2.1 · pp. 12, 14
FALCON predicts action rewards greedily, then randomizes toward higher-predicted actions, with exploration decreasing as the learning rate increases across epochs.Non-greedy action probabilities scale inversely with the predicted reward gap and learning rate.Source: §2.1 · p. 13
The epoch-varying learning rate is required for unknown T or fewer than log T oracle calls and yields tighter logarithmic regret bounds than a fixed rate.Source: §2.1 · p. 14
The analysis handles shared structure across rounds by tracing how exploration in early rounds benefits exploitation later.The authors describe this analysis as conceptually novel.Source: §2.1 · p. 14

2.2. Theoretical Guarantees

FALCON’s regret removes the superfluous sqrt(log T) factor in Agarwal et al. (2012) and matches their lower bound up to a constant or sqrt(log log T) factor.Theorem 1 assumes an epoch schedule with τ_m ≤ 2τ_(m−1) for m > 1 and τ_1 ≤ 2; its guarantee holds with probability at least 1 − δ.Source: §2.2 · p. 15
For possibly unknown T, FALCON uses O(log T) least-squares regression-oracle calls across T rounds, plus O(K) additional cost per round.It runs in O(log T) epochs and calls the oracle once per epoch.Source: §2.2 · p. 15
For a general finite function class, ILOVETOCONBANDITS, SquareCB, and RegCB require more oracle calls or harder-to-implement oracles than FALCON.The passage describes ILOVETOCONBANDITS as requiring eO(·) offline cost-sensitive classification calls, SquareCB as requiring O(T) online regression calls, and RegCB as requiring O(T^(3/2)) weighted least-squares calls.Source: §2.2 · p. 15
When T is known, FALCON reduces oracle calls to O(log log T) while retaining the same regret guarantee up to a log log T factor.This uses an epoch schedule specified for the known horizon.Source: §2.2 · p. 15

3. General Offline Regression Oracles

This section extends the contextual-bandit reduction to arbitrary offline regression oracles and function classes, using statistical learning guarantees to obtain regret bounds. It also discusses relaxations for approximate realizability, heavy-tailed rewards, and delayed or batched feedback.

3. General Offline Regression Oracles

The general offline oracle returns a predictor from training data and F, which need not belong to F; its learning guarantee bounds squared test-data L2 error under realizability.The assumption allows an arbitrary action-selection kernel and an error guarantee that decreases with sample size.Source: §3 · p. 16
The oracle framework is not limited to least squares and is strictly easier to implement than Foster and Rakhlin (2020)’s online regression oracle for adaptive sequential data.Any oracle satisfying their online requirement can be converted to one satisfying Assumption 2.Source: §3 · p. 17

3.1. Algorithm and Guarantees

FALCON+ sets an epoch-varying learning rate from the offline guarantee and trains its oracle call on only the previous epoch’s data to meet the i.i.d. data requirement.The paper describes this last-epoch-only strategy as a technical choice to avoid a more complicated martingale analysis.Source: §3.1 · p. 17
FALCON+ is rate-optimal whenever its offline regression oracle is rate-optimal, yielding a universal optimal reduction and minimax characterization without Foster and Rakhlin (2020)’s tensorization assumption.For function classes with empirical entropy O(ε^-p), the section uses optimal offline estimation rates to illustrate this transfer to contextual-bandit regret.Source: §3.1 · p. 18
For any function class with a computationally efficient, statistically optimal offline regression oracle, the method yields practical contextual-bandit algorithms with optimal regret.The discussion names high-dimensional parametric, Lipschitz, reproducing-kernel, regression-tree, and random-forest classes as examples.Source: §3.1 · p. 19
The regret bounds typically improve in their dependence on T over prior upper bounds because converting offline estimation error to regret loses little in T.The paper says this enables faster algorithms and improved regret bounds for broader contextual-bandit classes.Source: §3.1 · p. 19

3.2. Discussion

Exact ERM solutions are unnecessary: predictors may come from iterative optimization or online/streaming computation, with optimization error included in the offline learning guarantee.Assumption 2 does not restrict how the offline predictor is generated.Source: §3.2 · p. 20
Realizability may be approximate if the offline guarantee upper-bounds the predictor’s population L2 distance to the optimal reward function.The theorem’s proof relies on Assumption 2 rather than realizability itself, allowing a known misspecification error to be incorporated into the guarantee.Source: §3.2 · p. 20
In the misspecified setting, the regret bound is the well-specified bound plus an additive term linear in T, while regret is measured against the globally optimal policy.The discussion notes that this additive term is consistent with existing misspecified-setting results.Source: §3.2 · p. 20
For expected regret, the reduction permits arbitrary reward-noise distributions and unbounded mean-reward scale under a condition on gaps between action means.The stated condition concerns conditional means rather than the full reward distribution.Source: §3.2 · pp. 20–21
Different reward-distribution assumptions affect the bandit results through the offline learning guarantee, enabling offline advances for unbounded or heavy-tailed regression to transfer to contextual bandits.The reduction separates offline regression challenges from the contextual-bandit problem.Source: §3.2 · p. 21
O(log log T) batches suffice for optimal regret because the epoch-based algorithm processes feedback after each epoch and naturally supports delayed or batched feedback.Theorem 2 applies directly to batched stochastic contextual bandits with general function classes.Source: §3.2 · p. 21

4. Regret Analysis

The regret analysis uses randomized policies to connect instantaneous regret with implicit policy regret and examine how exploration and exploitation achieve optimal learning in the universal policy space. It then shows how realizability makes optimization tractable, relaxing policy-class optimization to per-context action-selection probabilities in FALCON.

4. Regret Analysis

The analysis presents the argument for finite context spaces for exposition, while stating that the results also hold for uncountable context spaces.The finite space may be arbitrarily large; the uncountable-space treatment is deferred to Appendix A.7.Source: §4 · pp. 21–22

4.1. A Tale of Two Processes

Sampling a policy before observing the context creates a virtual process with context-independent policy sampling, replacing the harder-to-analyze context-dependent action kernel.The analysis constructs an equivalent policy distribution for the algorithm’s action-selection kernel.Source: §4.1 · pp. 22–23

4.2. Action Selection Kernel as a Randomized Policy

Each action-selection kernel induces a unique product distribution over deterministic policies that reproduces its action probabilities, but the algorithm maintains it implicitly.Computing the product measure can require Ω(|X|) cost, so the distribution is used for statistical analysis rather than implementation.Source: §4.2 · p. 23

4.3. Dual Interpretation in the Universal Policy Space

Expected instantaneous regret equals the randomized policy’s weighted implicit regret, so epoch regret can be analyzed through its policy distribution regardless of the new context.The implicit regret of each deterministic policy is fixed, and the algorithm need not compute the distribution explicitly for this statistical analysis.Source: §4.3 · pp. 24–25

4.4. Optimal Contextual Bandit Learning in the Universal Policy Space

For a deterministic policy, the analysis defines decisional divergence as the context-averaged inverse probability that the randomized policy chooses the same action.The supplied passage introduces this quantity as an observation based on the equivalence between the action-selection kernel and its induced policy distribution.Source: §4.4 · p. 25
The IOP’s feasible solution Qm implicitly balances exploitation of policies with low predicted implicit regret and adaptive exploration across the universal policy space.The paper concludes that these properties, together with its uniform-convergence-type results, suffice for optimal contextual bandit learning in that space.Source: §4.4 · pp. 25, 27
With high probability, implicit-regret prediction error is controlled in relation to policies’ decisional divergence from previously used randomized policies.Policies more similar to past randomized policies have been more implicitly explored, making their predictions more accurate; the bound relies on an epoch-varying learning rate.Source: §4.4 · p. 26
The regret analysis establishes a uniform-convergence-type result for predicted implicit regret, not uniform convergence of absolute regret prediction error across all policies.The proof uses a tailored comparison of regret quantities so predictions for good policies become more accurate, while accuracy for bad policies is not required.Source: §4.4 · p. 26

4.5. Key Idea: Bypassing the Monster

On the universal policy space Ψ, the IOP has a completely decomposed form, letting the algorithm implicitly maintain a dense distribution over all policies while solving it in closed forms at no computational cost.Source: §4.5 · p. 27
Realizability lets the algorithm use a single greedy predictor for implicit policy estimates, making one offline regression-oracle call its main computational cost.Model-based prediction makes guarantees depend on the capacity of F rather than the policy space, and avoids explicitly computing policy estimates or modeling the context distribution.Source: §4.5 · pp. 27–28
Realizability improves predictions and computationally enables removing restrictions on the policy space, allowing the algorithm to bypass the monster.Source: §4.5 · p. 28

4.6. The Birth of FALCON

The thought experiment considers whether ILOVETOCONBANDITS can solve the problem without realizability, given an induced policy class, using inverse propensity scoring for predicted policy reward and regret; OP requires repeated cost-sensitive classification-oracle calls.Source: §4.6 · pp. 28–29
With realizability, a regression predictor estimates policy rewards over the universal policy space, and Lemma 7 unbinds predictor–policy dependence.This moves beyond Lemma 4.3 in Agarwal et al. (2012), which motivates Lemma 7.Source: §4.6 · p. 29
Relaxing OP from Π to Ψ yields IOP, which decomposes by context; FALCON selects actions with probabilities inversely proportional to predicted reward gap times γ_m.Source: §4.6 · p. 29

5. Concluding Remarks

The paper presents a provably optimal contextual-bandit algorithm based on an offline regression oracle, addressing an open problem. It also identifies a limitation in the dependence on the number of actions for linear contextual bandits and connects realizable and agnostic approaches.

5. Concluding Remarks

The paper gives the first provably optimal offline-regression-oracle-based algorithm for general contextual bandits, solving an important open problem.It reduces online decision-making to a well-studied offline supervised-learning problem.Source: §5 · pp. 29–30
Follow-up work extended the results to infinite actions (Xu and Zeevi 2020b), instance-dependent guarantees (Foster et al. 2020), non-stationary contextual bandits (Luo 2021), and unknown misspecification (Krishnamurthy et al. 2021).Source: §5 · pp. 29–30
In linear contextual bandits, the regret bound has worse dependence on K than LinUCB, and improving general dependence on K remains open.The authors attribute this limitation to the probabilistic selection strategy not fully using special properties of some function classes.Source: §5 · p. 30
The work establishes new connections between policy-based agnostic and value-function-based realizable contextual bandits.The authors hope the techniques and perspectives will find broader applications in reinforcement learning with function approximation.Source: §5 · p. 30

A. Proof of Theorem 1 and Theorem 2

The appendix proves Theorems 1 and 2 through a unified analysis under two distinct learning setups. It also addresses measurability for uncountable context spaces.

Setup 1 and Setup 2

Setup 1 assumes finite F, realizability, and rewards bounded in [0,1], whereas Setup 2 allows f* outside F and unbounded or heavy-tailed rewards under Assumption 2 and condition (5).Source: A. Proof of Theorem 1 and Theorem 2 · p. 33

Setup 1

Setup 1 permits data reuse across epochs and does not require geometrically growing epoch lengths.The appendix relates Setup 1 to using martingale concentration results for additional properties.Source: A. Proof of Theorem 1 and Theorem 2 · p. 33

Proof strategy

The appendix gives a detailed proof of both theorems that follows the proof sketch and uses a unified analysis.Source: A. Proof of Theorem 1 and Theorem 2 · p. 33

Measurability

The Section 4 proof assumes finite X to avoid measurability issues; Appendix A.7 treats uncountable X and presents a fix.The authors state that this establishes the generality of their results.Source: A. Proof of Theorem 1 and Theorem 2 · pp. 33–34

A.1. Definitions

The section defines the history, epoch, policy-space, variance, and regret quantities used in the analysis.

A.1. Definitions

Υ_t denotes the sigma-algebra generated by the interaction history through round t, and m(t) identifies the epoch containing round t.Source: §A.1 · p. 34
Ψ denotes the universal policy space A^X, and V_t(π) is the maximum V(p_m, π) over epochs before the current epoch.Source: §A.1 · p. 34
d Regt(π) is defined as bRt(π b fm(t)) − bRt(π), the difference between bRt evaluated at π b fm(t) and bRt evaluated at π.Source: §A.1 · p. 34

A.2. High-probability Events

Lemmas 1 and 2 establish high-probability events for Setup 1 and Setup 2, respectively. Each event holds with probability at least 1 − δ/2.

A.2. High-probability Events

The appendix introduces Lemmas 1 and 2 as basic concentration results for the two setups.The lemma statements and subsequent union-bound steps define the high-probability events used later.Source: §A.2 · pp. 34–35
For Setup 1, Lemma 1 gives a bound for every m ≥ 2 with probability at least 1 − δ/(2m^2), yielding event Γ1 with probability at least 1 − δ/2.The proof is omitted and follows results of Agarwal et al. (2012), with modified union bounds and the definition of γm.Source: §A.2 · p. 34
For Setup 2, Lemma 2 gives a bound for every m ≥ 2 with probability at least 1 − δ/(2m^2), yielding event Γ2 with probability at least 1 − δ/2.The provided passages identify the lemma and event but do not state the bound itself.Source: §A.2 · p. 35

A.3. Per-Epoch Properties of the Algorithm

The section analyzes each epoch by representing the algorithm’s action-selection kernel as a randomized policy over deterministic policies. It establishes properties connecting that representation to regret and prediction.

A.3. Per-Epoch Properties of the Algorithm

The action-selection kernel pm(· | ·) has an equivalent probability measure Qm over policies, which represents the same action probabilities.The section calls Qm the “equivalent randomized policy” induced by pm.Source: §A.3 · pp. 35–36
The expected instantaneous regret of pm equals the implicit regret of its induced randomized policy Qm.This equivalence lets the regret analysis focus on the induced policies’ implicit regret.Source: §A.3 · p. 36
Qm controls its predicted implicit regret relative to the greedy policy based on bfm within K/γm, with this error shrinking across epochs.The passages characterize this as a per-epoch property of the algorithm.Source: §A.3 · p. 36
For a deterministic policy, the decisional divergence from Qm is bounded by that policy’s predicted implicit regret.The divergence is described through the probability that the randomized and deterministic policies choose the same action over a random context.Source: §A.3 · p. 37

A.4. Bounding the Prediction Error of Implicit Rewards

This section relates prediction error in implicit rewards to the value Vt(π). Its statements apply after τ1 under the corresponding high-probability event for either setup.

A.4. Bounding the Prediction Error of Implicit Rewards

The section bounds the prediction error of a policy’s implicit reward in relation to its value Vt(π).The stated relationship is conditioned on Γ1 under Setup 1 or Γ2 under Setup 2.Source: §A.4 · p. 37
The result applies for rounds t > τ1 when Γ1 holds in Setup 1 or Γ2 holds in Setup 2.For Setup 1, the argument takes s0 = 1; the Setup 2 argument uses Γ2.Source: §A.4 · pp. 37–38
For policy π, the proof writes bRt(π) − R(π) = Eₓ∼Dₓ[Δₓ] and derives a bound using Cauchy–Schwarz, equation (9), and convexity of the ℓ1 norm.Source: §A.4 · p. 38

A.5. Bounding the Prediction Error of Implicit Regret

The section relates predicted implicit regret to true implicit regret under Γ1 or Γ2. Its stated bound applies across epochs, rounds, and policies, with c0 set to 5.15.

A.5. Bounding the Prediction Error of Implicit Regret

The lemma’s accuracy property improves for “good policies,” while predicted implicit regret for “bad policies” need not have that property.The proof establishes the result by induction over epochs.Source: §A.5 · pp. 39, 41
Under Γ1 or Γ2, Lemma 8 bounds the predicted implicit regret of every policy across all epochs and rounds, with c0 := 5.15.The statement applies under the corresponding setup and high-probability event.Source: §A.5 · p. 39
The inductive proof’s Setup 2 base case uses condition (5).The proof then assumes the claim for earlier epochs to establish the step for epoch m > 1.Source: §A.5 · p. 39

A.6. Bounding the True Regret

The appendix combines the bounds for both setups to prove Lemma 10 and derive theorem and corollary results. Its proof also establishes a high-probability regret bound and identifies cases where bounded rewards or realizability are unnecessary.

A.6. Bounding the True Regret

Bounded rewards are not required when the goal is only to bound expected regret.Source: §A.6 · p. 41
Lemma 10 bounds the algorithm’s expected regret after any T rounds in both setups.The supplied statement does not include the bound’s formula.Source: §A.6 · p. 41
The proof establishes a 1−δ high-probability regret bound by combining concentration with the Γ events.The rewards are assumed to lie in [0,1] for this high-probability argument.Source: §A.6 · pp. 41–42
Under Setup 1, Corollary 1 gives an epoch count m(T)=O(log log T).Source: §A.6 · p. 43
Theorem 2’s proof does not require realizability, supporting the stated extension to known misspecification.Source: §A.6 · p. 43

A.7. Dealing with Uncountable Context Spaces

For uncountable context spaces, the proof’s main measurability issue concerns deterministic policies that may not be measurable. The authors resolve it by working with measurable randomized policies, represented by action-selection kernels.

A.7. Dealing with Uncountable Context Spaces

The authors say the universal policy-space analysis clarifies realizability’s role and connects contextual-bandit research lines.Source: §A.7 · p. 44
The analysis directly assumes that the true reward function and regression-oracle predictors are measurable with respect to D_X.The passage says these conditions are needed for regret to be well-defined.Source: §A.7 · p. 44
With uncountable X, some deterministic policies may be non-measurable, leaving policy-based regret quantities undefined.Source: §A.7 · p. 44
Randomized policies avoid the issue: their expected reward is well-defined, and action-selection kernels represent these measurable policies.Source: §A.7 · p. 44
The proof restates its guarantees over measurable randomized policies, where the regret quantities are everywhere defined.The revised lemmas are described as almost identical to the earlier versions.Source: §A.7 · pp. 44–45