Double Pessimism is Provably Efficient for Distributionally Robust Offline Reinforcement Learning: Generic Algorithm and Robust Partial Coverage
Authors: Jose Blanchet
Miao Lu
Tong Zhang
Han Zhong
Venue: NeurIPS 2023 poster (2023)
Keywords: distributionally robust offline reinforcement learning
double pessimism
general function approximation

Abstract: We study distributionally robust offline reinforcement learning (RL), which seeks to find an optimal robust policy purely from an offline dataset that can perform well in perturbed environments. We propose a generic algorithm framework Doubly Pessimistic Model-based Policy Optimization ($\texttt{P}^2\texttt{MPO}$) for robust offline RL, which features a novel combination of a flexible model estimation subroutine and a doubly pessimistic policy optimization step. Here the double pessimism principle is crucial to overcome the distribution shift incurred by i) the mismatch between behavior policy and the family of target policies; and ii) the perturbation of the nominal model. Under certain accuracy assumptions on the model estimation subroutine, we show that $\texttt{P}^2\texttt{MPO}$ is provably sample-efficient with robust partial coverage data, which means that the offline dataset has good coverage of the distributions induced by the optimal robust policy and perturbed models around the nominal model. By tailoring specific model estimation subroutines for concrete examples including tabular Robust Markov Decision Process (RMDP), factored RMDP, and RMDP with kernel and neural function approximations, we show that $\texttt{P}^2\texttt{MPO}$ enjoys a $\tilde{\mathcal{O}}(n^{-1/2})$ convergence rate, where $n$ is the number of trajectories in the offline dataset. Notably, these models, except for the tabular case, are first identified and proven tractable by this paper. To the best of our knowledge, we first propose a general learning principle --- double pessimism --- for robust offline RL and show that it is provably efficient in the context of general function approximations.

Double Pessimism is Provably Efficient for Distributionally Robust Offline Reinforcement Learn- ing: Generic Algorithm and Robust Partial Coverage
Jose Blanchet
Miao Lu
Tong Zhang?* Han Zhong
Department of Management Science and Engineering, Stanford University
Department of Mathematics, The Hong Kong University of Science and Technology 3 Center for Data Science, Peking University
Abstract
We study distributionally robust offline reinforcement learning (RL), which seeks to find an optimal robust policy purely from an offline dataset that can perform well in perturbed environments. We propose a generic algorithm framework Doubly Pessimistic Model-basee Policy Optimization (P²MPO) for robust offline RL, which features novel combination of flexible model estimation subroutine and doubly pessimistic policy optimization step. Here the double pessimism principle is crucial overcome the distribution shift incurred by i) the mismatch between behavior policy and the family of target policies; and ii) the perturbation of the nominal model. Under certain accuracy assumptions the model estimation subroutine, we show that P2MPO is provably sample-efficient with robust partial coverage data, which means that the offline dataset has good coverage of the distributions induced by the optimal robust policy and perturbed models around the nominal model. By tailoring specific model estimation subroutines for concrete examples including tabular Robust Markov Decision Process (RMDP), factored RMDP, and RMDP with kernel and neural function approximations, we show that рºмPO enjoys a On -1/2) convergence rate, where n is the number of trajectories in the offline dataset. Notably, these models, except for the tabular case, are first identified and proven tractable by this paper. To the best of our knowledge, we first propose a general learning principle double pessimism for robust offline RL and show that is provably efficient in the context of general function approximations.
1 Introduction
Reinforcement learning (RL) [52] aims to learn an optimal policy that maximizes the cumulative rewards received in unknown environment. Typically, deep RL algorithms learn policy in online trial-and-error fashion using millions to billions of data. However, data collection could be costly and risky in some practical applications such healthcare [56] and autonomous driving [38]. To tackle this challenge, offline RL (also known as batch RL) [21, 22] learns near-optimal policy based on a dataset collected a priori without further interactions with the environment. Although there has been great progress in offline RL [72, 20, 16, 54, 62, 6], these works implicitly require that the offline dataset generated by the real-world environment, which may fail in practice. Taking robotics [18, 37] as an example, the experimenter trains agents in a simulated physical environment environments. Since the experimenter does not have access the true physical environment, there is mismatch between the simulated environment used to generate the offline dataset and the real-world environment used to deploy the agents. Such a mismatch
and then deploy them in
Alphabetical order. Email miaolu@etanford.cm
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

