For heavy-tailed piecewise-stationary bandits, this paper presents a Catoni-style change-point detector and a UCB-style algorithm whose regret matches a claimed lower bound up to logarithmic factors.
Catoni-style Confidence Sequences under Infinite Variance
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
In this paper, we provide an extension of confidence sequences for settings where the variance of the data-generating distribution does not exist or is infinite. Confidence sequences furnish confidence intervals that are valid at arbitrary data-dependent stopping times, naturally having a wide range of applications. We first establish a lower bound for the width of the Catoni-style confidence sequences for the finite variance case to highlight the looseness of the existing results. Next, we derive tight Catoni-style confidence sequences for data distributions having a relaxed bounded~$p^{th}-$moment, where~$p \in (1,2]$, and strengthen the results for the finite variance case of~$p =2$. The derived results are shown to better than confidence sequences obtained using Dubins-Savage inequality.
citation-role summary
method 1
citation-polarity summary
fields
cs.LG 1years
2025 1verdicts
REJECT 1roles
method 1polarities
use method 1representative citing papers
citing papers explorer
-
Catoni-Style Change Point Detection for Regret Minimization in Non-Stationary Heavy-Tailed Bandits
For heavy-tailed piecewise-stationary bandits, this paper presents a Catoni-style change-point detector and a UCB-style algorithm whose regret matches a claimed lower bound up to logarithmic factors.