MCTS 通常被认为是解决具有大分支因素的问题的好选择......但这种情绪的背景是它最初流行于玩围棋游戏，作为旧游戏玩法的替代品，例如α-β修剪。围棋的分支因子更像是 250-300，这通常被视为棋盘游戏的一个大分支因子。与您的分支因子相比，它不再是一个令人印象深刻的分支因子$6,000,000$...

当您在每一步都有 600 万个选择时，我认为 MCTS 不能开箱即用。如果你有一个非常有效的 MDP 实现（例如，如果你可以模拟每秒数百万次的推出），并且如果你有大量的“思考时间”（可能以小时或天）可用。

为了有机会在如此庞大的分支因子上做得更好，您确实需要跨动作进行泛化。你的 600 万个动作真的都是完全不同的动作吗？还是它们中的许多以某种方式相互关联？如果您收集了一些经验（MCTS 中的模拟，或者只是使用强化学习方法的轨迹），您能否将结果推广到您尚未收集经验的其他行动？

如果有某种方法可以将不同的操作视为“相似”（在给定状态下），您可以使用单个观察来一次更新多个不同操作的统计信息。最明显的方法是您可以为动作（或状态-动作对）定义有意义的特征。标准强化学习方法（使用函数逼近，可能是线性的，也可能是深度神经网络）然后可以相对“轻松”地以有意义的方式泛化许多动作。它们还可以以各种方式与 MCTS 结合（参见例如 AlphaGo Zero / Alpha Zero）。

尽管如此，600 万的分支因子仍然很大......但是跨动作的泛化可能是你最好的选择（这可能在 MCTS 内部完成，但确实需要在标准之上进行大量的花里胡哨方法）。

问题是在这些条件下 MCTS 是否是一种合适的方法。

• 行动$a_t \in A_t$

• 状态$s_t \in S_t$

• $[a_t, s_t] \Rightarrow s_{t+1}$

• $t_i \land i \in [1, 40]$

• $A(t) \in \text{set} \, A \; \land \; \text{size} (A) = 6 x 10^6$

• $S(t) \in \text{set} \, S \; \land \; \text{size} (S) = 1 x 10^8$

• 转移函数是随机的

MCTS 专注于最有前途的子树，因此是不对称的，非常适合某些具有高分支因子的系统，但除非利用某些对称性，否则集合大小可能会令人望而却步。

原始的 MCTS 算法不会快速收敛。这就是为什么经常使用 alpha-beta 剪枝和其他关注搜索空间最小化的搜索策略的原因，但它们在分支广度方面也有局限性。修剪启发式方法可以帮助减少组合爆炸，但可能会导致错过最有利的操作选项。

MCTS 的一些变体，例如以下文章中的变体，以及过去仅从游戏规则中学习围棋的 AlphaZero，在搜索速度方面表现出卓越的表现，但在没有并行性形式的情况下，可能达不到这种情况所需的程度计算集群或重要的硬件加速。

MCTS 的一个优秀特性是，可以在不耗尽所有子树评估的情况下选择早期发现的非常有希望的动作，但同样，这可能还不够。

一个可能具有约束性的考虑因素是是否会维护 Marcov 财产，如何维护以及是否应该维护。另一个考虑因素是系统是否涉及反对的智能参与者。所有采样或修剪搜索策略都存在无法可靠识别子树中单个分支的风险，这很容易导致不可逆转（或难以逆转）的损失。

这些是一些优秀的论文，讨论了这些考虑因素，并以研究结果的形式提供了高水平的经验。讨论近似求解器的文章涵盖了具有高分支的树搜索的计算挑战，这是一个高研究强度的领域。

• 动态环境中不确定性规划的在线 POMDP 求解器，H Kurniawati，V Yadav，2016

• 具有连续动作空间的 pomdps 的在线和近似求解器，KM Seiler，H Kurniawati，2015

• 后见之明只有 50/50：基于 MDP 的近似 POMDP 求解器不适合多分辨率信息收集，S Arora，S Choudhury，S Scherer，2018

• α-min：有限水平 POMDP 的紧凑近似求解器，Y Dujardin，T Dietterich，I Chades，2015

• 强化学习作为道德决策框架，D Abel，J MacGlashan，ML Littman，2016

• 关于迭代热带计算的复杂性及其在马尔可夫决策过程中的应用，N Balaji, S Kiefer, P Novotný, GA Pérez, 2018

• 在马尔可夫决策过程中优化受限策略类，E Banijamali，Y Abbasi-Yadkori，2018

• 用于可扩展多智能体决策的概率推理技术，A Kumar，S Zilberstein，M Toussaint，2015