PaperlayerView exact revision on arXiv

Source-linked AI summary

A Contextual Bandit Bake-off

Alberto Bietti, Alekh Agarwal, John Langford

arXiv:1802.04064v5stat.MLcs.LG

TL;DR

Practical contextual-bandit algorithms have seen progress, but their empirical behavior remains poorly understood. The paper evaluates oracle-based methods on a large collection of supervised-learning datasets converted to simulated bandit feedback. RegCB performs best overall, with greedy a close second, while the study is limited to stationary datasets.

  • Problem

    Practical contextual-bandit algorithms remain poorly understood empirically, despite the importance of exploration and difficulties in evaluating interactive problems across many real-world tasks.

    Source: §1 · p. 2

  • Method

    The paper evaluates practical algorithms relying on supervised-learning optimization oracles on more than 500 supervised-learning datasets converted to simulated bandit feedback.

    Source: §1 · p. 2

  • Results

    RegCB performs best overall, with greedy a close second that often outperforms most exploration algorithms.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The study offers practitioners a reference for implementations and highlights loss estimation and feedback encoding as consequential design choices.

    Source: §5 · p. 20

    The study uses stationary datasets and does not cover practical complications such as delayed or batched rewards, varying action sets, or action-subset heuristics.

    Source: §5 · p. 21

Abstract

from arXiv · show

Contextual bandit algorithms are essential for solving many real-world interactive machine learning problems. Despite multiple recent successes on statistically and computationally efficient methods, the practical behavior of these algorithms is still poorly understood. We leverage the availability of large numbers of supervised learning datasets to empirically evaluate contextual bandit algorithms, focusing on practical methods that learn by relying on optimization oracles from supervised learning. We find that a recent method (Foster et al., 2018) using optimism under uncertainty works the best overall. A surprisingly close second is a simple greedy baseline that only explores implicitly through the diversity of contexts, followed by a variant of Online Cover (Agarwal et al., 2014) which tends to be more conservative but robust to problem specification by design. Along the way, we also evaluate various components of contextual bandit algorithm design such as loss estimators. Overall, this is a thorough study and review of contextual bandit methodology.

1. Introduction

The paper asks how contextual-bandit learning and exploration should be done in practice, where empirical behavior of practical methods remains poorly understood. It evaluates oracle-based algorithms on more than 500 simulated datasets and reports that RegCB performs best overall, with greedy a close second.

1. Introduction

  • Practical algorithms are needed because many existing methods remain poorly understood empirically, while some are intractable for sparse, high-dimensional data or can explore overly conservatively.The paper also notes that UCB methods make strong modeling assumptions and may have uncontrolled regret when those assumptions fail.Source: §1 · pp. 1–3
  • The study evaluates practical methods using supervised-learning optimization oracles and online implementations, including RegCB, bootstrap Thompson sampling, Cover, ϵ-greedy, and greedy.It also examines loss encodings and reduction techniques for methods that use off-policy learning.Source: §1 · p. 2
  • More than 500 supervised-learning datasets are converted into contextual-bandit instances by treating labels as actions and revealing only the chosen action’s loss.The collection spans multiclass, multilabel, and cost-sensitive data; the setup captures the i.i.d. setting but avoids nonstationarity.Source: §1 · p. 2
  • RegCB performs best overall across the evaluated conditions, with the simple greedy baseline a close second and often ahead of most exploration algorithms.The figure compares relative loss to supervised learning on datasets with at least five actions and shows that Greedy and RegCB can both be outperformed by Cover-NU on some datasets.Source: §1 · p. 2, Figure 1 · p. 3

1.1 Organization of the paper

  • The paper proceeds from background and experimental setup to algorithm descriptions, empirical results, and a final discussion of practitioner guidance and open theoretical questions.Source: §1.1 · p. 3

2. Contextual Bandit Setup

The section sets out an i.i.d. contextual-bandit problem and describes algorithms built around supervised-learning optimization oracles. It then explains loss-estimation reductions and the simulated-dataset, online-learning setup used in the experiments.

