PaperlayerView exact revision on arXiv

Source-linked AI summary

Efficient Contextual Bandits in Non-stationary Worlds

Haipeng Luo, Chen-Yu Wei, Alekh Agarwal, John Langford

arXiv:1708.01799v4cs.LGstat.ML

TL;DR

Contextual bandit methods usually benchmark against a fixed policy, which is questionable when environments change over time. The paper equips efficient stationary algorithms with non-stationarity tests and derives interval, switching, and dynamic regret guarantees, including parameter-free bounds. It also reports a first efficient dynamic-regret result for fully adversarial contextual bandits and improves the prior parameter-free guarantee for two-armed bandits while generalizing it to contextual settings.

  • Problem

    Most contextual bandit algorithms compete with the best fixed policy, but evolving content and preferences require benchmarks that adapt to non-stationary environments.

  • Method

    The paper equips existing i.i.d. contextual-bandit algorithms with statistical tests that detect distribution changes and restart the algorithms when non-stationarity is detected.

  • Results

    The parameter-free ADA-BINGREEDY algorithm achieves min{S^1/4T^3/4, Δ^1/5T^4/5}, improving and generalizing the prior Δ^0.18T^0.82 two-armed-bandit result.

  • Takeaways & Limitations

    Efficient contextual-bandit algorithms can obtain near-Exp4.S guarantees for interval, switching, and dynamic regret, including under fully adversarial data.

  • Takeaways & Limitations

    The parameter-free guarantees are weaker than tuned guarantees in some regimes, and the paper notes practical drawbacks such as restarting.

Abstract

from arXiv · show

Most contextual bandit algorithms minimize regret against the best fixed policy, a questionable benchmark for non-stationary environments that are ubiquitous in applications. In this work, we develop several efficient contextual bandit algorithms for non-stationary environments by equipping existing methods for i.i.d. problems with sophisticated statistical tests so as to dynamically adapt to a change in distribution. We analyze various standard notions of regret suited to non-stationary environments for these algorithms, including interval regret, switching regret, and dynamic regret. When competing with the best policy at each time, one of our algorithms achieves regret $\mathcal{O}(\sqrt{ST})$ if there are $T$ rounds with $S$ stationary periods, or more generally $\mathcal{O}(Δ^{1/3}T^{2/3})$ where $Δ$ is some non-stationarity measure. These results almost match the optimal guarantees achieved by an inefficient baseline that is a variant of the classic Exp4 algorithm. The dynamic regret result is also the first one for efficient and fully adversarial contextual bandit. Furthermore, while the results above require tuning a parameter based on the unknown quantity $S$ or $Δ$, we also develop a parameter free algorithm achieving regret $\min\{S^{1/4}T^{3/4}, Δ^{1/5}T^{4/5}\}$. This improves and generalizes the best existing result $Δ^{0.18}T^{0.82}$ by Karnin and Anava (2016) which only holds for the two-armed bandit problem.

1. Introduction

The paper addresses contextual bandits in non-stationary environments, where competing with a fixed policy is inadequate, by developing efficient algorithms that detect distribution changes and adapt their learning. It provides interval, switching, and dynamic regret guarantees, including near-baseline performance and parameter-free bounds.

  • Motivation: Non-stationary applications require competing with adaptive policy sequences rather than the best fixed policy in hindsight.The fixed-policy benchmark is natural for stationary data but can be inappropriate when content and preferences evolve.
  • Approach: The proposed algorithms combine stationary contextual-bandit methods with statistical tests that detect non-stationarity and trigger restarts.ADA-GREEDY and ADA-ILTCB extend EPOCH-GREEDY and ILOVETOCONBANDITS, respectively.
  • Guarantees: The analysis covers interval, switching, and dynamic regret, including guarantees against the best policy at each time under slowly drifting distributions.The framework also yields switching guarantees when changes occur through hard distributional switches.
  • Guarantees: ADA-ILTCB achieves almost the same guarantee as the inefficient Exp4.S baseline across all three regret measures.Exp4.S provides a strong baseline but requires maintaining weights for every policy and is not oracle-efficient.
  • Novelty and scope: The dynamic-regret guarantees hold in a fully adversarial setting, which the paper identifies as the first such result for efficient contextual bandits.The paper notes that this data-dependent guarantee can still be linear in T in the worst case.
  • Parameter-free results: The parameter-free ADA-BINGREEDY bound is min{S^1/4T^3/4, Δ^1/5T^4/5}, improving and generalizing the prior Δ^0.18T^0.82 two-armed-bandit result.The parameter-free method addresses unknown non-stationarity quantities and extends the result to multi-armed and contextual settings.

