Best Arm Identification with Minimal Regret

Researchers have formalized a new multi-armed bandit problem that requires an agent to identify the best option with a prescribed confidence while simultaneously minimizing cumulative regret, a framework motivated by real-world applications demanding responsible experimentation [1]. The problem, introduced in a paper by Junwen Yang and colleagues, merges two classical objectives in sequential decision-making: regret minimization and best arm identification (BAI) [1]. In standard BAI, the goal is to find the optimal arm as efficiently as possible, a challenge that arises in adaptive clinical trials and hyperparameter optimization where sampling is costly [6]. The new variant adds a constraint: the agent must also keep the total regret low during the learning period [1]. The authors focus on single-parameter exponential families of distributions and derive an instance-dependent lower bound on the expected cumulative regret using information-theoretic techniques [1][4]. They also present an impossibility result that formalizes a tension between achieving minimal cumulative regret and the sample complexity required for fixed-confidence BAI [1][4]. This finding indicates that any asymptotically optimal algorithm for the problem will necessarily incur a higher-order sample complexity [4]. To address the dual objective, the team designed the Double KL-UCB algorithm [1]. The algorithm employs two distinct confidence bounds to guide arm selection in a randomized manner, and it achieves asymptotic optimality as the confidence level tends to zero [1][2]. The work builds on a broader research effort to unify exploration efficiency and reward maximization. A separate line of inquiry, termed Regret Optimal Best Arm Identification (ROBAI), previously introduced the EOCP algorithm, which commits to the optimal arm in O(log T) rounds with pre-determined stopping time and achieves asymptotic optimal regret [9]. That research also observed an "over-exploration" phenomenon in classic UCB algorithms, where stopping exploration earlier than UCB led to smaller regret, suggesting that excessive exploration can harm system performance [9]. The paper was first submitted to arXiv on 27 Sep 2024 as a 42 KB manuscript and was revised on 13 Jun 2026, with the updated version weighing 110 KB [1]. The authors state their findings provide a new perspective on the inherent connections between regret minimization and BAI [1].