与UCT和MCTS相关的几个问题

人工智能 强化学习 蒙特卡罗树搜索 规划
2021-11-07 20:14:17

Bandit Based Monte-Carlo Planning中,介绍了 UCT 作为规划算法的文章,在第 285 页(pdf 的 4)中有算法描述。

将这种 UCT(一种特定类型的 MCTS 算法)实现与游戏中通常使用的应用程序进行比较,有一个主要区别。在这里,奖励是针对每个状态计算的,而不是仅在模拟结束时进行评估。

我的问题是(它们都是相互关联的):

  • 这是唯一的大区别吗?或者换句话说,我可以对具有 4 个阶段的游戏执行与 MCTS 中相同的实现:选择、扩展、模拟和反向传播,其中模拟的结果是累积奖励而不是 0 和 1 之间的值?在这种情况下如何调整 UCT 选择?

  • 第 12 行中的 UpdateValue 函数究竟做了什么?在文本中它说它用于在给定深度调整状态-动作对值,这将用于选择吗?这是如何准确计算的?

  • 需要什么深度参数?它与UpdateValue有关吗?

最后,我想问一下您是否知道任何其他论文,其中明确实施 UCT 进行规划并获得多种奖励,而不仅仅是在模拟结束时。

1个回答

这是唯一的大区别吗?或者换句话说,我可以在一个简单的 MCTS 中执行相同的实现,包括 4 个阶段:选择、扩展、模拟和反向传播,其中模拟的结果是累积的奖励而不是 0 和 1 之间的值?在这种情况下如何调整 UCT 选择?

不,这不是唯一的区别。“原始 UCT”(如您链接的论文中所述)和“标准 UCT”(通常在游戏 AI 研究中实现)之间的重要区别在“关于蒙特卡洛树搜索和强化学习”的 2.4 小节中得到了很好的总结如果您有时间,我建议您阅读整篇论文或其中的大部分内容,但要总结一下主要区别:

  • 原始存储每次迭代的内存限制所允许的尽可能多的节点,标准每次迭代仅扩展一个节点。
  • 原始使用转置,标准实现不使用
  • 原始用途折扣系数γ, 标准没有(相当于拣货γ=1)
  • 原始考虑了观察到奖励的时间点,标准没有

最后一点是您的问题似乎主要涉及的问题。使用标准实现,但累积任何中间奖励并将其视为一个大的终端奖励的想法是不一样的实际上,考虑到观察到奖励的时间,就像在原始 UCT 中所做的那样,可以在树中间的节点中产生更准确的值估计(或至少更快地找到它们)。您的想法相当于从强化学习文献(例如 Sutton 和 Barto 的书)中学习 Monte-Carlo 备份,而原始 UCT 实现更类似于从 TD 学习(0) 备份。

请注意,在谈论 UCT 的“标准”实现时,这经常出现在关于两人零和游戏的论文中,其中所有中间奖励的值0,折扣被认为是不重要的(即γ=1),并且只有终端游戏状态有非零奖励。在这种特殊情况下,这两个想法确实变得等价了。


第 12 行中的 UpdateValue 函数究竟做了什么?在文本中它说它用于在给定深度调整状态-动作对值,这将用于选择吗?这是如何准确计算的?

这将以“标准”方式完成。访问计数增加,并且q可以加到所有的总和中q在搜索该状态-动作对期间观察到的值,因此可以将平均分数计算为q分数除以访问次数。这个平均分是X¯用于选择。


需要什么深度参数?它与UpdateValue有关吗?

我认为它通常不是真正需要的。在论文中,他们描述了它可以被认为具有深度截止。从纸:

“这可以是一个终结状态的范围,或者可以在某个深度(第 8 行)切割剧集。”