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

1. Problem Formulation

This paper addresses a non-standard variant of the stochastic Multi-Armed Bandit (MAB) problem, termed Regret Minimization with Free Exploration (RM with FE). Unlike classical regret minimization (RM), where regret accumulates from the first time step, or pure exploration (e.g., Best Arm Identification), where the goal is solely to identify the optimal arm, this setting introduces a two-phase structure:

1. Free Exploration (FE) Phase: The agent is granted a budget of $T_{FE}$ time steps during which no regret is accumulated. The agent can interact with the environment to gather information without penalty. This phase is motivated by practical scenarios such as offline calibration, simulation, or beta testing where mistakes do not impact end-users or revenue.
2. Regret Accumulation (RA) Phase: Following the FE phase, the agent operates for $T - T_{FE}$ steps where standard cumulative regret is incurred. The objective is to minimize the cumulative regret in this phase by leveraging the information gathered during the FE phase.

The paper focuses on the regime where the free exploration budget scales logarithmically with the time horizon, i.e., $T_{FE} = O(\ln T)$ but $T_{FE} = \omega(1)$. This regime is identified as non-trivial: if $T_{FE}$ is constant, it does not affect asymptotic regret; if $T_{FE}$ grows faster than $\ln T$, simple fixed-budget Best Arm Identification algorithms (like Sequential Halving) can achieve constant regret. The $O(\ln T)$ regime requires a more nuanced approach to balance information acquisition and regret minimization.

2. Methodology

2.1 Policy Class: $(\alpha, \beta)$-Probably Saving Policies

To quantify the effectiveness of an FE policy, the authors introduce a novel class of policies called $(\alpha, \beta)$-probably saving policies.

• Definition: A policy $\pi$ is $(\alpha, \beta)$-probably saving if, for any bandit instance, it saves at least an $\alpha$-fraction of the maximum possible regret (the "oracle saved regret") with probability at least $1 - O(T^{-\beta})$ as $T \to \infty$.
• Motivation: Standard definitions of "saving regret" based on expectation are insufficient because they allow for high-variance policies that might save regret on average but fail catastrophically on specific instances. The $(\alpha, \beta)$ definition ensures reliability with high probability.

2.2 The Proposed Algorithm: UFE-KLUCB-H

The authors propose a two-phase algorithm, UFE-KLUCB-H, which combines a specialized FE policy with a history-aware RA policy.

• Phase 1: Uniform sampling with Forced Elimination (UFE)

  • UFE operates in rounds. It maintains an active set of arms and a set of "bad" arms.
  • It performs uniform sampling among active arms to estimate means.
  • Crucially, it employs forced exploration on identified bad arms. Unlike standard elimination algorithms (e.g., Successive Elimination) that stop pulling suboptimal arms once they are identified, UFE continues to pull bad arms a specific number of times (calculated to approach $\frac{\ln T}{D_{KL}(\nu_i, \nu_1)}$).
  • Rationale: In the RM with FE setting, the goal is not just to identify the best arm but to ensure that suboptimal arms are sampled sufficiently during the FE phase so that they do not need to be sampled (and thus incur regret) during the RA phase. The forced exploration ensures that the empirical saved regret is maximized.

• Phase 2: KLUCB-H

  • This is a history-aware adaptation of the KL-UCB algorithm.
  • It initializes its statistics (pull counts and empirical means) using the data collected during the FE phase.
  • It then proceeds with standard KL-UCB index selection for the remaining horizon.
  • The algorithm is designed to be asymptotically optimal for Bernoulli bandits given any historical data, whether adaptively or non-adaptively collected.

3. Key Contributions and Results

3.1 Theoretical Upper Bounds

The paper derives instance-dependent upper bounds on the regret of UFE-KLUCB-H.

• The regret is shown to be strictly less than the standard Lai-Robbins lower bound for classical RM.
• Specifically, the regret is reduced by a term proportional to the "saved regret" achieved during the FE phase.
• For specific "two-valued" instances (where arms have only two distinct mean values), the authors derive explicit upper bounds showing that regret decreases as the FE budget parameter $\gamma$ increases. In regimes with sufficient budget, nearly all regret can be eliminated.

3.2 Theoretical Lower Bounds

The authors establish instance-dependent lower bounds for any $(\alpha, \beta)$-probably saving policy.

• Novel Perturbation Arguments: Unlike standard lower bound proofs that perturb a single arm's mean, this work requires perturbing multiple arms simultaneously to construct meaningful alternative instances. This is because changing a single arm's mean might not significantly alter the "saved regret" metric in the FE setting.
• Phase Transitions: The lower bounds reveal sharp phase transitions in the accumulated regret depending on the size of $T_{FE}$.
  • If $T_{FE}$ is too small, no $(\alpha, \beta)$-probably saving policy exists.
  • In moderate regimes, the saved regret scales linearly with the budget.
  • In large regimes, the regret can be reduced to negligible levels.
• Near-Optimality: By comparing the upper bounds of UFE-KLUCB-H with the derived lower bounds, the authors demonstrate that the algorithm is nearly asymptotically optimal for two-valued instances, with the gap between bounds being small (dependent on parameters $\beta$ and $\epsilon$).

3.3 Numerical Experiments

Simulations were conducted comparing UFE-KLUCB-H against several baselines:

• KL-UCB (w/o FE): Standard KL-UCB with effective horizon $T - T_{FE}$.
• KL-UCB (w/ FE): KL-UCB running from $t=1$ but with regret accumulation starting at $T_{FE}+1$.
• Uniform-KLUCB-H: Uses uniform sampling in the FE phase.
• Oracle-KLUCB-H: An oracle algorithm with access to true means.

Results:

• The FE phase consistently reduces regret compared to standard RM.
• Adaptivity is Key: UFE-KLUCB-H outperforms Uniform-KLUCB-H, particularly in instances where arm means are not uniform. This confirms that adaptive forced exploration is more efficient at utilizing the FE budget than simple uniform sampling.
• The algorithm demonstrates robustness across different distributions (Bernoulli and Gaussian) and varying numbers of arms.

4. Significance and Claims

The paper claims to advance the theoretical understanding of the exploration-exploitation trade-off by formalizing a setting that bridges classical regret minimization and pure exploration.

• Practical Relevance: The formulation captures real-world scenarios (robotics calibration, A/B testing) where a "safe" exploration budget exists before deployment.
• Theoretical Insight: The work identifies that in the $O(\ln T)$ regime, the optimal strategy is not merely to identify the best arm but to "pre-pay" for the exploration of suboptimal arms during the free phase to minimize future regret.
• Algorithmic Design: The introduction of forced exploration in the FE phase is highlighted as a critical design choice that distinguishes this approach from standard Best Arm Identification algorithms, which typically stop sampling suboptimal arms once they are identified.
• Optimality: The paper asserts that UFE-KLUCB-H is nearly optimal for the class of two-valued instances, providing a tight characterization of the benefits of free exploration.

The authors remain modest regarding extensions, noting that future work could explore non-parametric bandits, structured bandits (linear, Lipschitz), and scenarios with distribution shifts between the FE and RA phases.