PaperlayerView exact revision on arXiv

Source-linked AI summary

A Change-Detection based Framework for Piecewise-stationary Multi-Armed Bandit Problem

Fang Liu, Joohyun Lee, Ness Shroff

arXiv:1711.03539v2cs.LGcs.AIstat.ML

TL;DR

Reward distributions in bandit problems may change over time, making stationary assumptions uncertain in practice. The paper proposes change-detection UCB policies, including CUSUM-UCB and PHT-UCB, and reports regret guarantees and empirical comparisons. CUSUM-UCB has a stated regret upper bound, and the experiments report lower regret than existing policies.

  • Problem

    Reward distributions may change over time, so the stationary bandit setting may not reflect practical problems.

    Source: §1 · p. 1

  • Method

    The paper develops CD-UCB, which combines UCB with change detection and restarts after detected breakpoints, including CUSUM-UCB and PHT-UCB instances.

    Source: §1 · p. 2, §4 · p. 3

  • Results

    The paper gives CUSUM-UCB a regret upper bound and reports that it outperforms existing policies in regret across experiments.

    Source: §7 · p. 7

  • Takeaways & Limitations

    The proposed change-detection policies are evaluated on arbitrary Bernoulli rewards and webpage click-through-rate data, with reported regret reductions.

    Source: §7 · p. 7

    The analysis assumes breakpoint spacing greater than KM and mean shifts of at least 3ε; CD-UCB's α also trades off detector feeding against detectability.

    Source: §2.2 · p. 3, §4.1 · p. 4

Abstract

from arXiv · show

The multi-armed bandit problem has been extensively studied under the stationary assumption. However in reality, this assumption often does not hold because the distributions of rewards themselves may change over time. In this paper, we propose a change-detection (CD) based framework for multi-armed bandit problems under the piecewise-stationary setting, and study a class of change-detection based UCB (Upper Confidence Bound) policies, CD-UCB, that actively detects change points and restarts the UCB indices. We then develop CUSUM-UCB and PHT-UCB, that belong to the CD-UCB class and use cumulative sum (CUSUM) and Page-Hinkley Test (PHT) to detect changes. We show that CUSUM-UCB obtains the best known regret upper bound under mild assumptions. We also demonstrate the regret reduction of the CD-UCB policies over arbitrary Bernoulli rewards and Yahoo! datasets of webpage click-through rates.

1 Introduction

Reward distributions can change over time, leaving unclear whether stationary-bandit guarantees apply. The paper proposes change-detection UCB policies and analyzes their regret, then compares them empirically with existing policies.

1 Introduction

  • In non-stationary environments, reward distributions vary over time, and it is unclear whether stationary-bandit O(log T) regret is achievable.The introduction illustrates this setting with changing channel availability in dynamic spectrum access.Source: §1 · p. 1
  • Prior passively adaptive methods include D-UCB, SW-UCB, Exp3.S, and Rexp3, with regret bounds expressed using change counts or reward variation.Rexp3's bound is described as reflecting an adversarial assumption that the environment may change every time slot.Source: §1 · pp. 1–2
  • Passively adaptive policies track recent observations without detecting change times, while actively adaptive policies monitor for changes and restart after an alarm.Prior actively adaptive methods are described as lacking regret upper-bound analyses.Source: §1 · p. 2
  • The proposed CD-UCB framework combines change detection with UCB; its CUSUM-UCB and PHT-UCB instances use CUSUM and PHT, respectively.The paper reports a general regret bound for CD-UCB given change-detection performance and analyzes CUSUM detection delay and false alarms.Source: §1 · p. 2
  • CUSUM-UCB has an analytically established regret upper bound, and experiments report that the proposed algorithms outperform existing policies in regret.The paper presents this as the first regret bound for actively adaptive UCB policies in the bandit-feedback setting.Source: §1 · p. 2

2 Problem Formulation

The problem formulation models bounded rewards from arms whose distributions may change at unknown breakpoints. It defines regret and specifies assumptions used for analysis.

2.1 Basic Setting

  • At each of T time slots, the decision maker chooses one of K arms and observes a reward in [0, 1] from an unknown, potentially time-varying distribution.The text notes that results can be generalized to any bounded interval.Source: §2.1 · p. 2
  • A policy chooses each arm from past plays and rewards, and its regret is the expected total loss from playing suboptimal arms.The formulation also upper-bounds regret by the expected number of suboptimal plays because rewards are bounded.Source: §2.1 · p. 2

