arXiv 机器学习· Yuval Dagan, Nadav Eisen, Liad Erez, Tomer Koren·· 9 小时前AI 评分34
一般和博弈中的 Optimistic Hedge：基于时间逼近的理论极限与遗憾界
Optimistic Hedge in General-Sum Games: Fundamental Limits and Regret Bounds via Temporal Approximation
AI 导读
一项理论研究揭示了 Optimistic Hedge 算法在一般和博弈中的基本极限，证明其能否取得与时间跨度无关的多项式常数遗憾取决于玩家数量。在双人博弈中，该算法在合适学习率下可保证与时间跨度 $T$ 无关的 $O(n\log n)$ 遗憾界。但在玩家数 $m \ge 3$ 的博弈中，存在玩家遗憾达到 $2^{\Omega(mn)}$ 甚至随 $T$ 线性增长的情况。
来源：arXiv 机器学习 · arxiv.org