Source-linked AI summary
On Upper-Confidence Bound Policies for Non-Stationary Bandit Problems
Aurélien Garivier, Eric Moulines
TL;DR
Abruptly changing reward distributions challenge stationary bandit policies that must balance exploration and exploitation. The paper analyzes discounted and sliding-window UCB using regret bounds, a lower bound, and a self-normalized deviation inequality. Both policies nearly match the lower bound up to a logarithmic factor, while experiments support their effectiveness.
Problem
Stationary bandit policies may fail to track the best arm when reward distributions change abruptly at unknown time instants.
Method
The paper analyzes discounted UCB and sliding-window UCB, deriving regret upper bounds with a self-normalized deviation inequality and a lower bound for abruptly changing environments.
Results
The discounted UCB and sliding-window UCB policies both match the regret lower bound up to a logarithmic factor, and experiments support their performance.
Takeaways & Limitations
UCB policies can be adapted to non-stationary environments and can perform at least as well as softmax methods in the reported comparisons.
Takeaways & Limitations
The paper focuses theoretically on abruptly changing environments; continuously evolving reward distributions are left for future analysis.
Abstract
from arXiv · showhide
Multi-armed bandit problems are considered as a paradigm of the trade-off between exploring the environment to find profitable actions and exploiting what is already known. In the stationary case, the distributions of the rewards do not change in time, Upper-Confidence Bound (UCB) policies have been shown to be rate optimal. A challenging variant of the MABP is the non-stationary bandit problem where the gambler must decide which arm to play while facing the possibility of a changing environment. In this paper, we consider the situation where the distributions of rewards remain constant over epochs and change at unknown time instants. We analyze two algorithms: the discounted UCB and the sliding-window UCB. We establish for these two algorithms an upper-bound for the expected regret by upper-bounding the expectation of the number of times a suboptimal arm is played. For that purpose, we derive a Hoeffding type inequality for self normalized deviations with a random number of summands. We establish a lower-bound for the regret in presence of abrupt changes in the arms reward distributions. We show that the discounted UCB and the sliding-window UCB both match the lower-bound up to a logarithmic factor.
1. Introduction
Multi-armed bandits formalize exploration versus exploitation under uncertainty, but stationary models may not fit environments whose reward distributions change. This paper studies abrupt non-stationarity through adaptive UCB policies, regret bounds, and lower bounds.
- Stationary bandits: MAB algorithms choose among K arms over T rounds to balance exploiting known rewards with exploring uncertain alternatives while minimizing expected regret.Regret compares the policy’s total reward with that of always playing the arm with the highest expected reward.
- Motivation: Stationary models assume reward distributions remain constant, limiting their adequacy for evolving channels, website content preferences, and other changing environments.The paper notes that stationary policies can fail to track changes in the best arm.
- Contributions: The paper analyzes both policies, derives regret upper bounds and a lower bound for abrupt changes, and shows they are almost rate-optimal up to a logarithmic factor.The analysis uses a deviation inequality for self-normalized averages with a random number of summands.
- UCB background: UCB policies select the arm maximizing an upper confidence bound built from past reward observations, extending the Lai–Robbins approach to a non-parametric setting.UCB-1 uses an empirical mean plus a padding function based on the number of observations and time.
- Non-stationary setting: Abruptly changing environments keep reward distributions constant between unknown breakpoints, with the number of changes before time T denoted Υ_T.The paper distinguishes this setting from continuously evolving reward distributions.
- Adaptive policies: Discounted UCB weights recent observations more heavily, whereas Sliding-Window UCB computes local averages using only the τ most recent plays.These designs target instantaneous rewards in changing environments.
2. Analysis of Discounted UCB
The discounted-UCB analysis bounds suboptimal-arm plays in abruptly changing environments, accounting for estimation bias after breakpoints and random-sample deviations. With suitable discounting, D-UCB attains near-optimal regret while adapting its discount factor to breakpoint growth.
- Setup: D-UCB is analyzed by bounding the expected number of times a suboptimal arm is played over T rounds.The analysis uses the minimum gap between the best and suboptimal arms and the number of breakpoints before T.
- Proof strategy: A discounted empirical mean is biased after changes because recent observations can still reflect earlier reward distributions.The bias is controlled after D(γ) rounds following a breakpoint, while the padding function controls fluctuations.
- Proof strategy: A self-normalized deviation inequality with a random number of summands replaces the standard Chernoff-Hoeffding bound in the proof.This accommodates discounted observations and the changing reward distributions.
- Results: After a breakpoint, D-UCB can repeatedly select a suboptimal arm while its estimates remain poor.This transient adaptation cost is explicitly included in the regret analysis.
- Results: When ΥT = O(T^β), the discount factor can be tuned using the breakpoint growth rate, and D-UCB matches the lower bound up to log T.For β = 0, the number of breakpoints is bounded independently of T; with positive breakpoint density, the resulting regret bound is linear but non-trivial.
3. Sliding window UCB
Sliding-window UCB estimates rewards using only the most recent τ plays, eliminating the post-breakpoint bias within a stable window. Its regret bound is slightly better than D-UCB's in the analyzed abruptly changing setting.
- Algorithm: SW-UCB constructs its index from a local empirical average and confidence term based on the last τ plays.The window size τ determines how much recent history contributes to the estimate.
- Analysis: Within a τ-round stable period, the sliding-window estimator's bias exactly vanishes, simplifying the D-UCB proof.The analysis therefore bypasses the separate bias-control step used for discounted observations.
- Results: When ΥT = O(T^β), SW-UCB achieves an average-regret upper bound whose logarithmic gap to the lower bound is √log T.For β = 0, the window is tuned using the bounded breakpoint count, and the method is slightly better than D-UCB.
- Results: If there are no breakpoints, choosing τ = T recovers standard UCB and its usual logarithmic-regret type of bound.The paper also notes a better constant in this stationary special case.
- Implementation: SW-UCB has linear-time computational complexity but must store the last τ actions and rewards for efficient updates.The memory requirement depends on the window contents even though the time complexity does not involve τ.
4. A lower-bound on the regret in abruptly changing environment
The section derives a regret lower-bound for abruptly changing bandits, showing that insufficient exploration can leave policies playing suboptimal arms after breakpoints. It also compares this bound with stationary and minimax benchmarks.
- Lower-bound construction: Piecewise-constant rewards with two breakpoints create games where a suboptimal arm becomes optimal during one epoch.The construction changes arm K to a distribution with higher expected reward over a selected period.
- Lower-bound construction: Theorem 13 lower-bounds the number of suboptimal-arm plays for any policy over a specified horizon and exploration regime.The stated regime requires 64/(9α) ≤ Eπ[N_T(K)] ≤ T/(4α).
- Scope: The resulting non-stationary regret lower-bound applies to deterministic policies and also extends to randomized strategies.The proof is stated for deterministic policies, while the paper notes that the same result holds for randomized strategies.
- Interpretation: The lower-bound formalizes that policies exploring too little may fail to detect a breakpoint for a long period.Standard UCB, with Eπ[N(K)] = Θ(log T), is used as an example of insufficient exploration in this setting.
- Comparison: Unlike stationary fixed-game lower-bounds, the construction keeps the distance between reward distributions bounded away from zero as T grows.The paper states that minimax regret and fixed-game minimal regret have the same order in this setting.
5. Simulations
The simulations compare UCB variants with EXP3.S and UCB-1 in abruptly changing and continuously evolving environments. Discounted-UCB and sliding-window UCB track changing optima more effectively than the baselines.
- Abrupt changes: In the three-arm abrupt-change example, arm 1 is optimal before t = 3000 and after t = 5000, while arm 3 is optimal between the breakpoints.The experiment uses T = 10^4 and Bernoulli rewards, with arm 3's success probability rising to 0.9 during the middle epoch.
- Abrupt changes: D-UCB performs almost as well as SW-UCB and both detect breakpoints faster than EXP3.S and UCB-1.Their pulls quickly concentrate on the currently optimal arm.
- Abrupt changes: UCB-1 reacts quickly to the first breakpoint but takes a very long time to return to arm 1 after the second breakpoint.Its loose confidence interval for arm 3 explains the rapid first reaction, whereas recovery after t = 5000 is slow.
- Continuous evolution: In the continuously evolving two-arm example, D-UCB, SW-UCB, and to a lesser extent EXP3.S track the cyclic best arm, whereas UCB-1 fails to identify it.The environment uses a fixed reference arm and a periodically varying Bernoulli parameter for arm 1.
- Continuous evolution: D-UCB and SW-UCB accumulate almost equivalent and smaller regrets than UCB-1 and EXP3.S in the continuously evolving environment.The reported comparisons concern the simulated examples and use parameters tuned for the chosen horizon and breakpoint count.
6. Conclusion and perspectives
The conclusion reports that discounted and sliding-window UCB can handle non-stationary environments, with theoretical and experimental support. It also identifies abrupt changes and parameter tuning as important scope boundaries.
- Conclusions: SW-UCB's upper bound in abruptly changing environments matches the upper bound of Exp3.S, O(√(T log(T))).The paper interprets this as showing that UCB policies can be at least as good as softmax methods.
- Conclusions: In the two reported examples, D-UCB and SW-UCB outperform the optimally tuned Exp3.S algorithm.This is an empirical conclusion from the paper's numerical experiments.
- Perspectives: The theoretical analysis focuses on abruptly changing environments, while related tools are suggested for continuously evolving reward distributions.The paper says that such an analysis will be reported in future work.
- Limitations: Performance depends on tuning the D-UCB discount factor and SW-UCB window size.The paper identifies adaptive, data-driven tuning as ongoing research.
Appendix A. A Hoeffding-type inequality for self-normalized means with a random number of summands
The appendix develops a Hoeffding-type concentration inequality for bounded independent variables selected by predictable random indicators. It extends classical bounds to self-normalized sums with a random number of summands.
- Setup: The appendix considers independent bounded variables X_t ∈ [0, B] and predictable Bernoulli selectors ε_t.Each selector is measurable with respect to the past, while future variables remain independent of the current filtration.
- Proof strategy: The proof uses conditional moment generating functions and Markov's inequality to control deviations.Predictability of ε_{u+1} and independence of X_{u+1} from the current filtration enable the conditional calculation.
- Random normalization: The random selectors produce a self-normalized sum whose effective sample size can vary over time.The proof controls the random count through discretized ranges and a union bound.
- Bound quality: The resulting inequality is slightly less sharp than the classical Hoeffding bound because the summands are selected randomly.The appendix explicitly attributes the extra factor and slightly larger exponent to the random selectors.
- Corollary: When all variables share expectation µ and γ = 1, the general result yields a stationary-case corollary.The appendix distinguishes the γ < 1 and γ = 1 normalization regimes.
Appendix B. A maximal inequality for self-normalized means with a random number of summands
This appendix develops a maximal inequality for self-normalized averages with a random number of summands, using martingale and exponential-bound arguments to obtain uniform deviation control.
- The appendix strengthens an earlier theorem by upper-bounding the probability that an average reward deviates from its expectation at some time t.The bound is uniform over time rather than applying only at a fixed time.
- The theorem provides a bound for every positive integer T and every δ > 0, with separate treatment of the case γ = 1.The statement also holds for all η > 0, while the γ = 1 case is handled explicitly.
- Compared with classical Hoeffding bounds for deterministic εs, uniformity in t introduces a T- and ε-dependent exponential factor and a slightly larger exponent.For example, the appendix evaluates the bound at η = 0.3.
- The proof represents discounted reward sums through a martingale adapted to the filtration F.The recursive relation for the discounted sum provides the martingale construction used in the argument.
- The analysis applies exponential super-martingale bounds to control positive deviations for any x > 0.The resulting control is used within the maximal-inequality proof.
Appendix C. Technical results
This technical result defines a windowed count of arm selections, which supports analysis of recent observations for a given arm.
- For arm i and a positive integer window length τ, the lemma introduces N_t−τ:t(1, i) to count relevant selections within the recent window.The quantity is used as a technical object in the subsequent bound.
Proof
The proof partitions time into blocks and identifies the last within-block time when a windowed arm-count condition holds, enabling application of the preceding lemma.
- For each block j, the proof either has no qualifying selection of arm i or identifies a time t in that block satisfying the window-count condition.This converts the block contribution into an event that can be bounded.
- The proof selects t_j as the last qualifying time in block j before applying the preceding lemma.Choosing the maximum such time organizes the blockwise argument.
- Corollary 26 applies the lemma for any arm i, integer τ ≥ 1, and A > 0.The preceding argument is then specialized using m = γ^−τ A.