Reliable Scale-Free Bandits via Empirical Likelihood

Pratham Gupta; Alhad Sethi; Shubhada Agrawal

stat.MLOct 13, 2026

Reliable Scale-Free Bandits via Empirical Likelihood

Authors: Pratham Gupta, Alhad Sethi, Shubhada Agrawal

Organizations: Indian Institute of Science

Abstract

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 $\texttt{EL-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, $\texttt{EL-F}$ preserves the $g$ -Forcing asymptotics for pseudo-regret $R(T)$ : $R(T)/g(T)\to\sum_{i:Δ_i>0}Δ_i$ almost surely as $T\to\infty$ , where $Δ_i$ 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)\sum_{i:Δ_i>0}Δ_i+C_{\underline{P}}$ , where $C_{\underline{P}}$ 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.

Figures & tables

Algorithm	Anytime	Scale-free	Reward class	Regret guarantee	Regret tail
$g$ -Forcing [ Cowan and Katehakis, 2020 ]	$\surd$	$\surd$	finite mean a	$R(T)/g(T)\to\sum_{i}\Delta_{i}$ a.s.	not analyzed
R-UCB [ Ashutosh et al., 2021 ]	$\surd$	$\surd$	sub-exp.	$\mathcal{O}(g(T))$ in exp.	not analyzed
RDS [ Baudry et al., 2021 ]	$\surd$	$\surd$	sub-exp.	$\mathcal{O}(\log T\log\log T)$ in exp. b	not analyzed
FE [ Han et al., 2024 ]	$\times$ c	$\surd$	sub-Gaussian	$\mathcal{O}(\log^{2}T)$ in exp. d	not analyzed
AHB [ Hadiji and Stoltz, 2023 ]	$\surd$	$\surd$	bounded e	$\mathcal{O}(T^{1-\alpha})$ , $\alpha\in[\frac{1}{2},1)$ in exp.	not analyzed
Simchi-Levi et al. [2023]	$\surd$	$\times$ f	sub-Gaussian, sub-exp.	$\mathcal{O}(f(T))$ in exp.	$e^{-\Theta(f(x))}$ ; matching l.b.

Table 1: Comparison with existing work;

f\geq\log t

g=\omega(\log t)

, in exp.: in expectation, a.s.: almost surely. l.b.: lower bound a finite variance assumed for remainder-term bounds. b For

\rho_{n}=\mathcal{O}(\log n)

. c Near-logarithmic schedules take

T

as input; anytime schedule

f(r)=r

gives

\sqrt{T}

regret. d Equation 12 in their work. e Unknown range. Distribution-free regret is

\mathcal{O}(T^{\alpha})

; show lower bound that distribution-free regret

\Phi(T)=o(T)

implies distribution-dependent regret

\Omega(T/\Phi(T))

. f Means assumed in

[0,1]

. g

\mathrm{KL}

-UCB for known one-parameter exponential family,

f(t)=(1+b)\log t

gives tails

x^{-(1+b)}

Instance	$K$	Parameters	Means $(m_{a})_{a}$
Beta (wide gaps)	4	$(\alpha_{a},\beta_{a})\in\{(1,9),(3,7),(5,5),(8,2)\}$	$(5,\,15,\,25,\,40)$
Beta (small gaps)	5	$(\alpha_{a},\beta_{a})\in\{(5,10),(6,9),(7,8),(8,7),(9,6)\}$	$(16.67,\,20,\,23.33,\,26.67,\,30)$
Gaussian	4	$\sigma=10$	$(5,\,15,\,25,\,40)$
Exponential	4	rate $1/m_{a}$	$(5,\,15,\,25,\,40)$

Table 2: Instances used in experiments. Beta instances are scaled by 50 (arm

a

has law

50\cdot\mathrm{Beta}(\alpha_{a},\beta_{a})

); Gaussian arms are

N(m_{a},\sigma^{2})

and exponential arms are

\mathrm{Exp}(1/m_{a})

Figure 1: Pseudo-regret performance over

1{,}024

runs.

Policy	Beta (wide gaps)				Beta (small gaps)				Gaussian		Exponential
	$[0,1]$		$[0,50]$		$[0,1]$		$[0,50]$
	mean	med.	mean	med.	mean	med.	mean	med.	mean	med.	mean	med.
EL-F , $g_{1}$ , $C_{\mathrm{rad}}=0$	9.06	9.00	453	450	60.0	3.33	3,001	167	498	450	24,255	450
EL-F , $g_{1}$ , $C_{\mathrm{rad}}=3$	9.10	9.00	455	450	15.3	4.20	765	210	474	450	7,672	660
EL-F , $g_{2}$ , $C_{\mathrm{rad}}=0$	33.0	33.0	1,650	1,650	19.3	11.3	964	567	1,650	1,650	5,611	1,650
EL-F , $g_{2}$ , $C_{\mathrm{rad}}=3$	33.0	33.0	1,650	1,650	12.3	11.5	614	573	1,650	1,650	2,607	1,695

Table 3: Pseudo-regret at

T=10{,}000

over 1,024 independent runs, where

g_{1}(t)=\frac{1}{K}(\log t)\,(\log\log t)

and

g_{2}(t)=\frac{1}{K}(\log t)^{2}

, with

K

the number of arms.

