Plan-MCTS: Plan Exploration for Action Exploitation in Web Navigation

研究问题

树搜索已经被证明能帮助 agent 处理长程任务，但直接把 MCTS 或 Beam Search 套到网页导航里，会遇到两个结构性问题：

• sparse valid paths：真实可行解只稀疏地埋在巨大原子动作空间里，绝大多数探索都浪费在死路上。
• noisy context：原子级执行历史非常冗长，充满坐标、滚动、点击等低层细节，导致状态感知被稀释。

因此，本文要解决的不是“有没有搜索”，而是“搜索究竟该在什么空间里发生”。

核心思路

Plan-MCTS 的答案是：把探索从 Action Space 挪到 Plan Space。

作者认为，网页任务真正值得搜索的，不是逐步点击本身，而是高层子计划。于是他们把搜索流程拆成两部分：

• 在高层语义计划空间里做探索；
• 再把计划落地为具体动作执行。

这相当于把“找路”和“走路”分开，让搜索面向策略结构，而不是面向低层噪声。

方法结构

1. Dense Plan Tree

Plan-MCTS 把树的节点和边从原子动作改成高效的子计划。论文称之为 Dense Plan Tree：

• 每条边代表一个高价值子计划；
• 稀疏的长动作链被压缩成更稠密的高层意图结构；
• 搜索不再被底层动作分支爆炸拖住。

作者强调，这样做的结果是：有限搜索预算能够集中在更可能成功的战略分支上。

2. Abstracted Semantic History

第二个设计是 Abstracted Semantic History。Plan-MCTS 不保留全部原子执行痕迹，而是用已经验证过的 milestone 和任务进展来组织历史。

这样做有两个直接收益：

• 当前状态更容易被模型准确感知；
• 搜索时不必反复被坐标、滚动等局部执行噪声干扰。

也就是说，Plan Space 解决的是搜索稀疏性，Semantic History 解决的是上下文污染问题。

3. Dual-Gating Reward

Plan-MCTS 不是只看一个候选计划“像不像好主意”，还会做双重验证。Dual-Gating Reward 同时检查：

• 物理上是否可执行；
• 策略上是否与任务目标一致。

作者用这个机制避免两类常见错误：

• 计划逻辑上听起来合理，但实际上在当前页面上执行不了；
• 动作能做，但与任务目标无关，属于空耗预算。

4. Structural Refinement

一旦子计划失败，Plan-MCTS 不满足于只写一段文本反思，而是直接在搜索树上做 Structural Refinement，对错误 subplan 做在策略层面的修补。

论文专门拿它和普通 Reflection 比较，指出 Structural Refinement 的优势在于：

• 它会改树结构，而不只是积累错误说明；
• 能更直接修正根本原因；
• 因而能用更少预算找到更优轨迹。

主要结果

1. WebArena 上达到 SOTA

论文结论明确：Plan-MCTS 在 WebArena 上达到 state-of-the-art，整体优于强基线，并同时提升任务效果和搜索效率。

2. Plan Space 明显优于 Action Space

在统一环境下比较后，作者发现：

• 无论 backbone 是 Qwen3-VL-32B 还是 GPT-5-mini，Plan Space 方法都稳定优于 Action Space 方法；
• Plan-MCTS 又优于普通的 Plan Search。

这说明真正有效的增益，不只是“用了搜索”，而是“把搜索搬到了更合适的表示空间”。

3. 搜索成本显著下降

论文在效率分析中给出一个很实用的结果：

• 与 Action-Space 对应方法相比，Plan Search 和 Plan-MCTS 分别减少约 40% 和 28% 的 action interactions；
• 同时轨迹长度更短、结构更简洁。

这意味着 Plan-MCTS 不只是更准，也更省预算。

4. Structural Refinement 优于普通文本反思

在 ablation 中，作者比较了 Structural Refinement 和只产出文本反馈的 Reflection。结果表明，Structural Refinement 可以在更低搜索预算下获得更高成功率和更优轨迹。

这支持了一个很重要的判断：如果错误发生在子计划结构层面，单纯文本反思并不够，需要直接修改策略结构本身。

与相关文档的对照理解

结合知识库中另外 3 篇相近文档，可以更清楚地定位 Plan-MCTS：

• ColorBrowserAgent 通过外部知识和渐进摘要提升网页长程稳定性；Plan-MCTS 则通过搜索空间重构和计划树修复提升探索效率，两者互补但切入点不同。
• ColorBench 讨论移动 GUI 长程任务中的规划、记忆和反思瓶颈；Plan-MCTS 在网页导航里给出了一条规划侧的明确技术路线。
• MobileUse 依赖分层反思和主动探索来稳定移动执行；Plan-MCTS 更偏显式 search-based planning，而不是执行时反思控制。

可复用启发

• 对长程交互任务，搜索空间的表示方式往往比搜索算法名称本身更重要。
• 如果原子动作空间过稀疏，先把搜索对象提升到语义计划层，通常比继续堆更大的 action-level search 更有效。
• 历史压缩不应只是做摘要，而应服务于“当前状态还能不能被准确感知”。
• 错误如果发生在 plan structure 层面，修复也应回到结构层，而不是只输出自然语言反馈。

局限与边界

• 本笔记主要依据 arXiv 摘要页和 HTML 正文整理，未逐项展开附录中所有表格数值和实现细节。
• Plan Space 的质量依赖高层计划生成能力，如果计划抽象本身失真，搜索收益会被削弱。
• 该方法更适合长程网页导航，不等于对所有 GUI 任务都直接成立。

结论

Plan-MCTS 的关键价值，在于把网页导航中的“搜索难”重新定义为“搜索空间选错了”。通过在高层计划空间中做 MCTS，并配合语义历史压缩、双重验证奖励和结构化修复，它把原本稀疏、噪声很重的原子动作搜索，变成了更可控、更高效的战略探索过程。

来源：[[Plan-MCTS_ Plan Exploration for Action Exploitation in Web Navigation]]