AlphaSnake: 非确定性 NP-hard 马尔科夫决策过程的策略迭代

Nov, 2022

AlphaSnake: 非确定性 NP-hard 马尔科夫决策过程的策略迭代

AlphaSnake: Policy Iteration on a Nondeterministic NP-hard Markov Decision Process

Kevin Du, Ian Gemp, Yi Wu, Yingying Wu

TL;DR本文利用蒙特卡罗树搜索（Monte Carlo Tree Search，MCTS）算法创造了自主智能体，学习玩 Snake 游戏，该游戏可被公式化为单人折扣马尔可夫决策过程，问题困难度大，但与先前工作相比，该算法是首个实现胜率超过 $0.5$ 的算法，可应用于解决复杂的 NP 困难问题。

Abstract

reinforcement learning has recently been used to approach well-known NP-hard combinatorial problems in graph theory. Among these problems, Hamiltonian cycle problems are exceptionally difficult to analyze, even w

reinforcement learning combinatorial problems hamiltonian cycles monte carlo tree search snake game

发现论文，激发创造

基于模型的自我对弈强化学习的严密分析

本文针对多智能体马尔科夫博弈提出了一种基于模型的算法 Nash-VI，在理论上证明其具有较高的样本利用率，并且在实验中证明了其优于现有的基于模型的方法和一些基于无模型的算法，输出单个 Markov 策略且易于存储和执行。

Oct, 2020

单智能体优化：通过蒙特卡罗树搜索进行策略迭代

本文提出了一种使用基于 Monte-Carlo Tree Search 和深度强化学习相结合的方法的搜索算法，通过 1）用于潜在无限奖励问题的新颖行动价值规范机制，2）定义虚拟损失函数实现有效搜索并行化，以及 3）由自我对弈逐代训练的策略网络引导搜索，来提高搜索算法的效果。我们在同类游戏 SameGame 上进行实验，结果表明我们的算法在多个游戏宽度上优于基准算法，并与公共状态搜索问题的最新算法竞争力相当。

May, 2020

Monte-Carlo 树搜索作为正则化策略优化

展示 AlphaZero 的 heuristics 可以近似于规则化策略优化问题的解，并通过提出一种利用此解的变量来实现，实验表明该算法在多个领域中可靠地优于原始算法。

Jul, 2020

零和马尔可夫博弈强化学习的一种新政策迭代算法

本文提出了一种对于零和马尔可夫游戏的学习策略 ——lookahead 策略，该策略使用简单的 naive policy iteration，在计划阶段实现高效的收敛，进一步阐述了在使用我们的算法进行计算规划时的时间复杂度和样本复杂度界限。

Mar, 2023

强化学习中基于反馈的树搜索

本文提出一种基于模型的强化学习技术，该技术将 Monte-Carlo 树搜索应用于无限期 Marov 决策过程的有限期版本，并使用值函数和策略函数的组合来规定有限期问题的终端条件或决策树的叶节点评估器。作者还提供了第一个基于树搜索的强化学习算法的样本复杂度边界，并证明由深度神经网络实现的技术能够创建一种竞争性人工智能代理。

May, 2018

学习即规划：通过蒙特卡罗树搜索实现接近 Bayes 最优强化学习

使用前向搜索稀疏采样算法（FSSS）可以实现接近 Bayes 最优行为，从而使用 Monte-Carlo 树搜索算法有效地处理状态空间极大或无限大的马尔可夫决策过程（MDPs）。

Feb, 2012

非平稳马尔可夫决策过程：基于模型的加强学习最坏情况方法，扩展版

本研究旨在解决在非恒定随机环境下的鲁棒零 - shot 规划问题，通过引入定义了特定类别的马尔可夫决策过程来进行计算建模，并提出了一种零 - shot 基于模型的风险敏感树搜索算法。

Apr, 2019

高速公路图在强化学习中的加速

为了提高 RL 算法的训练效率，本研究基于高速公路图的观察，提出了一种新颖的图结构，用于模拟状态转换，将 RL 训练在早期阶段显著加速，并在性能上优于其他无模型和带模型的 RL 算法。同时，基于高速公路图训练的深度神经网络代理具有更好的泛化性能和更低的存储成本。

May, 2024

使用蒙特卡罗树搜索的策略梯度算法用于非马尔可夫决策过程

本文介绍一种结合 Policy Gradient 和 Monte-Carlo Tree Search 的混合策略，旨在克服两种方法在应对非马尔可夫决策过程上的困难，有效提升算法的效率。

Jun, 2022

数据高效的疟疾控制强化学习

本文介绍了一种名为 Variance-Bonus Monte Carlo Tree Search (VB-MCTS) 的实用、数据效率高的策略学习方法，它是一种基于模型的强化学习方法，应用高斯过程回归估计转变，提出了一种方差奖励来衡量对世界的不确定性，进一步优化了计划，得到了更有效的探究，综合实验结果表明，在困难的疟疾控制任务上，VB-MCTS 优于现有技术。

May, 2021