PaperlayerView exact revision on arXiv

Source-linked AI summary

Nearly Optimal Adaptive Procedure with Change Detection for Piecewise-Stationary Bandit

Yang Cao, Zheng Wen, Branislav Kveton, Yao Xie

arXiv:1802.03692v4stat.MLcs.LG

TL;DR

Piecewise-stationary bandits address reward distributions that change at unknown times, a setting between time-invariant and adversarial rewards. The paper combines UCB with simple change detection in M-UCB. It proves a nearly optimal regret bound and reports regret reductions against state-of-the-art algorithms in real-world experiments.

  • Problem

    Piecewise-stationary bandits model rewards that change at unknown times, between the time-invariant stochastic model and the frequently changing adversarial model.

    Source: §1 · p. 1

  • Method

    M-UCB combines UCB with a sliding-window change detector based on comparing running sample means, then resets learning when it detects a change.

    Source: §1 · p. 1, §3.3 · p. 3

  • Results

    O(√MKT log T) regret is nearly optimal up to a logarithmic factor under mild technical conditions, and experiments report significant regret reduction against state-of-the-art algorithms.

    Source: §1 · p. 2, §7 · p. 8

  • Takeaways & Limitations

    The paper concludes that M-UCB achieves a nearly optimal regret bound and significant regret reduction in experiments on real-world datasets.

    Source: §7 · p. 8

    M-UCB is based on UCB1; the authors identify KL-UCB and Thompson sampling as possible alternative exploration schemes.

    Source: §7 · p. 8

Abstract

from arXiv · show

Multi-armed bandit (MAB) is a class of online learning problems where a learning agent aims to maximize its expected cumulative reward while repeatedly selecting to pull arms with unknown reward distributions. We consider a scenario where the reward distributions may change in a piecewise-stationary fashion at unknown time steps. We show that by incorporating a simple change-detection component with classic UCB algorithms to detect and adapt to changes, our so-called M-UCB algorithm can achieve nearly optimal regret bound on the order of $O(\sqrt{MKT\log T})$, where $T$ is the number of time steps, $K$ is the number of arms, and $M$ is the number of stationary segments. Comparison with the best available lower bound shows that our M-UCB is nearly optimal in $T$ up to a logarithmic factor. We also compare M-UCB with the state-of-the-art algorithms in numerical experiments using a public Yahoo! dataset to demonstrate its superior performance.

1 Introduction

Piecewise-stationary bandits model reward distributions that change less frequently than in adversarial settings but are not time-invariant. The paper introduces M-UCB, combining UCB with change detection, and proves a nearly optimal regret bound.

1 Introduction

  • Piecewise-stationary bandits address settings where rewards change over time, but less frequently than the adversarial model allows.The model is also presented as an approximation to slowly time-varying reward functions.Source: §1 · p. 1
  • M-UCB monitors the estimated mean of the selected arm and resets to learn the new optimal arm when it detects a change.Its change detector compares running sample means over a sliding window.Source: §1 · pp. 1–2
  • O(√MKT log T) regret makes M-UCB nearly optimal up to a logarithmic factor under mild technical assumptions.The bound matches the stated Ω(√T) lower bound up to a logarithmic factor.Source: §1 · p. 2
  • Experiments validate the regret bound’s scalings in M and K, and the paper compares M-UCB with state-of-the-art algorithms.The scaling experiments are reported in Section 6.1; the Yahoo! comparison is in Section 6.2.Source: §1 · p. 2
  • In numerical experiments based on a public Yahoo! dataset, M-UCB achieves at least 50% regret reduction with respect to the best-performing state-of-the-art algorithm.Source: §1 · p. 2

2 Literature Review

Prior approaches to piecewise-stationary bandits either adapt passively by discounting or windowing rewards, or actively detect changes and restart learning. The paper positions M-UCB among active methods and contrasts its detection method and analysis with CUSUM-based work.

2 Literature Review

  • D-UCB discounts past rewards, while SW-UCB computes UCB indices from the most recent w rewards.Their stated regret bounds are O(KMT log T) for D-UCB and O(K√MT log T) for SW-UCB.Source: §2 · p. 2
  • EXP3.S, SHIFTBAND, and Rexp3 represent other approaches, using action-switch regularization, shifting comparators, and variation budgets, respectively.Rexp3’s bound depends on the total variation budget VT.Source: §2 · p. 2
  • Active change detection can locate change-points and is described as usually performing better in practice than passive adaptation.Passive methods instead adjust reward weights, as in D-UCB and SW-UCB.Source: §2 · p. 2
  • Earlier active methods include Page-Hinkley detection with restarted UCB1, Bayesian detection with Thompson Sampling, and windowed mean-shift detection.The WMD method requires observing past rewards of unpicked arms, violating bandit feedback.Source: §2 · p. 2
  • Unlike CUSUM-based work [Liu et al., 2017], M-UCB uses a simpler detector without parameter specification and applies to bounded rewards beyond Bernoulli rewards.The authors also present a renewal-process-based proof structure intended to generalize to other change-detection methods.Source: §2 · p. 2

