# Reliable Scale-Free Bandits via Empirical Likelihood

arXiv: https://arxiv.org/abs/2610.18055 · HTML: https://mlsanity.com/paper/2610.18055/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 17 of its 40 references that are in the map.
- First posted on arXiv 13 Oct 2026.

## Builds on (most cited first, 17 of 17)

- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [Statistics of Robust Optimization: A Generalized Empirical Likelihood Approach](https://mlsanity.com/paper/1610.03425/) (2016)
- [Regret Minimization in Heavy-Tailed Bandits](https://mlsanity.com/paper/2102.03734/) (2021)
- [The Fragility of Optimized Bandit Algorithms](https://mlsanity.com/paper/2109.13595/) (2021)
- [Adaptation to the Range in K-Armed Bandits](https://mlsanity.com/paper/2006.03378/) (2020)
- [Bandit algorithms: Letting go of logarithmic regret for statistical robustness](https://mlsanity.com/paper/2006.12038/) (2020)
- [A Scale Free Algorithm for Stochastic Bandits with Bounded Kurtosis](https://mlsanity.com/paper/1703.08937/) (2017)
- [Regret Distribution in Stochastic Bandits: Optimal Trade-off between Expectation and Tail Risk](https://mlsanity.com/paper/2304.04341/) (2023)
- [Empirical Likelihood for Contextual Bandits](https://mlsanity.com/paper/1906.03323/) (2019)
- [An Asymptotically Optimal Policy for Uniform Bandits of Unknown Support](https://mlsanity.com/paper/1505.01918/) (2015)
- [A Simple and Optimal Policy Design with Safety against Heavy-Tailed Risk for Stochastic Bandits](https://mlsanity.com/paper/2206.02969/) (2022)
- [Data-Driven Upper Confidence Bounds with Near-Optimal Regret for Heavy-Tailed Bandits](https://mlsanity.com/paper/2406.05710/) (2024)
- [Bayesian Inference of Contextual Bandit Policies via Empirical Likelihood](https://mlsanity.com/paper/2602.10608/) (2026)
- [Parameter-Free Heavy-Tailed Bandits](https://mlsanity.com/paper/2607.29460/) (2026)
- [Forced Exploration in Bandit Problems](https://mlsanity.com/paper/2312.07285/) (2023)
- [Regret Tail Characterization of Optimal Bandit Algorithms with Generic Rewards](https://mlsanity.com/paper/2604.14876/) (2026)

## Abstract (arXiv)

We study stochastic bandits without knowledge of reward scales or tail parameters. Almost-sure regret guarantees describe eventual learning but do not quantify expected performance or the risk of large regret in a finite run. We introduce textttEL-F, an anytime empirical-likelihood (EL) extension of the g-Forcing policy of Cowan and Katehakis (2020), and characterize its performance at three levels. First, for integrable rewards and non-decreasing, diverging exploration schedules g with vanishing increments, textttEL-F preserves the g-Forcing asymptotics for pseudo-regret R(T): R(T)/g(T)→sumi:Deltai>0Deltai almost surely as T→∞, where Deltai is the suboptimality gap of arm i. Second, on every sub-exponential instance, for non-decreasing g(t)=ω(log t) satisfying a mild feasibility condition, expected pseudo-regret is at most g(T)sumi:Deltai>0Deltai+C_underlineP, where C_underlineP is an instance-dependent constant independent of T. Moreover, we also establish finite-time tail bounds with super-polynomial decay in regret beyond the forced-exploration budget. For slowly varying g, we determine the exact exponent of linear regret deviations on two-armed Gaussian instances with common variance and establish a matching lower bound among policies satisfying the same expected-regret budget on every such Gaussian instance. These quantitative guarantees also cover the greedy variant obtained at zero EL radius. A fixed positive radius introduces local optimism while preserving the leading asymptotic regret. We establish coupled pathwise dominance over the greedy variant in two-armed bandits with a deterministic suboptimal arm. Experiments demonstrate reductions in prolonged suboptimal allocation compared with g-Forcing on challenging instances.