提出高效算法，降低博弈中策略切换的后悔值。
Tracking the Best Strategy in an Extensive-Form Game
- 设计基于参数ρ的在线学习算法，动态调整策略切换频率。
- 实现近似最优的切换后悔上界：(1/ρ + ρK)√(HAT)。
- 每轮计算仅需O(HB)时间，适合大规模博弈场景。
我们研究了在广义形式博弈中的无限形式强化学习问题，其中学习者每轮与一个迟钝对手进行博弈。关注的是切换后悔（switching regret），即学习者实际表现与任何固定策略切换序列相比的期望差距。所提算法引入参数ρ，可达到切换后悔上界为˜O((1/ρ + ρK)√(H A T))，其中K为比较序列的切换次数，H为单次对局中学习者最多可遍历的信息集数量，A为学习者可能采取的动作数。该算法极为高效，每轮只需O(H B)时间复杂度，其中B为任意信息集下学习者可用动作的最大数量。
原文摘要 · Abstract (English)
We consider the extensive-form bandit problem where on each trial the learner plays an extensive-form game against an oblivious adversary. We focus on the notion of switching regret, which measures the expected performance of the learner against that of any switching sequence of mixed strategies in retrospect. Our algorithm takes a parameter $ρ>0$ and achieves a switching regret of $\tilde{\mathcal{O}}((1/ρ+ρK)\sqrt{H A T})$ where $K$ is the number of switches in the comparator sequence, $H$ is the maximum number of the learner's information sets that can be traversed during a play of the game and $A$ is the number of actions that the learner can possibly take. Our algorithm is extremely efficient, taking a per trial time of only $\mathcal{O}(H B)$ where $B$ is the maximum number of actions available to the learner at any of its information sets.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。