3 Problem Formulation

The paper formalizes a bandit with bounded, independently drawn rewards that change asynchronously across stationary segments, with unknown distributions and segment statistics. It motivates a sliding-window mean comparison for detecting changes when the pre- and post-change distributions are unknown.

3.1 Piecewise-Stationary Bandit

  • A piecewise-stationary bandit is specified by K arms, T time steps, and time-varying reward distributions, with arm rewards independently drawn and supported on [0, 1].The reward distributions remain fixed within segments and shift at change-points.Source: §3.1 · p. 3
  • M denotes the number of stationary segments, so the process has M − 1 change-points and can change asynchronously across arms.The stochastic model is the special case M = 1, while the adversarial model is represented as M = T.Source: §3.1 · p. 3

3.2 Regret Minimization

  • The agent knows T and K but not the reward distributions, M, or segment means, and observes only the reward of its chosen arm.Its objective is to maximize expected cumulative reward, equivalently minimizing the paper’s T-step cumulative regret.Source: §3.1 · p. 3, §3.2 · p. 3
  • The paper’s regret metric is stricter than the adversarial-bandit metric because it compares against the optimal piecewise-stationary policy rather than the best action in hindsight.The stated relation is R(T) ≥ eR(T).Source: §3.2 · p. 3

3.3 Sequential Change-Point Detection

  • CUSUM is unsuitable when pre- and post-change distributions are unknown, while GLR allows unknown parameters but is non-recursive and computationally expensive.The paper identifies online and high-dimensional settings as especially unsuitable for GLR.Source: §3.3 · p. 3
  • The proposed detector compares running sample means over a sliding window, offering an efficient method with minimal parameter specification.It returns whether the absolute difference between the two window-half sums exceeds threshold b.Source: §3.3 · p. 3

4 M-UCB Algorithm

M-UCB combines uniform sampling, UCB-based exploration, and change detection to adapt to piecewise-stationary rewards. Uniform sampling supplies observations for detecting changes even in arms that ordinary UCB visits infrequently.

4 M-UCB Algorithm

  • M-UCB combines uniform sampling, UCB-based exploration, and change detection that monitors for shifts and triggers exploration.The uniform sampling component ensures data are gathered across arms for detection.Source: §4 · pp. 3–4
  • The algorithm takes T, K, and tuning parameters w, b, and γ, where w and b tune change detection and γ controls uniform sampling.The description identifies τ as the last detection time and n_k as arm k’s observations since τ.Source: §4 · pp. 3–4
  • At each time step, M-UCB chooses uniform sampling or UCB-based exploration, with the uniform fraction roughly γ.For UCB exploration, it computes standard UCB1 indices from observations since the last detection time τ.Source: §4 · p. 4
  • After at least w observations of the chosen arm since τ, M-UCB tests for a change and resets its exploration statistics if one is detected.The reset sets τ to the detection time and resets the arm observation counts.Source: §4 · p. 4
  • Uniform sampling is crucial because standard UCB may rarely select believed-suboptimal arms, slowing detection of changes in those arms.The sampling fraction is controlled by γ.Source: §4 · p. 4

5 Near Optimality of M-UCB

The section establishes a nearly optimal regret bound for M-UCB under its analysis assumptions and outlines how the proof combines bandit and change-detection analysis.

5 Near Optimality of M-UCB

  • The analysis assumes sufficiently separated change-points and a change large enough on at least one arm, but M-UCB can be implemented without these assumptions.The paper reports that the algorithm works well without them in its real-world experiments.Source: §5 · p. 4
  • Theorem 1 decomposes regret into UCB exploration, uniform sampling, detection delay, and unsuccessful or incorrect change-point detections.The first two terms are exploration costs; the latter two are change-detection costs.Source: §5 · p. 5
  • The regret bound is asymptotically tight up to logarithmic factors in T, and the paper reports leaving the lower-bound derivation in K and M for future work.The stated upper bound hides logarithmic factors.Source: §5 · p. 5

5.1 Proof Outline of Theorem 1

  • The proof bounds regret by separating paths with quick, correct reinitialization from paths with delayed or incorrect reinitialization.The analysis bounds bad-event probabilities and regret on good events, then combines those bounds.Source: §5 · p. 5, §5.1 · p. 6
  • In a stationary setting, regret includes false-alarm probability, classic UCB exploration, and uniform-sampling exploration.The false-alarm probability can be bounded by 1/T using the stated choice of b.Source: §5.1 · pp. 5–6
  • For a single change-point, the detection analysis bounds delay when the change exceeds a threshold and the segment lasts longer than L/2.With probability at least 1 − 1/T, detection occurs within L/2 steps when the change is greater than C1/√w for a constant depending only on T and K.Source: §5.1 · p. 6

6 Experiments

