Model-Free Offline Reinforcement Learning with Enhanced Robustness
Authors: Chi Zhang
Zain Ulabedeen Farhat
George K. Atia
Yue Wang
Venue: ICLR 2025 Poster (2025)
Keywords: offline RL
robust
scalability
model-free
Primary area: reinforcement learning

Abstract: Offline reinforcement learning (RL) has gained considerable attention for its ability to learn policies from pre-collected data without real-time interaction, which makes it particularly useful for high-risk applications. However, due to its reliance on offline datasets, existing works inevitably introduce assumptions to ensure effective learning, which, however, often lead to a trade-off between robustness to model mismatch and scalability to large environments. In this paper, we enhance both aspects with a novel double-pessimism principle, which conservatively estimates performance and accounts for both limited data and potential model mismatches, two major reasons for the previous trade-off. We then propose a universal, model-free algorithm to learn a policy that is robust to potential environment mismatches, which enhances robustness in a scalable manner. Furthermore, we provide a sample complexity analysis of our algorithm when the mismatch is modeled by the $l_\alpha$-norm, which also theoretically demonstrates the efficiency of our method. Extensive experiments further demonstrate that our approach significantly improves robustness in a more scalable manner than existing methods.

Published as a conference paper at ICLR 2025
MODEL-FREE OFFLINE REINTORCEMENT LEARNING WITH ENHANCED ROBUSTNESS
Chi Zhang', Zain Ulabedeen Farhat', George K. Atial.? Yue Wang
1 Department of Electrical and Computer Engineering *Department of Computer Science University of Central Florida Orlando, FL 32816, USA
{chi. zhang, mainclabedenn. farhat, george yue. 8unff edu
ABSTRACT
Offline reinforcement learning (RL) has gained considerable attention for its ability to learn policies from pre-collected data without real-time interaction, which makes it particularly useful for high-risk applications. However, due to its reliance on offline datasets, existing works inevitably introduce assumptions to ensure effective learning, which, however, often lead to a trade-off between robustness to model mismatch and scalability to large environments. In this paper, enhance both aspects with novel couble-pessimisn principle, which conservatively estimates performance and accounts for both limited data and potential model mismatches, two major reasons for the previous trade-off. We then propose universal, model- free algorithm to learn a policy that is robust to potential environment mismatches, which enhances robustness in a scalable manner. Furthermore, we provide a sample complexity analysis of our algorithm when the mismatch modeled by the la -norm, which also theoretically demonstrates the efficiency of our method. Extensive experiments further demonstrate that our approach significantly improves robustness in more scalable manner than existing methods.
INTRODUCTION
Traditional reinforcement learning (RI.) (Sutton & Barto 2018) optimizes agent's performance through iterative trial-and-error interactions with the environment, and has shown significant success in many areas such as video games (Wei et al.] 2022 Liu et al.) 2022a). However, such an online learning scheme can be costly or unsafe in real-world applications. For instance, in domains including autonomous driving (Kiran et al. 202T), stock market trading (Kabbani & Duman 2022 and
healthcare (Yu et al. 2021). poor decisions can have significant consequences, making extensive explorations impractical. To address them, offline RL has been developed (Lange et al.) [2012 Levine
et al. 2020), enabling agents to learn from pre-collected datasets, offering more reliable framework.
Since offline RI. relies heavily pre-collected datasets, the quality of these datasets largely de- termines performance. It is hence unclear whether satisfactory performance can be achieved for complex problems with a relatively limited dataset. In this context, two key challenges in improving offline RL performance have been studied. The first is scalability-the ability to handle large-scale problems. Without real-time interaction, learning an effective policy for large-scale problems from limited dataset, which may not fully cover the entire state- action space, can be challenging. Recent research has focused on improving scalability by adapting model-free algorithms (Shi al. 2022
Yan et al., 2022 Laroche et al. 2019 Fujimoto et al. 2019 Ghasemipour et al., 2021 Kumar et al. 2019 Wu et al.
2019) Siegel et al. (020) and leveraging function approximation techniques (Ross) & Bagnell 2012 Liu al. 2020 Xie al. 202 la Yin et al. 2221aa Xie & Jiang [02 Jiang & Huang 2020). However, due to the complexity of large environments, many of these approaches assume that the dataset sufficiently represents the full deployment environment, typically presuming that the deployment environment is identical to the one from which the data was collected.
However, this assumption can be too restrictive. Static datasets only capture the environment the time data collection, but real-world applications frequently face environmental uncertainty due to perturbations con-stationarity. This mismatch between the data collection and deployment

---

Published as a conference paper at ICLR 2025
environments, commonly known as the sim-to-real gap (Zhao al. 2020),
cause significant
performance degradation during deployment. Therefore, it is crucial to enhance the robustness of offline RL to ensure that the learned policies can perform reliably in the presence of such uncertainties. promising solution is to adapt robust RL frameworks (Iyengar| 2005 Nilim & El Ghaoui] 2004) to the offline setting, as explored recently in (Shi & (002 Blanchet al. 2023). However, these methods often come at the cost of scalability. Due to their inherent structure, robust RL methods typically rely on dynamic planning, which requires knowledge of the full transition dynamics, and are predominantly model-based. This necessitates learning and storing a complete transition model, which is resource-intensive (Zhang al., (021a) and limits scalability for large-scale problems.
Recognizing the limitations of current methods and the challenges posed by large-scale problems and model uncertainty, a trade-off between robustness and scalability becomes apparent. Enhancing one typically comes at the expense of the other. This naturally leads to the following question:
Can we develop a unified framework that enhances both scalability and robustness in offline RL?
In this paper, we address this question by presenting a model-free algorithm to learn a policy that is both robust model uncertainty and scalable to large-scale problems. Our method introduces a principle of double pessimism to simultaneously address two key sources of uncertainty: (1) the uncertainty arising from inaccurate estimations due the underexplored datasets, and (2) model mismatch between the data collection and deployment environments. We then propose a streamlined conceptual framework, design a model-free algorithm, and provide the first theoretical guarantee of convergence and robustness of our approach. Our contributions can be summarized as follows.
A Pessie- Principle for Offfine RL with Model Mismatch. We begin by framing the challenge of enhancing robustness in offline RL within an offline robust RL framework, where an uncertainty set captures potential environmental mismatches. To solve offline robust RL in scalable manner, we propose the double-pessimine not require transition kernel estimations. This principle maintains a conservative estimate of robust performance, obtained directly from data collection without requiring model estimation. We then introduce the first model-free pessimistic robust Q-learning algorithm. Our algorithm optimizes performance under model mismatch using offline dataset, while offering greater memory efficiency and more scalability than previous methods.
principle that does
First and Near-Optimal Model-Free Algorithm for Offline Robust RL. We provide a rigorous sample complexity analysis for our model-free double-pessimistie robust Q-learning algorithm under the widely used -nor uncertainty set. Our analysis shows that, given a dataset satisfying the partial coverage condition (to be introduced later), our algorithm can identify an optimal robust policy with near-optimal sample complexity, comparable to that of model-based offline robust RL and model-free offline non-robust RL. This represents the first sample complexity analysis for model-free robust offline RI., demonstrating its applicability to large-scale problems that require high data efficiency.
Numerical Experimental Verification of Enhanced Robustness. We conduct extensive numerical experiments demonstrate the improvements in robustness achieved by our algorithms in both simulated environments (Archibald et al.) 1995) and real srysics-bases Classic Control problems (Brockman al. (0166). In each case, our algorithm consistently outperform existing methods in handling model uncertainty, showcasing its enhanced ability maintain stable performance across wide range of environmental perturbations. Moreover, our approach demonstrates superior scalability stemming directly from our model- free algorithm design, shown by its effectiveness in solving more complex Classic Control problems with robustness guarantees, which have proven difficult or unsolvable for previous model-based robust methods.
2 PRELIMINARIES
2.1 FINITE- HORIZON MARKOV DECISION PROCESS (MDP)
A Lmite-horizzn MDP is represented by M = (S, A, H, (P.) & (ra)le)) where S and A are the finite state and action spaces of size S and A, respectively, and H is the horizon length.
2

---

Published as a conference paper at ICLR 2025
The probability transition kernel Pk. A A(S) and the reward function r4 : A A [0 are defined at each step h (1 h S H). At each step h, the agent starts in state Sj, takes action On, transitions to the next state $/++1 according the transition kernel P h,,,,,,, and receives reward (8,, an). This process terminates after H steps when the agent reaches state $1+1-
policy ) defines the strategy for selecting actions in different states, where dh (A) specifies the probability distribution over actions at step h. The performance of an agent following policy is measured by the value function Va. = (v/. 1h=1,
Pn.PP. " where
H Σ
re( az)
h
The expectation is taken over the trajectory {sh, ar. Th generated by executing the policy x and transitioning according to the transition kernel P: ag ~ (sh) and 81+1 ~ Ph.en.nn.
2.2 INFINITE-HORIZO MDP
An anfinitehhorizon MDP defined as M (S,A, where both the transition kernel P and the reward function r are stationary and do not change over time. The discount factor ? < 1 ensures the finiteness of the accumulated reward over an infinite horizon.
Due to its stationary nature, it suffices to consider only stationary policies S - A(A), which specify the action-sclection probabilities over the action space. The value function V= of a policy with transition kernel P is defined as
VT. (8) A ER.P
7 at) 80
2.3 ROBUST MDP
finite-horizon robust MDP (RMDP) is specified by HH, (Pa).r). horizon RMDP denoted by (S,A, P, r, 7), where P is a set containing some transition kernels, named the uncertainty set. At each step, the environment transitions the next state following arbitrary kernel belonging to the uncertainty set, instead of a fixed one as in non-robust MDPs. In this paper, consider the (s, reretnnnna uncertainty set (Wiesemann et al. 2013). where P is independently defined for each state-action pair, with X
and an infinite-
denoting the Cartesian product:
Pa
Phosaa (fiiite-horioon),
P
Ps.a (infinite-horizon).
(s,a)ESxA
(s.a)ESxA
The performance of policy in an RMDP is evaluated based on its worst-case value function over all the instances in the uncertainty set. Specifically, the finite-horizon robust value functions V (V. 1 and the
robust value functions V are defined as
Vi (s) inf V. VxxP(s)
(s) :
V
inf V*.P(s) anfinite-horizon PEP
PEP
where the infimum is taken over the uncertainty set of transition kernels. For a given initial state distribution p A(S), write the expected robust performance
(p) A EarpplVe (s)) (fiiie-horizon),
(p) & Ee<p (infinite-horizon). (4)
The goal of an RMDP to learn policy that optimizes worst-case performance, or equivalently, the robust value functions. Such policy is referred to as an optimal robust policy:
{mp)
arg max V (p), (finit-horizon),
(5)
n arg max V (p), (infinite-horizon).
(6)
K

---

Published as a conference paper at ICLR 2025
3 FORMULATION: ENHANCING ROBUSTNESS AND SCALABILITY
In this section, we develop our formulation, where we utilize RMDPs to formulate the offline RL problem against model mismatch.
In the offline setting, the dataset is collected under a fixed environment P (referred to as the nominal kernel) by executing some behavior policy μ.. However, due to factors such as non-stationarity. unexpected perturbations, or adversarial attacks, the deployment environment may differ from P.
To account for this model deviation and improve robustness, we construct an uncertainty set by perturbing the nominal kernel and aim to learn the optimal robust policy. Specifically, following (Xu
& Mannor, 2010 Xu et al. 2010 Derman et al. 2021 Kumar et al. 2023 we define the uncertainty set (of (s, (--pair) for modeling environmental perturbations as:
Ph,sa (PR,s, + A(S) E 2n,s.a) (finte-horizon), Pa.a = (Psa + ((S) : 2.,a} (infinite-horizon),
(8)
for some set Ch.s.as 2..a containing the possible model perturbations, and aim to learn the optimal robust policy for the corresponding RMDPs. This will not only provide an optimized lower bound on performance when the deployment environment lies within the uncertainty set, but also improves the robustness to model uncertainty (Pinto et 2017).
3.1 HORIIOO
In the finite-horizon setting, the dataset D consists of K episodes each of length H. These episodes independently generated based certain behavior policy μ and the nominal kernel P:
{( ai ri H a
H: N
where at ((-1(-)))) 5/11
Pi Pa and the initial state s p.
Since the dataset is collected by fixed policy under single nominal environment, there exists distribution shift between the data distribution, and the distribution induced by the optimal policy and the worst-case kernel. To guarantee that a provable efficient algorithm can be designed based on the dataset, we adopt a popular assumption on the distributional mismatch between the dataset distribution and the occupancy measure induced by the optimal policy n², as in (Shi & Chi 2022
Assumption (Robust single-policy concentrability). The behavior policy p satisfies that
(p.
C A
max (e.0, A.).S))XXxXXXIIIHH (s,
+00,
(10)
where d',, is the occupancy distribution induced by policy π and transition kernel P at step h.
In Assumption 1 only require that the dataset covers the state-action pairs that visited by the optimal policy, known as the partial coverage condition (Rashidinejad et al. (02T).
Our goal is then learn e-optimal policy for the RMDP with the uncertainty set defined in equation 3 and equation 7 such that
( Sc.
(11)
3.2 INFINITE-HORIZON
In the infinite-horizon setting, the offline dataset contains a single trajectory length obtained by executing behavior policy under the nominal kernel P:
D {81, 01, T1, $2, 8T),
(12)
where 8 P. a, pu((ss:) and 8 following two assumptions on the behavior policy.
P Payac For the infinite horizon setting, adopt the
We first adopt the partial coverage assumption in (Blacchet al. 2023 Wang al. 2024c
4

---

Published as a conference paper at ICLR 2025
Assumption 2.
The behavior policy a satisfies
d +00,
C
-
max (s,a,P")ESxAAx
(13)
dp(ssa)) a)
where dpp denotes the occupancy distribution induced by policy x and transition kernel P.
We make additional assumption the behavior policy as follows.
Assumption 3. The behavior policy μ. is stationary, and the induced Markov chain under the nominal kernel is uniformly ergodic.
Remark 1. This assumption is commonly adopted in prior works (Wang et al. 2020 Yan et al. 2022 Li et al. 2020 Wang & Zou 2020). as it ensures that the dataset includes all state-action pairs covered by the behavior policy, provided the dataset size exceeds a certain threshold. This assumption is required since the dataset consists of single Markovian trajectory. When the dataset contains ii.d. samples from the occupancy distribution d'p, as in (Wagg et al. 2024c Li et al. 2022). such assumption can be removed.
Our goal is then to find an 6-optimal policy म through DD for the RMDP with the uncertainty set defined in equation 3 and equation g such that
V" (p) (p) Se.
(14)
4
PRINCIPLE
In this section, we introduce our model-free algorithm for learning an optimal robust policy from an offline dataset. As we mentioned, two major challenges in offline RL are the two sources of uncertainty: one arising from the limited and under-explored dataset, and the other from the mismatch between the data collection and target environments. We aim to develop a unified double-pessimism principle to address both of them.
As suggested by previous studies on offline RI. e.g., (Rashidinejad et al. 2021: Li et al. 2022; Shi
et al. 2022 Yan et al.) 2022 Wang al. 2024c).. the uncertainty arising from the dataset can be addressed using a
principle. This involves introducing a penalty term b,, which depends the visitation frequency of each state-action pair, to penalize less frequently visited pairs. By doing so, we obtain a conservative estimate of the value function under the nominal kernel.
However, addressing the uncertainty arising from model mismatch is particularly challenging, espe- cially with model-free approach. Most previous robust RL studies require that the estimation of the worst-case transition, dp (V) - minpsp pV, be unbiased. This can be satisfied when the agent can freely generate data needed (e.g., (Wang et al.) (203dd] [Liu et al.) 2022b; Wang al., 2023c b)), yet is impractical in offline settings. To address this issue, we argue that another pessimism principle can be adopted, and that learning policy robust to model mismatch does not require an unbiased estimator or an accurate solution to the worst-case, As long as the estimator provides a (not too pessimistic) lower bound on the worst-case, it is sufficient account for the uncertainty due model mismatch and still learn a robust policy. We therefore propose a model-free estimator that lower bounds (V) to produce conservative estimation as follows.
Definition 1. For the uncertainty Pe.es a function is referred as a model-mismatch penalty function if for any non-negative vector V and sample s' ~ Ps.o from the nominal kernel,
E(V(s') Ks,aa OP... (V).
(15)
universal design of the penalty function x is provided in Appendix C Such a penalty function ensures that at each step, the updated estimate represents a lower bound on the true worst-case scenario, resulting in a conservative estimation and enhancing robustness. We note that this additional pessimism may result in more conservative policy, as the algorithm will estimate the robust value function more pessimistically. However, we argue that as long as the pessimism level is not too large, the learned policy will not be too conservative, maintaining satisfactory performance and enhancing the robustness. More importantly, calculation of 6 does not require any information of the model, but can be done in data-driven and model-free fashion.
5

---

Published as a conference paper at ICLR 2025
We then combine the two pessimism principles together, to develop double-pessimisnt algorithm based on the Q-learning algorithm. For each sample (s, a, s'), we update the Q table by
Q(s,a)+ (1 (1-1) (1-1)Q(s,a) a) (1(5,,) + +v(() 3/Ks, (V)
by (V
(16)
model mismatch
limited dataset
As we will show later, such an update rule incorporating the touble-pessimism principle ensures that estimation is conservative, and can effectively tackle the uncertainty in offline robust RL. More importantly, such an update rule does not require any information on the transition model, and hence can be adapted in model-free manner and is more suitable for large-scale problems.
Based on this, we develop our model-free offline algorithms for both finite and infinite horizon cases. In the following sections, present these algorithms and develop their sample complexity analysis.
Q-LEARNING FOR
MDPs
Adopting the double- paoble-psssimism principle, we propose our algorithm for fnite-horizon MDPs.
Algorithm Peuuble-Pessimimm Q-Learning for finite-horizon RMDPss
Input: D, target success probability 1 - 8, uncertainty set radius R, penalty function & Initialize: (s, a) O, NN, a) Vi, O, Vs, h
for k 1..... K do
Sample a trajectory (sh, ah Th Ph from D,, for h = 1..... H do
N4 (sh, aq.
(s), an) + +ln++ + (n an); Tm <
H+1
H+n
bn c Cb
113 (SKKH1))
n
(nh, an) + (1-1n)Qu (sh: an) + The (a(sn, an) (h+1(8n41) Khinnas (Vn+1) bn
(hh)s) +- max { (Vn),,, max, Qn au()
end for (s) + arg max, Q1 (s, a). Vs,h
end for
Tr (s) f- 7 (s), Vs, Output: = {
In our algorithm, the term x is for conservative estimation of the worst-case performance within the uncertainty set, while the term b addresses the pessimism of the limited dataset. We track the visitation count of each state-action pair and construct the penalty term based on these counts. As the dataset visits a pair more frequently, the associated uncertainty decreases and b decreases.
Our algorithm design universal and works for any uncertainty set models, as long as we have penalty function e satisfying equation [5] which provided in Appendix However, since is for different models requires individual studies, we mainly derive our theoretical analysis for the lo- -orn models (Kumar al. 2023
Remark 2.
Derman et al. 2021):
Ph.aa (E 1lg Pa.s.alla S Rh.sa }.
(17)
We again emphasize that our double-pessinine principle and algorithm design can be extended further other uncertainty models. We provide detailed discussion in Appendix C
Next, we develop our theoretical results for la norm sets. We first show that equation 15 is satisfied by our design, and the algorithm results conservative estimation of the robust value function.
Lemma 1. For the I, -oom uncertainty set, set the penalty function
Kh.s,a (V) A RR.s. min ||we V|[s, WER
(18)

---

Published as a conference paper at ICLR 2025
where B =- is the Hölder conjugate of a, and e (1, (I.1,...,1) 1) R Then, equation 15 is
satisfied. Moreover, it holds that for all (k, h, s) E [K] x [H] x S,
(s)s) -
- V (s).
(19)
The lemma provides a concrete construction of the penalty function for the la nnrm model. More importantly, our model-free estimator and algorithm result in pessimistic estimations of robust value functions, tackling both uncertainty sources. In our next result, we show that our double-pessimism principle is effective in learning the optimal robust policy from the mismatched offline dataset.
Theorem 2. For the Lo noor uncertainty set, and any å E (0, 1), suppose that the behavior policy satisfies Assumption 1 When T & HK > O(SC*), the policy ā returned by Algorithm 1 satisfies
VF (0) vi() 5ō ( HOSC T
(20)
with probability at least 1 Here, n²" is the optimal robust policy w.r.t. a (possibly) relaxed la-norm uncertainty set (see Appendix for detailed discussion). S(T) (g(()) means that [f(T) C g(T) (logg(T)) (TT) for some constants C > 0 and l 2 0, when T is sufficiently large.
Our algorithm the first model-free algorithm for offline RL under model mismatch with sub- optimality gap analysis. The sub-optimality gap we obtain in the previous result further implies that we can learn an e-optimal policy as long as the size of the offline dataset T exceeds
① 11 SC*
Ō(SC*)
(21)
2
burn in cost
e-dependent
Note that in the sample complexity, the second term, referred to the burn-in cost, is a universal constant that does not depend on e, while the first term asymptotically depends on e. When e becomes smaller, the first term dominates the overall complexity, resulting in an asymptotic complexity of
A more detailed discussion of the complexity will be provided in Section
Remark 3. When the radius R is small, it holds that [[V - (V)) =op,a (V) (see Theorem I in (Kumar et al. (023)). hence Algorithm Senrrittmmoooeeeee converges the optimal robust policy w.r.. the original uncertainty set. For general uncertainty set and corresponding penalty function к, Algorithm| 7 may converge to the optimal robust policy w.r.t. relaxed uncertainty set, as the estimation may be inaccurate. However, robustness can still be enhanced due to the additional pessimism. See Appendix forr further discussion.
DOUBLE-PESSIMISY Q-LEARNING FOR INFINITE-HORIZON MDPs
In this section, we present our algorithm design and analysis for offline RL with infinite-horizon MDPs. Due to space limitation and similarities in algorithm design, the algorithm is deferred to Algorithm in Appendix E. The algorithm follows similar design as the finite-horizon one, where the two terms and b represent conservative penalties for the double-pessee pesbbimsss principle. Again, algorithm design is universal, but we develop the sample complexity results only for nornorm models.
Theorem 3. Consider the la -o-m uncertainty set and any å E (0, 1). Suppose that the behavior policy p satisfies A Assumption 2 and Assumption 3 Then, the policy मt returned by Algorithm 3 satisfies
(VTC-S)'
C'S
C³
('( - ( (2))
+
T1- +
(22)
T(1-
with probability at least 1 8.
An e-optimal robust policy can be learned long the size of the offline dataset exceeds
SC
θ
(23)
(1 (1-7)66
7

---

Published as a conference paper at ICLR 2025
This sample complexity matches the results of model-free offline non-robust RL (Yan et al. 2022 without variance reduction techniques, which implies the near- optimality of our method. Compared to model-bascts offfine robust RL (Shi & Chi 2022 Blanchet et al., 2023). our result matches theirs in terms of C", , , but exhibits a higher order dependence on (1 - 7). We argue that, in general, model-free algorithms tend have lower memory requirements but incur higher sample complexity
compared to model-based approaches. A more detailed discussion will be provided in Section 7
7 RELATED WORK
7.1 COMPARISON WITH PRIOR ARTS
In this section, we compare our work to the most closely related studies for tabular offline robust RL (Shi & Chi 2022; Blanchet et al., 2023). The results are summarized in Table I where we only include the infinite horizon ones. Compared to previous studies, our method offers improved memory and computational complexity, while maintaining comparable sample complexity.
Reference
Memory complexity
Sample complexity
Computational complexity
Our Work
O(SA)
8G*
Polynomial
(Blanchet et al. 2023
O(S²A) A)
Sac (1-->)
NP Hard
Shi & Chi
2022
O(S²AA
80*
Polynomial
Table 1: Comparison with offline robust RL works. Shi & Chi 2022 for the KL-divergence set.
First, both related works are model-based which involves estimating and storing the transition model (Pa. (8, a) 8 A} R This approach thus requires an additional memory of size O(S A) to store the model, along with O(SA) space for the number of visited state-action pairs from the dataset. As a result, it becomes inefficient for large-scale problems or environments with complicated transition dynamics. In contrast, our model-free algorithm only requires ((SA)-sizes space for the number of visits. Such reduced memory complexity enables our model-free algorithms to handle large-scale problems, scaling effectively to large-scale or even continuous problems.
In terms of computational complexity, the most related work (Blanchet et al., (023) requires to solve non-rectangular RMDP, which is generally NP-hard (Wiesemann et al. 2013). In contrast, our algorithm can be effectively implemented in polynomial time, which is much more practical. Compared to (Shi& & Chi 2022). algorithm still enjoys lower computational complexity, since the update rule of the model-based approach requires computing the inner product Ps.a V, whereas model-free approach eliminates this computation and only requires a single vector entry V(s"). ) See Appendix C for a more detailed discussion.
In terms of sample complexity, both of our sample complexity results match the ones for offline non-robust Q-learning without variance reduction, illustrating our data efficiency and near-optimality. Our result improves the dependence on S compared to (Blanchet et al.) 2023) under the 4 -norm uncertainty set, showing the enhanced scalability to large-scale problems. On the other hand, is the general observation that
methods tend to demonstrate better sample complexity in terms of (1 - 7) than model-fres methods, especially when additional techniques like variance reduction are not employed. Such findings have been widely noted in various settings, for instance, when comparing robust RL with generative models ( (Wang et al. 2024a) vs. (Shi et al. 2023)) and
non-robust offline RL ( (Yan et al. 2022) vs. (Li al. 2022)).
On a side note, we note that our result for the finite-horizon setting exhibits a higher-order dependence on H (where set H I-y as the effective horizon in infinite setting). This is due to the non- stationary environment inherent in the finite-horizon setting, which is also consistent with findings from previous studies, such as in (Shi & Chi 2022).
To summarize, approach addresses existing gaps in offline RL by enhancing robustness to model mismatch, reducing memory requirements, and providing adaptability to large-scale problems, establishing state-of-the-art method in the field.
8

---

Published as a conference paper at ICLR 2025
7.2
OTHER RELATED WORKS
Offline RL without model mismatch. A significant body of offline RL works assumes identical
collection and deployment environments. Based on that, many early works further rely the global
coverage assumption, where the behavior policy covers all state-action pairs (Scherrer, [2014] Chen &
Jiang 2019; Munos
|005| Yin et al. [021bb Yin & Wang [021a] Jiang 2019; Wang et al. [2199]
Liao et al. 2020 Liu et al., 2019: Zhang et al.) 2020 Uehara et al.
et al. (020] Xie
Jiang 2020 Levine et al. 2020: Antos et al. 2007 Farahmand et al. 2010). This assumption is
requires complete coverage of state-action pairs in historical data (Gulcehre et al. 2020] Agarwal et al. 2020a Fu et al. 2020). A more practical partial coverage setting i8 later proposed, allowing to learn from a less explored dataset. Under partial coverage, the optimal policy can still be learned by incorporating the pessimism principle to handle dataset
often too restrictive and unrealistic,
uncertainty (Jin al., [221]] [eehara & Sun| [021] Xie et al. 2021 Rashidinejad et al. 2021
Zanette et al.
2021 Yin & Wang 2021b] (Shi et al. 2022 et al. 2022 IZhan et al. [022 Wang
al.
2023e]
Kumar et al. | 2020). Differently, we consider potential model mismatches.
Robust RL. Robust RL (lyengar 2005; Nilim & El Ghaoui 2004] Xu & Mannor 2010) aims to
tackle the challenge of model mismatch RL, by optimizing the worst-case performance over an
uncertainty set. Existing work focuses mainly on the online setting (Wang & Zou 2021 2022 Wang
al. 2023a Badrinath & Kalathil [021 Dong et al. 2022 [u et al. [024| Liu & Xul (2024a) or with
generative model Yang et al.j [2021] Xu et al., [023 Panaganti & Kalathil [2022] Shi et al. 2023
Wang et al. 2024a b. (022). Offline robust RI,, except for the two mentioned above, either relies
on strong assumptions, such as global coverage or absorbing states (Panaganti et al., 2022 Yang
al. 202T). y. or employs fitted type algorithm designs (Yang et al. [022] Panaganti et al. 2022 Liu
al. 2023). More importantly, most of them are model-based, while we develop the first model-free
algorithm for offline robust RL. Another line of research aims to improve robustness and scalability
through function approximation (Liu & Xu [222bb] Wang et al. 2224a Ma et al. (022), yet we focus on the tabular setting to develop a more fundamental understanding of offline RL. Another line of robust RL aims optimize the performance under the environment from corrupted dataset collected under the same environment (Yang et al. 2023 Zhang et al. 2021b 2022), which is different from setting.
EXPERIMENTS
We use numerical experiments to demonstrate the advantages of our framework in terms of robustness. We consider two sets of environments: simulated MDPs with controllable transition dynamics and Classic Control environments. More experiments are further provided Appendix B
8.1 SIMULATION MDPs
We first evaluate the performance of our algorithm on the Garnet problem (Archibald et al., 1995). a randomly generated MDP (a, b, c) with states, b actions, and branches (see Appendix A for more detailed description). Both the nominal kernels and reward functions are generated randomly. The uncertainty set is constructed using the 1.x- with the radius Ra,a E (0.1,0.5)
We first generate a dataset of size N from the nominal kernel and apply our double- pessimmm algorithm, with the sinlle-pssimmimm baseline (Yan et al. 2022), to learn policies. We then compute the robust value functions the learned policies and plot the difference between these values and the optimal robust value functions, referred to as the optimality gap, in Figure IT The results are averaged over 10 times, with the maximum and minimum gaps as an envelope around the average value. The results show that our double pessimmsss algorithm converges the true optimal robust value as the dataset size increases, maintaining a lower optimality gap, while the single-pessimism approach results in a larger gap. These findings demonstrate that our Nouble-pessimisn principle significantly enhances robustness while remaining model-free and scalable.
8.2 CLASSIC CONTROL PROBLEMS
To further demonstrate the improvements in both scalability and robustness offered by our approach, consider more complex Classic Control tasks from OpenAl Gym (Brockman al. (016))
9

---

Published as a conference paper at ICLR 2025
Decile
hosnking Drgk//ammann Glamrg
budls Poceiio Srghefasimbn Clearing
Sng ofuaatuan Cueamiig
1:30
1:25
3.20
620+
15
635
104
000
Octlact 949
(a) (20, 30, 20)
(b) (30, 50, 30)
(c) g(00, 100, 50)
Figure 1: Optimality gaps under different Garnet problems.
specifically MountainCar and CartPole (results are shown in Figure in Appendix). The dynamics of these environments are indirectly controlled by their parameters, e.g., the length of the pole in CartPole, the gravity and the force in MountainCar, and of interest to improve the robustness against their uncertainty. Since these model mismatches are hard to model, model-baset approaches become ineffective.yet our model-free method remains applicable and effective in such scenarios.
For each dataset generated under the nominal environment with the default parameters, imple- mented our algorithm alongside the baseline (Yan et al. 2022) to learn policies. To evaluate the robustness of the learned policies, test their performance in modified environments with parameter perturbations (Pinto et al. 2017] Wang & Zou (202)). where we randomly perturbed these parameters within the range of T for 800 trials. As shown in Fig. 2 double-pest peooll-ssssmmsm algorithm maintains a higher average performance under environment perturbations, demonstrating superior ro- bustness, which aligns with theoretical findings. This illustrates the enhanced robustness achieved by our approach. Moreover, given the large-scale and complex dynamics of these environments which are difficult for model-based approaches, our model-free algorithm effectively addresses these challenges, further demonstrating the scalability of our method.
www.mmmmammmmmm C-earring
Double "ooimbm O-Lamming
-125
Brubkeehauliiim Druamiing
-140
-340
-350
-160
-380
-130
-330
-222
-30
-220
-343
300
2003
300
1250
Numberee
Number Epen
(a) 7 = 0.02, MountainCar-vo
(b) r = 0.04, MountainCar-vD
(c) T = 0.06, MountainCar-v0
Figure 2: Reward profiles with different parameter perturbations.
CONCLUSION
We explored offline RL with focus on improving scalability and robustness simultaneously. We framed the problem as offline robust RL and developed a model-free algorithm optimize the worst-case performance within an uncertainty set accounting for the possible model mismatch. To address two key challenges uncertainty from the under explored dataset and model mismatch between data collection and deployment environments-ww introduced double-pessimisse principle that conservatively estimates the agent's performance a model-free manner. Building on this, we designed universal model-free algorithm that eliminates the need for model estimation, adapts to various uncertainty sets, and scales to large problems. We further analyzed its performance for the widely studied la ln-nomm uncertainty set. showing near-optimal data efficiency of our approach. Our approach significantly improves the robustness, scalability, and efficiency offline RL compared to existing methods, pushing the boundaries of offline RL research.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENT
This work was supported by DARPA under Agreement No. HR0011-24-9-0477 and NSF under Award CCF-2106339. The authors thank the anonymous reviewers whose constructive comments led to substantial improvement to the paper. The authors gratefully acknowledge Xinran Tang at the University of Central Florida helpful discussions.
REFERENCES
Alekh Agarwal, Sham Kakade, and Lin F Yang. Modell-asee reinforcement learning with a generative model minimax optimal. In Conference on Learning Theory, pp. 67-83. PMIR, 2020a.
Rishabh Agarwal, Dale Schuurmans, and Mohammad Norouzi. An optimistic perspective offline reinforcement learning. International Conference on Machine Learning, pp. 104-114, 114. PMIR, 2020b.
Andras Antos, Rémi Munos, and Csaba Szepesvari. Fitted Q-iteration continuous action-space mdps. In Neural Information Processing Systems, 2007.
TW Archibald, KIM McKinnon, and LC Thomas. On the generation of Markov decision processes. Journal of the Operational Research Society, 46(3):354-36) 1995.
Kishan Panaganti Badrinath and Dileep Kalathil. Robust reinforcement learning using least squares policy iteration with provable performance guarantees. In Proc. International Conference on Machine Learning (ICML), pp. 511-520, PMLR, 2021.
Dimitri P Bertsekas. Nonlinear programming. Journal of the Operational Research Society, 48(3): 334 334, 1997.
Jose Blanchet, Miao Lu, Tong Zhang, and Han Zhong. Double pessimism is provably efficient for distributionally robust offline reinforcement learning: Generic algorithm and robust partial coverage. arXiv preprint vrXiv:2305.09633 2023.
Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojeiech Zaremba. OpenAl Gym. arXiv preprint arXiv:1606.015440 2016.
Jinglin Chen and Nan Jiang. Information-theorrticc considerations in batch reinforcement learning. In International Conference on Machine Learning, pp. 1042-1051. PMLR, 2019.
Esther Derman, Matthieu Geist, and Shie Mannor. Twice regularized MDPs and the equivalence between robustness and regularization. In Proc. Advances Neural Information Processing Systems (NeurIPS), 2021.
Jing Dong, Jingwei Li, Baoxiang Wang, and Jingzhao Zhang. Online policy optimization for robust mdp. arXiv preprint arXiv:2209. 18411, 2022.
Yaqi Duan, Zeyu Jia, and Mengdi Wang. Minimax dinimax-oppimal off- policy evaluation with linear function approximation. In Proc. International Conference on Machine Learning (ICML), pp. 2701-2709. PMLR, 2020.
Amir Massoud Farahmand, Rémi Munos, and Csaba Szepesvári. Error propagation for approximate policy and value iteration. In Advances in Neural Information Processing Systems, 2010.
David Freedman. On tail probabilities for martingales. the Annals of Probability, pp. 100-118, 1975.
Justin Fu, Aviral Kumar, Ofir Nachum, George Tucker, and Sergey Levine. D4RL: Datasets for deep data-driven reinforeement learning. arXiv preprint arXiv:2004.07219, 2020.
Scott Fujimoto, David Meger, and Doina Precup. Off- deep reinforcement learning without exploration. In International Conference Machine Learning, pp. 2052-2062. PMLR, 2019.
11

---

Published as a conference paper at ICLR 2025
Seyed Kamyar Seyed Ghasemipour, Dale Schuurmans, and Shixiang Shane Gu. Emaq: Expected-man max q-learning operator for simple yet effective offline and online rl. In International Conference on Machine Learning, pp. 3682-3691 PMLR, 2021.
Caglar Gulcehre, Ziyu Wang, Alexander Novikov, Tom Le Paine, Sergio Gómez Colmenarejo, Konrad Zolna, Rishabh Agarwal, Josh Merel, Daniel Mankowitz, Cosmin Paduraru, et al. RL unplugged: Benchmarks for offline reinforcement learning. arXiv preprint (ttt:20006.188880 2020.
Garud N Iyengar. Robust dynamic programming. Mathematics of Operations Research, 30(2): 257-280, 2005.
Nan Jiang. On value functions and the agent-environment boundary. arXiv preprint arXiv:1905.133: 2019.
Nan Jiang and Jiawei Huang. Minimax value interval for off-policy evaluation and policy optimization. Advances in Neural Information Processing Systems, 33:2747-2758, 2020.
Chi Jin, Zeyuan Allen-Zhu Sebastien Bubeck, and Michael Jordan. Is Q-learning provably efficient? In Proceedings of the 32nd International Conference Neural Information Processing Systems, pp. 4868 4873,4888.202 2018
Ying Jin, Zhuoran Yang, and Zhaoran Wang. Is pessimism provably efficient for offiin RL? In International Conference on Machine Learning, pp. 5084-5096, 2021.
Taylan Kabbani and Ekrem Duman. Deep reinforcement learning approach for trading automation in the stock market. IEEE Access, 10:93564 93574, 2022.
Ravi Kiran, Ibrahim Sobh, Victor Talpaert, Patrick Mannion, Ahmad A Al Sallab, Senthil Yogamani, and Patrick Pérez. Deep reinforcement learning for autonomous driving: A survey. IEEE Transactions on Intelligent Transportation Systems, 23()):4999-4926, 2021.
Ilya Kostrikov, Ashvin Nair, and Sergey Levine Offline reinforcement learning with implicit q-learning. arXiv preprint 1rXiv22110.061660 2021.
Aviral Kumar, Justin Fu, George Tucker, and Sergey Levine. Stabilizing off-policy Q-learning via bootstrapping error reduction. arXiv preprint arXiv: 190::009099999 2019.
Aviral Kumar, Aurick Zhou, George Tucker, and Sergey Levine. Conservative Q-learning for offline reinforcement learning. arXiv preprint 000:2006604779, 2020.
Navdeep Kumar, Kfir Levy, Kaixin Wang, and Shie Mannor. An efficient solution to s-rectangular robust markov decision processes. arXiv preprint arX1v:2301.13642, 2023.
Sascha Lange, Thomas Gabel, and Martin Ricdmiller. Batch reinforcement learning. In Reinforcement learning, pp. 45-73. Springer, 2012.
Romain Laroche, Paul Trichelair, and Remi Tachet Des Combes. Safe policy improvement with baseline bootstrapping. In International Conference Machine Learning, pp. 3652-3661. PMLR. 2019.
Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu, Offline reinforcement learning: Tutorial, review, and perspectives on open problems, arXiv preprint arXiv:2005.0166 01643, 2020.
Gen Li, Yuting Wei, Yuejie Chi, Yuantao Gu, and Yuxin Chen. Breaking the sample size barrier in model-based reinforcement learning with generative model. In Proc. Advances in Neural Information Processing Systems (NeurIPS), volume 33, 2020.
Gen Li, Laixi Shi, Yuxin Chen, Yuantao Gu, and Yuejie Chi. Breaking the sample complexity barrier to regret-optimal model-free reinforcement learning. Advances in Neural Information Processing Systems, 34, 2021.
Gen Li, Laixi Shi, Yuxin Chen, Yuęjie Chi, and Yuting Wei. Settling the sample complexity of model-based offline reinforcement learning. in preparation, 2022.
12

---

Published as a conference paper at ICLR 2025
Peng Liao, Zhengling Qi, and Susan Murphy. Batch policy learning in average reward Markov decision processes. arXiv preprint arXiv:2007.11771, 2020.
Boyi Liu, Qi Cai, Zhuoran Yang, and Zhaoran Wang. Neural trust region/proximal policy optimization attains globally optimal policy. In Proc. Advances in Neural Information Processing Systems (NeurIPS), 2019.
Ruo-Ze Liu, Zhen-Jia Pang, Zhou-Yo Yu Meng, Wenhai Wang, Yang Yu, and Tong Lu. On efficient reinforcement learning for full-length game of starcraft ii. Journal of Artificial Intelligence Research, 75:213-266 2022a.
Xiao-Yio Yin Liu, Xu Zhou, Guo-Tao Li, Hao Li, Mei-Jiang Gui, Tian- Yu Xiang, De-Xing Huang, and Zeng-Guang Hou. Micro: Model-based offline reinforcement learning with a conservative bellman operator. arXiv preprint arXiv:2312.0399/ 2023.
Yao Liu, Adith Swaminathan, Alekh Agarwal, and Emma Brunskill. Provably good batch reinforce- ment learning without great exploration. arXiv preprint arXiv:2007.08202 2020.
Zhishuai Liu and Pan Xu. Distributionally robust off-dynamics reinforcement learning: Provable efficiency with linear function approximation. arXiv preprint arXiv:2402.15339 2024a.
Zhishuai Liu and Pan Xu. Minimax optimal and computationally efficient algorithms for distribution- ally robust offline reinforcement learning. arXiv preprint arXiv:2403.096211 2024b.
Zijian Liu, Qinxun Bai, Jose Blanchet, Perry Dong, Wei Xu, Zhengqing Zhou, and Zhengyuan Zhou. Distributionally robust Q-learning. In International Conference on Machine Learning, pp. 13623-13643, PMLR, 2022b.
Miao Lu, Han Zhong, Tong Zhang, and Jose Blanchet. Distributionally robust reinforcement learning with interactive data collection: Fundamental hardness and near-optimal algorithm. arXiv preprint arXiv:2404.03: 03570740 2024.
Xiaoteng Ma, Zhipeng Liang, Jose Blanchet, Mingwen Liu, Li Xia, Jiheng Zhang, Qianchuan Zhao, and Zhengyuan Zhou. Distributionally robust offline reinforcement learning with linear function approximation. arXiv preprint arXiv:2209.0663 2022.
Rémi Munos. Error bounds for approximate value itcration. In Proceedings of the National Conference on Artificial Intelligence, volume 20, pp. 1006. Menlo Park, CA; Cambridge, MA; London; AAAI Press; MIT Press; 1999, 2005.
Arnab Nilim and Laurent El Ghaoui. Robustness in Markov decision problems with uncertain transition matrices. In Proc. Advances in Neural Information Processing Systems (NIPS), pp. 839-846, 2004.
Kishan Panaganti and Dileep Kalathil. Sample complexity of robust reinforcement learning with generative model. In International Conference on Artificial Intelligence and Statistics, pp- 9582-9602. PMIR, 2022.
Kishan Panaganti, Zaiyan Xu, Dileep Kalathil and Mohammad Ghavamzadeh. Robust reinforcement learning using offline data. arXiv preprint arXiv:2208.0511 2022.
Lerrel Pinto, James Davidson, Rahul Sukthankar, and Abhinav Gupta. Robust adversarial reinforce- ment learning. In Proc. International Conference on Machine Learning (ICML), pp. 2817-2826.
PMLR, 2017.
Paria Rashidinejad, Banghua Zhu, Cong Ma, Jiantao Jiao, and Stuart Russell. Bridging offline rein- forcement learning and imitation learning: tale of pessimism. Advances in Neural Information Processing Systems,
2021.
Stephane Ross and J Andrew Bagnell. Agnostic system identification for model-based reinforcemett learning. arXiv preprint
2012.
Bruno Scherrer. Approximate policy iteration schemes: A comparison. In Proc. International Conference Machine Learning (ICML), pp. 1314-1322, 2014.
13

---

Published as a conference paper at ICLR 2025
Laixi Shi and Yuejie Chi. Distributionally robust model-based offline reinforcement learning with near-optimal sample complexity. arXiv preprint arXiv:2208.05776. 2022.
Laixi Shi, Gen Li, Yuting Wei, Yuxin Chen, and Yuejie Chi. Pessimistic Q-learning for offline reinforcement learning: Towards optimal sample complexity. International Conference on Machine Learning, pp. 19967-20025, 2022.
Laixi Shi, Gen Li, Yuting Wei, Yuxin Chen, Matthieu Geist, and Yuejie Chi. The curious price of distributional robustness in reinforcement learning with generative model. arXiv preprini arXiv:2305. 16589, 2023.
Noah Y Siegel, Jost Tobias Springenberg, Felix Berkenkamp, Abbas Abdolmaleki, Michael Neunert, Thomas Lampe, Roland Hafner, and Martin Riedmiller. Keep doing what worked: Behavioral modelling priors for offline reinforcement learning. arXiv preprint (rXiv:20022083396 2020.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Masatoshi Uchara and Wen Sun. Pessimistic model-based offline reinforcement learning under partial coverage. arXiv preprint arXiv:2107.06226. 2021.
Masatoshi Uehara, Jiawei Huang, and Nan Jiang. Minimax weight and Q-function learning for off- policy evaluation. In Proc. International Conference on Machine Learning (ICML), pp. 9659-9668. PMLR, 2020.
He Wang, Laixi Shi, and Yuejie Chi. Sample complexity of offline distributionally robust linear markov decision processes. arXiv preprint arXiv:2403.12946. 2024a.
Lingxiao Wang, Qi Cai, Zhuoran Yang, and Zhaoran Wang. Neural policy gradient methods: Global optimality and rates of convergence. In International Conference on Learning Representations, 2019.
Qiuhao Wang. Chin Pang Ho, and Marek Petrik. Policy gradient in robust mdps with global convergence guarantee, 2023a.
Shengbo Wang, Nian Si, Jose Blanchet, and Zhengyuan Zhou. A finite sample complexity bound for distributionally robust q-learning. In International Conference Artificial Intelligence and Statistics, pp. 3370-3398. PMLR, 2023b.
Shengbo Wang, Nian Si, Jose Blanchet, and Zhengyuan Zhou. Sample complextl of variance-reduced distributionally robust q-learning. arXiv preprint arXiv:2305.18420, 2023c.
Yuanhao Wang, Kefan Dong, Xiaoyu Chen, and Liwei Wang. Q-learning with UCB exploration is sample efficient for infinite-horizon MDP. In International Conference on Learning Representa- tions, 2020.
Yudan Wang, Shaofeng Zou, and Yue Wang. Model-free robust reinforcement learning with sample complexity analysis. In The 40th Conference on Uncertainty in Artificial Intelligence, 2024b. URL
Yue Wang and Shaofeng Zou, Finite-sample analysis of Greedy-GQ with linear function approxi- mation under Markovian noise. In Proc. International Conference on Uncertainty in Artificial Intelligence (UAI), pp. 11-20. PMLR, 2020.
Yue Wang and Shaofeng Zou. Online robust reinforcement learning with model uncertainty. In Proc. Advances in Neural Information Processing Systems (NeurIPS), volume 34, pp. 7193-7206, 2021.
Yue Wang and Shaofeng Zou. Policy gradient method for robust reinforcement learning. In Proc. International Conference on Machine Learning (ICML), volume 162, pp. 23484-24322 225566. PMLR, 2022.
Yue Wang, Fei Miao, and Shaofeng Zou. Robust constrained reinforcement learning. arXiv preprint arXiv:2209. 06666. 2022.
14

---

Published as a conference paper at ICLR 2025
Yue Wang, Alvaro Velasquez, George K Atia, Ashley Benter-Bennette, and Shaofeng Zou. Model-free robust average-reware reinforcement learning. In International Conference on Machine Learning. pp. 36431-36469, PMLR, 2023d.
Yue Wang, Jinjun Xiong, and Shaofeng Zou. Achieving the asymptotically optimal sample complexity of offline reinforcement learning: A dro-based approach. arXiv preprint arXiv:2305. 13289, 2023e.
Yue Wang. Jinjun Xiong, and Shaofeng Zou. Achieving the asymptotically minimax optimal sample complexity of offline reinforcement learning: A DRO-based approach. Transactions on Machine Learning Research, 2024c. ISSN 1835-8856. URL
net/ formm?
Id=Y7FbGcjOuD
Hua Wei, Jingxiao Chen, Xiyang Ji, Hongyang Qin, Minwen Deng, Siqin Li, Liang Wang, Weinan Zhang, Yong Yu, Liu Line, et al. Honor of kings arena: environment for generalization in competitive reinforcement learning. Advances in Neural Information Processing Systems, 35: 11881-11892, 2022.
Wolfram Wiesemann, Daniel Kuhn, and Berç Rustem. Robust Markov decision processes. Mathe- matics of Operations Research, 38(1):153-183, 2013.
Yifan Wu, George Tucker, and Ofir Nachum. Behavior regularized offline reinforcement learning. arXiv preprint arXiv:/911.1 1361, 2019.
Tengyang Xie and Nan Jiang. Batch value-function approximation with only realizability. arXiv preprint arXiv:2008.04990 2020.
Tengyang Xie and Nan Jiang. Batch value-function approximation with only realizability. In International Conference on Machine Learning, pp. 11404-11413. PMLR, 2021.
Tengyang Xie, Ching-An Cheng, Nan Jiang, Paul Mineiro, and Alekh Agarwal. Bellman-consistent pessimism for offline reinforcement learning. arXiv preprint (XXi:2106.00922 2021a.
Tengyang Xie, Nan Jiang, Huan Wang, Caiming Xiong, and Yu Bai. Policy finetuning: Bridg- ing sample-efficient offline and online reinforcement learning. Advances in neural information processing systems, 34:27395-27407, 2021b.
Huan Xu and Shie Mannor. Distributionally robust Markov decision processes. In Proc. Advances in Neural Information Processing Systems (NIPS), pp. 2505-25133 2010.
Huan Xu, Constantine Caramanis, and Sujay Sanghavi. Robust pea via outlier pursuit. In Advances in Neural Information Processing Systems, pp. 2496-2504, 2010.
Zaiyan Xu, Kishan Panaganti, and Dileep Kalathil. Improved sample complexity bounds for distribu- tionally robust reinforcement learning. In International Conference on Artificial Intelligence and Statistics, pp. 9728-9989 9754. PMLR, 2023.
Yuling Yan, Gen Li, Yuxin Chen, and Jianqing Fan. The efficacy of pessimism in asynchronous Q-learning. arXiv preprint arXiv:2203. 073668 2022.
Rui Yang, Chenjia Bai, Xiaoteng Ma, Zhaoran Wang, Chongjic Zhang, and Lei Han. Rorl: Robust offline reinforcement learning via conservative smoothing. Advances in neural information processing systems, 35:23851-23866 2022.
Rui Yang, Han Zhong, Jiawei Xu, Amy Zhang, Chongjie Zhang, Lei Han, and Tong Zhang Towards robust offline reinforcement learning under diverse data corruption. arXiv preprint arXiv:2310.12955, 2023.
Wenhao Yang. Liangyu Zhang, and Zhihua Zhang. Towards theoretical understandings of robust Markov decision processes: Sample complexity and asymptotics. arXiv preprint arXiv:2105.0300 033666 2021.
Ming Yin and Yu-Xiang Wang. Optimal uniform ope and model-based offline reinforcement learning in Hime-homogeneout reward- wwwerd-freeeae and aask-agnostic settings. arXiv preprint arXiv:2105.06029, 2021a.
15

---

Published as a conference paper at ICLR 2025
Ming Yin and Yu-Xiang Wang. Towards instance- optimaal offline reinforcement learning with pessimism. Advances in neural information processing systems, 34, 2021b.
Ming Yin, Yu Bai, and Yu-Xiang Wang. Near-optimal provable uniform convergence in offline policy evaluation for reinforcement learning. In International Conference on Artificial Intelligence and Statistics, pp. 1567-1575. PMLR, 2021a.
Ming Yin, Yu Bai, and Yu-Xiang Wang. Near-optimal offline reinforcement learning via double variance reduction. arXiv preprint avXiv:2102.01748 2021b.
Chao Yu, Jiming Liu, Shamim Nemati, and Guosheng Yin. Reinforcement learning in healtheare: A survey. ACM Computing Surveys (CSUR), 55(1):1-36, 2021.
Andrea Zanette, Martin Wainwright, and Emma Brunskill. Provable benefits of actor-critic methods for offline reinforcement learning, Advances in neural information processing systems, 34, 2021.
Wenhao Zhan, Baihe Huang, Audrey Huang, Nan Jiang, and Jason D Lee. Offline reinforcement learning with realizability and single-policy concentrability. arXiv preprint urXiv:220.004634, 2022.
Baohe Zhang, Raghu Rajan, Luis Pineda, Nathan Lambert, André Biedenkapp, Kurtland Chua, Frank Hutter, and Roberto Calandra. On the importance of hyperparameter optimization for model-based reinforcement learning. In International Conference Artificial Intelligence and Statistics, pp. 4015-4023. PMLR, 2021a.
Junyu Zhang, Alec Koppel, Amrit Singh Bedi, Csaba Szepesvari, and Mengdi Wang. Variational policy gradient method for reinforcement learning with general utilities. In Proc. Advances in Neural Information Processing Systems (NeurIPS), volume 33, pp.
2020.
Xuezhou Zhang, Yiding Chen, Xiaojin Zhu, and Wen Sun. Robust policy gradient against strong data corruption. In International Conference on Machine Learning, pp. 12391-12401. PMLR, 2021b.
Xuezhou Zhang, Yiding Chen, Xiaojin Zhu, and Wen Sun. Corruption-robust offline reinforcement learning. In International Conference Artificial Intelligence and Statistics, pp. 5757-5773. PMLR, 2022.
Wenshuai Zhao, Jorge Peña Queralta, and Tomi Westerlund. Sim-to-real transfer in deep reinforce- ment learning for robotics: a survey. 2020 IEEE symposium series on computational intelligence (SSCI), pp. 737-744. IEEE, 2020.
Ruida Zhou, Tao Liu, Min Cheng, Dileep Kalathil, PR Kumar, and Chao Tian. Natural actor-critic for robust reinforcement learning with function approximation. Advances in neural information processing systems, 36, 2024.
Zhengqing Zhou, Qinxun Bai, Zhengyuan Zhou, Linhai Qiu, Jose Blanchet, and Peter Glynn. Finite- sample regret bound for distributionally robust offline tabular reinforcement learning. In Proc. International Conference on Artifical Intelligence and Statistics (AISTATS), pp. 3331-3339. PMLR, 2021.
16

---

Published as a conference paper at ICLR 2025
A EXPERIMENTAL SETUP OF SECTION 8
A.1 GARNET PROBLEMS
For simulated MDP environments, we implement Algorithm on Garnet problems (20, 30, 20). G30,, 50, 30) and (50, 100, 50). Here, the branch number denotes the number of states that can be achieved after taking an action. The uncertainty radius Rs,a is randomly drawn from a uniform distribution ranging from 0.1 to 0.5 for all acteon pairs. The true robust expected values for the Garnet problems, over a certain state distribution, can be obtained via the model- -ased robust value iteration method. For each problem, we first generate a stochastic behavior policy with partial coverage over state-action pairs. To obtain a near-optimal stochastic behavior policy, we compute the Q-values for the nominal kernel, and adopt softmax transformation to assign probabílities for all state-action pairs. The randomness (i.e., optimality) of the behavior policy is controlled via temperature parameter tn2 1. State-action pairs with probabilities P... S 0.03 (for (20,, 30, 20)), P..a I 0.02 (for (330, 50, 30)) and P..a I 0.01 (for (50, 100, 50)) are then excluded to achieve partial coverage. Finally, non-zero elements are re-normalized to maintain valid probability distribution. By deploying the behavior policy on the nominal kernel, 10 datasets are generated at each dataset size from T 1000 to 20000. We compared the double-pessimism method with the
method in (Yan et al. 2022 We set 0.95, C. 1 x 10 and 5 0.02.
A.2 CLASSIC CONTROL PROBLEMS
Note in the Classic Control problems, the underlying uncertain environments may not be modeled using our perturbation- based uncertainty set in equation but we can still implement our algorithms to enhance the robustness. We generate the dataset according to random behavior policy, and implement Algorithm 3 with the radius R = т. In our experiments, we set y = 0.95, C. = I x 10-4 and 8 0.02. After policy is learned, we test its performance under perturbed environment with the parameter randomly generated from [-T, for 800 times, and plot the average performance among them.
B ADDITIONAL EXPERIMENT RESULTS
B.1 COMPARISONS IN TABULAR ENVIRONMENTS
In this section, we include additional experiment results under three simulated environments. Specif- ically, we consider the Frozen-L and Taxi environments from OpenAl Gym (Brockman et al. 2016), and the American Option problem (Panaganti et al. 2022 Shi & Chi 2022 /hou et al.) 2021). The transition dynamics of these environments can be directly controlled, and we construct Lo norm uncertainty sets centered at their nominal kernels. Similarly, we trained our double-pessimism Q-learning together with the single-pessimin pessimismm baseline, and plotted the optimality gap between the learned and optimal robust value functions. As the results F our double-pessimism Q-learning effectively obtains the optimal robust policy, whereas the single-pessimism Q-learning only achieves sub-optimal performance. The results hence indicate that our additional pessimism effectively enhances robustness against model uncertainty, verifying our theoretical results.
250
rg
Bess Lilaming
Ressivion
200
100
50-
3000
4000
Dacamut Size
0000
2002
30000
2020
6002
Datanal
6000
B000
30000
240
(a) Frozen-Lake
(b) Taxi
(c) American Option
Figure 3: Optimality gaps under different Gym environments.
17

---

Published as a conference paper at ICLR 2025
Dentlehesmmnn Queamin
Styfi OLeaming
150-
Double Sessirimm Learting Senle Prgie-Pssimse Luammng
395-
Deuble Fesdinte Lesminn
10c
Single Poser cr Dalamnay
100
25
250
750 1250 1500 1750 2000 Wimber of opoodes
510
1960 1250 1900
750
1500 2000
humber sploodes
Mumber of sodks
(a) T 0.6, CartPole-vO
(b) = 0.7, CartPole-vO
(c) 0.8, CartPole-vO
Figure 4: Reward profiles with different parameter perturbations.
B.2 SCALABLE ALGORITIMM WITH FUNCTION APPROXIMATION: DOUBLE CQL
In this section, we extend the evaluation of our double- pesbblem framework to large-scale problems using function approximation techniques. The algorithms presented earlier (Algorithm I Algo- rithm 3). while model-free, are designed for tabular settings and require memory space of ( for the Q-table, making them less efficient for large-scale applications. To improve scalability, replacing the Q-table with low-dimensional function approximations (e.g., neural networks) to reduce memory costs is a widely adopted approach. On the other hand, existing offline RL algorithms like
Conservative Q-learning (CQL. (Kumar et al. (2200) and Implicit Q-learning (IQL, (Kostrikov et al.
2021)), along with others (Ross & Bagnell 2012 Laroche al. 2019 Fujimoto et al. [2019] Kuman et al. 2019 Agarwal et al. 20.06) et al. 2020 Jin et 2022 Xie et al. 2021a)) Yin et al. 2021a
Rashidinejad al. 2021 Xie & Jiang 202 Jiang Huang, 2020), have focused solely offline
RL without model mismatch, resulting in degraded performance when model mismatch is present.
Aiming enhance both robustness and scalability, CQL algorithm, demonstrating that our framework is not limited to tabular settings but can also be integrated with function approximation or deep RL techniques, significantly improving robustness against model mismatch. Specifically, we employ the CQL method to impose pessimism on the limited dataset, and further incorporate an additional penalty term into the robust Bellman operator estimation to effectively mitigate model mismatch. Based on this construction, we can similarly design a double-pessimisn CQL algorithm, from which enhanced robustness expected.
design and evaluate double-pessimistt
20
40
0.2
(b) 0.5
(c) 0.8
Figure 5: Double-Pessimism CQL vs. Vanilla CQL under CartPole.
To validate the effectiveness of our Nouble-pessimisse principle, we compare our double-pest pessbe-- CQL with the vanilla pesle-- CQL under CartPole from OpenAl Gym. The policy is trained the nominal environment and evaluated randomly perturbed environments (perturbation radius 7) over 800 trials. The results, shown in Figure 5 display the average performance solid curves, with envelopes representing standard deviations.
As the results indicate, our double-pessimism CQL consistently outperforms the vanilla CQL in perturbed environments, demonstrating enhanced robustness. This experiment confirms the universal applicability of our algorithm used. It also highlights the scalability of our approach, which can be integrated with advanced deep offline RI algorithms for large-scale problems using function approximation.
framework in improving robustness, regardless of the specific
18

---

Published as a conference paper at ICLR 2025
B.3 ABLATION EXPERIMENTS
Our muuble-pessimisni principle addresses two key challenges: the first component tackles the limited dataset coverage in offline RL handle out-of-distribttion issues, while the second addresses model mismatch between the data generation and deployment environments.
In this section, conduct ablation experiments evaluate the effectiveness of this principle. Specif- ically, we compare four algorithms in an offline setting: vanilla Q-learning (with zero pessimism), robust Q-learning (with model--mssmtte pessimism only), offline non-robust Q-learning (with dataset pessimism only), and our proposed offline robust Q-learning (with double pessimism). The experi- ments are conducted on two Garnet problems, where we evaluate the robust value functions of the learned policies with respect to an uncertainty set defined by the -norm.
The results are shown Figure The solid curve represents the average value across 10 independent runs, while the shaded area indicates the maximum and minimum values observed.
Our peable-psssimism approach outperforms all four algorithms, including those with single source of pessimism, demonstrating the effectiveness of our framework. Furthermore, the single-pessimisiy methods achieve better performance than vanilla algorithm with no pessimism, highlighting the benefits of incorporating pessimism in offline robust RL. However, both ultimately outper- formed by our double-pe double-pessimine pessimism method, underscoring the importance addressing both sources of uncertainty through the double-pessimism principle.
Double
10
Single Mismatch Pessimism
Single Pessimism
Robust Value Function
Robust Value Function
Pessimism
4-
Double Pessimism
Single M smatch Pessimism
2-
Single Dataset Pessimism
250
500
750
1000
1250
1500
1750 2000
250
500
750
1250
2000
Dataset Size
Dataset Size
(a) (30, 10, 30)
(b) (40, 20,40) 40)
Figure 6: Robust value functions in Gamett problems.
C FURTHER DISCUSSION OF K.
C.I A UNIVERSAL CONSTRUCTION OF
In this section, we discuss the design of the penalty function x for universal uncertainty set models defined by some distribution divergence/distance functions F(-II-):
P= (P A(S) F(P + p) < R).
(24)
Note that this uncertainty set includes perturbed environments within a region centered around the nominal kernel, effectively modeling environmental uncertainty in practical applications. This because, in practice, perturbed environments should not deviate significantly from the nominal kernll and should therefore fall within defined region.
We first present the following theorem for universal construction of the penalty function k.
Theorem 4. Let kVV) be the optimal value of the following constrained problem:
max Σ V.V. S.f. Σ q =0, F(P + ql < R.
(25)
19

---

Published as a conference paper at ICLR 2025
Then, k(V) satisfies equation 15 i.e.
- PV-
S 5
dp(V).
(26)
Proof.
Note that the problem in equation 25 is equivalent to the problem
V where (q E R Σ q: al R).
VV,
(27)
The proof is then straightforward by noting that P C Q, hence
PV x(V) < min pV (V).
(28)
pEP
Such result provides universal construction of the penalty function K, for the perturbed-based uncertainty set as in equation 24 Note that x(V) depends on P, which is unknown in practice, but any unbiased estimation of it is sufficient. To illustrate this and show the generality of our design, we develop a case study for the x² divveeegee uncertainty set in the following section.
C.2 CASE STUDY: La -NOMM UNCERTAINTY SET
In this section, we provide a more detailed discussion on the la -nom uncertainty set. As discussed, we consider the relaxed l, -normm uncertainty set:
P.aa (Pa,a + q: Σ = 0, I Rs,ah:
(29)
where we relax the condition Ps.a + q 2 Then the worst-case transition w.r.t. P can be derived as
TB.0 (V) Ps.aV - =<(V,,
(30)
where
<(V) A R
Rmin wue - Vlla, weR
(31)
with 3 --I. For popular choices of a, the optimization problem in equation 31 has closed-form
solution, specified in Table 2 Kumar et al. 2023). Note that for the three choices of a 1,2, oo,
a
k(C)
max, v(s) mill, v(s)
V Σ, ((()) E, v(e) 2
2
Σ -=
(S+1)/22 v(x)) -E= (i=((8+1)/ v(s))
Table 2: Penalty term for la -norm uncertainty set
the resulting penalty terms incur a computational complexity of O(S). When combined with our algorithm, this leads to overall implementation complexity of O(SA) per step. In contrast, the bosedl-based methods proposed Shi & Chil 2022 Blanchet et al.) (203)) have a computational cost
of O(S² A) per step (Kumar et al. 2023), highlighting the superior efficiency and scalability of our approach.
Our algorithm and theoretical result will then characterize the convergence to the optimal robust policy w.r.t. P. More importantly, when the uncertainty radius R is small, the relaxation will not be effective, i.e., P- P (Zhou al. 2024
20

---

Published as a conference paper at ICLR 2025
C.3 CASE STUDY: X² UNCERTAINTY SET
We adapt the construction we obtained to the widely used ddviieegee as a case study. The design of ạ: for other uncertainty sets be obtained in similar way.
Specifically, the uncertainty defined for the (s, a)-pair is
2,a {Pa,0 + A(S) (Pa Pll S Ra,a):
(32)
where (pll)) = Σ, (pi-u.)² is the x2 -iviiverge We aim to design model-free function k that serves as the penalty term to address the uncertainty from the model mismatch.
We first establish the following lemma.
Lemma 5, The constrained problem
min Σ EVV.
V. S.I. Σ9 = =0 Pa.al)Pa.) S R.,a
(33)
has the solution
-Ba.a Rasa Varp,. (V).
(34)
Proof. To simplify the notation, we omit the subscript 8, a from Ps.a and R We note that if any entry P: then any feasible q O, otherwise the xi=divergence will be infinite. Thus, we can simply ignore the i-th entry in this case and only consider the remaining ones. Hence, we assume P. 0, vi without loss of generality.
Note that the condition Dx=(ạ + P(PP) < R is equivalent to
Σ
P. SR
(35)
hence the Lagrangian function of the constrained problem is
Σ of
-
L Σ 4v +v
R
(36)
From the KKT conditions (Bertsekas) μ² must satisfy
1997 the solution q² and the Lagrangian multipliers X and
2q
V + X
0, Vi.
(37)
P.
We first show that if d is the optimal solution, then Dy= PlIP) R. To show that this statement always holds, our claim is that there exists an optimal solution such that μr" = 0, then we have
=
(38)
and hence,
=
(39)
To prove that this claim is not possible, we provide counterexample to demonstrate that 1²" and Σ, q.' V, * O, which is contradiction:
For V [Vi, Va] and Ps.a |21, where Pl, P2 +
0. We have @2 -Qi, then
q
%
2
R.
(40)
P1
P2
Hence,
R
1ai
(41)
I
I
Pa
21

---

Published as a conference paper at ICLR 2025
The optimal value of the optimization problem is
V - 9V 201--00 V22.
(42)
Obviously, the optimization problem does not have an optimal solution, but instead an infimum. There always exists a feasible solution such that
Σ <0,
(43)
which means that 1² * 0 always holds. Thus,
V. = -xx - 2p (4h)
Vi,
(44)
P.
and hence,
(1t)²
Σ E -2p Σ
21 R.
(45)
P.
where we use the constraint E; ot = 0 and Σe
(/))² P.
= R.
Again, from equation 37 we have that
4(x²)2 2
(Vi+ + X7)?
(46)
Pj
and hence,
13 (V, + 27)3 P3
(47)
4(10)2
Taking the sum over i implics that
(g) )
+ X²)² 2²)
Σ
R Σ
P.
(48)
P.
4(H²)2
and hence,
2p¹ R
R Σ
Po(V++
(49)
On the other hand, note that equation
37 further implies that
0 Σ
P.V. X P:.
(50)
and hence,
x- Σ P.V.
(51)
Plugging in equation 49 implies that
2μ²R= RVarp(V).
(52)
Hence, from equation 45 the optimal solution of the constrained problem is then -v RRVarpPl (V). which completes the proof.
L
With the optimal solution to equation 33
we can then design the penalty function λ for the x² Firstly, we note that equation [3 is a relaxation of the support function over equation 32 therefore the optimal solution to equation 33 is not greater than
uncertainty set defined as in equation
32
22

---

Published as a conference paper at ICLR 2025
(V),,, and therefore is pessimistic penalty of the model mismatch. We thus design the penalty function as
<(V) = Σ P.V. - v RVarr(V).
(53)
We note that in the model-free setting, it is straightforward to obtain an unbiased estimation of which however requires more than sample. Specifically, for n i..dd samples (8, a, s{), = 1,... Rt the model-free penalty function is defined
> Li=1 (V(s) V)²
< <VV) V VRV
(54)
where -= V((()) Such a penalty function satisfies the condition equation of the pessimism principle, and hence we can extend our model-free algorithms to the divvieegee model. We present the algorithm for the infinite horizon in Algorithm 2
Different from Algorithm 3 for the
Algorithm 2 Double-Pessimismn Q-Learning for infinite-horizon RMDPs with -2-vverreence uncer- tainty set.
Input: D, target success probability 1 1 6, 1-7 log ST
Initialize: Qo (s, a)) 0, Vo(s) 0. no(s 0. Vss
for = 1,... do
Sample 2 samples
(1 a, s/: from D
ne (8
<- n (8-11, 0-11 + ( 0) t- n ( a), v(s,a) * (8--1,a-1)
ns( a);; The
(T 1)/ n)
bn co
T [9T0()))3]
n(1 11
M V4 1= (s:)+ (x,))
K - - - Rs ((V-1 - M) (V- M)
Qi (8 a)-1) = (1 mn) Qi-1 (8t-1, + nh
+ + 7n bn
Qi(s, a) = Qc-1(8, a) for all (s, a) (8--1,
Vi (s:-1) max maxacA Qe a), V2- (3h-1)
Vi(s) = (s) for all $1-1.
end for
f(s) arg A Qr(s,))
Output:
x2 diverreence model, we require samples at each step to estimate k. However, the estimation does not required any information on Ps.o and hence Algorithm is still model-free.
Note that generally the penalty function optimal robust policy. However, the robustness can still be enhanced due to the additional pessimism. We validate the effectiveness of our algorithm in optimizing performance under model mismatch in offline setting through numerical experiments. Specifically, implemented alongside the baseline single-pessimism Q-learning algorithm (Yan et al. (022) on Garnet problems with varying parameters, and three simulation environments: Frozen- Lake, Taxi, and American Option. Using datasets of different sizes, we computed the robust value function of the learned policy via dynamic programming (lyengar 2005), and plotted the results in Figure and Figure & Each curve represents the average over 10 independent runs, with the shaded region indicating the maximum and minimum values. As demonstrated the results, our double- pesble-pessimimm Q-learning significantly outperforms the single-pessimise approach, showcasing the robustness of our algorithm model mismatch and confirming the efficacy of our double couble-pessimisn design.
biased, thus the algorithm may not converge to the
algorithm
23

---

Published as a conference paper at ICLR 2025
Double-Pessimiss G-Learning
Singla-Passimism Q-Leariin
Robust value function
Robust function
12
12
10-
Double-Pessimism Q-Learning Single Pessimiss Q Q-Learning
4-
500 1000 1500 2000 2500 3000 3500 4000 Dataset
500
1000
1500
2000
2500
3000 3500 40co
Dataset size
(a) G15, 8, 15)
(b) ((0,, 10, 20)
Figure 7: Robust value functions of two Granet problems over X divergeee uncertainty set. Solid lines represent the mean values over 10 independent runs. Shaded areas represent the maximum and minimum values.
Do Jol NOS FrEm Learring Pertriin roaning
Tabous No1ae Puscton
-00
Feedrrinn Learring
regaitaasiimm Drues
trinnt 1iaeowo Fon Datamed Sibe
2000
10002 19960 20000
25000 30000 Dutiset Size
Datawet
(a) Frozen-Lake
Taxi
(c) American Option
Figure Robust value functions of three simulation environments over the x² diverrgene uncertainty set. Solid lines represent the mean values over 10 independent runs. Shaded areas represent the maximum and minimum values.
D ANALYSIS OF THE FINITE HORIZON SETTING
D.1 NOTATION
Recall the learning rate defined by
+1
(55)
H + n
for the n-th visit of given state-action pair given time step h. We further adopt two sequences of related quantities for any integers N 2 0 and n 2 1 from (Shi et al. 2022):
(1 7p) = 0, if N > 0,
Vo
(56)
if N 0
On 11: m,);
if N > n, N = n1
7
A
(57)
0.
if N <
has been shown (Shi et al. 2022
Yan et al.
2022 that
Σ m 1.
(58)
We also introduce the following notation:
24

---

Published as a conference paper at ICLR 2025
(s, a). or simply N The number of episodes that have visited the state-action pair (s, a) at step before the start of the k-th episode.
(8, a), or simply k": The index of the episode in which the state-action pair (8, a) is visited step for the n-th time. We adopt the convention that ko = 0.
PK E (0, 1J A row vector corresponding to the empirical transition at step h of the k-th episode, defined as
(s) = - s/t2)) for all 8,
(59)
x² {mf with (s) - arg max. Q (s, a) for all (h, E x The deterministic greedy policy at the beginning of the k-th episode.
#: The final output of the algorithm, corresponding to π k+1 defined above. For simplicity
in our analysis, we treat as " which does not affect the result.
D.2 LEMMAS FOR THEOREM 2
In this section, we present the lemmas that are utilized in the proof of Theorem
The first lemma demonstrates how our choice the penalty term & can address the uncertainty arising from model mismatch.
Lemma 6. (Theorem I in (Kumar et al. 2023 Let Ps.a a be the uncertainty set defined using the no-nrmm For any vector V, the following relationship holds:
Pa.a (V) = Pa.a V - Ko (V),
(60)
where K. is defined as in equation 18
The following lemma provides properties concerning the learning rates and is adapted from (Jin et al. 2018 Li et al. 202T).
Lemma 7 (Lemma in (Li Liet al.
202
For any integer N >> O, the following properties hold:
1
2
for all
1
(6la)
N
n2
Na
2
n=1
2H
2H
max Th
(m )2
<
Σ n=N
N < 1+
(61b)
ISREN
N
N
H
==1
The following lemmas concern the concentration properties of the sample generation.
The first lemma below is adapted from Xie et al. 2022bb Lemma A.1).
Lemma 8. (Lemma 8 in (Shi et al. 2022 Suppose N ~ Binomial (n, p), where n 2 1 and p E [o, 1].
For any 8 (0, 1), we have
8 log (1)
(62)
NV1
and
np
11)
1
2
if 2 8log
(63a)
8 log (1)
np
ifnp log (+) ifnp < 2 log (1)
N <
(63b)
2ea log (1)
with probability at least 1 1 48.
The following lemma is standard concentration inequlity result.
25

---

Published as a conference paper at ICLR 2025
Theorem 9 (Freedman's 's inequality (Freedman 1975)). Consider a filtration Fo, Fi F2 C.., and let Eg stand for the expectation conditioned on Fk. Suppose that Yn = =Kk=1 Xx E R, where { J is real-valued scalar sequence obeying
[x S R and
Ek-1 [&a] 0
for all k 2
for some quantity R < cc. We also define
n1 Wn
Bx [
In addition, suppose that Wn. S σ² holds deterministically for some given quantity o² < cc. Then,
for any positive integer m 2 1, with probability at least
8 one
Pr S max
o² (Wn.,
2m
4 R
2m
log
log
(64)
2m
3
8
The Freedman's 's inequality further implies several important results related to our problem.
Lemma 10. Let (WA E R |1 sisisk,1s H + 1] be collection of vectors satisfying the following properties:
Wi is fully determined by the samples collected up the end of the (h 1)-th step the i-th episode:
*Will I Cw.
For any positive integer N 2 H, consider the following sequence:
h, (N (PAW R - oh.s.a ( (b) = (8. a)}.
(65)
With probability at least
&
H
SAT
a,(s,a,,,N) N)
$ V C2 log
(66)
i=1
holds simultaneously for all s,,,s, e [K]
x
H
[K].
Proof. Let (s, (o.a)
From equation 61b
Lemma 7
we have
2H
(s.
Cu.
N
Given that Vark.s,a (W (((3a)) 4-1
C2 can apply Lemma 7 from Li al. 2021 to obtain, with
probability at least 1 6,
X,s,,a,,,N)
On log² SAT
Co
SAT 8
Th C2 +
Cn + V N
Cw
log
8
n=l
SAT
HOw N
SAT
log²
Cu +
log²
N
HC2
2 SAT
2A
log"
8
where the final line equation 61b from Lemma 7 again.
26

---

Published as a conference paper at ICLR 2025
Lemma 11. Let (s E R (s.a) E 8 A,1 K, s + 1 be collection of vectors satisfying the following properties:
Wh', a) is fully determined by the given state-action pair (s, a) and the samples collected up to the end of the (k- (k-18 1)th episode;
(W a) - Cw.
For any positive Ca 2 O, consider the following sequences:
d (o a/) p/ (ott ab)
X1,k _ Ca
W i ah)
Σ (pa(s,))Wht
(67)
(s.))SxA
( ah) d ( ah)
X1,8 & Ca
(5 + (3
Σ
d (
(68)
(a.0)SxA
Consider any E (0, 1). Then with probability at least 1 8,
K
K
NA.k
S
Σ
s
Σ
dp;,(8,a) a)
Pha W W (s, (s,a))² a))3 log + 2CaC log
2H
2H
8
1=1
(xa)ESxA
(69)
K X
2H
2H
S
Σ
CC
Σ
(pinssc))Phoo ( (s, a)]² log + 2C log
8
(sa)ESxA
(70)
hold simultaneously for all h [H].
Proof. The proof similarly follows from (Shi al. 2022
We then prove Lemma showing the effectiveness of our double pessimism principle, i.e., that our estimation conservative estimation of the robust value function.
Lemma 12. Consider any d E (0, 1), and suppose that cs > 0 is some sufficiently large constant. Then, with probability at least 1 1-66 8,
(a,a) Th
(x.0)
(s.a))
Thaaa (V (V
Ph
(s.a) (s,a)) (("")))) + R h+1
ht1
Σ
me
N (s.a)
bu
(71)
holds simultaneously for all (k. h, s) E [K] x H x S x A. and
(s) S V=* (8) S (*)
(72)
holds simultaneously for all (k, h 8) E [K] x H x S.
Proof. Proof of inequality equation 71, We show it by invoking Lemma 10 Let
Wh+ Vit
which satisfies
1 H=
Note that it holds that
(s,a) ph" (s,a)) (s.a) (s,a) (2ao Thea,a ht1
Ph.a "hks (s,a) Ry (V.""'a))))))) ph (s.a) (tt (c,o)
+ R RVaas(Vi""l.
h+1
27

---

Published as a conference paper at ICLR 2025
Pr P, (s,a)
ph
(s.aa) ( (s.a) h+1
(73)
1+11
where the first equation is from Lemma 6 Hence applying Lemma 10 1mpples that with probability at least 1 5,
(a,a)
No. (x:0)
( Ph"
(a."( (a,)))
+ Rs (V
Th
(a.0)
(s,0)
(Phisa - ppo
yh"
Un
ht1
Σ Xi(s, a, (
H322
S C/ N (s,
(74)
holds simultaneously for all (8, a, k. h) SSX A K] x [H] provided that the constant C > 0 is
large enough and that N -N, > O. When N (s, 0, we have the trivial bound
(aia,)
Th
(s,0))
Phi,aa
ph (s,a)
h+1
(s,a) 0.
(75)
Additionally, from the definition bn =chy
13,2
we observe that
Ntts,a Nh Exnr Th
by
cov
200
H
if (
(76)
(s,a)
(s,a))
En Th
bn 0,
if (=,a)) =
holds simultancously for all a, k SXEEXXAX [ x [K], which follows directly from the property equation 6la in Lemma
Combining the above, equation 74 and equation 76 hence imply that
(T.a))
(ala))
Thee, Oh.e,aVVi (V*" ph (s,a) (s.a)) + ae (V (x(aa)))))) h+l
Th
htl
n=1
N (s.a)
Ngla,a)
Ih bn.
Proof of inequality equation 72 Note that the second inequality of equation 72 is straightforward as
(s) (s)
holds for any policy As consequence, it suffices to establish the first inequality of equation
72
(s) & V (s) for all (s, S. k) e Sxx [H] x [K].
(77)
Define
ho (o, k, max {1:1< and (s((s) max (s, a)}
(78)
for any (h, kt 8) E [H] x [K] x S. which denotes the index of the latest episode before the end
of the (A: - 1) episode in which (s) has been updated. We abbreviate k. (h, h. s) as K (h)
whenever is clear from the context.
We utilize induction approach to show that. Assume that
V (6)
VF (s) for all (K', T) -k- HH S,
(79a)
28

---

Published as a conference paper at ICLR 2025
(6) s VF (6)
for all r 2 h 1 and 8.
(79b)
We need to verify
(s) s (s)
(8)
for all S.
(80)
Step 1: base case.
Let us begin with the base case when 1 H + 1 for all episodes & [K]. Recognizing the fact that V V##+1 0 for any ıt and any &o [K], we directly arrive at
(+) - v
for all (k, s) E [K] X
(81)
Step 2: induction. To justify equation 80 under the induction hypothesis equation 79 the difference term to obtain
we decompose
V (s) (s) Vi (s) max { max (s, a), 1
=QT"" (s, (+)) max max Q a). (s).
(82)
where the line holds since (s) has not been updated during episodes kio (h), (1)++1,,... k
(in view of the definition of ki (h) in equation 78). We shall prove that the right-hand side of
equation 82 non-negative by discussing the following two cases separately.
Case 1. Consider the case where V/" (s) max. (s, Note that
T arg max (s,
when VA (s) max (8,
(83)
holds for all (k, h) [K] x [H.. Thus
Vi (s) - (s) = Q (s)) max (s,
= Q (s,
- Q (s, (s))
(84)
To continue, we turn to controlling a more general term Q (s, a) - Q (s, a) for all (s, S x A. .
Invoking the fact Vio >
No Tm
(see equation 56 and equation 58) leads to
(s, = "o N² Q (s, a) +
na Nk Q (s,
This relation combined with equation 106 allows us express the difference between Q and Q as follows
Q (s. a) as)
N²
Nº
(QT (s, -Qh(sa))) +
Σ
No
QTT ((s,a)-r((s)) - - V/A" v= + R bn)
= =1h
mh
n=1
N
(
No Nlu
Qu (s,a) (s,a)-Q((s,a))
+ Σ
No nn
Phosaaae Re.ati(Vtt')) V + Re (vt2 + bn
n=1
(b)
No Pr.s.av' - Rs Rs.ak(VVr"" h+rl - ( + R
(V++) + bn]
N
No
(V - (V + nr (.. (Vb6") - Vi Rgan((Ve" (V++1) bn)
7/
N
(d)
NO [Phnaa -Phh") Vh+l bn)
7/2
(85)
29

---

Published as a conference paper at ICLR 2025
Here, (a) invokes the robust Bellman equation Q (s,a) rn(s,a) + hh,,a (V (b) holds since
Q% (s.a) 2 0 Q) (s. a); (c) is from Lemma 6 and (d) comes from the fact
V h++ 2 V
h++
owing to the induction hypothesis in equation 79 as well as the monotonicity of VA-1 in Lemma Consequently, it follows from equation 85 that
0% (s, a) - a%
(e.0)
(a,a
Σ
T/e
(a(a))))
(Prisaa Pht (oo)(
(ea(( h+1
+
th
NY
a=1
(a.0)
Tn
bn
Σ
The
(Ph.s.a pf
(s.))
4+1
(86)
for all state-action pair (s, a). where the last inequality holds due to the bound in equation 71 in
Lemma 12] Plugging the above result into equation 88 directly establishes that
V (s) Q7 (s. Qh
(s,s a (s)) 0.
(87)
Case 2. When (s) = (kk) (s), it indicates that
(M) (s) = max 2h (s. a),
ka( (s) = arg max ( (s,a), h
(88)
which follows from the definition of (h) in equation 78 and the corresponding fact in equation 83 We also make note of the fact that
(s) = A (s))))s)),
(89)
which holds since (s) (and hence (s)) has not been updated during episodes ko (h), ko (h)
1, ... k (in view of the definition equation 78p. Combining the above two results, we can show that
V (s) -s) Q (x,))(s)) Vnh (1)) Q (s, m+)(s) max No (8,
Q
Q (s, Th ka) (s)) 2n.((1) (s, nh (k))))
(N)
0,
(90)
where the final line can be verified using exactly the same argument as in the previous case to show equation 85 and then equation 87 Here, we omit the proof of this step for brevity.
To conclude, substituting the relations equation equation 82 we arrive at
87 and equation 90 in the above two cases back into
(s) Vi+(s) 2 0
desired in equation
80 This immediately completes the induction argument.
Lemma 13. With probability at least 1 - ò, it holds that
()(().))
Σ
(s
Th
Ni(a.a) (oh,o,a (Viit) - oh.saa h+11
(91)
Rm (s.
K
2H
2H
drstt(s) (5) (Vitt(s)) V/4 ( 24 H²C* log
+ 12HC* log
8
k=lses
Proof. is sufficient to show that
K
N (s.a) Σ (s,)),
Ni(ana)
(ohea(Vitt)) - Thisa (V (g(,a))))))
A
Ma
h+1
(92)
k= (3,0)ESxA
==1
=AA.k
30

---

Published as a conference paper at ICLR 2025
K
2H 8
2H
1 +
Σ SES
d p (8) (Vh+1(s) - V ( +24/ H2C log
+ 12H log
H
k=1
=:Bi,k
Define two auxiliary sequences {Yi, 1K k== and (Z 1K which are the empirical estimates of Ab,k
and k respectively. For any time step h in episode k, Yn. and Zn are defined as follows
Th ah
(ohett (V(itt)) - ohohiat ah (V/+1
h+11 (
d/ (5 a
( (sh, aft) d'p, (sh, oft))
Zh.k
+
(onot (Vi+1) Ohittaa (V (Vitz))
Note that
K
K d ( a
(otoiaaht Σ n=
No Nhttiat
(ohit at (Vi+z) onokiao 1+1
(V
n
Th
d (s aht
K
dr (oh a/p)
No
(shaaa))
The mhachioss } (ousshos (Vi+t) - Ohoohoot (Vi+t))
dr (sh2 a/p))
1=
(oh
(93)
d (sh att) 1 d (on, att)
(Thot, of of (Vi+1) oistiat (Vh+i))
Σ
Zh.k-
(94)
k=
Here, (a) holds by replacing k* ax with and gathering all terms that involve Vi+1 V h+1
; in the
last line, we have invoked the property Σ No (s,a)
Nn= Th N= Th = 1 1/H (see equation 61b
together with the fact V V 2 (see Lemma 12.. and have further replaced with
With the above relation in hand, in order to verify equation 93 terms
we further decompose A,, into several
A
A
Yn + Σ
(An,k
Yn.k)
Σ k=1
Zn,k k +
(An,k Yn.k)
k=1
k=1
k=1
k=1
K
K
BAnk
+
(Zn,k
Back) +
(An, Vn,k)
(95)
k=1
where (a) follows from equation
94
As result, it remains to control Ek (Zh, BB, and Ek (Ar, - Yn.k) separately in the following.
Step controlling Σk (An.k Vn We shall first control this term by means of Lemma Specifically, consider
(o(a)) (*(a,a))
Σ
N
(onena(Vin1) onaa (V
V (V
Ca =
(96)
which satisfies
| <
Σ
nn
(x.a,)
(11a + 1 (((aa))))))))))))))))){)))))))
2H Cw.
(97)
==1
31

---

Published as a conference paper at ICLR 2025
Here, we use the fact that Vo
Nk
Σ 2n=1
No
No
(see equation 56 and equation 58 Then, applying
Lemma 11 with equation 96
have with probability at least 8, the following inequality holds
true
(An Yn.k)
Σ X1.
2H [ (*, a) log + 2Ca Cw log
2H
CC
Σ (s,a)ESXA
T (8, a)
k=1
2H
2H 8
s 16 H2C*K log
+ 4HO" log
(98)
8
where the last inequality is from W (s. & Vi
(= 10 S H.
Step 2: controlling E (Zn,s B. Similarly, we shall control Σ (Zn,k BR, by invok-
ing Lemma
Recall that
d ( att)
Zn.N Bi.
+
di (s att (ohst (Vi+t) n (V
1 + H
Σ dp)+1(() (Vi+z(s) Vi+t(()),
(99)
xES
and let us consider
( = o (Vi++)) Th -h.sk (V/42))
Ca = 1+ s
(100)
which satisfies
W (s, & Vittlllo + || S 2H =: Ow
(101)
Similarly, in view Lemma II
we can show that with probability least 1 8.
K
Br,k Zn,k)
Σ X1.k
2H SHC* log
2H
S 1 H2CK log
(102)
8
Step putting all this together: Substitution results in equation 98 and equation 102 back into equation 95 completes the proof of equation 93 as follows
K
K
A
BA.k
+
(Zn.
BAnk)
+
(An,k - Yn.k)
k=
k=1
2H H2C* log 5
2H
B 24
12H log
This hence completes the proof.
term Exn E(sa)sSXA df (s, a) Nt(sa) H
Lemma
14.
Denote the
Z E(sa)ESxA A (s, a) D (a Nhts,,) bn by In- Consider any 8 E (0.
With
probability at least 8, we have
B
2H 2H + 12HC* log HCCK log 8
Σ
In + 24
H
E H SC* + HH
(103)
where recall that == log (SAT).
32

---

Published as a conference paper at ICLR 2025
Proof. The proof can be obtained by directly following the proof in (Shi al. 2022) and is hence omitted here.
D.3 PROOF OF THEOREM 2
We then proceed to the proof.
Theorem 15. (Restatement of Theorem 2 Consider any E (0, 1). Suppose that the behavior policy I satisfies Assumption I There exists some universal constant Ca. such that if we set log (STT) and set T > SC*", then the policy at returned by Algorithm 7 (saiisfes
HCSC
( S C
(104)
T
with probability at least 1 5.
Proof. For any state-action pair (s, a), according to the update rule specified in Algorithm 1 we have
(5, Q x + (s,
th 1h (s. + ANy (T((s,a) v (sh+1) R. (V
DNN
(105)
where the first identity holds because v. denotes the most recent episode before k that visits (s, a) at step h, and the learning rate is defined as in equation 55 Note that J-N% always holds. Applying the above relation recursively and using the notation defined in equation 56 we obtain
N
(h(saa)= = No a)
N Q/s,,)))))+ Σ Th n=1
(Ta(s,a)
v (sh+t)) (e. - by)) (106)
Applying Lemmal
12
the optimality gap term equation 104 can be decomposed follows
(p)
VP(())
E - E
[V][
[VT (s1)
E
[Vi"(s1)]
[V (s1)]
Spmpp
slap
K
E Vi+(s))] Stoup
[F((s))]
SIMP
K
of (s) (Vi V+(()))
(107)
A=1
where (a) follows from Lemma 12 (i.e., VT (8) Vi((s) for all S), (b) results from the
monotonicity property in Lemma 12, and the final equality holds because di (s) p(s).
We then bound the right-hand side of equation 107 Since n² is deterministie policy, d7 (8)
(s)) And from the fact that (s) 2 max. (s, 2 (8) and (s)(s)
(7, oī (s)), we have that
K
P.h (s) (V)(() v*)())
k=
SES
K
Σ
Σ
Jp (s, (s)) (V) (s)
33

---

Published as a conference paper at ICLR 2025
K
d (8, (x)) (0% (s,(s,))ss) (% =T())
k= SES
Σ
Σ
( a) (s, ())
(108)
(s,0)ExA
for any h E [H], where the last identity holds because
(s, a) =
for any a + (s).
(109)
To further bound the term (8(8,)) a) Q (s, a) in equation 108 we first adapt equation 58 and have that
N a))
@h( = mh
No
N
No (h a) +
N (s,
1
Th
= %
No (7 +
Σ
No The
(ra(s,a) + oh.aa(Vit))))
(110)
where the second line follows from the robust Bellman's optimality equation. Combining equation 106 and equation 110 implies that
(s) ((((s)))
N
= No
(Q) Qh(,,a)) ())((a)))
Σ
Nº
(on,aa(Vi+))) (Vi+1)
V (
a bn
Un
N²
Nk.
1/0
N (8) (h) +
Σ
Th
Nº
bn
Σ
mn (oh,,a(Vitz) Th.na (Vh
N
N Σ
Nx Tm
(Ph,o,a - ph Vh+t1
(111)
n=1
N
1 No
H + 2
No. Th
bn
No nh
(an (onns.(Vit))) Th.a.a -hha,a(V (V/+1)),
(112)
where (a) is from Lemma 6 and the definition of pl VA" = Vi (s ). and the last inequality
follows from the fact Q1 (8, (s) (s. a) 0 < H and equation 71 in Lemma 12 Plug
equation 112 in equation 108 we have that
d (8) (v) (s))
k=l
K
K H +2
Σ
Σ
as a (x.0))
Σ
Σ
(3,
Σ
(h bn
nn
k= (s.a)ExxA
k=
(x.)EExA
n=l
(g Σ
Σ
(s)))
ma
Ni(e,a)
(oh.s - ohhe,a(Vh"")))
(113)
(a.0)ESxA
34

---

Published as a conference paper at ICLR 2025
We then bound the last term the right-hand side of equation 113 implies that
By applying Lemma
B
(s) (s) - (s))
k=1sES
+
p (Vh+i(s) -Vh+i())
k= dES
2H + L. + 2 1 log 5
2H
+ 12H1 log
(114)
Recursively applying equation 114 over the time steps H, 1, 1: , with the terminal condition V
11+1 V 11+1 = 0 further implies that
K
oi (s) (Vi(ss) - (s)
k= SES
K
ΣΣ (s) (Vi(s) (s))
max NE[H] NES
H
2H In + 24 HCC* log
2H 8
Σ
+ 12HC* log
(115)
Finally, to bound the right-hand side of equation 115 which yields
we combine Lemma and equation 107
(p) -
di (s) (VT(s) v+))
K
R= 1 NES
K
(s) (V%(s) (s)
max KE(H
k=1sES
Ca
H
Co H2S
Co
HBSC*
Ca
SC
2
K
2
T
H
$
c
(116)
T
for some sufficiently large constant Ca 0, where the last inequality is valid long T > This hence completes the proof of Theorem
S0*
E ANALYSIS OF THE INFINITE HORIZON SETTING
E. ALGORITHM FOR INFINITE HORIZON
In this section, we present the analysis of the infinite horizon robust MDPs
E.2 NOTATION
The notation used in the proof for the infinite horizon setting is largely similar to that used in the finite horizon case. For any state s and action
A. define:
Ps. = P(- s. gixs
to be the (s, a)-th of probability transition matrix P E RAXS
35

---

Published as a conference paper at ICLR 2025
Algorithm 3 (Double-Pessimisse Q-Learning for infinite-horizon RMDPs.
Input: D, target success probability 1 6, uncertainty set radius R. 1-y log
penalty
function
Initialize: Qo (s. = 0, Vo(s) O, no(s, a) = O, Vs,a
fort= 1,... do
Sample a sample (5 0,-1, St) from D nh (51-1, 01-1) x n4 18 (1-1) 1; me(s, a) m-, V(s,a) (8--1, a1-1)
n - (8 a); Th f (T
+ 1)/ n)
T (9776))776)
bn - cby
m(1-2)"
Qi (st-1,)
(1-1m) mm) Q:-1 (8t-1, + mmfr (s1-1, + 7V/-1 (3t)
- (V--1) (V--1) - bn
Qi(8, a) = Qi-1Q1,0000 a) for all (8, # 9t-1,00-1
Vi (s:-1) = max
maxacA Qt (8)-1, (1-1(1--1))
Vi(s) Vs- for all # $1-1.
end for
7(s) arg m Qr(s, Output: म
For any t 2 0, we define Pt E RSAx5 to be an empirical probability transition matrix, given by:
P((s' 8,a) = [1.
if as) = (s.-1,
(117)
0, otherwise
for all 8, s' E S and a A. For any deterministic policy introduce two probability transition kernels: P. S + A(S) and pa S A A(S x A), defined as follows:
Pa (s) P(s' s, s,
(118a)
( P(s' |s,a),
if = = 0, otherwise
pd (a a' s,a)
(118b)
for any (s, (s, ESXA Additionally, we define p=' to be distribution over S x A such that:
p(s), =f==
p" (s,
(119)
10, otherwise
For any sequence {at)aa and two integers mi and m2, we define:
m2
E Eimnas (1y.0 0s, if max mi S min(ng, m2)
min(nn mn))
Σ
0,
otherwise
36

---

Published as a conference paper at ICLR 2025
E.3 LEMMAS FOR THEOREM
Lemma 16. (Lemma 4.1 in (Jin et al. 2018), Lemma I in Li et al. ) Recall the learning rates
1/ IT j=it1 (1 -7),,
ift >
and where ni (I (T + 1). Then
1o II (1 71))
7 0,
if
(120)
if t < i,
1. For any integer t 2 1, Ei= 1/. and n/ = 0.
2. For any integer i 2 and any 1/2 S a 1,
1
1
<
ja
to
3. For any integer t 2 1,
2r
2r v
max o S
and
(nb)
KE|M]
t
t
4. For any integer i 1,
0
Σ
7 1 t=1
We then present the following lemma to establish an upper bound on Q* - Q2, and simultancously justify that the value function estimate Ve is always pessimistic view of V*a (and hence V*). Lemma 17. With probability exceeding
8, for all 8 E S and t. E (T), it holds that
(*())*(ss) (x n (()x((())) (s)) S Σ th (o - (e)r)) + Br x² (s)), (121)
where n = nx(8, (s)) and we define
Bn (s, x xs)) = Bn = =300 n n1(1 (1117)) 7)3/
in addition, we also have
(())
E.
(122)
Proof. Proof of equation 121.
Consider any given pair (s, S A and denote nr(s, a), the total number of times that (s, a) has been visited prior to time t. Set ko -1, and let
k; = min { {0 <T k- (sk, ax) = (s. a) }.r}
(123)
for each S iigi T. Clearly, each k; is a stopping time. In view of the update rule, we have
Qi (s, Σ 72
th (r(.0) + (sk.-1) - -vo()))) by (s.a)
which together with the robust Bellman optimality equation gives
(Q -Qe) (8,a)
= r rs, a) + (V=) n (r(,0) + VVe (Sk+41) - 7V((V)) - by (s,
37

---

Published as a conference paper at ICLR 2025
n Σ "/ { VV,,
=00,,a(V*)
(V,(V,)) - by
1=1
Uz (v + Σ the - 1=1
Σ ?i ((p- 1op-Pale Pry) (8, + Σ n b (s.a), (124) 1=1
where the last two lines are valid since Σi=1 1// (cf. Lemma 16 and Lemma
Henceforth, we only focus on the case where = xt (s). Define F; to be the a-field generated by {(s; (:) a))= It is straightforward to check that for any S TT,
[I (MP-
(s,
}
i=1
a martingale difference sequence with respect to (Fi Hoeffding incquality together with the basic bound V4, s0 I
Then, we can invoke the Azuma-
to show that for any fixed E S I-7
and r E [T].
Σ IRsTTn ((s))s)Va: (s, (o,,
ST
log
r
ST
24
log
(1--))
8
holds with probability exceeding 8/(ST). Here, the last line utilizes Lemma 16 Taking the union bound over r S. 'I' allows us to replace with = ne(s, a) in the above inequality, namely, for any fixed E S and E A, with probability exceeding 8/S we have
Σ th y ((P -P-PP) PP.) (s)
S
(125)
n (1 (1-
holds for all n = na(s, T"' (s)) with 1 S < T. In view of Lemma know that
16 for any E S and E A we
m.(a,) (.(s. (s, s 201
Tt
V ne(s, a) (1 7)
(126)
me(8,a) (1 1 7)²
Therefore, when os is sufficiently large, it follows that
Q.) (s,, < Σ The
- (s, + 300g
n n2 71
Taking the union bound over s E and defining
I'
(n, ग (s)) = =300 n - 7
we can conclude that with probability exceeding - 6,
(Q' - Q+) (s, ST T
nh (oam)(()((*)) 0 (s,x)()((V2.))) + (s)
for all s and E [T].
Proof of equation 122 Note that V* > y*, holds trivially due to the optimality of V*, We are therefore left with showing V > Vi. Suppose for the moment that with probability exceeding 1
for all s E S, f. E (T) and E [t], it holds that
(Q* - Q2) (s, (s)) (oam (e)m)())(())))
(me(s, m((s) 2 21}
(127)
38

---

Published as a conference paper at ICLR 2025
the proof of this claim [27 is deferred to later. As consequence, for every E S and t [T), there exists j(t) E [t] such that
(V (s) (s)
Q (t)) 1s00
eT (s, (s
Iv
min {1 (s)) o os, .0}
IV
min ( ( (o
- (s .0]
Here, (a) and (b) hold since the update rule asserts that there must exist some j(t I t such that Vi(s) Vin (s) Qite) (s)) and (s)s) (y(1) (s); (c) utilizes 127); and (d) follows from the monotonicity of Ve in (by construction). By setting
8mn = arg min (V*L - (8),
sES
can deduce that
2 min {o Amino (8min) (VAt) - smi 550 5mm (8min) (50)) (m))) (Vi)).0}
(V Vi) (Smin)
2 min
min SES
(V - V1) (s), (8).
-min {7 (V V,) (smin) .0
which together with the assumption 0 < 7 < immediately gives
(V*r - V1) (8min) 2 0.
Given that (V*+ Vi) (s) 2 (V Vi) (8min) for every & E S, we conclude the proof.
Now we show equation 127 First of all, if ne (8, (+)) = 0, then for all j E [4], Q3 (s, (+)) =
since it is never updated; therefore, 127 holds true. From on, we shall only focus the when ne (s)) 2
Consider any s E S, t E [T] and j E [t. For the moment, let us define {k+)T_ w.r.t. the state-action
pair (s, TT(s)) in the same way as 123 We can then repeat the argument in 124 to decompose
(Q -i) (e))))
ny (x)))
vo+ (T())
(((() {
(r(s)T((s) + +VV, (Sk,+1) (0 bu (())
m
ny(s
()((m)(())) of (o (o - ( + ((P ((- Ph.) Pm. (ss (s,))((s)}
Th
(s))
Σ
(,
M (x))
(((T((()))
Σ
n
7
min Isish
(V) - - (V.ee(
(s)
Σ
((( Pko) Vks) (c()))
(x)r
Σ
by (5, (T)s
17:
? (Da.m.())
39

---

Published as a conference paper at ICLR 2025
ny (1(3)1(())) Σ
( 7
Pa.) Vo. (T())) + c ns(8, Tee (8)) (1 7)²-
r
(x(( ()(s)=((()) 1
Here, the last inequality follows from 126.. as well as the facts that Di=1 Ml (cf. Lemma [6) and that V2 is non-decreasing in L. It thus boils down to showing that for every & E S, I [T] and j [d].
ny(s,
Σ
((P
Te ny
(128)
(s) - 7)²
this were true and cb is sufficiently large, then we could combine the above two inequalities to conclude the proof of (12
We then prove the inequality equation 128 Notice that for all (s, my (x)) such that (s TT(s)) 2 1, must appear at least once in the sample trajectory. Therefore it suffices to show that for all 0 S < and E [2], it holds that
The (s)
((( 7 PP.. (s1,0t) oz) S 7b
ne(si, ar) (1 1 7)2
where we abuse the notation by defining {k: for the state-action pair (st, ai) in the same way as (23). Furthermore, it suffices to only check those (s), at) in the sample trajectory that were visited for the first time, i.e., mi(s), a1) 0 and m141(51, at) 1. It straightforward to check that, for any 1 < ST,
((P-
(s), (s),ai)) i=1
}
martingale difference sequence with respect to {Fih2o. where Fi is the o-field generated by {(s;, hin- Then, we can invoke the Houma-Hoeffding inequality to show that: for any such (st, ai) and any [T). with probability exceeding - 8/T?.
Σ MusTTn
(st, Vv.)
S
(nF) log
T 8
Tt 7
7)
Taking the union bound over r E [T] allows us to replace t with (s), ai) in the above inequality, namely, this shows that for any such (s), ai), with probability exceeding 8/T have
pe(eraz)) Th
T
(P-P.t)
Pk.) Vo:) (st, ai) S (i)s 71
for all E (T). Taking the union bound over all such (s1, at) (which are concerned with at most T pairs), we see that with probability exceeding 1 1-66 6,
me(eraz) Σ 1=1
ma(s),a1)
(ip-Pk))ii Vis (s), ai) S
Tt
n
at) (1 7)
is valid for any < j T and any [T]. This establishes the inequality equation 128 thus concluding the proof.
Next, we define two disjoint sets of state-action pairs, divided based on the associated occupancy probability induced by the behavior policy:
8
I =
(s, 15.7"(6 I S, (x)) 2
(129a)
ST
5
I (s. | U. ub S. <
(129b)
ST
It turns that the state-action pairs in Ie are rarely visited, formalized by the following lemma.
40

---

Published as a conference paper at ICLR 2025
Lemma 18. (Lemma 3 in (Yan al.
2022 WWith probability exceeding 1 6, we have
I ((t, 12
Lemma 19. (Lemma 5 in Yan et al. {st, of) K
2022
We can construct an auxiliary set of random variables
satisfying
(sk. o)) =1kksk lid.
pb.
(130a)
P{ (sk dbt = (8kT45, @xr+s) for all k S K - 13 2 T
(130b)
and
(5h o4) is independent of (st, St (k- - [)
(130c)
Lemma 20. (Lemma 4 in Yan et al. )022 Ler I =
1 log
ST 8
for some 0 < < 1. For any
vector with non- non-negative entries V E R2 we have
Σ
(
(c + (1 |
(131)
==
E.4
PROOF OF THEORAM 3
Following
Yan al. 2022,, we similarly define the following terms first:
0j
37 /
(o(P+)) 13] (s)) min Pniterrcon 1- 1 )
0
1 F
1-
EES
1 (5)
(o(Pa)) - - + + { (1+ 7
37541
1+ (1+1)
E =
(p(Pa.)tt V -Vo),
1 (1+
E
na(saa)
Σ
1 (pmi)) (5,
pe(s,a) Paia (V* - Vi((s,a))
A=tria (8) LAES,aEA
[pr (pa y1 (st, at)
ne(s)ra))
-1+ D
velosaed Pecice (V' Vislonail) ?
1/b (81, at)
3j42
[or (Px yo] (st, at)
1
=
1
Ps Panne (V*-V))
Ab (8t, at)
1 (1+1 1
(pFt)r (8, Ps Pa.a (V* (V*
sES,aEA
where we recall the definition of I in equation 129
We then proceed to the proof.
Theorem 21. (Restatement of Theorem 3 Consider any E (0. Suppose that the behavior policy
satisfies Assumption 2 The policy से returned by Algorithm 3 satisfies
(p) - (p) =0 (
C*S
C'S T(1 71-
C*
(
+
(132)
T(1-7))
with probability at least 1 5.
41

---

Published as a conference paper at ICLR 2025
Proof. Note that
T v
(2- @ vo) S (e, V
VT) (b)
1
E
(,.v
- vi)
00
(133)
Here, (a) holds true according to Lemma 17 (b) follows from the monotonicity of V in (by construction); and (c) follows simply from the definition of og- We then turn attention to bounding ao, towards which we observe that
fmild
VO Vi) + Σ Ep(s) min (o Vi(+), -V(()) 1 } 1-
00 Σ
t= (6) SES
fmx(6)-1
(0 V0 Vo.V*-WW -Vi) + Σ
Ex(s) min { (x( ( و-
1
tmm Emii (4) SES
(mx(
mels, (s))
(p, V - Vi) + Σ
Σ
ps))
Di
ue(s,* (Ta -0 (s) (Va.))
1=taie (5) sEB
T
p (8) min (mnterro)(( 1-75
1
+
1=1 SES
Here, the first identity holds since (*)) (s) (s)) and 0 (*) Vv(s) S 11/(1- 7) for all E S, the second line relies on the fact that (s) 2 max, Qi(s, a) 2 (=ss while the last line invokes Lemma 17 by
With probability exceeding 1 - 8, the first term ( can be upper bounded
SSY Σ Ep(s)
Σ
mn (x))
(oa) - 0,)= (.,=x))))))))x)))) (v)
n
t= (d) SES
Mb (8, a) p=¹ (s,a)
Me(o.a)
7 Σ
Σ
ne(s,a)
P (s) (V* - (Vk.
m
bb (s)
t= tmin (8) sES
T
Mb (8,a) p= (s,a)
m((aa)
Ra.a
1
(1.0)) (x(V²* - << <<(V).))
14b (8,
(= sES,aEA
1=1
me(saa
14 (8, p= (s,
5 7 Σ
Σ
me(s,a) T
(e) (V* - -vx)
bb (s)
t= (8) sES,aEA
ne(s.a)
Mb (8, p= (3, Pb (8)
2
Σ
Σ
Raa
Σ
T/
me(s,a)
(V* VV=VVe) ViL)
t= (d) sES,aed
1=1
where we utilize the fact that V 2 Vv, and x is I-Lipschitz. Hence we further have that
ag
T
Mb (s,a) 0" (s,a) ni(s.a)
< (1+ Rh Σ
Σ
ml(s,a)
Pe (o) (V* - Vv.)
1/b 1b (8,
tm Pani (8) aES
1=1
(8))
+ +1+R) R)
( V
Vi) + Po
T
1(( ax) 2) 1² (st, mi(sraa)
(
2 <111 + R)
(1+
1
Σ
bb (8t, ar)
1/
a)())a)))
Payay (V* - Vasleraa)) + 3/1
t= t=
1=1
42

---

Published as a conference paper at ICLR 2025
(8)
(1+ R
(p, V Vi) + 8o
a() E IJ pT at)
(n(()a))) Σ
? 1
Σ
Th Vallera))
Pan,a (V* - Vi) + v/
ub (s), a1)
(=mmie()
Ami (8)
+ +11 + R
V Vi) +00
t=1
(1
(s), E IJ p= (st, (t)
1bb (x) Price (V* - -V,) + +/o
A=
(8)
+
+1+
(p, V Vi)) +
1=1
Imx
=7
1+
Σ
Σ
p= (s,a) Peo (V* -V) + to + Φo + (1 R)
(p, V Vi) + 00
sES.REA
=7
|+ +
3
Σ (pPa
V*-
- Vi) + 100 + 60 + (1+
(8)
(0, V Vo) + 00
(1 +) 3 (pPr., V Vo) + (1+ R)
(6)
0n v/ Φ0 +7 7
(0. V Vi) 0o:
where we remind the reader of our notation p²¹ in equation
119
Here, (a) is valid (i.e.,
p(8,, (b)/ a) is well defined for & 2 (m)) due to Lemma 18 (b) holds by grouping the
terms in the previous line; and (c) utilizes Lemma and the property that V 2 V, (cf. Lemma 17). Therefore, we arrive at
00
1 Vi) + S + 0o
t=1
(mi
(p V Vi) + on + vo + do + (1+ (ppr. V - -Vo) + 0o
< (1 +
1 + Eu + Og
+ vhu + do:
where we have used the definition of Eo. Repeat the same argument to reach
aj S ajt1 + E, + + 3 + +Ø
for all j 2 1. This in turn allows us to conclude that
oo S li
+
0
1/
(134)
1=0
We will then bound the terms a, E, t and separately in the subsequent steps. Our proofs are similar to the ones in (aan et al., 2022), hence we omit the repeated part.
Bounding a. The bound is similar to Yan et al. 2022 is first observed that
a lim sup j+000
{
? 11
1 37
Σ
L. V1)
T
lim sup k
{ 7 (1+
1 37 T)
/ -0.
Bounding Ç.
43

---

Published as a conference paper at ICLR 2025
By utilizing
131
it holds that
(5)
0
7 1 + F) 1
1++
37
(pp V+ (oP...--vi
{ Σ
1+
T (p(Pr.))t,, v -
1
37
_-', -V6)
(6)
mix (0) +
(dp: V Vi) + ST (1 - 7)
1-7
t=0
mix
mix
1
log
log
T (1 7)
0"
Bounding 0. Following
Yan et al.
2022..
we have that Note that
373
T
Σ
[p(Px.)]] (8) min (milesr(())) I-75 (
==
1=1 AES
S"Stimie y1
CTST22 V (1-7)
Bounding vh. Note that
me(s.a)
マー Σ 7
1+ 1
Σ
Σ
(Pr' y (s:a)
Σ
n Pa.a (V* - Vai(aa))
(sss,))
(6)))16)
LeES,nEA
I ++ [p (pa yd] (se, ar)
Re(
me(serae)) Pesiae (V* Vizlonaa))
Pb ($t, at) at)
nels,a)
a(s,a)
malo,a) Pa. Peo (V* Vir(s,a))
(6)ma()) LsES,nEA
me((erae)
- -1+ 1
d (s),aa)
m((()))))))) Paioe (V* - Velcnasal)
Mb (8t,
Here,
d a(s,o)= Σ (1+ (or (pot))) ())
Σ
for any (s, 8 A. Note that this equation exactly matches with Step 2.4 in Yan al. 2022). hence the remaining proof similarly follows, and is omitted here. Specifically, we have that
O'ixit log²
T
C* Stmix
T 8
1b x
log
(1 71-
(1
Bounding o. Similar Yan et al. 2022 we can employ an analogous argument to show that á can be bounded as
2 C Imix
T
C S1 log
(7)
T
(1 73 log²
8
(1 (1-7)²
Now, plugging the bounds 0. s and further implies that
ag S a + E + 0 + 2 + o
C*ST
(T' C* St O'tmiic log²
(8)
(1 (1-7)3
(1 11-1) 7
(1 7)3
44

---

Published as a conference paper at ICLR 2025
We then invoke equation 133 to conclude that
S2
+ C* Slmil
C* lmix
V (p) - v (p) T
S
+
T(1 7))
[ 7)²
T 7) 3
This hence completes the proof.
45


Reviews:
[{"review_id": "SmvG8l2sno", "reviewer": "Reviewer_AZ4j", "summary": "This work enhances offline RL by developing a scalable, robust model-free algorithm that optimizes worst-case performance within an uncertainty set. Using a double-pessimism principle to handle data uncertainty and model mismatch, the method adapts across settings without model estimation. Through theoretical analysis the author demonstrates the algorithm’s near-optimal data efficiency, advancing robustness and scalability in offline RL.", "questions": "1. As mentioned above, have the authors evaluated how the proposed appraoch performs in any of the D4RL environments, which are widely used in offline RL research?\n2. Are there any strategies for fine-tuning parameters for specific tasks?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. The paper introduces a \"double-pessimism principle\" that uniquely addresses both model mismatch and limited dataset coverage within a model-free framework\n2. The authors provide a rigorous theoretical foundation, including sample complexity analysis and convergence guarantees, which enhances the paper's quality", "weaknesses": "1. The paper lacks sufficient experiments to demonstrate the effectiveness of the proposed method. For instance, there is no comparison with model-based baselines, and the evaluation environment is relatively simple.\n\n2. There are no ablation experiments analyzing the functionality of the proposed \"double-pessimism principle.\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "SkhVFJEZIP", "reviewer": "Reviewer_V4q8", "summary": "In this paper, the authors proposed a novel double-pessimism principle framework for offline reinforcement learning, which conservatively estimates the performance of offline policy learning and accounts for both the pessimism caused by limited data and potential model mismatch. Compared with previous methods that usually leverage model-based approaches, the authors proposed a model free algorithm to learn the optimal policy that is robust to potential environment mismatches, which enhances robustness in a scalable manner. The authors also provide sample complexity analysis of the algorithm and extensive experiments to further demonstrate that the approach is robust and scalable.", "questions": "- In some environments such as mujoco, how can we identify what kind of uncertainty set we should use here, and how can we estimate the uncertainty set hyperparameters to ensure the policy we learn is under the real settings?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- The authors present a scalable and robust model-free algorithm to quantify both the uncertainty of model mismatch and limited dataset; the way of constructing the model mismatch pessimistic allows the authors to derive a model-free algorithms;\n- The authors present the sample complexity result for both finite horizon case and infinite discounted case. \n- The authors demonstrate that with the double pessimism principle, empirically we can learn better policies compared with single pessimistic based algorithms.", "weaknesses": "-My central question about the paper is that in practise how we can justify the uncertainty set in real case, and how we can estimate the parameters of the uncertainty set instead of directly assigning some upper hyperparameter.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "ciXrawJdob", "reviewer": "Reviewer_cMFi", "summary": "This paper presents a model-free offline RL algorithm using a \"double-pessimism principle\" to enhance robustness against model mismatches and scalability, effectively handling uncertainties from limited data and environment shifts.", "questions": "n/a", "limitations": "", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "1. The paper is well-structured.  \n2. The double-pessimism principle effectively tackles uncertainties from both data limitations and environment mismatch, adding a valuable perspective to offline RL.  \n3. By avoiding transition model estimation, the algorithm shows strong scalability potential for complex environments.  \n4. The paper provides a detailed sample complexity analysis and shows performance improvements on benchmark tasks, supporting the method's effectiveness.", "weaknesses": "1. While the paper shows strong results, additional tests on more diverse, high-dimensional environments could provide a clearer picture of scalability, such as d4rl.\n2. Comparing other offline RL algorithms, such as CQL, IQL, etc., will further enhance the contribution of this work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "HLMAM3M5uY", "reviewer": "Reviewer_w3Hx", "summary": "The paper presents a new approach for offline reinforcement learning that emphasizes both robustness to model mismatch and limited dataset. The paper provides theoretical results regarding robust value estimation, sub-optimality gap, and sample efficiency. The empirical results also support the superiority of the proposed double-pessimism approach, compared to the single-pessimism approach.", "questions": "- In Figure 2, can the authors provide the standard deviations or confidence intervals for the y-axis of each method? The envelopes in Figure 1 were informative, but Figure 2 does not provide such.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The paper proposed the first offline model-free algorithm with a robustness guarantee.\n- The empirical results on toy environments show the proposed double-pessimism approach outperforms the single-pessimism baseline.", "weaknesses": "- The proposed method has a higher sample complexity than the baseline (Shi & Chi, 2022) regarding gamma.\n- Adding another pessimistic term might lead to overly conservative policies, especially when the model mismatch problem is not significant.\n- The source code is not provided, making it difficult to assess the reproducibility of the results.\n- It would be more practical if the authors could provide a real-world example where model mismatch is likely to occur and construct the uncertainty set based on that scenario. While the mismatch modeled by the \\ell_\\alpha norm is suitable for theoretical guarantees, it is unclear if real-world perturbations would follow this type.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "J373fFpUKg", "reviewer": "Reviewer_sEko", "summary": "The paper presents a novel approach to offline reinforcement learning (RL) by introducing a double-pessimism principle. This principle aims to enhance robustness and scalability by conservatively estimating performance, accounting for both limited data and potential model mismatches. The authors propose a model-free algorithm that is robust to environment mismatches and provide a rigorous sample complexity analysis for a specific case of mismatch modeling using the $l_\\alpha$-norm. The paper also includes some experiments demonstrating the approach's effectiveness.", "questions": "- Can you provide more details on the algorithm's implementation efficiency, particularly regarding the $\\kappa$ calculation? What is its computational complexity?\n- Does the current definition of perturbations ensure that their impacts are not cascading—meaning they don't affect future steps?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The introduction of the double-pessimism principle is a significant contribution to offline RL. By addressing both data limitations and model mismatches, the approach provides a more comprehensive framework for robust policy learning.\n- The paper offers a detailed sample complexity analysis for the $l_\\alpha$-norm model, which theoretically demonstrates the efficiency of the proposed method. This analysis is crucial for understanding the algorithm's performance and provides a solid foundation for its claims.\n- Some experiments conducted in both simulated and real environments showcase the practical applicability and robustness of the proposed algorithm. The results indicate that the double-pessimism approach outperforms existing methods in handling model uncertainty.", "weaknesses": "- The paper's focus on perturbations over transition probabilities is a limitation. In real-world applications, perturbations can occur in various forms, not just in transition probabilities. This narrow focus may hinder the practical applicability of the approach in more complex environments where other types of perturbations are present.\n- While the sample complexity analysis is rigorous, it is limited to the $l_\\alpha$-norm model. This restricts the generalizability of the theoretical findings to other types of perturbations or uncertainty models. A broader analysis covering more general cases would strengthen the paper's contributions.\n- For general perturbations, the approach may require solving large optimization problems for each update. This could significantly affect learning efficiency, especially in large-scale or real-time applications. The paper would benefit from a discussion on how to mitigate these computational challenges.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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:

Decision: Accept (Poster)