新算法同时实现稳定表现与高效攻击，适合对抗性环境。
Best of Both Worlds: Regret Minimization versus Minimax Play
- 设计新在线学习算法，兼顾固定策略与对比策略的最优表现
- 在零和博弈中，损失恒定在O(1)，可从对手失误中获益Ω(T)
- 首次实现双目标保障，适用于动态对抗场景
本文研究带反馈的在线学习算法是否存在能同时保证对给定比较策略的O(1)遗憾，以及对任意固定策略的 ilde{O}( \sqrt{T})遗憾（T为轮次数）。当比较策略支持所有动作时，我们首次给出了肯定答案。在零和博弈（包括正常形式与广义形式）且极小极大值为零的背景下，我们的结果表明：可将风险控制在O(1)损失内，同时从可被利用的对手中获得Ω(T)收益，从而结合了无遗憾算法与极小极大策略的优势。
原文摘要 · Abstract (English)
In this paper, we investigate the existence of online learning algorithms with bandit feedback that simultaneously guarantee $O(1)$ regret compared to a given comparator strategy, and $\tilde{O}(\sqrt{T})$ regret compared to any fixed strategy, where $T$ is the number of rounds. We provide the first affirmative answer to this question whenever the comparator strategy supports every action. In the context of zero-sum games with min-max value zero, both in normal- and extensive form, we show that our results allow us to guarantee to risk at most $O(1)$ loss while being able to gain $Ω(T)$ from exploitable opponents, thereby combining the benefits of both no-regret algorithms and minimax play.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。