2.2 Piecewise-stationary Environment

  • The environment is piecewise-stationary: reward distributions remain constant between abrupt changes, called breakpoints, whose count through time T is γ_T.The breakpoints occur at unknown time slots.Source: §2.2 · p. 3
  • The shortest interval between consecutive breakpoints must exceed KM, providing enough samples to estimate each arm's mean before a change.The paper characterizes this as an abruptly changing or switching environment, rather than one changing every time slot.Source: §2.2 · p. 3
  • Every change in an arm's mean must have magnitude at least 3ε, excluding infinitesimal shifts from the detectable changes considered.The paper describes this lower bound as reasonable when abrupt changes are bounded below by a threshold.Source: §2.2 · p. 3
  • All arm rewards are assumed Bernoulli, so an average of M samples lies on the grid {0, 1/M, …, 1}.This assumption is used to define a minimum nonzero gap λ between arm means and nearby grid points.Source: §2.2 · p. 3
  • The analysis defines λ as the smallest nontrivial gap across arms between the shifted mean thresholds and the empirical-average grid.The grid spacing follows from the Bernoulli-reward assumption.Source: §2.2 · p. 3

3 Change-Detection based Framework

The framework combines a bandit algorithm with a detector that monitors arm rewards and restarts the bandit algorithm after detecting a breakpoint. It addresses two difficulties created by bandit feedback and unknown change distributions.

3 Change-Detection based Framework

  • The detector monitors arm rewards and sends a restart signal to the bandit algorithm when it detects a breakpoint.The bandit algorithm selects an arm, and its observed reward is available to both components.Source: §3 · p. 3
  • The framework generalizes existing actively adaptive policies by pairing a change-detection algorithm with a bandit algorithm.The figure caption identifies it as a framework for non-stationary bandit problems.Source: §3 · p. 3, Figure 1 · p. 3
  • Bandit change detection faces unknown pre- and post-change distributions, for which estimating priors and applying PHT lacks analytical results in the cited discussion.Traditional change-detection methods are described as assuming known parameters for those distributions.Source: §3 · p. 3
  • With bandit feedback, only one arm is observed per time step, leaving the parallel detectors for other arms short of recent samples and potentially causing missed detection opportunities.The framework's detector monitors each arm's possible mean shift.Source: §3 · p. 3

4 Application of the Framework

The application pairs UCB with change detectors to address scarce observations and unknown priors. It develops CD-UCB, a tailored CUSUM detector, and CUSUM-UCB and PHT-UCB instances.

4.1 CD-UCB policy

  • CD-UCB addresses insufficient samples by using a change detector alongside UCB; its index combines an arm's sample average and confidence padding.The policy also uses tuning parameter α to control the fraction of plays used to feed the detector.Source: §4 · p. 3, §4.1 · p. 4
  • The CD-UCB policy restarts an arm's statistics and detector after an alarm, using observations since the latest alarm to form that arm's UCB index.The policy's α parameter controls detector-feeding plays; a large α may drive linear regret, while a small α can limit detectability.Source: §4.1 · p. 4

4.2 Tailored CUSUM algorithm

  • The tailored two-sided CUSUM uses the first M samples to estimate a baseline, then tracks possible positive and negative mean shifts with separate random walks.The walks have negative mean drift before a change and positive drift after one; either crossing threshold h triggers detection.Source: §4.2 · p. 4

4.3 CUSUM-UCB policy

  • CUSUM-UCB instantiates CD-UCB with K parallel CUSUM detectors, one for each arm.The paper refers readers to supplementary Algorithm 3 for its formal description.Source: §4.3 · p. 4

4.4 PHT-UCB policy

  • PHT-UCB is another CD-UCB instance, using the Page-Hinkley Test as its change detector and replacing the update in equation (6) with PHT-specific terms.The supplied description gives those terms as (s⁺_k, s⁻_k) = (y_k − ŷ_k − ε, ŷ_k − y_k − ε).Source: §4.4 · p. 4

5 Performance Analysis

The analysis combines a general CD-UCB regret bound with CUSUM detection guarantees to derive a CUSUM-UCB regret bound. It compares regret against SW-UCB under different gap conditions and discusses the knowledge needed to tune parameters.

