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

Jul 31, 2026

The Greedy Advantage in Finite-Horizon Bandits

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.

Kai Zhou, Michael Lingzhi Li, Kai Wang

Tsinghua University · Harvard Business School

Multi-Armed Bandits

Ask PDF

May 25, 2026

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

We study a stochastic multi-armed bandit problem where an agent is granted a free exploration budget before regret accumulates, a setting not captured by the classic regret minimization or pure exploration paradigms. The goal is to design an adaptive policy that strategically explores the bandit instance in the initial free exploration phase and minimizes the cumulative regret in the subsequent phase. We formalize this regret minimization with free exploration problem and identify an interesting regime where the free exploration budget scales logarithmically with the time horizon. To quantify the amount of regret saved with high probability as a result of the availability of the free exploration phase, we introduce a novel set of policies known as

(α,β)

-probably saving policies. We propose a two-phase, probably saving algorithm, UFE-KLUCB-H, which consists of a principled free exploration policy, UFE, and a history-aware regret minimization policy KLUCB-H. Instance-dependent upper bounds on UFE-KLUCB-H are derived, showing that UFE-KLUCB-H accumulates strictly less regret than policies that do not have access to a free exploration phase. Complementarily, we derive instance-dependent lower bounds based on novel multi-instance perturbation arguments tailored to the free-exploration setting, demonstrating the near-optimality of UFE-KLUCB-H for two-valued bandits. Our upper and lower bounds reveal sharp phase transitions in the accumulated regret depending on the amount of available free exploration. Simulations are conducted to demonstrate that forced exploration and adaptivity in the algorithm lead to greater regret savings.

Yunlong Hou, Zixin Zhong, Vincent Y. F. Tan

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

Multi-Armed Bandits Regret Minimization

Ask PDF

May 20, 2026

Regret Analysis of Retry-Based Bandits

We provide the first regret analysis of ReMax in stochastic multi-armed bandits. Originally introduced for reinforcement learning, ReMax is motivated by the role of exploration when multiple attempts are allowed, and is closely related to retry-based objectives such as pass@

k

and max@

k

, which value the best outcome across those attempts. Given a posterior over arm values, ReMax chooses a sampling distribution that maximizes the posterior expected maximum arm value over

M

virtual draws. For Gaussian rewards with

K

arms and any fixed integer

M\ge2

, we characterize optimal sampling distributions through an expected-improvement balance condition and prove an

O(\sqrt{(M-1)KT\log T})

finite-time bound on expected regret. Our analysis separates a logarithmic contribution from rounds without optimal-arm underestimation and a recovery term that dominates the bound. For every fixed instance with pairwise distinct arm means, we further prove an asymptotic logarithmic regret upper bound whose coefficient is at most

M-1

times the optimal coefficient by Lai and Robbins. When

M=2

, this bound implies the asymptotic optimality of ReMax. Gaussian-bandit experiments show that ReMax performs competitively with Thompson sampling and KL-UCB. They also reveal a trade-off: larger

M

reduces regret incurred during optimal-arm underestimation, but this reduction does not necessarily translate into lower total regret. Controlled recovery experiments show that separating suboptimal means accelerates recovery, while severe underestimation of the optimal arm can lead to long delays before it is sampled again.

Bingkui Tong, Junpei Komiyama, Soichiro Nishimori +1

Mohamed bin Zayed University of Artificial Intelligence · RIKEN AIP · The University of Tokyo

Multi-Armed Bandits Regret Minimization

Ask PDF