Oct, 2017

实时策略游戏的组合多臂赌博机

PDF
TL;DR本文主要介绍在计算机游戏中使用的 Monte Carlo Tree Search 算法中的采样策略 —— naive sampling，结合 Combinatorial Multi-armed Bandits 问题进行分析和比较，并在实时策略游戏中进行了验证。实验结果表明，在分支因子增加的情况下，naive sampling 比其他采样策略更有效。
monte carlo tree searchcombinatorial multi-armed banditsnaive samplingreal-time strategy gamesbranching factor
发现论文，激发创造
  • 组合半臂老虎机的汤普森抽样的统计效率

    本文研究了采用半智能反馈的随机组合多臂赌博机问题。研究中提出了解决对于两种不同分布情况下是否存在效率最优、渐进遗憾最小算法的问题。通过分别采用 Beta 先验和高斯先验对 Combinatorial Thompson Sampling 策略进行了分析，进而找到了这两种分布情况下的算法解决方案，从而得出计算效率上优于 Efficient Sampling for Combinatorial Bandit 策略的结论。

    Jun, 2020

  • 组合半臂老虎机的汤普森抽样

    本文研究了 Thompson 采样方法在随机组合多臂赌博机框架中的应用，分析了多种算法的累积遗憾，并给出了上限界以及其他算法之间的比较结果。

    Mar, 2018

  • 多人赌博机问题再探

    本文探讨了多层次反馈的多人多臂老虎机算法，并在不需要感知信息的情况下引入了一种被称为自私的有希望的启发式方法以适应与物联网网络的应用。研究结果显示，引入这些方法可以提高算法的性能并保证其渐近最优，降低拥堵的可能性。

    Nov, 2017

  • 用于多臂赌博机的实值组合纯探索的汤普森抽样

    我们研究了多臂赌博机问题的实值组合纯探索（R-CPE-MAB）问题。我们引入了一种名为广义汤普森采样探索（GenTS-Explore）算法，它是第一个能够在动作集的大小指数级增长时仍然有效的算法。我们还引入了一个新颖的问题相关样本复杂性下界，并证明 GenTS-Explore 算法实现了最优的样本复杂性，仅存在一个与问题相关的常数因子。

    Aug, 2023

  • 一种高效的动态采样策略用于蒙特卡洛树搜索

    本文探讨在有限时间马尔可夫决策过程的框架下，基于树形搜索策略的蒙特卡罗树搜索 (MCTS)。提出了一种动态抽样树策略，有效地分配有限的计算预算，以最大化选择最佳根节点动作的正确性概率。实验结果表明，所提出的树策略比其他竞争方法更有效。

    Apr, 2022

  • 蒙特卡洛树搜索：近期修改和应用综述

    本文调查了 Monte Carlo Tree Search (MCTS) 在领域特定修改和混合方法方面的应用，这种方法依赖于智能树搜索并平衡探索和利用。

    Mar, 2021

  • 应用于逐步强化学习和其他领域的组合多元多臂赌博机

    引入一种新的组合多臂赌博梳理 (CMAB) 框架，具有多维和概率触发的臂 (CMAB-MT)，其中每个臂的结果是一个 d 维多维随机变量，反馈遵循普通臂触发过程。

    Jun, 2024

  • 基于遗传多臂赌博机的通过仿真进行离散优化的强化学习方法

    本文提出了一种新算法 GMAB，将强化学习领域的多臂赌博机和遗传算法中的随机搜索策略相结合，通过模拟来解决离散随机优化问题。实验结果表明，GMAB 在大量测试问题中取得了优越的性能。

    Feb, 2023

  • 低成本在线决策：一种组合多臂赌博机方法

    本文基于组合多臂赌博机，考虑了测试成本，提供了一种新的成本高效的在线决策框架，并通过后验抽样或 BayesUCB 进行探索。我们对该框架进行了严格的理论分析，并提供了多个实验结果，证明了它在实际问题中的适用性。

    Aug, 2023

  • 使用抽样计算近似纳什均衡和强稳最佳响应

    本文研究在复杂的部分可观测的随机博弈中，两种用于决策的蒙特卡洛采样搜索技术，MCTS 和 MCCFR。作者发现 MCTS 能较快地找到一种强策略而 MCRNR 学得更快。

    Jan, 2014