研究如何在随机多臂赌博机中保留最优臂，提升流式算法效率。
On the Problem of Best Arm Retention
- 基于KL散度推导出最佳臂保留的理论下界。
- 证明了期望差距小于r时的样本复杂度紧界。
- 提出超越纯探索的算法，适合流式场景下的在线决策。
本文系统研究了最佳臂保留（Best Arm Retention, BAR）问题，该问题在随机多臂赌博机的流式算法中有重要应用。在BAR问题中，目标是从n个臂中经过若干轮试验后，保留包含最优臂在内的m个臂。我们首先在不同准则下研究纯探索的BAR问题，随后在流式算法进一步探索的背景下，研究带约束的最小化损失问题。我们重新审视了最佳臂识别（BAI）中$(\varepsilon,δ)$-PAC算法的下界，并将经典的KL散度方法推广至BAR问题，得到$(\varepsilon,δ)$-PAC算法的最优界。我们还研究了另一变种$ r $-BAR，要求被保留的最佳臂与最优保留臂之间的期望差距小于$ r $，并证明了该问题的紧样本复杂度。最后，我们探索了$ r $-BAR的损失最小化问题，提出了超越纯探索的算法，并给出了该设置下最优损失的猜想。
原文摘要 · Abstract (English)
This paper presents a comprehensive study on the problem of Best Arm Retention (BAR), which has recently found applications in streaming algorithms for multi-armed bandits. In the BAR problem, the goal is to retain $m$ arms with the best arm included from $n$ after some trials, in stochastic multi-armed bandit settings. We first investigate pure exploration for the BAR problem under different criteria, and then minimize the regret with specific constraints, in the context of further exploration in streaming algorithms. - We begin by revisiting the lower bound for the $(\varepsilon,δ)$-PAC algorithm for Best Arm Identification (BAI) and adapt the classical KL-divergence argument to derive optimal bounds for $(\varepsilon,δ)$-PAC algorithms for BAR. - We further study another variant of the problem, called $r$-BAR, which requires the expected gap between the best arm and the optimal arm retained is less than $r$. We prove tight sample complexity for the problem. - We explore the regret minimization problem for $r$-BAR and develop algorithm beyond pure exploration. We conclude with a conjecture on the optimal regret in this setting.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。