Technical Summary: Best Arm Identification with Minimal Regret

Problem Formulation

This paper introduces and investigates the problem of Best Arm Identification (BAI) with Minimal Regret within the framework of stochastic multi-armed bandits. The setting involves a fixed-confidence scenario where an agent interacts with $K$ arms, each associated with a reward distribution from a known single-parameter exponential family. The agent must identify the unique optimal arm (the one with the highest mean) with a probability of at least $1-\delta$.

Unlike standard fixed-confidence BAI, which focuses solely on minimizing sample complexity (the number of pulls required to reach the confidence level), or standard regret minimization, which focuses on maximizing cumulative reward over a fixed horizon, this problem seeks to minimize the expected cumulative regret up to the stopping time $\tau_\delta$, subject to the constraint that the probability of error is at most $\delta$. The authors argue that in practical applications like clinical trials, the cost of exploration is not uniform; pulling a suboptimal arm incurs a "regret" proportional to its suboptimality gap. Therefore, a "responsible" experimental process should prioritize minimizing this cumulative regret while still guaranteeing a correct identification of the best arm.

Methodology and Algorithm Design

To address this problem, the authors propose the Double KL-UCB (DKL-UCB) algorithm. The algorithm is designed to balance the conflicting objectives of identifying the best arm (requiring sufficient exploration of suboptimal arms) and minimizing regret (requiring exploitation of the current best estimate).

Key components of DKL-UCB include:

1. Dual Confidence Bounds: The algorithm maintains two distinct Kullback-Leibler (KL) Upper Confidence Bounds (UCBs) for each arm $i$ at time $t$:
   • $f$-UCB ($U^f_i(t)$): Uses an exploration function $f(t) = 3 \log t$. This bound is designed to aggressively identify the current best arm (the "leader").
   • $g$-UCB ($U^g_i(t)$): Uses an exploration function $g(\delta, t) = \log(2Kt^2/\delta)$. This bound is tailored for the fixed-confidence requirement and helps in distinguishing the best arm from suboptimal ones.
2. Candidate Selection: At each step, the algorithm identifies two candidate arms:
   • $A^f_t$: The arm with the highest $f$-UCB.
   • $A^g_t$: The arm with the highest $g$-UCB, excluding $A^f_t$.
3. Randomized Sampling: The agent pulls either $A^f_t$ or $A^g_t$ based on a biased coin flip with probability $\beta(\delta) = 1 - \min\{1/\log\log(1/\delta), 1/2\}$. As $\delta \to 0$, $\beta(\delta) \to 1$, meaning the algorithm increasingly favors the arm identified by the $f$-UCB (the likely optimal arm) to minimize regret, while still occasionally pulling the $g$-UCB candidate to ensure the suboptimal arms are sufficiently explored to satisfy the confidence constraint.
4. Stopping Rule: The algorithm terminates when the lower confidence bound (LCB) of the $f$-UCB leader exceeds the $g$-UCB of the runner-up, ensuring the confidence level $\delta$ is met.

Theoretical Results

1. Information-Theoretic Lower Bounds

The authors establish a fundamental instance-dependent lower bound on the expected cumulative regret for any $\delta$-PAC (Probably Approximately Correct) algorithm.

• Regret Lower Bound: For any $\delta$-PAC algorithm, the expected cumulative regret satisfies:
  $$\liminf_{\delta \to 0} \frac{E_\mu[R(\tau_\delta)]}{\log(1/\delta)} \geq I^*(\mu)$$
  where $I^*(\mu) = \sum_{i=2}^K \frac{\Delta_i}{\text{kl}(\mu_i, \mu_1)}$. Here, $\Delta_i$ is the suboptimality gap and $\text{kl}$ is the KL divergence.
• Impossibility Result (Sample Complexity): The paper proves that achieving asymptotic optimality in regret necessitates a super-logarithmic sample complexity. Specifically, any asymptotically optimal algorithm must satisfy $E_\mu[\tau_\delta] = \omega(\log(1/\delta))$. This highlights a fundamental tension: to minimize regret, the agent must pull the optimal arm significantly more often than the minimal logarithmic number required just to distinguish it, leading to a total sample complexity strictly larger than $\Theta(\log(1/\delta))$.

2. Algorithm Performance

The authors prove that DKL-UCB achieves asymptotic optimality in cumulative regret:
$$\limsup_{\delta \to 0} \frac{E_\mu[R(\tau_\delta)]}{\log(1/\delta)} \leq I^*(\mu)$$
This matches the lower bound, confirming that DKL-UCB is optimal for the problem of BAI with minimal regret.

Regarding sample complexity, the algorithm achieves:
$$E_\mu[\tau_\delta] = \omega(\log(1/\delta)) \cap o\left(\log(1/\delta) \cdot (\log\log(1/\delta))^2\right)$$
This indicates that while the sample complexity is super-logarithmic (as proven necessary), it is nearly optimal, deviating from the lower bound only by a small multiplicative factor of $(\log\log(1/\delta))^2$.

Key Contributions and Significance

The paper makes several distinct contributions to the multi-armed bandit literature:

1. Problem Formulation: It formally defines and motivates the problem of BAI with minimal regret, bridging the gap between pure sample complexity minimization and pure regret minimization. It argues that in real-world settings where suboptimal actions have varying costs (regrets), minimizing cumulative regret during the exploration phase is a more ethically and practically sound objective.
2. Fundamental Limits: It establishes the first instance-dependent lower bound for the expected cumulative regret in fixed-confidence BAI. Crucially, it provides an impossibility result showing that minimizing regret in BAI inherently requires a higher-order sample complexity compared to standard BAI, elucidating the "tension" between the two objectives.
3. Algorithmic Innovation: The design of DKL-UCB, which utilizes two distinct confidence bounds and a specific randomized selection strategy, offers a novel approach to balancing exploration and exploitation in the BAI context.
4. Comparative Analysis: The paper demonstrates that algorithms optimized for minimal sample complexity (like Track-and-Stop) do not necessarily minimize regret, and vice versa. Through theoretical analysis and numerical experiments, it shows that DKL-UCB significantly outperforms standard BAI algorithms in terms of cumulative regret, while maintaining near-optimal sample complexity.

Experimental Validation

Numerical experiments on Bernoulli bandit instances confirm the theoretical findings. DKL-UCB consistently achieves lower cumulative regret compared to Track-and-Stop and Top-Two Thompson Sampling (TTTS), particularly as the confidence level $\delta$ becomes small. Conversely, as expected, Track-and-Stop and TTTS exhibit lower sample complexity, validating the theoretical trade-off identified in the paper.

Conclusion

The paper concludes that while regret minimization and sample complexity minimization in BAI are distinct goals with different optimal strategies, they are deeply interconnected. The proposed DKL-UCB algorithm successfully navigates this trade-off, achieving the fundamental lower bound for regret while incurring only a marginal penalty in sample complexity. The authors note that future work could explore non-asymptotic bounds and worst-case regret performance, as well as the precise fundamental limits of sample complexity under relaxed regret constraints.