Pith. sign in

REVIEW 3 major objections 5 minor 31 references

Catoni-Style Change Point Detection for Regret Minimization in Non-Stationary Heavy-Tailed Bandits

T0 review · 3 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Heavy-tailed bandits with changing means get a near-optimal algorithm, the paper claims.

desk verdict Both the confidence sequence and the lower bound fail on inspection; the combination is worth a referee, but the version as written doesn't stand. read the letter →

arxiv 2505.20051 v1 pith:WB6MGRFK submitted 2025-05-26 cs.LG

Gianmarco Genalti , Sujay Bhatt , Nicola Gatti , Alberto Maria Metelli This is my paper
classification cs.LG MSC 68Q3262L10
keywords heavy-tailedbanditspiecewise-stationarynon-stationaryregretminimizationchange-pointdetectionconfidencesequencesCatoniestimatorinfinitevariance
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper introduces the heavy-tailed piecewise-stationary bandit setting, in which each arm's reward distribution can change at unknown times and rewards need only satisfy a bounded centered absolute moment of order $1+\epsilon$. It proposes Robust-CPD-UCB, an algorithm that combines a stationary heavy-tailed bandit policy with a Catoni-style confidence-sequence change-point detector, and proves an expected regret bound of order $\widetilde{O}((K\Upsilon)^{\epsilon/(1+\epsilon)}(vT)^{1/(1+\epsilon)})$. The paper also states a matching minimax lower bound, which would make the algorithm nearly optimal in its dependence on the number of arms, breakpoints, tail moment, and horizon. A sympathetic reader would care because this is the first treatment of non-stationary bandits under infinite-variance rewards, a setting relevant to finance and telecommunications.

What carries the argument

The load-bearing object is the Catoni-FCS-detector: a repeated-FCS-detector whose confidence intervals are defined through the Catoni influence function $\phi_\epsilon(u)=\log\left(1+|u|+\frac{|u|^{1+\epsilon}}{1+\epsilon}\right)$ and predictable weights, with the confidence level stitched over an exponential grid. At every round a new confidence sequence for the mean is opened, all open sequences are updated with the new sample, and a change is declared when the intersection of all open intervals becomes empty. The detector converts mean-estimation concentration into a sequential change-point test that works for infinite-variance observations; the bandit algorithm adds cyclic uniform exploration so every arm has enough fresh samples for the detector, and resets the policy when a change is declared.

What would settle it

Compute directly: for $p=v^{-1/\epsilon}\Delta^{(1+\epsilon)/\epsilon}$, let $X=0$ with probability $1-p$ and $X=v^{1/\epsilon}\Delta^{-1/\epsilon}$ with probability $p$. Then $E|X-EX|^{1+\epsilon}=v(1-p)(p^\epsilon+(1-p)^\epsilon)$, which exceeds $v$ for $\epsilon\in(0,1)$ and small $\Delta$. A reader who evaluates this for, say, $v=1$, $\epsilon=1/2$, $\Delta=1/10$ settles whether the lower bound's hard instances are admissible.

Watch

Extended reading notes

Core claim

The central claim is that heavy-tailed piecewise-stationary bandits admit a change-point detection method with finite-time guarantees and that this detector can be embedded in a bandit algorithm whose regret matches a new minimax lower bound. Specifically, Catoni-FCS-detector, an instantiation of repeated-FCS-detector using Catoni-style confidence sequences, is shown to detect a mean shift of size $\delta$ with high-probability delay $O(v^{1/\epsilon}\log(T)/\delta^{(1+\epsilon)/\epsilon})$ and false-alarm probability $O(1/T)$. Wrapped around a stationary heavy-tailed bandit sub-routine and a cyclic uniform-exploration schedule, this yields Robust-CPD-UCB; Theorem 4.8 decomposes its regret into detection-delay, stationary-policy, and exploration terms, and Corollary 4.11 concludes that, under an epoch-length assumption, the regret is $\widetilde{O}((K\Upsilon)^{\epsilon/(1+\epsilon)}(vT)^{1/(1+\epsilon)})$, matching the lower bound of Theorem 2.5 up to logarithmic factors.

Load-bearing premise

