A Finite-Sample Analysis of Payoff-Based Independent Learning in Zero-Sum Stochastic Games
A Finite-Sample Analysis of Payoff-Based Independent Learning in Zero-Sum Stochastic Games
复制标题
DOI：
10.48550/arxiv.2303.03100
复制
发表时间：
2023-03
期刊：
影响因子：
--
通讯作者：
Zaiwei Chen;K. Zhang;Eric V. Mazumdar;A. Ozdaglar;A. Wierman
中科院分区：
文献类型：
--
作者：
Zaiwei Chen;K. Zhang;Eric V. Mazumdar;A. Ozdaglar;A. Wierman
本文研究了二人零和随机博弈，提出了一种称为双平滑最佳响应动力学的独立学习动力学形式，它将最佳响应动力学的离散和双平滑变体集成到时间差（TD）学习和极小最大值迭代中。由此产生的动态是基于收益的、趋同的、理性的和玩家之间对称的。我们的主要结果提供了有限样本保证。特别是，我们证明了基于收益的独立学习动态的第一个已知的$\tilde{\mathcal{O}}(1/\epsilon^2)$样本复杂性界限，直到平滑偏差。在随机博弈只有一种状态的特殊情况下（即矩阵博弈），我们提供了更清晰的$\tilde{\mathcal{O}}(1/\epsilon)$样本复杂度。我们的分析使用了一种新的耦合李雅普诺夫漂移方法来捕捉多组耦合和随机迭代的演化，这可能是独立的兴趣。
We study two-player zero-sum stochastic games, and propose a form of independent learning dynamics called Doubly Smoothed Best-Response dynamics, which integrates a discrete and doubly smoothed variant of the best-response dynamics into temporal-difference (TD)-learning and minimax value iteration. The resulting dynamics are payoff-based, convergent, rational, and symmetric among players. Our main results provide finite-sample guarantees. In particular, we prove the first-known $\tilde{\mathcal{O}}(1/\epsilon^2)$ sample complexity bound for payoff-based independent learning dynamics, up to a smoothing bias. In the special case where the stochastic game has only one state (i.e., matrix games), we provide a sharper $\tilde{\mathcal{O}}(1/\epsilon)$ sample complexity. Our analysis uses a novel coupled Lyapunov drift approach to capture the evolution of multiple sets of coupled and stochastic iterates, which might be of independent interest.