2. Preliminaries

The paper reframes contextual-bandit evaluation for non-stationary environments using interval, switching, and dynamic regret, while defining oracle-efficient learning through policy optimization.

  • Most contextual-bandit work compares against the best fixed policy, a benchmark suited to essentially stationary data.
  • The framework assumes a finite policy class and defines oracle efficiency by polynomial running time and oracle calls in T, K, and ln N.
  • Interval regret measures cumulative regret against a fixed policy over a chosen time interval.
  • Dynamic regret instead compares performance with the best policy at each time, but no sub-linear regret is generally achievable without controlling non-stationarity.
  • Switching regret measures non-stationarity through the number S of stationary segments, whereas variation-based regret handles slowly drifting distributions.

3. Interval Regret

The interval-regret section develops baselines and oracle-efficient algorithms that detect non-stationarity and restart, with ADA-ILTCB improving on ADA-GREEDY under total-variation conditions.

  • Exp4.S provides strong interval-regret guarantees but is not oracle-efficient because it maintains weights for every policy.
  • ADA-GREEDY: ADA-GREEDY extends EPOCH-GREEDY with non-stationarity tests and periodic resets, trading delayed-change risk against extra stationary-environment penalty.
  • ADA-GREEDY: ADA-GREEDY guarantees interval regret for intervals of length at most L and reward variation at most v.
  • ADA-ILTCB: ADA-ILTCB combines ILOVETOCONBANDITS with tests for changes in empirical regret and reward-estimate variance, restarting when either changes significantly.
  • ADA-ILTCB: ADA-ILTCB improves the interval-regret rate over ADA-GREEDY, but its guarantee uses total variation ¯∆I because context variation affects variance control.

4. Implications

Interval-regret guarantees can be converted into switching and dynamic regret bounds by partitioning time into sufficiently stationary intervals. The efficient algorithms approach the inefficient Exp4.S baseline, but tuning remains necessary and some bounds become vacuous under large non-stationarity.

  • Switching Regret: Switching regret follows by partitioning the horizon into i.i.d. subintervals of length at most L and applying interval-regret guarantees.The reduction uses the fact that the best policy remains fixed on each subinterval.
  • Switching Regret: If S is known, setting L = T/S yields an eO(√STK ln N) switching-regret bound for Exp4.S.When S is unknown, alternative choices of L produce incomparable bounds.
  • Switching Regret: Exp4.S bounds become vacuous, Ω(T), when S is large enough but still sublinear in T.This motivates the parameter-free treatment developed later.
  • Dynamic Regret: Known variation measures permit dynamic-regret tuning, whereas ADA-GREEDY and ADA-ILTCB extend interval guarantees to fully adversarial settings through suitable variation tolerances.ADA-ILTCB is better than ADA-GREEDY and comes close to Exp4.S, though it uses the larger variation measure ¯∆.
  • Dynamic Regret: The dependence on K ln(N/δ) in these results is slightly loose and could be tightened.The paper notes this looseness for conciseness.

5. Achieving Switching/Dynamic Regret with No Parameters