The proof that the algorithm is nearly optimal depends on the lower-bound construction $\rho_\Delta$ belonging to the heavy-tailed class $H(v,\epsilon)$, meaning $E|X-EX|^{1+\epsilon}\le v$; for $\epsilon\in(0,1)$ and small $\Delta$ this can be false, so the hard instance may lie outside the class the bound claims to cover.

Editorial extensions

If this is right

  • If the bounds are correct, a learner needs only the horizon $T$ to run the algorithm, not the number of change points, their magnitudes, or the suboptimality gaps, and still achieves the claimed minimax rate.
  • The stated lower bound would mean the cost of non-stationarity is exactly a factor $\Upsilon^{\epsilon/(1+\epsilon)}$ on top of the stationary heavy-tailed rate, combining the known $\Omega(K^{\epsilon/(1+\epsilon)}T^{1/(1+\epsilon)})$ and $\Omega(\sqrt{K\Upsilon T})$ bounds.
  • Catoni-FCS-detector is a standalone finite-time tool: it detects mean shifts in infinite-variance streams with high-probability delay bounds and false-alarm control, independent of the bandit application.
  • Using Robust UCB with a median-of-means estimator as the stationary sub-routine yields both instance-dependent and instance-independent regret bounds, so the framework can exploit known problem constants when they are available.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The claimed near-optimality is only as solid as the lower-bound construction. If, as a direct computation suggests, the two-point distributions used in Theorem 2.5 fail the moment condition $E|X-EX|^{1+\epsilon}\le v$ for $\epsilon\in(0,1)$, then the lower bound does not currently cover the class it claims to cover, and the matching claim would need a corrected construction.
  • A plausible repair is to replace the two-point distribution with a scaled Pareto-type or other heavy-tailed law whose exact centered $(1+\epsilon)$-moment equals $v$ and whose mean shift is $\Delta$, preserving the likelihood-ratio comparison while staying inside the distribution class.
  • The increasing exploration schedule that removes knowledge of $\Upsilon$ from the algorithm suggests an adaptive variant that estimates the recent change-point rate online and sets the exploration level accordingly; the paper does not analyze such a rule.
  • Experiments compare the detector against an empirical-Bernstein confidence-sequence detector on Gaussian and Laplace streams; testing on heavier-tailed streams such as log-normal or $\alpha$-stable laws across a grid of tail indices and shift sizes would give a sharper practical picture.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper studies regret minimization in piecewise-stationary bandits with heavy-tailed rewards, where each epoch's reward distributions satisfy a centered absolute moment condition E|X-E[X]|^{1+epsilon} <= v. It introduces Catoni-FCS-detector, a change-point detector based on Catoni-style confidence sequences, and combines it with a stationary robust bandit subroutine in an algorithm called Robust-CPD-UCB. The paper claims a minimax lower bound on regret for this setting, an upper bound for R-CPD-UCB, near-optimality up to log factors, and supporting numerical experiments on synthetic and real data. The main theoretical results are Theorem 2.5 (lower bound), Proposition 4.2 (detection delay), Theorem 4.8 (regret decomposition), and Corollaries 4.10-4.11 (instance-dependent and near-optimal regret bounds).

Significance. If the theoretical claims were valid, this would be a useful first treatment of piecewise-stationary heavy-tailed bandits, and the Catoni-FCS-detector would be an interesting standalone contribution. The paper is well structured, the experiments are clearly described, and the dependency of the regret bound on T, K, Upsilon, and v is the right target for this setting. The reduction of change-point detection to confidence sequences is borrowed from published work, and the paper's analysis is not circular with respect to those results. However, the validity of the central claims is undermined by a load-bearing error in the Catoni confidence-sequence construction and by an invalid lower-bound hard instance. As a result, the paper's main theoretical conclusions are not currently supported.

