提出新算法，显著降低多人博弈中玩家的累计后悔值。
Faster Rates for No-Regret Learning in General Games via Cautious Optimism
- 结合乐观更新与自适应学习率，让玩家更谨慎地调整策略。
- 后悔值降至 O(n log²d log T)，对动作数 d 的依赖大幅降低。
- 适合研究多智能体博弈、在线学习的学者和工程师。
我们提出了首个无耦合学习算法，在多玩家一般和博弈中实现每玩家后悔值为 O(n log²d log T)，其中 n 为玩家数，d 为每玩家可用动作数，T 为博弈重复次数。相比已有方法，该算法在 d 上的依赖呈指数级改进（原为 O(n d log T)），且对迭代次数 T 的依赖从之前的 log⁴T 降至 log T。该算法通过将经典乐观乘法权重更新（OMWU）与自适应非单调学习率相结合，根据玩家后悔值是否过负来动态调节学习速度，使学习过程更谨慎。
原文摘要 · Abstract (English)
We establish the first uncoupled learning algorithm that attains $O(n \log^2 d \log T)$ per-player regret in multi-player general-sum games, where $n$ is the number of players, $d$ is the number of actions available to each player, and $T$ is the number of repetitions of the game. Our results exponentially improve the dependence on $d$ compared to the $O(n\, d \log T)$ regret attainable by Log-Regularized Lifted Optimistic FTRL [Far+22c], and also reduce the dependence on the number of iterations $T$ from $\log^4 T$ to $\log T$ compared to Optimistic Hedge, the previously well-studied algorithm with $O(n \log d \log^4 T)$ regret [DFG21]. Our algorithm is obtained by combining the classic Optimistic Multiplicative Weights Update (OMWU) with an adaptive, non-monotonic learning rate that paces the learning process of the players, making them more cautious when their regret becomes too negative.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。