A Scale Free Algorithm for Stochastic Bandits with Bounded Kurtosis
Not on the map. Why?
Abstract (arXiv)
Existing strategies for finite-armed stochastic bandits mostly depend on a parameter of scale that must be known in advance. Sometimes this is in the form of a bound on the payoffs, or the knowledge of a variance or subgaussian parameter. The notable exceptions are the analysis of Gaussian bandits with unknown mean and variance by Cowan and Katehakis [2015] and of uniform distributions with unknown support [Cowan and Katehakis, 2015]. The results derived in these specialised cases are generalised here to the non-parametric setup, where the learner knows only a bound on the kurtosis of the noise, which is a scale free measure of the extremity of outliers.
Key facts. Cited by 10 papers in the map (data through 14 Oct 2026). First posted on arXiv 27 Mar 2017.
Builds on
No reference list yet.
Built on by
Citing papers per year: 2021: 2; 2022: 0; 2023: 5; 2024: 0; 2025: 1; 2026: 2.
10 papers.
- 2021Regret Minimization in Heavy-Tailed Banditscited by 25
- 2021Optimal Rates of (Locally) Differentially Private Heavy-tailed Multi-Armed Banditscited by 25
- 2023Regret Distribution in Stochastic Bandits: Optimal Trade-off between Expectation and Tail Riskcited by 9
- 2023Variance-aware robust reinforcement learning with linear function approximation under heavy-tailed rewardscited by 8
- 2023Differentially Private Episodic Reinforcement Learning with Heavy-tailed Rewardscited by 4
- 2025Catoni Contextual Bandits are Robust to Heavy-tailed Rewardscited by 3
- 2023Forced Exploration in Bandit Problemscited by 1
- 2023(ε, u)-Adaptive Regret Minimization in Heavy-Tailed Banditscited by 0
- 2026Nonlinear Banditcited by 0
- 2026Reliable Scale-Free Bandits via Empirical Likelihoodcited by 0
- 2026Reliable Scale-Free Bandits via Empirical Likelihood13 Oct 2026
- 2026Nonlinear Bandit8 Jul 2026
- 2025Catoni Contextual Bandits are Robust to Heavy-tailed Rewards4 Feb 2025
- 2023Forced Exploration in Bandit Problems12 Dec 2023
- 2023(ε, u)-Adaptive Regret Minimization in Heavy-Tailed Bandits4 Oct 2023
- 2023Differentially Private Episodic Reinforcement Learning with Heavy-tailed Rewards1 Jun 2023
- 2023Regret Distribution in Stochastic Bandits: Optimal Trade-off between Expectation and Tail Risk10 Apr 2023
- 2023Variance-aware robust reinforcement learning with linear function approximation under heavy-tailed rewards9 Mar 2023
- 2021Optimal Rates of (Locally) Differentially Private Heavy-tailed Multi-Armed Bandits4 Jun 2021
- 2021Regret Minimization in Heavy-Tailed Bandits7 Feb 2021