随机博弈的高效 Q 学习
我们提出了一种两时间尺度 Q 学习算法,采用函数逼近,以找到两个玩家之间公平、收敛、理性且对称的纳什均衡。我们的方法在线性函数逼近的特殊情况下,建立了无限采样边界,从而对这类随机博弈中收敛到纳什均衡所需的样本量提供了多项式的上界。
Dec, 2023
该论文提出了一种多智能体强化学习动态模型,分析了其在无限期贴现马尔可夫潜在博弈中的收敛性质。论文在独立和分散的环境下进行,重点研究了多智能体可以通过简单的学习动态方法在最小信息环境下达到马尔可夫潜在博弈的稳定纳什均衡。
May, 2022
本论文研究了探索 - 利用困境下的平滑 Q 学习动态,并提出了一个探索速率的充分条件,使得该方法在任何游戏中都能收敛到唯一的均衡,这一结果适用于权重势博弈和权重零和多矩阵游戏。论文还比较了 Q 学习动态和实现均衡所能达到的社会福利,提供了一种充分条件,即使动态不收敛,Q 学习动态仍能超过均衡。
Jan, 2023
研究了强化学习在具有领导者 - 追随者结构的情境马尔可夫博弈中学习 Quantal Stackelberg Equilibrium 的问题,提出了基于函数逼近的在线和离线问题的高效算法,利用最大似然估计来学习追随者的量化响应模型,并结合模型自由或基于模型的强化学习解决领导者的决策问题,同时利用不确定性来实现对乐观和悲观算法的估计,并在线性和短视场景下具备计算效率。
Jul, 2023
该研究提出了一种新的无偏置、无重要性采样的两步离策略 Q 学习算法,并通过适当的假设证明,该算法的迭代是有界的,并且几乎肯定收敛于最优 Q 值。研究还探讨了两步 Q 学习的平滑版本的收敛性分析,即通过用对数 - 和 - 指数函数代替最大函数。该算法具有鲁棒性和易于实现性,并在基准问题上进行了实验验证,如轮盘问题、最大化偏置问题和随机生成的马尔可夫决策过程,并将其与现有文献中的方法进行了比较。数值实验证明了两步 Q 学习及其平滑变体的卓越性能。
Jul, 2024
该论文介绍了 Q-learning 在强化学习工具中的重要性,提供了随机逼近和 Q-learning 的教程,并介绍了确保算法稳定性和加速收敛的新方法。其中两个新的贡献是解决了 Q-learning 中线性函数逼近的稳定性问题,以及设计了一种近似牛顿 - 拉普森流动的算法。
Jul, 2023
提出在给定特征空间中嵌入转移函数的二人零和随机博弈中,通过采样逼近纳什均衡策略的二人 Q-learning 算法,已证明可使用与特征数线性相关的样本大小找到 ε 最优策略;进一步改进算法的样本效率,采用方差约减、单调性保持和双侧策略逼近等技术来加速算法,证明了该算法最多只需要使用 O~(K/(ε^2 (1-γ)^4)) 个样本即可以高概率找到 ε 最优策略,其中 K 是特征数,γ 是折扣系数;算法的样本、时间和空间复杂度与游戏的原始维度无关。
Jun, 2019
通过使用策略近似来减少学习零和随机博弈的纳什均衡的计算成本,我们提出了一种新的 Q-learning 类型算法,该算法使用一系列经过熵正则化的软策略来近似 Q 函数更新期间的纳什策略。我们证明, 在某些条件下,通过更新正则化的 Q 函数,该算法收敛于纳什平衡,并演示了该算法快速适应新环境的能力。提供一种动态超参数调度方案来进一步加快收敛速度。 应用于多个随机游戏的实证结果验证了所提出的算法收敛于纳什平衡,同时展现了比现有算法更快的加速效果。
Sep, 2020
本文介绍了一种可证明有效的基于线性函数逼近的 $Q$-learning 算法,提出了 DSEC oracle 概念,该算法使用多项式数量的轨迹返回近似最优策略,并可用于设计和分析具有一般函数逼近的强化学习算法。
Jun, 2019