The experiments examine M-UCB’s regret scaling in the number of segments and arms, then compare it with five algorithms on a Yahoo! dataset. The reported scaling estimates and Yahoo! comparison support the paper’s theoretical and empirical claims.

6.1 Regret Scalings in M and K

  • For the M-scaling experiment, K was fixed at 10 and change-points were evenly spaced at intervals of 20,000 steps.Rewards were assumed Bernoulli, and the reported averaged regret used 100 instances with 50 runs each.Source: §6.1 · pp. 6–7
  • Estimated regret-scaling exponents were 0.55 in M and 0.53 in K, suggesting the bound is roughly tight in both variables.Figure 1 varies M with K fixed; Figure 2 varies K with M fixed.Source: §6.1 · p. 7, Figure 1 · p. 7, Figure 2 · p. 7
  • For the K-scaling experiment, M was fixed at 4 and T at 3 × 10^5, with evenly spaced change-points.The estimated exponent came from 100 random instances, each run 50 times.Source: §6.1 · p. 7, Figure 2 · p. 7

6.2 Experiment on Yahoo! Dataset

  • The Yahoo! experiment used six articles over T = 4.32 × 10^5 steps and M = 9 stationary segments.Article click-through rates were computed over half-day intervals; changes below 0.01 were smoothed by carrying forward the prior rate.Source: §6.2 · p. 7, Figure 3 · p. 7
  • M-UCB reduced cumulative regret by 50% versus EXP3 and EXP3.S, and by 60% versus SW-UCB, D-UCB, and SHIFTBAND.The comparison used the Yahoo! piecewise-stationary scenario; the reported expected cumulative regrets are shown in Figure 4.Source: Figure 4 · p. 7, §6.2 · p. 8
  • The Yahoo! scenario violates Assumption 1: its changes are below 0.1, while the selected parameters require changes of at least 0.64.The authors report that M-UCB still outperforms the state-of-the-art baselines in this experiment.Source: §6.2 · p. 8

7 Conclusion

The paper presents M-UCB for bounded-reward piecewise-stationary bandits, combining UCB with sliding-window change detection. It proves a nearly optimal regret bound under mild technical conditions and reports regret reductions in real-world-data experiments.

7 Conclusion

  • M-UCB combines UCB with uniform exploration and change-point detection based on running sample means over a sliding window.The conclusion identifies the algorithm as based on classical UCB1.Source: §7 · p. 8
  • The proved regret bound is O(√(MKT log T)) under mild technical conditions.The paper describes the bound as nearly optimal.Source: §7 · p. 8
  • Experiments on real-world datasets report significant regret reduction relative to state-of-the-art algorithms.The conclusion notes that other exploration schemes, including KL-UCB and Thompson sampling, may be considered.Source: §7 · p. 8

A.1 Proof of Lemma 1

The proof bounds regret on the event that no change is detected before the horizon by controlling how often each arm is selected.

A.1 Proof of Lemma 1

  • N_k(t) denotes the number of times arm k has been selected in the first t steps.The proof focuses on bounding E[N_k(T) I{τ_1 > T}].Source: §A.1 · p. 11
  • When no detection occurs by T, arm selection follows uniform sampling or the largest UCB index in a stochastic-bandit setting.This observation supports the proof’s first inequality for the arm-selection count.Source: §A.1 · p. 11
  • In proving the result, the authors follow the same argument as in the proof of Theorem 1 of, then sum over k ∈ K.Source: §A.1 · p. 11

A.2 Proof of Lemma 2

The appendix controls false alarms and detection delays using concentration bounds, then uses those event bounds to build a recursive regret bound across stationary segments.

A.2 Proof of Lemma 2

  • The proof of Lemma 2 defines the first detection time for each arm and bounds the probability of any arm’s detection using a union bound.Under a stationary environment, the stated stopping times have geometric distributions, with detection probability p = P(S_k,w > b).Source: §A.2 · pp. 11–12
  • The proof bounds p using McDiarmid’s inequality and a union bound for the zero-mean statistic S_k,w.The passage identifies these concentration steps but does not provide the resulting bound in the supplied text.Source: §A.2 · p. 12

A.3 Proof of Lemma 3

  • For the detection-delay analysis, uniform sampling ensures at least w/2 samples per arm in intervals longer than L/2, supporting a concentration bound.The proof also invokes McDiarmid’s inequality for the statistic defined in equation (12).Source: §A.3 · p. 12

A.4 Proof of Lemma 4

  • The proof of Lemma 4 bounds expected detection delay using uniform-sampling counts, McDiarmid’s inequality, and Lemma 3.Its displayed analysis conditions on a sufficiently large change magnitude relative to the threshold.Source: §A.4 · p. 13

A.5 Proof of Theorem 1

  • Theorem 1’s proof defines good events for correctly and efficiently detecting each change, then bounds regret recursively across segments.It repeats the argument M − 1 times, using the renewal property after the algorithm restarts.Source: §A.5 · p. 14
Loading 1802.03692v4…