major comments (3)
  1. [Section 4.1, Eq. (3), Eq. (5), and Appendix B, Steps 1-3] The Catoni influence function is defined as phi_epsilon(x) = log(1 + |x| + |x|^{1+epsilon}/(1+epsilon)), which is even and nonnegative. Consequently, the estimating equation sum_{i=1}^t phi_epsilon(lambda_i(X_i - m)) = 0 has no solution unless every observed X_i equals m, so the Catoni estimator and the 'random solution of f_t(m)=0' used in Step 3 do not exist for a non-degenerate sample. The proof in Step 1 additionally claims E[exp(phi(lambda(X-mu)) - lambda^{1+epsilon} v/(1+epsilon))] <= E[1 + lambda(X-mu) + lambda^{1+epsilon}(X-mu)^{1+epsilon}/(1+epsilon)] exp(-lambda^{1+epsilon} v/(1+epsilon)), but exp(phi(u)) = 1 + |u| + |u|^{1+epsilon}/(1+epsilon), which is not bounded by 1+u+u^{1+epsilon}/(1+epsilon) for negative u, and the centered-moment assumption controls E|X-mu|^{1+epsilon}, not E[(X-mu)^{1+epsilon}]. Step 3 also asserts that f_t(m) is non-increasing in m, which is false for the even function phi. These errors invalidate the confidence-sequence construction, and therefore Proposition 4.2, Theorem 4.8, and Corollaries 4.10-4.11 are unsupported.
  2. [Section 2.3 and Appendix B, proof of Theorem 2.5] The two-point hard-instance distribution rho_y is asserted to belong to H(v,epsilon), but with the parameters chosen in the proof it does not satisfy the centered moment condition. For the suboptimal arm with y = Delta, writing p = v^{-1/epsilon} Delta^{(1+epsilon)/epsilon} and r = v^{1/epsilon} Delta^{-1/epsilon}, the centered (1+epsilon)-moment equals E|X-EX|^{1+epsilon} = v (1-p)(p^epsilon + (1-p)^epsilon). When Delta is set as in the proof, p = 2 log(2) K Upsilon / (16 T), which is small for large T. For epsilon in (0,1), the function f(p) = (1-p)(p^epsilon + (1-p)^epsilon) satisfies f(0)=1 and f'(0+)=+infinity, so f(p) > 1 for all sufficiently small p>0; hence E|X-EX|^{1+epsilon} > v, contradicting membership in H(v,epsilon). The same issue affects the good arm with y = 2^{epsilon/(1+epsilon)} Delta, whose p is 2 log(2) K Upsilon / (16 T). Thus the hard instances are outside the stated class and the lower bound of Theorem 2.5 is not established. The proof also states 'rho_y in H(1,epsilon)' rather than H(v,epsilon), and uses y = 2^{epsilon/(1+epsilon)} Delta even though the preceding sentence restricts y to [0,Delta].
  3. [Appendix B, Step 5 and Lemma B.2] The detection-delay proof and the regret proof rely on controlling the widths of all initialized confidence sequences simultaneously and on a union bound over O(T^2) events. The stated probability P(W_{1:t}) >= 1 - t(t+1)gamma/8 and the subsequent bound P(W_{a:b}) >= 1 - T(T+1)gamma/8 do not follow from the previous width bound when gamma = 2/T^3, because T(T+1)gamma/8 = O(1/T) is acceptable only if the union bound constant is correct; moreover the width bound itself depends on the invalid Step 3. Since Step 3 is the foundation for the width, the finite-time delay bound in Proposition 4.2 and the regret bound in Theorem 4.8 cannot be repaired without reworking the confidence-sequence construction.
minor comments (5)
  1. [Abstract and Section 2.1] The abstract cites 'heavy-tailed bandits, introduced by 7' instead of the proper reference; the author-year citation should be restored.
  2. [Eq. (5)] The interval notation with '\mp' and '\pm' is ambiguous and appears to be a typesetting artifact; the endpoints of the confidence interval should be written explicitly with a lower bound and an upper bound.
  3. [Section 5.2 and Appendix C.2] The main text refers to 'Figure 5' for the regret plots on Gaussian and Pareto rewards, but the corresponding figures in the text are labeled differently; the figure numbering should be made consistent.
  4. [Appendix C.3] The caption of Figure 8 states epsilon < 1 and v = 3, while the text of C.3 says v = 1; these values should be reconciled.
  5. [Section 5.2] The phrase 'we have delta_min = 0, i.e., and some actions may not change' contains a typo; it should read 'i.e., some actions may not change.'

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the regret bounds are derived from in-place proofs plus external confidence-sequence and change-point results; the coauthor self-citations are supporting and not load-bearing.

