Conceptio › Archive › arXiv CS

arXiv CSopen access

Online Robust Reinforcement Learning Through Monte-Carlo Planning

· arxiv_cs

arXiv CS · Papers · License: Open Access

Open Source ↗Direct PDF ↓

neural-networks

machine learning, deep learning, neural networks

Online Robust Reinforcement Learning Through Monte-Carlo Planning

Tuan Dam * 1 Kishan Panaganti * 2 Brahim Driss * 3 Adam Wierman 2

arXiv:2609.18599v1 [cs.LG] 16 Sep 2026

Abstract

Search (MCTS) algorithm, in conjunction with deep learning methods, solve complex decision-making problems in high-dimensional environments. Its celebrated success stories include autonomous RL decision-making agents playing board games Chess, Go, Shogi (Silver et al., 2016; Schrittwieser et al., 2020), Poker (Brown and Sandholm, 2018; Keshavarzi and Navidi, 2025), and solving various real-world challenging tasks like robotics and autonomous systems (Hoel et al., 2019; Kartal et al., 2019; Dam et al., 2022). MCTS offers a principled way to balance exploration and exploitation by using combinatorial search mechanisms derived from online simulated trajectories. As a result, MCTS can effectively promote the exploration of promising regions of the environment with only partial modeling information of the environment.

Monte Carlo Tree Search (MCTS) is a powerful framework for solving complex decisionmaking problems, yet it often relies on the assumption that the simulator and the real-world dynamics are identical. Although this assumption helps achieve the success of MCTS in games like Chess, Go, and Shogi, the real-world scenarios incur ambiguity due to their modeling mismatches in low-fidelity simulators. In this work, we present a new robust variant of MCTS that mitigates dynamical model ambiguities. Our algorithm addresses transition dynamics and reward distribution ambiguities to bridge the gap between simulation-based planning and real-world deployment. We incorporate a robust power mean backup operator and carefully designed exploration bonuses to ensure finite-sample convergence at every node in the search tree. We show that our algorithm achieves a convergence rate of O(n−1/2 ) for the value estimation at the root node, comparable to that of standard MCTS. Finally, we provide empirical evidence that our method achieves robust performance in planning problems even under significant ambiguity in the underlying reward distribution and transition dynamics.

However, most of these successes are limited to structured or simulated environments. As successful as RL algorithms are, an issue in applying them to real-world dynamical systems is the unavoidable discrepancy between the simulators and the actual real-world system dynamics. In traditional RL approaches (Kaelbling et al., 1996; Salvato et al., 2021), transition models are often learned from data collected by interacting with simulator models to avoid unsafe interactions with real-world systems, and reward models may be subject to stochasticity, hacked rewards, or unmodeled external factors. Such ambiguities arise from a variety of sources: limited training data, non-stationary environments, adversarial conditions, partial observability, or simply modeling simplifications. These factors can lead to a so-called simulation-to-reality gap, where the policy or value function that appears optimal in the simulated environment may perform poorly when deployed in the real world. A natural approach to addressing these challenges is to incorporate robustness against simulation-to-reality gaps directly into the planning algorithm.

1. Introduction Reinforcement learning (RL) provides a statistical machine learning framework to interact with the environments—such as autonomous vehicles, agile robots, and network systems—sequentially and learn to take control actions to achieve the desired objective. Monte Carlo Tree

RL agents making decisions under the framework of Robust Markov Decision Processes (RMDPs) (Iyengar, 2005; Nilim and El Ghaoui, 2005) offer a principled mechanism to conceptualize robustness against transition model and reward model mismatches raised by simulation-to-reality gaps. These robust RL agents explore policies that maximize expected returns under the worst-case model within a prescribed ambiguity set. The ambiguity set is typically constructed as a ball around the simulator dynamics or re-

Equal contribution 1 Hanoi University of Science and Technology, Hanoi, Vietnam 2 Department of Computing and Mathematical Sciences, California Insitute of Technology Pasadena, CA, USA 3 Univ. Lille, Inria, CNRS, Centrale Lille, UMR 9189-CRIStAL. Correspondence to: Tuan Dam <[email protected]>. Proceedings of the 42 nd International Conference on Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

Online Robust Reinforcement Learning Through Monte-Carlo Planning

ward model, with the design choice of the ball size covering the real-world ground truth model descriptors. Recent works demonstrate their potential to achieve robust decision-making performance when faced with perturbations in transition dynamics and reward function models. However, while value iteration and policy optimization methods have been introduced and analyzed for robust RL, MCTS-based planning algorithms have not been explored, as per the authors’ knowledge. We discuss more detailed related works in Section 2.

for standard, non-robust MCTS, thereby demonstrating that introducing robustness need not change the convergence speed in terms of the number of samples.

Contributions. In this work, to the best of our knowledge, we are the first to propose an MCTS-based algorithm for the robust RL problem. Our contributions are threefold: • Robust MCTS Algorithm: We solve the online robust RL problem–accounting for model ambiguity in both transitions and rewards–using a planning algorithm enabled by MCTS. This fundamental first step paves the way for future applications in large-scale dynamical systems. • Non-Asymptotic Guarantees: We provide rigorous finitesample performance bounds, ensuring that the robust MCTS converges with a known rate, on par with standard MCTS. Our analysis leads to novel exploration bonuses that arise from careful analyses of robust backup operators and the tree search mechanism by recasting robust MCTS for different ambiguity sets as a collection of nonstationary multi-armed bandit problems. • Robust Empirical Performance: We conduct experiments in two environments (Gambler’s Problem and Frozen Lake) to evaluate our robust algorithm, demonstrating that it achieves superior robust performance to model mismatches than the standard MCTS algorithm baseline.

In this work, we propose a novel robust MCTS algorithm equipped with non-asymptotic performance guarantees under model ambiguity set. Importantly, we incorporate both reward and transition ambiguity robustness, similar to recent works (Zhou et al., 2021; Wang et al., 2024b) in robust RL. In particular, our work resolves the following questions: Can we use a search-based planning approach like MCTS to balance exploitation and exploration for the robust RL problem? What theoretical guarantee can we provide? Can we show robust performance against standard algorithms under the simulation-to-reality issue? Our approach embeds the distributionally robust optimization (Rahimian and Mehrotra, 2019) mathematical principle into the MCTS framework, ensuring that the value estimates and action selections are robust to transitions and rewards drawn from the ambiguity sets. More precisely, we conceptualize a robust backup operator and design exploration bonuses that accommodate ambiguity sets defined using total variation, Kullback-Leibler, chi-squared, or Wasserstein measures. This allows MCTS to simultaneously use a tree search mechanism to solve for robust value estimates by trading off exploitation and exploration while achieving robust policies that work uniformly well across different models in the ambiguity set.

2. Related Works Robust RL. Robust RL agents make decisions to alleviate environmental ambiguities under the RMDP framework introduced by Iyengar (2005); Nilim and El Ghaoui (2005) considers distributional robust optimization (Rahimian and Mehrotra, 2019) mathematical formularization. Many recent works extensively study the robust RL problem, addressing multiple aspects of the challenges of decisionmaking learning algorithms. Panaganti and Kalathil (2021); Zhou et al. (2021); Panaganti and Kalathil (2022); Shi and Chi (2024) propose model-based dynamic programming algorithms to solve the robust RL problem for finite state-action environments, and Dong et al. (2022); Panaganti et al. (2025) extend to the online and offline settings, respectively. These works focus on addressing the sample complexity—minimal samples needed from the simulator model (leading to the construction of an approximate model) for every state-action pair to obtain an approximate value estimation—issue. Panaganti and Kalathil (2021); Panaganti et al. (2022); Zhang et al. (2023) propose modelfree value function approximation-based robust RL algorithms utilizing special structures in the Bellman backups arising due to specific forms of ambiguity sets. Different from these approaches, our algorithm is inspired by MCTS to solve the robust RL problem. MCTS scales well (Silver et al., 2016) for large problems by embedding strong search

One of the key contributions of this work is the establishment of finite-sample bounds on the convergence rates of our robust MCTS algorithm. Viewing each node in the MCTS tree as a non-stationary bandit problem sheds light on the nontrivial challenges of controlling the interaction between ambiguity sets and exploration bonuses. More specifically, coming up with exploration bonuses (thereby robust value approximations) is nontrivial based on the non-linear backup operator due to the formalization of robustness. We overcome these challenges by building on a sequence of technical lemmas and applying concentration inequalities to the robust backup operator, we show that our method attains a convergence rate of order O(n−1/2 ) for robust value estimation at the root node, where n is the number of states visited while exploring the environment. This convergence rate also matches the best-known results 2

Online Robust Reinforcement Learning Through Monte-Carlo Planning

mechanisms into model-based planning approaches in RL.

to high-dimensional dynamical systems (Panaganti et al., 2022; Zhang et al., 2023; Panaganti et al., 2024; Liu and Xu, 2024). The incorporation of the strong sampling procedure by MCTS avoids this issue.

MCTS for non-robust RL. AlphaGo-like (Silver et al., 2016) agents are powered by tree search mechanisms such as MCTS in traditional dynamic programming planning for standard RL. Kocsis and Szepesvári (2006); Shah et al. (2020); Dam et al. (2024b) provide theoretical guarantees for such heuristic search-based deep RL algorithms. Recently, the adoption of MCTS (Świechowski et al., 2023) in other learning settings has seen scaling advantages. For instance, in non-standard RL settings, like supervised learning systems (Guez et al., 2018; Wang et al., 2024a), constrained dynamical systems (Parthasarathy et al., 2023; Kurečka et al., 2024) to promote safe decision-making choices, and partially observable and constrained dynamical systems (Lee et al., 2018; Dam et al., 2022; 2020). In bandits, like agents taking decisions in the space of contexts (Ontanón, 2013; Mao et al., 2020). In applications, like autonomous vehicles and robots, (Kartal et al., 2019; Yin et al., 2022) where the imitation of expert decisions plays a critical role. Alternative approaches include entropy regularization methods like MENTS (Xiao et al., 2019), RENTS and TENTS (Dam et al., 2021; 2024a), and Boltzmann-based approaches (Painter et al., 2023), though these rely on temperature parameters that may impede convergence to true optimal values. Inspired by such adoption of MCTS, we enable MCTS-based planning for the first time to the robust RL problem—equipped with theoretical guarantees—that accounts for mitigating dynamical model ambiguities.

3. Preliminaries A Markov Decision Process (MDP) specified by the tuple (S, A, P, R), where S ⊂ Rd is the (potentially large) state space, A is a discrete action space, P : S × A → ∆(S) is the transition model mapping each state–action pair to a probability distribution over next states, and R : S × A → R is the (possibly uncertain) reward function assumed to be supported on a bounded interval [0, Rmax ]. A stationary policy π ∈ Π(M) is defined as π : S → ∆(A), meaning that at each discrete time step t, the agent observes a state st , samples an action at ∼ π(· | st ), collects a reward rt ∼ R(· | st , at ), and transitions to st+1 ∼ P (· | st , at ). We mention detailed notations used in this work in Table 3. 3.1. Value Functions and Policies We adopt a discounted formulation with discount factor γ ∈ (0, 1). The state-value and state–action value functions of a policy π are given by π VP,R (s) =

QπP,R (s, a) =

P∞

t=0 Eat ∼π

t γ rt s0 = s ,

(1)

t γ rt s0 = s, a0 = a . (2)

⋆ The optimal state-value function is defined as VP,R (s) = π supπ VP,R (s). By definition and existence of deterministic optimal actions, the optimal state–action value function Q∗ ⋆ (s) = maxa Q⋆P,R (s, a) for each s ∈ S. satisfies VP,R

Search-based planning for online robust RL. This line of research is closest to ours in terms of search-inspired algorithms. (Liu et al., 2022; Wang et al., 2023; Wang, 2024) introduces the Multi-Level Monte Carlo (MLMC) method (Heinrich, 2001; Giles, 2008) to approximate the robust Bellman backups. MLMC is another powerful statistical sampling method from the family of Monte Carlo estimators. However, they have the drawback of requiring random sampling procedures in each iteration of the robust RL planning stages for every state-action pair. By avoiding these pitfalls, MCTS adapts to the online sampling procedure by enabling search from a tree node—states and actions in dynamical systems—up to some constant depth in the tree. Other works introduce sampling-based Q-learning (Zhou et al., 2021; Liu et al., 2022; Wang et al., 2024b) and policy iteration (Panaganti and Kalathil, 2021; Kumar et al., 2023; Badrinath, 2023) inspired approaches. These are popular methods in standard online RL enabling trajectory-based updates—at current states, actions, and next states sampled with an updated policy—to approximate the Bellman backups. However, these require algorithmic and theoretical innovations–for e.g., function approximation architectures–for scaling up

