- 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 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 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 , so it is tight only when the sampled tree captures nearly all trajectory probability mass over the remaining horizon.
Questions for authors
For the setting of Fig. 3, what are the realized / and the certificate width 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.
Dear Reviwer DKkt,
Can you please reply to the authors' responses? Does it clarify your concerns?
AC