full rationale

The derivation chain is not circular. Theorem 4.8 decomposes the regret of R-CPD-UCB into detection delay (A), stationary regret (B), and forced exploration (C), and each term is bounded by in-place arguments: Proposition 4.2 and Appendix B prove the Catoni-FCS detection-delay bound, Lemma B.2 controls the failure event, and Corollaries 4.9-4.11 combine these with the external Robust-UCB guarantees of Bubeck et al. [7] and the repeated-FCS framework of Shekhar and Ramdas [26]. No parameter is fitted to a subset of data and then renamed as a prediction; the exploration schedule η_j is fixed a priori and the matching rate in Equation (11) follows algebraically from the earlier bounds under the stated explicit conditions. Theorem 2.5's lower bound is a standard two-point/Pinsker construction whose 'easy to verify' membership claim is a mathematical assertion, not a definitional identity with the upper bound. Self-citations exist ([5], [6], [12]), but they are not the load-bearing justification for the central claim: the Catoni CS width is re-derived in Appendix B rather than imported solely from [6], and [12] is used only as one technique in the lower-bound proof. Correctness concerns raised about the Catoni influence function being even and nonnegative, or about the heavy-tailed moment condition in the two-point construction, are substantive correctness risks but do not exhibit any equation that is equal to another by construction or any fitted input renamed as a prediction. The paper is therefore self-contained for the purpose of circularity analysis, and no circular step is exhibited.

Assumptions & free parameters 1 free parameters · 4 assumptions · 0 invented entities

The central theoretical claims rest on the centered moment assumption, the epoch-length assumption, and the correctness of the cited Catoni CS and Robust UCB bounds. The lower bound additionally requires the hard instances to satisfy the moment assumption, which they do not for ε<1. The algorithm has one user-chosen exploration coefficient η.

free parameters (1)
  • uniform exploration coefficient η = not fitted; user-specified or set to the schedule η0 sqrt(jK log(T)/T)
    The regret bound in Theorem 4.8 depends on η through terms (A) and (C), and the paper provides a theoretically motivated schedule requiring a constant η0. It is chosen by hand, not fitted to data.
assumptions (4)
  • domain assumption Reward distributions satisfy E[|X - E[X]|^{1+ε}] ≤ v for known ε ∈ (0,1] and v > 0.
    Definition 2.1; the algorithm's Catoni CS width and regret bounds use v and ε as inputs.
  • domain assumption Every epoch is long enough that Assumption 4.7 holds: |E_j| ≥ 2 n_min + 2⌈L_j K/η⌉.
    Assumption 4.7 is required for the regret decomposition and the detection-delay bound in Theorem 4.8.
  • ad hoc to paper The two-point hard-instance distributions ρ_y in the lower-bound proof belong to H(v,ε).
    Invoked in Theorem 2.5 proof as 'easy to verify'; false for ε<1, so the lower bound is unproven.
  • standard math The stationary policy π_s (Robust UCB with median-of-means) has the regret bounds of Bubeck et al. 2013, Theorem 3 and Proposition 1.
    Used to obtain Corollary 4.10 from the general regret decomposition.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Catoni-Style Change Point Detection for Regret Minimization in Non-Stationary Heavy-Tailed Bandits." pith.science (2026). https://pith.science/paper/WB6MGRFK

@misc{pith2026250520051,
  author       = {Pith},
  title        = {Pith review of: Catoni-Style Change Point Detection for Regret Minimization in Non-Stationary Heavy-Tailed Bandits},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/WB6MGRFK}},
  note         = {Machine review of arXiv:2505.20051}
}
abstract

