acceptodds
Under review as a conference paper at ICLR 2027

Scalable Robust MCTS with Anytime Deterministic Optimality Guarantees

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 within the limited computation available online 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 obtain these guarantees by restricting 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 both 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 certificates 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 certificates 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 given policy, independent of how it was obtained. Experiments verify the deterministic certificates, 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.

Primary area:
applications to robotics, autonomy, planning
Keywords:
robust planning, Monte Carlo tree search, robust Markov decision processes, model uncertainty, anytime planning, deterministic optimality guarantees

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_6RbKOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper tackles online planning in robust MDPs, where every Bellman backup requires an inner worst-case optimization and therefore scales poorly with state-space size and horizon. The core idea is to restrict planning to the sampled search tree without renormalizing the transition probabilities, so that the unsampled probability mass is retained explicitly and can be used to bound the approximation error deterministically. From this the authors derive two-sided anytime certificates on the robust value of any fixed policy under general (non-rectangular) uncertainty, and, under rectangularity, propagate them through the robust Bellman operator to bound the optimal robust value. These certificates are embedded in CAR-MCTS, a planner that uses the upper bound to guide search, prunes provably suboptimal branches, and terminates early once the root action is certified optimal. Validation on Frozen Lake confirms certificate validity and monotone tightening, shows higher return than nominal UCT, RSS, and Robust Power UCT under model mismatch, and demonstrates per-decision cost that is nearly independent of state-space cardinality up to 10610^6 states.gN

Critical strengths

The combination of “restrict the support but do not renormalize” with the observation that the inner robust optimization commutes with the restriction map (Lemma 3) is simple, and I checked the sign-case algebra in Appendix A.1 and A.7–A.8 — the derivations go through, including the conservative direction of the independently-minimized δ\delta recursion used in (137)–(138) and (144).

Critical weaknesses

The bound is informative exactly where the method is not needed, and vacuous exactly where it is advertised — and the paper never confronts this. The certificate width is ≈(rmax⁡−rmin⁡)(H−t−mtπ)\approx (r_{\max}-r_{\min})(H-t-m^\pi_t), so it is tight only when the sampled tree captures nearly all trajectory probability mass over the remaining horizon.

Questions for authors

For the ∣S∣=106|\mathcal{S}|=10^6 setting of Fig. 3, what are the realized mtπm^\pi_t / δ\delta and the certificate width URDB−LRDB\mathcal{URDB}-\mathcal{LRDB} at the root? Could you add interval width and achieved return to Fig. 3? If the interval is vacuous there, please say so explicitly and state the regime in which the guarantees are meant to bite.

Reviewer_DKktOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper is situated in the robust MDP planning framework. A problem in this area is that when using MCTS, the search tree grows exponentially with the horizon. Moreover, it is challenging to obtain deterministic guarantees rather than probabilistic guarantees. The authors propose an estimator that bases its robust value computations based on the sampled search tree only and approximates the contribution of the unsampled part. The resulting estimator has a few favourable properties: deterministic certificates are computable from the current sampled tree, hold at every node, and converge to the robust values as full support is recovered. An algorithm is then also proposed based on the estimator, which is a bound-guided MCTS planner that uses these certificates to improve exploration, prune subtrees, and halt once the optimum is found. The policy bounds from one policy can also be used to evaluate the performance of other policies.

Critical strengths
  • the paper generally reads well and is constructed logically
  • the computational complexity is O(n log n) where n is now the cardinality of the sampled next state support
Critical weaknesses
  • The guarantees provided are somewhat handwavy in the sense that there does not seem to be a convergence rate result
  • It is not clear when the computational complexity is better than other approaches
  • The analysis of related work is a single paragraph with only 4 works
  • The part about exploration guidance does not seem clear, perhaps more explanation is needed there
Questions for authors
  • Abstract: the abstract is very well written in the sense that the algorithm and main contributions can be easily understood. Perhaps a bit more information on what kind of quantitative guarantees are given would be useful.

  • the authors' complexity is based on the cardinality of the next state supported states. in RSS, this is the quantity of children sampled by the generative model. Is the former necessarily better than the latter? When is your computational complexity better in theory?

  • the experiments demonstrate an advantage in terms of the computational complexity compared to UCT. It would be good to compare them in theory as well.

  • what can you say about the convergence of your approach in terms of policy evaluation and policy improvement?

  • can the authors elaborate on the exploration guidance?

1 comment

Dear Reviwer DKkt,

Can you please reply to the authors' responses? Does it clarify your concerns?

AC

Reviewer_UpajOpenReview ↗
Rating
2
Confidence
1
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies MCTS-based planning for robust MDPs. It projects transition kernels and uncertainty sets onto sampled successors and bounds the contributions of unsampled outcomes, avoiding full-state robust backups. Under rectangular uncertainty, the resulting deterministic value bounds guide exploration, prune suboptimal actions, and certify the optimal root action.

Critical strengths

The deterministic certificates provide useful pruning and stopping rules. For rectangular TV uncertainty, restricting robust backups to sampled successors gives explicit computational savings. The experiments demonstrate both these savings and the practical use of the certificates.

Critical weaknesses

My main concern is that the theoretical advance over existing deterministic certificates for nominal planning is not sufficiently isolated. Restricting computation to a partial tree and bounding omitted reward contributions are general ideas. The paper should clarify which new obstacles arise from transition uncertainty and which parts of the analysis require more than extending nominal bounds through worst-case optimization. Without this comparison, I find the theoretical novelty difficult to assess.

The scalability evidence establishes cheaper computation at a fixed simulation budget, but leaves the cost of obtaining accurate decisions unclear. The explicit efficient implementation relies on rectangular TV uncertainty, while convergence assumes support recovery without quantifying the required simulations. Moreover, the large-state runtime experiment does not track certificate width or robust action quality as the state space grows. It therefore does not establish whether the computational advantage persists at matched decision quality.

Questions for authors
  • What are the main technical advances over existing deterministic certificates for nominal planning when extending them to robust planning?
  • Can the state-space scalability experiment also report certificate width or robust action suboptimality, and compare runtime at matched decision quality?
  • Beyond rectangular TV uncertainty, which uncertainty sets admit efficiently represented projections and tractable backups?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.