未知独立链随机博弈中的全在线去中心化学习

arXiv:2610.01181v1 公告类型：新增 摘要：我们研究具有相互独立的受控链且转移核未知的随机博弈，其中玩家只能观测各自的局部状态和实际获得的收益。我们在占用度量的对偶空间中，开发了一种全在线、去中心化且无需协调的镜像下降算法，用于逼近平稳纳什均衡（NE）策略。该算法在每个基本时间步仅使用一个转移/奖励样本，只依赖局部信息，既不要求覆盖联合状态空间，也不要求同步回合。在一致遍历性和有限覆盖假设下，我们证明，以高概率，时间平均的固定比较器遗憾以标准的 $O(T^{-1/2})$ 速率衰减，代价是对数因子和对博弈参数的多项式依赖。特别地，其复杂度取决于各个局部状态空间的覆盖时间，而非乘积状态空间的覆盖时间，从而避免了对玩家数量以及联合状态空间和动作空间规模的指数依赖。由此得到的有限时间遗憾界进一步给出了近似粗相关均衡保证；对于任意奖励函数而言，这一保证是自然的，因为在此设置下计算平稳 $\epsilon$-NE 是 PPAD-hard 的。在额外的全局变分稳定性条件下，我们证明同一个全在线算法的最后迭代点渐近收敛到平稳 $\epsilon$-NE。我们的结果为具有未知独立链的随机博弈提供了一个全在线且可扩展的学习框架。该算法也可被视为一种针对马尔可夫博弈的原始-对偶框架，利用了玩家受控转移链的独立性和局部结构。