设计一种无需知道奖励性质就能同时应对随机与对抗性场景的最优算法
Best of both worlds: Stochastic & adversarial best-arm identification
- 提出无需区分奖励类型的新算法，兼顾两种场景性能
- 证明对抗鲁棒性限制了随机场景下的最优误差率
- 算法在随机场景中误差率接近理论下界，且对对抗场景稳健
我们研究具有任意甚至可能对抗性奖励的多臂赌博机最优臂识别问题。单纯随机均匀选择策略在对抗场景下可达到最优错误率，但在随机奖励下表现不佳。因此我们提出：能否设计一种不依赖奖励性质、在两种场景下均表现最优的学习者？首先，我们证明这在一般情况下不可能实现。为保证对抗鲁棒性，仅能对部分随机问题保证最优误差率。我们给出了一个下界，刻画了在对抗鲁棒约束下随机问题的最优误差率。最后，我们设计了一个无参数的简单算法，其错误概率在随机场景中（至多对数因子内）逼近该下界，同时对对抗性奖励也保持鲁棒。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。