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

• URL: http://arxiv.org/abs/2605.25789v1
• Date: Mon, 25 May 2026 12:36:43 GMT
• Title: On the Benefits of Free Exploration for Regret Minimization in Multi-Armed Bandits
• Abstract summary: We study a multi-armed bandit problem where an agent is granted a free exploration budget before regret accumulates.<n>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.<n>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.
• Score: 54.384522012368556
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Improved Bounds for Reward-Agnostic and Reward-Free Exploration [5.120675183010349]
  We study reward-free and reward-agnostic exploration in episodic finite-horizon Markov decision processes.<n> Reward-free exploration aims to enable $$-optimal policies for any reward revealed after exploration, while reward-agnostic exploration targets $$-optimality for rewards drawn from a small finite class.
  arXiv  Detail & Related papers  (2026-02-18T11:04:15Z)
• EUBRL: Epistemic Uncertainty Directed Bayesian Reinforcement Learning [22.84927928856004]
  Epistemic uncertainty reflects systematic uncertainty due to limited knowledge.<n>We propose a Bayesian reinforcement learning algorithm, $texttEUBRL$, which leverages guidance to achieve principled exploration.
  arXiv  Detail & Related papers  (2025-12-17T12:55:05Z)
• Catoni-Style Change Point Detection for Regret Minimization in Non-Stationary Heavy-Tailed Bandits [31.212504858546232]
  We tackle the heavy-tailed piecewise-stationary bandit problem.<n>We provide a novel Catoni-style change-point detection strategy tailored for heavy-tailed distributions.<n>We introduce Robust-CPD-UCB, which combines this change-point detection strategy with optimistic algorithms for bandits.
  arXiv  Detail & Related papers  (2025-05-26T14:40:47Z)
• Best Arm Identification with Minimal Regret [55.831935724659175]
  Best arm identification problem elegantly amalgamates regret minimization and BAI. Agent's goal is to identify the best arm with a prescribed confidence level. Double KL-UCB algorithm achieves optimality as the confidence level tends to zero.
  arXiv  Detail & Related papers  (2024-09-27T16:46:02Z)
• Safe Exploration Incurs Nearly No Additional Sample Complexity for Reward-free RL [43.672794342894946]
  Reward-free reinforcement learning (RF-RL) relies on random action-taking to explore the unknown environment without any reward feedback information. It remains unclear how such safe exploration requirement would affect the corresponding sample complexity in order to achieve the desired optimality of the obtained policy in planning. We propose a unified Safe reWard-frEe ExploraTion (SWEET) framework, and develop algorithms coined Tabular-SWEET and Low-rank-SWEET, respectively.
  arXiv  Detail & Related papers  (2022-06-28T15:00:45Z)
• Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning [52.76230802067506]
  A novel model-free algorithm is proposed to minimize regret in episodic reinforcement learning. The proposed algorithm employs an em early-settled reference update rule, with the aid of two Q-learning sequences. The design principle of our early-settled variance reduction method might be of independent interest to other RL settings.
  arXiv  Detail & Related papers  (2021-10-09T21:13:48Z)
• Shortest-Path Constrained Reinforcement Learning for Sparse Reward Tasks [59.419152768018506]
  We show that any optimal policy necessarily satisfies the k-SP constraint. We propose a novel cost function that penalizes the policy violating SP constraint, instead of completely excluding it. Our experiments on MiniGrid, DeepMind Lab, Atari, and Fetch show that the proposed method significantly improves proximal policy optimization (PPO)
  arXiv  Detail & Related papers  (2021-07-13T21:39:21Z)
• Temporal Difference Uncertainties as a Signal for Exploration [76.6341354269013]
  An effective approach to exploration in reinforcement learning is to rely on an agent's uncertainty over the optimal policy. In this paper, we highlight that value estimates are easily biased and temporally inconsistent. We propose a novel method for estimating uncertainty over the value function that relies on inducing a distribution over temporal difference errors.
  arXiv  Detail & Related papers  (2020-10-05T18:11:22Z)
• On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimization [55.937424268654645]
  We consider algorithm-independent lower bounds for the problem of black-box optimization of functions having a bounded norm. We provide a novel proof technique for deriving lower bounds on the regret, with benefits including simplicity, versatility, and an improved dependence on the error probability.
  arXiv  Detail & Related papers  (2020-08-20T03:48:14Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.