Online Robust Reinforcement Learning Through Monte-Carlo Planning
Authors: Tuan Quang Dam
Kishan Panaganti
Brahim Driss
Adam Wierman
Venue: ICML 2025 poster (2025)
Keywords: Monte-carlo tree search
distributionally robust reinforcement learning
online reinforcement learning
Primary area: reinforcement_learning->planning
TL;DR: we provide monte-carlo tree search based planning algorithm for online robust RL problem

Abstract: Monte Carlo Tree Search (MCTS) is a powerful framework for solving complex decision-making 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 $\mathcal{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.

Online Robust Reinforcement Learning Through Monte-Carlo Planning
Tuan Dam Kishan Panaganti
Brahim Driss 3
Adam Wierman 2
Abstract
Search (MCTS) algorithm, in conjunction with deep learn- ing methods, solve complex decision- -ocision-making problems in high-dimensional environments. Its celebrated success sto- ries include autonomous RL decision-making agents play- ing board games Chess, Go, Shogi (Silver et al.] 2016) Schrittwieser et al., 2020). Poker (Brown and Sandholm 2018] Keshavarzi and Navidi] (2025), and solving vari- ous real-world challenging tasks like robotics and au- tonomous systems (Hoel et al.) 2019 Kartal et al. 2019 Dam al. 2022). MCTS offers a principled way to bal- ance exploration and exploitation by using combinatorial search mechanisms derived from online simulated trajecto- ries. As a result, MCTS can effectively promote the explo- ration of promising regions of the environment with only partial modeling information of the environment.
Monte Carlo Tree Search (MCTS) is pow- erful framework for solving complex decision- making problems, yet it often relies on the as- sumption that the simulator and the real-world dynamics are identical. Although this assump- tion helps achieve the success of MCTS in games like Chess, Go, and Shogi, the real-world scenarios incur ambiguity due to their model- ing mismatches in low-fidelity simulators. In this work, we present new robust variant of MCTS that mitigates dynamical model ambi- guities. Our algorithm addresses transition dy- namies and reward distribution ambiguities to bridge the gap between simulation-based plan- ning and real-world deployment. We incorpo- rate 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 11/2) for the value es- timation at the root node, comparable to that of standard MCTS. Finally, we provide empirical evidence that our method achieves robust perfor- mance in planning problems even under signifi- cant ambiguity in the underlying reward distribu- tion and transition dynamics.
However, most of these successes are limited structured or simulated environments. As successful as RL algorithms are, an issue in applying them to real-world dynamical sys- tems is the unavoidable discrepancy between the simula- tors and the actual real-world system dynamics. In tradi- tional RI. approaches (Kaelbling et al., 1996] Salvato et al., 2021), transition models are often learned from data col- lected by interacting with simulator models to avoid unsafe interactions with real-world systems, and reward models may be subject to stochasticity. hacked rewards, or unmod- eled external factors. Such ambiguities arise from a vari- cty of sources: limited training data, non-stationary envi- ronments, adversarial conditions, partial observability, or simply modeling simplifications. These factors can lead to so-called timulation-t--rellli gap, where the policy or value function that appears optimal in the simulated en- vironment may perform poorly when deployed in the real world. A natural approach to addressing these challenges is to incorporate robustness against cimulation-to-realle gaps directly into the planning algorithm.
1. Introduction
Reinforcement learning (RL) provides a statistical ma- chine learning framework to interact with the environ- ments-such as autonomous vehicles, agile robots, and net- work systemss-sequentall and learn to take control ac- tions to achieve the desired objective. Monte Carlo Tree
RL agents making decisions under the framework of Ro- bust Markov Decision Processes (RMDPs) (Tyengar 2005 Nilim and El Ghaoui 2005) offer 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 maxi- mize expected returns under the worst-case model within preseribed ambiguity set. The ambiguity set is typically constructed as a ball around the simulator dynamics
Equual contribution 'Hanoi University Science and Technology, Hanoi, Vietnam 'Department of Computing and Mathematical Sciences. California Insitte of Technology Pasadena, CA. USA 'Univ. Lille, Inria, CNRS, Centrale Lille, UMR 9189- CRIStAL. Correspondence to: Tuan Dam <tuandg@ wwiet.hust.cd...n..
Proceedings of the 1nnd International Conference 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 cov- ering the real-world ground truth model descriptors. Re- cent works demonstrate their potential to achieve robust becisinn-making performance when faced with perturba- tions 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 knowl- edge, we are the first to propose an (CCTS-basede algorithm for the robust RL problem. Our contributions are threefold:
Robust MCTS Algorithm: We solve the online robust RL mooblem-accoumee
for model ambiguity in both tran- sitions 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 finite- sample 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 oper- ators and the tree search mechanism by recasting robust MCTS for different ambiguity sets as collection of non- stationary multi-armed bandit problems.
In this work, we propose a novel robust MCTS algorithm equipped with non-asymptotic performance guarantees un- der model ambiguity set. Importantly, we incorporate both reward and transition ambiguity robustness, similar to re- cent works (Zhou et al., [2021] Wang et al., 2024b) in robust RL. In partieular, our work resolves the following ques- tions:
Can we use a search-based planning approuch like MCTS to balance exploitation and explo- ration for the robust RL problem? What theo- retical guarantee can provide? Can we show robust performance against standard algorithms under the simulation-to-relllee issue?
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.
Our approach embeds the distributionally robust optimiza- tion (Rahimian and Mehrotra 2019) mathematical princi- ple into the MCTS framework, ensuring that the value es- timates and action selections are robust to transitions and rewards drawn from the ambiguity sets. More precisely, we conceptualize a robust backup operator and design ex- ploration bonuses that accommodate ambiguity sets de- fined using total variation, Kullback-Leibler, chi-squared, or Wasserstein measures. This allows MCTS simultane- ously 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 allevi- ate environmental ambiguitics under the RMDP framework introduced by [yengar (2005); [ilim and El Ghaoui| (2005) considers distributional robust optimization (Rahimian and Mehrotra 2019) mathematical formularization. Many re- cent works extensively study the robust RL problem, ad- dressing multiple aspects of the challenges of decision- making learning algorithms. (Panaaani and Kalathil (2021 )
Zhou et al. (202I): Panaganti and Kalathil (2022):
: Shi
One of the key contributions of this work is the estab- lishment of sinite-sample bounds on the convergence rates of our robust MCTS algorithm. Viewing each node in the MCTS tree as 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 ro- bustness. 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 On -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
and Chi (2024) propose model-based dynamic program- ming algorithms solve the robust RL problem for finite action environments, and Dong et al.) (202); Pana- ganti et al. (2025) extend to the online and offline settings, respectively. These works focus on addressing the sam- plc complexity- minimal samples needed from the simu- lator model (leading to the construction of an approximate model) every value estimation -isute Panaganti and Kalathil (202T) panaganti al. (2022): Zhang al. (2023) propose model- free value function approximation based robust RL algo- rithms 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
every state-action pair to obtain an approximate
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 al.] 2024 Liu and
MCTS for non-robust RI.. AlphaGo-like (Silver et al.
Xu 2024). The incorporation of the strong sampling pro- cedure by MCTS avoids this issue.
2016) agents are powered by tree search mechanisms such as MCTS in traditional dynamic programming planning for
standard RL. Koesis and Szepesvári (2006); Shah et al.
3. Preliminaries
(2000); Dam al. (2024b) provide theoretical guarantees for such heuristic search-based deep RL algorithms. Re-
A Markov Decision Process (MDP) specified by the tuple (S, P. R), where S C R is the (potentially large) state space, A is discrete action space, P : S A + A(S) is the transition model mapping each state-action pair to a probability distribution over next states, and Rt : S x A + R is the (possibly uncertain) reward function assumed to be supported on a bounded interval [0, Rmax] A stationary policy и E (T( is defined as π : + A(A), meaning that at each discrete time step the agent observes a state St, samples
cently, the adoption of MCTS (Swiechowski et al. (023) in
other learning settings has seen scaling advantages. For in-
stance, in non-standard RL settings, like supervised learn- ing systems (Guez et al., [018 Wang et al. 2024a), con-
strained dynamical systems (Parthasarathy et al., 2023 Kurečka et al.] 2024) to promote safe decision-making choices, and partially observable and constrained dynam- ical systems (Lee et al., [0018] Daa et al. 2022] (020). In bandits, like agents taking decisions in the space of contexts (Ontanón 2013] Mao et al.) 2020). In applica- tions, like autonomous vehicles and robots, (Kartal et al.) 2019 Yin et al. 2022) where the imitation of expert deci- sions 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 con- vergence to true optimal values. Inspired by such adoption of MCTS, we enable MCTS-based planning for the first time the robust RL problem- pquilem-equipped with theoretical guarantees- that accounts for mitigating dynamical model ambiguities.
action O₂ .[- 8t), collects reward
rt ~ R(- 8t, (t), and transitions to 8t+1 ~ P(- 8t, ae).
We mention detailed notations used in this work in Table
3.1. Value Functions and Policies
We adopt discounted formulation with discount factor 7 E (0, 1). The state-value and state-action value functions of a policy π are given by
ViR(s) = Ei=o Bagnt [7're|
80 12/80- 8].
(1)
(p,((s,)) = D [
re 80 = 8, ag = a] (2)
The optimal state-value function is defined as V sup, (s) By definition and existence of deterministic optimal actions, the optimal stateaaction value function Q"
Search-based planning for online robust RL. This line of research closest to ours in terms of search-inspired algorithms. (Liu 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 power- ful 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 on- line sampling procedure by enabling search from a tree node-states and actions in dynamical systems-up up to some constant depth in the tree. Other works introduce sampling-based Q-learning (Zhou et al., [202 Liu et al.) 2022] Wang al., 2024b) and policy iteration (Panaganti and Kalathil [022 Kumar et al. 2023 Badrinath] [2023) inspired approaches. These popular methods in stan- dard online RI enabling vajectory-basee updates-aa at cur- rent states, actions, and next states sampled with an updated policy-to approximate the Bellman backups. However, these require algorithmic and thcoretical innovations for e.g., function approximation architectures-for scaling up
satisfies (s) = max, Q', (8, a) for each 8 E S.
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 time- varying. Let P and v denote the nominal transition prob- abilities and reward distributions, respectively, with each reward r(s, a) ~ ve... These nominal models can be either factory-set approximations a simulator of real-world sys- tems. Following Wang et al. (2024b); Zhou al. (202I): Liu et al. (2022), we allow the environment to deviate from (Po, (", within a robustness budget pT, PR respectively. This leads to a robust MDP that accounts for uncertainties in both transitions and rewards.
Ambiguity Sets. We model transitions in an ambiguity set P (s.a) Pr.s, where each Ps.o contains all plausi- ble distributions over next states from a). Analogously, ambiguity set R ((e,)) Re.a captures deviations in the reward distributions r(s, a). Here, with a chosen metric
3

---

Online Robust Reinforcement Learning Through Monte-Carlo Planning
D(+)).
where Rich min,,. E ER [ and op,.. (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.
Pa.a = Pana E ASS) D(Ps,as Po.0) S pr):
and
R3,a {veai Dive,s V2,0)= S PR).
MCTS a Robust MDP. In Monte Carlo Tree Search, we approximate a y-discounted solution by simulating tra- jectories down growing search tree. Each node corre- sponds to a state sh, with h indicating the depth in the tree (distance from the root). From S/ the algorithm either ex- pands a child node for the next state 81+11 or performs a rollout using a simpler policy To if h reaches the maximum search depth H. Trajectories terminate upon reaching depth H or a terminal state.
Different choices of D lead to distinct ambiguity sets, such total-variation balls (PTV), chi-squared neighbor- hoods (Px), or Wasserstein sets (PW). ). For notational con- venience, we denote the reward distributions Vs,a Ra,a also as their probability densities in the context of measur- ing distances :.:)).
4. Main Problem Formulation
Performance Measure. A canonical metric for MCTS algorithms is the convergence rale r(l), where / 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 T (*o) Q" (so: 2c) S r(1), or
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 modified so that each node's value estimate in- corporates worst-case rewards and transitions.
| (so) - [s0)) - r(t),
where ūz is the action chosen at the root after rollouts, and (s0) approximates (*(o)..
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 discrete, and the unknown reward r(s, a) and transition model P(. s, a, can lie within ambiguity set R and P (described in Section 3. At each step t, the agent ob- serves a state 8t, selects an action or E A, receives reward To, and transitions to a new state St+1- The ro- bust state-value and state-action value functions of a pol- icy ı are given by (s) = minpep, (s) and Q" (s,aa) a) minpeP.REx (s. respectively. pol- icy म² that maximizes the value function an optimal ro- bust policy with corresponding optimal robust value func- tions V* (s) and Q'(ssa). a). Hence, both transitions and re- wards may be adversarially perturbed, ensuring the agent plans robustly for worst-case scenarios within these sets.
Recursive Value Estimation Under Ambiguity. To cap- ture the robust (worst-case) aspect of the MDP, we define recursive estimation scheme at each node that accounts for inf R.. of reward and inf.er. transitions. Let sn be a node at depth h. We assign a robust value (s%) and robust action-value Q[sn, a) such that
((s Rrob + 7 To (V).
V(Sn) max a))
oEA
At leaf node (h = H), we approximate the value with a simple rollout policy To. yielding V(sH) R V (sH).
Goal of MCTS. Since finite sample sizes introduce noise, each node's robust value V(s)) is estimated from rollouts. The ultimate objective is to identify an action a, arg max, Q* a) at the root state sp within n sim- ulated trajectories, where Q* (50, a) represents the robust- optimal 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 re- spective ambiguity sets. From the robust MDP literature [Iyengar 20055 Liu et al., 2022), by the construction of P and R ambiguity sets, Q" is known to be computable, and thereby n² (8) argmax (s,
ān s arg max @(so. a), Vn(5o) ~ V(so),
with small statistical error. In Section we describe how
Let us define for any set B and vector (c) = inf v u B}. Robust dynamic programming, given by (s) = maxa (8, a) and
achieves this via specially de- signed backup operators and action-selection rules. Sec- tion 6 establishes finite-sample guarantees, showing that robustness in MCTS need not degrade convergence speed compared to its non-rofe non-robust counterpart.
(s) Reob yoP... (Vk),
4

---

Online Robust Reinforcement Learning Through Monte-Carlo Planning
5. Algorithm Description
Specifically, we maintain empirical estimate Qc(sn: a) for each action and add an exploration bonus of the form:
We now describe the core parts of our Robust-PPwer-Ocz 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.
(Tea, (t)
Pa+1
ahii Ph+1
(Ten,a(t))
where T,,, (t) is the total number of visits to Sn up to time t, and Tes (a) (t) is how often action a has been taken from but1 and 9a+1 control how aggressively Sh. The exponents Bh4: Bhaa
Table 1: Key Conditions for Algorithmic Constants (i E [0, H)
the algorithm explores, while C' is a user-chosen constant. the end of training (greedy mode), the action with the highest Q, is chosen.
Cond. Requirement
(1)
by < Oii and
b, > 2.
1 < 2
and
04 S
& 2
Main Loop and Rollout. As in standard MCTS, the al- gorithm repeatedly simulates from the root state So. select- ing actions according to the above scheme. When reaching a leaf node (unexpanded or maximum depth), a rollous pol- icy approximates the return from that leaf. These routines are routine and can be implemented similarly to classical MCTS methods.
(2)
or
(p> 2 and
3 2
0 < a; - & <1
(3)
0i b
bi < az.
(4)
0; (bi+1 1)
h+1
aitl
(5)
B. = (bi+1 - 1).
By combining an optimistic action selection mecha- nism with power mean and robust operator for value backup, Sobust-Power-Uose exploration of uncertain actions and exploitation of promis- ing ones, all under model ambiguity.
Value Backup. To estimate the value function at each node, we use a power mean backup operator. When node 9n is expanded in the tree, we define inductively for all t,
systematically balances
Ve(ss) = Σ
(t) t
[Ormalo(ssna) )
6. Theoretical Results
DEA.p
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 transi- tion ambiguity estimates. At each step, the empirical eval- uations shift, reflecting how robust exploration is balanced against uncertainty in the model. To handle this dynamic process, we begin by studying non-stationary multi- armed bandit froblem-focusing on how the pewer-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 2 1. This power mean backup places more em- phasis on actions that have high current value estimates (when p > 1), but still captures the contributions of other actions. Meanwhile Qt),.(t) (8)) a), or simply Qe(sh, a) as the root is Sh, itself is updated via
ac
Prob Po (Vr. (O).
where Prob min min,e R Enor [R] is empirical ro- bust reward at (sh, a). and (.).) is a robust operator cap- turing worst-case transitions for ambiguity sets governed by empirical estimates of nominal reward and transition models:
6.1. -tationaton Bandit Perspective
Po.a = (Pau E ASS): ((P..a Pa.)) & pr).
We first analyze Robust-Power--eeeee stationary multi-armed bandit setting. Here, actions are se- lected optimistically, and the power mean backup operator is used at the root node.
simpler non-
and
Rea = {uss E A(B): Div,,s Da,a) S p
6. 1.1.1 PROBLEM DESCRIPTION AND KEY DEFINITIONS
Action Selection. At each node 8ú in the search tree,
We consider a class of non-stationary multi-armed bandit (MAB) problems with K 2 1 actions (arms) with the re- ward E [0, R). Define sequence of estimator Pa,n (in this
PPoust-Power-Ocy selects an action a according to an optimistic rule that balances exploration and exploitation.
5

---

Online Robust Reinforcement Learning Through Monte-Carlo Planning
Algorithm I: Robust- with y discount factor. n : the number of rollouts. (h,, Oki, 8i are positive con-
stants that satisfy conditions in Table B is the total bins for [0, Rmax] To is a rollout policy, C' is an exploration constant.
Input: root node state 80
Output: optimal action the root node
Function R- Rollout (s, depth)
Function SimulateQ (8h; a, depth h,
(s) average of the call to (s)s))
S141 (-
return (s)
T(5h, Ven.o
if 88+1 & Terminal and depth & H - 1 then if Node 8h+1 not expanded then
Function = SelectAction (Sk, depth falsc, L)
h, greedy
if greedy false then
(0(+11) Rol1 oot (#a+1, depth)
hb-1 a= = arginax (0 -- Top (1) Ph+t
else
SimulateV 10-11,epple h 1, end end
(o)) Ph+zs
else
argmax Qra
Find
jE B.t. r(sh, a) E Bin Rmax]
Den.a()) = 3n (0)+1
end
Do (8h-1) Prp.a(ent))) ((n)))
return a
(0++1
Function SimulateV (sh, depth,
Ton (t) t (t) +1
4 eeeeectctiinnns depth- h, greedy = false, t) SimulateQ (8h, a, depth- 1)
Qr, (l)) (56. 4- Reob + +.0 (Vi (1)
Te, (1) t To, (1) +1
Function Ma Mainloop
+ (Za T!) Top
(Qro (())) 1
For = 0....
SimulateW (No, depth = 0,
return Select (50, greedy true, n)
paper is the robustness estimation of the mean value of arm a) such that po,n E [.e.n] We are interested in se- quence of estimators that satisfy suitable concentration property:
(m))))))))) By applying Theorem of Dam et al. (2024b), we get (p) o' n-c0 Me, where a' = (b 1) 2), and G' (b 1b-11 1).
Σ Da=1
Ta(n)
Definition (Concentration). A sequence of estimators (Yn)22 concentrates at rate (a, 3) toward a limit Y, writ- ing as Yn anf Y, there is a constant c >> O such that n
Connecting Back to MCTS. This bandit analysis under- pins how Robust -ontt-Pone Poeestt-ooweretee handles exploration and the power mean backup. In an MCTS context, each node's s local bandit analysis is augmented by worst-case backups, but the principle is similar: the algorithm discards subopti- mal branches with high probability, causing the robust es- timates to concentrate around the best actions.
nn 1, VE > n 9, Pi > 2) S en - eP.
Assumption 1 (Non-Stationn Statinaai Rewards). For each arm a E [K], the sequence (Pem))21 concentrates at rate (), toward a value Ha- i.e. Pa.n n-00 m (pol. assumed to be unique with a strict gap from suboptimal pa-
ai
Pa. Let u.. =
6. 6.3. MAIN CONVERGENCE RESULTS
Before presenting the main result (Theorem 3 we first show an important lemma used for our MCTS algorithm.
6.1.2. OPTIMISTIC ACTION SELECTION AND POWER MEAN BACKUP
Lemma 17. For m E [M], let (Vm.))oz) be a sequence of estimator satisfying Vm.. axe Vmn and there exists a n-000 constant L such that Vm... < L. > L. Let X₃ be an iid sequence from distribution v" with mean μ and S; be an tid sequence from distribution
Under Assumption we use an optimistic exploration rule similar to Robust- -2 Power-UCT. Let T. (n) be the num- ber of times arm a is pulled before time n. The algorithm pulls each arm once initially. For n > K:
(pi,..., sup- ported on {1,..., MY. Introducing the random variables N = #1ii < n : S, sm)l. Define a model estimate of as Pn No. No Ni.) We define an estimate of u
an = arg max (M.TT.(m) + C n Cn*/TTam)) (T.() aE|K]
(4)
as D/ = L - 6x. Recall Rlob = min ER-r [R]
where b > and b < a. For the power mean operator, let p E (1) and define (p(
w.t. v and Rrob min En [R] want Dy, We define
6

---

Online Robust Reinforcement Learning Through Monte-Carlo Planning
the sequence of estimators
Remark 2. These results show that both Robust-Power-UC. and standard (non-robust) MCTS achieve the same ((n11/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 de- codable (thereby not comparable other online robust RL. results (Dong et al. 2022 ) due to our analysis limitations.
Qn =Rrob + +100% (V.).
Then with 2a & 3, > 1, On n-200
af Rrob + (V))
Remark 1. This non-asymptoric convergence result shows that, for suitable purameters (a, B), the estimator Qn will concentrate around the limiting quantity R + (VV with high probability. Importantly, we do not claim these (a.3) are in any sense optimal; rather, only need the existence of such parameters that guarantee the concen- tration at the prescribed rate. Moreover, our analysis uses covering number generalization to handle continuous re- ward distributions. Furthermore, the constant e implicit in the notation Vn2 a.g V can depend on groblem-dependen n-
7. Experiments
We evaluate Robust Pooesttt-oww--CCC in three distinct envi- ronments designed to test different aspects of robust plan- ning: the Gambler's Problem, Frozen Lake, and Ameri- can Option Pricing. For each environment, Miochastic-Poee--UC (Dam et al., 2024b) (baseline) and Robust-Power-Ut with Total Variation, Chi-squared, and Wasserstein ambiguity sets.
factors (e.g., size of the action set A, number of states S. etc.), reflecting the stochastic process complexity.
compare:
6.2. Tree-Level Convergence
The above non-stationary bandit analysis is critical for proving the subsequent tree-level theorems. In particular, Theorem 2 (restated below) shows that under appropri- ate parameter settings (Table []. the estimated node values (-) and (n)-.)) converge at a known rate:
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 p 0.5, with these values showing con- sistent performance across preliminary experiments with different parameter settings. For concise presentation, we only experiment with transition model ambiguity just as prior robust RL works.
Theorem 2. When applying Robust CeaisstPoon UUT with parameters {b.) {ar) {8 satisfying Table 7
(i) For any node st at depth h E {O....,Hy H},
(a() Sn V(n)).
Full experimental details, environment descriptions and hy- perparameter configurations are provided in Appendix [ along with an additional analysis of the robustness budget. We also provide our code at https: //ts:///tttht com/ brahimd modiiirrsss...... RobustMMTS
(ii) For any node sy at depth h E :o...... H 1).
Qn(sn, a)
antigh+t as),,)), Aa A... n-
Remark 3. While the robust Bellman operator involves solving a minimization problem over probability distribu- tions, we can leverage dual reformulations to make its computation tractable. Many prior works (Iyengar 2005 Nilim and El Ghaoui 2005 Xu el al. 2023) show, for a value function V and nominal distribution po, the robust value under all ambiguity balls with radius pr can be com- puted in most O log(S)) time. Thus requiring only marginally more computation than standard Bellman op- erators 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, note that descending into child node effectively reduces the depth by one, thus the induction hypothesis applies. By carefully controlling ex- ploration (S and using robust backups, each node's s V and Q estimates concentrate at the specified rates. LI
Finally, Theorem 3 establishes that under optimal param- eter tuning, the expected payoff at the root converges at On
7.1. Gambler's Problem Robustness Results
Theorem 3. (Convergence of Expected Puyoff) At the root node 8o, there a choice of parameters yielding
The Gambler's Problem provides an ideal testbed for evalu- ating robustness to model misspecification. An agent must reach a target capital through a series of bets, with each
E [50o] - V(80)) S Onn
7

---

Online Robust Reinforcement Learning Through Monte-Carlo Planning
Planning with p_h 0.4
Planning with p.h = 0.6
Planning with h 0.8
1.0
10
1.0
0.8
0.0
0.8
Suicesss rate (%)
0.0
Successs rale
0.0
0.0
0.4
0.4
0.44
0.2
0.2
0.2
0.0
0.0
0.0
Execution puh
Execution p_h
Execution p.h
Stochastic Power
Power MCTS (TV)
Robust Power-UCT MCTS (Chi?)
Robust
Babber Power-UCT MCTS (Wasserstein)
Figure 1: Success rates 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 Stochastic-Power-UCT
bet winning with probability Pa- This enables precise con- trol of the planning-execuee execcutinn mismatch through single parameter.
proaches.
Both Wasserstein and Chi-squared variants outperform the baseline Poohastic-Power-UCT and Total Variation ap- proaches. Interestingly, when planning and execution prob- abilities align (underlined values). both robust variants maintain superior performance compared to standard ap- proaches. This suggests that explicitly accounting for un- certainty in the planning process provides benefits even without model mismatch, possible by encouraging more conservative and reliable decision maasinn strategies.
Figure [ illustrates the performance of different Power- UCT variants under model mismatch in the Gambler's Problem. The behavior of Peachastti--Poee-UCCT reveals fundamental vulnerability; when ps 0.5, there exist mul- tiple optimal policies that achieve winning ratios close to the true environment probability. However, when planning with Ps > 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 mechanism for bal- ancing conservatism against nominal performance.
The superior performance of robust variants stems from their conservative betting strategies. While Stochastic- Power-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 do- main 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 uncer- tain parameter being the probability Pu of price increases at each time step.
The Frozen Lake environment tests robustness in different complex setting where uncertainties compound over multi- ple steps. The agent must navigate to goal while avoid- ing hazards, with actions potentially failing with probabil- ity Palip-
different planning and exccution probabilities. With matching con- ditions (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 Palip 0.3, it achieves 58% success when Pexec 0.1, significantly outperforming other ap-
Table [ provides detailed success
Figure 2 demonstrates the reward robustness of different Power- UCT variants under model mismatch in option pric- ing scenarios. We examine two planning scenarios: training with P. = 0.5 (left panel) and Pa = 0.6 (right panel), then testing across execution probabilities from 0.4 to 0.8.
The results reveal that robust variants maintain significantly more stable performance compared to standard Power- UCT. When planning with p.. 0.5, the standard approach shows dramatic performance degradation the test prob- ability deviates from the planning assumption, dropping
8

---

Online Robust Reinforcement Learning Through Monte-Carlo Planning
Training with p
Training with p_u 0.6
Mean Reward
Mean Reward
Test 0.5
3.70
Test
Power MCTS (Standard)
Robust Power MCTS (TV)
Rebust Power MCTS (Chit)
Robust Power MCTS (Wasserstein)
Figure 2: Reward robustness comparison in American Option pricing under model mismatch. Results show planning with fixed price-up probabilities Pa {0.5, 3.6} while testing across different probabilities. Robust variants maintain signif- icantly more stable performance compared to standard Power-UCT, demonstrating consistent risk-averse behavior that particularly valuable in financial decision-making contexts where reliability is crucial.
Planning
Execution Pslip
nancial contexts where consistent performance is preferred over potentially high but unreliable returns.
plan Pallp
0.1
0.2
0.3
0.4
0.5
The Wasserstein and Chi-squared ambiguity sets show par- ticularly strong performance, maintaining steady rewards even under significant model mismatch, demonstrating that explicitly accounting for uncertainty leads policies in- herently robust different deployment conditions.
Sp
15
12
10
8
Tv
18
15
12
10
8
0.3
Cs
55
45
35
25
18
Ws
58
48
32
28
20
Sp
8
7
6
5
Tv
10
8
7
6
8. Conclusions
0.4
Cs
35
28
22
18
12
Ws
38
30
25
20
15
We have developed a robust variant Monte Carlo Tree Search (MCTS) that addresses dynamical model and re- ward distribution ambiguities, bridging gap between simulation-based planning and real-world deployment. The dependence of MCTS-based algorithms' convergence rates parameters (states S, actions A, depth H) remains un- derexplored 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, the future, we will explore alternative robust formulations that are more permeable less conservative solutions address the simulation-to-reality gap.
Sp
5
4
4
3
Tv
5
4
0.5
Cs
25
20
15
12
8
Ws
28
22
18
15
10
Table 2: Success rates (%) for planning with Power-UCT variants. Methods: Stochastic-Power-Uu version with Total Variation (Tv), Chi-squared (Cs), and Wasserstein (Ws) ambiguity sets. Underlined values indi- cate matching plamning and execution Pelip- Bold indicates highest success rate per planning scenario.
(Sp), Robust
Impact Statement
from approximately to near when P.. = 0.8. In contrast, robust variants maintain consistent performance across the entire range.
This paper presents a novel algorithm for the robust rein- forcement learning field using the Monte Carlo Tree Search planning mechanism. There are many potential societal consequences of our work, none of which feel must be specifically highlighted here.
When planning with P., 0.6, standard Power-UCT ex- hibits extreme sensitivity with dramatically varying perfor- mance. The robust variants demonstrate desired risk-averse behavior: achieving conservative but stable returns across all conditions. This stability especially valuable fi-

---

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, Pro- ceedings of the 38th International Conference on Ma- chine Learning, volume 139 of Proceedings of Machine Learning Research, pages 2365-2375. PMLR, 18-24 Jul 2021. URL httpthtttt///cceeeeeeess v139/dam211 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 Insti- tute and the 'PIMCO Postdoctoral Fellow in Data Science' fellowship at Caltech. B. Driss was funded by the project ANN-233CE23-0006. A. Wierman acknowledges support by the NSF through (NSS21468114 14, CPS-2136197, CNS- 2106403, and NGSDI-2105648. This work was granted ac- cess to the HPC resources of IDRIS under the allocation 10055599 made by GENCI.
mlr pttpp/sssr.pppr.///mmpm
Jing Dong, Jingwei Li, Baoxiang Wang, and Jingzhao Zhang. Online policy optimization for robust mdp. arXiv preprint arXiv:2209. 2022.
Nicolas Fournier and Arnaud Guillin. On the rate of con- vergence in wasserstein distance of the empirical mea- sure. 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. Math- ematics 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 4244,,444220004 2018.
Michael B Giles. Multilevel monte carlo path simulation. Operations research, 56(3):607-617, 2008
Imre Csiszár. Eine informationstheeortishhe ungleichung und ihre anwendung auf den beweis der ergodizität von markoffschen ketten. A Magyar Tudományos Akadémia Matematikai Kutató Intézetének Közleményei, 8( 8(1-2)855- 108, 1963.
Arthur Guez, Théophane Weber, Joannis Antonoglou, Karen Simonyan, Oriol Vinyals, Daan Wierstra, Rémi Munos, and David Silver. Learning to search with met- snets. In International conference on machine learning, pages 1822-1831. PMLR, 2018
Tuan Dam, Pascal Klink, Carlo D' Eraamo, Jan Peters, and Joni Pajarinen. Generalized mean estimation in monte- carlo tree search. In Christian Bessiere, editor, Pro- ceedings of the Twenty-Ninth International Joint Con- ference on Artificial Intelligence, IJCAI-20, pages 2397- 2404. International Joint Conferences on Artificial Intel- ligence Organization, 7 2020. doi: 10.24963/ijcai.20000 332. URL http::: https///aol.ccg/1..222//////////
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 Wolff, Leo Laine, and Mykel J Kochenderfer. Combin- ing planning and deep reinforcement learning in tactical decision making for autonomous driving. IEEE transac- tions on intelligent vehicles, 5(2):294-305, 2019.
Krister
2020 332
Main track.
Tuan Dam, Georgia Chalvatzaki, Jan Peters, and Joni Pa- jarinen. Monte-carlo robot path planning. IEEE Robotics and Automation Letters, 7(4): 1211111122200 2022.
Garud N Iyengar. Robust dynamic programming, Mathe- matics of Operations Research, 30(2):257-280, 2005.
Tuan Dam, Carlo D' D'Eramo, Jan Peters, and Joni Pajari- nen. A unified perspective on value backup and explo- ration in monte-carlo tree search. Journal of Artificial In- telligence 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, Odalrie-Ambrym Maillard, and Emilie Kaufmann. Power mean estimation in stochas- tic monte-carlo tree search. In Negar Kiyavash and Joris M. Mooij, editors, Proceedings of the Fortieth Conference on Uncertainty in Artificial In- telligence, volume 244 of Proceedings of Machine PMLR, 15-19 mir.
Bilal Kartal, Pablo Hernandez-Leal, and Matthew E Tay- lor. Action guidance with mets for deep reinforcement learning. In Proceedings of the AAAI conference on ar- tificial intelligence and interactive digital entertainment, volume 15, pages 153-159, 2019.
Learning Research, pages
Behbod Keshavarzi and Hamidreza Navidi. Comparative analysis of extensive form zero sum game algorithms for poker like games. Scientific Reports, 15(1):2917, 2025.
Jul 2024b. URL press/v245 4/dm224442222m 4a. html
10

---

Online Robust Reinforcement Learning Through Monte-Carlo Planning
Levente Koesis and Csaba Szepesvári. Bandit based monte-carlo planning. In European conference on chine learning, pages 282-293, Springer, 2006.
provable performance guarantees. In International Con- ference on Machine Learning, pages 511-520. PMLR, 2021.
Navdeep Kumar, Esther Derman, Matthicu 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 complex- ity of robust reinforcement learning with a generative model. In International Conference on Artificial Intelli- gence and Statistics, pages 9582-9602. PMLR, 2022.
Martin Kurečka, Václay Nevyhošténý, Petr Novotný, and Vít Unčovský. Threshold uet: Cost-constrained monte carlo tree search with pareto curves. arXiv preprint arXiv:241..13922, 2024.
Kishan Panaganti, Zaiyan Xu, Dileep Kalathil, and Mo- hammad Ghavamzadeh. Robust reinforcement learning using offline data. Advances in Neural Information Pro- cessing 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 Sys- tems, 31, 2018.
Kishan Panaganti, Adam Wierman, and Eric Mazumdar. Model-free robust g-divergence reinforcement learning using both offline and online data. ICML, arXiv preprint 200505240 2024.
Edouard Leurent. rl-agents: Implementations of rein- forcement learning algorithms. https://githut com/ell hwmm/llereet//ee -ragetsss 2018.
Kishan Panaganti, Zaiyan Xu, Dileep Kalathil, and Mo- hammad Ghavamzadeh. Bridging distributionally robust learning and offline rl: An approach to mitigate distribu- tion shift and partial data coverage. Learning for Dynam- ics and Control Conference, 2025.
Zhishuai Liu and Pan Xu. Distributionally robust off- dynamies reinforcement learning: Provable efficiency with linear function approximation. In International Con- ference Artificial Intelligence and Statistics, pages 2719-2727, PMLR, 2024.
Dinesh Parthasarathy, Georgios Kontes, Axel Plinge, and Christopher Mutschler. C-mets: Safe planning with monte carlo tree search, arXiv preprint arXiv:2305. 2023.
Zijian Liu, Qinxun Bai, Jose Blanchet, Perry Dong, Wei Xu, Zhengqing Zhou, and Zhengyuan Zhou. Distribu- tionally robust q-learning. International Conference on Machine Learning, pages 13623-13643, PMLR, 2022.
Hamed Rahimian and Sanjay Mehrotra. Distribution- ally robust optimization: A review. arXiv preprint arXiv: 1908.05690 2019.
Erica Salvato, Gianfranco Fenu, Eric Medvet, and Fe- lice Andrea Pellegrino. Crossing the reality gap: A sur- vey 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-asympiotic analysis. Advances in Neural Information Processing Systems, 33:4549-4559, 2020.
Julian Schrittwieser, Ioannis Antonoglou, Thomas Hu- bert, 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 trices. Operations Research, 53(5):780- 2005.
Santiago Ontanón. The combinatorial multi armed bandit problem and its application to real-time strategy games. In Proceedings of the AAAI Conference on Artificial Intelli- gence and Interactive Digital Entertainment, volume 9, pages 58 64, 2013.
Devavrat Shah, Qiaomin Xie, and Zhi Xu. Non- asymptotic analysis of monte carlo search. In Ab- stracts of the 2020 SIGMETRICSPerfomanc Joint In- ternational 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:7816 181 1811992 2023.
Laixi Shi and Yuejie Chi. Distributionally robust model- based offline reinforcement learning with npar-optimal sample complexity. Journal of Machine Learning Re- search, 25(200): 2024.
Kishan Panaganti and Dileep Kalathil. Robust reinforce- ment learning using least squares policy iteration with

---

Online Robust Reinforcement Learning Through Monte-Carlo Planning
David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrit- twieser, loannis Antonoglou, Veda Panneershelvam, Mare 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. Ad- vances in Neural Information Processing Systems, 35: 2577-2589 2022.
Runyu Zhang, Yang Hu, and Na Li. Regularized bust mdps and risk-sensitive mdps: Equivalence, pol- icy gradient, and sample complexity. arXiv preprint arXiv:2306. 1626, 2023.
Richard S Sutton and Andrew G Barto. Reinforcement learning: an introduction, 2nd edn. adaptive computation and machine learning, 2018.
Maciej Swiechowski, Konrad Godlewski, Bartosz Saw- icki, and Jacek Mańdziuk. Monte carlo tree search: A review of recent modifications and applications. Artificial Intelligence Review, 56(3):2497-2562, 2023.
Zhengqing Zhou, Zhengyuan Zhou, Qinxun Bai, Linhai Qiu, Jose Blanchet, and Peter Glynn. Finite-sample re- gret bound for distributionally robust offline tabular rein- forcement learning. In International Conference Artifi- cial Intelligence and Statistics, pages 3331-3339. PMLR, 2021.
Mark Towers, Ariel Kwiatkowski, Jordan Terry, John U Balis, Gianluca De Cola, Tristan Deleu, Manuel Goulão, Andreas Kallinteris, Markus Krimmel, Arjun KG, et al. Gymnasium: A standard interface for reinforcement learning environments. arXiv preprint arXiv:2407.1703: 2024.
Jie Wang, Rui Gao, and Yao Xie. Regulariza- tion for adversarial robust learning. arXiv preprint 0tti:2408.09672., 2024a.
Shengbo Wang, Nian Si, Jose Blanchet, and Zhengyuan Zhou. A finite sample complexity bound for distribu- tionally robust q-learning. In International Conference on Artificial Intelligence and Statistics, pages 3390-3398. PMLR, 2023.
Shengbo Wang, Nian Si, Jose Blanchet, and Zhengyuan Zhou. Sample complexity of variance-reduced distribu- tionally robust q-learning. Journal of Machine Learning Research, 15(34)):1-77,
2024b. 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 Mci, Dale Schuurmans, and Martin Müller. Maximum entropy monte-carlo planning. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc Buc, E. Fox, and R. Gamett, editors, Advances in Neural Information Process- ing Systems, volume 32. Curran Associates, Inc.,
2019. URL http:::/procedddssssnn neurips. cc /t//ppperff.leee//ppe///////////
FFbbe0eee00760335051162222233333 Paper pdf
Zaiyan Xu, Kishan Panaganti, and Dileep Kalathil. Im- proved sample complexity bounds for distributionally ro- bust reinforcement learning. In International Conference on Artificial Intelligence and Statistics, pages PMLR, 2023.
12

---

Online Robust Reinforcement Learning Through Monte-Carlo Planning
A. Notations
Notation
Description
S. A
State space and action space of the MDP. Planning horizon (depth of the search tree).
H
(s.a)
A specific state action pair: S. E .A.
[M]
Denotes the { 2, 2.,...,,MM., ,..
Ve.
Nominal (truc) reward distribution for statc-action pair (s, a).
Ve,a, Da.a
Generic and empirical reward distributions for (s, a), respectively.
Rmax
Maximum possible reward value (i.e., reward is supported in [0. Rmax)).
(P(P
f-divergence between distributions P and pe, for convex f()).
P.Y. P PW
Uncertainty sets under Total Variation, Chi-square, and Wasserstein distances, respectively. Worst-case value operator (or "robust backup") over uncertainty set P....
OP..o (V)
p
Radius (budget) for the uncertainty set in f-divergence Wasserstein distance.
gg. (V.)
Robust backup operator with the empirical transition P., as the set center for empirical value V...
By
Constant bounding the metric space for Wasserstein distance (e.g. max distance d²)..
a' a,,""
Dual variables optimizing robust reward functions under TV uncertainty sets.
A(X)
Probability simplex over the support of set or size of X.
(R(
8-cover set used for bounding the supremum of (1) R)+ in total-variation analysis.
Infinity norm (maximum absolute value in vector) and & norm (sum of absolute values in voctor). A point Parameters often controlling confidence levels or approximation accuracy in concentration bounds. Constants from generic concentration or covering-number arguments (possibly problem-dependent) Used for i.idd sampling from a discrete distribution (pI,..., Par), with N the count of outcomes of type m. Estimated and true robust Q-values, respectively.
realization æ.
8,0,s
C
Nm
Qn.Q² Q"
V.. V
Estimated true robust value functions, respectively. Discount factor in the MDP.
W(Hn.H) 2g
Wasserstein distance between empirical measure 14n and true measure μs.
Notation concentration at rate (a, (); see text for precise definition.
Table 3: Key Notations Used in the Appendix. Symbols and definitions for uncertainty sets (TV, x², 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. E S x A and for any V1, V/2 plsl, have
|or, (Vi) o.,. (V2) < V V2lloo and p.... (V)
p. (V22 & [|V - V2ll
Lemma (Proposition Xuu et al. 2023)) Fix any h, 8.a E [H] S x A. For any 0,5 E (0, 1), we have with the probability of at least 1 pryx (Vn+1)= pry (Ve+1)
20 + / H2 log( 44//6))/2m
From Lemma
2 we have
Opppy (Vn+1) Pay (va+z) > 20 + /H² log( (H/44)
(5)
Set 0 = e/4 with E = 2 H2 log 4H 1H/88 /2m, then
2n /4 = 2² log = exp( sepp-2nn='
2n 2 H2 = e8 16H
(6)
16H exp( n 22H2)
+ 8 =
so that
16H exp{-nE? /2H²
(Oppy (Vn+1) - o pry
(V (h+1)
25)
(8)
Lemma 3. (Proposition 4 Xu et al.
2023)) Fix any h 2.8. E [H] x S x A. For any 0,5 E (0. 1), we have with the
probability of at least 1 5, |oyx (Vn+1)=
px (Vn+1))
< 20 +
V203H
(vi08
2(1+C,
(C,-lyn
13

---

Online Robust Reinforcement Learning Through Monte-Carlo Planning
Then have
P Plappx (Va+1)-0u -or (Vh+1)) E 20
H
2(1 + C,H - 1)11 -111)
+1) <d 99)
(Cp - 1)v (1/00
8
v20311 Set 0 =/4 with = (C,(c-)) (V108
2(,,-111
(20+CHH/00(G,111) +1). then
C - 1)ynE -1) -1)= loog
2(1 + C2Hl/(0CC, - 1)))
(10)
2v 2/202H
(Cp- (1 -IVEE -1 1
8 2(1 CpHl/(0(C, 1))))
exp
(11)
2V/02H
P (opx (Vh+1)
fex (Vntz) EE)
(12)
(Cp [Gp-11 1) TE -11 )}
2 1 1+ (
exp
(13)
4
2//02211
Lemma 4. (Proposition (Xu et al. 2023)) Fix any h, s,a E [H] S A. For any 0,6 8 E (0, 1). we have with the
probability of at least 5, poy. (V++1)= - oow (Pn+1)
< 20 +
B +p)
log
2n
Similarly, Set E/4 with (B,
log
2p 62.55
then
2n p2P
8088
exp
(14)
(B + pp)2
2HB, + 2H pp
4 B,H + 2H vPn)
2ns² p2P
+ 8
exp
(15)
PPE
*HH² + 0p)2
so that
P Plopp (Vh+1)= ow (Vn-1) 26)
4 (2HB +H VPn)
2ne p
exp
(16)
P
4H² + pP)2
Lemma 5. (Lemma Fournier and Guillin 2015), Concentration inequality for Wasserstein distance For μ. e P(R), consider i.i.d. sequence (Xk) of p-distributed random variables and, for all n. > the empirical measure
Pn
6X.-
Assume that there exists y > 0 such that (1) = J2 exp (7/x//2 p(dr) < co. Then for all a > all
P (W (pns p1) > x)) < Cexp (-enx²)
where the Wasserstein distance W (pas p)) is defined by and the positive constant C and e depends only on y and (1)
{
{ |x (dx du)
W (pa, 1): = inf xEIl(
14

---

Online Robust Reinforcement Learning Through Monte-Carlo Planning
Lemma 6. (Lemma Zhou al. 2021 Let X P be random variable with X [0, MY. and Pn denotes its empirical distribution of sample size For ó 0, for any
a' E arg max { -aa log Ep e x/o)) -a6} ag0
(17)
(1) o² O. Furthermore, assume that the support of X is finite. Then there exists a constant N' == N'e,, ((e,8, P), such that N'. with probability at least we have
E arg max { -a log EEp. [e- (-X%/a) ad}
0.00
(2) a' > Then there exists constant N" (e, 8, P), such that for any d N with probability at least E, there exists
E arg max { -a log [Bp, (e-X/a)) - a00 000
á"
such that a", ā" a). where a > 0 is independent of and ā M/6.
The Total Variation, Chi-square, and Kullback-Liee Liebler uncertainty sets are constructed with the f-divergence. The f diver- gence between the distributions P and po is defined as
Dy (P|IP)) /
dP dPo
dP
(18)
where f is a convex function CSiszár 1963). We obtain different divergences for different forms of the function f. includ- ing some well-known divergences. For example, f(t) |t 11/2 gives Total Variation, f(t) = 1) gives chi-square, and f(t) log(t) gives Kullback-Liebler.
Lemma 7. (Lemma 5 (Panaganti et al. 2022 Let D be as defined in equation 18 with f(t) | 1 corresponding to the TV uncertainty set. Then,
inf (P Ex([(x)]= =- inf Ep (17- 1(X))++ nn- wER
inf 1(x) x p-1 DEX
Lemma 8. (Covering number (TV)). Given a reward function R Ra let UR {(1 1 R)+ : E [0, Rmax]] Fix
any 0 (0, 1). Denote
NR( = ((1 1 R)+ : : E
where Ng- = [mmax/() Then Then.N((0) is 0-cover for with respect to ||=||,o, and its cardinality is bounded as (Nn(O) < 2Rmax/0 00. Furthermore, for any v E (O),), we have |||||00 < 1.
Proof. First, Ng = RRmax/0 is the minimal number of subintervals of length 0 needed to cover [0, Rmaa). Denote J, (i-1)). i0) to be the i-th subinterval, 1 < < Ng. Fix some E Ug. Then μ = (n - R)+. Without loss of generality, assume this particular 7 E J; Let ((10) R)+. Now, for any 8, a E S x A.
(v(saa) p(s,a)) a)l
(i0 R)+ (n R1+
(a)
li0 R + R
100 (i - 1)0 = 0
where (a) follows from i0 > and the fact that maxfa, 1,, 0} max 0} < x y. x: > y. Taking maximum with respect to s, a on both sides, we get || - plllo & 0. Since (0). this suggests (R( is a 0-cover for Ug. The cardinality bound directly follows from
15

---

Online Robust Reinforcement Learning Through Monte-Carlo Planning
[R((0)] No [Rmax 1 & Rmax/0 / + 2Rmax/O
where the last incquality is due to 0 0 < Now, for any (R)()), we can establish the following
p= (n 1 1t) & (Amax
1 - Rt+ & Rmax
where the inequality element-wise.
Lemma 9. Fix any () E S x A. Fix any reward function R E Rs Let NR(0) be the d-cover of UR
{(7-1 R)+ n E [0, Rmax]} as described in Lemma
We then have
ERTE [(n - RR+] E R [(1] - RD+1 [m--))+] <
Paar 22 + 20
sup Rmax) Rmax]
max reNx(()
Proof. For any μ Un, there exists E (R) such that || rl100 8. Now for such particular fu and r, we have
Ds,att Ds,arl + |Daar- v2 122or v2,a1
Pesalli || - rlloo + 10sar - r + 1| ||r -A1lo
1 1 1/ + 20.
max vENx(1)
Taking maximum over Ug on both sides, we get
sup
Ps.alt v2,au1
max rENR(()
DosaT vo2atl 20.
HElR
Now note that by the definition of Un, have
sup Rm..
[(n-1]] Rt)+] ER [(n - 18),]
< max
+0 Pear - -2 + 20
rENn(!))
The desired result directly follows.
Lemma 10. Consider the total-variation uncertainty set
PTV { Po 6].
Let Reobrv = min min,,... R..RR... ER-T. R and R = min,, R... En-r. R be the robust rewards defined using the empirical estimate Vs, and vr,a and respectively. Then there exists constant
(", 8, v2.):
such that for all n. 2 N (Lee a sufficiently large number of reward samples at (8, a), the following holds with probability at least E:
R2 log (2/0)
Probry 5,a
probry 8.a
2n
16

---

Online Robust Reinforcement Learning Through Monte-Carlo Planning
Proof. Following similar analyses in Proposition etu 2023) (Lemma 2p. we get
R
inf n Remaa.
ERNBen [(1 R)+1 (7
inf
R'
-p-1
(19)
R' Rmaee
E ERAve (11 - (R)+) {11
inf n mmm0.2Rmax//0
inf R(
Rt' +
-p- 11
(20)
(a)
sup DE Remae
BR a 111 111-10 11)+1 BRNNS [(1 - R1)+1
(21)
< max
sup Nemaz
ERNDy (11-11) - R]+1 - ER [(1] - (1y-1)44
(22)
sup Ruaxx R.max /pl
ER-Dn. [11] - R)+] - Enowy [11- (o-R)++1
(23)
max
BR-BAI [11]- - R)+1 - BRRUN [(n- R)+1
(24)
nE (O, Riax.
E B
[R]
E ER
[
(25)
max
max (ENa(O)
V v2 + 20, ER-D. [R]
ER
[1]]
(26)
where (a) follows from the fact that jin[, f()) inf> g(x)) & sup, ((x) g(x)) For (b), recall that R & Rmax for any R E R. Henee, the term R' is always non-negative for 77 E [Rmax m p). which cancels out by linearity of the expectation. (c) follows from applying Lemma to the first term. Recall that all E NNz(0) is upper bounded by R
Now we can apply Hoeffding's inequality to the first term in equation 26
PP ((Dsaa vl 3 3) & 2exp
(-
(-2ns² 2ns²
3A >
R2
Now choose
R2 log (0)1))) and recall that [nx(0)] & Rimax /0 from Lemma 8
We have
2N
12
log(AR (mma 105)
R2 Riax log (2 (R (0)())))) /8)
PP
|Paar // 2
max
< P
Daar v2 >
2n
2n
8
Wn((0)l
Applying a union bound over (O), get
R2
log(4Rmaaz/ (8)
max rE)
Deear- - v2o0r <
(27)
2n
with probability at least 8. Now can also apply Hoeffding's inequality to the second term in equation 26 Recall that any reward function is bounded by Rmax. We have
R2 log (2/6)
Reobrv s,a
Rrobrv
(28)
2n
with probability at least Combining equation 26
equation 28 completes the proof.
17

---

Online Robust Reinforcement Learning Through Monte-Carlo Planning
From Lemma
10
have
P ( Probrv R 20 +
R Rimax L0g(4Rmex/866//1)
(29)
Set 0 =/4 with Σ 2 R Ra log( ( 106) / /nn, then
2n,
2ns² 2 /4 = Ryaxx log( (08(4maxx/00 (00) + expl - [Baaxx = =6/16Rmax
(30)
+ 8 16 exp(-nE? 2 / Rmax
(31)
so that
16R exp(-nE? 3062//0 /
P Probrv
RrobrV
(32)
Lemma 11. (Lemma Panaganti et al. 2022 Let Dy be defined as in equation (t - 1)2 corresponding to the Chi-square uncertainty set. Then
with the convex function f(t)
inf Ep[((X)] = inf WER
(Vp+IVEP ((o - 7)
Lemma 12. Fix any s,a 8 A. For any 0, (0, and p > O, we have, with probability at least 6, can find
constant N such that Vn 2 N we have
V2C 9 Renax
(vioe
(1 + Rmax/ (C, -1))) + +1)
111))
Probx
probx 3,a
< 20 +
(Cp 1) vn
Proof. Similar to Lemma probability.
10 the result is direct by applying the results of Lemma
9 Lemma and the law of total
From the results Lemma 12 Then we have
V20g 120x.mmxx Rmmxx ( (110g)
2((1 + Cp Remnae(OOCC - 1)1)
P
Rrobx
Rrobx
20
+
+1 +1) <
(33)
(Cp 1)vn
8
Set = s/4 with g = V2 Renax
(C,-1)iv (Vlog 221+C, Mal+C.Bmnn/00i (0lc
+1). then
C, - 1)
2(1 + C. Rmaxx (0(Cp 111])
-1)
= log
(34)
2v 2v203 22222RRRnn Rinax
-1) )
(Cp 1)
8
exp
(35)
2V2C 122C2RRmes Rmax
2(1 + Cp Rmaxx (0(C, 1]))
3 >))< <2 (<<(1+00p) C1 [Cpp -11) exp {-
(C,
Rrobx
probx s.a
(36)
2V2C2 Rmax
Lemma 13. Consider an MDP with the Wasserstein distance Dw. Fix any E S x A. we can derive
inf Pp) [x((())=
inf Aefx am p (Ap² -ER'nve lint R'R (R" + Xe (R", R')])
18

---

Online Robust Reinforcement Learning Through Monte-Carlo Planning
Proof. Fix any (8,a) 8 A. We have
inf Dw Pp
En-pl(X)] =-
[R-r)-[(X)]
Dw (P))
(a)
inf A
E ER'NUS
sup {-R" dall (R", ,2)) + App
RE
sup
ER'
inf {R" + Adl (1E", 1873 - 2x0)
A30
EPER
(R" + Ad (R" R')] App }.
sup xE(o, Ramax/ pp]
inf R"ER
where (a) follows from (Gaao and Kleywegt 2023) Theorem For (b), let first denote any optimizer in (a) be X Observe that since R is non-negative, follows that
inf {R" + ddl (R" R')]] & ~xppp + ER [R' + Ad (R', R')] & -xp pp + Rmax
< -p + ER
Rd
where in the last inequality we use that the distance metric satisfies d(R, R) for any R E R.
Lemma 14. (Covering number (Wasserstein)). Consider the following set of [Rl vectors:
Up = {(AVEe AARER (R" + >d (R", .)),,................. inf (R" + Ad (R" (R', R"ER
= E [0, Rmax/
Let
No.r(0)=
=
{{(
inf {R" + Ad (R",))},.. RR
inf (R" + Ad (R", 111)) T R"ER
: {
20
No.0 D.
Bp }
Bp Bp
and Bp max R d (R", RR). Then Ne)re(f) a f-cover of Up with respect to || ll,e. and its cardinality is bounded (N,x(0)) & Baux By Ramss Vpr) Furthermore, for any E &N,,R(()) have || & Runn (B, PP)
where Np.0
RuuaBB" By PP0
D2
Proof. Fix any 0 E (0, 1). First note that No. is the minimal number of subintervals of length 0 Br [0, Rmax/ p Denote J; = (i 1) #
needed to cover
B 1 < i & No.. Fix some E Up Then must takes the form
i
inf {R" Ad (R" 1)} E
inf eeER
{R" + Ad (R", R1]]]
for some [0, Rmax/
pº). Without loss generality, assume À E J., Now we pick
dp (R", (R)))1)) 122)))
==
inf R"
R" + i Bp
de (R" 1et 11) .........
inf RE.
RR + Bp
Fix any R' n and R" E v, we have
19

---

Online Robust Reinforcement Learning Through Monte-Carlo Planning
0 d' (R", R)
RR' R"I
inf
(R" + Ad (R", R('}
inf EU
R8" +
RREER
Bp
ME
0
sup RMER
i
(R", RR))
Bp
max d' (R", RR) R R!
Bp
Bp
Bp
1) Bg
Bp 0
Bp
where (a) due to linfz f(x) inf g(x)l & sup, 1f(x) g(zr)). Taking maximum over R' E on both sides, we get || - volooo < Since (0)). this suggests that Nº, (0)) a 0-cover for Up
To bound the cardinality of p, (0), consider two cases. If 0 p 1, then pr8 1 and
Rmax Bp
Rmax Bp
Peax Bp
Rmmax
Rmax Bp + Rmax
<
+1 <
+
p
On the other hand, if p 1, then since 8 (0, 1), we have
Riaaxf Bp Prg
Rmax Bp
Rmax Bp
p²
Rmaax Bp
p
Rmax Bp + Pe
<
Png
P
PPB
PPB
p
Hence, we have (2,,((0)= = No < any R' E R,
Rmmer BmmeB (B v
Now we prove the last claim. Fix any v E No. R. Note that for
Rmax pp
Rinax (Bp + p²)
R' inf {Rt + Adl (R", R')3 & Rmax + XBp & Rimx + H"ER
B,
pe
The result then follows from taking maximum over R' R on both sides. Lemma 15. Fix any (s,a) S x A. Let ((f) be the f-cover of the set
{
inf {R" + Ad (R" 1)),..... (R" + Ad (R", (2111 A E [0, Rmax/ 1P0)
Up
RRER
as described in Lemma 14 We then have
sup Remas/
E
{R" + dal (R" R()} Erew HeER
inf
inf (R" + Ad (R", [8)} ER
10 Do v2 + 20.
max rENp,n(0)
Proof. The proof is identical to the proof of Lemma 9
Lemma 16. Fix any (s, a) E S x A. For any 0,8 (0, and p 0, we have the the following inequality with probability least 1 - 8
2R By 12-22(1 Pimax Vpy)
Probw RRobw
<
Rmax (Bp + p²)
log
P=08
+ 20
P
2n
where Bp = max,,,... no d' (R", R.).
20

---

Online Robust Reinforcement Learning Through Monte-Carlo Planning
Proof. From Lemma
we have
Rrobw 8,0
sup Xe(0, pF]
inf {R" + Ad (R" R('}
- Xpp
RRER
Brobw
sup Xc((0, Rmaxe De]
inf {R" Ad (R", RR} ER
Ap
Now it follows that
Rrobw
Rrobw sup Amao. pp]
E ERerey
inf {R" Ad (R", (R", RRER
-2p0
(37)
inf {R" Ad (R", R')) -Ap= }
sup XE(D.Buaa
E
(38)
HEER
sup
inf {R" Ad (R" R() RRER
(39)
Re
ER'
inf ER
{1" + Adl (e",
(40)
max rEN).n(0)
Do 12 v/a vl +
(41)
where (a) follows from lsup, f(z) sup, g(x)] < su [f(x) g[z)]. (b) follows from Lemma 15
Recall that all v E (() is bounded by Vmax
Rmaae (pppp) Now we can apply Hoeffding's 's inequality:
2n
2n Renaxe Renax (Bptee))
PP (102 Ui > 2) & 2exp
= 2 2exp
4e > 0
122 Vmxx
Now recall that (N)) & Rear (Bm VpP) and choose
PF0
Rmax (Bp + PP) 8
log (2 (0))
P
2N
We then have
Rmax (Bp + p²)
(log (2 (o)
100 T r- - vgarr
V
p
2n
Wp.n(0))'
Finally, applying union bound over (p),((), we get
Rmax (Bp + p²)
log
22mmxx By 2(Rmo vpo)
Rmox PPB8
100 12000 2o V
(())
Pr
with probability at least Combining the above and equation completes the proof.
21

---

Online Robust Reinforcement Learning Through Monte-Carlo Planning
Similarly, Set e/4 with
2.mmx PRaax(BBtt0 B,+ pp
log
2Rmaae Ep
228max v
then
2n
2nc² p2p
088
exp
4R Bp pm))2
2Rmax By 2m pp
(42)
4 (2 Bp 22maxx vp")
exp {
2n p2p
8
(43)
4R2
max (Bp + pp)2
so that
4 ( Bp 22 (Px
2no? p2P
Rrobw 8
23)
exp
(44)
PPe
4R2 max
(Bp + pp)2
C. Convergence of Robust-Power-Uut Multi-armed bandits
Lemma 17. For m E [M). let (Vm.nnns1 be sequence of estimator satisfying Vm,. n-toc
0.8 Vmn and there exists a constant
such that Vn, < L, Vn 7 Let X; be an iid sequence from a distribution vº with mean i and St be an iid sequence from a distribution p (Pi..... PM) supported on {l..... M). Introducing the random variables N # (i < n S: = 8m}) }. Let us study a random vector Pn- No.
No
NM
We define an estimate of vo as
n
2 2 Dn =
6x
where 6x, is point mass X,, And define R min,aR ER [R] w.r. ve and R min, E ( wonl Du define the sequence of estimator
2n = =RR + +70p. (Vx).
Then with 2a & 3,331 1,
Qn a.8 RR + topp(V)
n
M D x; 1,,, > 0} is the (M 1)-dimensional simplex. Without loss of generality, we assume that Pm > 0 for all m. Let us define V = (Vi, Var).. Let V.n (VI.NT, V2,Nz..... VM,Nz,, EM No n, Nr is the number of times that population was observed. We have Qn
Proof. Let p (PI.P2....PM) .PP....MM A where M for RM
R yop (Vn). Therefore,
P @2 - (RR +Vo, (2))
<
-R
>
+P
1r0 (V)) (V))
1
(45)
2
2
1
P
R
>
+ P
lop (Va)
[V)) >
(46)
27
To upper bound A,
TV:
A 16Rmax exp(-n(e/4)) (lle/4)2/1((2 12122 (
(47)
8/4
Chi-square:
{ {- { 1) ((GGG-INee_
}
A 2 1+ CyRmax/( (((p-11))
22/C7 7 Rmuxx -1)
exp
(48)
4
22

---

Online Robust Reinforcement Learning Through Monte-Carlo Planning
Wasserstein:
4 422 By + 2 22maxx vpP) A &
2n p2P
exp
(49)
4R2 max (Bp pp))
To upper bound B, let us consider oūn (Vn) - -o = (op, (Vn)
(p((P)) + (op - -op(V)). Then,
B $ P Rr (Pn) - -o((V)) > 47
1
- P (op(Pn) -op(V))
>
1
(50)
4yy
By applying results from Lemma
2 and Equation 8
obtain
TV:
16H exp( expee-le//A4)
B1 &
(51)
E/4y
Chhi-square:
Bi < (1 + C,HH/( (
[C, ((C,, - 1)vTEE -11
2
exp
(52)
2/
Wasserstein:
4 (,HB, + 2H 2P")
2n P2P
Bi <
exp
(53)
p
4/12 Bpp + pp)2
For Bg, as the result from Lemma I we have
(Vn) - -v( < <1i -
< lV
Vll
Therefore,
B2
& Pr
Σ
V Nm
Vill
1
Pr
[
Vml 1
4yM e
(54)
47
m==
M
N
P
Vint
Vm 2
c Nm
(55)
N
4yM
m==1
1=1
E
(N )
-
6
(56)
4
m=1
Let us define an event 3
=
m
>
nPm 2
Therefore,
M
M
n1pm 2
B2 <
Cl -a
+
P(N m
&
(57)
2
4yM
m=1
m==
M
M
22
3 -a Pm
M )m
-8 -a 88
E P(N7
Pm S
Pm T1
(58)
m 1
2
28
28 9
Pm
M ym -
exp {
-nn
Pm 2
(59)
Therefore,
23

---

Online Robust Reinforcement Learning Through Monte-Carlo Planning
TV:
16R max expl exp{-n(e/4))/> (2/(E/))//2/mm Faax
16H exp (ononnnn))/////E
A+ B1 + B2 <
(60)
e/4
E/47
M
M
+
(c20+28 / Pm M )m - - 8
+ Σ
exp
2n
Pmnll )²
(61)
2
77
CChi-Square:
(Cp (Cp-1)) 1) -1) }}}
1+ Cp / (E(G) - -1)) exp
A + B2 <
(62)
2 22/22 Rmax
{- - 11
+2 1+ Cp
=Cpp-
{-( 2/2C2H
-1)
Σ
2220 pm )m
exp
4
m=1
(63)
p )2
Pm
exp
2n(
(64)
2
Wasserstein:
(2 By + 2R V
2n p2p
A A+BS A+ Bi + B₂ <
exp
(65)
PRE
R2
max
(Bp + p
42HB, B, 2H vPD)
2nE2 pp
M
exp {
(c20+287 Pm M M0 -8
(66)
P
4H² Bp + pp)2
m=1
M
{ -2n
Pmnl )2
exp
(67)
VIL
In both three cases, that leads to
M +
P 1@ -RR +70,(V)) >8) < <(eepp(-n)) + O(e expe-cnn?)) ))
Σ
222 80 pm
-MM8 nd) gg (68)
m=1
M
exp { - 2nl
Pm )2
aen
(69)
2
m=1
with é' 0 depends on c, M, or, 3, Pt. Here need
2a B,
(70)
to argue that -1 --eep((-enns = Therefore, with n > 1,e > 0.
p p(
Q2.. 2(@0n -(1t + + <cn-ag-
(71)
24

---

Online Robust Reinforcement Learning Through Monte-Carlo Planning
Furthermore,
E @ (R 1 +
lim
(72)
[ P (1ēn - (R (op(1)) 30 5)
lim
ds
(73)
20000
n na 3
too
<
lim
1ds
+
e ~
(74)
00
8 8-1+
+00
lim n=000
n2 7
C
(75)
-B+1
in
a(8-1) n 3
lim
n
7
n
0 (because a 0. 1)
(76)
n n00
-
+
so that,
lim E[Qn] R (V),
This means
@ 0 R 7V,((V,
which concludes the proof.
D. Convergence of Robust-Power-te
Monte-Carlo Tree Search
0.8 Theorem 1. (Theorem 1 of Dam et al. (024b) For each arm a [K], let Pa.n n-oo Po and define μ. = maxa(Ha).
Suppose arms are selected according to equation with parameters (a, B,b, C), and let p E (0)
S s 2, and a S 2 or p> 2, < a <1
and
a a(1 (1--) I < a, then there exists suitable constant C (depending K,b, a. p. Amia) such that
o' Th (p)
n+000 ph:
where Amin mina: <u. (p. Ma), a' (6 1) -1)1))) 2), and B' =(b- (b- (6-1). 1). Theorem 2. When applying Robust-Power--On with parameters {b,) fai) and (3,1 H satisfying Table !
(i) For any node s at depth h E fO....,H,, H}.
(a6) annh ((a).
(ii) For any node st, at depth h (O..... H 1}.
Qu(s,, a) on 18111 @(hh.)), Va E Asn. n00
Proof. We follow the proof technique of Dam et al. (2024b Theorem 2).
Base Case (H 1). Consider the root node 8g. Each time we visit (so. a), we collect:
A reward sample r'(so, a) from the reward distribution ua which then leads evaluating P, and Prob min r ER-r[RR, thus approximates the worst-case reward (so, a).
25

---

Online Robust Reinforcement Learning Through Monte-Carlo Planning
A next state 81 Po from M |Leeal possible states (denote such states as St). This then leads to Pa and captures the worst-case value from the transition ambiguity set P Pag.ar
By definition of the robust Bellman backup, recall
((50, a) = Raoha + 7 (V),
where Rrob min, aagia Reg.n Bir].
Since H = the next state is treated as leaf. We approximate ((s)) V (s1). i.d. rollout returns under the policy By standard concentration bounds (e.g., Hoeffding), we obtain for all child nodes 81 E Sg:
(11)
on ((1)).
(77)
10000
Next, recall by equation 3
(s, a) Rrob + t000 Pro.. (v)) (n))
Here Vr,,(n) (m) is the estimated value at all child nodes $1 E SS. By Lemma 17 and equation 77 it follows that
in a) angh (500 a).
Since Su is the root node, we perform the power-mean backup on (2n(
Va(s))
(
T (n)
a)
n
Avo
Under Theorem (from Dam al. (204bb for robust settings), we conclude
V (s0)
Ouo B0
((s)).
11
This establishes both points (i) and (ii) at depth 0 and confirms the result for H 1.
Inductive Step (H > 1). Assume the theorem holds for all search trees up to depth H 1. We now add more level to create tree of depth H. Let be child of the new root sg. Then itself is root of subtree with depth (H 1). By the inductive hypothesis:
(a())) anth (si), an))) ui @(s1,a)), Va'.
At the new root sp, we repeat the argument used in the base case:
Observing rewards 7' (so. a) from D S0.a
Transitioning under Po P to state $1.
Hence, Lemma 17 again implies
@n(so. a) angei ((5n a):
n-000
and the power-mean operator at so yields
80 (7
V(so).
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.
26

---

Online Robust Reinforcement Learning Through Monte-Carlo Planning
Theorem 3. (Convergence of Expected Payoff) At the root node 50, there a choice of parameters yielding
[n((s)] - V(s0)] _ O
Proof. By Jensen's inequality (convexity of [2:)), we obtain
I [Voo)]]] - (sso
= E [20) - v(50)
% P (((((0))) v((0)) 2 8) ds.
Next, we split this integral at -o0/30, Using the concentration property (3() a0y00 V(s)), we have
P (()) - Vss)) 2 8) S nt 00 8 8
for s n 000 Hence,
E [ V(50
ds
Ga
Co 71
ds
200
80
+
80
ds
80
08
8o
+
00
n
0g
8
00
30
p0
1
Because 3o < } (see Theorem 1. the dominant term is O(n 2). Thus,
[[Va - V(so s Onn=2)
E. Experimental setup and Parameters selection
E.1. Experimental setup
All experiments done over 100 seeds, using y 0.99 and robustness budget p 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 un- certainty sets (Total Variation, Chi-squared, and Wasserstein)), while maintaining the core MCTS selection and expansion strategies. We also provide our code /ttppp/s///tttt.....cooo//aaaaap
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 reach specific goal amount through a series of betting decisions. In our implementation, the agent begins with 50 units of capital and must reach goal of 100 units to win. At each step, the agent can bet any amount up its current capital. The environment has a win probability Ph for each bet, where the agent either wins the wagered amount with probability Pa 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 particularly suitable for studying decision 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, scaled down the problem all the essential characteristics and decision-making complexity of the original problem.
starting capital of 5 units and goal of 10 units. This smaller scale version preserves
Frozen Lake(Tower, et al. 2024): This environment presents 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 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 '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.
F.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 Wasserstein. The agent's robustmess is evaluated across different uncertainty budgets p (0.1, 0.3, 0.5, 0.7, 0.9), where higher values of p 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 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 demonstrate a clear trade-off between performance and robustness across different uncertainty budgets. Agents with lower uncertainty budgets (p 0.1, 0.3) achieve better performance when the execution probability matches or ex- ceeds the planning probability, but their success rate drops significantly in misspecified environments. In contrast, higher uncertainty budgets (p 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 (p = 0.5) appears to offer a balanced trade-off, maintaining reasonable performance across both regimes.
We now investigate wide range of transition model ambiguities for the Frozen Lake environment. Table provides an extended version of Table 2 with detailed success rates across different planning and execution probabilities. We observe algorithm degrades faster for increased noise injection for slipping prob-
that the performance of Beechastic-Powere abilities 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.
28

---

Online Robust Reinforcement Learning Through Monte-Carlo Planning
Uncertainty Budget Impact on Agent Performance
Success rate (%)
0.6
0.4
0.2
0.0
0.3
0.5 Execution p_h
0.8
Budget:
Budget: 0.3
Budget: 0.5
Budget:
Budget: 0.9
Figure 3: Performance comparison across different uncertainty budgets (p). Planning probability fixed at Pa 0.6 (ver- tical dashed line), while execution probability varies from 0.2 to 0.8. Higher uncertainty budgets lead to more conservative policies, showing improved robustness when Ps 0.6 but potentially reduced performance when ph. > 0.6.
29

---

Online Robust Reinforcement Learning Through Monte-Carlo Planning
Planning
Execution Palip
plan
0.1
0.2
0.3
0.4
0.5
Sp
100
85
71
60
34
Tv
100
84
71
51
39
0.0
Cs
100
87
62
53
33
Ws
100
86
72
58
45
Sp
65
52
41
32
21
Tv
68
54
42
33
24
0.1
Cs
95
82
65
52
35
Ws
97
84
68
55
38
Sp
35
28
22
15
12
Tv
38
30
25
18
15
0.2
Cs
75
65
48
35
25
Ws
78
68
45
38
28
Sp
15
12
10
8
7
Tv
18
15
12
10
8
0.3
Cs
55
45
35
25
18
Ws
58
48
32
28
20
Sp
8
7
6
5
4
Tv
10
8
7
6
5
0.4
Cs
35
28
22
18
12
38
30
25
20
15
Sp
5
4
4
3
3
Tv
6
5
4
4
3
0.5
Cs
25
20
15
12
8
Ws
28
22
18
15
10
Table Success rates (%) for planning with Power- UCT variants. Methods: Stochastic-Powed Power-UCT (Sp). Robust version
with Total Variation (Tv), Chi-squared (Cs), and Wasserstein (Ws) ambiguity sets. Underlined values indicate matching planning and execution Palip- Bold indicates highest success rate per planning scenario.
30


Reviews:
[{"review_id": "dfMK1Nw17L", "reviewer": "Reviewer_ZeKp", "summary": "This paper presents Robust-Power-UCT, a variant of Monte Carlo Tree Search (MCTS) designed for Robust Markov Decision Processes (RMDPs). The key assumption is that exact transition and reward models are unknown, but approximate models exist with bounded uncertainty captured in an ambiguity set. This is particularly relevant for sim-to-real policy transfer, where learned policies must perform reliably in real-world settings despite discrepancies in simulated training environments. The paper provides empirical evaluation on two domains: Gambler’s Problem and Frozen Lake, where Robust-Power-UCT outperforms Stochastic-Power-UCT, especially in the Frozen Lake domain.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thoughtful and constructive comments on our paper. We are encouraged by the fact that they found our paper: well-written, *technically sound*, *aligns with prior work on robust RL*. We'd like to address several important points below. We will revise our paper based on these comments. \n\n**Robustness and Conservative Policies** The reviewer correctly notes that robust planning can lead to more conservative policies. This is indeed an intentional feature rather than a limitation. In many high-stakes applications (autonomous vehicles, medical robotics, financial systems), conservative policies that prioritize worst-case performance are precisely what is needed when the cost of failure is high. Our approach enables this safety-oriented planning while maintaining theoretical guarantees. \n\n**Lack of ablation studies** While we appreciate the concern about ablation studies, we believe there may be a misunderstanding of our experimental approach. In our paper, we already provide explicit comparisons between different ambiguity set formulations (Total Variation, Chi-squared, and Wasserstein) across all experiments, with Tables 2 and 4 showing comprehensive results for each formulation under various planning-execution scenarios. In particular, the robust policies across Total Variation, Chi-squared, and Wasserstein are separately trained, and none of them affects the other. If the reviewer is suggesting a different form of ablation beyond comparing these different uncertainty sets, we would appreciate clarification on what specific ablation studies would be most valuable to include in our revised paper.\n\n**Performance Trade-offs** We appreciate the observation about trade-offs between robustness and performance. Section E.3 in the supplementary material provides a detailed analysis of this trade-off. The ambiguity set radius parameter ρ provides direct control over this trade-off. When ρ = 0, our approach reduces exactly to standard Power-UCT, while increasing ρ progressively enhances robustness at the potential cost of optimality under matched conditions. \n\n**Evaluation Environments** As mentionned by reviewer k1UW, the selected environments are well-known benchmarks in RL literature that effectively capture the robustness/uncertainty problems we're addressing. While not as complex as some benchmark suites, they provide the right level of challenge to highlight our solution's properties while remaining computationally tractable for robust planning experiments. \n\n**Scalability and Computational Cost**\nThe robust value under all ambiguity balls with radius $\\rho_T$ can be computed in at most $O(S \\log(S))$ time. Thus requiring only marginally more computation than standard Bellman operators $O(S)$. It is an open research direction to design and showcase computation efficiency for other kind of robust ambiguity sets. We have only considered some popular ones from the $f$-divergence class and the Wasserstein ball.\n\n**Broader Application Domains**\nThanks for this constructive review. As a next step for high-dimensional settings, we want to test our robust MCTS approach for Go. We recently found that there have been some interest [R1] in discovering adversarial plays for Go and algorithms to mitigate such plays. We believe our approach can handle such adversarial Go strategies. This is our future focus. We think as further next steps, our robust MCTS approaches can resolve some parameter uncertainty in real-world robotic problems [R2]. We are excited for all these next steps from this initial contribution we have made to bring in robust optimization for traditional MCTS approach. \n\n[R1] Tseng, T., McLean, E., Pelrine, K., Wang, T. T., & Gleave, A. (2024). Can Go AIs be adversarially robust?. arXiv preprint arXiv:2406.12843.\n\n[R2] Dam, T., Chalvatzaki, G., Peters, J., & Pajarinen, J. (2022). Monte-carlo robot path planning. IEEE Robotics and Automation Letters, 7(4), 11213-11220.\n\n-----\n\nWe look forward to hearing from you and providing any other clarifications during the discussion period (up to Apr 8). Thank you!", "claims_and_evidence": "The paper is generally well-written and technically sound. However, I have a few concerns:\n\n- Title and Framing Issue: The title refers to \"Reinforcement Learning,\" but no actual learning (policy updates or value function approximation) is involved. The paper focuses on robust planning using MCTS, which is a search-based algorithm rather than an RL method in the typical sense. A more precise title would avoid potential misinterpretation. While this is a minor issue, it could be easily improved for clarity.\n\n- Experimental Support for Claims: The paper claims that Robust-Power-UCT achieves robust performance in the presence of model uncertainty, but the empirical results are somewhat limited:\n  - The performance gains are not always significant: In the Gambler’s Problem, robust planning leads to a conservative policy, which does not necessarily result in better performance.\n  - There is no clear trade-off analysis: The robustness comes from planning for the worst-case, but it is unclear whether this conservatism hurts performance in cases where the real-world dynamics are less adversarial than assumed.\n  - Lack of ablation studies: The paper does not explore how different ambiguity set formulations (Total Variation, Chi-squared, Wasserstein) affect performance trade-offs.", "methods_and_evaluation_criteria": "- While Gambler’s Problem and Frozen Lake serve as controlled testbeds, they do not fully capture the real-world challenges of sim-to-real transfer.\n- More realistic domains, such as robotics or autonomous driving, would better demonstrate how Robust-Power-UCT performs in complex, high-dimensional environments.\n- The evaluation criteria focus primarily on success rate, but additional metrics (e.g., computational cost, robustness vs. performance trade-offs) would strengthen the empirical results.", "theoretical_claims": "The theoretical results appear correct and well-structured. The proofs provide clear convergence guarantees, and the analysis aligns with prior work on robust RL. I did not find any obvious flaws in the derivations.", "experimental_designs_or_analyses": "See above.", "relation_to_broader_scientific_literature": "This paper contributes to robust RL and planning under uncertainty, addressing a key issue in sim-to-real transfer.", "essential_references_not_discussed": "N.A.", "other_strengths_and_weaknesses": "N.A.", "other_comments_or_suggestions": "N.A.", "questions_for_authors": "Q1: Impact of Conservative Planning\n  - Have you analyzed cases where worst-case planning leads to overly conservative decisions that might reduce performance in non-adversarial settings?\n  - How does the performance of Robust-Power-UCT compare when the true model lies within the ambiguity set but is not necessarily the worst-case model?\n\nQ2: Scalability and Computational Cost\n  - What is the computational overhead of Robust-Power-UCT compared to standard MCTS?\n  - Could the robust backup operator be optimized for efficiency in large-scale applications?\n\nQ3: Broader Application Domains\n  - Do you have plans to test Robust-Power-UCT in high-dimensional real-world domains, such as robotics or self-driving cars?\nHow would the method handle partial observability in real-world scenarios?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "FJOXyVa5Zy", "reviewer": "Reviewer_6Th3", "summary": "Reinforcement learning utilizes Monte Carlo search for planning with use of a\nmodel. However, MC search can fail to perform well in situations where the\nmodel does not accurately represent the transition or reward dynamics. This may\nbe due to inaccuracies in the model used for training an agent, non-stationarity\nof the environment dynamics and several other reasons. This paper focusses on\nthe robustness of agents to deployment in problems where the planning model does\nnot accurately represent the environment dynamics. While robustness has been\nstudied in RL, this paper explicitly introduces a robust version of MCTS for\nplanning. The authors propose a backup update rule and a tree policy for MCTS that\ntakes into account the expected worst-case returns to learn robust policies.\nThey also theoretically show that their approach converges to the optimal at a\nrate commensurate to that of standard MCTS. They also evaluate their proposed\nalgorithm against an MCTS algorithm.\n\n## Update after rebuttal\n\nI raised my score to a weak accept.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thoughtful feedback.\n\n**Baseline comparisons**\n Our work focuses specifically on robust online planning using MCTS, and to the best of our knowledge, this work is the first to provide theoretical guarantees for robust online planning using MCTS, with convergence bounds matching those of standard MCTS while providing robustness to model misspecification. Our method differs fundamentally from offline learning approaches like robust value iteration or Q-learning. This distinction is critical for several reasons:\n\n1. Online vs. Offline Paradigm: MCTS performs dynamic tree expansion from the current state during execution, while methods like robust value iteration [1,2] require pre-computing policies across the entire state space. This fundamental difference makes direct comparisons methodologically problematic.\n2. Controlled Comparison: By comparing Robust-Power-UCT against Stochastic-Power-UCT, we isolate the specific impact of our robustness modifications while controlling for all other algorithmic components, providing a clear assessment of our contribution.\n3. Principled Exploration: MCTS naturally incorporates optimism-under-uncertainty for exploration, adapting to each state encountered during execution. This contrasts with offline methods that require separate exploration strategies or complete model knowledge.\n4. Integration with Deep Learning: Recent breakthroughs like AlphaZero [3] and MuZero [4] have demonstrated the power of integrating MCTS with neural networks. This would allow us to leverage value functions learned through offline methods (like robust value iteration) to guide online planning while maintaining robustness guarantees. This integration represents a promising direction where our work complements, rather than competes with, offline robust RL methods - creating a hybrid approach that benefits from both paradigms.\n\nThe empirical results across both environments consistently demonstrate that Robust-Power-UCT significantly outperforms non-robust approaches under model mismatch conditions.\n\n[1] Nilim, A. and El Ghaoui, L. (2005). Robust control of Markov decision processes with uncertain transition matrices.\n\n[2] Iyengar, G.N. (2005). Robust dynamic programming. Mathematics of Operations Research.\n\n[3] Silver, D. et al. (2018). A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play.\n\n[4] Schrittwieser, J. et al. (2020). Mastering Atari, Go, chess and shogi by planning with a learned model.\n\n**Gambler's problem performance**\nWe agree that our phrasing could be improved for clarity. When discussing \"superior performance,\" we should have been more precise. What we intended to highlight was our algorithm's ability to maintain consistent performance across different execution environments, particularly when the execution probability is lower than the planning probability. This consistency under model mismatch is what defines robustness in our context, rather than achieving the highest possible reward in matched conditions. We'll clarify this important distinction between optimality and robustness in the revised paper to avoid any confusion.\n\n**Confidence intervals**\nWe report success rates as the proportion of successful episodes over 100 independent runs, which directly measures the algorithm's ability to complete the task. Success rate is a binary outcome metric (success/failure), so traditional error bars aren't applicable - the reported percentage itself represents the statistical performance. We chose this metric over average reward with confidence intervals as it provides a more interpretable and direct evaluation of performance in environments with sparse rewards. However, if preferred, we can supplement our analysis with mean reward and standard deviation in our revised paper.\n\n**Frozen Lake performance**\nThe reviewer's observation about planning with different slip probabilities highlights an important point that we should clarify. When planning with lower slip probabilities (e.g., $p=0.3$), the environment is more deterministic, allowing the algorithm to find more reliable paths within a fixed computational budget. The Frozen Lake environment has a particular characteristic where reducing slippage improves performance up to a certain point - with too little slippage, the agent might fail to consider important failure modes. With the same number of rollouts, planning in a lower-noise environment naturally leads to better policies. As the planning slip probability increases (e.g., $p=0.5$), the higher stochasticity requires significantly more rollouts to converge to optimal paths since the signal-to-noise ratio decreases. This explains why planning with $p=0.3$ can outperform planning with $p=0.5$ even when executed in matching environments.\n\n---\n\nWe look forward to hearing from you and providing any other clarifications during the discussion period (up to Apr 8). Thank you!", "claims_and_evidence": "1. Their approach solves the online robust RL problem.\n    - A very strong claim that is not backed by evidence.\n2. Their approach has theoretical performance on par with standard MCTS.\n    - They provide theoretical proof.\n3. Their approach performs better than standard MCTS on problems with\nsimulation-to-real model discrepancies\n    - This claim is only partially supported by empirical evidence.", "methods_and_evaluation_criteria": "The variation of MCTS the authors propose seem reasonable for the problem being\nmotivated. Updating values based on expected worst-case dynamics makes sense for\nhaving a measure of the robustness of actions.\n\nThe evaluation criteria makes sense because they are explicitly measuring the\nperformance an RL agent by the reward it accumulates. However, I think there are\ntwo issues:\n- Not enough baselines\n    - Given the number of relevant approaches mentioned in the literature\n    review, there were a number of different approaches to the same problem that\n    could have been used for comparisons.\n- The one baseline they use is not appropriate on its own\n    - The authors selected a baseline that does not seem to be used for robust\n    RL. While the authors proposed approach seems to be an extension of this\n    baseline, it does not seem surprising that they outperform it.\n    - Ideally, for me, the evaluation would answer the question: \"Does my\n    proposed algorithm have any benefits over other algorithms used to address the\n    problem I want to solve?\"", "theoretical_claims": "The authors make the claim that the finite-time error decreases at a rate at\nmost $\\mathcal{O}(n^(-1/2))$.\n\n- I cannot verify the correctness of these claims the proofs lay in the\nsupplementary materials and it is too long for me to go through thoroughly in a \nreasonable amount of time. However, the approach the authors take seem sound.", "experimental_designs_or_analyses": "- The evaluation domains selected are reasonable. Although, experiments on a\ndomain that is larger would strengthen results.\n\n- In the Gambler's Problem, the authors state that robust-power-UCT (RP) has superior\n  performance. This may be supported by the results when execution $p_h \\leq 0.5$,\n  but stochastic-power-uct (SP) performs better otherwise. I still think these\nresults are interesting, but I would not agree with the claim that their\napproach is more robust --- I would say that this demonstrates that their\napproach makes the agent more cautious.\n- The authors also state that their results are over 100 randomly seeded runs\nhowever they do not state (or I missed where they do) what measures of central\ntendency they report nor do they show confidence intervals/errors.\n\n- Similarly, I do not know how strongly the results in Frozen Lake support the\nclaim that RP improves robustness, per se. Planning with $p=0.3$ has a success\nrate of 20% in execution with $p=0.5$ meanwhile planning with $p=0.5$ has a\nsuccess rate of 10%. Why would it perform *worse* on the problem on which it's\ntrained?", "relation_to_broader_scientific_literature": "I found the paper overall interesting and I believe the problems focussed on\nare of interest to the community in robust MDPs, POMDPs, RL with cautious\nagents, continual learning and planning in non-stationary environments.", "essential_references_not_discussed": "I do not have anything in mind.", "other_strengths_and_weaknesses": "## Novelty\n\nThe paper applies an existing approach to a framework in which it has not been\napplied.\n\n## Clarity\n\nThe paper, for the most part, was clear and easy to understand.", "other_comments_or_suggestions": "- The introduction was very long and I do not know if that space could have been\n  put to better use.\n- Similarly, the pseudocode does not help with understanding the algorithm and\nmaybe that space could have been used for theoretical analyses.", "questions_for_authors": "No questions.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "qInRkMfzuE", "reviewer": "Reviewer_k1UW", "summary": "The authors address the problem of model mismatch in Monte Carlo Tree Search (MCTS)-based algorithms. They formulate their approach as a robust optimization problem under the framework of robust Markov decision processes (RMDPs) and provide both an algorithm that solves the online robust reinforcement learning (RL) problem, as well as non-asymptotic convergence guarantees. The algorithm builds upon a robust Bellman backup operator and facilitates safe exploration over prescribed ambiguity transition and reward sets. The authors provide an empirical evaluation of their approach using two well-known RL benchmarks, for different levels of mismatch between the model used for planning in MCTS and the actual application environment.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thoughtful and constructive comments on our paper. We are encouraged by the fact that they found our paper: *provide a good overview and comparison to prior work*, our test suites are at the right level of challenge. We'd like to address several important points below. We will revise our paper based on these comments.\n\n**FrozenLake results**\n\nWe thank the reviewer for raising this important point about our FrozenLake results. They identified a pattern that seems counterintuitive at first glance - where more conservative planning doesn't always translate to better performance in less stochastic execution environments.\nThis behavior stems from several key aspects of our experimental setup:\n\n**1.Episode Structure:** We do implement a maximum episode length (200) in our FrozenLake environment. This creates two possible failure modes: (a) falling into a hole (terminal state with zero reward) or (b) timing out (exceeding the maximum steps without reaching the goal).\n\n**2.Fixed Simulation Budget:** To ensure fair comparison across all experimental conditions, we standardized the number of MCTS rollouts for each planning process. This design choice significantly impacts our results. When planning with higher slip probabilities ( $p_{slip} = 0.5$), the search space becomes substantially more stochastic, requiring more simulations to converge to an optimal policy.\nThe key insight for understanding why planning with $p_{slip} = 0.3$ outperforms planning with  $p_{slip} = 0.5$ (even when executed in a  $p_{slip} = 0.5$ environment) lies in the convergence rate of policy search under different noise levels. In highly stochastic planning environments, the reward signal becomes noisier and the effective search space expands dramatically. With our fixed simulation budget, planning with  $p_{slip} = 0.3$ benefits from clearer reward signals and a more focused search space, allowing it to discover strategies that balance safety and efficiency. In contrast, planning with  $p_{slip} = 0.5$ with limited rollouts often results in overly conservative policies that increase the likelihood of timeout failures, even when executed in the same stochastic environment used for planning.\nWe fundamentally agree with your expectation that \"an agent that plans more conservatively (higher, e.g., 0.5) does not transition to unfavorable states in MDPs with less stochasticity than anticipated (lower, e.g., 0.1).\" This principle would likely emerge if we allowed sufficient computational budget for full policy convergence at each slip probability level.\n\n**Table 1 parameters used in each experiment**\nThe parameters in Table 1 were chosen specifically to achieve the optimal convergence rate shown in Theorem 3. To obtain the optimal simple regret of $\\mathcal{O}(n^{-1/2})$, we need $\\frac{b_i}{\\beta_i} = \\frac{1}{4}$ and $\\frac{\\alpha_i}{\\beta_i} = \\frac{1}{2}$, which follows directly from the proof of Theorem 3. These ratios ensure that the algorithm can obtain the optimal rate of $\\mathcal{O}(n^{-1/2})$.\nWith these parameter settings, the exploration bonus term in our action selection rule becomes:\n$C \\cdot \\frac{(T_{s_h}(t))^{\\frac{1}{4}}}{(T_{s_h,a}(t))^{\\frac{1}{2}}}$\nThis specific form of the exploration term provides the necessary balance between exploring uncertain actions and exploiting promising ones under model ambiguity. We chose the exploration constant C = 2 for all the experiments. We apologize for the ambiguity and will update the details in the revised version.\n\n**Improved documentation**\nWe appreciate this valuable suggestion regarding code documentation. We will update the provided code with clear docstrings and comments that explicitly connect implementation blocks to their corresponding steps in Algorithm 1, along with a mapping document that shows the direct relationship between notations and implementation.\n\n**Related works** \nWe thank the reviewer for pointing us to [R1, R2]. As the reviewer mentions, these are not mathematically rigorous works - but nonetheless, they propose heuristic methods to address environmental uncertainty. We will include these works in our revised paper.\n\n[R1] Rostov, M., & Kaisers, M. (2021). Robust online planning with imperfect models. In Adaptive and Learning Agents Workshop\n\n[R2] Farnaz Kohankhaki, Kiarash Aghakasiri, Hongming Zhang, Ting-Han Wei, Chao Gao, Martin Muller: Monte Carlo Tree Search in the Presence of Transition Uncertainty\n\n---\n\nWe look forward to hearing from you and providing any other clarifications during the discussion period (up to Apr 8). Thank you!", "claims_and_evidence": "From my point of view, the description of the algorithm lacks clarity (comment below in Section 5 of the paper) and there are some open questions on the empirical results (also addressed in comment below). Therefore, I would be hesitant to confirm that all claims have been supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "The test environments are well-known benchmarks in RL literature and are able to capture the underlying robustness/uncertainty problem the authors are trying to address. Even though they are not as complex as other benchmark suites (e.g., a version of the game of go or Atari benchmarks) due to computational requirements, they still provide the right level of challenge for the authors to highlight the properties of the proposed solution.", "theoretical_claims": "I did not check any proofs or theoretical claims. The theoretical parts in the main paper seem correct to me.", "experimental_designs_or_analyses": "The test environments are well-known benchmarks in RL literature, so I was able to follow the results for both experiments. \n\nI would have a point/question on the FrozenLake results (e.g., Table 2). In general, I would expect that an agent that plans more conservatively (higher $p_{slip}$, e.g., 0.5) does not transition to unfavorable states in MDPs with less stochasticity than anticipated (lower $p_{slip}$, e.g., 0.1). In case the authors have specified a maximum number of steps in the episode, it would be useful if the table included the numbers the agent failed due to time-out and the numbers the agent failed due to transitioning to a zero-reward terminal state. If there is no time-out, then I would ask the authors to explain more detailed why this behavior is observed.", "relation_to_broader_scientific_literature": "The authors provide a good overview and comparison to prior work in section 2. However, there are at least two papers that discuss similar problems as the paper but are not cited or discussed:\n- Even though the work there is not as extensive or mathematically rigorous as this paper, I would still suggest the authors to include the following paper in the related work section, as it also tries to address aspects of the robust MCTS problem:\nRostov, M., & Kaisers, M. (2021). Robust online planning with imperfect models. In Adaptive and Learning Agents Workshop - ALA \n- Farnaz Kohankhaki, Kiarash Aghakasiri, Hongming Zhang, Ting-Han Wei, Chao Gao, Martin Muller: Monte Carlo Tree Search in the Presence of Transition Uncertainty", "essential_references_not_discussed": "no", "other_strengths_and_weaknesses": "For me, the weakest part of the paper is the presentation of the algorithm in Section 5. There, symbols (e.g., $T_{s_h}$, $v$, etc.) and design choices (e.g., reward bins) are introduced without explanation, while the dense algorithmic mechanism illustrated in Algorithm 1 is not really described as a whole. This makes the section hard to follow and the reader must often seek information in the table of notations and other papers referenced in related work to be able to fully understand the provided algorithm.\n\nRelated to this, it would help the reproducibility of the paper:\n- if the parameters of Table 1 used in each experiment were provided\n- if the code was documented in a way that code snippets are matched to specific blocks of Algorithm 1", "other_comments_or_suggestions": "Comments/suggestions:\n- Provided code:\n  - It would help if the authors could provide not only the agent implementations, but also training scripts (and running instructions) that could replicate the experiments of the paper\n  - It would be easier to utilize the provided code, if extensive documentation and comments that connect the code to Algorithm 1 in the paper were provided", "questions_for_authors": "- How are the constants B (bins for reward), $b_i$, $\\alpha_i$ and $\\beta_i$ selected in Algorithm 1? What are their values in the experiments conducted in the paper?\n- Also related to one of the points in the experimental section: has the FrozenLake environment a maximum number of time-steps?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Qnan12XawR", "reviewer": "Reviewer_Qnkk", "summary": "The paper presents a robust variant of Monte Carlo Tree Search (MCTS) aimed at addressing the discrepancies between simulated and real-world environments, focusing on ambiguities in transition dynamics and reward distributions. The authors claim that their method offers a robust approach, supported by both theoretical analysis and empirical results. Sorry, I am not well-versed in this specific field so I can't give a reasonable review. My review should be considered as a general overview.\n\n## update after rebuttal\n\nI have raised my score to a weak accept.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive review of our paper. We will revise our paper based on these comments.\n\n**Computation efficiency**\nWe want to emphasize that the robust value under all ambiguity balls with radius $\\rho_T$ can be computed in at most $O(S \\log(S))$ time. Thus requiring only marginally more computation than standard Bellman operators $O(S)$. It is an open research direction to design and showcase computation efficiency for other kind of robust ambiguity sets. We have only considered some popular ones from the $f$-divergence class and the Wasserstein ball. Our contribution in this work has been to adopt robust optimization tools for the standard MCTS planning that has seen historical successes in many sequential decision-making applications.\n\n**Scaling to higher dimensions** As a next step for high-dimensional settings, we want to test our robust MCTS approach for Go. We recently found that there have been some interest [R1] in discovering adversarial plays for Go and algorithms to mitigate such plays. We believe our approach can handle such adversarial Go strategies. This is our future focus. We think as further next steps, our robust MCTS approaches can resolve some parameter uncertainty in real-world robotic problems [R]. We are excited for all these next steps from this initial contribution we have made to bring in robust optimization for traditional MCTS approach. \n\n[R1] Tseng, T., McLean, E., Pelrine, K., Wang, T. T., & Gleave, A. (2024). Can Go AIs be adversarially robust?. arXiv preprint arXiv:2406.12843.\n\n[R2] Dam, T., Chalvatzaki, G., Peters, J., & Pajarinen, J. (2022). Monte-carlo robot path planning. IEEE Robotics and Automation Letters, 7(4), 11213-11220.\n\n---\n\nWe look forward to hearing from you and providing any other clarifications during the discussion period (up to Apr 8). Thank you!", "claims_and_evidence": "The paper claims that their robust variant of Monte Carlo Tree Search (MCTS) can handle the discrepancies between simulated and real-world environments, specifically targeting ambiguities in transition dynamics and reward distributions. The theoretical analysis of the method, along with the empirical results, appear to support the claim that their method offers a robust approach. However, I must admit that I do not have the expertise to fully assess the correctness of the theoretical foundations. From a high-level view, the evidence provided seems reasonable, but I would advise experts in the area to review the technical details more closely.", "methods_and_evaluation_criteria": "The proposed method, which involves incorporating robust power mean backups and exploration bonuses into the MCTS framework, seems appropriate for tackling the problem of robust reinforcement learning. The evaluation criteria, based on empirical tests in environments like the Gambler’s Problem and Frozen Lake, show promising results. However, I lack sufficient background to verify the soundness of the proposed method in depth. That being said, the methodology appears to be well thought out.", "theoretical_claims": "I am not confident in my ability to evaluate the correctness of the theoretical claims and proofs in the paper, particularly the ones related to non-asymptotic convergence rates for robust MCTS. The paper presents some complex mathematical formulations and claims about convergence rates that I cannot verify due to my limited understanding of the related theory. I suggest that this part of the paper be carefully reviewed by experts in the field of robust reinforcement learning.", "experimental_designs_or_analyses": "The experimental designs seem sound at a high level, as the paper compares the performance of the robust MCTS algorithm with traditional methods like the Stochastic-Power-UCT baseline. However, I cannot assess the statistical validity or appropriateness of the experimental setup in detail. From the description, the results indicate that the proposed method performs better under model mismatch conditions, but I would recommend someone with more expertise in reinforcement learning to verify the robustness of these findings.", "relation_to_broader_scientific_literature": "The paper introduces a novel approach by applying MCTS to robust reinforcement learning, addressing simulation-to-reality gaps. This relates to existing work in robust Markov Decision Processes (RMDPs) and distributionally robust optimization, as seen in the works of Iyengar (2005), Nilim and El Ghaoui (2005), and more recent studies like Zhou et al. (2021) and Wang et al. (2024b). The novelty of the paper lies in combining MCTS with robustness principles, which has not been extensively explored in the literature. While previous research focused on model-based dynamic programming or value iteration methods for robust RL, the integration with MCTS opens up new avenues for planning under uncertainty in large-scale environments. The results presented seem to confirm the potential of this approach, particularly in environments with model mismatches, though further exploration is needed in more complex real-world tasks.", "essential_references_not_discussed": "The paper does a decent job of referencing related work in robust reinforcement learning, particularly in the context of MCTS and distributional robust optimization. However, there may be other recent works that could be relevant but aren't cited, especially those that focus on the practical deployment of robust RL methods in real-world settings. It would be helpful to check if all relevant literature has been included.", "other_strengths_and_weaknesses": "While I lack the expertise to fully assess the paper's theoretical and experimental contributions, the algorithm appears to be a promising approach to addressing real-world challenges in reinforcement learning. The novelty of incorporating model ambiguity directly into MCTS is noteworthy. The empirical results seem to suggest that the proposed method can outperform existing algorithms in certain environments, which could be a valuable contribution. However, I would recommend that the authors clarify the scalability of their method and explore its performance in more complex or higher-dimensional environments.", "other_comments_or_suggestions": "The writing is generally clear, but due to the complexity of the mathematical formulations, it could benefit from further explanation for readers who are not specialists in the area. Simplifying some of the concepts or providing additional intuitive explanations could make the paper more accessible.", "questions_for_authors": "1. Could you provide further clarification on how your algorithm scales to larger or more complex environments? Are there any practical limitations to consider when deploying this method in real-world applications?\n\n2. How does the robustness of your algorithm compare in environments with higher-dimensional state or action spaces?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper proposes a robust MCTS approach based on access to an uncertain model with an uncertainty set that contains the true model. Broadly speaking, the paper was well liked, even though there are a few concerns on presentation (which can be addressed in a final version), and more importantly with regards to the experimental section which is limited.

Even so, the paper would be a good addition to ICML.
Decision: Accept (poster)