commonly referred to as the sim-to-real gap [42, 76]. Since the optimal policy is sensitive to the model [31, 9]. the potential sim-to-real gap may lead the poor performance of RL algorithms.
A promising solution to remedy this issue is robust RI. [13, 9, 32] - training a robust policy that performs well in bad or even adversarial environment. A line of work on deep robust RI. [43, 44, 41, 30, 53, 75, 19] demonstrates the superiority of the trained robust policy in real world environments. Furthermore, the recent work of Hu et al. [11] theoretically proves that the ideal robust policy can attain near optimality in dealing with problems with sim-to-real gap, but this work does not suggest how to learn robust policy from a theoretical perspective. In order to understand robust RL from the theoretical side, robust Markov decision process (RMDP) [13, 9] has been proposed, and many recent works [77. 47, 29] design sample-efficient learning algorithms for robust offline RL. These works mainly focus on the tabular case, which is not capable of tackling large state spaces. Meanwhile, in the non-robust setting, a line of works [16, 54, 62, 73, 45] show that "pessimism" is the general learning principle for designing algorithms that can overcome the distributional shift problem faced by offine RL. In particular, in the context of function approximation, Xie et al. [62] and Uehara and Sun [54] leverage the pessimism principle and propose generic algorithms in the model-free and model-based fashion, respectively. Hence, is natural to ask the following questions:
Q1: What is the general learning principle for robust offline RL?
Q2: Based on this learning principle, can we design a generic algorithm for robust offline RL in the context of function approximation?
To answer these two questions, we need to tackle the following two intertwined challenges: (i) distributional shift, that is, the mismatch between offline data distribution and the distribution induced by the optimal robust policy. In robust offline RL, the distributional shift has two sources - behavior policy and perturbed model, where the latter is the unique challenge not presented in non-robust RL; and (ii) function approximation. Existing works mainly focus on the tabular case, and it remains elusive how to add reasonable structure conditions to make RMDPs with large state spaces tractable. Despite these challenges, we answer the aforementioned two questions affirmatively.
Contributions. We study robust offline RL in general framework, which not only includes existing known tractable S x A-rectangular tabular RMDPs, but also subsumes several newly proposed models (e.g., S A-rectangular factored RMDPs, S A-rectangular kernel RMDPs, and S A- rectangular neural RMDPs) as special cases. Under this general framework, we propose a generic model-based algorithm, dubbed as Doubly Pessimistic Model-based Policy Optimization (P²MPO), which consists of a model estimation subroutine and a policy optimization step based on doubly pessimistic value estimators. We note that the model estimation subroutine can be flexibly chosen according to structural conditions of specific RMDP examples. Meanwhile, the adoption of doubly pessimistic value estimators in the face of model estimation uncertainty and environment uncertainty plays a key role in overcoming the distributional shift problem in robust offline RL.
From the theoretical perspective, we characterize the optimality of P'MPO with partial coverage. In particular, we show that the suboptimality gap of PDMPO is upper bounded by the model estimation error (see Condition 3.2) and the robust partial coverage coefficient (see Assumption 3.3). For concrete examples of RMDPs, by customizing specific model estimation mechanisms and plugging them into P2MPO, we show that PºMPO enjoys a 112 convergence rate with robust partial coverage data, where n is the number of trajectories in the offline dataset. In summary, we identify a general learning principle- - double pessimism - for robust offline RL. Based on this principle, we can perform sample-efficient robust offline RL with robust partial coverage data via general function approximation. See Table for a summary of our results and comparison with mostly related works.
1.1 Related Works
Robust reinforcement learning in robust Markov decision processes. Robust RL is usually
modeled as robust MDP (RMDP) [13, 9], and its planning has been well studied [13, 9, 65, 60, 57]. Recently, robust RL in RMDPss has attracted considerable attention, and growing body of works studies this problem in the generative model [68, 39, 49, 58, 69, 66, 71. online setting [59, 3, 8).
and offline setting [77, 40, 47, 29]. Our work focuses on robust offline RL, and we provide a more in-depth comparison with Zhou et al. [77], Shi and Chi [47], Ma et al. [29] as follows. Under the full coverage condition (a uniformly lower bounded data distribution), Zhou et al. [77] provide the first sample-efficient algorithm for S x A-rectangular tabular RMDPs. After, Shi and Chi [47]

---

Table 1: A comparison with closely related works robust offline RL. means the work can tackle
this model with robust partial coverage data, v! means the work requires full coverage data to solve the model, and X means the work cannot tackle the model. Lightblue color denotes the models that
are first proposed and proved tractable in this work.
Zhou al. [77]
Shi and Chi [47]
Ma al. [29]
This Work
x A-rectangular tabular RMDP
d rectangular linear RMDP
X
x
S A-rectangular factored RMDP
x
$ x A-rectangular kernel RMDP
X
$ x A-rectangular neural RMDP
X
X
X
leverage the pessimism principle and design sample-efficient offline algorithm that only requires robust partial coverage data for x A-rectangular tabular RMDPs. Ma et al. [29] propose new d-rectangular RMDP and develop a pessimistic style algorithm that can find near-optimal robust policy with partial coverage data. In comparison, we provide a generic algorithm that can not only solve the models in Zhou et al. [77], Shi and Chi [47], Ma et al. [29]. but also tackle various newly proposed RMDP models such as S x A-rectangular factored RMDP, S x A-rectangular kernel RMDP, and S A-rectangular neural RMDP. See Table 1 for a summary. Moreover, propose new pessimistic type learning principle "double pessimism" for robust offline RL. Although Shi et al. [48] and Ma et al. [29] adopt the similar algorithmic idea in tabular linear settings, neither of them have identified a general learning principle for robust offline RL in the regime of large state space.
Non-robust offline RL and pessimism principle. The line of works on offline RL aims to design efficient learning algorithms that find an optimal policy given an offline dataset collected a priori. Prior works [33, 2, 5] typically require a dataset of full coverage, which assumes that the offline data have good coverage of all state-action pairs. In order to avoid such a strong coverage condition on data, the pessimism principle- being conservative in policy value estimation of those state-action pairs that are not sufficiently covered by data has been proposed. Based on this principle, a long line of works [see e.g., 16, 54, 62, 63, 45, 73, 71, 64, 48, 24, 26, 74, 28, 46] propose algorithms that can learn the optimal policy only with the partial coverage data. The partial coverage data only requires to cover the state-actie aatennction pairs visited by the optimal policy. Among these works, work is mostly related to the work of Uehara and Sun [54], which proposes a generic model-based algorithm for non-robust offline RL. Our algorithm for robust offline RL is also in a model-based fashion, and our study covers some models such as S x A-rectangular kernel and neural RMDPs whose non-robust counterparts are not studied by Uchara and Sun [54]. More importantly, our algorithm is based on newly proposed double pessimism principle, which is tailored for robust offline RL and is in parallel with the pessimism principle used in non-robust offline RL. Also, we show that the performance of our proposed algorithm depends on the notion of robust partial coverage coefficient, which is also different from the notions of partial coverage coefficient in previous non-robust offline RL works [16, 62, 54].
1.2 Notations
For any set A, we use 2 to denote the collection of all the subsets of A. For any measurable space X. we use ( denote the collection of probability measures over X. For any integer n. we use [n] to denote the set ... (m). Throughout the paper, we use D(-Ii-) to denote (pseudo-)distamm) between two probability measures (or densities). In specific, we define the KL-divergence (pll()llg)
between two probability densities and q over X' as
(Kl(p) f p(x) log
p(x) ((x)
dx.
and we define the TV-distance Drv(pplgg) between two probability densities p and g over X' as
Dry()lla) = x 1g(z)= p(x) dz.
Given function class FF equipped with some norm ||,,,,, denote by N, the e-bracket number of F. and N/e,, F,ll [|=) the e-covering number of F.
3

---

2 Preliminaries
2.1 A Unified Framework of Robust Markov Decision Processes
We introduce a unified framework for studying episodic robust Markov decision processes (RMDP). which we denote as a tuple (S, A, H, p* R. PM, 2). The set S is the state space with possibly infinite cardinality, A is the action space with finite cardinality. The integer H is the length of each episode. The set P* = {P; Th is the collection of transition kernels where each P/: S A H A(S), and R = [ H h=1 is the collection of reward functions where each R2 : S A [0, 1]. We use ((8) to note the probability simplex on S (i.e. the space of probability measures with support on S).
We consider mhodel-based perspective of reinforcement learning, and we denote P -P(
S x A + (SS) as the space of all transition kernels. The space PM C PP of the RMDP is a realizable model space which contains the transition kernel P i.e., PA E Pas for any step h [H]. Finally, the RMDP is equipped with mapping + PM + 2 that characterizes the robust set of any transition kernel in PM. Formally, for any transition kernel P E PM. we call & (P) the robust set of P. One can interpret the transition kernel P% E PM as the transition kernel of the training environment, while $ (P;) contains all the possible transition kernels of the test environment.
Remark 2.1. The mapping & is defined on the realizable model spuce PM, while for generality we allow the image of & to be outside of PM. That is, a P E PPP) for some P E PM might be in Psr Policy and robust value function. Given an RMDP (S, A, H. P R, PM: b), consider using with Th A + (SS) for each step [M]. For simplicity, we use policy to refer to a Markovian policy.
a Markovian policy to make decision. A Markovian policy т is defined as π = {Th /
Given any policy म. we define the robust value function of x with respect to any set of transition kernels P = 1H S PM the following, for each step h [H)
Vi,,P,o()) (s) = inf (s: (Pr) Y (.EO(P))SSKC inf (8. a) (.E
(2.1)
( a; (PA) ((s,0)
(2.2)
Here (z ( and QN (A are the state-value function and the action-value funciitioo [52] of policy ı in the standard episodic MDP (S, A, H, 1 R).
(x (PA) = (PW
Σ
R2 0z)
8h = AsES
(2.3)
H
Qh(s, a; (Pr) = E (P.) M
Re a:)
8h = 8, 0.0h
v(s.a) S (2.4)
h
where the expectation E. ((P.)__ [ is taken with respect to the trajectories induced by the transition
kernel ( Pr, Pr 1= and the policy æ. Intuitively, the robust value function of policy æ given transition kernel P is defined as the least expected cumulative reward achieved by when the transition kernel varies in the robust set of P. This is how an RMDP takes the perturbed models into consideration.
S x A-rectangular robust set and robust Bellman equation. Ideally, we would like to consider robust value function that has recursive expressions, just like the Bellman equation satisfied by (2.3) in a standard MDP [52]. To this end, we focus on a generally adopted kind of robust set in our unified framework, which is called the S x A-rectangular robust set [13].
Assumption 2.2 (S x A-rectangular robust set). We assume that the mapping &b induces S x A- rectangular robust sets. Specifically, the mapping & satisfies, for VP E PM.
Pp(s, az P), Polo, az P) (P() D(P()))(PPPPP =))
(P))
(s.))ESAA
for some (pseudo-) distance D(-1I-) on A(S) and some p E [R.. Intuitively, S x A-rectangula requires that (P) gives decoupled robust sets for P(-|s, a) across different (s, a) a)piiis. The (pseudo-
ipseudo-jdistance Jdistance (--ll-) can be chosen as a o-divergence [68, 10] or a p- www--estein--issteaeeeee [35].

---

Thanks to the S x A-rectangular assumption on the mapping L the robust value functions (2.1) of any policy π then satisfy a recursive expression, which is called robust Bellman equation [13, 36).
Proposition 2.3 (Robust Bellman equation). Under Assumption 2.2, for any P= {Pr) h= where Pa E PM and any Mi with Th S + A(A), the following robust Bellman equation holds,
(s) B- (s,,a) S (s. Rn(s,a)+ + inf E 1erpFa((e (.EO(P))
(2.5)
((s,a)
(2.6)
To be self-contained, in Appendix B we provide a detailed proof of the robust Bellman equation in our framework under Assumption 2.2. Equation (2.5) actually says that the infimum over all the transition kernels (recall the definition of V. in (2.1)) can be decomposed into a "one-step" infimum over the current transition kernel, i.e., inf (PE)()))) and an infimum over the future transition kernels, i.e. Such a property is crucial to the algorithmic design and theoretical analysis for RMDPs.
2.2 Examples of Robust Markov Decision Processes
In this section, we give concrete examples for the general RMDP framework proposed in Section 2.1. Most existing works on RMDPs hinge on the finiteness assumption the state space, which fails to deal with prohibitively large or even infinite state space. In our framework, RMDPs can be considered in the paradigm of infinite state space, for which we adopt various powerful function approximation tools including kernel and neural functions. Also, we introduce a new type of RMDP named robust factored MDP, which is robust extension of standard factored MDPs [17].
Remark 2.4. Besides S x A-rectangular-typ robust sets (Assumption 2.2), our unified framework of RMDP can also cover other types of robust sets considered in some previous works as special cases, including S-rectangular robust set [61] and d-rectangular robust set for linear MDPs [29]. See Section A for a discussion about these two types of robust sets.
In the sequel, we introduce concrete examples of our framework of RMDP.
Example 2.5 (8 x A-rectangular robust tabular MDP). When the state space is a finite set, we call the corresponding model an S x A-rectangular robust tabular MDP. Recently, there is a line of works on the S A-rectangulat robust tabular MDP [77, 68, 39, 27, 47, 40, 10, 35, 58. 69, 66, 7]. For S x A-rectangular robust tabular MDPs, we choose PM = P containing all possible transitions.
Remark 2.6. We point out that our framework of RMDP under S x A-rectangular assumption covers substantially more model than S A-rectangular robust labular MDP since our state space S can be infinite. The model space PM can be adapted to function approximation methods to handle the infinite state space. Thus any efficient algorithm developed for our framework of RMDPs can not be covered by algorithms for S x A-rectangular robust tabular MDPs. Example 2.7 and 2.8 are infinite state space x A-rectangular robust MDPs with function approximations.
Example 2.7 (S x A-rectangulaa robust MDP with kernel function approximations). We consider an infinite state space S x A-rectangular robust MDP whose realizable model space PM is in reproduced kernel Hilbert space (RKHS). Let H be a RKHS associated with a positive definite kernel : x x S) x (S x A x 8) + R. (See Appendix D.3.1 1 for review of the basics of RKHS). We denote the feature mapping of H by sb SS x A S サ H. With H. an S A-rectangular robust MDP with kernel function approximation is defined as an S x A-rectangular robust MDP with
PM {P(s' s, a) = (1bs,, a, 5'), fYH :: f E H. lIfllH S Bk).
(2.7)
for some Bx > O. Here we implicitly identify P(. .) as the density of the corresponding distribution with respect to a proper base measure on S x A x S.
Example 2.8 (S x A-rectangular robust MDP with neural function approximations). We consider an infinite state space Sx x A-rectangular robust MDP whose realizable model space Pss is parameterized by an overparameterized neural network. We first define a two-layer fully-connected neural network on some X C Rdx as
NN(x; W.
1
Σ 1=1
m
(x Twy), VXEX.
(2.8)
Vm
5

---

where m E N4 is the number of hidden units of NN, (W, a) is the parameters given by W (W1.'.,; Wm) E Raxm, a a= =- [a1, (0m) 0mm) E RRm, and (-)) is the activation function. Now we assume that the state space S _ I for some ds E N+. Also, we identify actions via one-hot vectors in BlAi, i.e, we represent a E A by (0,... ......0.,, 0.1,0.... 0,........ ,0) with in the a-th coordinate. Let X' = Ax S with dx- 2dg + |Al. Then an S x A-rectangular robust MDP with neural function approximation is defined as an S x A-rectangular robust MDP with Py given by
PM - (P) NN((s, a, 8'); W. a²) |W - -W S Bx},
(2.9)
for some BN > O and some fixed (W", a²) which can be interpreted as the initialization. We refer to Appendix 1.4.1 for more details about neural function approximations and analysis techniques.
Example 2.9 (S x A-rectangular robust factored MDP). We consider a factored MDP equipped with S x A-rectangular factored robust set. A standard factored MDP [17] is defined as follows. Let d be an integer and O be finite set. The state space S is factored as S = O², For each E [d], s[i] is the i-coordinate of s and it is only influenced by s s(pa,), where pa; S [d] That is, the transition of factored MDP can be factorized as
P7 a)
II Ph, (o][i]](ppa
Here we let the realizable model space PM consist of all the factored transition kernels, i.e.,
P. ::paa x AO)) [d] PM= P(sl|s, = II P. P.(''
i=1
For an S x A- A-rectangular robust factored MDP, we define Tb as, for any transition kernel P()'(s,a)
Ih P[('|i]]s(pa)) E PM. (PP) = = Prac,pls, 0; P), with
[ PP:::: ::::PPP)) E E D(PLO)I)(((( a)) S pr Vi E [d]
P a; P)
for some (pseudo-kdistanee D on (OO) and some positive real numbers (p:)
2.3 Offline Reinforcement Learning in Robust Markov Decision Processes
In this section, we define the offline RL protocol in a RMDP (S, P* R, PM, $). The learner given the realizable model space PM and the robust mapping + but the learner doesn't 't know the transition kernel p*. For simplicity, we assume that the learner knows the reward function It.
Offline dataset generation. We assume that the learner is given an offline dataset ID that consists of n i.i.d. trajectories generated from the standard MDP (S,A, H, P* .R) using some behavior policy b. For each 7 E [n]. the trajectory has the form of ((), oi rf) H T RA (sT, a, and 4 (-1s%, at) for each step h [H]
/h=1- satisfying that of ~ (-18))
Given transition kernels P (Pr and policy n, we use (-.) to denote the state- visitation distribution at step h when following policy and transition kernel P. With this notation,
the distribution of (s), af, can be written as di=',, or simply d'>,,,- , for each e [n] and E [H].
We also use di- (--=,,()) to denote the marginal distribution of state step h when there is no confusion.
Learning objective. In offline robust RL., the goal is to learn the policy x' from the offline dataset ID) which maximizes the robust value function Vi*.P-.. that is,
n argsup VT.P. (81), 81 E,
(2.10)
TEll
where II = (- ) Th S + (AA) denotes the collection of all Markovian policies. In view of (2.10). we call nt the optimal robust policy. Equivalently, we want to learn a policy क e II which minimizes the suboptimality gap between के and n²,, defined as
SubOpt s1) == VT.p- * (51) Vē.r- f0rr=,.66 (s1), Vs
(2.11)
This reasonable since learning the reward function easier than learning the transition kernel. 'Wttoout loss of generality, we assume that the initial state is fixed to some $1 E S. Our algorithm and theory be directly extended the case when p ASS).

---

Algorithm 1 Doubly Pessimistic Model-based Policy Optimization (P²MPO)
1: Input: model space PM. mapping 4, dataset D. policy class II, algorithm ModelEst.
2: Model estimation step:
3: Obtain confidence region P ModelEst PM))
4: Doubly pessimistic policy optimization step:
5: Set policy as are Jpess" (TT) where Jpeas? (TT) is defined in (3.1).
6: Output: रे = (Th [
3 Algorithm: Generic Framework and Unified Theory
In this section, we propose Doubly Pessimistic Model-based Policy Optimization (P²MPO) algorithm to solve offline RL in the RMDP framework we introduce in Section 2.1, and establish a unified theoretical guarantee for P2MPO. Our proposed algorithm and theory show that double pessimism is a general principle for designing efficient algorithms for offline robust RL. The algorithm features three key points: i) learning the optimal robust policy π approximately; ii) requiring only a partial coverage property of the offline dataset DD; iii) able handle infinite state space via function approximations.
We first introduce our proposed algorithm framework PºMPO in Section 3.1. Then we establish a unified analysis for P'MPO in Section 3.2. Our algorithm framework be specified to solve all the concrete examples of RMDP we introduce in Section 2.2, which we show in Section 4.
3.1 Algorithm Framework: PºMPO
The P²MPO algorithm framework (Algorithm 1) consists of a model estimation step and a doubly pessimistic policy optimization step, which we introduce in the following respectively.
Model estimation step (Line 3). The POMPO algorithm framework first constructs an estimation
of the transition kernels P* {Pr 1 i.e., it estimates the dynamic of the training environment.
implements a sub-algorithm ModelEst(ID, PM) that returns a confidence region P for P* = {PX) Specifically, p = (/ with P/, S Ps for each step h E [H].
The sub-algorithm ModelEst can be tailored specific RMDPs. We refer to Section 4 for detailed implementations of ModelEst for different examples of RMDPs introduced in Section 2.2. Ideally, to ensure sample-efficient learning, we need P ModelEst (ID, PM) to satisfy: i) the transition kernels == = (P% 1+11/ h= are contained in P {PA) ii) each transition kernel Ph E P,, enjoys small "robust estimation error" which is highly related to the robust Bellman equation in (2.5). We quantify these two conditions of P for sample-efficient learning in Section 3.2.
Doubly pessimistic policy optimization step (Line 5). After model estimation step. РºMPP performs policy optimization to find the optimal robust policy. To learn the optimal robust policy in the face of uncertainty, P2MPO adopts a double pessimism principle. To explain, this general principle has two sources of pessimism: i) pessimism in the face of data uncertainty; ii) pessimism to find a robust policy. Specifically, for any policy, first estimate its robust value function via two infimums, where one is an infimum over the confidence set constructed in the model estimation step, and one is an infimum over the robust sets. Formally, for any II, define the doubly pessimistic estimator
inf Jrasa (T) P.EPR.ISACH (P.)))
inf
VT (P.
(3.1)
where Vi" is the standard value function of policy π defined in (2.3). Then P2MPO outputs the policy म that maximizes the doubly pessimistic estimator Jrana? (T) defined in (3.1), i.e.,
= argsup Jreas? (TT)
(3.2)
*ell
The novelty of the doubly pessimistic policy optimization step is performing pessimism from the two sources (data uncertainty and robust optimization) simultaneously. Compared with the previous works on standard offline RL MDPs [62. 54] and offline RL in RMDPs without pessimism [68, 77, 40], they only contain one source of pessimism in algorithm design, contrasting with algorithm.
We note that recent work [47] also studied robust offline RL in A-rectangular robust tabular MDPs (Example 2.5) using pessimism techniques. Compared with our double pessimism principle,
7

---

their algorithm performs pessimism in face of data uncertainty i) depending on the tabular structure of the model since a point-wise pessimism penalty needed and ii) depending on the specific form of the robust set (P), which makes it difficult to adapt to the infinite state space case with general function approximations and general types of robust set Φ (P).
3.2 Unified Theoretical Analysis
In this section, we establish a unified theoretical analysis for the P²MPO algorithm framework proposed in Section 3.1. We first specify the two conditions that the model estimation step of PDMPO should satisfy in order for sample-efficient learning. Then we establish an upper bound of suboptimality of the policy obtained by PPMPO given that these two conditions are satisfied. In Section 4, we show that the specific implementations of the sub-algorithm ModelEstt for the RMDPs examples in Section 2.2 satisfy these conditions, which results in tailored suhoptimality bounds for these examples.
Conditions. The two conditions on the model estimation step are given by the following.
Condition 3.1 (d-accuracy). With probability least 1 6, it holds that PX E Pa, for any [H]. Condition 3.2 (ō-model estimation error). With probability least 1 6, it holds that
E (s.)))dph pr
(
inf (PP)(PP))
inf (AE
P
I Eir th (n. 6).
for any P {Pr with PA E Pr. Here (V = E., A.AAA V p,
Condition 3.1 requires that the confidence region PA. contains the transition kernel of the training environment PA with high probability. Condition 3.2 requires that each transition kernel PA. Pr. induces an error from P7 less than certain quantity ErT, (n, 8). where the error is adapted from the robust Bellman equation (2.5) and involves an infimum over the robust set of Ph and Px In specific implementations of ModelEst for RMDP examples in Section we show that the quantity ErT, (n, 6) generally scales with On -)), where n is the number of trajectories in the offline dataset.
Suboptimality analysis. Now we establish unified suboptimality bound for the P'MPO algorithm framework. Thanks the double pessimism principle of P'MPO, we can prove a suboptimality bound while only making a mild robust partial coverage assumption on the dataset. Assumption 3.3 (Robust partial coverage). We assume that
(Fuls,a) ap dp.
27
Cjr, x = sup
sup
E
(o.a))aph
< +o0,
ISNSH P= PE
and we call C7-, the robust partial coverage coefficient.
To interpret, Assumption 3.3 only requires that the dataset covers the visitation distribution of the optimal policy n², but in a robust fashion since Cj.- considers all possible transition kernels in the robust set (PP). The robust consideration in C'P, is because in RMDPs the policies are all assumption is much weaker than full-coverage- style assumptions [68, 77, 40] which require either a uniformly lower bounded dataset distribution or covering the visitation distribution of any π E II. For x A-rectangular robust tabular MDPs (Fxample 2.5), the robust partial coverage coefficient Cj-- f is similar with the partial coverage coefficient proposed by [47] who studied tabular RMDPs under partial coverage. We highlight that beyond S x A-rectangular robust tabular MDPs, our robust partial coverage assumption can handle other examples of RMDPs (Section 2.2) under our unified theory.
evaluated in a robust way. This cartial-coveragestyye
Our main result is the following theorem. See Appendix C for detailed proof.
Theorem 3.4 (Suboptimality of P2MPO), Under Assumptions 2.2 and 3.3. suppose that Algorithmm I implements a sub-algorithm that satisfies Conditions 3.1 and 3.2, then with probability at least 1 - 28,
H
SubOpt (1) S / Op-
Σ
V
Em 2 (n,
When Err (n, d) achieves a rate of Ö(n-1), then P2MPO enjoys ((nn=1/))suuoopimmaii In the following Section 4, we give specific implementations of the model estimation step of P2MPO for each example of RMDP in Section 2. The implementations will make Conditions 3.1 and 3.2 satisfied and thus specify the unified result Theorem 3.4.
8

---

Implementations of PPP for Examples of RMDPs
In this section, we provide concrete implementations of the ModelEst sub-algorithm in P"MPO (Al- gorithm 1). In Section 4.1, , we implement ModelEst for all the RMDPs that satisfy Assumption 2.2,
and we specify the suboptimality bounds in Theorem 3.4 to Examples 2.5, 2.7, 2.8 Section 2.2. In
Section 4.2, we implement ModelEst for S x A-rectangular robust factored MDPs (Example 2.9) and specify Theorem 3.4 this example.
4.1 Model Estimation for General RMDPs with A-rectangular Robust Sets
Using the offline data D. we first construct the maximum likelihood estimator (MLE) of the transition kernel P*. Specifically, for each step h [H], we define
P = arg max
Σ log
(4.1)
PEPM 71
After, construct confidence region for the MLE estimator, denoted by P. Specifically, P contains all transitions which have a small total variance distance from P. For each step h E [H] we define
P = { PEPM-
Σ Pa(--15 07)) - P(11%% 111 S
(4.2)
Here { >> is tuning parameter that controls the size of the confidence region Ph. Finally, we set ModelEst(DD PM) = (Pn 1 with Pr, given (4.2). In the sequel, we mainly consider distance D(-II-) in Assumption 2.2 to be KL-divergence and TV-distance. The following corollary specifies Theorem 3.4 to model estimation step given by (4.2). See Appendix for a detailed proof.
Corollary 4.1 (Suboptimalityy of P2MPO: S x A-rectangular robust MDP). Under Assumption 2.2, 3.3, setting the tuning parameter & as
C1 Log(C2H1N
16)))
for some constants C1, C2 O, pd MPO with model estimation step given by (4.2) satisfies that when D(-II-) KL-divergence and Assumption D.3 holds with parameter 2 then with probability al least 25,
Cb., (Ixx(1)eep(H//))
Cf (L// PM, -11,00/))
SubOpt(T;s1)
when (1-1l.) is TV-iveergence, then with probability at least 25,
/ /G Cog(CCH (1/N2 PM, 1018)))
SubOpt(f;s1) VCp HH² H2
x A-rectangular robust tabular MDP (Example 2.5). When S is finite as in Example 2.5, the MLE estimator (4.1) coincides the empirical estimator
Pa Σn 138 = 8, 8, = a, 14,8%111 8)
(4.3)
IV 1s5 s. s. =
which is adopted by [77, 68, 39, 47, 40J. Furthermore, in Example 2.5, the realizable model space PM (P: ( (S)). When S and are finite, we can bound the bracket number of PM as
log No (1/n2, PM, (11,,0) 2|8) || log(()).)
(4.4)
Combining (4.4) and Corollary 4.1, we can conclude that: i) under TV-distance the suboptimality of
P²MPO for S A-rectanuulla robust tabular RMDP is given by O(H2, / /C+,, (|7 A log(nH/8)/n))
ii) under KI -l-diiergencce the suboptimality of P2MPO for S x A-rectangular robust tabular MDP is given by O exp(H/A)/p CCp. | log(n (nn/H)HH))))) 8)) We prove (4.4) in Appendix D.2.

---

Remark 4.2. We note that for KL-divergence robust sets, the dependence on expl H)) is due to the usage of general function approximations. which also appears in a recent work [29] for RMDPs with linear function upproximations. For the special case of robust tabular MDPs, under Kl.- divergence, existing work| [47] derived sample complexities without exp( H),, but with an additional dependence on 1/dginn and 1/P Here d'ninn (s.. als,a)>0 ap. ( a) and Pmin =
min ())p Pî (5' (1)) We remark that our analysis for P2MPO algorithm can be tailored to the tabular case and become exp(H)-free using their techniques, with the cost of an additional dependence on 1 1/dmin and P But we note that in the infinite stale space case, both the 1/d dependence and the P/ dependence becomes problematic. So, it serves as an interesting future work to answer whether one derive both exp(H))-rre and (1/d 1/P min) free results for (general) function approximations under KL-divergence.
S x A-rectangular robust MDP with kernel and neural function approximations (Examples 2.7 and 2.8). By specifying the bracket numbers in Corollary 4.1, we can provide the detailed subopti- mality guarantees for S x A-rectangular robust MDP with kernel and neural function approximations. Due to space limitations, we defer the detailed results Appendices D.3 and D.4.
4.2 Model Estimation for S x A-rectangular Robust Factored MDPs (Example 2.9)
We first construct MLE estimator for each factor Ph, of the transition Px
d P h,s that is,
Pr.
arg max Pr
Σ log 1ol
(4.5)
Then given {Prijd we construct a confidence region that is factored across i E [d]. Specifically,
d
Pr
II 2=1
a) 1 Σ 1=1
(IP, Praa)-157 DiI S E,, V. (4.6)
{ with Pr, given in (4.6). The following corollary specifies Theorem 3.4 to model estimation step given by (4.6). See Appendix E for detailed proof. Corollary 4.3 (Suboptimality of рºMPO: S x A-rectangulaa robust factored MDP). Supposing the RMDP is an S x A-rectangular robust factored MDP, under the same Assumptions and parameter choice in Theorem 3.4 and Proposition E.I, 12 MPO with model estimation step given by (4.6) satisfies when (--ll-) is KL-divergence and Assumption D.3 holds with parameter X, then with probability at least 25, (defining Pmin = min Ps)
Finally, we set ModelEst(ID.
Co H Hxx((HHAA)
dci Ed 10 + A log C/nd/))
SubOpt(fi:s1)
Punin
when D(-Il-) is TVviierggee,,, then with probability at least 1 1--2 26,
dc, Ei 1= O| log log(Ch) (Cnnd/8)
SubOpt(f;:11) - Vop. HP
Compared with the suboptimality bounds for S x A-rectangular robust MDPs in Section 4.1, the suboptimality of S A-rectangular robust factored MDPs with ModelEst given in (4.6) only scales with Σi [0]1+ipa, instead of scaling with [S] = H |O] which is of order exp(d). This justifies the benefit of considering S x A-rectangular robust factored MDPs when the transition kernels of training and testing environments enjoy factored structures.
Conclusion and Discussions
This paper proposes a general learning principle - double pessimism - for robust offline RL. Based on this learning principle, we propose a generic algorithm that only requires robust partial coverage data to solve S x A-rectangular RMDPs with general function approximation. Our results are ready to be extended to d-rectangular linear RMDPs [29]. See Appendix for details. In Appendix A, we also provide some challenges to perform sample efficient RL in S-rectangular RMDPs.
10

---

Acknowledgments and Disclosure of Funding
The material in this paper is based upon work supported by the Air Force Office of Scientific Research under award number FA9550-20-1-085 1-0397. Additional support is gratefully acknowledged from NSF 1915967, 21 18199, 2229012, 2312204.
References
[1] Alekh Agarwal, Nan Jiang, Sham M Kakade, and Wen Sun. Reinforcement learning: Theory and algorithms. CS Dept., UW Seattle, Seattle, WA, USA, Tech. Rep, pages 10-4, 2019.
[2] András Antos, Csaba Szepesvári, and Rémi Munos. Learning near-optimal policies with bellman-reeidual minimization based fitted policy iteration and single sample path. Machine Learning, 71(1 71(1):89-129, 2008.
[3] Kishan Panaganti Badrinath and Dileep Kalathil. Robust reinforcement learning using least squares policy iteration with provable performance guarantees. In International Conference on Machine Learning, pages 51 1-5-0... PMLR, 2021.
[4] Qi Cai, Zhuoran Yang, Csaba Szepesvari, and Zhaoran Wang. Optimistic policy optimization with general function approximations. 2020.
[5] Jinglin Chen and Nan Jiang. Information-theorete considerations in batch reinforcement learning. In International Conference Machine Learning, pages 1042-1051. PMLR, 2019,
[6] Ching-An Cheng, Tengyang Xie, Nan Jiang, and Alekh Agarwal. Adversarially trained actor critic for offline reinforcement learning. arXiv preprint arXiv:2202.022446 2022.
[7) Pierre Clavier, Erwan Le Pennec, and Matthieu Geist. Towards minimax optimality of model- based robust reinforcement learning. arXiv preprint arX1v:2302.05372, 2023.
[8] Jing Dong, Jingwei Li, Baoxiang Wang, and Jingzhao Zhang. Online policy optimization for robust mdp. arXiv preprini 22:::2229938811 2022.
[9] Laurent El Ghaoui and Arnab Nilim. Robust solutions to markov decision problems with uncertain transition matrices. Operations Research, 53(5):780- 2005.
[10] Chin Pang Ho, Marek Petrik, and Wolfram Wiesemann. Robust di-divergence mdps. 2022.
[11] Jiachen Hu, Han Zhong, Chi Jin, and Liwei Wang. Provable sim-to-real transfer in continuous domain with partial observations. arXiv preprini 10..xx::220..55500 2022.
[12] Zhaolin Hu and Jeff Hong. Kullback-leibler divergence constrained distributionally robust optimization. Available at Optimization Online, pages 1695-1724, 2013.
[13] Garud N Iyengar. Robust dynamic programming. Mathematics of Operations Research, 30(2): 257-280, 2005.
[14] Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kemel: Convergence and generalization in neural networks. Advances in neural information processing systems, 31, 2018.
[15] Chi Jin, Zhuoran Yang. Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pages 2137- 2143. PMLR, 2020.
[16] Ying Jin, Zhuoran Yang. and Zhaoran Wang. pessimism provably efficient for offline rI? In International Conference on Machine Learning, pages 5084-5000 5096. PMLR, 2021.
[17] Michael Kearns and Daphne Koller. Efficient reinforcement learning in factored mdps. In IJCAI, volume 16, pages 740-747, 1999.
[18] Jens Kober, J Andrew Bagnell, and Jan Peters. Reinforcement learning in robotics: survey. The International Journal of Robotics Research, 32(11)) 2013,

---

[19] Yufei Kuang, Miao Lu, Jie Wang, Qi Zhou, Bin Li, and Houqiang Li. Learning robust policy against disturbance in transition dynamics via state-conservative policy optimization. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 7247-7254, 2022.
[20] Aviral Kumar, Aurick Zhou, George Tucker, and Sergey Levine. Conservative q-learning for offline reinforcement learning. Advances in Neural Information Processing Systems, 33: 1 1179-1191, 2020.
[21] Sascha Lange. Thomas Gabel, and Martin Riedmiller. Batch reinforcement learning. In Reinforcement learning, pages 45-73. Springer, 2012.
[22] Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu. Offline reinforcement learning: Tutorial, review, and perspectives on open problems. arXiv preprint arXiv:2005.01643; 2020.
[23] Chris Junchi Li, Dongruo Zhou, Quanquan Gu, and Michael I Jordan. Learning two-player mixture markov games: Kernel function approximation and correlated equilibrium. arXiv preprini N20::2200.003666 2022.
[24] Gen Li, Laixi Shi, Yuxin Chen, Yuejie Chi, and Yuting Wei. Settling the sample complexity of model-based offline reinforcement learning. arXiv preprint arXiv:2204.05275. 2022.
[25] Zhihan Liu, Miao Lu, Zhaoran Wang, Michael Jordan, and Zhuoran Yang. Welfare maximiza- tion in competitive equilibrium: Reinforcement learning for markov exchange economy. In International Conference on Machine Learning, pages 13870-1391 1. PMLR, 2022.
[26] Zhihan Liu, Yufeng Zhang, Zuyue Fu, Zhuoran Yang, and Zhaoran Wang. Learning from demon- stration: Provably efficient adversarial policy imitation with linear function approximation. In International Conference Machine Learning, pages 14094 14138. PMLR, 2022.
[27] Zijian Liu, Qinxun Bai, Jose Blanchet, Perry Dong, Wei Xu, Zhengqing Zhou, and Zhengyuan Zhou. Distributionally robust q- g-learning. In International Conference on Machine Learning. pages 13623-13643. PMLR, 2022.
[28] Miao Lu, Yifci Min, Zhaoran Wang, and Zhuoran Yang. Pessimism in the face of confounders: Provably efficient offline reinforcement learning partially observable markov decision pro- cesses. arXiv preprint arXiv:2205. 2022.
[29] Xiaoteng Ma. Zhipeng Liang. Li Xia, Jiheng Zhang, Jose Blanchet, Mingwen Liu, Qianchuan Zhao, and Zhengyuan Zhou. Distributionally robust offline reinforcement learning with linear function approximation. arXiv preprint arXiv:200.006620. 2022.
[30] Ajay Mandlekar, Yuke Zhu, Animesh Garg, Li Fei-Fei, and Silvio Savarese. Adversarially robust policy learning: Active construction of physically perturbations. In 20/7 IEEE/RS/ International Conference on Intelligent Robots and Systems (IROS), pages 3932-3939 IEEE, 2017.
[31] Shie Mannor, Duncan Simester, Peng Sun, and John N Tsitsiklis. Bias and variance in value function estimation. In Proceedings of the twenty-first international conference on Machine learning, page 72, 2004.
[32] Jun Morimoto and Kenji Doya. Robust reinforcement learning. Neural computation, 17(2): 335-359, 2005.
[33] Rémi Munos. Error bounds for approximate value iteration. In Proceedings of the National Conference on Artificial Intelligence, volume 20, page 1006. Menlo Park, CA; Cambridge, MA; London; AAAI Press; MIT Press; 1999, 2005.
[34] Gergely Neu and Ciara Pike-Burke. A unifying view of optimism in episodic reinforcement learning. Advances in Neural Information Processing Systems, 33:1392. 33:1392-1444 1403, 2020.
[35] Ariel Neufeld and Julian Sester. Robust q-learning algorithm for markov decision processes under wasserstein uncertainty. arXiv preprint arXiv:2210.00880 2022.
12

---

[36] Arnab Nilim and Laurent EI Ghaoui. Robust control of markov decision processes with uncertain transition matrices. Operations Research, 53(5):780-798, 2005.
[37] OpenAI, Marcin Andrychowicz. Bowen Baker. Maciek Chociej. Rafal Józefowicz, Bob McGrew, Jakub Pachocki, Arthur Petron, Matthias Plappert, Glenn Powell, Alex Ray. Jonas Schneider, Szymon Sidor, Josh Tobin, Peter Welinder, Lilian Weng, and Wojciech 7aremba. Learning dexterous in-hand manipulation. CoRR, 2018. URL http://arxii org/ abs/ 1abbb//88880007...
[38] Yunpeng Pan, Ching-An Cheng, Kamil Saigol, Keuntaek Lee, Xinyan Yan, Evangelos Theodorou, and Byron Boots. Agile autonomous driving using end-to-end deep imitation learning. arXiv preprint urXiv:1709.07111 2017.
[39] Kishan Panaganti and Dileep Kalathil. Sample complexity of robust reinforcement learning with generative model. In International Conference Artificial Intelligence and Statistics, pages 9582-9602. PMLR, 2022.
[40] Kishan Panaganti. Zaiyan Xu, Dileep Kalathil, and Mohammad Ghavamzadeh. Robust rein- forcement learning using offline data. arXiv preprint Stti::2208.052299 2022.
[41] Anay Pattanaik, Zhenyi Tang, Shuijing Liu, Gautham Bommannan, and Girish Chowdhary. Robust deep reinforcement learning with adversarial attacks. arXiv preprint arXiv:1712.0362. 2017.
[42] Xue Bin Peng. Marcin Andrychowicz, Wojeiech Zaremba, and Pieter Abbeel. Sim-to-real transfer of robotic control with dynamics randomization. In 2018 IEEE international conference on robotics and automation (ICRA), pages 3803-3810. IEEE, 2018.
[43] Lerrel Pinto, James Davidson, and Abhinav Gupta. Supervision via competition: Robot adver- saries for learning tasks. In 2017 IEFE International Conference on Robotics and Automation (ICRA), pages 1601-1608. IEEE, 2017
[44] Lerrel Pinto, James Davidson, Rahul Sukthankar, and Abhinav Gupta. Robust adversarial reinforcement learning. In International Conference on Machine Learning, pages 2817-2826.
PMLR, 2017.
[45] Paria Rashidinejad, Banghua Zhu, Cong Ma. Jiantao Jiao, and Stuart Russell. Bridging offline reinforcement learning and imitation learning: A tale of pessimism. Advances in Neural Information Processing Systems, 34:1 1702-11716, 2021.
[46] Paria Rashidinejad, Hanlin Zhu, Kunhe Yang, Stuart Russell, and Jiantao Jiao. Optimal conservative offline rl with general function approximation via augmented lagrangian. arXiv preprint arXiv:2211 1..0222..10006..11 2022.
[47] Laixi Shi and Yuejie Chi. Distributionally robust model-based offline reinforcement learning with near-optimal sample complexity. arXiv preprint arXiv:2208.05767, 2022.
[48] Laixi Shi, Gen Li, Yuting Wei, Yuxin Chen, and Yuejie Chi. Pessimistic q-learning for offline reinforcement learning: Towards optimal sample complexity. arXiv preprint 22X2:22002.18900 2022.
[49] Nian Si, Fan Zhang, Zhengyuan Zhou, and Jose Blanchet. Distributionally robust batch contextual bandits. Management Science, 2023.
[50] Ingo Steinwart and Andreas Christmann. Support vector machines. Springer Science & Business Media, 2008
[51] Wen Sun, Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, and John Langford. Model-based contextual decision processes: Pac bounds and exponential improvements over model-free approaches. In Conference on learning theory, pages 2898-2933. PMLR, 2019.
[52] Richard Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
13

---

[53] Chen Tessler, Yonathan Efroni, and Shie Mannor. Action robust reinforcement learning and applications in continuous control. In International Conference on Machine Learning, pages 2215-62244 PMLR, 2019.
[54] Masatoshi Uehara and Wen Sun. Pessimistic model-based offline reinforcement learning under partial coverage. arXiv preprint arXiv:2107.06226, 2021.
[55] Sara A Van de Geer. Empirical Processes in M-estimation, volume Cambridge university press, 2000.
[56] Lu Wang. Wei Zhang, Xiaofeng He, and Hongyuan Zha. Supervised reinforcement learning with recurrent neural network for dynamic treatment recommendation. In Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery data mining, pages 2447-2456 2018.
[57] Qiuhao Wang, Chin Pang Ho, and Marek Petrik. On the convergence of policy gradient in robust mdps. arXiv preprint arXiv:2212.10339, 2022.
[58] Shengbo Wang, Nian Si, Jose Blanchet, and Zhengyuan Zhou. A finite sample complexity bound for distributionally robust q-earnnng. In International Conference Artificial Intelligence and Statistics, pages 3370-3398. PMLR, 2023.
[59] Yue Wang and Shaofeng Zou. Online robust reinforcement learning with model uncertainty. Advances Neural Information Processing Systems, 34:7193-7200 2021.
[60] Yue Wang and Shaofeng Zou. Policy gradient method for robust reinforcement learning. In International Conference Machine Learning, pages 23484-23526. PMLR, 2022.
[61] Wolfram Wiesemann, Daniel Kuhn, and Berç Rustem. Robust markov decision processes. Mathematics of Operations Research, 38(1):153- 2013.
[62] Tengyang Xie, Ching-An Cheng, Nan Jiang, Paul Mineiro, and Alekh Agarwal. Bellman- consistent pessimism for offline reinforcement learning. Advances in neural information processing systems, 34:6683-6694, 2021.
[63] Tengyang Xie, Nan Jiang, Huan Wang, Caiming Xiong, and Yu Bai. Policy finetuning: Bridging sample-efficient offline and online reinforcement learning. Advances in neural information processing systems, 34:27395-2745
2021.
[64] Wei Xiong, Han Zhong, Chengshuai Shi, Cong Shen, Liwei Wang, and Tong Zhang. Nearly minimax optimal offline reinforcement learning with lincar function approximation: Single- agent mdp and markov game. arXiv preprint 1555, 2022.
[65] Huan Xu and Shie Mannor. Distributionally robust markov decision processes. Advances in Neural Information Processing Systems, 23, 2010.
[66] Zaiyan Xu, Kishan Panaganti, and Dileep Kalathil. Improved sample complexity bounds for distributionally robust reinforcement learning. In International Conference on Artificial Intelligence and Statistics, pages 9728-99888 997889994. PMLR, 2023.
[67] Greg Yang and Hadi Salman. A fine-grained spectral perspective neural networks. arXiv preprint arxiv: 1907, 10599, 2019.
[68] Wenhao Yang, Liangyu Zhang, and Zhihua Zhang. Towards theoretical understandings of robust markov decision processes: Sample complexity and asymptotics. arXiv preprint arXiv:2/05.03383, 2021.
[69] Wenhao Yang, Han Wang, Tadashi Kozuno, Scott M Jordan, and Zhihua Zhang, Avoiding model estimation robust markov decision processes with generative model. arXiv preprint arXiv:2302.01224, 2023.
[70] Zhuoran Yang, Chi Jin, Zhaoran Wang, Mengdi Wang, and Michael Jordan. Provably efficient reinforcement learning with kernel and neural function approximations. Advances in Neural Information Processing Systems, 13:13993-1 2020.
14

---

[71] Ming Yin and Yu-Xin Yu-Xiang Wang. Towards eetaace--ptimag offline reinforcement learning with pessimism. Advances neural information processing systems, 34:4065-400 2021.
[72] Tianhe Yu, Garrett Thomas, Lantao Yu, Stefano Ermon, James Zou, Sergey Levine, Chelsea Finn, and Tengyu Ma. Mopo: Model-based offline policy optimization. Advances in Neural Information Processing Systems, 1141199-1142,, 2020.
[73] Andrea Zanette, Martin Wainwright, and Emma Brunskill. Provable benefits of actor-critt methods for offlin reinforcement learning. Advances in neural information processing systems, 34:1 14:13626-13640 2021.
[74] Wenhao Zhan, Baihe Huang, Audrey Huang, Nan Jiang, and Jason Lee. Offline reinforcement learning with realizability and single-policy concentrability, In Conference on Learning Theory, pages
PMLR, 2022.
[75] Huan Zhang. Hongge Chen, Chaowei Xiao, Bo Li, Mingyan Liu, Duane Boning, and Cho- Jui Hsieh. Robust deep reinforcement learning against adversarial perturbations on state observations. Advances in Neural Information Processing Systems, 33:2 33:21024-21037, 2020.
[76] Wenshuai Zhao, Jorge Peña Queralta, and Tomi Westerlund. Sim-to-real transfer in deep reinforcement learning for robotics: a survey. In 2020 IEEE Symposium Series on Computational Intelligence (SSCI), pages 737-744. IEEE, 2020.
[77] Zhengqing Zhou, Zhengyuan Zhou, Qinxun Bai, Linhai Qiu, Jose Blanchet, and Peter Glynn. Finite-sample regret bound for distributionally robust offline tabular reinforcement learning. In International Conference on Artificial Intelligence and Statistics, pages 3331-3339, PMLR, 2021.
15


Reviews:
[{"review_id": "IRA7Ubd4Gq", "reviewer": "Reviewer_NCKb", "summary": "This paper studies the offline robust RL problem. A double pessimism approach is proposed and studied. ", "questions": "1. Do you have some efficient approach to solve the model you proposed? \n2. The analysis seems similar to the ones in [Masatoshi Uehara and Wen Sun, 2022], can you highlight the novelty and contribution?", "limitations": "See parts above.", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The approach is novel and new compared to previous offline robust RL ones. \n2. The approach can be used for large-scale problems. \n3. The theoretical analysis is comprehensive. ", "weaknesses": "1. The model the authors proposed, seems hard to solve. With no robustness consider, the model reduces to the one in [Masatoshi Uehara and Wen Sun, 2022]. The model in the non-robust is hard to solve and becomes hard together with robustness. \n2. Compared to [Masatoshi Uehara and Wen Sun, 2022], the contribution seems a little bit incremental to me. The results and approaches are not surprising, in aspects of approach designing and error bound analysis.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Response to Reviewer NCKb**\n\nThanks for your review and the feedback. We will try our best to address all your concerns and questions in the following.\n\n**Q1: The model the authors proposed, seems hard to solve. Do you have some efficient approach to solve the model you proposed?**\n\n**A1:** We clarify that our work focuses on the statistical side of robust offline RL under general function approximations, which remains an important open problem. Our algorithm is therefore information-theoretic and is indeed intractable with an abstract function approximation class. The objective we designed is to achieve statistical efficiency in the most general setup. Computational efficiency is not our focus.\n\nMeanwhile, if we specify the model space, for example, tabular case or linear/kernel function classes, we can design approximations of our doubly pessimistic algorithm. For example in tabular RMDPs, we can replace the iterative infimum in our double pessimism objective by an LCB-style bonus. This has been shown to be efficient both theoretically and experimentally by [1], which can demonstrate the efficiency and practicality of our general algorithm design. For more complicated deep RL setup, a promising approach is to extend the algorithm proposed by [2]. It implements the model-based pessimistic offline RL algorithm for non-robust MDPs, which iterates between an agent update step (corresponding to $\\sup_{\\pi\\in\\Pi}$) and an adversarial model update step (corresponding to $\\inf_{P\\in\\widehat{\\mathcal{P}}}$). Adapting the adversarial model update step to our doubly pessimistic value estimator can serve as an approximate implementation of the algorithm proposed by our work.\n\n**Q2: Compared to [3], the contribution in terms of approach designing and error bound analysis seems a little bit incremental. Can you highlight the novelty and contribution?**\n\n**A2:** We respectfully disagree that our work contributes incrementally compared to [3]. Essentially, our work is on distributionally robust offline reinforcement learning, a different problem setup from [3], with its own distinct challenges in terms of algorithmic design and theoretical analysis. And to the best of our knowledge, our work is the first to propose a provably sample-efficient algorithm for distributionally robust offline RL in the context of general function approximation. \n\nIn the following, we compare our work with [3] in more detail.\n\n- **Approach designing.** In robust offline RL, there exist two sources of distributional shifts which are coupled with each other: (i) the mismatch between the behavior policy and the target policies to be learned; and (ii) the mismatch between the nominal environment and the perturbed environment. The latter is a unique challenge that is not presented in non-robust offline RL [3]. Therefore, it remains unknown how to design sample-efficient algorithms that can provably tackle these two types of shifts under general function approximation. With this in mind, our approach features a noval algorithmic design principle named \"double pessimism\", which performs pessimistic model selection in the face of both kinds of distributional shifts *simultaneously*. This is essentially different from [3]. Our work is the first to identify such a new algorithmic design principle for robust offline RL with general function approximation.\n- **Error bound analysis.** When there are coupled shifts (i) and (ii), the theoretical analysis of [3] would also fail. In fact, our analysis is based on a different framework from [3], in terms of analyzing: \n    - *Pessimism in the face of two souces of distributional shifts*: These calls for new analysis techniques for error decomposition and analysis of pessimism (Appendix D). Also, our analysis is based on the notion of robust partial coverage coefficient (Assumption 3.3) which is customized for robust RL. This is different from using the standard partial coverage coefficient for MDPs [3], requiring new analysis techniques. \n    - *Model estimation error analysis coupled with distributional shifts:* Compared with standard offline RL analysis of transition kernel estimation [3], this requires a delicate application and analysis of the dual representations for distributionally robust objectives (Appendices E and F). Under our unified analysis framework, we customize different model estimation subroutines and their corresponding analysis for different kinds of RMDPs. Also, we highlight that our work studies several new examples of RMDPs, e.g., factored RMDPs, and their model estimation analysis are completely new.\n\n\n**References:**\n\n[1] Shi, Laixi, and Yuejie Chi. \"Distributionally robust model-based offline reinforcement learning with near-optimal sample complexity.\" arXiv preprint arXiv:2208.05767 (2022).\n\n[2] Rigter, Marc, Bruno Lacerda, and Nick Hawes. \"Rambo-rl: Robust adversarial model-based offline reinforcement learning.\" Advances in neural information processing systems 35 (2022): 16082-16097.\n\n[3] Uehara, Masatoshi, and Wen Sun. \"Pessimistic Model-based Offline Reinforcement Learning under Partial Coverage.\" International Conference on Learning Representations. 2022.\n"}, {"review_id": "gmlHfAdFwH", "reviewer": "Reviewer_p1MD", "summary": "This paper proposed a generic framework to study distributionally robust offline reinforcement learning problems, which included a model estimation step and a robust policy optimization step. Previous works in the literature usually assume finite state action spaces; this framework can incorporate function approximations and ultimately paved the way of tackling large state action spaces. Additionally, two specific model estimation approaches are introduced and studied in details; corresponding sample complexity results are provided.", "questions": "1.  The underscore $\\lambda$ and $C_1$ in the Corollary 4.1 is not defined in the main paper. They are well-defined in the appendix; I think it is better to at least provided the meaning of underscore $\\lambda$ here. In addition, is it possible to avoid the assumption of the lower bound on the dual variable $\\lambda$? As you consider the two-step uncertainty set, I think you could provide sub-optimality gap in terms of $\\epsilon$ and $\\rho$ in Section 4 and discuss the choices of them as well. \n\n2. Some distributionally robust RL papers that adopt KL-divengence as the uncertainty set measure have radius square in the SubOpt term, e.g., [37] [64] in the papers you cited, while your SubOpt does not suffer from the radius square term. Can you comment on this? I think this could be a big benefit when selecting small $\\rho$s.", "limitations": "This is a theoretical work at this stage and thus no potential negative societal impact of their work.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "This paper explicitly considered the two sources of uncertainties in distirbutionally robust RL problems. The first one is the difference between the estimated training model using finite samples and the true training model; the second one is the difference between the true training model and the testing model. Current literature usually assume that the testing model is within a radius of the estimated training model. The double pessimistic idea is new. Additionally, only partial coverage offline dataset is required, while many previous works require observing all state action pairs in the dataset.  \n\nThis paper also provided an interesting sub-optimality theorem that decomposes the sub-optimality gap into a model estimation error part and a data coverage part, which could be used for future developments. \n\nThe problem setting, definitions and notations are clear and easy to understand.", "weaknesses": "The paper is somewhat hard to follow. A lot of examples that can be studied under the proposed framework are presented in the main paper. I think it is better to present one example in details in the main paper, move the others to the appendix and put relevant literature review in the main paper. Similarly, in the model estimation parts, one example should be enough. \n\nThe motivation of considering the double pessimism is not clear to me. Two uncertainty sets are introduced, the model uncertainty set, for example, is controlled by $\\epsilon$ when using MLE estimator and the distribution shift robust uncertainty set is controlled by $\\rho$. It is not clear to me whether the two phase uncertainty sets are necessary as in general we don't know $\\rho$. In practice, people may use similar datasets that include both training and testing sets to estimate (guess) the uncertainty set radius, which is a single phase approach and directly captures the difference between the finite training set and the testing set. More rationales or examples should be provided to motivate the two-step approach. For example, 1) the authors could provide applications that singles-step uncertainty set cannot be easily estimated while the two-step approach is more applicable in practice, 2) the author could theoretically show that this two-step approach can avoid conservativeness under certain conditions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your detailed review and the meaningful suggestions! In the following, we will try our best to address all your concerns and questions. \n\n**Q1: It is better to present one example in details in the main paper, move the others to the appendix and put relevant literature review in the main paper. Similarly for the model estimation parts.**\n\n**A1:** Thanks for pointing out! We will improve the presentation following your suggestions.\n\n**Q2: The motivation of double pessimism is not clear. It's unknown whether the two phase uncertainty sets are necessary as in general we don't know $\\rho$.  ···**\n\n**A2:** Thanks for your questions. In the following, we will explain more about the motivation and necessity of the double pessimism principle.\n\nThe theoretical motivation to consider performing pessimism twice is that we want to handle the two sources of distributional shifts in robust offline RL: (i) the mismatch between the behavior policy and the target policies to be learned; (ii) the mismatch between the training environment and the testing environment. Thus our approach is to perform pessimism in the face of *model estimation uncertainty* and *test environment uncertainty* simultaneously. The model estimation uncertainty originates from statistical estimation of the training environment transition kernel $P^{\\star}$ under the mismatch between the state-action distributions induced by the behavior policy and the target policies. The test environment uncertainty comes from the the mismatch between the environments for training and testing. Since the test environemt is in a robust set centered at the training environment $P^{\\star}$, these two kinds of uncertainties are coupled with each other and a two-step-style pessimism approach is developed.\n\nTheoretically, our double pessimism approach can reduce the requirement of the training data to the minimum: the robust partial coverage condition (Assumption 3.3), i.e., only covering the distributions induced by the optimal policy and the transition kernels in the robust set of the nominal transition kernel, which is much weaker than full-coverage-style conditions like a uniformly lower bounded data distribution. This is impossible without the double pessimism approach.\n\nRegarding your concern that $\\rho$ might be unknown, we admit that in practice this could be the case. In that case, the robust parameter can either serve as a tuning parameter balancing between the robustness of and the performance of the learned policy, or simply be chosen by experts or priors. Still, in our theoretical work we assume a known $\\rho$, which is commonly adopted by the large body of researches on robust RL.\n\nFinally, we clarify that our work focuses on the offline setup with no access to the test environment data, which is often the case in practice. E.g., in robotics, people may have no access to the exact place where the robotics they trained will be deployed. Thus no test data are available. It's an interesting future work if the learner is provided with an extra data related to the test environment.\n\n**Q3: The underscore $\\underline{\\lambda}$ and $C_1$ in the Corollary 4.1 is not defined in the main paper. I think it is better to provide the meaning of underscore $\\underline{λ}$ here. In addition, is it possible to avoid the assumption of the lower bound on the dual variable $\\underline{\\lambda}$?**\n\n**A3:** We have mentioned in Line 293 that $C_1$ is an absolute constant. Furthermore, we acknowledge the importance of clarifying the meaning of $\\underline{\\lambda}$ in Corollary 4.1. In the revision, we will provide an explanation that $\\underline{\\lambda}$ represents the lower bound of the dual variables of some DRO problems. \n\nWe want to emphasize that this issue is incurred by the KL robust set. In addition to this setting, we also study robust RL with TV robust set, which is also a standard and important setting. For robust RL with TV robust set, we do NOT need the regular assumption like Assumption E.3, and the final suboptimality gap is *polynomial in all parameters*. It's worth mentioning that the adoption of this assumption in problems with the KL robust set is consistent with previous works (e.g., [45]). From our perspective, removing this assumption in the context of RMDPs with function approximation, without introducing additional assumptions, presents a challenge due to the inherent nature of KL-divergence.\n\n\n**Q4: As you consider the two-step uncertainty set, I think you could provide sub-optimality gap in terms of $\\epsilon$ and $\\rho$ in Section 4 and discuss the choices of them as well.**\n\n**A4:** We note that the conclusions in Section 4 are actually in terms of the $\\epsilon$ and $\\rho$ you mentioned. The parameter $\\xi$ in Corollary 4.1 & 4.2 corresponds to $\\epsilon$. Therefore, for KL-divergence robust sets, the suboptimality gap is of order $\\mathcal{O}(\\xi\\cdot\\rho^{-1})$, while for the TV-distance robust sets the suboptimality gap is of order $\\mathcal{O}(\\xi)$, i.e., $\\rho$-independent. The choice of $\\xi$ is obtained from statistical analysis of the estimation of the nominal transition kernel, while $\\rho$ is fixed by the RMDP problem instance we are considering. Thanks for pointing that out and we will add discussions.\n\n**Q5: Some DRRL papers with KL-divengence have radius square in the SubOpt term, e.g., [37] [64] you cited, while your SubOpt does not suffer from the radius square term. Can you comment on this?**\n\n**A5:** It seems that both [37] and [64] have Suboptimality scaling with $\\mathcal{O}(\\rho^{-1})$. Their results are presented in the form of sample complexity $N_{\\mathrm{KL}} = \\mathcal{O}(\\epsilon^{-2}\\rho^{-2})$, which means that to obtain $\\epsilon$-optimal robust polciy, $N_{\\mathrm{KL}}$ samples are needed. Converting it to the language of SubOpt, this gives an $\\mathcal{O}(\\rho^{-1}\\cdot N_{\\mathrm{KL}}^{-1/2})$ suboptimality. Thus, in the tabular case, our dependence on $\\rho$ conincides with [37] and [64]."}, {"review_id": "s64u6dj6eM", "reviewer": "Reviewer_otjP", "summary": "This paper studies distributionally robust offline reinforcement learning. They propose a general learning principle, double pessimism, as well as a generic algorithm framework P$^2$MPO for robust offline RL, and  show that it is provably efficient in the context of general function approximation.", "questions": "1. On line 100, is the policy a function from $\\mathcal{S}$ to $\\Delta(A)$?\n\n2. How strong are assumption D.1 and E.1, are they reasonable?\n\n3. Check inequality (E.23) '$0\\leq \\lambda_iH$'.\n", "limitations": "Yes.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper is well-written and theoretically solid. It provides several novel contributions to the field of distributionally robust MDP.\n\nFirst, it proposes a general learning principle, double pessimism, together with a generic algorithm framework P$^2$MPO and a unified theoretical analysis.\n\nSecond, it proposes several novel structures of uncertainty set and discusses their qualities under three commonly used rectangularity assumptions. Under these structures, they solve the open problem of learning robust offline RL in the context of general function approximation.\n", "weaknesses": "Some minor issue of typos.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Response to Reviewer otjP**\n\nThanks you so much for your appreciation of our work! We will keep improving our paper following your feedbacks. In the following, we address all your concerns and questions.\n\n**Q1: Some minor typos: i) On line 100, is the policy a function from $\\mathcal{S}$ to $\\Delta(\\mathcal{A})$? ii) Check inequality (E.23) $0\\leq \\lambda_i H$.**\n\n**A1:** Thanks so much for pointing those out! We will correct them in the revision.\n\n**Q2: How strong are assumption D.1 and E.1, are they reasonable?**\n\n**A2:** You mean the assumptions on the lower bound of dual variables (Assumption E.3 and F.2)? It's worth mentioning that the adoption of this assumption in problems with the KL robust set is consistent with previous works (e.g., [1]). From our perspective, removing this assumption in the context of RMDPs with function approximation, without introducing additional assumptions, presents a challenge due to the inherent nature of KL-divergence. In our work, we also investigate robust RL with the TV robust set, which is a standard and significant setting. For robust RL with TV robust set, we do NOT need the regular assumption like Assumption E.3 and F.2, and the final suboptimality gap is *polynomial in all parameters*. \n\n**References:**\n\n[1] Ma, Xiaoteng, et al. \"Distributionally robust offline reinforcement learning with linear function approximation.\" arXiv preprint arXiv:2209.06620 (2022)."}, {"review_id": "3k4pu1SRri", "reviewer": "Reviewer_F7Eb", "summary": "This study focuses on distributionally robust offline reinforcement learning to discover an optimal robust policy using an offline dataset for effective performance in perturbed environments. A novel algorithm framework called Doubly Pessimistic Model-based Policy Optimization (P2MPO) is proposed. P2MPO combines a flexible model estimation subroutine with a doubly pessimistic policy optimization step, leveraging the double pessimism principle to address challenges arising from behavior-policy mismatch and model perturbations. The study demonstrates the sample efficiency of P2MPO with robust partial coverage data and highlights its convergence rate. It introduces the concept of double pessimism as a general learning principle for robust offline RL, showcasing its efficiency in kernel and neural function approximators.", "questions": "please see weaknesses", "limitations": "Regarding S-rectangular sets, please see weaknesses", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "I think this work really pushes the robust RL community research efforts further by answering: \n> can we design a generic algorithm for robust offline RL in the context of function approximation?\n\nThe main contribution of double pessimism: one for robustness of dynamics uncertainty and one for model-estimation using offline data is a really nice idea worthy for publication at NeurIPS.", "weaknesses": "I have only minor weaknesses for this work as follows:\n\n1. The robust Bellman equation for d-rectangular sets are not formally proven. The proof isn't there even in [Ma et al. 22] to the extent of my search. The current Appendix C just rewrites [Iyengar 05] proof. Maybe replace it by the proof for d-rectangular robust Bellman equation?\n2. The robust partial concentrability dependence on the robust set $\\Phi$: Is it tight? Is there a lower bound for this setting? The reason for this question is coming from the fact that the robust solution is looking for $\\min$ over the robust set $\\Phi$.\n3. Honestly, Section B.2 can be expanded further. I found the following statement vague in its current form:\n> our algorithm framework is unable to deal with this kind of rectangular robust sets in the context of partial coverage data due to some technical problems in applying the partial coverage coefficient (Assumption 3.3) under this kind of robust sets.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Response to Reviewer F7Eb**\n\nThanks so much for your appreciation of our work! We will keep improving our paper following your suggestions. In the following, we address all your concerns and questions.\n\n\n**Q1: The robust Bellman equation for $d$-rectangular sets are not formally proven. The proof isn't there even in [1] to the extent of my search. The current Appendix C just rewrites [2] proof. Maybe replace it by the proof for d-rectangular robust Bellman equation?**\n\n**A1:** Yes, we agree with your comments that currently a strict proof of the robust Bellman equation for $d$-rectangular linear MDPs proposed by [1] is still missing. Actually we can prove it following a similar argument as in $\\mathcal{S}\\times\\mathcal{A}$-robust set case. Thanks for your suggestions and we would consider adding its proof in the revision to be self-content.\n\n**Q2: regarding the robust partial concentrability dependence on the robust set $\\boldsymbol{\\Phi}$, is it tight? Is there a lower bound for this setting? The reason for this question is coming from the fact that the robust solution is looking for min over the robust set $\\boldsymbol{\\Phi}$.**\n\n**A2:** We think the robust concentrability dependence on the robust set is tight. For the robust single-policy clipped concentrability $C_{\\mathrm{rob}}^\\star$ defined in [3], we can show that $\\sqrt{C_{P^\\star, \\boldsymbol{\\Phi}}^\\star} \\le C_{\\mathrm{rob}}^\\star.$ Together with the lower bound $\\Omega(C_{\\mathrm{rob}}^\\star/\\varepsilon^2)$ in [3], we know our robust partial coverage coefficient $C_{P^\\star, \\boldsymbol{\\Phi}}^\\star$ characterizes the statistical limit of robust offline RL. Here we omit other parameters such as the horizon length $H$ in the lower bound and $\\varepsilon$ is the accuracy of the desired policy.\n\n**Q3: Honestly, Section B.2 can be expanded further. I found the following statement vague in its current form: \"our algorithm framework is unable to deal with this kind of rectangular robust sets in the context of partial coverage data due to some technical problems in applying the partial coverage coefficient (Assumption 3.3) under this kind of robust sets.\"**\n\n**A3:** Thanks for your suggestion! We will make the statement clearer in our revision. In the following we briefly explain the technical problems we met. Intuitively, for $\\mathcal{S}$-rectangular RMDPs, it actually obeys another form of robust Bellman equation (RBE):\n\n$$\n   V_{h,P,\\boldsymbol{\\Phi}}^{\\pi}(s_h) = \\mathbb{E}_{a_h\\sim \\pi_h(\\cdot|s_h)}[R_h(s_h,a_h)] + \\inf\\_{\\widetilde{P}_h\\in\\boldsymbol{\\Phi} (P_h)} \\mathbb{E}\\_{a_h\\sim \\pi_h(\\cdot|s_h), s'\\sim \\widetilde{P}_h(\\cdot|s_h,a_h)}[V\\_{h+1,P,\\boldsymbol{\\Phi}}^{\\pi}(s')]\n$$\n\n($\\mathcal{S}\\times\\mathcal{A}$-rectangular RMDPs also satisfy this form of RBE, but $\\mathcal{S}$-rectangular RMDPs only satisfy this form of RBE). However, this form of RBE would not give the same suboptimality decomposition as we did by our proof techniques (Eqn. (D.8) in Appendix D), which is key to apply the robust partial coverage condition adopted by our paper (Assumption 3.3). Therefore, currently we are not sure of whether or not it is actually possible to include $\\mathcal{S}$-rectangular RMDPs to our theoretical framework. It is an interesting future work for us to figure this out.\n\n**References:**\n\n[1] Ma, Xiaoteng, et al. \"Distributionally robust offline reinforcement learning with linear function approximation.\" arXiv preprint arXiv:2209.06620 (2022).\n\n[2] Iyengar, Garud N. \"Robust dynamic programming.\" Mathematics of Operations Research 30.2 (2005): 257-280.\n\n[3] Laixi Shi and Yuejie Chi. Distributionally robust model-based offline reinforcement learning with near-optimal sample complexity. arXiv preprint arXiv:2208.05767, 2022."}, {"review_id": "cR73tjVTjX", "reviewer": "Reviewer_Ty5v", "summary": "This paper proposed a unified framework of Robust Markov Decision Process, which includes many newly proposed models as special cases. Under their generic framework, they proposed Doubly Pessimistic Model-based Policy Optimization (P^2MPO) that adopts a double pessimism principle for policy optimization. They showed that the suboptimality gap of the proposed algorithm can be upper bounded by the model estimation error and the robust partial coverage coefficient. They further provided concrete implementations of their algorithm on some specific models and showed that their algorithm enjoys a $n^{-1/2}$ convergence rate with $n$ being the number of trajectories in the offline dataset.", "questions": "- Why the robust partial coverage assumption (which considers all the possible transition kernels in a robust set) is much weaker than assuming the dataset covers the visitation distribution of any possible policy (under only the true transition kernel)? In other words, does the full-coverage-style assumption implies the partial-coverage-style assumption?\n- How does the rates obtained in Section 4 Corollary 4.1, 4.3 compare with the previous works?\n", "limitations": "See weaknesses", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- They proposed a generic framework that covers many models such as $\\mathcal{S}\\times\\mathcal{A}$-rectangular tabular RMDPs, $\\mathcal{S}\\times\\mathcal{A}$-rectangular kernel RMDPs, $\\mathcal{S}\\times\\mathcal{A}$-rectangular neural RMDPs, $\\mathcal{S}\\times\\mathcal{A}$-rectangular factored RMDPs.\n- Instead of covering the visitation distribution of any policy, they only require a partial coverage style assumption, i.e., the dataset covers the visitation distribution of the optimal policy in a robust fashion.\n", "weaknesses": "- Computationally inefficient, i.e., not sure how to solve (4.1), (4.2) and (3.2) efficiently.\n- Though the authors showed how the model estimation step is implemented on some specific models, it is not clear how to implement the model estimation step that satisfies Condition 3.1 and Condition 3.2 in general.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Response to Reviewer Ty5v**\n\nThanks very much for your appreciation of our work!  In the following, we will try our best to address all your concerns and questions.\n\n**Q1: The algorithm is computationally inefficient, i.e., not sure how to solve (4.1), (4.2) and (3.2) efficiently.**\n\n**A1:** We clarify that our work focuses on the statistical side of robust offline RL under general function approximations, which remains an important open problem. Our algorithm is therefore information-theoretic and is indeed intractable with an abstract function approximation class. The objective we designed is to achieve statistical efficiency in the most general setup. Computational efficiency is not our focus.\n\nMeanwhile, if we specify the model space, for example, tabular case or linear/kernel function classes, we can design approximations of our doubly pessimistic algorithm. For example in tabular RMDPs, we can replace the iterative infimum in our double pessimism objective (3.2) by an LCB-style bonus. This has been shown to be efficient both theoretically and experimentally by [1], which can demonstrate the efficiency and practicality of our general algorithm design. \n\n**Q2: Though the authors showed how the model estimation step is implemented on some specific models, it is not clear how to implement the model estimation step that satisfies Condition 3.1 and Condition 3.2 in general.**\n\n**A2:** Conditions 3.1 and 3.2 involved in our unified theory are guidelines for customizing the model estimation subroutine for different RMDP examples, which shows the flexibility of our algorithm and theory. Actually, different RMDP examples have different structures. By tailoring the model estimation step for specific RMDP examples, one can utilize their structures to the best and obtain better sample efficiency.\n\nFor example, for $\\mathcal{S}\\times\\mathcal{A}$-rectangular robust factored MDP (Example 2.9) with finite states and actions, our proposed model estimation subroutine (Section 4.2) enjoys better sample efficiency than naively applying the model estimation step designed for general $\\mathcal{S}\\times\\mathcal{A}$-rectangular robust tabular MDPs (Example 2.5 in Section 4.1). This is also the case for $d$-rectangular robust linear MDPs (Appendix B). \n\nIn general, an RMDP instance could have a very complicated and detailed structure. Designing an once-for-all model estimation subroutine would lose certain information which may help to boost the sample-efficiency. Therefore, implementing the model estimation step that satisfies Conditions 3.1 and 3.2 in general is not our focus.\n\n\n\n**Q3: Why the robust partial coverage assumption (which considers all the possible transition kernels in a robust set) is much weaker than assuming the dataset covers the visitation distribution of any possible policy (under only the true transition kernel)? In other words, does the full-coverage-style assumption implies the partial-coverage-style assumption?**\n\n**A3:** Thanks for pointing that out! We clarify this point in the following. \n\nIn our paper (Line 262 to 264) we mentioned two types of coverage condition: (i) the distribution of the data is uniformly lower bounded; (ii) covering the visitation distribution of any $\\pi\\in\\Pi$. It seems that we did not elaborate under what transition kernels (ii) holds. By (ii), we meant to refer to the robust-full-coverage-style assumption which holds for all $\\pi\\in\\Pi$ and $P\\in\\boldsymbol{\\Phi}(P^{\\star})$, parallel to our robust-partial-coverage-style assumption in terms of transition kernels. When considering the full-coverage-style assumption you mentioned, it is important to note that a direct implication between it and our robust-partial-coverage-style assumption cannot be established. However, as is shown by an information-theoretical lower bound by [1] for the tabular RMDP case, the robust-partial-coverage-style assumption is the \"minimal\" assumption on the offline data to some extent.\n\nMeanwhile, we remark that all previous full-coverage-style offline setup papers use (i) as their data assumption. Since (i) requires that the distribution of the state-action pairs are uniformly lower bounded, this kind of full-coverage assumption is definitely much stronger than our robust partial coverage assumption.\n\n\n**Q4: How does the rates obtained in Section 4 Corollary 4.1 & 4.3 compare with the previous works?**\n\n**A4:** We have compared our results in Corrolary 4.1 with existing work [1] in Remark 4.2. Regarding our results for robust factored MDPs in Corollary 4.3, their is no existing work to compare with. This novel model is proposed by our work, and our algorithm stands as the first efficient algorithm designed for this problem.\n\n**References:** \n\n[1] Shi, Laixi, and Yuejie Chi. \"Distributionally robust model-based offline reinforcement learning with near-optimal sample complexity.\" arXiv preprint arXiv:2208.05767 (2022)."}]

Author rebuttal:

Meta-review: This paper explores the realm of distributionally robust offline reinforcement learning by introducing a concept termed 'double pessimism', and a generic algorithmic framework. Notably, the paper is well-articulated, with a clear presentation and substantial theoretical contributions. 

Following in-depth discussion among reviewers and authors, the majority have recommended acceptance of this paper, a view with which I agree. The authors are encouraged to integrate all points raised during the rebuttal phase into the final version of their manuscript.

Lastly, congratulations on this well-accomplished piece of work!
Decision: Accept (poster)