Appendix figures & tables6 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 2: Mean pseudo-regret over

1{,}024

runs on all six instances, for every algorithm.

Figure 3: Empirical tail

\hat{P}(R_{T}>x)

of the final pseudo-regret over

1{,}024

runs on all six instances, for all the algorithms (

x

on a logarithmic scale).

Figure 4: Mean pseudo-regret for the radius ablation of EL-F over

1{,}024

runs on all six instances, under exploration schedules

g_{1}

and

g_{2}

Figure 5: Empirical tails of final pseudo-regret at

T=10{,}000

for the radius variants in Figure 4 , over

1{,}024

runs (

x

on a logarithmic scale).

Policy	Beta (wide gaps)				Beta (small gaps)				Gaussian		Exponential
	$[0,1]$		$[0,50]$		$[0,1]$		$[0,50]$
	mean	med.	mean	med.	mean	med.	mean	med.	mean	med.	mean	med.
EL-F , $g_{1}$ , $C_{\mathrm{rad}}=0$	9.06	9.00	453	450	60.0	3.33	3,001	167	498	450	24,255	450
EL-F , $g_{1}$ , $C_{\mathrm{rad}}=3$	9.10	9.00	455	450	15.3	4.20	765	210	474	450	7,672	660
EL-F , $g_{1}$ , $C_{\mathrm{rad}}=\log\log t+3$	9.13	9.00	456	450	11.7	5.20	586	260	484	450	6,994	855
EL-F , $g_{1}$ , $C_{\mathrm{rad}}=\log t+3$	9.20	9.00	460	450	14.8	8.83	742	442	523	450	6,906	1,755

Appendix

Table 4: Mean and median of the pseudo-regret

R(T)=\sum_{a}\Delta_{a}N_{a}(T+1)

T=10{,}000

over 1,024 independent runs, on all six instances, where

g_{1}(t)=\frac{1}{K}\log t\,\log\log t

and

g_{2}(t)=\frac{1}{K}(\log t)^{2}

, with

K

the number of arms.

Policy	Beta (wide gaps)		Beta (small gaps)		Gaussian	Exponential
	$[0,1]$	$[0,50]$	$[0,1]$	$[0,50]$
EL-F , $g_{1}$ , $C_{\mathrm{rad}}=0$	0.0	0.0	8.1	8.1	0.0	14.6
EL-F , $g_{1}$ , $C_{\mathrm{rad}}=3$	0.0	0.0	1.2	1.2	0.0	3.5
EL-F , $g_{2}$ , $C_{\mathrm{rad}}=0$	0.0	0.0	0.9	0.9	0.0	2.0
EL-F , $g_{2}$ , $C_{\mathrm{rad}}=3$	0.0	0.0	0.0	0.0	0.0	0.4

Appendix

Table 5: Percentage of runs satisfying the trapped-run criterion for EL-F at

T=10{,}000

, over

1{,}024

independent runs. A run is classified as trapped if the optimal arm is selected fewer than

T/2=5{,}000

times.

Explore similar work

The Greedy Advantage in Finite-Horizon Bandits
Jul 31, 2026Kai Zhou, Michael Lingzhi Li, Kai WangMulti-Armed Bandits
Tsinghua University · Harvard Business School
On the Benefits of Free Exploration for Regret Minimization in Multi-Armed Bandits
May 25, 2026Yunlong Hou, Zixin Zhong, Vincent Y. F. TanMulti-Armed Bandits Regret Minimization
Department of Mathematics, National University of Singapore · Data Science and Analytics Thrust, Hong Kong University of Science and Technology (Guangzhou) · Department of Electrical and Computer Engineering, National University of Singapore
Regret Analysis of Retry-Based Bandits
May 20, 2026Bingkui Tong, Junpei Komiyama, Soichiro Nishimori +1Multi-Armed Bandits Regret Minimization
Mohamed bin Zayed University of Artificial Intelligence · RIKEN AIP · The University of Tokyo

Jul 31, 2026J/K move · Enter open · S save

The Greedy Advantage in Finite-Horizon Bandits

Kai Zhou, Michael Lingzhi Li, Kai Wang

Tsinghua University · Harvard Business School

Multi-Armed Bandits

Open paper AskPDF arXiv

Organizations increasingly rely on sequential experimentation to improve decision-making. While the multi-armed bandit literature has developed algorithms with strong asymptotic regret guarantees, many practical applications operate over finite and externally imposed horizons. Motivated by the finite-horizon setting, we develop a class of regularized greedy algorithms for multi-armed Bernoulli bandits. We derive the first finite-horizon regret envelopes for regularized greedy bandits, showing that finite-horizon regret decomposes into transient exploration costs and a suboptimal convergence term that decays exponentially with the regularization strength. This characterization yields principled calibration rules for the regularization parameters and, as a limiting case, sharper regret guarantees for the classical greedy policy. Across extensive numerical experiments, calibrated regularized greedy policies consistently match or outperform state-of-the-art algorithms. These results suggest that regularized greedy policies can provide an effective approach for finite-horizon bandit problems.

Abstract

Explore similar work

The Greedy Advantage in Finite-Horizon Bandits

On the Benefits of Free Exploration for Regret Minimization in Multi-Armed Bandits

Regret Analysis of Retry-Based Bandits