5 Performance Analysis

  • For α = 0 and ξ = 1, CD-UCB regret is O((γT + E[F]) · log T + γT · E[D]).Source: §5 · p. 5
  • CUSUM bounds detection delay and false alarms conditional on |û0−u0| < ε; outside that range, restart occurs within (h+1)/(|û0−u0|−ε) slots.Source: §5 · p. 5
  • The paper presents the first regret bound for an actively adaptive UCB policy in the bandit feedback setting.The CUSUM-UCB bound is stated under Assumptions 1, 2, and 3.Source: §5 · p. 5
  • Choosing h uses the horizon and breakpoint count when known; estimating γT from history is practically viable when the reward change rate is regular.Source: §5 · p. 5
  • With ∆µT(i) constant in T, CUSUM-UCB has a smaller regret term in γT than SW-UCB.Table 1 compares regret upper bounds for the non-stationary setting under this condition.Source: Table 1 · p. 6, §5 · p. 6
  • When ∆µT(i) decreases with T, CUSUM-UCB regret grows much slower than SW-UCB regret.Source: §5 · p. 6

6 Simulation Results

The simulations compare change-detection policies with existing approaches in synthetic switching and flipping environments and on Yahoo! click data. CUSUM-UCB and PHT-UCB show lower regret than passive policies in the reported settings, with their relative performance depending on the environment.

6 Simulation Results

  • The evaluation covered two synthetic settings and Yahoo! user-click data; Yahoo! experiments used either 5 or 100 selected articles.Synthetic comparisons averaged regret over 1000 trials; parameter choices used prior knowledge of dataset characteristics.Source: §6 · p. 6, §6.2 · p. 7

6.1 Synthetic Datasets

  • In the flipping environment, CUSUM-UCB outperformed D-UCB and SW-UCB, and its gap over SW-UCB increased as Δ decreased.The comparison varied Δ from 0.02 to 0.3; results of other algorithms were omitted.Source: §6.1 · p. 6, Figure 2 · p. 6
  • In the switching environment, fitted exponents were 0.72 for CUSUM-UCB and 0.69 for PHT-UCB, lower than the other policies; PHT-UCB performed better than CUSUM-UCB.Assumptions 1 and 2 were violated in this setting, and the authors attribute PHT-UCB's result to its more stable estimation.Source: §6.1 · pp. 6–7, Figure 2 · p. 6

6.2 Yahoo! Dataset

  • On Yahoo! K=5, CUSUM-UCB's fitted regret exponent was 0.69 versus 1 for D-UCB, Rexp3, and SW-UCB; PHT-UCB's was 0.79.The authors report sublinear regret for the active policies and CUSUM-UCB outperforming PHT-UCB in this dataset.Source: §6.2 · p. 7, Figure 3 · p. 7
  • On Yahoo! K=100, CUSUM-UCB and PHT-UCB showed robust performance, while D-UCB, SW-UCB, and Rexp3 had linear regret for most of the time.Fitted exponents were 0.85 for CUSUM-UCB and 0.9 for PHT-UCB, compared with 1 for each of the three passive policies.Source: §6.2 · p. 7, Figure 4 · p. 7

7 Conclusion

The paper concludes that its change-detection UCB framework yields a regret guarantee for CUSUM-UCB and performs well in experiments. The accompanying lemma list records probability and CUSUM results used in the analysis.

7 Conclusion

  • The paper's conclusion presents CD-UCB as a framework for non-stationary bandits, with CUSUM-UCB and PHT-UCB detecting breakpoints to react to environmental changes.The framework's general regret bound is given conditional on change-detection performance.Source: §7 · p. 7
  • CUSUM-UCB's regret is analytically bounded by O(γT), which the authors state is lower than existing non-stationary regret bounds and is the first bound for actively adaptive UCB policies.The conclusion also reports that CUSUM-UCB outperforms existing policies in experiments on arbitrary Bernoulli rewards and webpage click-through rates.Source: §7 · p. 7

A Lemma List

  • The lemma list includes a Chernoff-Hoeffding bound, Wald's identity, and a two-sided CUSUM result.The passages refer readers to Pollard (1984), Gallager (2012), and Khan (1981) for proofs.Source: A Lemma List · p. 9

B Proof of Theorem 1

The proof bounds regret by tracking arm choices relative to the best arm and accounting for detection points, false alarms, and detection delays. It uses sample-count thresholds and concentration events to control suboptimal choices.

