arXiv preprint ·
Scalable Robust MCTS with Anytime Deterministic Optimality Guarantees
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
MDP planners often rely on nominal transition models that may differ from the true dynamics. Robust MDP planning accounts for this uncertainty through a set of admissible models, but doing so with limited online computation is challenging: the search tree grows exponentially with the horizon and each robust backup requires an additional optimization. Existing online robust methods remain limited in scale and offer at most probabilistic guarantees. We introduce, to the best of our knowledge, the first deterministic anytime guarantees for robust online MDP planning. We restrict computation to the sampled search tree while deterministically bounding the contribution of unsampled trajectories. For any fixed policy, we derive lower and upper bounds on the gap between its projected and true robust values under rectangular and non-rectangular uncertainty sets. Under rectangular uncertainty, we propagate these bounds through the robust Bellman operator to bound the optimal robust value. These bounds are computable from the current sampled tree, hold at every node, tighten as the sampled support expands, and converge to the robust values as full support is recovered. We develop CAR-MCTS, a bound-guided MCTS planner that uses these deterministic bounds to guide exploration, prune provably suboptimal branches, and terminate once the optimal root action is certified. The fixed-policy bounds also yield an anytime policy-evaluation mechanism that certifies the robust value of any policy, independent of how it was obtained. Experiments verify the deterministic bounds, their tightening under support expansion, substantial branch pruning, root-action certification, and convergence to the optimal robust policy. To our knowledge, this is the first scalable robust MCTS framework with anytime deterministic guarantees for both online planning and policy evaluation, without enumerating the full state space.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Artificial Intelligence
MoMaTune: Model, Match, Then Tune Language Models for Numerical Records
Computational Reflective Equilibrium for Agentic AI: A Rawlsian Alignment Scaffold for Governance
Framework for an AI-Ready ARPES Community Database
When Does Compensating Inherited Quantization Error Help? Mean-Square Guarantees for Layer-Wise Quantization and Their Limits
ClinEdge: An Expert-Graded Benchmark of Real Patient Edge Cases Where Frontier Multimodal Models Fail
Get the few papers worth your time in Artificial Intelligence every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.