Regret minimization in stochastic non-stationary bandits gained popularity over the last decade, as it can model a broad class of real-world problems, from advertising to recommendation systems. Existing literature relies on various assumptions about the reward-generating process, such as Bernoulli or subgaussian rewards. However, in settings such as finance and telecommunications, heavy-tailed distributions naturally arise. In this work, we tackle the heavy-tailed piecewise-stationary bandit problem. Heavy-tailed bandits, introduced by Bubeck et al., 2013, operate on the minimal assumption that the finite absolute centered moments of maximum order $1+\epsilon$ are uniformly bounded by a constant $v<+\infty$, for some $\epsilon \in (0,1]$. We focus on the most popular non-stationary bandit setting, i.e., the piecewise-stationary setting, in which the mean of reward-generating distributions may change at unknown time steps. We provide a novel Catoni-style change-point detection strategy tailored for heavy-tailed distributions that relies on recent advancements in the theory of sequential estimation, which is of independent interest. We introduce Robust-CPD-UCB, which combines this change-point detection strategy with optimistic algorithms for bandits, providing its regret upper bound and an impossibility result on the minimum attainable regret for any policy. Finally, we validate our approach through numerical experiments on synthetic and real-world datasets.

Figures

Figures reproduced from arXiv: 2505.20051 by the authors.