2.1 Learning Setting

  • The learner observes contexts and chooses actions but sees only the chosen action’s loss, trading off exploration and exploitation against the best policy in a policy class.Contexts and loss vectors are drawn independently from a fixed distribution in the stochastic setting.Source: §2.1 · p. 4

2.2 Optimization Oracles

  • The study focuses on contextual-bandit algorithms that use supervised-learning-style optimization oracles, especially cost-sensitive classification and regression oracles.Exact oracle solutions can be impractical, particularly for CSC; the paper instead uses online oracles that incrementally update policies or regressors.Source: §2.2 · pp. 4–5

2.3 Loss Estimates and Reductions

  • Loss estimates can support off-policy learning through a CSC objective; IPS is unbiased when an action has positive probability but can have high variance at small propensities.Doubly robust estimation uses a separate loss predictor to reduce variance when it estimates observed losses well, while IWR directly reduces to a regression oracle and is suited to off-policy methods.Source: §2.3 · pp. 5–6
  • IWR avoids CSC’s action-scaled online updates by updating only the chosen action, but it is not directly applicable to algorithms that explicitly reduce to CSC with designed cost vectors.The paper also considers regression-based loss estimation and notes that IWR can use importance-weight-aware online updates for large inverse propensities.Source: §2.3 · p. 6

2.4 Experimental Setup

  • Experiments simulate bandit feedback from multiclass, multilabel, and cost-sensitive datasets, use Vowpal Wabbit online oracles, and treat loss encoding as a design choice.The algorithms use linear parameterizations in the experiments, while the paper notes that they extend to more general feature maps.Source: §2.4 · pp. 7–8

3. Algorithms

The section presents online contextual-bandit algorithms built around supervised-learning oracles, contrasting explicit exploration strategies with regression-based confidence bounds.

3. Algorithms

  • The algorithms share an explore/learn loop that computes an action distribution, observes the chosen action’s loss, and updates policies or regressors through supervised-learning oracles.Some methods use off-policy updates alone, while Cover and RegCB also make more specialized oracle calls.Source: §3 · p. 8

3.1 ϵ-greedy and greedy

  • ϵ-greedy mixes greedy choice with uniform exploration; Greedy omits explicit exploration and relies on context diversity, while active ϵ-greedy often improves basic ϵ-greedy but is often outperformed by other methods.Under appropriate assumptions, context diversity can give Greedy nonzero selection probability for every action.Source: §3.1 · pp. 8–9

3.2 Bag (Online Bootstrap Thompson Sampling)

  • Online Bootstrap Thompson sampling approximates a posterior over policies with online bootstrap samples and uses their full action distribution for loss estimation and off-policy learning.The online bootstrap uses a Poisson(1) number of updates per policy per round; the IPS and DR variants were outperformed by IWR in the experiments.Source: §3.2 · pp. 9–10

3.3 Cover

  • Cover trains a sequence of policies with modified cost-sensitive examples that favor actions underrepresented by earlier policies; Cover-NU removes uniform exploration outside covered actions.The diversity reward decays for actions already covered, and Cover-NU was introduced because uniform exploration could be highly inefficient.Source: §3.3 · pp. 11–12

3.4 RegCB

  • RegCB uses regression-oracle confidence intervals: its optimistic variant selects the smallest lower bound, while elimination explores uniformly among plausibly best actions; it requires a known loss range.The confidence bounds are based on worst-case predictions among regressors with small excess squared loss.Source: §3.4 · pp. 12–13

4. Evaluation

Across simulated contextual-bandit tasks built from supervised datasets, RegCB-optimistic performed best overall; Greedy was a close competitor under -1/0 encoding, while Cover-NU offered robustness and randomized exploration logs. Results also show trade-offs across dataset conditions, reductions, encodings, and offline evaluation.

Evaluation setup

  • The evaluation simulated bandit feedback across 516 multiclass, five multilabel, and three cost-sensitive datasets, comparing methods by progressive validation loss and heuristic significant win-loss differences.Datasets were evaluated in one or more fixed, shuffled orders; progressive validation loss captures the explore-exploit trade-off and generalization.Source: §4 · pp. 14–15