The parameter-free ADA-BINGREEDY algorithm addresses the need to tune unknown non-stationarity parameters by incorporating bin-based exploration into ADA-GREEDY. It improves and generalizes the prior two-armed-bandit result, while retaining limitations in interval regret and exploration overhead.

  • Motivation: Unknown S or ∆ causes tuned regret guarantees to degrade and potentially become vacuous, motivating a parameter-free algorithm.The paper seeks bounds whose exponents sum to one, as in the known-parameter case.
  • Results: The parameter-free result improves and generalizes Karnin and Anava’s eO(∆^0.18T^0.82) guarantee, which was limited to two-armed bandits.The paper states this comparison as a significant improvement.
  • Algorithm: ADA-BINGREEDY incorporates bin-based exploration into ADA-GREEDY and extends the approach beyond the two-armed bandit setting.The construction is based on techniques from Karnin and Anava (2016).
  • Algorithm: ADA-BINGREEDY divides blocks into equal-length bins, randomly selects pure-exploration bins, and runs non-stationarity tests only within exploration bins.It also computes an empirical best policy at the beginning of each block.
  • Analysis: Lower reward-estimate variance in pure-exploration bins is crucial to the ADA-BINGREEDY analysis.The paper attributes this to the improved term in its non-stationarity tests.
  • Limitations: The bin-exploration component dominates regret, so combining it with ADA-ILTCB does not improve the parameter-free result.Whether better bounds of this type are possible remains open.
  • Limitations: ADA-BINGREEDY can have poor regret on some intervals because exploration bins yield only a loose eO(T^4) interval-regret bound.The paper identifies this as a limitation of the approach.

6. Conclusions

The paper takes a first step toward non-stationary contextual bandits by proposing algorithms and guarantees under several regret notions. It also identifies long-term memory and simpler, more practical algorithms as future directions.

  • The work studies non-stationary contextual bandits through several new algorithms and achievable results under various regret notions.
  • Future work includes algorithms with long-term memory to identify distributions experienced before.
  • The current methods have impractical aspects such as restarting, motivating simpler and more practical algorithms.

Appendix B. Exp4.S Algorithm and Proofs

Exp4.S maintains a distribution over policies and updates it multiplicatively using loss estimates, with exploration mixed into the updated distribution. Its proof partitions the horizon into subintervals and sums interval-wise regret bounds.

  • Exp4.S initializes a uniform policy distribution and updates it multiplicatively using estimated losses.
  • The algorithm mixes the updated policy distribution with uniform exploration using parameter µ.
  • Exp4.S is a direct contextual generalization of Exp3.S and uses loss estimates instead of reward estimates.
  • The proof partitions the horizon into intervals and subintervals, then applies a theorem to each subinterval and sums the regrets.

Appendix C. Proofs for ADA-GREEDY

The ADA-GREEDY proofs establish concentration and variation properties that control non-stationarity tests and reruns on sufficiently stationary intervals. The analysis shows that such intervals contain at most one triggered rerun under the stated events.

  • The appendix introduces notation used to analyze ADA-GREEDY and ADA-ILTCB throughout the proofs.
  • FLAG triggers a rerun after epoch length L or when NONSTATTEST detects non-stationarity in a later block.
  • For intervals with ∆I ≤ v, variation lemmas bound policy performance differences across subintervals.
  • Freedman’s inequality and a union bound yield EVENT1 with probability at least 1 − δ/2.
  • If |I| ≤ L and ∆I ≤ v, EVENT1 implies at most one round in I has FLAGt = True.
  • The rerun case is handled by splitting I around the triggered round and bounding the two resulting intervals separately.

Appendix D. Omitted Details for ADA-ILTCB

The appendix supplies implementation details and concentration arguments for ADA-ILTCB and ADA-BINGREEDY. These analyses connect statistical tests and bin or block structure to rerun behavior and regret control.

  • Figure 1 presents an ADA-ILTCB optimization subroutine adapted from Agarwal et al. (2014).
  • The analysis assumes L ≥ 4Kd without loss of generality; when L < 4Kd, the theorem bound holds trivially.
  • For intervals with bounded variation, lemmas relate variation in regret and variance quantities to the non-stationarity measures.
  • EVENT2 provides simultaneous concentration guarantees, and under it an interval of length at most L has at most one triggered rerun.
  • ADA-BINGREEDY uses exploration and exploitation bins, with flat bins defined by uniformly small regret gaps over dyadic subintervals.
  • Under EVENT3, ADA-BINGREEDY ends an epoch only when a distribution change occurs.

Proof

