Learning in games with continuous action sets and unknown payoff functions
Learning in games with continuous action sets and unknown payoff functions
复制标题
DOI：
10.1007/s10107-018-1254-8
复制
发表时间：
2016-08
影响因子：
2.7
通讯作者：
P. Mertikopoulos;Zhengyuan Zhou
中科院分区：
文献类型：
--
作者：
P. Mertikopoulos;Zhengyuan Zhou
本文研究了具有连续行动集的博弈中无悔学习的收敛性。具体来说，我们专注于通过“双平均”学习，这是一种广泛使用的无遗憾学习方案，玩家沿着他们的个人收益梯度沿着小步，然后将输出“镜像”回他们的行动集。在反馈方面，我们假设玩家只能估计他们的收益梯度到一个零均值误差与有界方差。为了研究诱导序列的收敛性，我们引入了变分稳定性的概念，并证明了稳定的平衡点以高概率局部吸引，而全局稳定的平衡点以概率1全局吸引。我们还讨论了有限游戏中的混合策略学习的一些应用，并提供了该方法的收敛速度的明确估计。
This paper examines the convergence of no-regret learning in games with continuous action sets. For concreteness, we focus on learning via “dual averaging”, a widely used class of no-regret learning schemes where players take small steps along their individual payoff gradients and then “mirror” the output back to their action sets. In terms of feedback, we assume that players can only estimate their payoff gradients up to a zero-mean error with bounded variance. To study the convergence of the induced sequence of play, we introduce the notion ofvariational stability, and we show that stable equilibria are locally attracting with high probability whereas globally stable equilibria are globally attracting with probability 1. We also discuss some applications to mixed-strategy learning in finite games, and we provide explicit estimates of the method’s convergence speed.