在对抗性环境中提前识别未来表现最优的选项,突破了过去经验无效的困境。
Lookahead identification in adversarial bandits: accuracy and memory bounds
- 设计前瞻识别机制,预先选定未来时间段并锁定近优策略
- 实现误差ε=O(1/√log T),在Ω(√T)个预测窗口中可达成有效识别
- 揭示需至少K比特内存才能获得非平凡精度,稀疏条件下仅需对数级内存
我们研究多臂老虎机中的识别问题:每轮学习者选择一个臂并观测其奖励,目标是最终识别出在未来某一时刻表现最佳的臂。在对抗性环境中,过去的表现可能无法反映未来,这引发了一个根本问题:有意义的识别是否可能?本文提出“前瞻识别”任务,要求学习者事先选定一个未来预测窗口,并承诺选择一个在该窗口内平均奖励与最优值相差不超过ε的臂。我们的分析刻画了前瞻识别的可实现精度及其所需内存资源。从精度角度看,对任意时间跨度T,我们给出一个算法,可在Ω(√T)个预测窗口中实现ε = O(1/√log T)。这表明,尽管信息严重不足,识别仍可能实现。我们还证明了几乎匹配的下界:ε = Ω(1/log T)不可避免。随后我们研究内存的作用:首先证明任何实现非平凡精度的算法都需Ω(K)比特内存;在自然的局部稀疏条件下,我们证明相同精度可用仅poly-logarithmic内存实现。
原文摘要 · Abstract (English)
We study an identification problem in multi-armed bandits. In each round a learner selects one of $K$ arms and observes its reward, with the goal of eventually identifying an arm that will perform best at a {\it future} time. In adversarial environments, however, past performance may offer little information about the future, raising the question of whether meaningful identification is possible at all. In this work, we introduce \emph{lookahead identification}, a task in which the goal of the learner is to select a future prediction window and commit in advance to an arm whose average reward over that window is within $\varepsilon$ of optimal. Our analysis characterizes both the achievable accuracy of lookahead identification and the memory resources required to obtain it. From an accuracy standpoint, for any horizon $T$ we give an algorithm achieving $\varepsilon = O\bigl(1/\sqrt{\log T}\bigr)$ over $Ω(\sqrt{T})$ prediction windows. This demonstrates that, perhaps surprisingly, identification is possible in adversarial settings, despite significant lack of information. We also prove a near-matching lower bound showing that $\varepsilon = Ω\bigl(1/\log T\bigr)$ is unavoidable. We then turn to investigate the role of memory in our problem, first proving that any algorithm achieving nontrivial accuracy requires $Ω(K)$ bits of memory. Under a natural \emph{local sparsity} condition, we show that the same accuracy guarantees can be achieved using only poly-logarithmic memory.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。