arXiv cs.AI· Tomer Massas, Vadim Indelman·· 3 天前AI 评分22
CAR-MCTS：首个具备随时确定性最优性保证的可扩展鲁棒 MCTS 规划器
Scalable Robust MCTS with Anytime Deterministic Optimality Guarantees
AI 导读
研究者提出 CAR-MCTS，一个由确定性边界引导的 MCTS 规划器，为鲁棒在线 MDP 规划提供首个随时确定性保证。该方法将计算限制在采样搜索树上，同时确定性地界定未采样轨迹的贡献，可剪枝可证明次优的分支，并在最优根动作被认证后终止。固定策略边界还提供了一种随时策略评估机制，无需枚举完整状态空间。
正文 · AI 翻译
摘要：MDP 规划器通常依赖可能与真实动态不一致的名义转移模型。鲁棒 MDP 规划通过一组可接受模型来考虑这种不确定性，但在有限的在线计算下这样做颇具挑战：搜索树随规划时域呈指数增长，且每次鲁棒回溯都需要额外的优化。现有的在线鲁棒方法在规模上仍然受限，且至多提供概率性保证。据我们所知，我们首次为鲁棒在线 MDP 规划引入了确定性随时保证。我们将计算限制在采样的搜索树上，同时确定性地界定未采样轨迹的贡献。对于任意固定策略，我们推导了在矩形和非矩形不确定性集下其投影鲁棒值与真实鲁棒值之间差距的下界和上界。在矩形不确定性下，我们通过鲁棒贝尔曼算子传播这些界，以界定最优鲁棒值。这些界可由当前采样树计算，在每个节点都成立，随着采样支撑集扩大而收紧，并在恢复完整支撑集时收敛到鲁棒值。我们开发了 CAR-MCTS，一种由界引导的 MCTS 规划器，它使用这些确定性界来引导探索、剪除可证明次优的分支，并在最优根动作得到认证后终止。固定策略界还产生了一种随时策略评估机制，可认证任意策略的鲁棒值，无论该策略如何获得。实验验证了确定性界、其在支撑集扩展下的收紧、大幅分支剪枝、根动作认证以及对最优鲁棒策略的收敛。据我们所知，这是首个可扩展的鲁棒 MCTS 框架，为在线规划和策略评估均提供随时确定性保证，且无需枚举完整状态空间。
| 评论： | 33 页，含附录 |
| 主题： | 人工智能（cs.AI） |
| 引用为： | arXiv:2610.15461 [cs.AI] |
| （或 arXiv:2610.15461v1 [cs.AI] 用于此版本） | |
| https://doi.org/10.48550/arXiv.2610.15461 arXiv 颁发的 DOI 经由 DataCite（待注册） |
提交历史
来自：Tomer Massas [查看电子邮件]
[v1]
2026 年 10 月 11 日星期日 09:01:25 UTC（1,387 KB）
来源：arXiv cs.AI · arxiv.org