The proof bounds regret across blocks and epochs by controlling exploration, non-flat bins, and reruns, then combines these bounds with concentration and union arguments.

  • Block and epoch regret: Exploration-bin counts are bounded with high probability using Hoeffding-Azuma and a union bound over block indices and blocks.The resulting event is used throughout the subsequent proof stages.
  • Reruns and tests: Reruns are triggered by the non-stationarity test, while the proof bounds the resulting non-flat bins and combines the associated inequalities.The analysis identifies the first non-flat exploration bin and preceding non-flat exploitation bins as the key quantities.
  • Block and epoch regret: Non-flat exploitation bins before the first non-flat exploration bin have geometrically decreasing tail probability, yielding a high-probability bound on their count.The argument defines X for this count and bounds Pr{X > x} using pmin.
  • Final combination: The switching-regret theorem follows by combining several lemmas with probability at least 1 −5δ/2.The combined bound includes contributions from exploration and non-flat bins.
  • Final combination: ADA-BINGREEDY supplies the required per-bin guarantee used in the final regret combination.The lemma applies to flat exploitation bins and is invoked alongside the switching-regret components.

Proof

The proof establishes dynamic regret by relating interval guarantees to subintervals, summing across epochs, and combining the resulting bounds with the switching-regret analysis.

  • Dynamic-regret decomposition: ADA-BINGREEDY provides a per-interval guarantee for every policy on flat exploitation bins.The guarantee applies to intervals [s, e] contained in such a bin with length 2^q.
  • Dynamic-regret decomposition: Each bin is partitioned into intervals of length L′ = 2^q so dynamic regret can be related to interval regret against a fixed policy.A final shorter interval is further divided into at most log2 L′ subintervals.
  • Epoch and horizon summation: The proof sums regret over flat exploitation bins within epochs and then over epochs using Hölder’s inequality.The number of flat exploitation bins in an epoch is bounded by eO(|E|^(1−γ)).
  • Final theorem: The dynamic-regret theorem combines Lemmas 26, 27, 24, and 25 with probability at least 1 −5δ/2.The switching- and dynamic-regret components are combined using a union bound.

Appendix F. Omitted Proofs in Section 4

These omitted proofs convert local interval guarantees into variation-dependent regret bounds by partitioning the horizon into subintervals with controlled variation.

  • Interval decomposition: The interval-to-dynamic-regret relation is established by bounding the contribution of policy changes within each interval.The proof rewrites regret and bounds the remaining term by 2∆I.
  • Final bound: The final theorem is obtained by summing regret over all intervals.
  • Variation-controlled intervals: For intervals with |I| ≤ L and ∆I ≤ L^−1/3, ADA-GREEDY satisfies the required local regret guarantee with high probability.This condition is the starting point for the variation-based partition.
  • Variation-controlled intervals: Partitioning the horizon gives at most S′ ≤ T/L + ∆/L^−1/3 subintervals, each meeting the local length and variation conditions.The construction uses evenly spaced intervals followed by sequential subintervals with variation at most v.
  • Final bound: Summing the local bounds and applying Cauchy-Schwarz and Hoeffding-Azuma yields the claimed corollary.The proof uses ∆ ≤ T in the final bound.

Appendix G. Omitted Details for Corralling BISTRO+

The appendix describes Corralling BISTRO+ copies that start over time, constructs losses for started and unstarted algorithms, and derives interval and dynamic-regret guarantees.

  • Algorithm construction: Algorithm 5 maintains copies of BISTRO+ that start at staggered rounds and combines their suggested actions through CORRAL.The i-th copy starts after round (i −1)⌈T/M⌉.
  • Algorithm construction: At each round, CORRAL samples a started base algorithm, plays its suggested action, constructs estimated losses, and updates the master distribution.Unstarted algorithms receive the actual loss of the picked action, while started algorithms receive importance-weighted losses.
  • Algorithm improvement: The correction term zt in the CORRAL update replaces some dependence on T by L in the resulting bound.This update follows the improved version proposed by Wei and Luo (2018).
  • Interval guarantee: For an interval longer than T/M, the proof isolates the first newly added BISTRO+ copy and bounds the interval regret by T/M plus the remaining interval regret.The remaining terms are analyzed using the master bound and a result from Agarwal et al. (2017).
  • Dynamic regret: The dynamic-regret guarantee follows by partitioning the horizon into intervals, applying the interval guarantee, and using the interval-to-dynamic-regret lemma.The appendix states a transductive-setting corollary for this result.
  • No-change analysis: When there is no distribution change, the proof bounds reruns and reuses epoch and block regret results to control regret on the interval.The no-change case allows at most one rerun with the stated high-probability event.
Loading 1708.01799v4…