3.2. Conceptualization of Robustness A key challenge in real-world RL is that both transitions P and rewards R may be partially unknown or even timevarying. Let P o and ν o denote the nominal transition probabilities and reward distributions, respectively, with each o reward r(s, a) ∼ νs,a . These nominal models can be either factory-set approximations or a simulator of real-world systems. Following Wang et al. (2024b); Zhou et al. (2021); Liu et al. (2022), we allow the environment to deviate from P o , ν o within a robustness budget ρT , ρR respectively. This leads to a robust MDP that accounts for uncertainties in both transitions and rewards. Ambiguity NSets. We model transitions in an ambiguity set P = (s,a) Ps,a , where each Ps,a contains all plausible distributions over next N states from (s, a). Analogously, an ambiguity set R = (s,a) Rs,a captures deviations in the reward distributions r(s, a). Here, with a chosen metric 3

Online Robust Reinforcement Learning Through Monte-Carlo Planning rob where Rs,a = minrs,a ∈Rs,a ER∼rs,a [R], and σPs,a (V ) captures the worst-case expected reward at (s, a) and value of V over Ps,a , converges to optimal robust value functions V ∗ and Q∗ respectively.

D(·, ·), n o o Ps,a = Ps,a ∈ ∆(S) : D Ps,a , Ps,a ≤ ρT , and

MCTS in a Robust MDP. In Monte Carlo Tree Search, we approximate a γ-discounted solution by simulating trajectories down a growing search tree. Each node corresponds to a state sh , with h indicating the depth in the tree (distance from the root). From sh , the algorithm either expands a child node for the next state sh+1 or performs a rollout using a simpler policy π0 if h reaches the maximum search depth H. Trajectories terminate upon reaching depth H or a terminal state.

n o o Rs,a = νs,a : D νs,a , νs,a ≤ ρR . Different choices of D lead to distinct ambiguity sets, such as total-variation balls (P TV ), chi-squared neighborhoods (P X ), or Wasserstein sets (P W ). For notational convenience, we denote the reward distributions νs,a ∈ Rs,a also as their probability densities in the context of measur ing distances D ·, · .

4. Main Problem Formulation

Performance Measure. A canonical metric for MCTS algorithms is the convergence rate r(t), where t indexes the number of simulated trajectories (rollouts). Informally, r(t) bounds how quickly the MCTS estimates approach the true optimal values at the root node.For instance, one may require that E V ⋆ (s0 ) − Q⋆ (s0 , b at ) ≤ r(t), or ⋆ E V (s0 ) − Vbt (s0 ) ≤ r(t),

This section establishes how Monte Carlo Tree Search (MCTS) can be adapted to account for model ambiguity in a robust Markov Decision Process (MDP). Our goal is twofold: first, to clarify the root assumptions behind the robust planning framework, and second, to describe how MCTS is modified so that each node’s value estimate incorporates worst-case rewards and transitions.

where b at is the action chosen at the root after t rollouts, and Vbt (s0 ) approximates V ⋆ (s0 ).

Robust MDP. We consider a robust MDP M = (S, A, P, R) in which the state space S may be large or partially continuous, the action space A is discrete, and the unknown reward r(s, a) and transition model P(· | s, a) can lie within an ambiguity set R and P (described in Section 3). At each step t, the agent observes a state st , selects an action at ∈ A, receives reward rt , and transitions to a new state st+1 . The robust state-value and state-action value functions of a polπ (s) and icy π are given by V π (s) = minP ∈P,R∈R VP,R π π Q (s, a) = minP ∈P,R∈R QP,R (s, a) respectively. A policy π ⋆ that maximizes the value function is an optimal robust policy with corresponding optimal robust value functions V ⋆ (s) and Q⋆ (s, a). Hence, both transitions and rewards may be adversarially perturbed, ensuring the agent plans robustly for worst-case scenarios within these sets.

