最佳臂识别的蒙特卡罗树搜索
在多臂老虎机游戏中,利用少量样本通过固定置信度水平下的置信区间,提出了一种最初的置信上界算法,该算法使用的样本数量与基于迭代对数定理的下限相比仅相差常数因子,同时使用了一种新的停止时间来避免在其他上置界型算法中观察到的臂联合的界限,从而进一步优化了算法,并通过模拟证明了算法的性能。
Dec, 2013
研究了多臂赌博机中的最佳臂辨识问题,提出了一个基于顺序淘汰算法的通用框架,并基于采样机制和每轮淘汰臂数量提出了性能评估指标,设计了一种按剩余臂数的非线性函数划分预算的算法,能够在纯探索场景下获得改进的理论保证和实验性能。
Sep, 2016
该论文研究了在固定置信度情况下,通过从多个嘈杂的微观可观测变量映射中获得价值信息来识别最佳行动的问题,并针对这个问题引入了一个抽象框架,提出了一种新的算法(LUCB-micro),同时分析了其下界和上界样本复杂性的结果。
Jun, 2017
本文主要介绍在计算机游戏中使用的Monte Carlo Tree Search算法中的采样策略 —— naive sampling,结合Combinatorial Multi-armed Bandits问题进行分析和比较,并在实时策略游戏中进行了验证。实验结果表明,在分支因子增加的情况下,naive sampling比其他采样策略更有效。
Oct, 2017
本文探讨在有限时间马尔可夫决策过程的框架下,基于树形搜索策略的蒙特卡罗树搜索(MCTS)。提出了一种动态抽样树策略,有效地分配有限的计算预算,以最大化选择最佳根节点动作的正确性概率。实验结果表明,所提出的树策略比其他竞争方法更有效。
Apr, 2022
本研究回顾了129篇关于神经蒙特卡罗树搜索方法在除游戏外的领域应用的同行评审文章,旨在系统评估此类方法在实践中的构造方式,以及它们在其他领域中是否成功应用。研究发现这类方法在各种领域中都有应用,采用了多种不同的学习策略和价值函数指导搜索树,并且采用了不同的训练方法。本文扫描了神经蒙特卡罗树搜索算法家族在实践问题中的现有景象,这是针对特定问题及要求设计此类算法的更加原则性的步骤的开端。
Mar, 2023
本文提出了一种新的游戏搜索算法,PN-MCTS,该算法将Monte-Carlo树搜索(MCTS)和证明数搜索(PNS)相结合。我们定义了三个领域,在这些领域中,在MCTS树中收集的证明和反证号所提供的额外知识可能会被使用。在不同的时间设置中测试了所有可能的组合,并与几个游戏进行了对抗。实验表明,PN-MCTS在5个游戏领域中(Gomoku除外)自信地优于MCTS,Lines of Action的胜率高达96.2%。
Mar, 2023
研究了多臂赌博机问题中学习者在选择臂时精度受限的变体,并且给出了期望停留时间的渐近下限并提出了一种修改后的算法用于处理非唯一最优配置,并且针对在简单的情况下访问不重叠臂的情况给出了非渐近下限和上限。
May, 2023
研究了多智能体路径规划中如何利用蒙特卡洛树搜索(Monte-Carlo Tree Search)解决问题,提出了一种适用于多智能体路径规划的改进MCTS变种,通过计算个体路径和奖励来指导搜索过程,实验证明该方法优于基线规划算法。
Jul, 2023
通过将组合优化注入蒙特卡罗树搜索,我们在抽象棋盘游戏中提出了一种新的AI方法,该方法在对强化学习算法的基线进行测试时的胜率达到96%,并在Board Game Arena平台上与人类玩家对抗时取得了良好的成绩。
Jun, 2024