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

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

cs.LGMay 25, 2026

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

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

Organizations: 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

Abstract

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.

Explore similar work

Jul 31, 2026stat.ML

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

Optimal Bandit Algorithms Linear Regret Exponential Horizon Dependence Bandits

Ask PDF

May 1, 2026cs.LG

Trading off rewards and errors in multi-armed bandits

In multi-armed bandits, the most-explored arms are the most informative, while reward maximization typically pulls only the best arm. We study the tradeoff between identifying arm means accurately and accumulating reward, and present an algorithm with regret guarantees that interpolates between the two objectives. We provide both upper and lower bounds and validate empirically.

Akram Erraqabi, Alessandro Lazaric, Michal Valko +2

Multi-Armed Bandits Regret Trade-Off Errors

Ask PDF

May 19, 2026cs.LG

Active Context Selection Improves Simple Regret in Contextual Bandits

We study the contextual multi-armed bandit problem with a finite context space (a.k.a. subpopulations), where the learner recommends a best action for each context and is evaluated by context-weighted simple regret. Our guarantees are worst-case over the reward distributions, while remaining instance-dependent with respect to the context distribution vector

p

. Akin to experimental design problems where the population of interest is fixed but the sampled subpopulation can be controlled, we allow the learner to actively choose which context to sample from. For a known

p

, we characterize tight regret rates: passive sampling where contexts are randomly revealed achieves regret of order

\sqrt{n/T \, \lVert p \rVert_{1/2}}

, whereas active sampling with allocation

q_j \propto p_j^{2/3}

achieves the tight rate

\sqrt{n/T} \, \lVert p \rVert_{2/3}

. The resulting improvement can be as large as

Θ(k^{1/4})

, where

k

is the number of contexts. We further extend the analysis to budgeted active sampling, characterize the corresponding tight rate, and identify when a limited active budget suffices to recover the fully active rate. When

p

is unknown, we propose the Explore-Explore-Then-Commit (EETC) algorithm, which optimally balances estimating the context distribution and the time to switch to active allocation, such that for large horizons, it matches the known-

p

active rate up to constants. Experiments on synthetic and real-world data support our theoretical findings.

Mohammad Shahverdikondori, Jalal Etesami, Negar Kiyavash

Optimal Bandit Algorithms Linear Regret Adaptive Sampling

Ask PDF