B Proof of Theorem 1

  • For sufficiently many samples of a suboptimal arm, the proof uses confidence deviations to rule out an event in which that arm is selected over the best arm.The threshold A_i is defined using log T and the squared reward gap for arm i.Source: B Proof of Theorem 1 · p. 9
  • The proof tracks detection points, including false alarms, and defines per-arm intervals based on whether a breakpoint occurs near those points.It also counts false alarms and the detection delay of each breakpoint on an arm.Source: B Proof of Theorem 1 · p. 9
  • The regret bound accounts for the number of breakpoints, expected false alarms, expected detection delay, and terms involving the per-arm gap and a confidence parameter.The displayed bound combines these quantities with an additional term proportional to (γT + E[F] + 1)π^2/3.Source: B Proof of Theorem 1 · p. 10

C Proof of Proposition 1

The proposition proof analyzes CUSUM detection through its average run length, relating that quantity to detection delay and false alarms. It treats upper- and lower-side tests symmetrically and considers estimation-error cases.

C Proof of Proposition 1

  • The analysis assumes bounded observations and a pre-change mean estimate from the first M samples; the pre- and post-change means differ by at least 2ϵ.It divides the bounds into cases according to the estimate's error and the direction of the mean change.Source: C Proof of Proposition 1 · p. 10
  • The algorithm is described as a symmetric two-sided CUSUM, with upper- and lower-side average run lengths analyzed by symmetry.The lower-side stopping rule monitors a random walk crossing a boundary and restarts the sequential probability ratio test after an alarm.Source: C Proof of Proposition 1 · p. 10
  • The average run length characterizes CUSUM detection performance: it is the mean detection delay under θ1 and the mean time between false alarms under θ0.The proof uses these quantities to express expected delay and false-alarm counts.Source: C Proof of Proposition 1 · p. 10
  • When the estimate is within ϵ of the pre-change mean and the post-change mean is lower, the proof bounds lower-side detection delay and the mean time between false alarms.The displayed false-alarm bound is L−(θ0) ≥ exp(r−(θ0)h).Source: C Proof of Proposition 1 · pp. 10–11

D Proof of Theorem 2

The proof derives bounds for change detection by averaging conditional results over the estimator and separating cases based on its distance from the true mean. It combines these bounds to control mean detection delay and false alarms over horizon T.

D Proof of Theorem 2

  • The proof takes conditional expectations over the estimator and splits the analysis according to whether |uhat-u0| is below epsilon.Estimator values in the second case lie on a grid with spacing 1/M.Source: D Proof of Theorem 2 · pp. 11–12
  • Under Assumption 3, where yk is Bernoulli, the argument derives an upper bound on L(θ1) when u1 < u0 and lower bounds on L−(θ0) and L+(θ0).Source: D Proof of Theorem 2 · pp. 11–12
  • The proof uses positive minimum inter-change gaps δT(i), with Assumption 2 ensuring δT(i) is at least epsilon.The gap is defined over times when an arm's mean reward changes.Source: D Proof of Theorem 2 · p. 11
  • The bounds assume the auxiliary estimates exist when 2epsilon < u0 < 1−2epsilon; linear reward scaling places the mean in that interval without loss of generality.The passage states the scaling function as f(x) = (1−4epsilon)x + 2epsilon.Source: D Proof of Theorem 2 · p. 12
  • Combining the casewise results yields an upper bound on mean detection delay and a lower bound on false alarms within horizon T.The proof sums the component results to obtain these bounds.Source: D Proof of Theorem 2 · p. 13

E Proof of Theorem 3

Theorem 3 combines earlier results, accounting for M regret per detection alarm and scaling the mean detection delay by the sampling rate. The CUSUM-UCB policy uses parallel CUSUM detectors and countdown timers to support estimation and detector resets.

E Proof of Theorem 3

  • Theorem 3's regret accounting adds M for each detection alarm, and its mean detection delay bound is scaled by dividing by sampling rate alpha/K.The result follows from Theorems 1 and 2.Source: E Proof of Theorem 3 · p. 13

F CUSUM-UCB policy

  • CUSUM-UCB instantiates CD-UCB with K parallel CUSUM algorithms and resets the detected arm's CUSUM after an alarm.The algorithm also updates that arm's timer when an alarm occurs.Source: F CUSUM-UCB policy · p. 13
  • Countdown timers let CUSUM-UCB complete mean estimation with M observations as soon as possible.The policy's performance depends on alpha and h.Source: F CUSUM-UCB policy · p. 13

G Simulation Parameters

The simulation section identifies parameter settings and specifies the threshold used to count breakpoints.

G Simulation Parameters

Loading 1711.03539v2…