提出一种去中心化学习框架，可高效求解零和博弈中的纳什均衡。
Decentralized Best-Response-Based Learning in Two-Player Zero-Sum Stochastic Games: A Finite-Sample Analysis
- 基于对手策略的平滑最优响应更新自身策略，仅依赖自身收益观测。
- 在矩阵博弈中实现 ε-纳什分布的样本复杂度为 O(ε⁻¹)，ε-纳什均衡为 Õ(ε⁻⁸)。
- 适用于多智能体博弈、强化学习等场景，尤其适合分布式系统设计者。
本文对双人零和矩阵博弈与随机博弈中的去中心化学习进行了有限样本分析，聚焦于基于最优响应的学习算法。在矩阵博弈中，学习算法为收益驱动且对称：每名玩家仅根据自身收益观测，逐步逼近对手最新策略的平滑最优响应。对于随机博弈，基于该矩阵博弈基础，提出值迭代与平滑最优响应结合的算法（VI-SBR），融合诱导矩阵博弈中的平滑最优响应学习与去中心化的无模型最小最大值迭代近似。在两种设定下均建立有限样本保证：在矩阵博弈中，找到 ε-纳什分布的样本复杂度为 𝒪(ε⁻¹)，经显式探索后，ε-纳什均衡的样本复杂度为 Õ(ε⁻⁸)；在随机博弈中，增强探索的 VI-SBR 算法达到 Õ(ε⁻⁸) 的样本复杂度。技术上，提出耦合李雅普诺夫漂移框架，同时处理多个相互作用的随机迭代、由独立更新的价值函数生成的非零和辅助博弈，以及由时变策略引发的时变马尔可夫噪声。该工具可推广至分析具有耦合随机迭代与非平稳采样过程的学习算法。
原文摘要 · Abstract (English)
We present a finite-sample analysis of decentralized learning in two-player zero-sum matrix games and stochastic games, with a focus on best-response-based learning algorithms. In matrix games, the learning algorithm is payoff-based and symmetric: each player updates its policy using only its own payoff observations, incrementally moving toward an estimated smoothed best response to the opponent's latest policy. For stochastic games, we build on this matrix-game primitive to develop a learning algorithm called value iteration with smoothed best response (VI-SBR), which combines smoothed-best-response learning in induced matrix games with a decentralized, model-free approximation of minimax value iteration. We establish finite-sample guarantees in both settings. For matrix games, our results imply a sample complexity of $\mathcal{O}(ε^{-1})$ for finding an $ε$-Nash distribution and, with explicit exploration, $\tilde{\mathcal{O}}(ε^{-8})$ for finding an $ε$-Nash equilibrium. For stochastic games, we prove that the exploration-enhanced VI-SBR algorithm achieves a sample complexity of $\tilde{\mathcal{O}}(ε^{-8})$ for finding an $ε$-Nash equilibrium. Technically, our analysis develops a coupled Lyapunov-drift framework. This framework simultaneously handles stochastic iterative algorithms with multiple interacting stochastic iterates, the non-zero-sum auxiliary games generated by independently updated value functions, and the time-inhomogeneous Markovian noise induced by time-varying policies. The resulting tools may be useful more broadly for analyzing learning algorithms with coupled stochastic iterates and nonstationary sampling processes.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。