Tree-Guided Identify-Then-Exploit: A Unified Framework of Best Arm Identification and Regret Minimization for Dueling Bandits
Authors: Pu Wang, Yao-Xiang Ding
Organizations: State Key Lab of CAD&CG, Zhejiang University
Abstract
We study N-armed stochastic dueling bandits under the Condorcet-winner assumption, where three widely adopted objectives are considered: best-arm identification (BAI), weak regret, and strong regret. We propose Tree-Guided Identify-Then-Exploit (TG-ITE), the first unified framework to tackle all these objectives to our knowledge. Without requiring stronger assumptions, we propose a shared tree-guided identification approach to find a high-confidence incumbent within O(N) comparisons. We further propose varied exploitation strategies to utilize this warm-start stage to optimize the specific objectives at hand. This methodology enables our approach to (1) achieve O(N) sample complexity in BAI without commonly adopted stronger assumptions; (2) build the first winner-stays-style algorithm to achieve O(N) weak regret; (3) enjoy the same O(NlogT) guarantee as specialized strong-regret approaches; (4) realize the joint optimization of BAI and weak regret with O(N) guarantees for both, eliminating the sub-optimal gap of O(logN) in the existing approach. Our results provide evidence that the trade-off between BAI and regret minimization is relatively benign in dueling bandits.
We study bandit best-arm identification with arbitrary and potentially adversarial rewards. A simple random uniform learner obtains the optimal rate of error in the adversarial scenario. However, this type of strategy is suboptimal when the rewards are sampled stochastically. Therefore, we ask: Can we design a learner that performs optimally in both the stochastic and adversarial problems while not being aware of the nature of the rewards? First, we show that designing such a learner is impossible in general. In particular, to be robust to adversarial rewards, we can only guarantee optimal rates of error on a subset of the stochastic problems. We give a lower bound that characterizes the optimal rate in stochastic problems if the strategy is constrained to be robust to adversarial rewards. Finally, we design a simple parameter-free algorithm and show that its probability of error matches (up to log factors) the lower bound in stochastic problems, and it is also robust to adversarial ones.
Yasin Abbasi-Yadkori, Peter L. Bartlett, Victor Gabillon +2
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
We study the problem of identifying the dominant arm in multi-armed bandits, where the objective is to find the action with the highest probability of exceeding the realized rewards of all other actions. Conventional mean-based and pairwise comparison-based algorithms often fail to identify the arm with the highest realized reward. To address this challenge, we introduce a novel dominant arm criterion and an efficient estimator with theoretical guarantees. Our approach relies on two key technical innovations: (i) a dominance score criterion that an arm beats the locally dominant over the partitioned reward space and (ii) a joint mixing and recycling mechanism coupled with a doubly robust estimator that guarantees simultaneous convergence of the empirical distribution functions for all arms. These key innovations pave a way to efficient computation of global arm dominance. Our proposed elimination algorithm identifies the best dominant arm with nearly optimal rate of sample complexity. Numerical experiments demonstrate that our algorithm consistently achieves exact recovery of the true dominant arm, outperforming existing baselines.