使用抽样计算近似纳什均衡和强稳最佳响应
本文介绍了 CFR$^+$ 算法,它通常在计算时间上比以前已知算法快一个数量级或更多,同时可能需要更少的内存。该算法可用于不完美信息博弈中,是近似纳什均衡解的最佳方法之一。
Jul, 2014
本文主要介绍在计算机游戏中使用的 Monte Carlo Tree Search 算法中的采样策略 —— naive sampling,结合 Combinatorial Multi-armed Bandits 问题进行分析和比较,并在实时策略游戏中进行了验证。实验结果表明,在分支因子增加的情况下,naive sampling 比其他采样策略更有效。
Oct, 2017
本文探讨在有限时间马尔可夫决策过程的框架下,基于树形搜索策略的蒙特卡罗树搜索 (MCTS)。提出了一种动态抽样树策略,有效地分配有限的计算预算,以最大化选择最佳根节点动作的正确性概率。实验结果表明,所提出的树策略比其他竞争方法更有效。
Apr, 2022
使用前向搜索稀疏采样算法(FSSS)可以实现接近 Bayes 最优行为,从而使用 Monte-Carlo 树搜索算法有效地处理状态空间极大或无限大的马尔可夫决策过程(MDPs)。
Feb, 2012
本文研究了 Markov 粗粒度关联均衡问题的计算复杂性及其在多智能体强化学习中的应用,发现当多智能体交互为回合制、折扣因子和粗略程度为常数时,计算近似的 Markov 粗粒度关联均衡策略属于 NP 难问题,但是提供了在多智能体中非稳定 Markov CCE 策略的学习解决方案。
Apr, 2022
本文提出了两种基于蒙特卡罗树搜索的算法,能够针对非线性效用函数计算风险意识和多目标环境下的回报策略,并考虑累计回报,同时,这两个算法在多目标强化学习中,预期回报的表现超越了现有的最优算法。
Nov, 2022
本文研究了去中心化多智能体强化学习问题中的不后悔算法,并探讨了自主学习能否在标准 Markov 博弈框架中实现无后悔学习。结果表明,无论是已知还是未知的博弈,该问题都无法以多项式时间实现无后悔学习,该文贡献了理论证明支持,提出了基于集聚方法的创新性应用,并发现了 SparseCCE 问题的下限,从而说明了近年来学者对于该问题的研究成果,并对博弈理论和强化学习算法研究方向提出了新的思考。
Mar, 2023
本文提出了第一个在 CFIR 基础上打破了迭代次数平方根的收敛速度的 CFR 变体,通过优化后的遗憾最小化器和新的稳定性概念,在 CFR 中引入了稳定可预测性,并将每个遗憾最小化器稳定性设置为所在决策树中的位置,实现了 $O (T^{-3/4})$ 的收敛速率。
Feb, 2019
本研究针对具有线性结构的两人零和有限马尔可夫博弈提出了一种基于乐观价值迭代的增强学习算法,该算法通过构建价值函数的上下置信区间,并用 Coarse Correlated Equilibrium 求解泛化和纳什均衡问题,实现了性能的总时间平方根复杂度的上限。
Feb, 2020
介绍一种名为本地无后悔学习(LONR)的算法,它使用类似于 Q 学习的更新规则,允许在没有输入状态或完美回忆的情况下进行学习,证明了其在 MDPs 和有限的扩展中的收敛性,并呈现实验结果,表明它在许多情况下实现了最后迭代的收敛,特别是 NoSDE 游戏这类的 Markov 游戏。
Oct, 2019