Near-optimal no-regret algorithms for zero-sum games
Near-optimal no-regret algorithms for zero-sum games
复制标题
零和博弈的近乎最优无悔算法
DOI：
10.1016/j.geb.2014.01.003
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
A. Kim
中科院分区：
文献类型：
--
作者：
C. Daskalakis;Alan Deckelbaum;A. Kim
提出了一种新的无遗憾学习算法。当用于对抗对手时，我们的算法实现了平均遗憾，随着回合数的增加而增加。这种遗憾边界是最优的，但并不罕见，因为有许多学习算法具有这种遗憾保证。然而，当我们的算法被零和游戏的两个玩家使用时，他们的平均后悔尺度为，保证了接近线性的收敛速度。这代表了一个几乎是二次的改进收敛速度的游戏的价值已知要实现的任何无遗憾的学习算法，本质上是最优的，因为我们显示了一个下界。此外，我们的算法在游戏设置中产生的动态是强解耦的，因为每个玩家都不知道游戏的支付矩阵和其他玩家的策略数量，私人存储空间有限，并且不允许有趣的位运算，可以使问题变得微不足道;相反，他只观察他的策略相对于其他参与者的行动的表现，并且可以使用私有存储来记住过去玩过的策略和观察到的收益，或其累积信息。在这里，同样，我们的收敛速度是接近最佳的，并代表了一个几乎二次的改善，以前已知的最好的强解耦动态。
We propose a new no-regret learning algorithm. When used against an adversary, our algorithm achieves average regret that scales as with the numberTof rounds. This regret bound is optimal but not rare, as there are a multitude of learning algorithms with this regret guarantee. However, when our algorithm is used by both players of a zero-sum game, their average regret scales as , guaranteeing a near-linear rate of convergence to the value of the game. This represents an almost-quadratic improvement on the rate of convergence to the value of a game known to be achieved by any no-regret learning algorithm, and is essentially optimal as we show a lower bound of . Moreover, the dynamics produced by our algorithm in the game setting are strongly-uncoupled in that each player is oblivious to the payoff matrix of the game and the number of strategies of the other player, has limited private storage, and is not allowed funny bit arithmetic that can trivialize the problem; instead he only observes the performance of his strategies against the actions of the other player and can use private storage to remember past played strategies and observed payoffs, or cumulative information thereof. Here, too, our rate of convergence is nearly-optimal and represents an almost-quadratic improvement over the best previously known strongly-uncoupled dynamics.