Efficient exploration methods

  • RegCB-optimistic had the best overall performance; under -1/0 encoding, Greedy came close and beat other methods on many datasets, while Cover-NU was competitive.Source: Table 1 · p. 15, §4 · pp. 15–16

Variability with dataset characteristics

  • RegCB-opt was preferred in most settings and dominated on larger datasets, while Cover-NU did better with small samples, large action spaces, or high-dimensional features, and Greedy could lead on easy datasets.The paper relates RegCB's stronger performance on larger datasets to favorable noise conditions; Cover-NU's more conservative exploration can be more effective early or with larger action spaces.Source: §4 · pp. 16–17

Reductions

  • For Bag and ϵ-greedy, IWR outperformed other reductions; its computational cost is independent of the total action count, making Bag with IWR a candidate when Cover-NU or RegCB are impractical.IWR only requires updates for the chosen action.Source: §4 · pp. 17–18, Table 3 · p. 18

Encodings

  • -1/0 was the better overall encoding, though 0/1 could perform better on larger datasets; -1/0 can reduce variance when binary costs are often 1.Shifting real-valued RCV1 costs did not improve results, while MSLR and Yahoo showed some improvement with costs shifted to [-1, 0].Source: Table 4 · p. 18, §4 · p. 18

Counterfactual evaluation

  • Efficient exploration methods gave poor IPS estimates for the uniform random policy, while uniform exploration in ϵ-greedy yielded better estimates, especially on larger datasets.The results indicate a trade-off between efficient exploration and counterfactual evaluation; broad offline evaluation may require uniform exploration.Source: Figure 3 · p. 19, §4 · pp. 19–20

5. Discussion and Takeaways

The evaluation finds that worst-case robustness can lead methods to over-explore, while methods that limit or forgo explicit exploration often perform better empirically. The discussion offers practitioner guidelines and notes limitations of the study; Appendix A describes online oracle implementations.

5. Discussion and Takeaways

  • Worst-case theoretical robustness often forces methods to over-explore, while RegCB, Cover-NU, and Greedy limit or forgo explicit exploration and dominate empirically.The study also stresses the importance of loss estimation and feedback encoding for practical performance.Source: §5 · p. 20
  • Distribution-modeling methods such as RegCB, and sometimes Greedy, are often preferred to robust approaches such as Cover-NU, especially on larger or easier datasets.Domain knowledge may help design feature representations that improve prediction and, in turn, exploration for these methods.Source: §5 · p. 20
  • Uniform exploration usually hurts empirical performance, but may be necessary on the hardest datasets or for offline counterfactual evaluation..Source: §5 · p. 20
  • For reduction-based methods, DR is preferred over IPS, while IWR is typically best for ϵ-Greedy and Bag and also offers computational benefits.Source: §5 · p. 20
  • Cost encodings matter: -1/0 is a good default for binary outcomes when observed loss is often 1, and random tie-breaking or a shared additive baseline can mitigate pessimistic initial estimates.Source: §5 · p. 21

Appendix A. Algorithm Details

  • Appendix A implements online regression with adaptive gradient updates, reduces cost-sensitive classification to K regression examples, and supplies online IPS, DR, and IWR updates.The IPS and DR estimators are described as implementing the estimator routine; the online off-policy updates implement the corresponding update routine.Source: Appendix A · pp. 26–27

Appendix B. Datasets

The study constructs contextual-bandit datasets from public multiclass, multilabel, cost-sensitive classification, and learning-to-rank datasets. Its collection includes 516 multiclass datasets, alongside smaller collections for other task types.

Multiclass classification datasets

  • The collection includes 516 OpenML multiclass datasets spanning medical, gene-expression, text, sensory, and synthetic data, including eight datasets used by Foster et al. (2018).Nine previously included datasets were removed after being identified as poorly converted regression datasets.Source: Appendix B · p. 27

Multilabel classification datasets