Recursive Value Estimation Under Ambiguity. To capture the robust (worst-case) aspect of the MDP, we define a recursive estimation scheme at each node that accounts for inf r(s,a)∈Rs,a of reward and inf P ∈Ps,a transitions. Let sh be a node at depth h. We assign a robust value Ve (sh ) and e h , a) such that a robust action-value Q(s rob e h , a) = Rs,a Q(s + γ σPsh ,a Ve , e h , a). Ve (sh ) = max Q(s a∈A

At a leaf node (h = H), we approximate the value with a simple rollout policy π0 , yielding Ve (sH ) ≈ Vπ0 (sH ). Goal of MCTS. Since finite sample sizes introduce noise, each node’s robust value Ve (sh ) is estimated from rollouts. The ultimate objective is to identify an action a⋆ = arg maxa Q⋆ (s0 , a) at the root state s0 within n simulated trajectories, where Q⋆ (s0 , a) represents the robustoptimal action value. Intuitively, we want:

Robust Bellman Operator. In the robust MDP, the worst-case expected value arises from an adversarial choice of both transition and reward distributions within their respective ambiguity sets. From the robust MDP literature (Iyengar, 2005; Liu et al., 2022), by the construction of P and R ambiguity sets, Q⋆ is known to be computable, and thereby π ⋆ (s) = argmaxa∈A Q⋆ (s, a).

e 0 , a), b an ≈ arg max Q(s a

Vbn (s0 ) ≈ Ve (s0 ),

with small statistical error. In Section 5, we describe how Robust-Power-UCT achieves this via specially designed backup operators and action-selection rules. Section 6 establishes finite-sample guarantees, showing that robustness in MCTS need not degrade convergence speed compared to its non-robust counterpart.

Let us define for any set B and a vector v, σB (v) = inf{uT v : u ∈ B}. Robust dynamic programming, given by Vk+1 (s) = maxa ∈ A Qk+1 (s, a) and rob Qk+1 (s, a) = Rs,a + γ σPs,a (Vk ),

Online Robust Reinforcement Learning Through Monte-Carlo Planning

5. Algorithm Description

b t (sh , a) Specifically, we maintain an empirical estimate Q for each action and add an exploration bonus of the form:

We now describe the core parts of our Robust-Power-UCT algorithm, focusing on the value backup and action selection strategies. Other details, such as the main loop and rollout procedure, are standard MCTS routines and hence only briefly mentioned.

bh+1 Tsh (t) βh+1 C· αh+1 , Tsh ,a (t) βh+1 where Tsh (t) is the total number of visits to sh up to time t, and Tsh ,a (t) is how often action a has been taken from h+1 and αβh+1 control how aggressively sh . The exponents βbh+1 h+1 the algorithm explores, while C is a user-chosen constant. At the end of training (greedy mode), the action with the b t is chosen. highest Q

Table 1: Key Conditions for Algorithmic Constants (i ∈ [0, H]) Cond.

Requirement

(1)

(4)

bi < αi and bi > 2.  βi  1 ≤ p ≤ 2 and αi ≤ 2 , or   p > 2 and αi ≤ β2i , 0 < αi − βpi < 1 αi 1 − αbii ≤ bi < αi . αi = (bi+1 − 1) 1 − αbi+1 . i+1

(5)

βi = (bi+1 − 1).

(2) (3)

Main Loop and Rollout. As in standard MCTS, the algorithm repeatedly simulates from the root state s0 , selecting actions according to the above scheme. When reaching a leaf node (unexpanded or maximum depth), a rollout policy approximates the return from that leaf. These routines are routine and can be implemented similarly to classical MCTS methods. By combining an optimistic action selection mechanism with a power mean and robust operator for value backup, Robust-Power-UCT systematically balances exploration of uncertain actions and exploitation of promising ones, all under model ambiguity.

Value Backup. To estimate the value function at each node, we use a power mean backup operator. When node sh is expanded in the tree, we define inductively for all t, Vbt (sh ) =

X a∈Ash

ip p1 Tsh ,a (t) h b QTsh ,a (t) (sh , a) , t

6. Theoretical Results In robust MCTS planning, each internal node of the search tree can be viewed as a non-stationary multi-armed bandit due to ongoing updates of the node’s reward and transition ambiguity estimates. At each step, the empirical evaluations shift, reflecting how robust exploration is balanced against uncertainty in the model. To handle this dynamic process, we begin by studying a non-stationary multiarmed bandit problem—focusing on how the power-mean backup operator concentrates around its robust-optimal value. We then leverage these results to prove convergence properties of our robust MCTS algorithm, showing that it systematically discards suboptimal branches under model uncertainty while maintaining sample efficiency.

where p ≥ 1. This power mean backup places more emphasis on actions that have high current value estimates (when p > 1), but still captures the contributions of other b T (t) (sh , a), or simply Q b t (sh , a) actions. Meanwhile Q sh ,a as the root is sh , itself is updated via b b t (sh , a) = R bsrob,a + γσ b (3) Q Ps ,a VTsh+1 (t) , h h

bsrob,a = min b where R r∈Rsh ,a ER∼r [R] is an empirical roh bust reward at (sh , a), and σPb (·) is a robust operator capturing worst-case transitions for ambiguity sets governed by empirical estimates of nominal reward and transition models: n o bs,a = Ps,a ∈ ∆(S) : D Ps,a , pbs,a ≤ ρT , P

6.1. Non-Stationary Bandit Perspective We first analyze Robust-Power-UCT in a simpler nonstationary multi-armed bandit setting. Here, actions are selected optimistically, and the power mean backup operator is used at the root node.

and n o b s,a = νs,a ∈ ∆(B) : D νs,a , νbs,a ≤ ρR . R

6.1.1. P ROBLEM D ESCRIPTION AND K EY D EFINITIONS

Action Selection. At each node sh in the search tree, Robust-Power-UCT selects an action a according to an optimistic rule that balances exploration and exploitation.

We consider a class of non-stationary multi-armed bandit (MAB) problems with K ≥ 1 actions (arms) with the reward ∈ [0, R]. Define a sequence of estimator µ ba,n (in this 5

Online Robust Reinforcement Learning Through Monte-Carlo Planning

Algorithm 1: Robust-Power-UCT with γ discount factor. n : the number of rollouts. {bi , αi , βi }H i=0 are positive constants that satisfy conditions in Table 1. B is the total bins for [0, Rmax ]. π0 is a rollout policy. C is an exploration constant. Input: root node state s0 Output: optimal action at the root node Function R = Rollout (s, depth) Ve (s) = average of the call to π0 (s) return Ve (s) Function a = SelectAction (sh , depth = h, greedy = f alse, t) if greedy == false then

Function SimulateQ (sh , a, depth = h, t) sh+1 ∼ P o (·|sh , a) r(sh , a) ∼ νsoh ,a if sh+1 ∈ / T erminal and depth ⩽ H − 1 then if Node sh+1 not expanded then VbTsh+1 (t) (sh+1 ) = Rollout(sh+1 , depth) else SimulateV (sh+1 , depth = h + 1, t) end end Find j ∈ B s.t. r(sh , a) ∈ Binj [0, Rmax ] ν bs ,a (j)·Tsh ,a (t)+1 νbsh ,a (j) = h Ts ,a (t)+1

bh+1 βh+1

Tsh (t) bT a = argmax{Q αh+1 } sh ,a (t) (sh , a) + C a

β Tsh ,a (t) h+1

else bT a = argmax{Q sh ,a (t) (sh , a)} a

end return a Function SimulateV (sh , depth, t) a ← SelectAction(sh , depth = h, greedy = false, t) SimulateQ (sh , a, depth = h, t) Tsh (t) ← Tsh (t) + 1 P T 1 sh ,a (t) b p p VbTsh (t) (sh ) ← ( Q (s , a)) h T (t) sh ,a a Ts (t)

pbsh ,a (sh+1 ) =

Tsh ,a (t) ← Tsh ,a (t) + 1 bT brob Q (t) (sh , a) ← Rs ,a + γσ b sh ,a

paper is the robustness estimation of the mean value of arm a) such that µa,n = E µ ba,n . We are interested in sequence of estimators that satisfy a suitable concentration property:

p K Ta (n) µ ba,Ta (n) a=1 n

Assumption 1 (Non-Stationary Rewards). For each arm a ∈ [K], the sequence {b µa,n }n≥1 concentrates at rate →

. By applying Theorem 1 of

Connecting Back to MCTS. This bandit analysis underpins how Robust-Power-UCT handles exploration and the power mean backup. In an MCTS context, each node’s local bandit analysis is augmented by worst-case backups, but the principle is similar: the algorithm discards suboptimal branches with high probability, causing the robust estimates to concentrate around the best actions.

> ε ≤ c n−α ε−β .

α,β

α′ ,β ′

n→∞

Psh ,a (VTsh+1 (t) )

Dam et al. (2024b), we get µ bn (p) → µ⋆ , where α′ = n→∞ (b − 1) 1 − αb , and β ′ = (b − 1).

Definition 1 (Concentration). A sequence of estimators {Ybn }n≥1 concentrates at rate (α, β) toward a limit Y , writα,β ing as Ybn → Y , if there is a constant c > 0 such that

(α, β) toward a value µa , i.e. µ ba,n

Function MainLoop For t = 0, · · · , n SimulateV (s0 , depth = 0, t) return SelectAction (s0 , greedy = true, n)

α ∀ n ≥ 1, ∀ ε > n− β , Pr Ybn −Y

p bsh ,a (sh+1 )·Tsh ,a (t)+1 Tsh ,a (t)+1

µa . Let µ⋆ = 6.1.3. M AIN C ONVERGENCE R ESULTS

maxa∈[K] {µa }, assumed to be unique with a strict gap from suboptimal µa .

Before presenting the main result (Theorem 3), we first show an important lemma used for our MCTS algorithm.

6.1.2. O PTIMISTIC ACTION S ELECTION AND P OWER M EAN BACKUP

Lemma 17. For m ∈ [M ], let (Vbm,n )n⩾1 be a sequence α,β of estimator satisfying Vbm,n → Vm , and there exists a

Under Assumption 1, we use an optimistic exploration rule similar to Robust-Power-UCT. Let Ta (n) be the number of times arm a is pulled before time n. The algorithm pulls each arm once initially. For n > K: n o b α an = arg max µ ba,Ta (n) + C n β /Ta (n) β , (4)

n→∞

constant L such that Vbm,n ⩽ L, ∀n ⩾ 1. Let Xi be an iid sequence from a distribution ν o with mean µ and Si be an iid sequence from a distribution p = (p1 , . . . , pM ) supported on {1, . . . , M }. Introducing the random variables n Nm = #|{i ⩽ n : Si = sm }|. Define a model estimate of N1n N2n Nn p as pbn = ( nP , n , ..., nM ). We define an estimate of ν o n as νbn = n1 i=1 δXi . Recall Rrob = minr∈R ER∼r [R] brob = min b ER∼r [R] w.r.t νbn . We define w.r.t ν o and R r∈R

a∈[K]

where b > 2 and b < α. For the power mean operator, let p ∈ [1, ∞) and define µ bn (p) = 6

Online Robust Reinforcement Learning Through Monte-Carlo Planning

Remark 2. These results show that both Robust-Power-UCT and standard (non-robust) MCTS achieve the same O(n−1/2 ) rate for value estimation at the root node, which implies that robustness need not affect convergence speed, which is order-optimal. While we achieve this rate, the exact dependence on various problem-dependent factors (e.g., number of actions A, number of states S, tree search depth H, etc.) is not decodable (thereby not comparable to other online robust RL results (Dong et al., 2022)) due to our analysis limitations.

the sequence of estimators bn = R brob + γσpb (Vbn ). Q n b n α,β Then with 2α ⩽ β, β > 1, Q → Rrob + γσp (V ). n→∞

Remark 1. This non-asymptotic convergence result shows b n will that, for suitable parameters (α, β), the estimator Q concentrate around the limiting quantity Rrob + γ σp (V ) with high probability. Importantly, we do not claim these (α, β) are in any sense optimal; rather, we only need the existence of such parameters that guarantee the concentration at the prescribed rate. Moreover, our analysis uses covering number generalization to handle continuous reward distributions. Furthermore, the constant c implicit in α,β the notation Vbn → V can depend on problem-dependent

7. Experiments We evaluate Robust-Power-UCT in three distinct environments designed to test different aspects of robust planning: the Gambler’s Problem, Frozen Lake, and American Option Pricing. For each environment, we compare: Stochastic-Power-UCT (Dam et al., 2024b) (baseline) and Robust-Power-UCT with Total Variation, Chi-squared, and Wasserstein ambiguity sets.

n→∞

factors (e.g., size of the action set A, number of states S, etc.), reflecting the stochastic process complexity. 6.2. Tree-Level Convergence

While several robust reinforcement learning methods exist (c.f.Section 2), to the best of our knowledge, this is the first work to incorporate ambiguity sets directly into MCTS, making Stochastic-Power-UCT our primary baseline. All experiments are done over 100 seeds, using γ = 0.99 and robustness budget ρ = 0.5, with these values showing consistent performance across preliminary experiments with different parameter settings. For concise presentation, we only experiment with transition model ambiguity just as prior robust RL works.

The above non-stationary bandit analysis is critical for proving the subsequent tree-level theorems. In particular, Theorem 2 (restated below) shows that under appropriate parameter settings (Table 1), the estimated node values b n (·, ·) converge at a known rate: Vbn (·) and Q Theorem 2. When applying Robust-Power-UCT with H H parameters {bi }H i=0 , {αi }i=0 , {βi }i=0 satisfying Table 1: (i) For any node sh at depth h ∈ {0, . . . , H}, αh ,βh Vbn (sh ) → Ve (sh ).

Full experimental details, environment descriptions and hyperparameter configurations are provided in Appendix.E.1, along with an additional analysis of the robustness budget. We also provide our code at https://github.com/ brahimdriss/RobustMCTS.

n→∞

(ii) For any node sh at depth h ∈ {0, . . . , H − 1}, ,βh+1 b n (sh , a) αh+1→ e h , a), Q Q(s n→∞

∀ a ∈ Ash . Remark 3. While the robust Bellman operator involves solving a minimization problem over probability distributions, we can leverage dual reformulations to make its computation tractable. Many prior works (Iyengar, 2005; Nilim and El Ghaoui, 2005; Xu et al., 2023) show, for a value function V and nominal distribution P o , the robust value under all ambiguity balls with radius ρT can be computed in at most O(S log(S)) time. Thus requiring only marginally more computation than standard Bellman operators O(S). This computational efficiency is crucial for practical implementations, particularly in online planning settings like MCTS with frequent Bellman updates.

Proof. (Sketch) The argument proceeds by induction on the tree depth H. For H = 1, we handle the root node using Lemma 17 plus the concentration assumptions on leaf nodes. For general H, we note that descending into a child node effectively reduces the depth by one, thus the induction hypothesis applies. By carefully controlling exploration (Section 5) and using robust backups, each node’s b estimates concentrate at the specified rates. Vb and Q Finally, Theorem 3 establishes that under optimal parameter tuning, the expected payoff at the root converges at O(n−1/2 ).

7.1. Gambler’s Problem Robustness Results

Theorem 3. (Convergence of Expected Payoff) At the root node s0 , there is a choice of parameters yielding E Vbn (s0 ) − Ve (s0 ) ≤ O n−1/2 .

The Gambler’s Problem provides an ideal testbed for evaluating robustness to model misspecification. An agent must reach a target capital through a series of bets, with each 7

Online Robust Reinforcement Learning Through Monte-Carlo Planning Planning with p_h = 0.6

Planning with p_h = 0.8 1.0

0.8

0.6 0.4 0.2

Success rate (%)

1.0

Success rate (%)

Planning with p_h = 0.4 1.0

0.6 0.4 0.2

0.0 0.3

0.4

0.5

0.6

0.7

0.8

0.0 0.2

0.3

Execution p_h Stochastic-Power-UCT

0.4 0.2

0.0 0.2

0.6

0.4

0.5

0.6

0.7

0.8

0.2

Execution p_h Robust-Power-UCT MCTS (TV)

Robust-Power-UCT MCTS (Chi²)

0.3

0.4

0.5

0.6

0.7

0.8

Execution p_h Robust-Power-UCT MCTS (Wasserstein)

Figure 1: Success rates in the Gambler’s Problem under model mismatch. Results show planning with fixed probabilities ph = {0.4, 0.6, 0.8} while executing across different probabilities. Shaded area demonstrates how robust methods maintain more consistent performance under model mismatch compared to Stochastic-Power-UCT. bet winning with probability ph . This enables precise control of the planning-execution mismatch through a single parameter.

proaches. Both Wasserstein and Chi-squared variants outperform the baseline Stochastic-Power-UCT and Total Variation approaches. Interestingly, when planning and execution probabilities align (underlined values), both robust variants maintain superior performance compared to standard approaches. This suggests that explicitly accounting for uncertainty in the planning process provides benefits even without model mismatch, possible by encouraging more conservative and reliable decision-making strategies.

Figure 1 illustrates the performance of different PowerUCT variants under model mismatch in the Gambler’s Problem. The behavior of Stochastic-Power-UCT reveals a fundamental vulnerability: when ph < 0.5, there exist multiple optimal policies that achieve winning ratios close to the true environment probability. However, when planning with ph ⩾ 0.5, the algorithm converges to an aggressive single-bet strategy that fails catastrophically when the true probability is lower than assumed.

These results on Gambler’s Problem and Frozen Lake demonstrate that explicitly accounting for model ambiguity during planning can significantly improve reliability when deployment conditions differ from simulation assumptions. The choice of ambiguity set provides a mechanism for balancing conservatism against nominal performance.

The superior performance of robust variants stems from their conservative betting strategies. While StochasticPower-UCT often makes large single bets, robust variants tend to make smaller, sequential bets that preserve capital for future opportunities.

7.3. American Option Robustness Results 7.2. Frozen Lake Robustness Results

The American Option environment provides a financial domain to test reward robustness under model uncertainty. In this setting, the agent must decide when to exercise an option to maximize expected returns, with the key uncertain parameter being the probability pu of price increases at each time step.

The Frozen Lake environment tests robustness in a different complex setting where uncertainties compound over multiple steps. The agent must navigate to a goal while avoiding hazards, with actions potentially failing with probability pslip .

Figure 2 demonstrates the reward robustness of different Power-UCT variants under model mismatch in option pricing scenarios. We examine two planning scenarios: training with pu = 0.5 (left panel) and pu = 0.6 (right panel), then testing across execution probabilities from 0.4 to 0.8.

Table 2 provides detailed success rates across different planning and execution probabilities. With matching conditions (4000 rollouts and pslip = 0.3 case), our results closely match those reported in the original paper (Dam et al., 2024b) even with slightly different dynamics. The Wasserstein uncertainty set exhibits superior performance in scenarios with lower execution probabilities, achieving the highest success rates (bold) across multiple conditions. For example, with pslip = 0.3, it achieves 58% success when pexec = 0.1, significantly outperforming other ap-

The results reveal that robust variants maintain significantly more stable performance compared to standard PowerUCT. When planning with pu = 0.5, the standard approach shows dramatic performance degradation as the test probability deviates from the planning assumption, dropping 8

Online Robust Reinforcement Learning Through Monte-Carlo Planning Training with p_u = 0.5

Training with p_u = 0.6

8 7

Mean Reward

4 5 4 3

2 1 1 0

0.40

0.45

0.50

0.55

0.60

0.65

0.70

0.75

0.80

0.40

0.45

0.50

Test p_u

0.55

0.60

0.65

0.70

0.75

0.80

Test p_u

Power MCTS (Standard)

Robust Power MCTS (TV)

Robust Power MCTS (Chi²)

Robust Power MCTS (Wasserstein)

Figure 2: Reward robustness comparison in American Option pricing under model mismatch. Results show planning with fixed price-up probabilities pu = {0.5, 0.6} while testing across different probabilities. Robust variants maintain significantly more stable performance compared to standard Power-UCT, demonstrating consistent risk-averse behavior that is particularly valuable in financial decision-making contexts where reliability is crucial. nancial contexts where consistent performance is preferred over potentially high but unreliable returns.

Execution pslip

Planning pplan slip

0.1

0.2

0.3

0.4

0.5

0.3

Sp Tv Cs Ws

15 18 55 58

12 15 45 48

10 12 35 32

8 10 25 28

7 8 18 20

The Wasserstein and Chi-squared ambiguity sets show particularly strong performance, maintaining steady rewards even under significant model mismatch, demonstrating that explicitly accounting for uncertainty leads to policies inherently more robust to different deployment conditions.

0.4

Sp Tv Cs Ws

8 10 35 38

7 8 28 30

6 7 22 25

5 6 18 20

4 5 12 15

8. Conclusions

Sp Tv Cs Ws

5 6 25 28

4 5 20 22

4 4 15 18

3 4 12 15

3 3 8 10

0.5

We have developed a robust variant of Monte Carlo Tree Search (MCTS) that addresses dynamical model and reward distribution ambiguities, bridging the gap between simulation-based planning and real-world deployment. The dependence of MCTS-based algorithms’ convergence rates on parameters (states S, actions A, depth H) remains underexplored in standard RL. We will address this gap for both robust and non-robust setups in the future. As our formulation follows an overly conservative mathematical framework, in the future, we will explore alternative robust formulations that are more permeable to less conservative solutions to address the simulation-to-reality gap.

Table 2: Success rates (%) for planning with Power-UCT variants. Methods: Stochastic-Power-UCT (Sp), Robust version with Total Variation (Tv), Chi-squared (Cs), and Wasserstein (Ws) ambiguity sets. Underlined values indicate matching planning and execution pslip . Bold indicates highest success rate per planning scenario.

Impact Statement from approximately 5 to near 0 when pu = 0.8. In contrast, robust variants maintain consistent performance across the entire range.

This paper presents a novel algorithm for the robust reinforcement learning field using the Monte Carlo Tree Search planning mechanism. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here.

When planning with pu = 0.6, standard Power-UCT exhibits extreme sensitivity with dramatically varying performance. The robust variants demonstrate desired risk-averse behavior: achieving conservative but stable returns across all conditions. This stability is especially valuable in fi9

Online Robust Reinforcement Learning Through Monte-Carlo Planning

Acknowledgments

Tuan Q Dam, Carlo D’Eramo, Jan Peters, and Joni Pajarinen. Convex regularization in monte-carlo tree search. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 2365–2375. PMLR, 18–24 Jul 2021. URL https://proceedings.mlr.press/ v139/dam21a.html.

Tuan Dam was funded by Hanoi University of Science and Technology (HUST) under Project No. T2024-TD-024. K. Panaganti acknowledges support from the Resnick Institute and the ‘PIMCO Postdoctoral Fellow in Data Science’ fellowship at Caltech. B. Driss was funded by the project ANR-23-CE23-0006. A. Wierman acknowledges support by the NSF through CNS-2146814, CPS-2136197, CNS2106403, and NGSDI-2105648. This work was granted access to the HPC resources of IDRIS under the allocation 2024-AD011015599 made by GENCI.

Jing Dong, Jingwei Li, Baoxiang Wang, and Jingzhao Zhang. Online policy optimization for robust mdp. arXiv preprint arXiv:2209.13841, 2022. Nicolas Fournier and Arnaud Guillin. On the rate of convergence in wasserstein distance of the empirical measure. Probability theory and related fields, 162(3):707– 738, 2015.

References Kishan Panaganti Badrinath. Robust Reinforcement Learning: Theory and Algorithms. PhD thesis, Texas A&M University, 2023.

Rui Gao and Anton Kleywegt. Distributionally robust stochastic optimization with wasserstein distance. Mathematics of Operations Research, 48(2):603–655, 2023.

Noam Brown and Tuomas Sandholm. Superhuman ai for heads-up no-limit poker: Libratus beats top professionals. Science, 359(6374):418–424, 2018.

Michael B Giles. Multilevel monte carlo path simulation. Operations research, 56(3):607–617, 2008.

Imre Csiszár. Eine informationstheoretische ungleichung und ihre anwendung auf den beweis der ergodizität von markoffschen ketten. A Magyar Tudományos Akadémia Matematikai Kutató Intézetének Közleményei, 8(1-2):85– 108, 1963.

Arthur Guez, Théophane Weber, Ioannis Antonoglou, Karen Simonyan, Oriol Vinyals, Daan Wierstra, Rémi Munos, and David Silver. Learning to search with mctsnets. In International conference on machine learning, pages 1822–1831. PMLR, 2018.

Tuan Dam, Pascal Klink, Carlo D’Eramo, Jan Peters, and Joni Pajarinen. Generalized mean estimation in montecarlo tree search. In Christian Bessiere, editor, Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI-20, pages 2397– 2404. International Joint Conferences on Artificial Intelligence Organization, 7 2020. doi: 10.24963/ijcai.2020/ 332. URL https://doi.org/10.24963/ijcai. 2020/332. Main track.

Stefan Heinrich. Multilevel monte carlo methods. In Large-Scale Scientific Computing: Third International Conference, LSSC 2001 Sozopol, Bulgaria, June 6–10, 2001 Revised Papers 3, pages 58–67. Springer, 2001. Carl-Johan Hoel, Katherine Driggs-Campbell, Krister Wolff, Leo Laine, and Mykel J Kochenderfer. Combining planning and deep reinforcement learning in tactical decision making for autonomous driving. IEEE transactions on intelligent vehicles, 5(2):294–305, 2019.

Tuan Dam, Georgia Chalvatzaki, Jan Peters, and Joni Pajarinen. Monte-carlo robot path planning. IEEE Robotics and Automation Letters, 7(4):11213–11220, 2022.

Garud N Iyengar. Robust dynamic programming. Mathematics of Operations Research, 30(2):257–280, 2005.

Tuan Dam, Carlo D’Eramo, Jan Peters, and Joni Pajarinen. A unified perspective on value backup and exploration in monte-carlo tree search. Journal of Artificial Intelligence Research, 81:511–577, 2024a.

Leslie Pack Kaelbling, Michael L Littman, and Andrew W Moore. Reinforcement learning: A survey. Journal of artificial intelligence research, 4:237–285, 1996.

Tuan Dam, Odalric-Ambrym Maillard, and Emilie Kaufmann. Power mean estimation in stochastic monte-carlo tree search. In Negar Kiyavash and Joris M. Mooij, editors, Proceedings of the Fortieth Conference on Uncertainty in Artificial Intelligence, volume 244 of Proceedings of Machine Learning Research, pages 894–918. PMLR, 15–19 Jul 2024b. URL https://proceedings.mlr. press/v244/dam24a.html.

Bilal Kartal, Pablo Hernandez-Leal, and Matthew E Taylor. Action guidance with mcts for deep reinforcement learning. In Proceedings of the AAAI conference on artificial intelligence and interactive digital entertainment, volume 15, pages 153–159, 2019. Behbod Keshavarzi and Hamidreza Navidi. Comparative analysis of extensive form zero sum game algorithms for poker like games. Scientific Reports, 15(1):2917, 2025. 10

Online Robust Reinforcement Learning Through Monte-Carlo Planning

Levente Kocsis and Csaba Szepesvári. Bandit based monte-carlo planning. In European conference on machine learning, pages 282–293. Springer, 2006.

provable performance guarantees. In International Conference on Machine Learning, pages 511–520. PMLR, 2021.

Navdeep Kumar, Esther Derman, Matthieu Geist, Kfir Y Levy, and Shie Mannor. Policy gradient for rectangular robust markov decision processes. Advances in Neural Information Processing Systems, 36:59477–59501, 2023.

Kishan Panaganti and Dileep Kalathil. Sample complexity of robust reinforcement learning with a generative model. In International Conference on Artificial Intelligence and Statistics, pages 9582–9602. PMLR, 2022.

Martin Kurečka, Václav Nevyhoštěnỳ, Petr Novotnỳ, and Vı́t Unčovskỳ. Threshold uct: Cost-constrained monte carlo tree search with pareto curves. arXiv preprint arXiv:2412.13962, 2024.

Kishan Panaganti, Zaiyan Xu, Dileep Kalathil, and Mohammad Ghavamzadeh. Robust reinforcement learning using offline data. Advances in Neural Information Processing Systems (NeurIPS), 2022.

Jongmin Lee, Geon-Hyeong Kim, Pascal Poupart, and Kee-Eung Kim. Monte-carlo tree search for constrained pomdps. Advances in Neural Information Processing Systems, 31, 2018.

Kishan Panaganti, Adam Wierman, and Eric Mazumdar. Model-free robust φ-divergence reinforcement learning using both offline and online data. ICML, arXiv preprint arXiv:2405.05468, 2024.

Edouard Leurent. rl-agents: Implementations of reinforcement learning algorithms. https://github. com/eleurent/rl-agents, 2018.

Kishan Panaganti, Zaiyan Xu, Dileep Kalathil, and Mohammad Ghavamzadeh. Bridging distributionally robust learning and offline rl: An approach to mitigate distribution shift and partial data coverage. Learning for Dynamics and Control Conference, 2025.

Zhishuai Liu and Pan Xu. Distributionally robust offdynamics reinforcement learning: Provable efficiency with linear function approximation. In International Conference on Artificial Intelligence and Statistics, pages 2719–2727. PMLR, 2024.

Dinesh Parthasarathy, Georgios Kontes, Axel Plinge, and Christopher Mutschler. C-mcts: Safe planning with monte carlo tree search. arXiv preprint arXiv:2305.16209, 2023.

Zijian Liu, Qinxun Bai, Jose Blanchet, Perry Dong, Wei Xu, Zhengqing Zhou, and Zhengyuan Zhou. Distributionally robust q-learning. In International Conference on Machine Learning, pages 13623–13643. PMLR, 2022.

Hamed Rahimian and Sanjay Mehrotra. Distributionally robust optimization: A review. arXiv preprint arXiv:1908.05659, 2019. Erica Salvato, Gianfranco Fenu, Eric Medvet, and Felice Andrea Pellegrino. Crossing the reality gap: A survey on sim-to-real transferability of robot controllers in reinforcement learning. IEEE Access, 9:153171–153187, 2021.

Weichao Mao, Kaiqing Zhang, Qiaomin Xie, and Tamer Basar. Poly-hoot: Monte-carlo planning in continuous space mdps with non-asymptotic analysis. Advances in Neural Information Processing Systems, 33:4549–4559, 2020.

Julian Schrittwieser, Ioannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Simon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, et al. Mastering atari, go, chess and shogi by planning with a learned model. Nature, 588(7839):604– 609, 2020.

Arnab Nilim and Laurent El Ghaoui. Robust control of markov decision processes with uncertain transition matrices. Operations Research, 53(5):780–798, 2005. Santiago Ontanón. The combinatorial multi-armed bandit problem and its application to real-time strategy games. In Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, volume 9, pages 58–64, 2013.

Devavrat Shah, Qiaomin Xie, and Zhi Xu. Nonasymptotic analysis of monte carlo tree search. In Abstracts of the 2020 SIGMETRICS/Performance Joint International Conference on Measurement and Modeling of Computer Systems, pages 31–32, 2020.

Michael Painter, Mohamed Baioumy, Nick Hawes, and Bruno Lacerda. Monte carlo tree search with boltzmann exploration. Advances in Neural Information Processing Systems, 36:78181–78192, 2023.

Laixi Shi and Yuejie Chi. Distributionally robust modelbased offline reinforcement learning with near-optimal sample complexity. Journal of Machine Learning Research, 25(200):1–91, 2024.

Kishan Panaganti and Dileep Kalathil. Robust reinforcement learning using least squares policy iteration with 11

Online Robust Reinforcement Learning Through Monte-Carlo Planning

David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al. Mastering the game of go with deep neural networks and tree search. nature, 529(7587):484, 2016.

Zhao-Heng Yin, Weirui Ye, Qifeng Chen, and Yang Gao. Planning for sample efficient imitation learning. Advances in Neural Information Processing Systems, 35: 2577–2589, 2022. Runyu Zhang, Yang Hu, and Na Li. Regularized robust mdps and risk-sensitive mdps: Equivalence, policy gradient, and sample complexity. arXiv preprint arXiv:2306.11626, 2023.

Richard S Sutton and Andrew G Barto. Reinforcement learning: an introduction, 2nd edn. adaptive computation and machine learning, 2018.

Zhengqing Zhou, Zhengyuan Zhou, Qinxun Bai, Linhai Qiu, Jose Blanchet, and Peter Glynn. Finite-sample regret bound for distributionally robust offline tabular reinforcement learning. In International Conference on Artificial Intelligence and Statistics, pages 3331–3339. PMLR, 2021.

Maciej Świechowski, Konrad Godlewski, Bartosz Sawicki, and Jacek Mańdziuk. Monte carlo tree search: A review of recent modifications and applications. Artificial Intelligence Review, 56(3):2497–2562, 2023. Mark Towers, Ariel Kwiatkowski, Jordan Terry, John U Balis, Gianluca De Cola, Tristan Deleu, Manuel Goulão, Andreas Kallinteris, Markus Krimmel, Arjun KG, et al. Gymnasium: A standard interface for reinforcement learning environments. arXiv preprint arXiv:2407.17032, 2024. Jie Wang, Rui Gao, and Yao Xie. Regularization for adversarial robust learning. arXiv preprint arXiv:2408.09672, 2024a. Shengbo Wang, Nian Si, Jose Blanchet, and Zhengyuan Zhou. A finite sample complexity bound for distributionally robust q-learning. In International Conference on Artificial Intelligence and Statistics, pages 3370–3398. PMLR, 2023. Shengbo Wang, Nian Si, Jose Blanchet, and Zhengyuan Zhou. Sample complexity of variance-reduced distributionally robust q-learning. Journal of Machine Learning Research, 25(341):1–77, 2024b. Yudan Wang. Model-free robust reinforcement learning with sample complexity analysis. Master’s thesis, State University of New York at Buffalo, 2024. Chenjun Xiao, Ruitong Huang, Jincheng Mei, Dale Schuurmans, and Martin Müller. Maximum entropy monte-carlo planning. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL https://proceedings.neurips. cc/paper_files/paper/2019/file/ 7ffb4e0ece07869880d51662a2234143-Paper. pdf. Zaiyan Xu, Kishan Panaganti, and Dileep Kalathil. Improved sample complexity bounds for distributionally robust reinforcement learning. In International Conference on Artificial Intelligence and Statistics, pages 9728–9754. PMLR, 2023. 12

Online Robust Reinforcement Learning Through Monte-Carlo Planning

A. Notations Notation

Description

S, A H (s, a) [M ] o νs,a νs,a , νbs,a Rmax Df (P ∥P o ) TV X W Ps,a , Ps,a , Ps,a σPs,a (V ) ρ σpbn (Vbn ) Bp α∗ , α b∗ ∆(X) NR (θ) ∥ · ∥∞ , ∥ · ∥1 δx δ, θ, ε c, C n p m , Nm ⋆ b Qn , Q Vbn , V ⋆ γ W(µn , µ)

State space and action space of the MDP. Planning horizon (depth of the search tree). A specific state–action pair; s ∈ S, a ∈ A. Denotes the set {1, 2, · · · , M }. Nominal (true) reward distribution for state–action pair (s, a). Generic and empirical reward distributions for (s, a), respectively. Maximum possible reward value (i.e., reward is supported in [0, Rmax ]). f -divergence between distributions P and P o , for a convex f (·). Uncertainty sets under Total Variation, Chi-square, and Wasserstein distances, respectively. Worst-case value operator (or “robust backup”) over an uncertainty set Ps,a . Radius (budget) for the uncertainty set in f -divergence or Wasserstein distance. Robust backup operator with the empirical transition pbn as the set center for empirical value Vbn . Constant bounding the metric space for Wasserstein distance (e.g. max distance dp ). Dual variables optimizing robust reward functions under TV uncertainty sets. Probability simplex over the support of set X or size of X. θ-cover set used for bounding the supremum of (η − R)+ in total-variation analysis. Infinity norm (maximum absolute value in a vector) and ℓ1 norm (sum of absolute values in a vector). A point mass at a realization x. Parameters often controlling confidence levels or approximation accuracy in concentration bounds. Constants from generic concentration or covering-number arguments (possibly problem-dependent). n Used for i.i.d. sampling from a discrete distribution (p1 , . . . , pM ), with Nm the count of outcomes of type m. Estimated and true robust Q-values, respectively. Estimated and true robust value functions, respectively. Discount factor in the MDP. Wasserstein distance between empirical measure µn and true measure µ.

α,β

→

n→∞

Notation for concentration at rate (α, β); see text for precise definition.

Table 3: Key Notations Used in the Appendix. Symbols and definitions for uncertainty sets (TV, χ2 , Wasserstein), reward distributions, and the main variables in robust MDP analysis.

B. Useful technical results Lemma 1. (Lemma 1 (Panaganti and Kalathil, 2022)) For any (s, a) ∈ S × A and for any V1 , V2 ∈ P|S| , we have |σPs,a (V1 ) − σPs,a (V2 )| ⩽ ∥V1 − V2 ∥∞ and |σPbs,a (V1 ) − σPbs,a (V2 )| ⩽ ∥V1 − V2 ∥∞ Lemma 2. (Proposition 2 (Xu et al., 2023)) Fix any h, s, a ∈ [H] × S × A. For any θ, δ ∈ (0, 1), we have with the p probability of at least 1 − δ, σP T V (Vbh+1 ) − σ bT V (Vbh+1 ) ⩽ 2θ + H 2 log(4H/θδ)/2n s,a

Ps,a

From Lemma 2, we have P

b b T V (Vh+1 ) − σ b T V (Vh+1 ) ⩾ 2θ + σPs,a P s,a

p H 2 log(4H/θδ)/2n < δ

(5)

p Set θ = ε/4 with ε = 2 H 2 log(4H/θδ)/2n, then 2nε2 /4 = H 2 log(4H/θδ) ⇒ exp{−2nε2 /H 2 } = εδ/16H 2

⇒δ=

(6)

16H exp{−nε /2H } ε

(7)

so that P

2 2 bh+1 ) − σ bT V (Vbh+1 ) ⩾ ε < 16H exp{−nε /2H } T V (V σPs,a Ps,a ε

(8)

Lemma 3. (Proposition 4 (Xu et al., 2023)) Fix any h, s, a ∈ [H] × S × A. For any θ, δ ∈ (0, 1), we have with the r √ 2 2Cp H 2(1+Cp H/(θ(Cp −1))) b b √ X (Vh+1 ) − σ b X (Vh+1 ) ⩽ 2θ + probability of at least 1 − δ, σPs,a log +1 P δ (Cp −1) n s,a

Online Robust Reinforcement Learning Through Monte-Carlo Planning

Then we have b b X (Vh+1 ) − σ b X (Vh+1 ) ⩾ 2θ P σPs,a P s,a

√

2C 2 H

p √ Set θ = ε/4 with ε = 2 (Cp −1) n

log

√

2Cp2 H √ + (Cp − 1) n

2(1+Cp H/(θ(Cp −1))) δ

2(1 + Cp H/(θ(Cp − 1))) log δ

<δ

(9)

+ 1 , then

!2 √ 2(1 + Cp H/(θ(Cp − 1))) (Cp − 1) nε √ = log −1 δ 2 2Cp2 H   !2 √   δ (Cp − 1) nε √ ⇒ exp − −1 = 2   2(1 + Cp H/(θ(Cp − 1))) 2 2Cp H b b X (Vh+1 ) − σ b X (Vh+1 ) ⩾ ε < ⇒ P σPs,a Ps,a  !2  √   ε(Cp − 1) (Cp − 1) nε √ 2 1 + Cp H/( ) exp − −1   4 2 2Cp2 H

(10)

(11) (12) (13)

Lemma 4. (Proposition 9 (Xu et al., 2023)) Fix any h, s, a ∈ [H] × S × A. r For any θ, δ ∈ (0, 1), we have with the log

H(Bp +ρ ) b b W (Vh+1 ) − σ b W (Vh+1 ) ⩽ 2θ + probability of at least 1 − δ, σPs,a P ρp

2HB +2H √ρp 2n

s,a

r 2H(Bp +ρp ) Similarly, Set θ = ε/4 with ε = ρp

log

p ρp θδ

2HB +2H √ρp p ρp θδ

, then

ρp θδ 2nε2 ρ2p √ = 2 p 2 4H (Bp + ρ ) 2HBp + 2H ρp √ 4 (2HBp + 2H ρp ) 2nε2 ρ2p ⇒δ= exp − ρp ε 4H 2 (Bp + ρp )2

exp −

(14) (15)

so that P

4 (2HB + 2H √ρp ) 2nε2 ρ2p p b b W (Vh+1 ) − σ b W (Vh+1 ) ⩾ ε σPs,a < exp − Ps,a ρp ε 4H 2 (Bp + ρp )2

(16)

Lemma 5. (Lemma 2 (Fournier and Guillin, 2015), Concentration inequality for Wasserstein distance ). For µ ∈ P(R), we consider an i.i.d. sequence (Xk )k⩾1 of µ-distributed random variables and, for all n ⩾ 1, the empirical measure n

µn :=

1X δXk . n k=1

Assume that there exists γ > 0 such that E2,γ (µ) :=

R R

exp γ|x|2 µ(dx) < ∞. Then for all n ⩾ 1, all x > 0,

P (W (µn , µ) ⩾ x) ⩽ C exp −cnx2

where the Wasserstein distance W (µn , µ) is defined by Z W (µn , µ) :=

inf π∈Π(µn ,µ)

and the positive constant C and c depends only on γ and E2,γ (µ).

|x − y|π(dx, dy)

Online Robust Reinforcement Learning Through Monte-Carlo Planning

Lemma 6. (Lemma 4 (Zhou et al., 2021)). Let X ∼ P be a random variable with X ∈ [0, M ], and Pn denotes its empirical distribution of sample size n. For δ > 0, for any i o n h α∗ ∈ arg max −α log EP e−X/α − αδ

(17)

α⩾0

(1) α∗ = 0. Furthermore, assume that the support of X is finite. Then there exists a constant N ′ := N ′ (ε, δ, P ), such that n ⩾ N ′ , with probability at least 1 − ε, we have i o n h 0 ∈ arg max −α log EPn e−X/α − αδ α⩾0

(2) α∗ > 0. Then there exists a constant N ′′ := N ′′ (ε, δ, P ), such that for any n ⩾ N ′′ , with probability at least 1 − ε, there exists a i o n h α b∗ ∈ arg max −α log EPn e−X/α − αδ α⩾0

such that α∗ , α b∗ ∈ [α, ᾱ], where α > 0 is independent of n and ᾱ = M/δ. The Total Variation, Chi-square, and Kullback-Liebler uncertainty sets are constructed with the f -divergence. The f divergence between the distributions P and P o is defined as Z dP Df (P ∥P o ) = f dP o (18) dP o where f is a convex function (Csiszár, 1963). We obtain different divergences for different forms of the function f , including some well-known divergences. For example, f (t) = |t − 1|/2 gives Total Variation, f (t) = (t − 1)2 gives chi-square, and f (t) = t log(t) gives Kullback-Liebler. Lemma 7. (Lemma 5 (Panaganti et al., 2022)) Let Df be as defined in equation 18 with f (t) = |t − 1|/2 corresponding to the TV uncertainty set. Then, inf o

Df (P ∥P )⩽ρ

EP [l(X)] = − inf EP o [(η − l(X))+ ] + η − inf l(x) × ρ − η, x∈X

η∈R

Lemma 8. (Covering number (TV)). Given a reward function R ∈ Rs,a , let UR = {(η · 1 − R)+ : η ∈ [0, Rmax ]}. Fix any θ ∈ (0, 1). Denote NR (θ) = {(η · 1 − R)+ : η ∈ {θ, 2θ, . . . , Nθ · θ}} where Nθ = ⌈Rmax /θ⌉. Then NR (θ) is a θ-cover for UR with respect to ∥·∥∞ , and its cardinality is bounded as |NR (θ)| ⩽ 2Rmax /θ. Furthermore, for any ν ∈ NR (θ), we have ∥ν∥∞ ⩽ 1. Proof. First, Nθ = ⌈Rmax /θ⌉ is the minimal number of subintervals of length θ needed to cover [0, Rmax ]. Denote Ji = [(i − 1)θ, iθ) to be the i-th subinterval, 1 ⩽ i ⩽ Nθ . Fix some µ ∈ UR . Then µ = (η · 1 − R)+ . Without loss of generality, assume this particular η ∈ Ji . Let ν = ((iθ) · 1 − R)+ . Now, for any s, a ∈ S × A, |ν(s, a) − µ(s, a)| = |(iθ − R)+ − (η − R)+ | (a)

⩽ |iθ − R − η + R| ⩽ |iθ − (i − 1)θ| = θ where (a) follows from iθ > η and the fact that max{x, 0} − max{y, 0} ⩽ x − y, if x > y. Taking maximum with respect to s, a on both sides, we get ∥ν − µ∥∞ ⩽ θ. Since ν ∈ NR (θ), this suggests NR (θ) is a θ-cover for UR . The cardinality bound directly follows from 15

Online Robust Reinforcement Learning Through Monte-Carlo Planning

|NR (θ)| = Nθ = ⌈Rmax /θ⌉ ⩽ Rmax /θ + 1 ⩽ 2Rmax /θ where the last inequality is due to 0 < θ < 1. Now, for any ν ∈ NR (θ), we can establish the following ν = (η · 1 − R)+ ⩽ (Rmax 1 − R)+ ⩽ Rmax where the inequality is element-wise.

Lemma 9. Fix any (s, a) ∈ S × A. Fix any reward function R ∈ Rs,a . Let NR (θ) be the θ-cover of UR = {(η · 1 − R)+ : η ∈ [0, Rmax ]} as described in Lemma 8 . We then have sup η∈[0,Rmax ]

o ER∼bνs,a (η − R)+ − ER∼νs,a (η − R)+ ⩽ max

r∈NR (θ)

o νbs,a r − νs,a r + 2θ

Proof. For any µ ∈ UR , there exists r ∈ NR (θ) such that ∥µ − r∥∞ ⩽ θ. Now for such particular µ and r, we have o o o o r − νs,a µ r + νs,a νs,a µ − νbs,a r| + νbs,a r − νs,a νbs,a µ − νs,a µ ⩽ |b o o ⩽ ∥b νs,a ∥1 ∥µ − r∥∞ + νbs,a r − νs,a r + νs,a ∥r − µ∥∞ 1

⩽ max

ν∈NR (θ)

o νbs,a r − νs,a r + 2θ.

Taking maximum over UR on both sides, we get o sup νbs,a µ − νs,a µ ⩽ max

r∈NR (θ)

µ∈UR

o νbs,a r − νs,a r + 2θ.

Now note that by the definition of UR , we have sup η∈[0,Rmax ]

o ER∼bνs,a (η − R)+ − ER∼νs,a (η − R)+ ⩽ max

r∈NR (θ)

o νbs,a r − νs,a r + 2θ

The desired result directly follows. Lemma 10. Consider the total-variation uncertainty set TV Ps,a =

o o ∥1 ≤ δ . P : 12 ∥P − Ps,a

robT V brobT V = min Let R = minrs,a ∼Rs,a ER∼rs,a [R] be the robust rewards defined using the b s,a ER∼rs,a [R] and Rs,a s,a rs,a ∼R o empirical estimate νbs,a and νs,a and respectively. Then there exists a constant o N ∗ (ε, δ, νs,a ),

such that for all n ≥ N ∗ (i.e. a sufficiently large number of reward samples at (s, a), the following holds with probability at least 1 − ε: r 2 Rmax log(2/δ) robT V robT V b ⩽ Rs,a − Rs,a . 2n 16

Online Robust Reinforcement Learning Through Monte-Carlo Planning

Proof. Following similar analyses as in Proposition 2 (Xu et al., 2023) (Lemma.2), we get ( rob rob bs,a T V − Rs,a T V = | inf ER∼bν (η − R) + η − R inf +

s,a

η∈[0,2Rmax /ρ]

R′ ∈[0,Rmax ]

′

·ρ−η

−

inf η∈[0,2Rmax /ρ]

(a)

sup

⩽

η∈[0,2Rmax /ρ]

inf

R′ ∈[0,Rmax ]

(19)

(

o ER∼νs,a (η − R)+ + η −

)

′

)

·ρ−η

(20)

o ER∼bνs,a (η − R)+ − ER∼νs,a (η − R)+

(21)

o (η − R)+ , ER∼bνs,a (η − R)+ − ER∼νs,a

(22)

( ⩽ max

sup η∈[0,Rmax ]

) sup η∈[Rmax ,2Rmax /ρ]

o ER∼bνs,a (η − R)+ − ER∼νs,a (η − R)+

(23)

(

(b)

⩽ max

sup η∈[0,Rmax ]

o ER∼bνs,a (η − R)+ − ER∼νs,a (η − R)+ ,

(24)

o o ER∼bνs,a [R] − ER∼νs,a [R] (c) o o ⩽ max max νbs,a r − νs,a r + 2θ, ER∼bνs,a [R] − ER∼νs,a [R]

(25) (26)

r∈NR (θ)

where (a) follows from the fact that |inf x f (x) − inf x g(x)| ⩽ supx |f (x) − g(x)|. For (b), recall that R ⩽ Rmax for any R ∈ R. Hence, the term η − R′ is always non-negative for η ∈ [Rmax , 2Rmax /ρ], which cancels out by linearity of the expectation. (c) follows from applying Lemma 9 to the first term. Recall that all r ∈ NR (θ) is upper bounded by Rmax . Now we can apply Hoeffding’s inequality to the first term in equation 26: 2nε2 o , P νbs,a r − νs,a r ⩾ ε ⩽ 2 exp − 2 Rmax Now choose ε =

2 Rmax log(2|NR (θ)|/δ) and recall that |NR (θ)| ⩽ 2Rmax /θ from Lemma 8. We have 2N

r P

∀ε > 0

o νbs,a r − νs,a r

⩾

2 Rmax log(4Rmax /θδ) 2n

r o νbs,a r − νs,a r

⩽P ⩽

⩾

2 Rmax log (2 |NR (θ)| /δ) 2n

δ |NR (θ)|

Applying a union bound over NR (θ), we get r max r∈NR (θ)

o νbs,a r − νs,a r

⩽

2 Rmax log(4Rmax /θδ) 2n

(27)

with probability at least 1 − δ. Now we can also apply Hoeffding’s inequality to the second term in equation 26. Recall that any reward function is bounded by Rmax . We have r brobT V − RrobT V R s,a s,a

⩽

2 Rmax log(2/δ) 2n

with probability at least 1 − δ. Combining equation 26 - equation 28 completes the proof.

(28)

Online Robust Reinforcement Learning Through Monte-Carlo Planning

From Lemma 10, we have

robT V robT V bs,a ⩾ 2θ + R − Rs,a

2 Rmax log(4Rmax /θδ)/2n < δ

(29)

p 2 log(4Rmax /θδ)/2n, then Set θ = ε/4 with ε = 2 Rmax 2 2 2nε2 /4 = Rmax log(4Rmax /θδ) ⇒ exp{−2nε2 /Rmax } = εδ/16Rmax

(30)

⇒δ=

2 16Rmax exp{−nε /2Rmax }

(31)

so that P

16R 2 2 max exp{−nε /2Rmax } robT V robT V bs,a R ⩾ε < − Rs,a ε

(32)

Lemma 11. (Lemma 9 (Panaganti et al., 2022)) Let Df be defined as in equation 18 with the convex function f (t) = (t − 1)2 corresponding to the Chi-square uncertainty set. Then inf o

Df (P ∥P )⩽ρ

EP [l(X)] = − inf

η∈R

ρ+1

EP o [(η − l(X))2 ] − η

Lemma 12. Fix any s, a ∈ S × A. For any θ, δ ∈ (0, 1) and ρ > 0, we have, with probability at least 1 − δ, we can find a constant N ⋆ such that ∀n ⩾ N ⋆ , we have √

robX robX bs,a − Rs,a R

2Cρ2 Rmax √ ⩽ 2θ + (Cρ − 1) n

log

2 (1 + Cρ Rmax / (θ (Cρ − 1))) δ

+1 .

Proof. Similar to Lemma 10, the result is direct by applying the results of Lemma 9, Lemma 11 and the law of total probability. From the results of Lemma 12, Then we have robX robX bs,a − Rs,a ⩾ 2θ P R √

2Cp2 Rmax √ Set θ = ε/4 with ε = 2 (Cp −1) n

√

2Cp2 Rmax √ + (Cp − 1) n

s 2(1 + Cp Rmax /(θ(Cp − 1))) +1 <δ log δ

(33)

r 2(1+Cp Rmax /(θ(Cp −1))) log + 1 , then δ

!2 √ (Cp − 1) nε 2(1 + Cp Rmax /(θ(Cp − 1))) √ −1 = log δ 2 2Cp2 Rmax   ! 2 √   (Cp − 1) nε δ √ ⇒ exp − −1 =   2(1 + Cp Rmax /(θ(Cp − 1))) 2 2Cp2 Rmax   ε(Cp − 1) robX robX bs,a ⇒P R − Rs,a ⩾ ε < 2 1 + Cp Rmax /( ) exp −  4

(34)

(35) √

(Cp − 1) nε √ −1 2 2Cp2 Rmax

!2   

Lemma 13. Consider an MDP with the Wasserstein distance DW . Fix any s, a ∈ S × A, we can derive o inf DW (P ∥P o )⩽ρ EP [l(X)] = − inf λ∈[0,Rmax /ρp ] (λρp −ER′ ∼νs,a [inf R′′ ∈R {R′′ + λdp (R′′ , R′ )}] . 18

(36)

Online Robust Reinforcement Learning Through Monte-Carlo Planning

Proof. Fix any (s, a) ∈ S × A. We have inf

DW (P ∥P o )⩽ρ

ER∼P [l(X)] = −

sup DW (P ∥P o )⩽ρ

ER∼P [−l(X)]

o = − inf ER′ ∼νs,a sup {−R′′ − λdp (R′′ , R′ )} + λρp λ⩾0 R′′ ∈R ′′ p ′′ ′ p o = sup ER′ ∼νs,a inf {R + λd (R , R )} − λρ ′′ (a)

R ∈R

λ⩾0

(b)

sup λ∈[0,Rmax /ρp ]

o R′ ∼νs,a

p inf {R + λd (R , R )} − λρ , ′′ ′′

′′

′

R ∈R

where (a) follows from ((Gao and Kleywegt, 2023) Theorem 1). For (b), let us first denote any optimizer in (a) to be λ∗ . Observe that since R is non-negative, it follows that

h i o o 0 ⩽ −λ∗ ρp + ER′ ∼νs,a inf′′ {R′′ + λdp (R′′ , R′ )} ⩽ −λ∗ ρp + ER′ ∼νs,a [R′ + λdp (R′ , R′ )] ⩽ −λ∗ ρp + Rmax R

where in the last inequality we use that the distance metric satisfies d(R, R) = 0, for any R ∈ R.

Lemma 14. (Covering number (Wasserstein)). Consider the following set of R|R| vectors: ( Uρ,R =

) T p inf {R + λd (R , 1)} , . . . , inf {R + λd (R , |R|)} : λ ∈ [0, Rmax /ρ ] ′′ ′′ ′′

′′

R ∈R

′′

R ∈R

Let ( Nρ,R (θ) =

where Nρ,θ =

T ) θ 2θ θ inf {R + λd (R , 1)} , . . . , inf {R + λd (R , |R|)} :λ∈ , , . . . , Nρ,θ , R′′ ∈R R′′ ∈R Bp Bp Bp ′′

Rmax Bp ρp θ

′′

and Bp = maxR′ ,R′′ dp (R′′ , R′ ). Then Nρ,R (θ) is a θ-cover of Uρ,R with respect to ∥ · ∥∞ ,

and its cardinality is bounded as |Nρ,R (θ)| ⩽ Rmax (Bp +ρp ) . ρp

Rmax Bp +(Rmax ∨ρp ) . Furthermore, for any ν ∈ Nρ,R (θ), we have ∥ν∥∞ ⩽ ρp θ

Proof. Fix any θ ∈ (0, 1). First note that Nρ,θ is the minimal number of subintervals of length Bθp needed to cover h [0, Rmax /ρp ]. Denote Ji = (i − 1) Bθp , i Bθp , 1 ⩽ i ⩽ Nρ,θ . Fix some µ ∈ Uρ,R . Then µ must takes the form µ=

T ′′ p ′′ ′′ p ′′ inf {R + λd (R , 1)} , . . . , inf {R + λd (R , |R|)} , ′′ ′′

R ∈R

for some λ ∈ [0, Rmax /ρp ]. Without loss of generality, assume λ ∈ Ji . Now we pick ν=

inf ′′

R ∈R

R′′ + i

T θ p ′′ θ p ′′ ′′ d (R , 1) , . . . , inf R + i d (R , |R|) R′′ ∈R Bp Bp

Fix any R′ ∈ µ and R′′ ∈ ν, we have 19

Online Robust Reinforcement Learning Through Monte-Carlo Planning

′

′′

′

inf {R + λd (R , R )} − inf ′′

|R − R | =

R′′ ∈R

R ∈R

(a)

λ−i

⩽ sup

R′′ ∈R

θ Bp

θ R + i dp (R′′ , R) Bp ′′

dp (R′′ , R′ )

θ θ max dp (R′′ , R′ ) = λ − i Bp ′ ′′ Bp R ,R Bp θ θ ⩽ (i − 1) Bp = θ −i Bp Bp ⩽ λ−i

where (a) is due to |inf x f (x) − inf x g(x)| ⩽ supx |f (x) − g(x)|. Taking maximum over R′ ∈ R on both sides, we get ∥µ − ν∥∞ ⩽ θ. Since ν ∈ Nρ,R (θ), this suggests that Nρ,R (θ) is a θ-cover for Uρ,R . To bound the cardinality of Nρ,R (θ), we consider two cases. If 0 < ρ < 1, then ρp θ < 1 and

Rmax Bp ρp θ

⩽

Rmax Bp Rmax Bp Rmax Rmax Bp + Rmax +1⩽ + p = ρp θ ρp θ ρ θ ρp θ

On the other hand, if ρ > 1, then since θ ∈ (0, 1), we have

Rmax Bp ρp θ

⩽

Rmax Bp Rmax Bp ρp θ Rmax Bp ρp Rmax Bp + ρp +1= + p ⩽ + p = p p p ρ θ ρ θ ρ θ ρ θ ρ θ ρp θ

Hence, we have |Nρ,R (θ)| = Nρ,θ ⩽ any R′ ∈ R,

Rmax Bp +(Rmax ∨ρp ) . Now we prove the last claim. Fix any ν ∈ Nρ,R . Note that for ρp θ

R′ = inf {R′′ + λdp (R′′ , R′ )} ⩽ Rmax + λBp ⩽ Rmax + ′′ R ∈R

Rmax Rmax (Bp + ρp ) B = p ρp ρp

The result then follows from taking maximum over R′ ∈ R on both sides. Lemma 15. Fix any (s, a) ∈ S × A. Let Nρ,R (θ) be the θ-cover of the set ( Uρ,R =

) T p inf {R + λd (R , 1)} , . . . , {R + λd (R , |R|)} : λ ∈ [0, Rmax /ρ ] ′′ ′′

′′

R ∈R

as described in Lemma 14. We then have sup λ∈[0,Rmax /ρp ]

o | ER′ ∼νs,a

′′ p ′′ ′ ′′ p ′′ ′ ′ o inf {R + λd (R , R )} − E inf {R + λd (R , R )} | R ∼b νs,a ′′ ′′

R ∈R

⩽

max r∈Nρ,R (θ)

o o νbs,a r − νs,a r + 2θ.

Proof. The proof is identical to the proof of Lemma 9. Lemma 16. Fix any (s, a) ∈ S × A. For any θ, δ ∈ (0, 1) and ρ > 0, we have the following inequality with probability at least 1 − δ

robW robW bs,a R − Rs,a

v u 2Rmax Bp +2(Rmax ∨ρp ) u ρp θδ Rmax (Bp + ρp ) t log + 2θ ⩽ ρp 2n

where Bp = maxR′ ,R′′ dp (R′′ , R′ ). 20

Online Robust Reinforcement Learning Through Monte-Carlo Planning

Proof. From Lemma 13 , we have

robW = Rs,a robW bs,a R =

sup

o ER′ ∼νs,a

λ∈[0,Rmax /ρp ]

sup λ∈[0,Rmax /ρp ]

′′ p ′′ ′ p inf {R + λd (R , R )} − λρ , ′′

R ∈R

o ER′ ∼bνs,a

′′

′

inf {R + λd (R , R )} − λρ

R′′ ∈R

Now it follows that robW robW bs,a =| R − Rs,a

sup

o ER′ ∼νs,a

λ∈[0,Rmax /ρp ]

−

sup λ∈[0,Rmax /ρp ]

o ER′ ∼bνs,a

λ∈[0,Rmax /ρp ]

o − ER′ ∼bνs,a

(b)

⩽

′′

max r∈Nρ,R (θ)

o | ER′ ∼νs,a

′′

′

inf {R + λd (R , R )} − λρ

R′′ ∈R

sup

(37)

R ∈R

(a)

⩽

′′ p ′′ ′ p inf {R + λd (R , R )} − λρ ′′

inf {R′′ + λdp (R′′ , R′ )} ′′

(39)

R ∈R

inf {R + λd (R , R )} | ′′

(40)

o o νbs,a r − νs,a r + 2θ

(41)

′′

′

R ∈R

where (a) follows from |supx f (x) − supx g(x)| ⩽ supx |f (x) − g(x)|. (b) follows from Lemma 15. R (B +ρp ) . Now we can apply Hoeffding’s inequality: Recall that all ν ∈ Nρ,R (θ) is bounded by νmax := max ρpp   2 2 2nε 2nε   o o P νbs,a r − νs,a r ⩾ ε ⩽ 2 exp − 2 = 2 exp − 2  , p νmax Rmax (Bp +ρ )

∀ε > 0

ρp

Now recall that |Nρ,R (θ)| ⩽

Rmax Bp +(Rmax ∨ρp ) and choose ρp θ

log (2 |Nρ,R (θ)| /δ) 2N

Rmax (Bp + ρp ) ε= ρp We then have

o o νbs,a r − νs,a r

(38)

Rmax (Bp + ρp ) ⩾ ρp

log (2 |Nρ,R (θ)| /δ) 2n

⩽

δ . |Nρ,R (θ)|

Finally, applying a union bound over Nρ,R (θ), we get v u 2Rmax Bp +2(Rmax ∨ρp ) u p t log p ρ θδ Rmax (Bp + ρ ) o o max νbs,a r − νs,a r ⩽ , ρp 2n r∈Nρ,R (θ) with probability at least 1 − δ. Combining the above and equation 41 completes the proof. 21

Online Robust Reinforcement Learning Through Monte-Carlo Planning

r p

2R (B +ρ ) Similarly, Set θ = ε/4 with ε = max ρp p

log

max Bp +2Rmax ρp θδ

2nε2 ρ2p exp − 2 4Rmax (Bp + ρp )2

√ p ρ

, then

ρp θδ √ = 2Rmax Bp + 2Rmax ρp √ p 4 (2Rmax Bp + 2Rmax ρ ) 2nε2 ρ2p ⇒δ= exp − 2 ρp ε 4Rmax (Bp + ρp )2

(42) (43)

so that P

√ p 4 (2R 2nε2 ρ2p max Bp + 2Rmax ρ ) robW robW b Rs,a − Rs,a ⩾ε < . exp − 2 ρp ε 4Rmax (Bp + ρp )2

(44)

C. Convergence of Robust-Power-UCT Multi-armed bandits α,β

Lemma 17. For m ∈ [M ], let (Vbm,n )n⩾1 be a sequence of estimator satisfying Vbm,n → Vm , and there exists a constant n→∞

L such that Vbm,n ⩽ L, ∀n ⩾ 1. Let Xi be an iid sequence from a distribution ν o with mean µ and Si be an iid sequence n = #|{i ⩽ n : from a distribution p = (p1 , . . . , pM ) supported on {1, . . . , M }. Introducing the random variables Nm n N1n N2n NM o Si = sm }|. Let us study a random vector pbn = ( n , n , ..., n ). We define an estimate of ν as n

ν o ≈ νbn =

1X δX , n i=1 i

where δXi is a point mass at Xi . And define RR = minr∼R ER∼r [R] w.r.t ν o and RR = minr∼R bn . We b ER∼r [R] w.r.t ν define the sequence of estimator b b n = RR + γσpbn (Vbn ). Q b

Then with 2α ⩽ β, β > 1, b n α,β Q → RR + γσp (V ). n→∞

PM Proof. Let p = (p1 , p2 , ...pM ), p ∈ △M where △M = {x ∈ RM : i=1 xi = 1, xi ⩾ 0} is the (M − 1)-dimensional simplex. Without loss of generality, we assume that pm > 0 for all m. Let us define V = (V1 , V2 , ...VM ). Let Vbn = PM n n b n ), (Vb1,N1n , Vb2,N2n , ..., VbM,NM i=1 Ni = n, Ni is the number of times that population i was observed. We have Qn = b RR + γσpb (Vbn ). Therefore, n

1 1 b R R R b b P |Qn − R + γσp (V ) | ⩾ ε ⩽ P |R − R | ⩾ ε + P |γσpbn (Vn ) − γσp (V )| ⩾ ε 2 2 1 1 b R R b ε . ⩽ P |R − R | ⩾ ε + P |σpbn (Vn ) − σp (V )| ⩾ 2 2γ | {z } | {z } A

(45) (46)

To upper bound A, • TV: A⩽

2 16Rmax exp{−n(ε/4)2 /2Rmax } ε/4

(47)

• Chi-square:   ε(Cp − 1) A ⩽ 2 1 + Cp Rmax /( ) exp −  4

!2  √  (Cp − 1) nε √ −1  2 2Cp2 Rmax

(48)

Online Robust Reinforcement Learning Through Monte-Carlo Planning

• Wasserstein: √ 4 (2Rmax Bp + 2Rmax ρp ) 2nε2 ρ2p A⩽ exp − 2 ρp ε 4Rmax (Bp + ρp )2

(49)

To upper bound B, let us consider σpbn (Vbn ) − σp (V ) = (σpbn (Vbn ) − σp (Vbn )) + (σp (Vbn ) − σp (V )). Then, 1 1 B ⩽ P σpbn (Vbn ) − σp (Vbn ) ⩾ ε + P σp (Vbn ) − σp (V ) ⩾ ε . 4γ 4γ {z } | {z } | B1

(50)

By applying results from Lemma 2 and Equation 8, we obtain • TV: B1 ⩽

16H exp{−n(ε/4γ)2 /2H 2 } ε/4γ

(51)

• Chi-square:   ε(Cp − 1) B1 ⩽ 2 1 + Cp H/( ) exp −  4

!2  √  (Cp − 1) nε √ −1  2 2Cp2 H

(52)

• Wasserstein: √ 4 (2HBp + 2H ρp ) 2nε2 ρ2p B1 ⩽ exp − ρp ε 4H 2 (Bp + ρp )2

(53)

For B2 , as the result from Lemma 1, we have σp (Vbn ) − σp (V ) ⩽ ∥Vbn − V ∥∞ ⩽ ∥Vbn − V ∥1 Therefore, M X

1 n − Vm | ⩾ ε B2 ⩽ Pr |Vbm,Nm 4γ m=1

! ⩽

M X

n − Vm | ⩾ Pr |Vbm,Nm

m=1

1 n ε|Nm 4γM

n Nm M X 1 X 1 n E P ε Nm ⩽ Vm,t − Vm ⩾ n Nm 4γM m=1 t=1 M X ε −β n −α ⩽ E c(Nm ) ( ) . 4γM m=1

Let us define an event E =

n Nm > np2m

(54)

(55)

(56)

. Therefore,

X M M X npm −α ε −β npm n B2 ⩽ E c( ) ( ) + E P(Nm ⩽ ) 2 4γM 2 m=1 m=1 M M X X pm n β −α −β n ) = (c2α+2β γ β p−α M )n ε + E P(N − p n ⩽ − m m m 2 m=1 m=1 M M X X pm n 2 β −α −β ⩽ (c2α+2β γ β p−α M )n ε + exp − 2n( ) m 2 m=1 m=1 Therefore, 23

(57)

(58)

(59)

Online Robust Reinforcement Learning Through Monte-Carlo Planning

• TV: 2 16Rmax exp{−n(ε/4)2 /2Rmax } 16H exp{−n(ε/4γ)2 /2H 2 } + ε/4 ε/4γ M M X X pm n 2 β −α −β + (c2α+2β γ β p−α ε + ) . exp − 2n( m M )n 2 m=1 m=1

A + B ⩽ A + B1 + B2 ⩽

(60) (61)

• Chi-Square:  !2  √   (Cp − 1) nε ε(Cp − 1) √ ) exp − −1 (62) A + B ⩽ A + B1 + B2 ⩽ 2 1 + Cp Rmax /(   4 2 2Cp2 Rmax  !2  √ M  X  ε(Cp − 1) (Cp − 1) nε β −α −β √ + + 2 1 + Cp H/( ) exp − −1 (c2α+2β γ β p−α ε m M )n   4 2 2Cp2 H m=1 (63) +

M X

exp

− 2n(

m=1

pm n 2 ) . 2

(64)

• Wasserstein: √ 4 (2Rmax Bp + 2Rmax ρp ) 2nε2 ρ2p A + B ⩽ A + B1 + B2 ⩽ exp − 2 ρp ε 4Rmax (Bp + ρp )2 √ p M X 2nε2 ρ2p 4 (2HBp + 2H ρ ) β −α −β (c2α+2β γ β p−α ε exp − + + m M )n ρp ε 4H 2 (Bp + ρp )2 m=1 M X pm n 2 + exp − 2n( ) . 2 m=1

(65) (66)

(67)

In both three cases, that leads to M X β −α −β b n − RR + γσp (V ) | ⩾ ε ⩽ O(exp{−n}) + O(e−1 exp{−cnε2 }) + P |Q (c2α+2β γ β p−α ε m M )n

(68)

m=1

M X m=1

exp

pm n 2 − 2n( ) 2

′

⩽ c n−α ε−β ,

(69)

′

with c > 0 depends on c, M, α, β, pi . Here we need 2α ⩽ β,

(70)

to argue that e−1 exp(−cnε2 ) = O(n−α ε−β ). Therefore, with n ⩾ 1, ε > 0, P

b n − RR + γσp (V ) Q 24

′ ⩾ ε ⩽ c n−α ε−β .

(71)

Online Robust Reinforcement Learning Through Monte-Carlo Planning

Furthermore, h i b n − RR + γσp (V ) lim E Q n−→∞ Z ∞ b n − RR + γσp (V ) ⩾ s ds P Q = lim n−→∞ 0  −α  Z n β Z +∞ ′ ⩽ lim  1ds + c n−α s−β  α n−→∞

n α

′

= lim

n− β + c n−α

= lim

n− β − c n−α

n−→∞

−

(72) (73) (74)

+∞ s−β+1 =0 +C α − −β + 1 n β α(β−1) !! n β = 0 (because α > 0, β > 1) −β + 1

(75) (76)

so that, b n ] = RR + γσp (V ). lim E[Q

n→∞

This means b n α,β Q → RR + γσp (V ), n→∞

which concludes the proof.

D. Convergence of Robust-Power-UCT n Monte-Carlo Tree Search α,β

Theorem 1. (Theorem 1 of Dam et al. (2024b)) For each arm a ∈ [K], let µ ba,n → µa and define µ⋆ = maxa {µa }. n→∞

Suppose arms are selected according to equation 4 with parameters (α, β, b, C), and let p ∈ [1, ∞). If 1 ≤ p ≤ 2, and α ≤ β2 , and

p > 2, 0 < α − βp < 1,

α 1 − αb ≤ b < α,

then there exists a suitable constant C (depending on K, b, α, p, ∆min ) such that α′ ,β ′

µ bn (p) → µ⋆ , n→∞

where ∆min = mina: µa <µ⋆ (µ⋆ − µa ), α′ = (b − 1) 1 − αb , and β ′ = (b − 1). H H Theorem 2. When applying Robust-Power-UCT with parameters {bi }H i=0 , {αi }i=0 , and {βi }i=0 satisfying Table 1:

(i) For any node sh at depth h ∈ {0, . . . , H}, αh ,βh Vbn (sh ) → Ve (sh ). n→∞

(ii) For any node sh at depth h ∈ {0, . . . , H − 1}, ,βh+1 b n (sh , a) αh+1→ e h , a), Q Q(s n→∞

∀ a ∈ Ash .

Proof. We follow the proof technique of Dam et al. (2024b, Theorem 2). Base Case (H = 1). Consider the root node s0 . Each time we visit (s0 , a), we collect: bsrob,a = • A reward sample rt (s0 , a) from the reward distribution νso0 ,a , which then leads to evaluating νbn and R 0 minr∈R b s ,a ER∼r [R], thus approximates the worst-case reward at (s0 , a). 0

Online Robust Reinforcement Learning Through Monte-Carlo Planning

• A next state s1 ∼ Pso0 ,a from M = |As0 | possible states (denote such states as S01 ). This then leads to pbs0 ,a , and bs ,a . captures the worst-case value from the transition ambiguity set P 0 By definition of the robust Bellman backup, recall e 0 , a) = Rsrob,a + γ σP Q(s Ve , s0 ,a 0 where Rsrob = min rs0 ,a ∈ Rs0 ,a E[r]. 0 ,a SinceH = 1, the next state s1 is treated as a leaf. We approximate Ve (s1 ) ≈ Vπ0 (s1 ), i.i.d. rollout returns under the policy π0 . By standard concentration bounds (e.g., Hoeffding), we obtain for all child nodes s1 ∈ S01 : α1 ,β1 Vbn (s1 ) → Ve (s1 ). n→∞

(77)

Next, recall by equation 3: b n (s0 , a) ← R brob + γσ b (VbT (n) ) Q s0 ,a s1 Ps ,a 0

Here Vb Ts1 (n) is the estimated value at all child nodes s1 ∈ S01 . By Lemma 17 and equation 77, it follows that 1 ,β1 b n (s0 , a) α→ e 0 , a). Q Q(s

n→∞

b n (s0 , a)}: Since s0 is the root node, we perform the power-mean backup on {Q Vbn (s0 ) =

X T (n) 1 s0 ,a b T (n) (s0 , a) p p . Q s0 ,a n a ∈ A s0

Under Theorem 1 (from Dam et al. (2024b) for robust settings), we conclude α0 ,β0 Vbn (s0 ) → Ve (s0 ). n→∞

This establishes both points (i) and (ii) at depth 0 and confirms the result forH = 1. Inductive Step (H > 1). Assume the theorem holds for all search trees up to depth H − 1. We now add one more level to create a tree of depth H. Let s1 be a child of the new root s0 . Then s1 itself is a root of a subtree with depth (H − 1). By the inductive hypothesis: α1 ,β1 2 ,β2 b n (s1 , a′ ) α→ e 1 , a′ ), ∀ a′ . Vbn (s1 ) → Ve (s1 ), Q Q(s n→∞

n→∞

At the new root s0 , we repeat the argument used in the base case: • Observing rewards rt (s0 , a) from νso0 ,a . • Transitioning under Pso0 ,a to state s1 . Hence, Lemma 17 again implies 1 ,β1 b n (s0 , a) α→ e 0 , a), Q Q(s

n→∞

and the power-mean operator at s0 yields α0 ,β0 Vbn (s0 ) → Ve (s0 ). n→∞

Thus, depth H inherits the same concentration property from depth (H − 1). This completes the inductive argument, establishing statements (i) and (ii) for any node at any depth ⩽ H.

Online Robust Reinforcement Learning Through Monte-Carlo Planning

Theorem 3. (Convergence of Expected Payoff) At the root node s0 , there is a choice of parameters yielding E Vbn (s0 ) − Ve (s0 ) ≤ O n−1/2 . Proof. By Jensen’s inequality (convexity of |x|), we obtain i h E Vbn (s0 ) − Ve (s0 ) ≤ E Vbn (s0 ) − Ve (s0 ) Z ∞ P Vbn (s0 ) − Ve (s0 ) ≥ s ds. = 0 α0 ,β0 Next, we split this integral at s = n−α0 /β0 . Using the concentration property Vbn (s0 ) → Ve (s0 ), we have n→∞

P Vbn (s0 ) − Ve (s0 ) ≥ s ≤ c0 n−α0 s−β0 , for s > n−α0 /β0 . Hence, α0

E Vbn (s0 ) − Ve (s0 ) ≤

Z n− β 0

Z ∞

−α0 −β0 α0 c0 n s ds − n β0 Z ∞ c0 n−α0 − α0 s−β0 ds n β0

1 ds + 0 α − β0

α − β0

≤ n

= n

∞ c0 α0 . n−α0 s−β0 +1 − β0 − 1 s=n β0 1

Because αβ00 ≤ 12 (see Theorem 1), the dominant term is O(n− 2 ). Thus, 1 E Vbn (s0 ) − Ve (s0 ) ≤ O n− 2 .

E. Experimental setup and Parameters selection E.1. Experimental setup All experiments are done over 100 seeds, using γ = 0.99 and robustness budget ρ = 0.5, with these values showing consistent performance across preliminary experiments with different parameter settings. We use 2000 rollouts for The Gambler’s Problem and 4000 rollouts for Frozen Lake. We implement our robust MCTS framework by extending a base Monte Carlo Tree Search implementation from (Leurent, 2018). Our codebase adds Stochastic Power UCT and introduces new robust backup operators for handling different uncertainty sets (Total Variation, Chi-squared, and Wasserstein), while maintaining the core MCTS selection and expansion strategies. We also provide our code at https://github.com/brahimdriss/RobustMCTS. E.2. Environments The Gambler’s Problem (Sutton and Barto, 2018): a classic casino-inspired reinforcement learning environment where an agent starts with an initial capital and aims to reach a specific goal amount through a series of betting decisions. In our implementation, the agent begins with 50 units of capital and must reach a goal of 100 units to win. At each step, the agent can bet any amount up to its current capital. The environment has a win probability ph for each bet, where the agent either wins the wagered amount with probability ph or loses it with probability 1 − ph . The state space consists of all possible integer capital amounts from 0 to 100, with 0 and 100 being terminal states. The action space at each state includes all possible integer bets up to the current capital. This environment is particularly suitable for studying decision-making under uncertainty as it combines both risk management and optimal stopping aspects. 27

Online Robust Reinforcement Learning Through Monte-Carlo Planning

In our experiments, to reduce computational complexity while maintaining the same fundamental dynamics and challenges, we scaled down the problem to use a starting capital of 5 units and a goal of 10 units. This smaller scale version preserves all the essential characteristics and decision-making complexity of the original problem. Frozen Lake(Towers et al., 2024): This environment presents a gridworld navigation challenge where an agent must traverse a 4x4 frozen surface from a starting position to a goal while avoiding holes. The surface is slippery, introducing stochastic dynamics where the agent’s intended actions may result in sliding to adjacent states with some probability. The state space consists of 16 discrete states representing different positions on the grid, with some states marked as holes (H) and one goal state (G). The action space includes four possible movements: left, right, up, and down. When the agent executes an action, it moves in the intended direction with probability 1/3 and slides perpendicular to the intended direction (left or right) with probability 2/3, making the environment highly stochastic. This environment is particularly valuable for evaluating robust policies as it combines both navigational planning and uncertainty in action outcomes. In our experiments, we define pslip as the probability that the executed action differs from the agent’s selected action. When a slip occurs, the actual executed action is sampled uniformly at random, effectively modeling the uncertain dynamics of the frozen surface. E.3. Robust Performance Results We investigate the impact of uncertainty budgets on agent performance in a modified gambler’s problem. In this experiment, we fix the planning probability ph at 0.6 , the ambiguity set at Wasserstein. The agent’s robustness is evaluated across different uncertainty budgets ρ ∈ {0.1, 0.3, 0.5, 0.7, 0.9}, where higher values of ρ correspond to more conservative policies. For each uncertainty budget, we assess the agent’s performance by varying the execution probability from 0.2 to 0.8, thus testing the policy’s robustness to model misspecification. This experimental design allows us to analyze how different levels of conservatism (controlled by the uncertainty budget) affect the agent’s ability to maintain performance when faced with discrepancies between planning and execution environments. Figure 3 demonstrate a clear trade-off between performance and robustness across different uncertainty budgets. Agents with lower uncertainty budgets (ρ = 0.1, 0.3) achieve better performance when the execution probability matches or exceeds the planning probability, but their success rate drops significantly in misspecified environments. In contrast, higher uncertainty budgets (ρ = 0.7, 0.9) show more consistent performance across different execution probabilities, particularly maintaining better success rates when the execution probability is lower than the planning probability. This suggests that while conservative policies might not achieve optimal performance in well-specified environments, they provide better robustness to model misspecification. The moderate uncertainty budget (ρ = 0.5) appears to offer a balanced trade-off, maintaining reasonable performance across both regimes. We now investigate a wide range of transition model ambiguities for the Frozen Lake environment. Table 4 provides an extended version of Table 2 with detailed success rates across different planning and execution probabilities. We observe that the performance of Stochastic-Power-UCT algorithm degrades faster for increased noise injection for slipping probabilities pslip . We again see Wasserstein robust MCTS does well across all planning versus execution phases. All robust MCTS variants outperform the baseline. Finally, our experiments reveal that the Wasserstein robust MCTS algorithm showcases the most robust performance across all variants. It might be of independent interest for future research to give a theoretical understanding of this phenomenon.

Online Robust Reinforcement Learning Through Monte-Carlo Planning

Uncertainty Budget Impact on Agent Performance 1.0

Success rate (%)

0.8

0.6

0.4

0.2

0.0 0.2

0.3

0.4

0.5

0.6

0.7

0.8

Execution p_h Stochastic-Power-UCT

Budget: 0.1

Budget: 0.3

Budget: 0.5

Budget: 0.7

Budget: 0.9

Figure 3: Performance comparison across different uncertainty budgets (ρ). Planning probability is fixed at ph = 0.6 (vertical dashed line), while execution probability varies from 0.2 to 0.8. Higher uncertainty budgets lead to more conservative policies, showing improved robustness when ph ⩽ 0.6 but potentially reduced performance when ph > 0.6.

Online Robust Reinforcement Learning Through Monte-Carlo Planning

Execution pslip

Planning pplan slip

0.1

0.2

0.3

0.4

0.5

0.0

Sp Tv Cs Ws

100 100 100 100

85 84 87 86

71 71 62 72

60 51 53 58

34 39 33 45

0.1

Sp Tv Cs Ws

65 68 95 97

52 54 82 84

41 42 65 68

32 33 52 55

21 24 35 38

0.2

Sp Tv Cs Ws

35 38 75 78

28 30 65 68

22 25 48 45

15 18 35 38

12 15 25 28

0.3

Sp Tv Cs Ws

15 18 55 58

12 15 45 48

10 12 35 32

8 10 25 28

7 8 18 20

0.4

Sp Tv Cs Ws

8 10 35 38

7 8 28 30

6 7 22 25

5 6 18 20

4 5 12 15

0.5

Sp Tv Cs Ws

5 6 25 28

4 5 20 22

4 4 15 18

3 4 12 15

3 3 8 10

Table 4: Success rates (%) for planning with Power-UCT variants. Methods: Stochastic-Power-UCT (Sp), Robust version with Total Variation (Tv), Chi-squared (Cs), and Wasserstein (Ws) ambiguity sets. Underlined values indicate matching planning and execution pslip . Bold indicates highest success rate per planning scenario.

Record · ID 965436 · SHA-256 0605491682bc3122
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.