Paper deep dive
Scalable Robust MCTS with Anytime Deterministic Optimality Guarantees
Tomer Massas, Vadim Indelman
Intelligence
Status: not_run | Model: - | Prompt: - | Confidence: 0%
Entities (0)
Relation Signals (0)
No relation signals yet.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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.
Tags
Links
- Source: https://arxiv.org/abs/2610.15461v1
- Canonical: https://arxiv.org/abs/2610.15461v1
Trouble viewing inline? Open PDF directly →
Full Text
125,456 characters extracted from source content.
Expand or collapse full text
Scalable Robust MCTS with Anytime Deterministic Optimality Guarantees Tomer Massas Vadim Indelman Faculty of Electrical and Computer Engineering, Technion – Israel Institute of Technology Stephen B. Klein Faculty of Aerospace Engineering, Technion – Israel Institute of Technology Faculty of Data and Decision Sciences, Technion – Israel Institute of Technology tomer.massas@campus.technion.ac.il, vadim.indelman@technion.ac.il 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. 1 Introduction Markov decision processes (MDPs) provide a standard framework for sequential decision making under uncertainty, with the objective of finding a policy that maximizes the expected cumulative reward. As the state space or planning horizon grows, solving the MDP globally becomes computationally intractable. Online planning instead focuses computation on the current decision through a lookahead from the current state. Common online methods, such as Monte Carlo Tree Search (MCTS), address this lookahead through sampling, incrementally constructing and selectively expanding a partial search tree (Kocsis and Szepesvári, 2006). By allocating simulations to a subset of future outcomes, MCTS reduces the cost of online planning while refining root action-value. Model-based online planning relies on a generative transition model that may differ from the true dynamics. Consequently, nominal value estimates may be inaccurate and nominally optimal policies may become suboptimal under model perturbations (Wiesemann et al., 2013). Robust Markov decision processes (RMDPs) address this sensitivity by optimizing against the worst-case model within a set of admissible transition models (Iyengar, 2005; Nilim and El Ghaoui, 2005), but each robust backup then requires an additional optimization over transition models. Repeating these backups throughout the online search tree under a limited decision-time budget further restricts how much of the tree can be explored. To improve scalability, robust RL has explored approaches such as function approximation and policy learning from sampled interactions under model uncertainty (Tamar et al., 2014; Wang and Zou, 2021; Panaganti and Kalathil, 2022). These methods generally aim to learn a robust policy over the state space, rather than allocating computation to the specific decision faced online. More recently, sample-based methods have targeted robust online planning directly, including Robust Sparse Sampling (RSS) (Shazman et al., 2026) and robust MCTS (Dam et al., 2026). However, RSS scales exponentially with the planning horizon, while Dam et al. (2026) robust MCTS relies on the full state space, hindering scalability in real world problems that often exhibit large state spaces. Beyond scalability, online planning acts on a partially explored tree, leaving the effect of unexplored outcomes on the current decision unknown. This is particularly important in the robust setting, where such outcomes may alter the worst-case value and preferred action. For MCTS under a known model, Shah et al. (2022) provide finite-time probabilistic guarantees, which Dam et al. (2026) leverage to establish finite-sample guarantees for Robust-Power-UCT. Similarly, RSS provides probabilistic finite-sample guarantees for robust sample-based planning (Shazman et al., 2026). In a complementary line of work, Barenboim and Indelman (2023); Barenboim and Indelman (2026) establish deterministic anytime guarantees for sample-based anytime POMDP planning in the nominal setting. However, such deterministic anytime guarantees are not available for robust online planning, where the effect of unexplored outcomes must be assessed jointly with model uncertainty. To address these gaps, we formulate robust online planning directly over the sampled portion of the search tree while explicitly accounting for the probability mass associated with unexplored outcomes. Restricting computation to the sampled tree preserves the scalability required for online planning. The resulting bounds quantify how much unexplored outcomes may still affect the current solution. This remaining uncertainty guides further search, focusing the limited planning budget where it can most effectively tighten the bounds and ultimately certify the decision. Contributions. To the best of our knowledge, this is the first work to provide deterministic anytime bounds for sample-based online planning in robust MDPs. Our main contributions are: • We derive deterministic anytime two-sided bounds on the robust value of a fixed policy under general and non-rectangular uncertainty sets. The bounds tighten monotonically as the sampled support expands and, in the non-robust setting, improve upon prior deterministic sample-based bounds by providing tighter lower and upper guarantees. • Under rectangular uncertainty, we extend the fixed-policy bounds to deterministic anytime lower and upper certificates on the optimal robust value through robust Bellman recursion. • We introduce CAR-MCTS (Certified Anytime Robust MCTS), an anytime robust planner with deterministic optimality guarantees computed solely from the constructed partial search tree. By avoiding enumeration of the full state space, CAR-MCTS remains applicable to large state spaces while retaining online computation. It uses the upper certificate to guide exploration and prunes provably suboptimal actions to focus computation on unresolved branches. Once the bounds certify the optimal root action, the search can terminate immediately and return the certified optimal decision. • We empirically evaluate CAR-MCTS against existing robust online planners, demonstrating certificate tightening, pruning, root-action certification, and convergence toward the optimal robust solution. 2 Related Work Robust online planning has received comparatively limited attention. Sharma et al. (2019) introduced RAMCP, a Monte Carlo planner for risk-sensitive Bayes-adaptive planning, but its formulation relies on a prior over a parametric family of transition models. Kohankhaki et al. (2024) developed UA-MCTS, which incorporates transition uncertainty into MCTS exploration; its empirical evaluation considers deterministic environments, while its theoretical analysis is limited to the corrupted-bandit setting. More closely related to our setting, Shazman et al. (2026) introduced Robust Sparse Sampling (RSS), which extends Sparse Sampling to RMDPs using Sample Average Approximation and provides finite-sample performance guarantees. Its complexity is independent of the state-space cardinality but grows exponentially with the planning horizon. Its analysis is further based on non-negative rewards and assumes the existence of a zero-reward fail-state that is absorbing under every model in the uncertainty set. Dam et al. (2026) developed a robust MCTS planner that combines robust power-mean backups with exploration bonuses and establishes finite-sample convergence throughout the search tree. While its tree search is selective, the robust transition optimization retains an explicit dependence on the full state space, thereby limiting scalability as the state-space cardinality grows. 3 Preliminaries A robust MDP accounts for model uncertainty by replacing the single transition model with a set of admissible models. We consider a finite-horizon non-stationary RMDP ℳrob=(,,0:H−1T,r,H)M^rob=(S,A,P^T_0:H-1,r,H), where S and A, are the finite state and action spaces. The set T0:H−1P^T_0:H-1 contains admissible non-stationary transition model sequences PT0:H−1P^T_0:H-1, over the horizon H. The information available to the agent is summarized by the history of actions and states up to time t which is denoted by ht≜(a0:t−1,s0:t)h_t (a_0:t-1,s_0:t). The reward function r:×→[rmin,rmax]r:S×A→[r_min,r_max] is assumed to be bounded. A policy specifies how actions are selected based on the history. For a finite-horizon problem, a policy is a sequence π=πtt=0H−1π=\ _t\_t=0^H-1, where each πt _t maps a history hth_t to an action: πt:ℋt→ _t:H_t . Given a sequence of nominal models P̊0:H−1T P_0:H-1^T, such that the kernel at time step k is P̊kT:×→Δ() P_k^T:S×A→ (S), Let Tt:H−1P^T_t:H-1 denote a general set of admissible non-stationary transition model sequences. One common choice is a ball uncertainty set of the form: Tt:H−1 ^T_t:H-1 =Pt:H−1T:D(Pt:H−1T||P̊t:H−1T)≤ρ, =\P^T_t:H-1:\ D (P^T_t:H-1|| P_t:H-1^T )≤ρ\, (1) where D(⋅,⋅)D(·,·) denotes a distance between sequences of transition kernels, potentially coupling deviations across time steps and state-action pairs, and ρ quantifies the uncertainty radius. The robust value function evaluates π under the worst-case admissible model, and is defined as: Vtπ,rob(ht)=infPTt:H−1∈Tt:H−1Vtπ(ht;Pt:H−1T), V_t^π,rob(h_t)= _P^T_t:H-1 ^T_t:H-1V_t^π(h_t;P^T_t:H-1), (2) where Vtπ(ht;Pt:H−1T)V_t^π(h_t;P^T_t:H-1) is the value function given a sequence of models. To reduce clutter, when clear from context, we omit the explicit dependence on PTt:H−1P^T_t:H-1, and write Vtπ(ht;Pt:H−1T)V_t^π(h_t;P^T_t:H-1) as: Vtπ(ht)=r(st,πt(ht))+st+1:H−1π,PT[∑j=t+1H−1r(sj,πj(hj))∣ht]. V_t^π(h_t)=r (s_t, _t(h_t) )+E^π,P^T_s_t+1:H-1 [ _j=t+1^H-1r (s_j, _j(h_j) ) h_t ]. (3) The non-rectangular formulation in (1) and (2), forces the adversary to choose the model sequence jointly, so the admissibility of the model at one time may depend on choices at others. This coupling prevents a dynamic-programming decomposition of the Bellman backup, motivating the rectangular relaxation introduced by Iyengar (2005); Nilim and El Ghaoui (2005). The rectangular set at time step t is defined as tT,rect=⨂s∈a∈tT(s,a)P_t^T,rect= _ subarraycs \\ a subarrayP^T_t(s,a), and the state-action uncertainty set is: tT(s,a) ^T_t(s,a) =PtT(⋅|s,a):D(PtT(⋅|s,a)||P̊tT(⋅|s,a))≤ρs,a. = \P^T_t(·|s,a):D (P^T_t(·|s,a)|| P_t^T(·|s,a) )≤ _s,a \. (4) Rectangularity is imposed across time and transition rows. First, nature may choose a different worst-case model at each stage independently of its choices at other stages. Second, the uncertainty set is (s,a)(s,a)-rectangular, such that each transition row PtT(⋅∣s,a)P^T_t(· s,a) is selected independently. Since we represent the planning problem as a history tree, we additionally adopt a history-rectangular interpretation: each history-action node (ht,a)(h_t,a) is associated with an independent local uncertainty set tT(st,a)P^T_t(s_t,a). Thus, nature may select different admissible transition rows at distinct history nodes. This represents an adversary that may adapt its models choices locally rather than committing in advance to a fixed sequence of models. Under this rectangular formulation, the robust value in (2) admits the recursive form: Vt,rectπ,rob(ht)=r(st,πt(ht))+infPtT∈tTst+1PtT[Vt+1,rectπ,rob(ht+1)]. V_t,rect^π,rob(h_t)=r (s_t, _t(h_t) )+\ _P^T_t ^T_tE_s_t+1^P^T_t [V_t+1,rect^π,rob(h_t+1) ]. (5) The rectangular relaxation comes at a cost of a more conservative robust value: since t:H⊆t:HrectP_t:H _t:H^rect, enlarging the uncertainty set can only decrease the robust value, yielding Vt,rectπ,rob(ht)≤Vtπ,rob(ht)V_t,rect^π,rob(h_t)≤ V_t^π,rob(h_t). Monte Carlo Tree Search. Monte Carlo Tree Search (MCTS) incrementally constructs a finite lookahead tree rooted at the current history hth_t through repeated simulations (Kocsis and Szepesvári, 2006). During each simulation, at a decision node hkh_k, k≥tk≥ t, an action is selected according to an exploration-strategy that balances exploration and exploitation, and a successor state is sampled from a generative transition model. If the resulting successor has not previously been encountered, the tree is expanded with the new history hk+1=(hk,ak,sk+1)h_k+1=(h_k,a_k,s_k+1). The simulation then continues until the planning horizon is reached, after which the resulting values are backed up along the visited path. Repeating this process progressively expands the sampled portion of the planning tree while concentrating computation on branches favored by the search strategy. At decision time, the planner selects an action at the root based on the resulting action-value estimates. In our setting, this sampled tree defines the support of the simplified RMDP introduced in Section 4. 4 Simplified Robust MDP Computing the exact optimal robust value online is generally intractable: the planning tree grows exponentially with the horizon, while each robust backup additionally requires optimization over the transition uncertainty set. We therefore construct a projected planning problem defined only over the portion of the tree represented by the current samples. Importantly, the projected transition probabilities are not renormalized; probability mass assigned to unsampled next-state outcomes is retained implicitly and will later be used to bound the approximation error deterministically. At a history-action node hk+1−=(hk,ak)h_k+1^-=(h_k,a_k), let ^(hk+1−)⊆ S(h_k+1^-) S denote the sampled next-state support. For compactness, we use st+1:j∈^(hj−)s_t+1:j∈ S(h_j^-) to denote that sk+1∈^(hk+1−)s_k+1∈ S(h_k+1^-) for every k=t,…,j−1k=t,…,j-1. 4.1 Projected Transition Model For each history-action node ht+1−=(ht,at)h_t+1^-=(h_t,a_t), we define the projected transition model by restricting the full transition model to the sampled next-state support: P^tT(st+1∣st,at;ht+1−)≜PtT(st+1∣st,at),st+1∈^(ht+1−). P^T_t(s_t+1 s_t,a_t;h_t+1^-) P^T_t(s_t+1 s_t,a_t), s_t+1∈ S(h_t+1^-). (6) The projected probabilities are not renormalized. Hence, P^tT P^T_t is generally a sub-probability vector, where the missing mass corresponds exactly to transitions leaving the sampled support. Restricting the transition model in this manner reduces each robust backup from an optimization over ℝ||R^|S| to one over ℝ|^(ht+1−)|R^| S(h_t+1^-)|. This reduction makes each robust backup depend only on the sampled support and constitutes the main computational saving of the projected planner. Using these we define the simplified value function: V^tπ(ht)=∑j=tH−1∑st+1:j∈^(hj−)[∏k=tj−1P^kT(sk+1∣sk,πk(hk))]r(sj,πj(hj)). V_t^π(h_t)= _j=t^H-1 _s_t+1:j∈ S(h_j^-) [ _k=t^j-1 P^T_k (s_k+1 s_k, _k(h_k) ) ]r (s_j, _j(h_j) ). (7) Unlike an ordinary value function, V^tπ V_t^π is not an expectation under a normalized transition model; it is the contribution of trajectories represented in the sampled tree. 4.2 Projected Uncertainty Set Simply imposing the original uncertainty constraint directly in the lower-dimensional space does not, in general, preserve the set of models induced by the original RMDP. For a full transition model PkTP_k^T, we define the restriction operator ℛkT(PkT,hk)≜P^kT(sk+1|sk,ak),sk+1∈^(hk+1−)R^T_k(P^T_k;h_k) P^T_k(s_k+1|s_k,a_k),\ \ s_k+1∈ S(h_k+1^-). Let ℛt:H−1TR_t:H-1^T apply this restriction over the planning horizon. We define the projected uncertainty set as the image of the original uncertainty set under this restriction: ^t:H−1T(hH−1)≜ℛt:H−1T(Pt:H−1T):Pt:H−1T∈t:H−1T. P^T_t:H-1(h_H-1) \R^T_t:H-1(P^T_t:H-1):P^T_t:H-1 ^T_t:H-1 \. (8) Thus, every projected model in ^Tt:H−1 P^T_t:H-1 is the restriction of at least one admissible full model; equivalently, its omitted components can be completed to a model belonging to Tt:H−1P^T_t:H-1. We define the resulting simplified-RMDP, as the tuple ℳ^rob=(^,,^t:H−1T,r,H) M^rob=( S,A, P^T_t:H-1,r,H). Given a policy π, its simplified robust value is the worst-case projected value over all projected models consistent with the original uncertainty set: V^tπ,rob(ht)=infP^Tt:H−1∈^Tt:H−1V^tπ(ht;P^t:H−1T). V_t^π,rob(h_t)= _ P^T_t:H-1∈ P^T_t:H-1 V_t^π(h_t; P^T_t:H-1). (9) Thus, V^tπ,rob V_t^π,rob applies the same worst-case model criterion as the original robust value, but evaluates only the trajectories represented in the sampled tree. 5 Anytime Deterministic Guarantees Having defined the simplified RMDP, we now characterize the approximation induced by restricting planning to the sampled tree. We first derive deterministic anytime certificates for the robust value of an arbitrary fixed policy under general uncertainty sets. We then exploit rectangularity to propagate these certificates recursively through the robust Bellman optimality operator and obtain deterministic bounds on the optimal robust value. 5.1 Fixed-Policy Guarantees We first consider an arbitrary policy π and quantify the error introduced by evaluating it on the simplified RMDP rather than the full RMDP. For a projected model sequence P^t:H−1T P_t:H-1^T, we define the cumulative in-support mass: mtπ(P^t:H−1T)≜∑j=tH−1∑st+1:j∈^(hj−)∏k=tj−1P^kT(sk+1∣sk,πk(hk))m_t^π ( P^T_t:H-1 ) _j=t^H-1 _s_t+1:j∈ S(h_j^-) _k=t^j-1 P^T_k (s_k+1 s_k, _k(h_k) ). At each future step j, the inner sum is the probability mass that remains within the sampled tree up to j. Hence, mtπm_t^π measures the cumulative coverage of the policy-induced future by the current sampled tree. Theorem 1 (Fixed-policy deterministic bounds). Let hth_t be the history at time t, and Vtπ,rob(ht)V_t^π,rob(h_t) and V^tπ,rob(ht) V_t^π,rob(h_t) denote the robust values of the same policy π in the full (2) and simplified (9) RMDPs, respectively. For any transition uncertainty set Tt:H−1P^T_t:H-1 and its projected counterpart ^Tt:H−1 P^T_t:H-1: ℒtπ(ht) _t^π(h_t) ≤Vtπ,rob(ht)−V^tπ,rob(ht)≤tπ(ht), ≤ V_t^π,rob(h_t)- V_t^π,rob(h_t)\ ≤\ U_t^π(h_t), (10) where tπ(ht) to0.0pt 20.44434ptU_t^π(h_t) ≜supP^Tt:H−1∈^Tt:H−1[rmax(H−t−mtπ(P^t:H−1T))], _ P^T_t:H-1∈ P^T_t:H-1 [r_max (H-t-m_t^π ( P^T_t:H-1 ) ) ], (11) ℒtπ(ht) _t^π(h_t) ≜infP^Tt:H−1∈^Tt:H−1[rmin(H−t−mtπ(P^t:H−1T))]. _ P^T_t:H-1∈ P^T_t:H-1 [r_min (H-t-m_t^π ( P^T_t:H-1 ) ) ]. (12) The proof is provided in the Appendix A.1. The quantity H−t−mtπH-t-m_t^π is the cumulative probability mass not represented by the sampled tree over the remaining horizon. Since the reward is bounded as rmin≤r(s,a)≤rmaxr_ ≤ r(s,a)≤ r_ , Theorem 1 bounds the value contribution of the unsampled portion of the tree using the reward range. Importantly, the result does not rely on rectangularity or on a particular structure of the transition uncertainty set, and thus applies to general robust MDP formulations. Corollary 1 (Asymptotic convergence). For any policy π, as the sampled state support expands to the full state space at every node ^(hk−)↑,k=t,…,H S(h_k^-) S,\ k=t,…,H, the simplified robust value (9) convergences to the true robust value (2): V^tπ,rob(ht)→Vtπ,rob(ht). V_t^π,rob(h_t) V_t^π,rob(h_t). (13) The proof is provided in the Appendix A.6. Corollary 2 (Monotonic tightening under support expansion). Let n denote the MCTS simulation index. Since the search tree is expanded incrementally, the sampled supports are nested across simulations: ^(n)(hk−)⊆^(n+1)(hk−),k=t,…,H S^(n)(h_k^-) S^(n+1)(h_k^-),\ k=t,…,H. Thus the deterministic bounds of Theorem 1 tighten monotonically: |ℒtπ,(n+1)(ht)|≤|ℒtπ,(n)(ht)|,|tπ,(n+1)(ht)|≤|tπ,(n)(ht)|. |L_t^π,(n+1)(h_t) |≤ |L_t^π,(n)(h_t) |, |U_t^π,(n+1)(h_t) |≤ |U_t^π,(n)(h_t) |. (14) Indeed, expanding the sampled support can only increase the in-support probability mass, such that mtπ,(n)≤mtπ,(n+1).m_t^π,(n)≤ m_t^π,(n+1). Consequently, the cumulative unrepresented mass H−t−mtπH-t-m_t^π decreases, and both bounds contract monotonically toward zero. Thus, adding sampled support can only improve the certificate. The convergence rate is governed by how quickly the planner captures probability mass in the sampled support. Different support-expansion strategies may therefore yield different rates of certificate tightening without affecting its validity. Anytime Certified Policy Evaluation. The bounds in Theorem 1 depend only on the current sampled support, the projected uncertainty set, and the evaluated policy, and are therefore computable from the current partial tree provided the corresponding optimization over the projected uncertainty set can be solved. Consequently, they provide an anytime deterministic certificate on the robust value of any policy, including under non-rectangular uncertainty sets, independently of how that policy was obtained. Recursive Form Under Rectangular Uncertainty. Rectangularity enables a recursive robust Bellman decomposition, allowing the lower and upper fixed-policy certificates to be propagated through the planning tree. Accordingly, the fixed-policy certificates of Theorem 1 admit a recursive action-conditioned form. The recursive quantity introduced below is directly related to the cumulative in-support mass mtπm_t^π of Theorem 1. Under rectangular uncertainty, 1+δtπ(st∣ht)=infP^Tt:H−1∈^Tt:H−1mtπ(P^t:H−1T).1+ _t^π(s_t h_t)= _ P^T_t:H-1∈ P^T_t:H-1m_t^π( P^T_t:H-1). The unit term corresponds to the current stage, while δtπ _t^π represents the worst-case cumulative in-support mass from the next step onward. Rectangularity allows this global minimization to be decomposed recursively as: δkπ(sk|hk) _k^π(s_k|h_k) =infP^kT∈^kTδkπ,P^kT(sk,πk(hk))k=t,…,H−2, = _ P^T_k∈ P^T_k _k^π, P^T_k(s_k, _k(h_k)) k=t,…,H-2, (15) δkπ,P^kT(sk,ak|hk) _k^π, P^T_k(s_k,a_k|h_k) =∑sk+1∈^(hk+1−)P^kT(sk+1∣sk,ak)[1+δk+1π(sk+1|hk+1)], = _s_k+1∈ S(h_k+1^-) P^T_k(s_k+1 s_k,a_k)\, [1+ _k+1^π(s_k+1|h_k+1) ], (16) with a terminal condition δH−1π(sH−1)≡0 _H-1^π(s_H-1)≡ 0. The term 1+δt+1π1+ _t+1^π accounts for the probability mass retained at the next state together with all subsequent in-support mass along the continuation. The action-conditioned bounds are defined as: ℒt,rectπ,P^tT(ht,at)≜rmin(H−1−t−δtπ,P^tT(st,at|ht)), _t,rect^π, P^T_t(h_t,a_t) r_min (H-1-t- _t^π, P^T_t (s_t,a_t|h_t) ), (17) t,rectπ,P^tT(ht,at)≜rmax(H−1−t−δtπ,P^tT(st,at|ht)). _t,rect^π, P^T_t(h_t,a_t) r_max (H-1-t- _t^π, P^T_t (s_t,a_t|h_t) ). (18) For clarity, we present the recursive bounds for the common case rmin≤0≤rmaxr_ ≤ 0≤ r_ . The remaining reward-sign cases follow analogously by replacing the corresponding infimum with a supremum when the multiplying reward bound is negative; the full expressions are given in the appendix. 5.2 Optimality Guarantees Building on the recursive fixed-policy certificates derived above for rectangular uncertainty, we now extend them to bound the optimal robust value. By optimizing the lower and upper recursive backups over actions, we obtain deterministic anytime bounds on Vt,rect∗,robV_t,rect^*,rob. Using the action-conditioned bounds (17) and (18), for an arbitrary continuation policy π, we define the lower and upper robust deterministic backups as: ℒℛℬtπ(ht,at) _t^π(h_t,a_t) ≜r(st,at)+infP^tT∈^tT(^st+1|htP^tT[V^t+1,rectπ,P^t+1T,ℒℛℬ(ht+1)]+ℒt,rectπ,P^tT(ht,at)), r(s_t,a_t)+ _ P^T_t∈ P^T_t ( E_s_t+1|h_t P^T_t\! [ V_t+1,rect^π, P_t+1^T,LRDB(h_t+1) ]+L_t,rect^π, P^T_t(h_t,a_t) ), (19) ℛℬtπ(ht,at) _t^π(h_t,a_t) ≜r(st,at)+infP^tT∈^tT(^st+1|htP^tT[V^t+1,rectπ,P^t+1T,ℛℬ(ht+1)]+t,rectπ,P^tT(ht,at)). r(s_t,a_t)+ _ P^T_t∈ P^T_t ( E_s_t+1|h_t P^T_t\! [ V_t+1,rect^π, P_t+1^T,URDB(h_t+1) ]+U_t,rect^π, P^T_t(h_t,a_t) ). (20) We use P^t+1T,ℒℛℬ P_t+1^T,LRDB and P^t+1T,ℛℬ P_t+1^T,URDB to denote the projected continuation models induced by the minimizing model choices of the corresponding recursive LRDB and URDB backups from time t+1t+1 onward. Importantly, the projected value and its correction term are evaluated under the same transition model inside each robust backup. Thus, the adversarial model jointly determines both the projected return and the corresponding approximation correction, rather than minimizing them independently. We now leverage these recursive deterministic backups to establish deterministic anytime optimality guarantees for the rectangular RMDP. Theorem 2 (Optimal robust value bounds). Let hth_t be an expanded history node at time step t, and let πLπ^L and πUπ^U be the lower- and upper-bound policies defined in (22). Under rectangular transition uncertainty, the optimal robust value is bounded deterministically by: ℒℛℬtπL(ht,πtL(ht))≤Vt,rect∗,rob(ht)≤ℛℬtπU(ht,πtU(ht)),LRDB_t^π^L (h_t, _t^L(h_t) )≤ V_t,rect^*,rob(h_t) _t^π^U (h_t, _t^U(h_t) ), (21) where πtL _t^L and πtU _t^U are the lower- and upper-bound policies defined greedily with respect to their corresponding deterministic backups: πtL(ht)=argmaxat∈tℒℛℬtπL(ht,at),πtU(ht)=argmaxat∈tℛℬtπU(ht,at). _t^L(h_t)= arg\,max _a_t _t \LRDB_t^π^L(h_t,a_t) \, _t^U(h_t)= arg\,max _a_t _t \URDB_t^π^U(h_t,a_t) \. (22) Theorem 2 assumes that all actions in A are initialized at every expanded decision node. The proof is provided in the Appendix A.7. Corollary 3 (Asymptotic optimality). As the sampled state support expands to the full state space at every node, ^(hk−)↑,k=t,…,H, S(h_k^-) S,\ k=t,…,H, both deterministic bounds converge to the optimal rectangular robust value: ℒℛℬtπL(ht,πtL(ht)) _t^π^L (h_t, _t^L(h_t) ) ⟶Vt,rect∗,rob(ht), V_t,rect^*,rob(h_t), (23) ℛℬtπU(ht,πtU(ht)) _t^π^U (h_t, _t^U(h_t) ) ⟶Vt,rect∗,rob(ht). V_t,rect^*,rob(h_t). (24) The proof is provided in the Appendix A.9. Action pruning and certification. The lower and upper action-value certificates induce a deterministic ordering test between actions. For two actions a,a′a,a , if: ℛℬ(h,a)<ℒℛℬ(h,a′)\ URDB (h,a )<LRDB (h,a ), then a is provably suboptimal and its subtree can be safely pruned. Likewise, an action a∗a^* is certified optimal when: ℒℛℬ(h,a∗)>maxa≠a∗ℛℬ(h,a)\ LRDB (h,a^* )> _a≠ a^*URDB (h,a ). This eliminates redundant search in branches that can no longer affect the optimal decision, allowing computation to be focused on unresolved regions of the tree. At the root, this provides an anytime stopping criterion: planning can terminate as soon as the optimal root action is certified, rather than exhausting the search budget. Robust backup computation. For the TV uncertainty sets in our experiments, each inner robust optimization reduces to a robust expectation over the sampled successors and one aggregate unsampled state, solvable in O(|^(h,a)|log|^(h,a)|)O(| S(h,a)| | S(h,a)|) time. See Appendix B. Together, Theorems 1 and 2 provide runtime-accessible deterministic certificates for both policy evaluation and optimal robust planning. We next use these certificates within our MCTS planner and evaluate their effect on convergence, pruning, and root-action certification. 6 Algorithm Algorithm 1 CAR-MCTS: Certified Anytime Robust MCTS 1: Input: root state s0s_0, horizon H, budget N 2: Output: root action a, certification flag c, action-value bounds 3: h0←NewNode(s0,0)h_0← NewNode(s_0,0) 4: n←0n← 0 5: while n<Nn<N do 6: (c,a⋆)←Certify(h0)(c,a )← Certify(h_0) 7: if c then 8: return (a⋆,true,[ℒℛℬ(s0,a⋆),ℛℬ(s0,a⋆)])(a , true,[LRDB(s_0,a ),URDB(s_0,a )]) 9: end if 10: h←h0h← h_0 11: path←∅path← 12: while t(h)<H−1t(h)<H-1 and n<Nn<N do 13: a←argmaxaℛℬt(h)(h,a)a← _aURDB_t(h)(h,a) 14: s′∼P̊t(h)T(⋅∣s(h),a)s P^T_t(h)(· s(h),a) 15: n←n+1n← n+1 16: append (h,a)(h,a) to path 17: h←ExpandIfNeeded(h,a,s′)h← ExpandIfNeeded(h,a,s ) 18: end while 19: for all (h,a)(h,a) in reverse(path)(path) do 20: Backup(h,ah,a) 21: Prune(h) 22: end for 23: end while 24: a←argmaxaQ^0rob(s0,a)a← _a Q^rob_0(s_0,a) 25: return (a,false,[ℒℛℬ(s0,a),ℛℬ(s0,a)])(a, false,[LRDB(s_0,a),URDB(s_0,a)]) Operations: NewNode(s,t)(s,t) Initialize all actions a∈a . ExpandIfNeeded(h,a,s′)(h,a,s ) If s′s is not in the sampled support, add it and create the corresponding child node. Return the child. Backup(h,a)(h,a) Update Q^rob Q^rob, ℒℛℬLRDB, and ℛℬURDB. Prune(h)(h) Prune action a if ℛℬ(h,a)<maxa′ℒℛℬ(h,a′).URDB(h,a)< _a LRDB(h,a ). Certify(h)(h) Let a⋆=argmaxaℒℛℬ(h,a).a = _aLRDB(h,a). Return true if ℒℛℬ(h,a⋆)>maxa≠a⋆ℛℬ(h,a).LRDB(h,a )> _a≠ a URDB(h,a). We instantiate the proposed certificates in CAR-MCTS (Certified Anytime Robust MCTS), summarized in Algorithm 1. At each simulation, the planner descends the current search tree by selecting the action with the largest upper certificate ℛℬURDB and samples the next state from the nominal transition model. Previously unseen successors are added to the sampled support, after which the projected robust values and certificates are backed up along the visited path, avoiding explicit enumeration of the full state space and thereby preserving scalability to large state spaces. During the backup, actions whose upper certificate falls below a competing lower certificate are pruned at every visited node. At the root, planning terminates early whenever an action is certified optimal. If certification is not reached within the sampling budget, CAR-MCTS returns the action with the largest projected robust action-value Q^0rob Q_0^rob together with deterministic optimality certificates. 7 Results Experimental setup. We evaluate CAR-MCTS in the Frozen Lake domain with varying grid sizes, terminal holes, and different start and goal cells. At each nonterminal cell, the agent chooses one of four actions: left, down, right, or up. Under the nominal transition model, the agent moves toward the intended neighboring cell with probability 1−pslip1-p_slip; the remaining probability pslipp_slip is distributed over cells in concentric Chebyshev-distance rings around the current cell, up to a configurable radius k. This ring model allows the number of possible successor states to be varied across experiments. Transition uncertainty is modeled by rectangular total-variation sets around the nominal transition rows. The reward function and remaining experiment-specific parameters, including the grid size, horizon, pslipp_slip, ring radius k, and uncertainty radius, are provided in the Appendix. We first evaluate the fixed-policy guarantees of Theorem 1 by progressively expanding the sampled tree of a fixed policy. Figure 1(a) plots the projected robust value and its deterministic certificate against the fraction of the complete depth-H tree represented, with the exact robust value obtained from the full tree shown for reference. Throughout the search, the exact value remains within the certificate, while the interval contracts as the sampled support expands and the projected value converges to the exact value. The experiment is repeated over 50 independent nested tree expansions, illustrating both the anytime validity and the convergence of the certificate. (a) Fixed-policy certificate tightening. (b) Pruning and root-action certification. Figure 1: Deterministic certificates: fixed-policy evaluation and CAR-MCTS planning. Figure 1(b) illustrates how CAR-MCTS uses the certificates during planning. Actions down and up, which lead toward nearby holes, are quickly identified as suboptimal and pruned; their certificates therefore stop changing once their subtrees are no longer sampled. The remaining computation is concentrated on the left and right actions. Since tree traversal selects the action with the largest ℛℬURDB, the more promising left branch is sampled more frequently, causing its certificate and projected value to tighten faster. Eventually, left is deterministically certified as the optimal action. Even when certification is not reached within the budget, this targeted allocation improves the projected values used by CAR-MCTS’s argmaxaQ^rob(s0,a) _a Q^rob(s_0,a) fallback decision. Comparison with robust planning baselines. Figure 2 compares CAR-MCTS with nominal UCT, RSS (Shazman et al., 2026), and Robust Power UCT (Dam et al., 2026) on a 16×1616× 16 Frozen Lake domain. The execution dynamics are fixed at ptrue=0.05p_true=0.05, while pslipp_slip denotes the slip probability assumed by the planner and the uncertainty radius is adjusted to the resulting model mismatch. Hence, larger values of pslipp_slip primarily increase model mismatch rather than environment difficulty. CAR-MCTS maintains substantially higher return over increasing mismatch than all baselines, with the advantage becoming particularly pronounced at larger horizons. At H=11H=11, CAR-MCTS maintains near-maximal return through pslip=0.5p_slip=0.5, whereas nominal UCT and Robust Power UCT deteriorate sharply and show no comparable benefit from deeper lookahead. Figure 2: CAR-MCTS vs. robust planning baselines across model mismatch and planning horizons. In particular, the degradation of nominal UCT illustrates the limitation of planning with an inaccurate nominal model when transition uncertainty is significant. RSS is omitted at H=11H=11 because its sparse-sampling expansion becomes computationally prohibitive. At pslip=0.6p_slip=0.6, CAR-MCTS also deteriorates as the large model mismatch induces a correspondingly large uncertainty set, leading to increasingly conservative behavior under the robust policy. Scalability with state-space size. Figure 3 isolates the dependence of robust planning on state-space cardinality. For each grid size, the transition kernel is constructed so that every state has nonzero probability under every transition row, i.e., |suppPT(⋅∣s,a)|=|||suppP^T(· s,a)|=|S|, while the planning horizon and simulation budget are held fixed. Figure 3: Decision time of CAR-MCTS and Robust Power UCT as |||S| grows under full-support transition kernels. CAR-MCTS remains nearly constant at 55–66 ms per decision as |||S| grows from 10210^2 to over 10610^6. In contrast, Robust Power UCT grows from 2.12.1 ms to 11.611.6 s. This difference stems from the robust backups: CAR-MCTS operates only on the sampled support generated by its fixed simulation budget, whereas Robust Power UCT incurs computation over the full state space, making online planning increasingly impractical as |||S| grows. Thus, CAR-MCTS scales essentially independently of full state-space cardinality, maintaining practical decision times even in very large state spaces. The same distinction is reflected in memory usage: CAR-MCTS requires only the sampled-support representation and remains at approximately 0.20.2 MB across the sweep, whereas Robust Power UCT’s full-state representation grows with |||S|, reaching 152152 MB at ||≈106|S|≈ 10^6. Additional ablations on robustness to increasing environment slipperiness and model mismatch, sensitivity to the number of feasible successor states, scalability with planning depth, true optimal-action selection rate, and practical certification and pruning rates are provided in Appendix C. 8 Conclusion In this work, we presented a methodology for scalable robust online MDP planning with deterministic anytime guarantees. The core principle we propose is to restrict computation to the sampled search tree while explicitly accounting for the contribution of unexplored outcomes, thereby avoiding enumeration of the full state space. We first derived deterministic lower and upper bounds on the error between the simplified and full robust values of an arbitrary policy under general transition uncertainty, including non-rectangular sets, and showed that these certificates tighten as the sampled support expands and converge as the full support is recovered. Under rectangular uncertainty, we extended this construction to recursive action-value certificates that bound the optimal robust value, enabling provably suboptimal actions to be pruned, reducing unnecessary computation, and optimal root actions to be certified for early termination. Building on these results, we introduced CAR-MCTS, which integrates the certificates directly into MCTS to guide exploration, prune resolved branches, and terminate once the root decision is certified, while retaining deterministic action-value certificates when the sampling budget is exhausted. Experiments validate the derived guarantees, demonstrate robustness to model mismatch, and show that CAR-MCTS remains practical as the full state space grows while competing robust MCTS methods become increasingly costly. To our knowledge, this is the first robust online MCTS framework combining scalable sampled-support planning with deterministic anytime guarantees. 9 Acknowledgments This work was supported by the Israel Ministry of Innovation, Science and Technology. References Barenboim and Indelman (2023) M. Barenboim and V. Indelman Online pomdp planning with anytime deterministic guarantees. Advances in Neural Information Processing Systems 36, p. 79886–79902. Cited by: §1. Barenboim and Indelman (2026) M. Barenboim and V. Indelman Online pomdp planning with anytime deterministic optimality guarantees. Artificial Intelligence 350, p. 104442. External Links: ISSN 0004-3702, Document, Link Cited by: §1. Dam et al. (2026) T. Dam, K. Panaganti, B. Driss, and A. Wierman Online robust reinforcement learning through monte-carlo planning. arXiv preprint arXiv:2609.18599. Cited by: §1, §1, §2, §7. Iyengar (2005) G. N. Iyengar Robust dynamic programming. Mathematics of Operations Research 30 (2), p. 257–280. Cited by: §1, §3. Kocsis and Szepesvári (2006) L. Kocsis and C. Szepesvári Bandit based monte-carlo planning. In European conference on machine learning, p. 282–293. Cited by: §1, §3. Kohankhaki et al. (2024) F. Kohankhaki, K. Aghakasiri, H. Zhang, T. Wei, C. Gao, and M. Müller Monte carlo tree search in the presence of transition uncertainty. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 38, p. 20151–20158. Cited by: §2. Nilim and El Ghaoui (2005) A. Nilim and L. El Ghaoui Robust control of markov decision processes with uncertain transition matrices. Operations Research 53 (5), p. 780–798. Cited by: §1, §3. Panaganti and Kalathil (2022) K. Panaganti and D. Kalathil Sample complexity of robust reinforcement learning with a generative model. In International Conference on Artificial Intelligence and Statistics, p. 9582–9602. Cited by: §1. Shah et al. (2022) D. Shah, Q. Xie, and Z. Xu Nonasymptotic analysis of monte carlo tree search. Operations research 70 (6), p. 3234–3260. Cited by: §1. Sharma et al. (2019) A. Sharma, J. Harrison, M. Tsao, and M. Pavone Robust and adaptive planning under model uncertainty. In Proceedings of the international conference on automated planning and scheduling, Vol. 29, p. 410–418. Cited by: §2. Shazman et al. (2026) T. Shazman, I. Lev-Yehudi, R. Benchetrit, and V. Indelman Online robust planning under model uncertainty: a sample-based approach. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 40, p. 36386–36393. Cited by: §C.4, §1, §1, §2, §7. Tamar et al. (2014) A. Tamar, S. Mannor, and H. Xu Scaling up robust mdps using function approximation. In International conference on machine learning, p. 181–189. Cited by: §1. Wang and Zou (2021) Y. Wang and S. Zou Online robust reinforcement learning with model uncertainty. Advances in Neural Information Processing Systems 34, p. 7193–7206. Cited by: §1. Wiesemann et al. (2013) W. Wiesemann, D. Kuhn, and B. Rustem Robust markov decision processes. Mathematics of Operations Research 38 (1), p. 153–183. Cited by: §1. Appendix A Mathematical analysis and proofs A.1 Proof of Theorem 1 (Fixed-policy deterministic bounds): Essentials lemmas and definitions for the proof: 1. The restriction mapping ℛR: ℛt:k−1T(Pt:k−1T;hk−1) ^T_t:k-1(P^T_t:k-1;h_k-1) =PTt:k−1,st:k−1∈^(hk−1),0,otherwise. = casesP^T_t:k-1,&s_t:k-1∈ S(h_k-1),\\ 0,&otherwise. cases (25) Lemma 1 (restated). Let H be the horizon of the MDP, π=πkk=tH−1π=\ _k\_k=t^H-1 be the policy,r:×→[rmin,rmax]r:S×A→[r_ ,r_ ] be the bounded state-action reward function , and P^kT P^T_k be the projected transition model defined in (6). The theoretical and simplified value functions VtπV_t^π and V^tπ V_t^π at time step t are: Vtπ(ht)=∑j=tH−1∑st+1:j∏k=tj−1PkT(sk+1∣sk,πk(hk))r(sj,πj(hj)), V_t^π(h_t)= _j=t^H-1 _s_t+1:j _k=t^j-1P^T_k (s_k+1 s_k, _k(h_k) )r (s_j, _j(h_j) ), (26) V^tπ(ht)=∑j=tH−1∑st+1:j∈^(hj)∏k=tj−1P^kT(sk+1∣sk,πk(hk))r(sj,πj(hj)). V_t^π(h_t)= _j=t^H-1 _s_t+1:j∈ S(h_j) _k=t^j-1 P^T_k (s_k+1 s_k, _k(h_k) )r (s_j, _j(h_j) ). (27) Lemma 2 (restated). For any 2 functions f(θ)f(θ) and f^(θ) f(θ), the following holds: infθf(θ)−infθf^(θ)≤supθ(f(θ)−f^(θ)). _θf(θ)- _θ f(θ)≤ _θ (f(θ)- f(θ) ). (28) Lemma 3 (restated). Let P denote some uncertainty set, and P denote its projected counterpart defined in (8). Let ℛR be the restriction map that takes a full probability distribution P∈P and retains only the entries associated with the sampled support: ℛ(P,^) (P; S) =P(s),s∈^,0,otherwise. = casesP(s),&s∈ S,\\ 0,&otherwise. cases (29) Then minimizing some function f:P^→ℝf: P over P is the same as minimizing f(ℛ(P))f(R(P)) over the full set P, namely: infP∈f(ℛ(P))=infP^∈^f(P^). _ subarraycP subarrayf(R(P))= _ subarrayc P∈ P subarrayf( P). (30) Lemma 4 (restated). For any 2 functions f(θ)f(θ) and f^(θ) f(θ), the following holds: infθ(f(θ)−f^(θ)).≤infθf(θ)−infθf^(θ) _θ (f(θ)- f(θ) ).≤ _θf(θ)- _θ f(θ) (31) Proof of Theorem 1. Theorem 1 (restated) (Fixed-policy deterministic bounds). Let hth_t be the history at time t, and Vtπ,rob(ht)V_t^π,rob(h_t) and V^tπ,rob(ht) V_t^π,rob(h_t) denote the robust values of the same policy π in the full (2) and simplified (9) RMDPs, respectively. For any transition uncertainty set Tt:H−1P^T_t:H-1 and its projected counterpart ^Tt:H−1 P^T_t:H-1: ℒtπ(ht)≤Vtπ,rob(ht)−V^tπ,rob(ht)≤tπ(ht), _t^π(h_t)≤ V_t^π,rob(h_t)- V_t^π,rob(h_t)\ ≤\ U_t^π(h_t), (32) such that: tπ(ht)≜rmax(H−t−infP^Tt:H−1∈^Tt:H−1mtπ(P^Tt:H−1)),rmax≥0,rmax(H−t−supP^Tt:H−1∈^Tt:H−1mtπ(P^Tt:H−1)),rmax<0, _t^π(h_t) casesr_max (H-t- _ P^T_t:H-1∈ P^T_t:H-1m_t^π ( P^T_t:H-1 ) ),r_max≥ 0,\\ r_max (H-t- _ P^T_t:H-1∈ P^T_t:H-1m_t^π ( P^T_t:H-1 ) ),r_max<0, cases (33) ℒtπ(ht)≜rmin(H−t−supP^Tt:H−1∈^Tt:H−1mtπ(P^Tt:H−1)),rmin≥0,rmin(H−t−infP^Tt:H−1∈^Tt:H−1mtπ(P^Tt:H−1)),rmin<0, _t^π(h_t) casesr_min (H-t- _ P^T_t:H-1∈ P^T_t:H-1m_t^π ( P^T_t:H-1 ) ),r_min≥ 0,\\ r_min (H-t- _ P^T_t:H-1∈ P^T_t:H-1m_t^π ( P^T_t:H-1 ) ),r_min<0, cases (34) and mtπ(P^t:H−1T)≜∑j=tH−1∑st+1:j∈^(hj)∏k=tj−1P^kT(sk+1∣sk,πk(hk)). m_t^π ( P^T_t:H-1 ) _j=t^H-1 _s_t+1:j∈ S(h_j) _k=t^j-1 P^T_k (s_k+1 s_k, _k(h_k) ). (35) Proof. The robust non-rectangular value function is defined as: Vtπ,rob(ht)≜infPTt:H−1∈Tt:H−1Vtπ(ht;Pt:H−1T), V_t^π,rob(h_t) _P^T_t:H-1 ^T_t:H-1\ V_t^π (h_t;P^T_t:H-1 ), (36) and the simplified robust value function: V^tπ,rob(ht)≜infP^Tt:H−1∈^Tt:H−1V^tπ(ht;P^t:H−1T), V_t^π,rob(h_t) _ P^T_t:H-1∈ P^T_t:H-1\, V_t^π (h_t; P^T_t:H-1 ), (37) where the theoretical and simplified value functions are defined in (26) and (27). Using Lemma (3) together with the restriction map ℛTt:H−1R^T_t:H-1 from (25), which project the full uncertainty set onto the projected uncertainty set, we obtain: V^tπ,rob(ht)=infPTt:H−1∈Tt:H−1V^tπ(ht;ℛt:H−1T(Pt:H−1T)). V_t^π,rob(h_t)= _P^T_t:H-1 ^T_t:H-1\, V_t^π\! (h_t;R^T_t:H-1(P^T_t:H-1) ). (38) We first begin with the Upper Bound: Vtπ,rob(ht)−V^tπ,rob(ht) V_t^π,rob(h_t)- V_t^π,rob(h_t) = = infPTt:H−1∈Tt:H−1Vtπ(ht;Pt:H−1T)−infPTt:H−1∈Tt:H−1V^tπ(ht;ℛt:H−1T(Pt:H−1T)) _P^T_t:H-1 ^T_t:H-1\,V_t^π\! (h_t;\,P^T_t:H-1 )- _P^T_t:H-1 ^T_t:H-1\, V_t^π\! (h_t;\,R^T_t:H-1(P^T_t:H-1) ) (39) ≤ ≤ supPTt:H−1∈Tt:H−1(Vtπ(ht;Pt:H−1T)−V^tπ(ht;ℛt:H−1T(Pt:H−1T))) _P^T_t:H-1 ^T_t:H-1 (\,V_t^π\! (h_t;\,P^T_t:H-1 )- V_t^π\! (h_t;\,R^T_t:H-1(P^T_t:H-1) ) ) (40) For the last transition we used Lemma 2. Writing the value functions explicitly: supPTt:H−1∈Tt:H−1( _P^T_t:H-1 ^T_t:H-1 ( ∑j=tH−1∑st+1:j∏k=tj−1PkT(sk+1∣sk,πk(hk))r(sj,πj(hj))− _j=t^H-1 _s_t+1:j _k=t^j-1P^T_k (s_k+1 s_k, _k(h_k) )r (s_j, _j(h_j) )- ∑j=tH−1∑st+1:j∈^(hj)∏k=tj−1ℛkT(PkT(sk+1∣sk,πk(hk)))r(sj,πj(hj))) _j=t^H-1 _s_t+1:j∈ S(h_j) _k=t^j-1R^T_k (P^T_k (s_k+1 s_k, _k(h_k) ) )r (s_j, _j(h_j) ) ) (41) splitting the sums into in/out support: supPTt:H−1∈Tt:H−1( _P^T_t:H-1 ^T_t:H-1 ( ∑j=tH−1(∑st+1:j∈^(hj)∏k=tj−1(PkT(sk+1∣sk,πk(hk))−ℛkT(PkT(sk+1∣sk,πk(hk))))⏟≡0r(sj,πj(hj)) _j=t^H-1 ( _s_t+1:j∈ S(h_j) _k=t^j-1 (P^T_k (s_k+1 s_k, _k(h_k) )-R^T_k (P^T_k (s_k+1 s_k, _k(h_k) ) ) )_≡ 0r (s_j, _j(h_j) ) +∑st+1:j∉^(hj)∏k=tj−1PkT(sk+1∣sk,πk(hk))r(sj,πj(hj))))= + _s_t+1:j∉ S(h_j) _k=t^j-1P^T_k (s_k+1 s_k, _k(h_k) )r (s_j, _j(h_j) ) ) )= (42) The under braced term equals zero by the definition of the Restricted mapping ℛR. Therefore: supPTt:H−1∈Tt:H−1(∑j=tH−1∑st+1:j∉^(hj)∏k=tj−1PkT(sk+1∣sk,πk(hk))r(sj,πj(hj))) _P^T_t:H-1 ^T_t:H-1 ( _j=t^H-1 _s_t+1:j∉ S(h_j) _k=t^j-1P^T_k (s_k+1 s_k, _k(h_k) )r (s_j, _j(h_j) ) ) (43) ≤ ≤ rmaxsupPTt:H−1∈Tt:H−1(∑j=tH−1∑st+1:j∉^(hj)∏k=tj−1PkT(sk+1∣sk,πk(hk))) r_max _P^T_t:H-1 ^T_t:H-1 ( _j=t^H-1 _s_t+1:j∉ S(h_j) _k=t^j-1P^T_k (s_k+1 s_k, _k(h_k) ) ) (44) Since r(s,a)≤rmaxr(s,a)≤ r_ , the out-of-support contribution is upper bounded by rmaxr_ times its probability mass. For rmax≥0r_ ≥ 0, maximizing this product is equivalent to maximizing the out-of-support mass, yielding the supremum in (44). If rmax<0r_ <0, the supremum is replaced by an infimum. Since P(st+1:j|ht)P(s_t+1:j|h_t) defines a full probability distribution over sequences of states trajectories, we have: ∑st+1:jP(st+1:j|ht)=∑st+1:j∏k=tj−1PkT(sk+1∣sk,πk(hk))≡1, _s_t+1:jP(s_t+1:j|h_t)= _s_t+1:j _k=t^j-1P^T_k (s_k+1 s_k, _k(h_k) )≡ 1, (45) therefore: ∑st+1:j∉^(hj)P(st+1:j|ht)=1−∑st+1:j∈^(hj)P(st+1:j|ht). _s_t+1:j∉ S(h_j)P(s_t+1:j|h_t)=1- _s_t+1:j∈ S(h_j)P(s_t+1:j|h_t). (46) Thus (44) equals: rmaxsupPTt:H−1∈Tt:H−1(∑j=tH−1(1−∑st+1:j∈^(hj)∏k=tj−1PkT(sk+1∣sk,πk(hk))))= r_max _P^T_t:H-1 ^T_t:H-1 ( _j=t^H-1 (1- _s_t+1:j∈ S(h_j) _k=t^j-1P^T_k (s_k+1 s_k, _k(h_k) ) ) )= (47) rmaxsupPTt:H−1∈Tt:H−1(∑j=tH−1(1−∑st+1:j∈^(hj)∏k=tj−1ℛkT(PkT(sk+1∣sk,πk(hk)))))= r_max _P^T_t:H-1 ^T_t:H-1 ( _j=t^H-1 (1- _s_t+1:j∈ S(h_j) _k=t^j-1R^T_k (P^T_k (s_k+1 s_k, _k(h_k) ) ) ) )= (48) Using Lemma 3 again: rmaxsupP^Tt:H−1∈^Tt:H−1(∑j=tH−1(1−∑st+1:j∈^(hj)∏k=tj−1P^kT(sk+1∣sk,πk(hk))))= r_max _ P^T_t:H-1∈ P^T_t:H-1 ( _j=t^H-1 (1- _s_t+1:j∈ S(h_j) _k=t^j-1 P^T_k (s_k+1 s_k, _k(h_k) ) ) )= (49) rmax(H−t−infP^Tt:H−1∈^Tt:H−1∑j=tH−1∑st+1:j∈^(hj)∏k=tj−1P^kT(sk+1∣sk,πk(hk)))≜ r_max (H-t- _ P^T_t:H-1∈ P^T_t:H-1 _j=t^H-1 _s_t+1:j∈ S(h_j) _k=t^j-1 P^T_k (s_k+1 s_k, _k(h_k) ) ) (50) tπ(ht) _t^π(h_t) (51) Lower Bound: Vtπ,rob(ht)−V^tπ,rob(ht)= V_t^π,rob(h_t)- V_t^π,rob(h_t)= infPTt:H−1∈Tt:H−1Vtπ(ht;Pt:H−1T)−infPTt:H−1∈Tt:H−1V^tπ(ht;ℛt:H−1T(Pt:H−1T))≥ _P^T_t:H-1 ^T_t:H-1\,V_t^π\! (h_t;\,P^T_t:H-1 )- _P^T_t:H-1 ^T_t:H-1\, V_t^π\! (h_t;\,R^T_t:H-1(P^T_t:H-1) )≥ (52) infPTt:H−1∈Tt:H−1(Vtπ(ht;Pt:H−1T)−V^tπ(ht;ℛt:H−1T(Pt:H−1T)))= _P^T_t:H-1 ^T_t:H-1 (\,V_t^π\! (h_t;\,P^T_t:H-1 )- V_t^π\! (h_t;\,R^T_t:H-1(P^T_t:H-1) ) )= (53) For the last transition we used Lemma 4. As shown above in (42), the difference on the support is canceled, and we get: infPTt:H−1∈Tt:H−1∑j=tH−1(∑st+1:j∉^(hj)∏k=tj−1PkT(sk+1∣sk,πk(hk))r(sj,πj(hj)))≥ _P^T_t:H-1 ^T_t:H-1 _j=t^H-1 ( _s_t+1:j∉ S(h_j) _k=t^j-1P^T_k (s_k+1 s_k, _k(h_k) )r (s_j, _j(h_j) ) )≥ (54) Since r(s,a)≥rminr(s,a)≥ r_ , the out-of-support contribution is lower bounded by rminr_ times its probability mass. For rmin≤0r_ ≤ 0, minimizing this product is equivalent to maximizing the out-of-support mass, yielding the supremum below. If rmin>0r_ >0, the supremum is replaced by an infimum. rminsupPTt:H−1∈Tt:H−1∑j=tH−1(∑st+1:j∉^(hj)∏k=tj−1PkT(sk+1∣sk,πk(hk)))= r_min _P^T_t:H-1 ^T_t:H-1 _j=t^H-1 ( _s_t+1:j∉ S(h_j) _k=t^j-1P^T_k (s_k+1 s_k, _k(h_k) ) )= (55) rminsupP^Tt:H−1∈^Tt:H−1∑j=tH−1(1−∑st+1:j∈^(hj)∏k=tj−1P^kT(sk+1∣sk,πk(hk)))= r_min _ P^T_t:H-1∈ P^T_t:H-1 _j=t^H-1 (1- _s_t+1:j∈ S(h_j) _k=t^j-1 P^T_k (s_k+1 s_k, _k(h_k) ) )= (56) rmin(H−t−infP^Tt:H−1∈^Tt:H−1∑j=tH−1∑st+1:j∈^(hj)∏k=tj−1P^kT(sk+1∣sk,πk(hk))) r_min (H-t- _ P^T_t:H-1∈ P^T_t:H-1 _j=t^H-1 _s_t+1:j∈ S(h_j) _k=t^j-1 P^T_k (s_k+1 s_k, _k(h_k) ) ) (57) ≜ℒtπ(ht) _t^π(h_t) (58) which concludes the proof. ∎ Transition to a rectangular setting: If we assume rectangular uncertainty sets 4, the above bounds 51, 58 can be written as nested optimizations, that allows dynamic programming: t,rectπU(ht)≜rmax _t,rect^π^U(h_t) r_max (H−1−t−(infP^tT∈^tT∑st+1∈^(ht+1−)P^tT(st+1∣πt(ht),st;ht)( (H-1-t- ( _ P^T_t∈ P^T_t _s_t+1∈ S(h_t+1^-) P^T_t(s_t+1 _t(h_t),s_t;h_t)\, ( 1+infP^t+1T∈^t+1T∑st+2∈^(ht+2−)P^t+1T(st+2∣πt+1,st+1)(CLOSE 1+ _ P^T_t+1∈ P^T_t+1 _s_t+2∈ S(h_t+2^-) P^T_t+1(s_t+2 _t+1,s_t+1)\, ( ⋯ ·s 1+infP^H−2T∈^H−2T∑sH−1∈^(hH−1−)P^H−2T(sH−1∣πH−2,sH−2))⋯) 1+ _ P^T_H-2∈ P^T_H-2 _s_H-1∈ S(h_H-1^-) P^T_H-2(s_H-1 _H-2,s_H-2)\, )·s ) (59) ℒt,rectπL(ht)≜rmin _t,rect^π^L(h_t) r_min (H−1−t−(infP^tT∈^tT∑st+1∈^(ht+1−)P^tT(st+1∣πt(ht),st;ht)( (H-1-t- ( _ P^T_t∈ P^T_t _s_t+1∈ S(h_t+1^-) P^T_t(s_t+1 _t(h_t),s_t;h_t)\, ( 1+infP^t+1T∈^t+1T∑st+2∈^(ht+2−)P^t+1T(st+2∣πt+1,st+1)(CLOSE 1+ _ P^T_t+1∈ P^T_t+1 _s_t+2∈ S(h_t+2^-) P^T_t+1(s_t+2 _t+1,s_t+1)\, ( ⋯ ·s 1+infP^H−2T∈^H−2T∑sH−1∈^(hH−1−)P^H−2T(sH−1∣πH−2,sH−2))⋯) 1+ _ P^T_H-2∈ P^T_H-2 _s_H-1∈ S(h_H-1^-) P^T_H-2(s_H-1 _H-2,s_H-2)\, )·s ) (60) We can write 59, 60 in a compact form, recursively: t,rectπU(ht)≜rmax(H−1−t−δtπU(st|ht)) _t,rect^π^U(h_t) r_max (H-1-t- _t^π^U(s_t|h_t) ) (61) ℒt,rectπL(ht)≜rmin(H−1−t−δtπL(st|ht)) _t,rect^π^L(h_t) r_min (H-1-t- _t^π^L(s_t|h_t) ) (62) Such that for k∈[t,H−2]k∈[t,H-2]: δkπ(sk|hk) _k^π(s_k|h_k) =infP^kT∈^kTδkπ,P^kT(sk,πk(hk)) = _ P^T_k∈ P^T_k _k^π, P^T_k(s_k, _k(h_k)) (63) δkπ,P^kT(sk,ak|hk) _k^π, P^T_k(s_k,a_k|h_k) =∑sk+1∈^(hk+1−)P^kT(sk+1∣sk,ak)[1+δk+1π(sk+1|hk+1)] = _s_k+1∈ S(h_k+1^-) P^T_k(s_k+1 s_k,a_k)\, [1+ _k+1^π(s_k+1|h_k+1) ] (64) and for k=H−1k=H-1 there is no continuation therefore: δH−1π(sH−1)≡0 _H-1^π(s_H-1)≡ 0 (65) Note: we switch the infinf to supsup: 1. In equations 60, 63: if rmin>0r_ >0. 2. In equations 59, 63: if rmax<0r_ <0. 3. δ is shared only when rmin≤0≤rmaxr_min≤ 0≤ r_max A.2 Proof of Lemma 1 Lemma 1. Let H be the horizon of the MDP, π=πkk=tH−1π=\ _k\_k=t^H-1 be the policy,r:×→[rmin,rmax]r:S×A→[r_ ,r_ ] be the bounded state-action reward function , and P^kT P^T_k be the projected transition model defined in (6). The theoretical and simplified value functions VtπV_t^π and V^tπ V_t^π at time step t are: Vtπ(ht)=∑j=tH−1∑st+1:j∏k=tj−1PkT(sk+1∣sk,πk(hk))r(sj,πj(hj)), V_t^π(h_t)= _j=t^H-1 _s_t+1:j _k=t^j-1P^T_k (s_k+1 s_k, _k(h_k) )r (s_j, _j(h_j) ), (66) V^tπ(ht)=∑j=tH−1∑st+1:j∈^(hj)∏k=tj−1P^kT(sk+1∣sk,πk(hk))r(sj,πj(hj)). V_t^π(h_t)= _j=t^H-1 _s_t+1:j∈ S(h_j) _k=t^j-1 P^T_k (s_k+1 s_k, _k(h_k) )r (s_j, _j(h_j) ). (67) Proof. The value function is the expected future cumulative reward: Vtπ(ht)=st+1:H−1π,PT[∑j=tH−1r(sj,πj)∣ht]. V_t^π(h_t)=E^π,P^T_s_t+1:H-1 [ _j=t^H-1r(s_j, _j) h_t ]. (68) By the linearity of the expectation [∑f(⋅)]=∑[f(⋅)]E[Σ f(·)]= [f(·)], and writing the expectation explicitly: ∑j=tH−1st+1:H−1π,PT[r(sj,πj)∣ht]=∑j=tH−1∑st+1:jP(st+1:j|ht)r(sj,πj). _j=t^H-1E^π,P^T_s_t+1:H-1 [r(s_j, _j) h_t ]= _j=t^H-1 _s_t+1:jP (s_t+1:j|h_t )r(s_j, _j). (69) Applying chain rule on the states sequence probability: P(st+1:j|ht)=∏k=tj−1P(sk+1|ht,st+1:k). P(s_t+1:j|h_t)= _k=t^j-1P(s_k+1|h_t,s_t+1:k). (70) We assume markovian models, therefore the probability of transition to next state depends only on current state and action. since hk=(st:k,at:k−1)h_k=(s_t:k,a_t:k-1), the states sequence probability is: P(st+1:j|ht)=∏k=tj−1PkT(sk+1|sk,π(hk)). P(s_t+1:j|h_t)= _k=t^j-1P^T_k (s_k+1|s_k,π(h_k) ). (71) Where in (71) we assume non-stationary transition model. Using (69) and (71), we derived the final expression for the value function: Vtπ(ht)=∑j=tH−1∑st+1:j∏k=tj−1PkT(sk+1|sk,π(hk))r(sj,πj(hj)). V_t^π(h_t)= _j=t^H-1 _s_t+1:j _k=t^j-1P^T_k (s_k+1|s_k,π(h_k) )r (s_j, _j(h_j) ). (72) Similarly, using the projected transition model defined in (6), the simplified value function is: V^tπ(ht)=∑j=tH−1∑st+1:j∈^(hj)∏k=tj−1P^kT(sk+1∣sk,πk(hk))r(sj,πj(hj)). V_t^π(h_t)= _j=t^H-1 _s_t+1:j∈ S(h_j) _k=t^j-1 P^T_k (s_k+1 s_k, _k(h_k) )r (s_j, _j(h_j) ). (73) ∎ For stochastic policies: Vtπ(ht)=∑j=tH−1∑at:j∑st+1:j(∏k=tj−1π(ak|hk)PkT(sk+1|sk,ak))π(aj|hj)r(sj,aj). V_t^π(h_t)= _j=t^H-1 _a_t:j _s_t+1:j ( _k=t^j-1π(a_k|h_k)P^T_k(s_k+1|s_k,a_k) )π(a_j|h_j)r(s_j,a_j). (74) A.3 Proof of Lemma 2 Lemma 2. for any 2 function f(θ),f^(θ)f(θ), f(θ), the following holds: infθf(θ)−infθf^(θ)≤supθ(f(θ)−f^(θ)) _θf(θ)- _θ f(θ)≤ _θ (f(θ)- f(θ) ) (75) Proof. Let ε≜supθ∈Θ(f(θ)−g(θ)) _θ∈ (f(θ)-g(θ) ) Then for every θ, f(θ)−g(θ)≤ε→f(θ)≤ε+g(θ)f(θ)-g(θ)≤ \ \ →\ \ f(θ)≤ +g(θ) Taking minima gives infθf(θ)≤infθg(θ)+ε _θf(θ)≤ _θg(θ)+ Therefore infθf(θ)−infθg(θ)≤ε≜supθ∈Θ(f(θ)−g(θ)) _θf(θ)- _θg(θ)≤ _θ∈ (f(θ)-g(θ) ) ∎ A.4 Proof of Lemma 3 Lemma 3. Let P denote some uncertainty set, and P denote its projected version. Let ℛR be the restriction map that takes a full probability distribution P∈P and retains only the entries associated with the sampled support: ℛ(P,^) (P; S) =P(s),s∈^,0,otherwise. = casesP(s),&s∈ S,\\ 0,&otherwise. cases (76) Then minimizing some function f:P^→ℝf: P over P is the same as minimizing f(ℛ(P))f(R(P)) over the full set P, namely: infP∈f(ℛ(P))=infP^∈^f(P^), _ subarraycP subarrayf(R(P))= _ subarrayc P∈ P subarrayf( P), (77) Proof. By the definition of the projected uncertainty sets as the images of the full uncertainty sets under the restriction maps, we have ^=ℛ(), P=R (P ), (78) We prove the desired equality by showing both inequalities. First, let P∈, P , (79) be arbitrary full distribution. By definition: ℛ(P)∈^, (P)∈ P, (80) Therefore, infP^∈^f(P^)≤f(ℛ(P)). _ P∈ Pf( P)≤ f(R(P)). (81) Since this holds for every P∈, P , (82) we can take the infimum over the full uncertainty set and obtain infP^∈^f(P^)≤infP∈f(ℛ(P)). _ P∈ Pf( P)≤ _P f(R(P)). (83) For the opposite direction, let P^∈^, P∈ P, (84) be arbitrary projected distribution. Since the projected uncertainty set is defined as the image of the full uncertainty set, there exist a full model: P∈, P , (85) such that P^=ℛ(P), P=R(P), (86) Therefore, f(P^)=f(ℛ(P)) f( P)=f(R(P)) (87) Hence, infP∈f(ℛ(P))≤f(P^). _P f(R(P))≤ f( P). (88) Since this holds for every P^∈^, P∈ P, (89) we can take the infimum over the projected uncertainty set and obtain infP∈f(ℛ(P))≤infP^∈^f(P^). _P f(R(P))≤ _ P∈ Pf( P). (90) Combining the two inequalities gives equality: infP∈f(ℛ(P))=infP^∈^f(P^). _P f(R(P))= _ P∈ Pf( P). (91) Which proves the Lemma. ∎ A.5 Proof of Lemma 4 Lemma 4. for any 2 function f(θ),f^(θ)f(θ), f(θ), the following holds: infθ(f(θ)−f^(θ))≤infθf(θ)−infθf^(θ) _θ (f(θ)- f(θ) )≤ _θf(θ)- _θ f(θ) (92) Proof. Let ε≜infθ∈Θ(f(θ)−g(θ)) _θ∈ (f(θ)-g(θ) ) Then for every θ, ε≤f(θ)−g(θ)→ε+g(θ)≤f(θ) ≤ f(θ)-g(θ)\ \ →\ \ +g(θ)≤ f(θ) Taking minima gives ε+infθg(θ)≤infθf(θ) + _θg(θ)≤ _θf(θ) Therefore ε≜infθ∈Θ(f(θ)−g(θ))≤infθf(θ)−infθg(θ) _θ∈ (f(θ)-g(θ) )≤ _θf(θ)- _θg(θ) ∎ A.6 Proof of Corollary 1 (Asymptotic convergence) Corollary 1 (restated) (Asymptotic convergence). For any policy π, as the sampled state support expands to the full state space at every node ^(hk−)↑,k=t,…,H S(h_k^-) S,\ k=t,…,H, the simplified robust value (9) convergences to the true robust value (2): V^tπ,rob(ht)→^→Vtπ,rob(ht). V_t^π,rob(h_t) subarrayc S→S subarrayV_t^π,rob(h_t). (93) Proof. Restating the upper and lower bounds of theorem 1: tπ(ht)≜rmax(H−t−infP^Tt:H−1∈^Tt:H−1mtπ(P^Tt:H−1)),rmax≥0,rmax(H−t−supP^Tt:H−1∈^Tt:H−1mtπ(P^Tt:H−1)),rmax<0 _t^π(h_t) casesr_max (H-t- _ P^T_t:H-1∈ P^T_t:H-1m_t^π ( P^T_t:H-1 ) ),r_max≥ 0,\\ r_max (H-t- _ P^T_t:H-1∈ P^T_t:H-1m_t^π ( P^T_t:H-1 ) ),r_max<0 cases (94) ℒtπ(ht)≜rmin(H−t−supP^Tt:H−1∈^Tt:H−1mtπ(P^Tt:H−1)),rmin≥0,rmin(H−t−infP^Tt:H−1∈^Tt:H−1mtπ(P^Tt:H−1)),rmin<0 _t^π(h_t) casesr_min (H-t- _ P^T_t:H-1∈ P^T_t:H-1m_t^π ( P^T_t:H-1 ) ),r_min≥ 0,\\ r_min (H-t- _ P^T_t:H-1∈ P^T_t:H-1m_t^π ( P^T_t:H-1 ) ),r_min<0 cases (95) mtπ(P^t:H−1T)≜∑j=tH−1∑st+1:j∈^(hj)∏k=tj−1P^kT(sk+1∣sk,πk(hk)) m_t^π ( P^T_t:H-1 ) _j=t^H-1 _s_t+1:j∈ S(h_j) _k=t^j-1 P^T_k (s_k+1 s_k, _k(h_k) ) (96) The state-trajectory likelihood is bounded by 1, and is monotonic non-decreasing for every new state sample that is added, and equals 1 over the full state space, namely: ∑st+1:j∈^(hj)P(st+1:j|ht)=∑st+1:j∈^(hj)∏k=tj−1PkT(sk+1∣sk,πk(hk))→^→1, _s_t+1:j∈ S(h_j)P(s_t+1:j|h_t)= _s_t+1:j∈ S(h_j) _k=t^j-1P^T_k (s_k+1 s_k, _k(h_k) ) subarrayc S→S subarray1, (97) Therefore mtπ(P^t:H−1T)→^→H−t m_t^π ( P^T_t:H-1 ) subarrayc S→S subarrayH-t (98) Which induces: tπ(ht)→^→0 _t^π(h_t) subarrayc S→S subarray0 (99) ℒtπ(ht)→^→0 _t^π(h_t) subarrayc S→S subarray0 (100) ∎ A.7 Proof of Theorem 2 (Optimal robust value bounds): Essentials lemmas and definitions for the proof: 1. In-support expectation operator: ^s[f(h)]=∑s∈^PtT(s)⋅f(h) E_s\! [f(h) ]= _s∈ SP^T_t(s)· f(h) (101) 2. Upper robust deterministic bound: ℛℬtπU(ht,at) _t^π^U(h_t,a_t) ≜r(st,at)+infP^tT∈^tT(^st+1|htP^tT[V^t+1,rectπU,P^t+1T,ℛℬ(ht+1)]+t,rectπU,P^tT(ht,at)) r(s_t,a_t)+ _ P^T_t∈ P^T_t ( E_s_t+1|h_t P^T_t\! [ V_t+1,rect^π^U, P_t+1^T,URDB(h_t+1) ]+U_t,rect^π^U, P^T_t(h_t,a_t) ) (102) =Q^t,rectπU,P^tT,ℛℬ(ht,at)+t,rectπU,P^tT,ℛℬ(ht,at) = Q_t,rect^π^U, P_t^T,URDB(h_t,a_t)+U_t,rect^π^U, P_t^T,URDB(h_t,a_t) (103) 3. Lower robust deterministic bound: ℒℛℬtπL(ht,at) _t^π^L(h_t,a_t) ≜r(st,at)+infP^tT∈^tT(^st+1|htP^tT[V^t+1,rectπL,P^t+1T,ℒℛℬ(ht+1)]+ℒt,rectπL,P^tT(ht,at)) r(s_t,a_t)+ _ P^T_t∈ P^T_t ( E_s_t+1|h_t P^T_t\! [ V_t+1,rect^π^L, P_t+1^T,LRDB(h_t+1) ]+L_t,rect^π^L, P^T_t(h_t,a_t) ) (104) =Q^t,rectπL,P^tT,ℒℛℬ(ht,at)+ℒt,rectπL,P^tT,ℒℛℬ(ht,at) = Q_t,rect^π^L, P_t^T,LRDB(h_t,a_t)+L_t,rect^π^L, P_t^T,LRDB(h_t,a_t) (105) Lemma 5 (restated). Let hth_t be the history at time step t. For any action at∈ta_t _t, and future action at+1a_t+1 selected by the greedy policies πL,πUπ^L,π^U, the following inequalities hold: ℒℛℬtπL(ht,at)≤r(st,at)+infPtT∈tT(^st+1|htPtT[ℒℛℬt+1πL(ht+1)]+Pout⋅rmin⋅(H−1−t)), _t^π^L(h_t,a_t)≤ r(s_t,a_t)+ _P^T_t ^T_t ( E_s_t+1|h_t^P^T_t\! [LRDB_t+1^π^L(h_t+1) ]+P^out· r_min·(H-1-t) ), (106) And: ℛℬtπU(ht,at)≥r(st,at)+infPtT∈tT(^st+1|htPtT[ℛℬt+1πU(ht+1)]+Pout⋅rmax⋅(H−1−t)). _t^π^U(h_t,a_t)≥ r(s_t,a_t)+ _P^T_t ^T_t ( E_s_t+1|h_t^P^T_t\! [URDB_t+1^π^U(h_t+1) ]+P^out· r_max·(H-1-t) ). (107) Proof of Theorem 2. Theorem 2 (restated) (Optimal robust value bounds). Let hth_t be an expanded history node at time step t, and let πLπ^L and πUπ^U be the lower- and upper-bound policies defined in (109),(110). Under rectangular transition uncertainty, the optimal robust value is bounded deterministically by: ℒℛℬtπL(ht)≤Vt,rect∗,rob(ht)≤ℛℬtπU(ht). _t^π^L(h_t)≤ V_t,rect^*,rob(h_t)\ ≤\ URDB_t^π^U(h_t). (108) Subject to the policies: πU=πkUk=H−1tπ^U=\ _k^U\_k=H-1^t and πL=πkLk=H−1tπ^L=\ _k^L\_k=H-1^t: πtL(ht)=argmaxat∈tℒℛℬtπL(ht,at)=argmaxat∈tQ^t,rectπL,P^tT,ℒℛℬ(ht,at)+ℒt,rectπL,P^tT,ℒℛℬ(ht,at), _t^L(h_t)= arg\,max _a_t _t \LRDB_t^π^L(h_t,a_t) \= arg\,max _a_t _t \ Q_t,rect^π^L, P_t^T,LRDB(h_t,a_t)+L_t,rect^π^L, P_t^T,LRDB(h_t,a_t) \, (109) πtU(ht)=argmaxat∈tℛℬtπU(ht,at)=argmaxat∈tQ^t,rectπU,P^tT,ℛℬ(ht,at)+t,rectπU,P^tT,ℛℬ(ht,at), _t^U(h_t)= arg\,max _a_t _t \URDB_t^π^U(h_t,a_t) \= arg\,max _a_t _t \ Q_t,rect^π^U, P_t^T,URDB(h_t,a_t)+U_t,rect^π^U, P_t^T,URDB(h_t,a_t) \, (110) Proof. We prove by induction, that by applying the Bellman optimality operator on upper/lower bounds to the robust value function, we get an upper/lower bounds on the optimal value function. Base case (t=H−1t=H-1): the optimal action-value at the terminal node is: QH−1,rect∗,rob(hH−1,aH−1)=r(sH−1,aH−1). Q_H-1,rect^*,rob(h_H-1,a_H-1)=r(s_H-1,a_H-1). (111) At the terminal time step H−1H-1 of the MDP, there is no future transition term, therefore: H−1,rectπU=ℒH−1,rectπL=0 _H-1,rect^π^U=L_H-1,rect^π^L=0 (112) We set the terminal action-value to be the immediate reward: Q^H−1,rectπL,rob(hH−1,aH−1)=Q^H−1,rectπU,rob(hH−1,aH−1)=r(sH−1,aH−1). Q_H-1,rect^π^L,rob(h_H-1,a_H-1)= Q_H-1,rect^π^U,rob(h_H-1,a_H-1)=r(s_H-1,a_H-1). (113) ℒℛℬH−1πL(hH−1,aH−1)=ℛℬH−1πU(hH−1,aH−1)=r(sH−1,aH−1). _H-1^π^L(h_H-1,a_H-1)=URDB_H-1^π^U(h_H-1,a_H-1)=r(s_H-1,a_H-1). (114) and the base-case for the induction is the best immediate reward: maxaH−1∈H−1ℒℛℬH−1πL(hH−1,aH−1)≤ _ subarrayca_H-1 _H-1 subarrayLRDB_H-1^π^L(h_H-1,a_H-1)≤ VH−1,rect∗,rob(hH−1)≤maxaH−1∈H−1ℛℬH−1πU(hH−1,aH−1) V_H-1,rect^*,rob(h_H-1)≤ _ subarrayca_H-1 _H-1 subarrayURDB_H-1^π^U(h_H-1,a_H-1) (115) VH−1,rect∗,rob(hH−1) V_H-1,rect^*,rob(h_H-1) ≡maxaH−1∈H−1r(sH−1,aH−1). ≡ _ subarrayca_H-1 _H-1 subarrayr(s_H-1,a_H-1). (116) Induction Hypothesis: at time step t+1t+1, for every ht+1=(ht,at,st+1)h_t+1=(h_t,a_t,s_t+1) with st+1∈^(ht+1−)s_t+1∈ S(h_t+1^-) we assume the following holds: ℒℛℬt+1πL(ht+1)≤Vt+1,rect∗,rob(ht+1)≤ℛℬt+1πU(ht+1). _t+1^π^L(h_t+1)≤ V_t+1,rect^*,rob(h_t+1)\ ≤\ URDB_t+1^π^U(h_t+1). (117) This means that at the next depth of the tree ℒℛℬt+1πL,ℛℬt+1πULRDB_t+1^π^L,\ URDB_t+1^π^U are already valid lower/upper bounds on the optimal rectangular robust value. Induction Step: We will now show that the hypothesis holds for time step t, specifically: ℒℛℬtπL(ht,at)≤Qt,rect∗,rob(ht,at)≤ℛℬtπU(ht,at) _t^π^L(h_t,a_t)≤ Q_t,rect^*,rob(h_t,a_t) _t^π^U(h_t,a_t) (118) Writing the the action value in the recursive Bellman form: Qt,rect∗,rob(ht,at)=r(st,at)+infPtT∈tTst+1|htPtT[Vt+1,rect∗,rob(ht+1)]= Q_t,rect^*,rob(h_t,a_t)=r(s_t,a_t)+ _P^T_t ^T_tE_s_t+1|h_t^P^T_t\! [V_t+1,rect^*,rob(h_t+1) ]= (119) r(st,at)+infPtT∈tT(∑st+1∈^PtT(st+1|st,at)Vt+1,rect∗,rob(ht+1)+∑st+1∉^PtT(st+1|st,at)Vt+1,rect∗,rob(ht+1)) r(s_t,a_t)+ _P^T_t ^T_t ( _s_t+1∈ SP^T_t(s_t+1|s_t,a_t)V_t+1,rect^*,rob(h_t+1)+ _s_t+1∉ SP^T_t(s_t+1|s_t,a_t)V_t+1,rect^*,rob(h_t+1) ) (120) For simplicity we use the following abbreviation: Pout=∑st+1∉^PtT(st+1|st,at)P^out= _s_t+1∉ SP^T_t(s_t+1|s_t,a_t) by the induction hypothesis at time step t+1t+1, and bound the out of support term by rmax/rmin⋅(H−1−t)r_max/r_min·(H-1-t): r(st,at)+infPtT∈tT(^st+1|htPtT[ℒℛℬt+1πL(ht+1)]+Pout⋅rmin⋅(H−1−t))≤ r(s_t,a_t)+ _P^T_t ^T_t ( E_s_t+1|h_t^P^T_t\! [LRDB_t+1^π^L(h_t+1) ]+P^out· r_min·(H-1-t) )≤ (121) Qt,rect∗,rob(ht,at)≤ Q_t,rect^*,rob(h_t,a_t)≤ r(st,at)+infPtT∈tT(^st+1|htPtT[ℛℬt+1πU(ht+1)]+Pout⋅rmax⋅(H−1−t)), r(s_t,a_t)+ _P^T_t ^T_t ( E_s_t+1|h_t^P^T_t\! [URDB_t+1^π^U(h_t+1) ]+P^out· r_max·(H-1-t) ), following Lemma 5: ℛℬtπU(ht,at)≥r(st,at)+infPtT∈tT(^st+1|htPtT[ℛℬt+1πU(ht+1)]+Pout⋅rmax⋅(H−1−t)), _t^π^U(h_t,a_t)≥ r(s_t,a_t)+ _P^T_t ^T_t ( E_s_t+1|h_t^P^T_t\! [URDB_t+1^π^U(h_t+1) ]+P^out· r_max·(H-1-t) ), (122) ℒℛℬtπL(ht,at)≤r(st,at)+infPtT∈tT(^st+1|htPtT[ℒℛℬt+1πL(ht+1)]+Pout⋅rmin⋅(H−1−t)), _t^π^L(h_t,a_t)≤ r(s_t,a_t)+ _P^T_t ^T_t ( E_s_t+1|h_t^P^T_t\! [LRDB_t+1^π^L(h_t+1) ]+P^out· r_min·(H-1-t) ), (123) taking maximum over the actions gives: Vt,rect∗,rob(ht)=maxat∈tQt,rect∗,rob(ht,at)≤maxat∈tℛℬtπU(ht,at)≜ℛℬtπU(ht), V_t,rect^*,rob(h_t)= _ subarrayca_t _t subarrayQ_t,rect^*,rob(h_t,a_t)≤ _ subarrayca_t _t subarrayURDB_t^π^U(h_t,a_t) _t^π^U(h_t), (124) Vt,rect∗,rob(ht)=maxat∈tQt,rect∗,rob(ht,at)≥maxat∈tℒℛℬtπL(ht,at)≜ℒℛℬtπL(ht), V_t,rect^*,rob(h_t)= _ subarrayca_t _t subarrayQ_t,rect^*,rob(h_t,a_t)≥ _ subarrayca_t _t subarrayLRDB_t^π^L(h_t,a_t) _t^π^L(h_t), (125) which proves the induction step, and the theorem. ∎ A.8 Proof of Lemma 5 Restating essential definition for the lemma: 1) ℛℬ/ℒℛℬURDB/LRDB transition model: P^tT,ℛℬ(⋅|st,at)=argminP^tT∈^tT^st+1|htP^tT[V^t+1,rectπU,P^t+1T,ℛℬ(ht+1)]+t,rectπU,P^tT(ht,at), P_t^T,URDB(·|s_t,a_t)= arg\,min _ P^T_t∈ P^T_t \ E_s_t+1|h_t P^T_t [ V_t+1,rect^π^U, P_t+1^T,URDB(h_t+1) ]+U_t,rect^π^U, P^T_t(h_t,a_t) \, (126) P^tT,ℒℛℬ(⋅|st,at)=argminP^tT∈^tT^st+1|htP^tT[V^t+1,rectπL,P^t+1T,ℒℛℬ(ht+1)]+ℒt,rectπL,P^tT(ht,at), P_t^T,LRDB(·|s_t,a_t)= arg\,min _ P^T_t∈ P^T_t \ E_s_t+1|h_t P^T_t [ V_t+1,rect^π^L, P_t+1^T,LRDB(h_t+1) ]+L_t,rect^π^L, P^T_t(h_t,a_t) \, (127) 2) For simplicity, we denote the probabily mass for the off-support by: Pout=∑st+1∉^PtT(st+1|st,at)P^out= _s_t+1∉ SP^T_t(s_t+1|s_t,a_t) Proof of Theorem 5. Lemma 5. Let hth_t be the history at time step t. For any action at∈ta_t _t, and future action at+1a_t+1 selected by the greedy policies πL,πUπ^L,π^U, the following inequalities hold: ℒℛℬtπL(ht,at)≤r(st,at)+infPtT∈tT(^st+1|htPtT[ℒℛℬt+1πL(ht+1)]+Pout⋅rmin⋅(H−1−t)), _t^π^L(h_t,a_t)≤ r(s_t,a_t)+ _P^T_t ^T_t ( E_s_t+1|h_t^P^T_t\! [LRDB_t+1^π^L(h_t+1) ]+P^out· r_min·(H-1-t) ), (128) And: ℛℬtπU(ht,at)≥r(st,at)+infPtT∈tT(^st+1|htPtT[ℛℬt+1πU(ht+1)]+Pout⋅rmax⋅(H−1−t)). _t^π^U(h_t,a_t)≥ r(s_t,a_t)+ _P^T_t ^T_t ( E_s_t+1|h_t^P^T_t\! [URDB_t+1^π^U(h_t+1) ]+P^out· r_max·(H-1-t) ). (129) Proof. We first focus on the upper bound: By the definition of the ℛℬtπU(ht,at)URDB_t^π^U(h_t,a_t) (102), at time step t+1t+1: r(st,at)+infPtT∈tT(^st+1|htPtTCLOSE r(s_t,a_t)+ _P^T_t ^T_t ( E_s_t+1|h_t^P^T_t OPEN[ℛℬt+1πU(ht+1)]+Pout⋅rmax⋅(H−1−t))= \! [URDB_t+1^π^U(h_t+1) ]+P^out· r_max·(H-1-t) )= (130) r(st,at)+infPtT∈tT(^st+1|htPtTCLOSE r(s_t,a_t)+ _P^T_t ^T_t ( E_s_t+1|h_t^P^T_t OPEN[maxat+1∈t+1ℛℬt+1πU(ht+1,at+1)]+Pout⋅rmax⋅(H−t))= \! [ _ subarrayca_t+1 _t+1 subarray \URDB_t+1^π^U(h_t+1,a_t+1) \ ]+P^out· r_max·(H\!-\!1\!-\!t) )= (131) r(st,at)+infPtT∈tT(^st+1|htPtTCLOSE r(s_t,a_t)+ _P^T_t ^T_t ( E_s_t+1|h_t^P^T_t [maxat+1∈t+1Q^t+1,rectπU,P^t+1T,ℛℬ(ht+1,at+1)+t+1,rectπU,P^t+1T,ℛℬ(ht+1,at+1)] \! [ _ subarrayca_t+1 _t+1 subarray \ Q_t+1,rect^π^U, P_t+1^T,URDB(h_t+1,a_t+1)+U_t+1,rect^π^U, P_t+1^T,URDB(h_t+1,a_t+1) \ ] +Pout⋅rmax⋅(H−1−t)) +P^out· r_max·(H-1-t) ) (132) The action at+1a_t+1 that maximizes the expression is the same action that comes from the policy πUπ^U, namely: at+1U=πt+1U(ht+1)=argmaxat+1∈tQ^t+1,rectπU,P^t+1T,ℛℬ(ht+1,at+1)+t+1,rectπU,P^t+1T,ℛℬ(ht+1,at+1) a_t+1^U=π^U_t+1(h_t+1)= arg\,max _a_t+1 _t \ Q_t+1,rect^π^U, P_t+1^T,URDB(h_t+1,a_t+1)+U_t+1,rect^π^U, P_t+1^T,URDB(h_t+1,a_t+1) \ (133) Therefore we replace at+1a_t+1 with πt+1U _t+1^U (Q^(ht+1,πt+1U)→V^(ht+1)) ( Q(h_t+1,π^U_t+1)→ V(h_t+1) ): r(st,at)+infPtT∈tT(^st+1|htPtT[V^t+1,rectπU,P^t+1T,ℛℬ(ht+1)+t+1,rectπU,P^t+1T,ℛℬ(ht+1,πt+1U)]) r(s_t,a_t)+ _P^T_t ^T_t ( E_s_t+1|h_t^P^T_t\! [ V_t+1,rect^π^U, P_t+1^T,URDB(h_t+1)+U_t+1,rect^π^U, P_t+1^T,URDB(h_t+1, _t+1^U) ] ) +Pout⋅rmax⋅(H−1−t))= +P^out· r_max·(H-1-t) )= (134) we split the sum to in/out sampled support: r(st,at) r(s_t,a_t) +infPtT∈tT(∑st+1∈^PtT(st+1|st,at)[V^t+1,rectπU,P^t+1T,ℛℬ(ht+1)+t+1,rectπU,P^t+1T,ℛℬ(ht+1,πt+1U)] + _P^T_t ^T_t ( _s_t+1∈ SP^T_t(s_t+1|s_t,a_t)\! [ V_t+1,rect^π^U, P_t+1^T,URDB(h_t+1)+U_t+1,rect^π^U, P_t+1^T,URDB(h_t+1, _t+1^U) ] +∑st+1∉^PtT(st+1|st,at)[rmax⋅(H−1−t)])= + _s_t+1∉ SP^T_t(s_t+1|s_t,a_t) [r_max·(H-1-t) ] )= (135) r(st,at) r(s_t,a_t) +infPtT∈tT(∑st+1∈^PtT(st+1|st,at)[V^t+1,rectπU,P^t+1T,ℛℬ(ht+1)+rmax⋅(H−2−t−δt+1πU,P^t+1T,ℛℬ(st+1|ht+1))] + _P^T_t ^T_t ( _s_t+1∈ SP^T_t(s_t+1|s_t,a_t)\! [ V_t+1,rect^π^U, P_t+1^T,URDB(h_t+1)+r_max· (H-2-t- _t+1^π^U, P_t+1^T,URDB\!\!\!\!\!\!\!\!(s_t+1|h_t+1) ) ] +(1−∑st+1∈^PtT(st+1|st,at))⋅[rmax⋅(H−1−t)])= + (1- _s_t+1∈ SP^T_t(s_t+1|s_t,a_t) )· [r_max·(H-1-t) ] )= (136) r(st,at) r(s_t,a_t) +infPtT∈tT(∑st+1∈^PtT(st+1|st,at)⋅V^t+1,rectπU,P^t+1T,ℛℬ(ht+1) + _P^T_t ^T_t ( _s_t+1∈ SP^T_t(s_t+1|s_t,a_t)· V_t+1,rect^π^U, P_t+1^T,URDB(h_t+1) OPEN+rmax(H−1−t−∑st+1∈^PtT(st+1|st,at)⋅[1+δt+1πU,P^t+1T,ℛℬ(st+1|ht+1)]))≤ +r_max (H-1-t-\!\!\! _s_t+1∈ S\!\!P^T_t(s_t+1|s_t,a_t)· [1+ _t+1^π^U, P_t+1^T,URDB\!\!\!\!\!\!\!\!\!(s_t+1|h_t+1) ]\! ) )≤ (137) as defined in (63), δ uses infimum/suprimum based on the sign of rmaxr_max : δt+1πU≤δt+1πU,P^t+1T,ℛℬ,rmax≥0,δt+1πU≥δt+1πU,P^t+1T,ℛℬ,rmax<0. cases _t+1^π^U≤ _t+1^π^U, P_t+1^T,URDB,&r_max≥ 0,\\[10.00002pt] _t+1^π^U≥ _t+1^π^U, P_t+1^T,URDB,&r_max<0. cases (138) Therefore: r(st,at) r(s_t,a_t) +infPtT∈tT(∑st+1∈^PtT(st+1|st,at)⋅V^t+1,rectπU,P^t+1T,ℛℬ(ht+1) + _P^T_t ^T_t ( _s_t+1∈ SP^T_t(s_t+1|s_t,a_t)· V_t+1,rect^π^U, P_t+1^T,URDB(h_t+1) OPEN+rmax(H−1−t−∑st+1∈^PtT(st+1|st,at)⋅[1+δt+1πU(st+1|ht+1)]))= +r_max (H-1-t-\!\!\! _s_t+1∈ S\!\!P^T_t(s_t+1|s_t,a_t)· [1+ _t+1^π^U(s_t+1|h_t+1) ]\! ) )= (139) r(st,at) r(s_t,a_t) +infPtT∈tT(∑st+1∈^PtT(st+1|st,at)⋅V^t+1,rectπU,P^t+1T,ℛℬ(ht+1)+t,rectπU,PtT(ht,at))= + _P^T_t ^T_t ( _s_t+1∈ SP^T_t(s_t+1|s_t,a_t)· V_t+1,rect^π^U, P_t+1^T,URDB(h_t+1)+U_t,rect^π^U,P^T_t(h_t,a_t) )= (140) Using Lemma 3 together with the restriction map ℛtTR^T_t from 25, that project the full uncertainty set onto the projected uncertainty set, we get the following equalities: r(st,at)+infPtT∈tT(^st+1|htℛT(PtT)[V^t+1,rectπU,P^t+1T,ℛℬ(ht+1)]+t,rectπU,ℛT(PtT)(ht,at))= r(s_t,a_t)+ _P^T_t ^T_t ( E_s_t+1|h_t^R^T (P^T_t ) [ V_t+1,rect^π^U, P_t+1^T,URDB(h_t+1) ]+U_t,rect^π^U,R^T (P^T_t )(h_t,a_t) )= (141) r(st,at)+infP^tT∈^tT(^st+1|htP^tT[V^t+1,rectπU,P^t+1T,ℛℬ(ht+1)]+t,rectπU,P^tT(ht,at))≜ r(s_t,a_t)+ _ P^T_t∈ P^T_t ( E_s_t+1|h_t P^T_t [ V_t+1,rect^π^U, P_t+1^T,URDB(h_t+1) ]+U_t,rect^π^U, P^T_t(h_t,a_t) ) (142) ℛℬtπU(ht,at), _t^π^U(h_t,a_t), (143) which proves the upper bound. The lower bound follows the same proof structure, with the following modifications: 1. Replace ℛℬURDB with ℒℛℬLRDB. 2. Replace t+1U_t+1 with ℒt+1L_t+1. 3. Replace πUπ^U with πLπ^L. 4. Replace rmaxr_max with rminr_min. 5. Change the inequality directions. 6. Analogue justification to the transition after (137): δt+1πL≥δt+1πL,P^t+1T,ℒℛℬ,rmin≥0,δt+1πL≤δt+1πL,P^t+1T,ℒℛℬ,rmin<0. cases _t+1^π^L≥ _t+1^π^L, P_t+1^T,LRDB,&r_min≥ 0,\\[10.00002pt] _t+1^π^L≤ _t+1^π^L, P_t+1^T,LRDB,&r_min<0. cases (144) ∎ A.9 Proof of Corollary 3 (Asymptotic optimality) Corollary 3 (restated) (Asymptotic optimality). As the sampled state support expands to the full state space at every node, ^(hk−)↑,k=t,…,H, S(h_k^-) S,\ k=t,…,H, both deterministic bounds converge to the optimal rectangular robust value: ℒℛℬtπL(ht,πtL(ht)) _t^π^L (h_t, _t^L(h_t) ) ⟶Vt,rect∗,rob(ht), V_t,rect^*,rob(h_t), (145) ℛℬtπU(ht,πtU(ht)) _t^π^U (h_t, _t^U(h_t) ) ⟶Vt,rect∗,rob(ht). V_t,rect^*,rob(h_t). (146) Proof. We define the following expressions, essential for the proof: ϵ≜maxsupπk,ak,hk,P^kT∈^kTk∈[t,H−1]max|k,rectπ,P^kT(hk,ak)|,|ℒk,rectπ,P^kT(hk,ak)| ε _k∈[t,H-1] _ subarrayc _k,a_k,h_k,\\ P^T_k∈ P^T_k subarray \ |U_k,rect^π, P^T_k(h_k,a_k) |, |L_k,rect^π, P^T_k(h_k,a_k) | \ (147) Gk≜suphk|ℛℬkπU(hk)−ℒℛℬkπL(hk)|,k∈[t,H−1] G_k _h_k |URDB_k^π^U(h_k)-LRDB_k^π^L(h_k) |, k∈[t,H-1] (148) We will show the following for the proof: 1. Gt≤4⋅(H−1−t)⋅ϵG_t≤ 4·(H-1-t)·ε 2. ϵ→^→0ε subarrayc S→S subarray0 3. Vt,rect∗,rob(ht)∈[ℒℛℬtπL(ht),ℛℬtπU(ht)]V_t,rect^*,rob(h_t)∈[LRDB_t^π^L(h_t),URDB_t^π^U(h_t)], and by claim 1 and 2 Gt→^→0G_t subarrayc S→S subarray0, which proves the corollary. Step 1: base case GH−1=0G_H-1=0 by equations 114. For some k∈[t,H−2]k∈[t,H-2]: |ℛℬkπU(hk)−ℒℛℬkπL(hk)|≤maxak|ℛℬkπU(hk,ak)−ℒℛℬkπL(hk,ak)| |URDB_k^π^U(h_k)-LRDB_k^π^L(h_k) |≤ _a_k |URDB_k^π^U(h_k,a_k)-LRDB_k^π^L(h_k,a_k) | (149) we continue with arbitrary aka_k for now: maxak|infP^kT∈^kT(^sk|hkP^kT[V^k+1,rectπU,P^k+1T,ℛℬ(hk+1)]+k,rectπU,P^kT(hk,ak)) _a_k | _ P^T_k∈ P^T_k ( E_s_k|h_k P^T_k\! [ V_k+1,rect^π^U, P_k+1^T,URDB(h_k+1) ]+U_k,rect^π^U, P^T_k(h_k,a_k) ) −infP^kT∈^kT(^sk|hkP^kT[V^k+1,rectπL,P^k+1T,ℒℛℬ(hk+1)]+ℒk,rectπL,P^kT(hk,ak))|≤ - _ P^T_k∈ P^T_k ( E_s_k|h_k P^T_k\! [ V_k+1,rect^π^L, P_k+1^T,LRDB(h_k+1) ]+L_k,rect^π^L, P^T_k(h_k,a_k) ) |≤ (150) maxaksupP^kT∈^kT|(^sk|hkP^kT[V^k+1,rectπU,P^k+1T,ℛℬ(hk+1)]+k,rectπU,P^kT(hk,ak) _a_k _ P^T_k∈ P^T_k | ( E_s_k|h_k P^T_k\! [ V_k+1,rect^π^U, P_k+1^T,URDB(h_k+1) ]+U_k,rect^π^U, P^T_k(h_k,a_k) OPEN−^sk|hkP^kT[V^k+1,rectπL,P^k+1T,ℒℛℬ(hk+1)]+ℒk,rectπL,P^kT(hk,ak))|≤ - E_s_k|h_k P^T_k\! [ V_k+1,rect^π^L, P_k+1^T,LRDB(h_k+1) ]+L_k,rect^π^L, P^T_k(h_k,a_k) ) |≤ (151) using linearity of expectation, and definition of (147): supP^kT∈^kT|(^sk|hkP^kT[V^k+1,rectπU,P^k+1T,ℛℬ(hk+1)−V^k+1,rectπL,P^k+1T,ℒℛℬ(hk+1)])|+2ϵ≤ _ P^T_k∈ P^T_k | ( E_s_k|h_k P^T_k\! [ V_k+1,rect^π^U, P_k+1^T,URDB(h_k+1)- V_k+1,rect^π^L, P_k+1^T,LRDB(h_k+1) ] ) |+2ε≤ (152) Using equations 102, 104, and we also get rid of the supsup: |(ℛℬk+1πU(hk+1)−k+1,rectπU,P^k+1T,ℛℬ(hk+1,πk+1))−(ℒℛℬk+1πL(hk+1) | (URDB_k+1^π^U(h_k+1)-U_k+1,rect^π^U, P_k+1^T,URDB(h_k+1, _k+1) )- (LRDB_k+1^π^L(h_k+1) OPEN−ℒk+1,rectπL,P^k+1T,ℒℛℬ(hk+1,πk+1))|+2ϵ≤ -L_k+1,rect^π^L, P_k+1^T,LRDB(h_k+1, _k+1) ) |+2ε≤ (153) |ℛℬk+1πU(hk+1)−ℒℛℬk+1πL(hk+1)|+4ϵ≤ |URDB_k+1^π^U(h_k+1)-LRDB_k+1^π^L(h_k+1) |+4ε≤ (154) suphk+1 _h_k+1 |ℛℬk+1πU(hk+1)−ℒℛℬk+1πL(hk+1)|+4ϵ= |URDB_k+1^π^U(h_k+1)-LRDB_k+1^π^L(h_k+1) |+4ε= (155) Gk+1+4ϵ. G_k+1+4ε. (156) Unrolling H−1H-1 times from GH−1G_H-1 gives: Gt≤4⋅(H−1−t)⋅ϵ G_t≤ 4·(H-1-t)·ε (157) Step 2: Restating the rectangular upper and lower bounds (61) in theorem 1, with the fixed model version: k,rectπ,P^kT(hk)≜rmax(H−1−k−δkπ,P^kT(sk|hk)) _k,rect^π, P^T_k(h_k) r_max (H-1-k- _k^π, P^T_k(s_k|h_k) ) (158) ℒk,rectπ,P^kT(hk)≜rmin(H−1−k−δkπ,P^kT(sk|hk)) _k,rect^π, P^T_k(h_k) r_min (H-1-k- _k^π, P^T_k(s_k|h_k) ) (159) δkπ,P^kT(sk|hk)=∑sk+1∈^(hk+1−)P^kT(sk+1∣sk,πk(hk))[1+δk+1π(sk+1)] _k^π, P^T_k(s_k|h_k)= _s_k+1∈ S(h_k+1^-) P^T_k (s_k+1 s_k, _k(h_k) )\, [1+ _k+1^π(s_k+1) ] (160) δH−1π,P^kT(sH−1)≡0 _H-1^π, P^T_k(s_H-1)≡ 0 (161) As the sampled state support increases: ∑sk:H−1∈^(hH−1−)∏i=kH−1PiT(si+1∣si,πi(hi))→^→1, _s_k:H-1∈ S(h_H-1^-) _i=k^H-1P^T_i (s_i+1 s_i, _i(h_i) ) subarrayc S→S subarray1, (162) therefore: δkπ,P^kT(sk|hk)→^→H−1−k, _k^π, P^T_k(s_k|h_k) subarrayc S→S subarrayH-1-k, (163) which induces: k,rectπ,P^kT(hk)→^→0, _k,rect^π, P^T_k(h_k) subarrayc S→S subarray0, (164) ℒk,rectπ,P^kT(hk)→^→0. _k,rect^π, P^T_k(h_k) subarrayc S→S subarray0. (165) Therefore: ϵ→^→0ε subarrayc S→S subarray0 Step 3: 0≤ℛℬtπU(ht)−Vt,rect∗,rob(ht)≤Gt, 0 _t^π^U(h_t)-V_t,rect^*,rob(h_t)≤ G_t, (166) 0≤Vt,rect∗,rob(ht)−ℒℛℬtπL(ht)≤Gt, 0≤ V_t,rect^*,rob(h_t)-LRDB_t^π^L(h_t)≤ G_t, (167) we have shown that Gt→^→0G_t subarrayc S→S subarray0, which then concludes the proof. ∎ Appendix B Robust Backup under TV Uncertainty For the TV uncertainty sets used in our experiments, the inner optimization in (19), (20), can be solved directly on the sampled successor support. Let p̊out=1−∑s′∈^(h,a)P̊T(s′∣s,a) p_out=1- _s ∈ S(h,a) P^T(s s,a) denote the nominal probability mass outside the currently sampled support. Since projection restricts the transition row without renormalization, all unsampled successors can be represented by a single aggregate outside state. Consequently, the projected uncertainty set is equivalently represented by a TV ball over the |^(h,a)|+1| S(h,a)|+1 dimensional vector consisting of the sampled successor probabilities and the aggregate outside mass. The aggregate outside state represents the omitted probability mass, with its contribution determined by the corresponding projected backup. The resulting inner problem is a linear optimization over a TV ball. We solve it by the standard mass-transfer procedure: probability mass of at most ρ is shifted from successors with the largest continuation values toward those with the smallest values, subject to the simplex constraints. Sorting the continuation values gives a per-backup complexity of O(|^(h,a)|log|^(h,a)|)O(| S(h,a)| | S(h,a)|) and O(|^(h,a)|)O(| S(h,a)|) memory. Thus, the robust backup depends on the currently sampled successor support rather than on the cardinality of the full state space. Appendix C Experiments C.1 Frozen Lake Domain We evaluate the planners on a family of Frozen Lake domains represented by two-dimensional grids containing traversable frozen cells, terminal holes, a start cell, and a goal cell. Each grid cell corresponds to an MDP state, and we additionally introduce an absorbing terminal state sdones_done. The action space is =left,down,right,upA=\ left, down, right, up\, corresponding to the four cardinal movement directions. Reaching either a hole or the goal terminates the episode, after which the process transitions to sdones_done. The objective is to reach the goal while avoiding holes. Different experiments vary the grid size, obstacle layout, start and goal locations, and planning horizon; their specific configurations are summarized in Section C.6. Figure 4: Frozen Lake Map Example C.2 Ring Transition Model The standard Frozen Lake dynamics have a small successor support. To evaluate planning with substantially larger transition supports, we use a stochastic ring transition model. For a state s, let ℛd(s)=s′:∥s′−s∥∞=d,d=1,…,k,R_d(s)= \s :\|s -s\|_∞=d \, d=1,…,k, denote the Chebyshev ring of radius d around s. For an interior state, ℛd(s)R_d(s) contains 8d8d cells. Under action a, the intended neighboring cell receives probability 1−pslip1-p_slip. The remaining probability pslipp_slip is distributed over the k rings. The fraction assigned to ring d is qd=βd−1∑ℓ=1kβℓ−1,q_d= β^d-1 _ =1^kβ -1, and this mass is distributed uniformly among the 8d8d cells in that ring. Thus, for an interior state, each cell in ring d receives slip probability pslipqd8d.p_slip q_d8d. The intended successor is itself contained in the first ring and therefore receives both its ring contribution and the additional 1−pslip1-p_slip intended-transition probability. Near the grid boundary, ring locations falling outside the grid are clipped to the nearest valid cell, and probability masses mapping to the same cell are accumulated. Holes block transitions: if a transition crosses an adjacent hole, the transition is redirected to that hole, which terminates the episode. Figure 5: Illustration of the ring transition model used in the Frozen Lake experiments. C.3 Transition Uncertainty Model To account for model uncertainty, we construct a rectangular uncertainty set independently around each nominal transition row. Specifically, for every state-action pair (s,a)(s,a), T(s,a)=PT(⋅∣s,a):TV(PT(⋅∣s,a),P̊T(⋅∣s,a))≤ρ,P^T(s,a)= \P^T(· s,a):TV\! (P^T(· s,a), P^T(· s,a) )≤ρ \, (168) where ρ is the uncertainty radius and TV(p,q)=12‖p−q‖1.TV(p,q)= 12\|p-q\|_1. The uncertainty set preserves the support of the nominal transition model: states assigned zero probability by P̊T(⋅∣s,a) P^T(· s,a) cannot receive probability mass under an admissible model. Thus, robustness accounts for uncertainty in the transition probabilities over the ring-kernel support without introducing additional successor states. In experiments involving model mismatch, the environment is executed using a slip probability ptruep_true, whereas the planner constructs its nominal model using pslipp_slip. The uncertainty radius ρ is chosen to contain the true model within the corresponding TV uncertainty set. The exact values used in each experiment are reported in Section C.6. C.4 Reward Model We use two distance-based reward models across the experiments. Inverse-Manhattan reward. For the main planner comparison and Ablations 1–2, we use the distance-shaped reward of Shazman et al. Shazman et al. (2026). For a nonterminal free cell s, let m(s)m(s) denote its Manhattan distance to the goal, computed directly on the grid without treating holes as obstacles: rIM(s)=w(11+m(s))p.r_IM(s)=w ( 11+m(s) )^p. (169) We use w=0.1w=0.1 and p=3p=3, with goal reward 33 and rewards 00 for holes and sdones_done. The cubic inverse-distance shaping decays rapidly away from the goal, so most free cells receive only a small intermediate reward and the task remains predominantly driven by reaching the terminal goal. Positive-distance reward. For several experiments we instead use the shortest-path distance d(s)d(s) from s to the goal, computed while routing around holes. Let dmaxd_ be the largest such distance on the map and define c(s)=dmax−d(s)dmax∈[0,1].c(s)= d_ -d(s)d_ ∈[0,1]. The positive-distance reward is r+(s)=wdmaxc(s)p.r_+(s)=wd_ c(s)^p. Thus, free-cell rewards increase as the agent approaches the goal, with the distance computed according to the traversable structure of the map rather than directly through holes. Goal and hole rewards are specified separately and override the shaping value, while r(sdone)=0r(s_done)=0. When a fixed reward span is used, we set w=span/dmaxw=span/d_ , making the free-cell reward range independent of the map diameter. The specific reward model and parameters used by each experiment are summarized in Section C.6. C.5 Planning Protocol All online planning experiments use a receding-horizon protocol. At each environment step, the planner constructs a finite search tree of depth H rooted at the current state and performs planning using its available computation budget. The selected root action is then executed in the environment, the resulting next state is observed, and a new depth-H planning problem is initialized from that state. Thus, H denotes the planner’s lookahead horizon rather than the episode length. For model-mismatch experiments, planning is performed using the nominal transition model P̊T P^T parameterized by pslipp_slip, whereas executed transitions are sampled from the environment model parameterized by ptruep_true. Episodes terminate upon reaching either the goal or a hole. C.6 Experiment Configurations Table 1 summarizes the parameters used in the main experiments. Unless stated otherwise, all experiments use the domain, transition kernel, uncertainty model, and planning protocol described above. Table 1: Configuration of the experiments reported in the main paper. Parameter Fig. 1a Fig. 1b Fig. 2 Fig. 3 Grid 8×88× 8 8×88× 8 16×1616× 16 (10×10)(10× 10)–(103×103)(10^3× 10^3) H 66 33 2,5,11\2,5,11\ 55 k 11 22 88 n−12 n-12 β 11 11 11 0.390.39–0.990.99 pslipp_slip 0.30.3 0.20.2 0.010.01–0.60.6 0.30.3 ptruep_true – – 0.050.05 – ρ 0.10.1 0.10.1 0.040.04–0.540.54 0.10.1 Budget – varied 2020–200200 8080 Runs 5050 2020 2020 55 Reward r+r_+ r+r_+ rIMr_IM r+r_+ Figure 1a uses r+r_+ with goal reward 11, hole reward −1-1, span=1span=1, and p=0.5p=0.5; Figure 1b uses the same specification with p=1p=1. Figure 2 uses rIMr_IM with goal reward 33, hole reward 00, w=0.1w=0.1, and p=3p=3. Figure 3 uses r+r_+ with goal reward 11, hole reward 00, and p=1p=1. C.6.1 Ablation 1: Robustness to Environment Slipperiness and Model Mismatch We first examine how planner performance changes as the true environment becomes increasingly slippery, and how this interacts with model mismatch. We fix the planning depth to 33 and use the 16×1616× 16 Frozen Lake domain. For the main experiment, the ring radius is k=8k=8 with β=1β=1. We vary the true environment slip probability as ptrue∈0.01,0.1,0.2,0.3p_true∈\0.01,0.1,0.2,0.3\, corresponding to the four columns of Figure 6. Within each column, ptruep_true is fixed while the planner-assumed slip probability pslipp_slip is varied from 0.010.01 to 0.60.6. Hence, moving across columns makes the true environment increasingly difficult, whereas moving along the x-axis changes the model assumed by the planner while leaving the true environment unchanged. For each pair, the TV uncertainty radius is set to the smallest value that contains the true transition model. Each configuration is evaluated over 500500 independent seeds. Figure 6: Success rate at planning depth 33 as the true environment becomes more slippery and the planner-assumed transition model varies. Columns correspond to ptrue∈0.01,0.1,0.2,0.3p_true∈\0.01,0.1,0.2,0.3\, while the x-axis shows the planner-assumed pslipp_slip. The ring radius is k=8k=8. 500500 seeds. As ptruep_true increases, success rates decrease for all methods, reflecting the increasing difficulty of controlling the agent when the true environment becomes more slippery. CAR-MCTS degrades substantially more gracefully than the baselines and achieves the highest or near-highest success rate across the tested environment difficulties. Importantly, this behavior persists as pslipp_slip moves away from ptruep_true: within each column the true environment is unchanged, yet CAR-MCTS remains comparatively stable over increasing mismatch between the planning and true environment models. The RSS variants are not restricted to the same sampling budget as the MCTS methods. CAR-MCTS, nominal UCT, and Robust Power UCT use 2020 simulations per decision, corresponding to 6060 transition samples at depth 33. In contrast, the recursive sparse-sampling expansion requires substantially more transition samples as C increases: Method Samples per decision Relative to MCTS MCTS methods 6060 1×1× RSS C=2C=2 584584 9.7×9.7× RSS C=3C=3 18841884 31.4×31.4× RSS C=4C=4 43684368 72.8×72.8× Table 2: Transition samples per decision at planning depth 33. Despite this substantially larger sampling budget, RSS remains consistently below CAR-MCTS across the tested configurations. With C=2C=2, RSS is often comparable to nominal UCT and in several configurations performs worse. Thus, although RSS explicitly performs robust planning, this does not translate into a consistent empirical robustness advantage over the nominal planner under the tested model mismatch. Increasing the branching factor to C=3C=3 or C=4C=4 generally improves RSS, but the gains are inconsistent; even with tens of times more transition samples, its success rate frequently remains close to that of nominal UCT. Effect of transition-support width. To test whether the behavior of RSS is primarily caused by the broad successor support of the k=8k=8 kernel, we repeat the same experiment with k=1k=1, while keeping the remaining settings unchanged, shown in Figure 7. Figure 7: The same experiment as Figure 6, with the ring radius reduced from k=8k=8 to k=1k=1. Reducing the ring radius substantially improves several competing methods, showing that their performance is sensitive to the number of feasible next states. In contrast, CAR-MCTS changes remarkably little between k=8k=8 and k=1k=1. This is an important strength of the proposed approach: CAR-MCTS maintains similar performance even when the transition support grows dramatically, whereas the competing sampling-based planners benefit substantially from the easier, narrower-support setting. RSS also improves in several configurations, but C=2C=2 remains frequently comparable to or worse than nominal UCT, while the larger-C variants still do not consistently outperform it. Hence, the behavior observed for RSS at k=8k=8 cannot be explained solely by insufficient sampling of a broad successor distribution. Overall, the ablation highlights three complementary strengths of CAR-MCTS. First, its performance degrades more gracefully as the true environment becomes increasingly slippery. Second, for a fixed true environment, it remains robust as the planner’s assumed transition model moves away from the true dynamics. Third, its performance is far less sensitive to the width of the transition support: increasing the number of feasible next states has only a limited effect on CAR-MCTS, while substantially degrading the competing methods. Together, these results show that CAR-MCTS remains effective under both model uncertainty and broad transition dynamics, without requiring the large increase in successor samples used by RSS. C.6.2 Ablation 2: Scalability with Planning Horizon We next isolate the effect of the planning horizon on online computation. All environment and planner parameters are held fixed while varying H∈1,…,10H∈\1,…,10\. Experiments use a 100×100100× 100 Frozen Lake domain with hole density 0.150.15, ring radius k=8k=8, and β=1β=1. The planner uses pslip=0.3p_slip=0.3, while the true execution dynamics use ptrue=0.1p_true=0.1, giving ρ=0.197ρ=0.197. CAR-MCTS and Robust Power UCT use 2020 MCTS simulations per decision, and results are averaged over 2020 independent seeds. Figure 8: Decision time as a function of planning depth. CAR-MCTS and Robust Power UCT use 2020 simulations per decision, while RSS uses branching factor C=2C=2. A 2020-second computation cap is imposed per decision; RSS reaches this limit at depth 66, and deeper configurations are therefore not evaluated. Figure 8 shows a clear difference in scalability with planning depth. CAR-MCTS remains within the tens-of-milliseconds regime throughout the entire sweep, with decision time increasing only gradually as the depth grows. Robust Power UCT similarly remains approximately constant over the tested range. In contrast, RSS is initially the fastest method at small depths, but its computational cost grows rapidly with each additional planning level, increasing from below 11 ms at depth 11 to more than 200200 ms at depth 55. We impose a 2020-second computation cap per decision; at depth 66, RSS reaches this limit before completing the planning step. Consequently, deeper RSS configurations are not evaluated. The difference stems from the underlying search structure. RSS recursively samples C successor states for every action at each level of the tree, so its computational cost grows rapidly with depth. In contrast, CAR-MCTS uses a fixed simulation budget: increasing the planning depth lengthens the sampled trajectories and their backups, but does not require recursively expanding all sampled successor combinations. Consequently, CAR-MCTS supports substantially deeper lookahead while retaining practical online decision times. C.6.3 Ablation 3: True Optimal-Action Selection Finally, we evaluate the quality of the action selected by each planner directly, rather than through the stochastic outcome of an episode. For each planning problem, we compute the optimal action offline using the true transition model and measure the fraction of decisions in which each planner selects this action. Importantly, the true model is used only as an evaluation oracle and is not available to any of the planners. We use a 4×44× 4 Frozen Lake domain with ring radius k=1k=1, search depth 33, and 2020 simulations for the MCTS-based methods. RSS uses C=2C=2, and each configuration is evaluated over 100100 independent seeds. As in Ablation 11 C.6.1, the columns vary the true environment slip probability ptrue∈0.01,0.1,0.2,0.3p_true∈\0.01,0.1,0.2,0.3\, while the x-axis varies the planner-assumed pslipp_slip. Figure 9: Fraction of decisions selecting the action that is optimal under the true transition model. Columns correspond to different values of ptruep_true, while the x-axis varies the planner-assumed pslipp_slip. The true model is used only for evaluation. Figure 9 shows that CAR-MCTS selects the true optimal action more reliably than the competing planners over nearly the entire sweep. When the true environment is only mildly slippery, all methods perform well when the planning model is accurate, but their behavior diverges as the assumed model moves away from the true dynamics. CAR-MCTS degrades more gradually and maintains a substantially higher optimal-action selection rate under increasing model mismatch. The difference becomes particularly pronounced as the true environment itself becomes more slippery. For ptrue=0.2p_true=0.2 and 0.30.3, CAR-MCTS maintains a clear advantage over a broad range of pslipp_slip values, showing that it continues to identify the correct decision even when both the environment is more difficult and the planner model is inaccurate. Robust Power UCT generally improves over nominal UCT in parts of the sweep, but does not approach the consistency of CAR-MCTS. RSS with C=2C=2 is typically comparable to or below nominal UCT, indicating that its robust formulation does not translate into a consistent advantage in identifying the true optimal action under the tested planning budget. This experiment complements the episode-level results of Ablation 1 C.6.1. Higher success rates can in principle result partly from favorable stochastic transitions after an action is selected; here, the evaluation isolates the planning decision itself. The results therefore show that CAR-MCTS’s advantage is not limited to better realized outcomes: it more frequently selects the action that is optimal under the true environment dynamics. Together with the previous ablations, this demonstrates stronger decision quality under model mismatch, reduced sensitivity to broad transition support, and practical scalability with planning depth. C.6.4 Ablation 4: Certification and Pruning in Practice Finally, we examine how frequently the deterministic bounds used by CAR-MCTS lead to root-action certification and branch pruning in practice. We evaluate three grid sizes, 4×44× 4, 8×88× 8, and 16×1616× 16, while varying pslipp_slip and the planning budget over 100,200,500,1000\100,200,500,1000\ simulations. We report the fraction of decisions for which the root action is certified and the fraction of branches pruned during search. Figure 10: Root-action certification rate (top) and branch-pruning rate (bottom) for different grid sizes, planning budgets, and values of pslipp_slip. Figure 10 shows that root certification occurs frequently in practice and increases strongly with the available planning budget. Even with relatively small budgets of 100100–200200 simulations, CAR-MCTS certifies a substantial fraction of root decisions, with certification rates often around 50%50\% or higher depending on the configuration. As the budget increases, the deterministic intervals tighten further and the certification rate rises sharply. At 500500 and 10001000 simulations, CAR-MCTS certifies the root decision in nearly all runs over a large portion of the tested configurations. This demonstrates that the certificates are not only theoretical guarantees, but can become sufficiently tight during online planning to provide an effective early-stopping criterion. The lower row shows that the same bounds also eliminate a meaningful fraction of suboptimal branches during search. Interestingly, the measured pruning rate tends to decrease when certification becomes frequent. This is consistent with the two mechanisms playing complementary roles: while the root decision remains unresolved, continued sampling contracts the action-value bounds and enables dominated branches to be pruned; once the root action is certified, planning terminates and no further pruning is needed. Overall, the ablation shows that CAR-MCTS uses its deterministic certificates in two complementary ways to reduce online computation: locally, by pruning branches that can no longer contain the optimal action, and globally, by terminating planning once the root action is certified. The high certification rates achieved with larger simulation budgets show that both mechanisms are actively useful in practice rather than serving only as theoretical guarantees.