Appendix B. Datasets

Cost-sensitive classification datasets

  • Cost-sensitive tasks include a multilabel RCV1 variant with tree-distance costs and learning-to-rank datasets with relevance scores converted to losses from 0 to 1.The ranking tasks use Microsoft Learning to Rank and Yahoo! Learning to Rank Challenge data, with action-dependent features and a fixed parameter vector for documents.Source: Appendix B · p. 28

C.1 Algorithms and Hyperparameters

The appendix describes the hyperparameter choices used to evaluate each method. The experiments vary learning rates, reductions, and loss encodings, with fixed choices selected through a voting procedure.

C.1 Algorithms and Hyperparameters

  • Each method was evaluated using algorithm-specific hyperparameters, nine learning rates from 0.001 to 10, three reductions, and three loss encodings.Source: §C.1 · pp. 29–30
  • Fixed hyperparameters for -1/0 encodings were selected by instant-runoff voting over 200 multiclass datasets, which ranked choices by significant wins minus losses.Table 9 records method choices, and Table 10 gives optimized choices for different encodings.Source: Table 9 · p. 30
  • The study also reports optimized hyperparameter choices for -1/0 and 0/1 encodings, used across different tables and figures.Source: Table 10 · p. 30

C.2 Additional Evaluation Results

Additional experiments examine dataset-specific comparisons, counterfactual evaluation, and shared additive baselines. They report that baseline effects can help Greedy and RegCB-opt, while IPS estimates on losses tend to be worse than estimates on rewards.

C.2 Additional Evaluation Results

  • Both RegCB variants become more competitive against other methods with 0/1 encodings in the extended multiclass and multilabel results.The tables report significant wins and losses, including separate dataset-type statistics.Source: §C.2 · p. 31, Table 11 · p. 31, Table 12 · p. 32
  • Greedy can outperform RegCB on some of the eight UCI datasets, while RegCB-opt is often superior to the elimination variant.The experimental setup differs from Foster et al. (2018), which may explain some result differences.Source: §C.2 · p. 31, Table 13 · p. 33
  • Active ϵ-greedy reduces uniform exploration relative to vanilla ϵ-greedy, and its Figure 5 results show improvements under different settings.The figure caption notes that the IWR implementation often outperforms ϵ-greedy despite approximating the active algorithm.Source: §C.2 · p. 31, Figure 5 · p. 35
  • IPS estimates applied directly to losses tend to be significantly worse than IPS estimates applied to rewards.Figure 6 extends the counterfactual evaluation to all algorithms and includes loss-based estimates.Source: §C.2 · p. 31, Figure 6 · p. 36

C.3 Shared baseline parameterization

  • An additive baseline can help Greedy and RegCB-opt adapt quickly to constant losses and mitigate pessimistic zero initialization under -1/0 encoding.The optimized-baseline comparison is shown in Figure 7 and Table 16.Source: §C.3 · p. 32, Figure 7 · p. 37, Table 16 · p. 38
  • With 9/10 encodings, a baseline can help methods reach an unknown loss-estimate range; RegCB was not evaluated because it requires known cost bounds.Source: §C.3 · p. 32

Appendix D. Active ϵ-greedy: Practical Algorithm and Analysis

Active ϵ-greedy reduces uniform exploration using disagreement-based active-learning techniques, and the appendix presents its practical algorithm and theoretical analysis.

Appendix D. Active ϵ-greedy: Practical Algorithm and Analysis

  • The method reduces uniform exploration by borrowing techniques from disagreement-based active learning.The appendix presents the practical algorithm in D.1 and its theoretical analysis in D.2.Source: Appendix D · p. 39
  • Under specific favorable settings, active ϵ-greedy achieves regret O(T^1/3), compared with O(T^2/3) for vanilla ϵ-greedy.Source: Appendix D · p. 39

D.1 Algorithm

Active ϵ-greedy limits exploration to actions that remain plausible under disagreement tests, with practical implementations and regret guarantees described for the method.

