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

Gianmarco Genalti, Sujay Bhatt, Nicola Gatti, Alberto Maria Metelli · 2025

Read Catoni-Style Change Point Detection for Regret Minimization in Non-Stationary Heavy-Tailed Bandits by Gianmarco Genalti, Sujay Bhatt, Nicola Gatti, Alberto Maria Metelli (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-20051.txt.

Introduction

Gianmarco Genalti, Sujay Bhatt, Nicola Gatti, and Alberto Metelli tackle a hard choice problem, in a research paper from 2025. In bandit problems, a system picks among options again and again to earn the most reward. Here the best option can change at unknown times, and rewards can have rare, very large values.

The team adds a new way to spot when the rewards have changed. Their method is built to stay calm in the face of those extreme values. They prove limits on how much reward any method must lose, then test their approach on both made-up and real data sets.

Catalog record

CREATORGianmarco Genalti, Sujay Bhatt, Nicola Gatti, Alberto Maria Metelli
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE84 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-20051

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Catoni-Style Change Point Detection for Regret Minimization in Non-Stationary Heavy-Tailed Bandits Gianmarco Genalti, Sujay Bhatt, Nicola Gatti, Alberto Maria Metelli 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 7 , operate on the minimal assumption that the finite absolute centered moments of maximum order 1 + ϵ 1+\epsilon are uniformly bounded by a constant v < + ∞ v<+\infty , for some ϵ ∈ ( 0 , 1 ] \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. 1 Introduction In a Multi-Armed Bandit (MAB, for short, 18 ), a decision-maker (also called learner ) is faced with a sequence of repeated decisions among a fixed number of options (or actions or arms ), observing a reward drawn from a probability distribution after each decision. MABs gained popularity over the last two decades, as they allow for strong theoretical guarantees over algorithms’ performance while maintaining the model’s generality. However, the most traditional MAB model relies on demanding assumptions that are rarely met in the real world. The majority of the research effort in the MAB literature focused on progressively overcoming these limitations to cover richer scenarios. Examples include non-stationary ( 3 ) , linear ( 1 ) , and heavy-tailed ( 7 ) MABs. In this work, we focus on a broad class of problems that relaxes, at the same time, two core assumptions of the standard MAB problem. In particular, we focus on heavy-tailed non-stationary MABs. Our framework allows for a general class of reward-generating probability distributions without relying on parametric assumptions and with a possibly infinite variance, called heavy-tailed distributions. This setting gained popularity over the last decade due to its applications in finance and telecommunications. Moreover, it extends the assumption of sub-gaussian reward distributions, which is customary in the MAB literature. In such application domains, the assumption that reward-generating distributions are fixed along the whole time horizon is too limiting. It is natural to consider settings, such as finance, characterized by non-stationary processes. We address, with a single algorithm named Robust-CPD-UCB , the problem of learning in non-stationary environments where the noise of the observations can be heavy-tailed. We prove theoretical guarantees over the performance of R-CPD-UCB and show that they are nearly optimal under some mild assumptions. To the best of the authors’ knowledge, this is the first work to address the problem of regret minimization in non-stationary bandits under infinite-variance reward distributions. In particular, we face the technical challenge of developing the first change-point detection strategy with proven theoretical guarantees for such types of distributions. The contributions are organized as follows: • In Section 2 , we introduce the definition of the heavy-tailed piecewise-stationary MAB setting. We define the learning problem and introduce a lower bound on the expected regret for this setting. • In Section 3 , we recall some notions and results from the existing literature on mean estimation for heavy-tailed random variables and on change-point detection. • In Section 4 , we introduce Robust-CPD-UCB , an algorithm from regret minimization in our setting. We provide theoretical guarantees on its expected regret and insights on choosing its parameters. • Finally, in Section 5 (and Appendix C ), we provide numerical evaluations of the performance of R-CPD-UCB , comparing it with baselines from the literature on both real-world and synthetic data. 2 Problem Formulation In this section, we recall the definitions of heavy-tailed and piecewise-stationary bandit. Then, we introduce the heavy-tailed piecewise-stationary bandits, the focus of this work. We formally define the problem of regret minimization and provide a novel regret lower bound for the problem. 2.1 Bandit Settings Every round t\in[T]\coloneqq\{1,\ldots,T\} , a decision I_{t}\in[K] is undertaken (possibly at random) and a reward X_{I_{t},t} is sampled from a probability distribution \nu_{I_{t}} . We call the set \bm{\nu}=\{\nu_{i}\}_{i\in[K]} of reward-generating distributions an instance of the MAB (from now on, just MAB). Most of the literature deals with reward-generating distributions either sub-gaussian or with bounded supports. Heavy-Tailed Bandits. In heavy-tailed bandits [ 7 ] , the probability distributions \{\nu_{i}\}_{i=1}^{K} are heavy-tailed . In this work, we use the same definition of heavy-tailed MAB (HT MAB, for short). Definition 2.1 (Heavy-Tailed MAB) . Let X\sim\nu be a random variable with support on \mathbb{R} . Then, we call X a heavy-tailed random variable if it satisfies \mathbb{E}_{\nu}[|X-\mathbb{E}_{\nu}[X]|^{1+\epsilon}]\leq v, (1) for \epsilon\in(0,1] and v\in\mathbb{R}^{+} . Let \bm{\nu} be a MAB. Then, if \bm{\nu}\in\mathcal{H}_{(v,\epsilon)}^{K} , where \mathcal{H}_{(v,\epsilon)} is the set of probability distributions satisfying Equation ( 1 ), we call \bm{\nu} a heavy-tailed bandit (HT MAB, for short). Note that Equation ( 1 ) implies that the variance of the rewards-generating distributions may be infinite (when \epsilon<1 ). Most of the technical tools employed for sub-gaussian rewards are ineffective for HT MABs. We address readers to [ 12 ] for a recent literature review on HT MABs. Piecewise-Stationary Bandits. In standard MABs, the reward-generating distributions are assumed to never change during learning. In non-stationary bandits , instead, the reward-generating distributions are dynamic in time, i.e. , the rewards of the same arm are sampled from different distributions depending on the pull time t\in[T] . However, if there is no constraint on how many times the distributions may change, then the problem may quickly become non-tractable. Thus, in this work, we consider the most popular non-stationary MAB setting, i.e. , the piecewise-stationary bandit (PS MAB) from [ 29 ] , where the distributions of rewards remain constant for a certain period, called epoch , and then abruptly change at some unknown time points, called breakpoints . We assume that the total number of breakpoints \Upsilon\in[T] is fixed before the trial. We define a PS MAB as follows. Definition 2.2 (Piecewise-Stationary Bandit) . Let \{\bm{\nu}^{(j)}\}_{j\in[\Upsilon]} be a set of \Upsilon MABs. Then, let \Upsilon be a set of timesteps \{t_{c}^{(j)}\}_{j\in[\Upsilon]}\subset[T] and call E_{j} the set of indices \{t_{c}^{(j-1)},\ldots,t_{c}^{(j)}\} , where t_{c}^{(0)}=0 and t_{c}^{(\Upsilon+1)}=T , by convention. If \nu_{i}^{(j)} is the reward-generating distribution of arm i\in[K] when t\in E_{j} , then (\{\bm{\nu}^{(j)}\}_{j\in[\Upsilon]},\{t_{c}^{(j)}\}_{j\in[\Upsilon]}) defines a piecewise-stationary bandit (PS MAB, for short). E_{j} is the j -th epoch of the PS MAB, and t_{c}^{(j)} to the j -th breakpoint. To simplify notation, we define \mu_{i}^{(j)}\coloneqq\mathbb{E}_{\nu_{i}^{(j)}}[X_{i,t}] as the mean of the reward-generating distribution of action i during epoch j . Note that the reward-generating distribution of an action is fixed

Read the complete text