Figure 1
Figure 1. Rescaled closing prices of four selected cryptocurrencies (blue) with a piecewise-constant [PITH_FULL_IMAGE:figures/full_fig_p009_1.png] view at source ↗
Figure 2
Figure 2. Cumulative regrets on HTPS built from cryptocurrency dataset. 20 trials, mean ± std. 0 300 600 900 1200 1500 t 0 100 200 300 400 500 R-CPD-UCB M-UCB SW-UCB Change-point (a) Gaussian rewards. 0 300 600 900 1200 1500 t 0 100 200 300 400 500 600 700 800 R-CPD-UCB M-UCB SW-UCB Change-point (b) Pareto rewards [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗
Figure 4
Figure 4. Distribution delay distribution over 20 trials. 0 300 600 900 1200 1500 t 0 100 200 300 400 500 R-CPD-UCB M-UCB SW-UCB Change-point (a) Gaussian rewards. 0 300 600 900 1200 1500 t 0 100 200 300 400 500 600 700 800 R-CPD-UCB M-UCB SW-UCB Change-point (b) Pareto rewards [PITH_FULL_IMAGE:figures/full_fig_p021_4.png] view at source ↗
Figures from the paper (6 more)
Figure 5
Figure 5. Figure 5: Cumulative regrets of the considered algorithms. We performed [PITH_FULL_IMAGE:figures/full_fig_p021_5.png]
Figure 6
Figure 6. Figure 6: Mean rewards per epoch. Cells highlighted in yellow contain the optimal reward for the [PITH_FULL_IMAGE:figures/full_fig_p022_6.png]
Figure 7
Figure 7. Figure 7: Average rewards per epoch. C.3 Sensibility to δ In this section, we study the sensibility of R-CPD-UCB to different magnitudes of changes. Setting We consider four HTPS MABs with Pareto rewards (ϵ < 1, v = 1), K = 3, T = 500, and Υ = 1. The starting means are µ1 = 1, µ…
Figure 8
Figure 8. Figure 8: HTPS MABs with different magnitudes of change. For all instances: [PITH_FULL_IMAGE:figures/full_fig_p023_8.png]
Figure 9
Figure 9. Figure 9: Cumulative regrets of R-CPD-UCB in the four HTPS MABs represented in [PITH_FULL_IMAGE:figures/full_fig_p023_9.png]
Figure 10
Figure 10. Figure 10: Cumulative regrets of R-CPD-UCB, Robust UCB [7], and MR-APE [19] on the four HT MABs defined in [PITH_FULL_IMAGE:figures/full_fig_p024_10.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

31 extracted references · 29 canonical work pages

  1. [5]

    Piecewise stationary bandits under risk criteria

    Sujay Bhatt, Guanhua Fang, and Ping Li. Piecewise stationary bandits under risk criteria. In International Conference on Artificial Intelligence and Statistics, pages 4313–4335. PMLR, 2023

    work page 2023

  2. [1]

    Improved algorithms for linear stochastic bandits

    Yasin Abbasi-Yadkori, D´avid P ´al, and Csaba Szepesv ´ari. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011

    work page 2011

  3. [2]

    Adaptively tracking the best bandit arm with an unknown number of distribution changes

    Peter Auer, Pratik Gajane, and Ronald Ortner. Adaptively tracking the best bandit arm with an unknown number of distribution changes. In Conference on Learning Theory, pages 138–158. PMLR, 2019

    work page 2019

  4. [3]

    Stochastic multi-armed-bandit problem with non-stationary rewards

    Omar Besbes, Yonatan Gur, and Assaf Zeevi. Stochastic multi-armed-bandit problem with non-stationary rewards. Advances in neural information processing systems, 27, 2014

    2014

  5. [4]

    Efficient change-point detection for tackling piecewise-stationary bandits

    Lilian Besson, Emilie Kaufmann, Odalric-Ambrym Maillard, and Julien Seznec. Efficient change-point detection for tackling piecewise-stationary bandits. Journal of Machine Learning Research, 23(77):1–40, 2022

    work page 2022

  6. [6]

    Catoni-style Confidence Sequences under Infinite Variance

    Sujay Bhatt, Guanhua Fang, Ping Li, and Gennady Samorodnitsky. Catoni-style confidence sequences under infinite variance. arXiv preprint arXiv:2208.03185, 2022

    work page Pith review arXiv 2022

  7. [7]

    Bandits with heavy tail

    S´ebastien Bubeck, Nicolo Cesa-Bianchi, and G ´abor Lugosi. Bandits with heavy tail. IEEE Transactions on Information Theory, 59(11):7711–7717, 2013

    work page 2013

  8. [8]

    Nearly optimal adaptive procedure with change detection for piecewise-stationary bandit

    Yang Cao, Zheng Wen, Branislav Kveton, and Yao Xie. Nearly optimal adaptive procedure with change detection for piecewise-stationary bandit. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 418–427. PMLR, 2019

    work page 2019

Show all 31 references
  1. [9]

    Challenging the empirical mean and empirical variance: a deviation study

    Olivier Catoni. Challenging the empirical mean and empirical variance: a deviation study. In Annales de l’IHP Probabilit´es et statistiques, volume 48, pages 1148–1185, 2012

    2012

  2. [10]

    Explore first, exploit next: The true shape of regret in bandit problems

    Aur´elien Garivier, Pierre M´enard, and Gilles Stoltz. Explore first, exploit next: The true shape of regret in bandit problems. Mathematics of Operations Research, 44(2):377–399, 2019

    2019

  3. [11]

    On upper-confidence bound policies for switching bandit problems

    Aur´elien Garivier and Eric Moulines. On upper-confidence bound policies for switching bandit problems. In International conference on algorithmic learning theory, pages 174–188. Springer, 2011

    2011

  4. [12]

    (ϵ, u)-adaptive regret minimization in heavy-tailed bandits

    Gianmarco Genalti, Lupo Marsigli, Nicola Gatti, and Alberto Maria Metelli. (ϵ, u)-adaptive regret minimization in heavy-tailed bandits. In The Thirty Seventh Annual Conference on Learning Theory, pages 1882–1915. PMLR, 2024

    1915

  5. [13]

    Graph-triggered rising bandits

    Gianmarco Genalti, Marco Mussi, Nicola Gatti, Marcello Restelli, Matteo Castiglioni, and Alberto Maria Metelli. Graph-triggered rising bandits. In Forty-first International Conference on Machine Learning, 2024

    2024

  6. [14]

    Change point detection and meta-bandits for online learning in dynamic environments

    C´edric Hartland, Nicolas Baskiotis, Sylvain Gelly, Michele Sebag, and Olivier Teytaud. Change point detection and meta-bandits for online learning in dynamic environments. In CAp 2007: 9`e Conf´erence francophone sur l’apprentissage automatique, pages 237–250, 2007

    2007

  7. [15]

    Tight policy regret bounds for improving and decaying bandits

    Hoda Heidari, Michael J Kearns, and Aaron Roth. Tight policy regret bounds for improving and decaying bandits. In IJCAI, pages 1562–1570, 2016

    2016

  8. [16]

    Time-uniform, nonparametric, nonasymptotic confidence sequences

    Steven R Howard, Aaditya Ramdas, Jon McAuliffe, and Jasjeet Sekhon. Time-uniform, nonparametric, nonasymptotic confidence sequences. The Annals of Statistics, 49(2), 2021

    2021

  9. [17]

    Discounted ucb

    Levente Kocsis and Csaba Szepesv´ari. Discounted ucb. In 2nd PASCAL Challenges Workshop, volume 2, pages 51–134, 2006

    2006

  10. [18]

    Bandit algorithms

    Tor Lattimore and Csaba Szepesv ´ari. Bandit algorithms. Cambridge University Press, 2020

    2020

  11. [19]

    Minimax optimal bandits for heavy tail rewards

    Kyungjae Lee and Sungbin Lim. Minimax optimal bandits for heavy tail rewards. IEEE Transactions on Neural Networks and Learning Systems, 35(4):5280–5294, 2022. 10

    2022

  12. [20]

    A change-detection based framework for piecewise- stationary multi-armed bandit problem

    Fang Liu, Joohyun Lee, and Ness Shroff. A change-detection based framework for piecewise- stationary multi-armed bandit problem. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018

    2018

  13. [21]

    Procedures for reacting to a change in distribution

    Gary Lorden. Procedures for reacting to a change in distribution. The annals of mathematical statistics, pages 1897–1908, 1971

    1908

  14. [22]

    Stochastic rising bandits

    Alberto Maria Metelli, Francesco Trovo, Matteo Pirola, and Marcello Restelli. Stochastic rising bandits. In International Conference on Machine Learning, pages 15421–15457. PMLR, 2022

    2022

  15. [23]

    Model selection test for the heavy-tailed distributions under censored samples with application in financial data

    Hanieh Panahi. Model selection test for the heavy-tailed distributions under censored samples with application in financial data. International Journal of Financial Studies, 4(4):24, 2016

    2016

  16. [24]

    Rotting bandits are no harder than stochastic ones

    Julien Seznec, Andrea Locatelli, Alexandra Carpentier, Alessandro Lazaric, and Michal Valko. Rotting bandits are no harder than stochastic ones. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 2564–2572. PMLR, 2019

    2019

  17. [25]

    A single algorithm for both restless and rested rotting bandits

    Julien Seznec, Pierre Menard, Alessandro Lazaric, and Michal Valko. A single algorithm for both restless and rested rotting bandits. In International Conference on Artificial Intelligence and Statistics, pages 3784–3794. PMLR, 2020

    2020

  18. [26]

    Reducing sequential change detection to sequential estimation

    Shubhanshu Shekhar and Aaditya Ramdas. Reducing sequential change detection to sequential estimation. arXiv preprint arXiv:2309.09111, 2023

    2023 arXiv

  19. [27]

    Sequential changepoint detection via backward confidence sequences

    Shubhanshu Shekhar and Aaditya Ramdas. Sequential changepoint detection via backward confidence sequences. In International Conference on Machine Learning, pages 30908–30930. PMLR, 2023

    2023

  20. [28]

    Catoni-style confidence sequences for heavy-tailed mean estimation

    Hongjian Wang and Aaditya Ramdas. Catoni-style confidence sequences for heavy-tailed mean estimation. Stochastic Processes and Their Applications, 163:168–202, 2023

    2023

  21. [29]

    Piecewise-stationary bandit problems with side observations

    Jia Yuan Yu and Shie Mannor. Piecewise-stationary bandit problems with side observations. In Proceedings of the 26th annual international conference on machine learning, pages 1177–1184, 2009

    2009

  22. [30]

    N (j) i |Ej| # − 1 K KX i=1 E(i∗ −j ,0)

    Xiaotian Yu, Han Shao, Michael R Lyu, and Irwin King. Pure exploration of multi-armed bandits with heavy-tailed payoffs. In UAI, pages 937–946, 2018. 11 A Additional Related Works on Non-Stationary MABs In this appendix, we discuss more in detail the related works on non-stati...

    2018

  23. [31]

    Then, there exists a predictable sequence {λi}T i=1 s.t

    Set γ = 2 T 3 . Then, there exists a predictable sequence {λi}T i=1 s.t. Catoni-FCS-detector enjoys (i) Ptc (τ − tc)+ ≤ O v 1 ϵ log(T ) δ 1+ϵ ϵ ≥ 1 − 14 T and (ii) Ptc (τ < tc) ≤ 14 T . Proof. Due to its length, we divided this proof into several steps. In Steps 1-3 we extend ...

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.