D.1 Algorithm

  • Rather than explore uniformly over actions, the method explores an action only when a low-loss policy could choose it instead of the current policy’s choice.Otherwise, it assigns the action the maximum loss; the algorithm assumes a known loss range.Source: §D.1 · p. 39
  • O(T^1/3) regret holds with high probability under favorable disagreement and noise conditions; in the worst case, regret is O(T^2/3), while a positive gap can yield constant regret.Source: §D.1 · p. 40
  • The practical disagreement test estimates empirical loss differences using online cost-sensitive classification oracles based on regression.The method’s practical implementation corresponds to the loss_diff procedure.Source: §D.1 · pp. 39–40
  • In the online setup, the estimated loss difference is approximately the required importance weight divided by the number of examples so far.Source: §D.1 · p. 40
  • For IPS/DR, the implementation estimates how much importance weight is needed to make a candidate action preferred, using online cost-sensitive classification regressors and their sensitivities.The estimate is based on the point where predicted action losses cross.Source: §D.1 · pp. 40–41
  • For IWR, an approximation keeps standard IWR updates but explores only actions that pass a disagreement test.Its importance-weight estimate is the weight needed for the candidate action’s regressor prediction to match the best predicted action.Source: §D.1 · p. 41

D.2 Theoretical Analysis

The analysis studies active ϵ-greedy’s correctness and regret, using a theoretical version of the algorithm and definitions for its samples, losses, and policy disagreement.

D.2 Theoretical Analysis

  • The theoretical analysis covers correctness, a Massart-type low-noise condition, and regret guarantees under worst-case and disagreement conditions.It also considers an extreme setting in which the method can achieve constant regret.Source: §D.2 · p. 41

D.2.1 Algorithm and definitions

  • The analyzed version uses exact cost-sensitive classification oracles, including an oracle constrained to choose a specified action at the current context.Its threshold is defined later; the practical variant instead uses a parameter to avoid requiring policy-class size knowledge.Source: §D.2.1 · p. 41
  • The section defines the full and biased samples, estimated losses, empirical policy losses, expected policy loss, and disagreement between policies.Source: §D.2.1 · pp. 41–42

D.2.2 Correctness

The correctness analysis shows that the optimal policy’s actions remain eligible for exploration and that pruning actions preserves policy quality, then introduces a low-noise condition for faster rates.

D.2.2 Correctness

  • Assigning loss 1 to unexplored actions creates a favorable empirical-sample bias when the optimal policy’s actions are explored.The analysis states that this bias does not hurt identification of the optimal policy.Source: §D.2.2 · p. 44
  • With high probability, the optimal policy’s action is always among those explored.Source: §D.2.2 · p. 44
  • Discarding some actions from exploration does not hurt identification of good policies: the chosen policy remains about as good as under uniform ϵ-exploration.Source: §D.2.2 · p. 45
  • A Massart-type condition requires a positive lower bound on the expected loss gap between the optimal action and the best alternative, and supports a fast rate for considered policies.Source: §D.2.2 · p. 45

D.2.3 Regret Analysis

This section gives regret guarantees for Algorithm 11, including worst-case behavior and improved rates under disagreement and noise conditions.

D.2.3 Regret Analysis

  • In the worst case, Algorithm 11 has an O(T^2/3) regret guarantee, similar to vanilla ϵ-greedy.Source: §D.2.3 · p. 46
  • The analysis extends active-learning disagreement notions to multiclass policies, defining a policy ball around π* under the pseudometric ρ.Source: §D.2.3 · p. 47
  • Under the Massart condition and finite disagreement coefficient θ, regret scales as O(T^1/3) up to logarithmic factors, improving on worst-case guarantees of optimal algorithms.The cited worst-case guarantees include those of Agarwal et al. (2012, 2014) and Dudik et al. (2011a).Source: §D.2.3 · p. 47
  • With a positive gap to every suboptimal policy and finite disagreement coefficient, expected regret is constant and stops accruing for T > T0.Here T0 := max{t : 2∆t > τ}.Source: §D.2.3 · p. 48
Loading 1802.04064v5…