arXiv:2412.07120cs.GTcs.LG2024-12被引 5

提出自适应学习动态,应对玩家策略偏离时的博弈均衡求解问题。

Corrupted Learning Dynamics in Games

  • 设计新学习机制,自动适应玩家偏离程度
  • 零和博弈下外部后悔率受偏离累积量影响
  • 适用于策略或收益观测被污染的场景

学习在博弈中指多个玩家在共享环境中互动,各自试图最小化自身遗憾。当所有玩家遵循乐观跟随正则化领导者(OFTRL)时,可实现 $O(1/T)$ 的快速均衡收敛。然而该加速仅在所有玩家诚实遵循算法的条件下成立,现实可能不成立。为此,本文提出受污染学习动态,其收敛速率取决于各玩家偏离指定策略的程度。在双人零和博弈中,$x$-玩家的外部遗憾约为 $O("log (m_x m_y) + \\

原文摘要 · Abstract (English)

Learning in games refers to scenarios where multiple players interact in a shared environment, each aiming to minimize their regret. An equilibrium can be computed at a fast rate of $O(1/T)$ when all players follow the optimistic follow-the-regularized-leader (OFTRL). However, this acceleration is limited to the honest regime, in which all players adhere to a prescribed algorithm -- a situation that may not be realistic in practice. To address this issue, we present corrupted learning dynamics that adaptively find an equilibrium at a rate that depends on the extent to which each player deviates from the strategy suggested by the prescribed algorithm. First, in two-player zero-sum corrupted games, we provide learning dynamics for which the external regret of $x$-player (and similarly for $y$-player) is roughly bounded by $O(\log (m_x m_y) + \sqrt{\hat{C}_y} + \hat{C}_x)$, where $m_x$ and $m_y$ denote the number of actions of $x$- and $y$-players, respectively, and $\hat{C}_x$ and $\hat{C}_y$ represent their cumulative deviations. We then extend our approach to multi-player general-sum corrupted games, providing learning dynamics for which the swap regret of player $i$ is bounded by $O(\log T + \sqrt{\sum_{k} \hat{C}_k \log T} + \hat{C}_i)$ ignoring dependence on the number of players and actions, where $\hat{C}_i$ is the cumulative deviation of player $i$ from the prescribed algorithm. Our learning dynamics are agnostic to the levels of corruption. A key technical contribution is a new analysis that ensures the stability of a Markov chain under a new adaptive learning rate, thereby allowing us to achieve the desired bound in the corrupted regime while matching the best existing bound in the honest regime. Notably, our framework can be extended to address not only corruption in strategies but also corruption in the observed expected utilities, and we provide several matching lower bounds.

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。