Minimax Optimal and Computationally Efficient Algorithms for Distributionally Robust Offline Reinforcement Learning
Authors: Zhishuai Liu
Pan Xu
Venue: NeurIPS 2024 poster (2024)
Keywords: offline reinforcement learning
distributionally robust Markov decision processes
function approximation
Primary area: reinforcement_learning
TL;DR: This paper studies instance dependent upper and lower bounds under the setting of offline linear DRMDPs.

Abstract: Distributionally robust offline reinforcement learning (RL), which seeks robust policy training against environment perturbation by modeling dynamics uncertainty, calls for function approximations when facing large state-action spaces. However, the consideration of dynamics uncertainty introduces essential nonlinearity and computational burden, posing unique challenges for analyzing and practically employing function approximation. Focusing on a basic setting where the nominal model and perturbed models are linearly parameterized, we propose minimax optimal and computationally efficient algorithms realizing function approximation and initiate the study on instance-dependent suboptimality analysis in the context of robust offline RL. Our results uncover that function approximation in robust offline RL is essentially distinct from and probably harder than that in standard offline RL. Our algorithms and theoretical results crucially depend on a novel function approximation mechanism incorporating variance information, a new procedure of suboptimality and estimation uncertainty decomposition, a quantification of the robust value function shrinkage, and a meticulously designed family of hard instances, which might be of independent interest.

Minimax Optimal and Computationally Efficient Algorithms for Distributionally Robust Offline Reinforcement Learning
Zhishuai Liu
Pan Xu Duke University pan www.xuuduukee.m edu
Duke University zhishuai. wwwluuukeee.... edu
Abstract
Distributionally robust offline reinforcement learning (RL), which seeks robust policy training against environment perturbation by modeling dynamics uncertainty, calls for function approximations when facing large state-action spaces. However, the consideration of dynamics uncertainty introduces essential nonlinearity and computational burden, posing unique challenges for analyzing and practically employing function approximation. Focusing on a basic setting where the nominal model and perturbed models are linearly parameterized, we propose minimax optimal and computationally efficient algorithms realizing function approximation and initiate the study on instance-deper dependded suboptimality analysis in the context of robust offline RL. Our results uncover that function approximation in robust offline RL is essentially distinct from and probably harder than that in standard offline RL. Our algorithms and theoretical results crucially depend on novel function approximation mechanism incorporating variance information, a new procedure of suboptimality and estimation uncertainty decomposition, quantification of the robust value function shrinkage, and a meticulously designed family of hard instances, which might be of independent interest.
Introduction
Offline reinforcement learning (RL) [17, 18), which aims to learn an optimal policy achieving maximum expected cumulative reward from a pre-collected dataset, plays an important role critical domains where online exploration is infeasible due to high cost or ethical issues, such as precision medicine [49, 11, 22, 21] and autonomous driving [32, 433. The foundational assumption of offline RL [18, 15, 53] is that the offline dataset is collected from the same environment where learned policies are intended be deployed. However, this assumption can be violated in practice due to temporal changes in dynamics. In such cases, standard offline RL could face catastrophic failures [10, 31, 64]. To address this issue, the robust offline RL [28, 30] focuses on robust policy training against the environment perturbation, which serves as promising solution. Existing empirical successes of robust offline RL rely heavily on expressive function approximations [37, 36, 25, 45, 63, 16), as the omnipresence of applications featuring large state and action spaces necessitates powerful function representations to enhance generalization capability of decision decision-making in RL.
To theoretically understand robust offline RL with function approximation, the distributionally robust Markov decision process (DRMDP) [39, 30, 13] provides an established framework. In stark contrast to the standard MDP, DRMDP specifically tackles the model uncertainty by forming an uncertainty set around the nominal model, and takes a max-min formulation aiming to maximize the value function corresponding
policy, uniformly across all perturbed models in the uncertainty set [55, 52, 57, 35, 41, 59, 40]. The core of DRMDPs lies in achieving an amenable combination of uncertainty set design and corresponding techniques to solve the inner optimization over the
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

uncertainty set. However, this consideration of model uncertainty introduces fundamental challenges to function approximation in terms of computational and statistical efficiency, particularly given the need to maximally exploit essential information in the offline dataset. For instance, in cases where the state and action spaces are large, the commonly used (s, recttanggll uncertainty set can make the inner optimization computationally intractable for function approximation [66]. Additionally, the distribution shifts, arising from the mismatch between the behavior policy and the target policy, as well as the mismatch between the nominal model and perturbed models, complicate the statistical analysis 44. Several recent works attempt to conquer these challenges. Panaganti et al. [35] studied the (s, re-trttangullrrtty and their algorithm may suffer from the above mentioned computational issue. Additionally, the (s, a) -rectanggla uncertainty set may contain transitions that would never happen in reality, and thus leads to conservative policies; Blanchet et al. [4] proposed novel double pessimism principle, while their algorithm requires strong oracles, which is not practically implementable. Meanwhile, line of works study function approximation in the online setting [44, 38, 51, 3, 20] or with a simulator [66], which are not applicable to offline RI. Thus, the following question arises:
Is it possible to design computationally efficient and minimax optimal algorithm for robust offline RL with function approximation?
To answer the above question, focus a basic setting of d-rectangular linear DRMDP, where the nominal model is a standard linear MDP, and all perturbed models are parameterized in a linearly structured uncertainty set. We provide the first destadne-dependent suboptimality analysis in the DRMDP literature with function approximation, which offers insights into the problem's 's intrinsic characteristics and challenges. Concretely, our contributions are summarized follows.
We propose a computationally efficient algorithm. Distributionally Robust Pessimistic Value Iteration (DRPVI), based on the pessimism principle [15, 53, 41] with new function approximation mechanism explicitly devised for d-rectangular linear DRMDPs. We show that DRPVI achieves the following instance-dependent upper bound the suboptimality gap:
31 (Po) Σ ET P [[E: [|oc(sn, on) (n)1: = =]]
This bound resembles those established in offline RL within standard linear MDPs [15, 62, 54]. However, there are two significant differences in our results. First, our bound depends on the supremum over the uncertainty set of transition kernels instead of one single transition kernel. Second, our result relies on a diagonal-baut based normalization, instead of the Mahalanobis norm of the feature vector, [|(s), ax)] A See Table for clearer comparison. These two distinctions are unique to DRMDPs with function approximation, which discuss in more details in Section 4. Moreover, our analysis provides a novel pipeline for studying instance-dependen upper bounds of computationally efficient algorithms under d-rectangular linear DRMDPs.
We improve DRPVI by incorporating variance information into the new function approximation mechanism, resulting in the VA-DRPVI algorithm, which achieves smaller upper bound:
B2 PuP ΣH E
[E (1) an) 11 mn 181 = =]2
This improves the result of DRPVI due to the fact that Σ < H by definition [60, 54]. Furthermore, when the uncertainty level p O(1), show that the robust value function attains a Range Shrinkage property, leading to an improvement in the upper bound by an order of H. This explicit improvement is new in variance- algorithms, and is unique to DRMDPs.
We further establish an information-theon VA-DRPVI matches the cooommttion-theorettt lower bound up to 32, which implies that VA-DRPVI is npar-optimal in the sense of information theory. Importantly, both DRPVI and VA-DRPVI are computationally efficient and do not suffer from the high computational burden, discussed above in settings with the (x, d)-rectangular uncertainty set, due to a decoupling property of the d-rectangular uncertainty set (see Remark 4.1 for more details). Thus, we confirm that, for robust offline RI. with function approximation, both the computational efficiency and minimax optimality are achievable under the setting of d-rectangular linear DRMDPs.
lower bound. We prove that the upper bound of
'eere, is the feature dimension, H is the horizon length, 81 = Õ(VāH) is a tunning parameter in DRPVI, ue (P'))) is the uncertainty set with radius p. x' is the optimal robust policy, <(...) S A + Rd is the instance-dependent feature vector, and As, is the covariance matrix defined in (4.3). 32 O(Vd) is hyperparameter in VA-DRPVE Vf, is the variance- variance-weighted covariance matrix, see (5.5).

---

Table 1: Summary of instance-dependent results in offline RL with linear function approximation. An and Σ are the empirical covariance matrix defined in (4.3) and (5.5) respectively. Note that '¹ means the optimal policy in standard MDPs and the optimal robust policy in DRMDPs. The definition of Σ also depends on the corresponding definition of π²
Algorithm
Setting
Instance-dependent upper bound on the suboptimality gap
PEVT [15]
MDP
dH E E" P [[]((s, an Al, 2, 1/1
LinPEVI-ADV
MDP
VdH. H B=" PP [ an - = s]
[54]
LinPEVI-ADV+ [54]
MDP
Vd. > 21=1 Bxd [[ an =-13-111 =
DRPVI (ours)
DRMDP
VdH PEPP Σ B Ei= (1 an)))n))lll )1 A.1l Σn
VA-DRPVI (ours)
DRMDP
Vd su-suppr))(po)
B
P
Σ I1 an) 1ell 211 1/81 =
Our algorithm design and theoretical analysis draw inspiration from two erucial ideas proposed in standard linear MDPs: the reference-advantal decomposition [54] and the warihnce-weighted ridge regression [65]. However, the unique challenges in DRMDPs necessitate novel treatments that go far beyond a combination of existing techniques. Specifically, existing analysis of standard linear MDPs highly relies on the linear dependency of the Bellman equation on the (nominal) transition kernel. This linear dependency is disrupted by the consideration of model uncertainty, which induces essential nonlinearity that significantly complicates the statistical analysis of estimation error. To obtain our instance-depender upper bounds, we establish a new theoretical analysis pipeline. This pipeline starts with a nontrivial decomposition of the suboptimality, and employs a new uncertainty decomposition that transforms the estimation uncertainty over all perturbed models to estimation uncertainty under the nominal model.
The iiformationnthhorett lower bound in our paper is the first of its kind in the linear DRMDP setting, which could be of independent interest to the community. Previous lower bounds, which are based on the commonly used Assouad's 's method and established under the standard linear MDP, do not consider model uncertainty. In particular, one prerequisite for applying Assouad's s method is switching the initial minimax objective to minimax risk in terms of Hamming distance. The intertwining of this prerequisite with the nonlinearity induced by the model uncertainty makes the analysis significantly more challenging. To this end, construct a novel family of hard instances, carefully designed to (1) mitigate the nonlinearity caused by the model uncertainty, (2) fulfil the prerequisite for Assouad's method, and (3) be concise enough to admit matrix analysis.
Notations: We denote A(S) as the set of probability measures over some set S. For any num- ber E Z.,, we denote [H] as the set of
For any function V + R, we denote [Px, (ss,a) = B. [V(')] as the expectation of V with respect to the transition kernel Pt. (s) max(1, [Var, as) as the truncated variance of V. and [V())]a = min(V(s), (s),, a. given a scalar 0, the truncated value of V. For vector æ. we denote x, as its j-th entry. And we denote [α)]ve[d]] as a vector with the i-th entry being F4. For a matrix A, denote (A)) as the i-th eigenvalue of A. For two matrices A and B, we denote A < B as the fact that B A is positive semidefinite matrix. For any function ʃ S + R, we denote || = sup (s). Given P. Q E A(S), the total variation divergence of P and Q is defined as D(PIIQ) = 1/2 Is Ps)) Q(s)(ds.
[P,, 13,, a) (IF,, V[ss, a²)² as the variance of V. (ss,
2 Most Related Work
DRMDPs. The DRMDP framework has been extensively studied under different settings. The works of [55, 52, 61, 26, 12] assumed precise knowledge of the environment and formulated the DRMDP as classic planning problems. The works of [67, 57. 33, 56, 42, 58] assumed access to a generative model and studied the sample complexities of DRMDPs. The works of [35, 41, 4] studied the offline setting assuming access to only an offline dataset, and established sample complexities under data coverage or concentrability assumptions. The works of [51, 3, 8, 19, 20 studied the online setting where the agent can actively interact with the nominal environment to learn the robust policy.
3

---

DRMDPs with linear function approximation. Tamar et al. [44], Badrinath and Kalathil [3] proposed to use linear function approximation to solve DRMDPs with large state and action spaces and established asymptotic convergence guarantees. Zhou et al. [66] studied the natural Actor- Critic with function approximation, assuming access to a simulator. Their function approximation mechanisms depend on two novel uncertainty sets, one based on double sampling and the other on an integral probability metric. Ma et al. [24] first combined the linear MDP with the d-rectangular uncertainty set [12], and proposed the setting dubbed as the d-rectangular linear DRMDP, which naturally admits linear representations of the robust Q-functions', Panaganti et al. [34] leverages the d-rectangular linear DRMDP framework to address the distribution shift problem in offline linear MDPs. Blanchet et al. [4] studied the offline d-rectangular linear DRMDP setting, for which the provable efficiency is established under double pessimism principle. Liu and Xu [20] then studied the online d-rectangular linear DRMDP setting and pointed out that the intrinsic nonlinearity of DRMDPs might pose additional challenges for linear function approximation. After the release of our work, a concurrent study [48] emerged, which independently investigated offline DRMDPs with linear function approximation. Their algorithms attained the same mnstance-dependee suboptimalities as proposed algorithms DRPVI and VA-DRPVI. Their algorithm DROP also achieved the same order of worst-case suboptimality, (VdHK//KK. as our DRPVI. However, we further demonstrated that our algorithm VA-DRPVI can strictly improve this result to Ö(dH min H H// introduced novel hard instance and established the first information -tteoretccc lower bound for offline DRMDPs with linear function approximation. We also note that there is line of works [4, 35] studied general function approximation under DRMDPs with the commonly studied (s, a) r)eectnngull uncertainty sets, where no further structure is applied except the rectangularity.
\/VK). Moreover, we
3 Problem Formulation
In this section, we provide the preliminary of d-rectangular linear DRMDPs, and describe the dataset as well as the learning goal in offline reinforcement learning.
Standard MDPs. We start with the standard MDP, which constitutes the basic of DRMDPs. A finite horizon Markov decision process is denoted by MDP H. P.r). where S and A are the state and action spaces, H Z+ is the horizon length, P (Pr) denotes the set of probability transition kernels, r {r denotes the reward functions. More specifically, for any (h, s, a) E [H] x S x A, the transition kernel (-s., a) is a probability function over the state space S, and the reward function гą S A + [0, 1] is assumed to be deterministic for simplicity. A sequence of deterministic policies is denoted as π = { Ah- where TA : :S + A is the policy for step h E [H]. Given any policy π and transition P, for all (s, a, h) E S x A x [H].
H
the corresponding value function V/ PxT.(()) (s) = E..P E (st,, az) |hh = s] and Q-function (s,a)= ? starting from step h, and both of them are bounded in [0, H).
Px.P EEEn (e("e; 41){s) 8, an = a] characterize the expected cumulative rewards
Distributionally robust MDPs. A finite horizon distributionally robust Markov decision process denoted by DRMDP(S,A, A, H, (P")), where po = (P is the set of nominal transition kernels, and (PO) 2NE (P)) is the uncertainty set of transitions, where each Ug (PP) is usually defined as ball centered at p0 with radius/uncertainty level p 2 0 based on some probability divergence measures [13, 57, 56]. To account for the model uncertainty, the robust value function ViT (TT = inf peue Vi P (s), v(h,s) s) E [H] x S is defined as the value function under the worst possible transition kernel within the uncertainty set (P').. Similarly, the robust Q-function is defined as QT.'(s, a)- = inf pp) Q7," (s, a), for any (h, s, a) E [H] x S x A. Further, we define the optimal robust value function and the optimal robust Q-function
(s) Supxem (s),,)),
(s, sup (s, v(h,s,a) E [H] S A.
$ "Ma al. [24] study the offline d-rectangular linear DRMDPs with Kullback-Leibler (KL) uncertainty sets. We remark that 1) the proofs of their main lemmas (Lemma D.I and Lemma D.2) related to suboptimality decomposition and the proof of theorems have technique flaws; 2) The formulation of their assumption 4.4 on the dual variable of the dual formulation of the KL-divergene is ambiguous and may be too strong to be realistic. Thus, the fundamental challenges of d-rectangular linear DRMDPs remain unresolved.

---

where II is the set of all policies. The optimal robust policy x² = { { is defined as the policy that achieves the optimal robust value function: x, (s) arg supxen V (s), A(h, s) E [H] S.
d-rectangular linear DRMDPs. A d-rectangular linear DRMDP is a DRMDP where the nominal environment a special case of linear MDP with a simplex feature space [14, Example 2.2] and the uncertainty set 24, (P%) is defined based on the linear structure of the nominal transition kernel Po. In particular, we make the following assumption about the nominal environment.
(s(s,a) 2 0, for any (i, a) [d] x S x A. For any (h, 8,a) E [H] 1= (2(8, a) = reward function and the nominal transition kernels have a linear representation: r = (Ø(s, a), 0x), and (- a) = (ø(s, a), (-),,,), where |00112 S vd, and ph = 1 ..... (ha are unknown probability measures over S.
Assumption 3.1. Let Φ SSA + Rd be state-action feature mapping such that >d
S A. the
With notations in Assumption 3.1, define the factor uncertainty sets Ug, {a: uu
(SS), D(ullp())) S p) v(,, E [H] x [d], where D(-II-) is specified as the total variation (TV) divergence in this work. The uncertainty set is defined as Uf = 2 (ssa))SxxA Uf az p.)) where Uff. (*)) - (5 a))nn:()) mh,(()) E Uf,,, (r Vi E [d]]. A notable feature of H.d ( are decoupled from the state-action pair (s, a) and also independent with each other. As demonstrated later, this decoupling property results in a computationally efficient regime for function approximation.
this design is that the factor uncertainty sets (1
Robust Bellman equation. Under the setting of d-rectangular linear DRMDPs, it is proved that the robust value function and the robust Q-function satisfy the robust Bellman equations [20]:
(s, a) = =r(ss a) + inf
Ps. (1 [F V (s),
(3.la)
V/ (s) E (- 10% (s, a))
(3.1b)
and the optimal robust policy xt is deterministic. Thus, we can restrict the policy class II to the deterministic one. This leads to the robust Bellman optimality equations:
( a) = r a) + inf Pa PP (s) A
(3.2a)
(3.2b)
Offline Dataset and the Learning Goal. Let D denote offline dataset consisting of K i.i.d trajectories generated from the nominal environment MDP(S, A, H,
PD r) by a behavior policy
n = (m [=) In concrete, for each т E [K], the trajectory {(ST, 0% r.) <)=)> satisfies that a n (11s% ). T% (s], a.)); and s4+1
(-1s% ax)) for any h [M]. The goal of the
robust offline RL is to learn the optimal robust policy n² using the offline dataset D. We define the suboptimality gap between any policy गे and the optimal robust policy x as
SubOpt(#t ft, $1, P1 == V1 (s1) V (81).
(3.3)
Then the goal of an algorithm in distributionally robust offline reinforcement learning is to learn robust policy & that minimizes the suboptimality gap SubOpt(f. 8, p), for any s E S.
4
Warmup: Robust Pessimistic Value Iteration
In this section, we first propose a simple algorithm in Algorithm 1 as a warm start, and provide an irtance-dependen upper bound on its suboptimality gap in Theorem 4.4.
The optimal robust Bellman equation (3.2) implies that the optimal robust policy x" is greedy with respect to the optimal robust Q-function. Therefore, it suffices estimate Q"," approximate n². To this end, we estimate the optimal robust Q-function by iteratively performing an empirical version of the optimal robust Bellman equation similar to (3.2). In concrete, given the estimators step h+ denoted by Qn-1(e (s, a) and (s) max.E Q (s, a), Liu and Xu [20] show that applying one step backward induction similar to (3.2) leads to
Qn(s.a) a) (s, a) + inf P. (1..)) [PA V Vn+1 (s, a) (b(s, On + +vf)
(4.1)
5

---

(2n where uhi == [ (=),((a) - p(a- ming (VannVV (s)))))))a) =n,(a) = B [V)+1(6)))
vi E [d], (s)1(s')la = min (V and a is a dual variable stemming from the dual formulation (see Proposition H.1). To estimate (s, a), it suffices to estimate vectors ()((a)= (a).,(a)...... (a)) and v as follows.
Estimate nn (a)): note that [PA[V=+1la[(ss0 a) - (Ø(s, a), zn(a)) by Assumption 3.1, where the expectation is taken with respect to the nominal kernel (-ls, a). Given the estimator Va+1 (s), it is natural to estimate Zn (a) by solving the following ridge regression on the offline dataset D.
t (a) argmingER*
Σ (( 0% x) *1=111
K A
[ r=
(4.2)
where 0, 67 is a shorthand notation for (68,, :. af), and A₁ is the covariance matrix:
K Σイ= An
())) AL.
(4.3)
Estimate Df: based on (a), we can estimate 1g1 as follows.
ph = max (a) p(a min, (V (s')), E [d].
(4.4)
After these two steps, we immediately obtain the estimated robust Q-function at step h,
(s, (Ø(s, a). 0₁ +
(4.5)
Note that these estimations are constructed based on an offline dataset D, which is known to cause distributional shift. We propose incorporate a penalty term the estimator (4.5) following the pessimism principle in the face of uncertainty [15, 53, 41].
Algorithm Distributionally Robust Pessimistic Value Iteration (DRPVI)
Require: Input dataset 'D and parameter 31; (++ 0.
1: for H.... ... do
2: Ag - Σx= 0 + AI
3:
for : . do
4:
Update ih; according to (4.4) end for
5:
6:
Ta(:,) < 31 Σ Di= |.6 )1, A5¹
7: (g(())) + (o(:.)) (0, + 1))) - (I)(.:)) [0,1-
8: (.1.) + argmax,, ())())).mm)) (n(1))) and V.(.) (,
9:
end for
Remark 4.1. In Algorithm 1, the pessimism is achieved by subtracting a robust penalty term, Ei= [):(1 A, from the robust Q-function estimation, which is derived from bounding the robust estimation uncertainty arising from d ridge regressions. In particular, step E [H). denoting af = argmax (a) - p(a min,' [VP h+ (s')].)} Vi E [d], we solve d separate ridge regressions to obtain different coordinates of D This design is tailored for the d-rectangular linear DRMDP, as we will see, leading to a distinct -eeendee upper bound in Theorem 4.4.
[0, H] in (4.4), one will repeatedly invoke the closed form solution (4.2) for different values of a. Moreover, the optimization decoupled from the state-action pair, due the decoupling property of d-rectangular uncertainty set. Similar algorithm designs have also appeared in [24] for Kullback- linear DRMDPs and [20] for online linear DRMDPs. As for the computational tractability, we note that the minimization over a in (4.4) has been implemented in [20] using the minimize function method [29] in the Python module scipy.optimize. The minimization over the state space is avoided under a 'fail-state' assumption, common in applications such as robotics and healthcare (see Assumption and Remark 4.2 in their paper). Without this assumption, we can also use the Nelder-Mead method to solve it. Thus, Algorithm is in general computationally tractable.
Remark 4.2. Notably, solve the optimization problem with respect
divergence based
the Nelder-

---

Before presenting the theoretical guarantee of DRPVI, we make the following data coverage assump- tion, which is standard for offline linear MDPs [50, 9, 60, 54].
Assumption 4.3. We assume x := min W) Amin (E=". (0(s,, an) an) 0 for the behavior policy x² and the nominal transition kernel p"
Assumption 4.3 requires the behavior policy to sufficiently explore the state-action space under the nominal environment. Indeed, it implicitly assumes that the nominal and perturbed environments share the same state-action space, and that the full information of this space is accessible through the nominal environment and the behavior policy T². Assumption 4.3 rules out cases where new states emerge in perturbed environments that can never be queried under the nominal environment as a result of the distribution shift. Now we present the theoretical guarantee for Algorithm 1.
Theorem 4.4. Under Assumptions 3.1 and 4.3, AK > max log (2dH22 /6)/ 20449e /x]
and 6 E (0, 1), if we set À = and A3 = Ó(VZH) in Algorithm 1, then with probability at least 1 6, vss E S, the suboptimality of DRPVI satisfies
Sub S 31
sup PELL((PP) h=1
Σ
E P
Σ Iolssh an an)1: = (4.6)
where A, is the empirical covariance matrix defined in (4.3).
The result Theorem 4.4 resembles existing instance-dependent bounds for standard linear MDPs [15, 54] (see Table I for a detailed comparison). However, there are two major distinctions between these results. First, our result depends on the weighted sum of diagonal elements Σi= (1 ax) (,))1ll A dubbed as the d-rectangular robust estimation error, instead of the Mahalanobis norm of the feature vector || ($),, a;) an)ll A,;" As discussed in Remark 4.1, this term primarily arises due to the necessity to solve d distinct ridge regressions in each step, which presents a unique challenge in our analysis. Second, we consider the supremum expectation of d-rectangular robust estimation error with respect to all transition kernels in the uncertainty set, which measures the worst case coverage of the covariance matrix As under the optimal robust policy x².
To connect with existing literature [4], we further show that under Assumption 4.3, the instance- dependent suboptimality bound can be simplified as follows.
Corollary 4.5. Under the same assumptions and settings as Theorem 4.4, with probability at least
1-8. 8, for all E S, the suboptimality of DRPVI satisfies SubOpt ft, p) Ö(V(H² /(Vn: K))- Remark 4.6. Since [ 1l1 I 1 by Assumption 3.1, the coverage parameter e is trivially upper bounded by 1/d. Assuming that x = ct /d for a constant < cl 1, then we have SubOpt(f, = O(dH² /(ct VK)). This bound improves the ofte-oof-the-art [4, Theorem 6.3], by O(d).
Distributionally Robust Variance-Aware Pessimistic Value Iteration
The instance- dependend bound in Theorem 4.4 has explicit dependency H. which arises from the fact that Qf (s. a) E [o, H] for any (h, p) E [H] x (0, 1] and the Hoeffding-ty self normalizee concentration inequality used in our analysis. We will show in this section that the range of any robust value function could be much smaller under a refined analysis. Consequently, we can leverage variance information improve Algorithm 1 and achieve strengthened upper bound.
Intuition In the robust Bellman equation (3.1), the worst-case transition kernel would put as much mass possible the minimizer of V (s), denoted by smin. Based on this observation, conjecture that the robust Bellman equation (3.1) recursively reduces the maximal value of robust value functions, and thus shrinks its range. To see this, we define Ph. (1 - p)p + pm where Spmi. is the Dirac measure smin and we assume V (Smin) = 0 for any (H, E 11 x [W] just for illustration. It easy to verify that Pn,s E (Kf,, and indeed the worst-case factor kernel. Then by (3.1) we have V (s) = Ea-z (s, a) (1-p) PP P a)], which immediately implies p) max h42 (8'). This justifies our conjecture that the range of the robust value functions shrinks over stage. We dub this phenomenon as Range Shrinkage and summarize it in the following lemma, with more formal proof postponed to Appendix G.5.
max.s (s) < 1
7

---

Algorithm 2 Distributionally Robust and Variance Aware Pessimistic Value Iteration (VA-DRPVI)
Require: Input dataset D, D' and 82; V ++)+
1: Run Algorithm 1 using dataset DD' to get (V/
(V/hhe[[ ]NE(H]
2: for h = H,... do
3: Construct variance estimator ( using D' by (5.2) and (5.3)
4: Ex(a) Σデ= 0 ( +
5:
(a) Mn (a)
K 0% (8
6:
aE (a) p(a min, (V (8')la)) Vi E [d]
7:
ph = (a;) - p(a; - min. |/ (d')aa)) ViE E [d]
8:
(n(:,) -) < 32 Ei= | [
9:
(R(;)) -(b(:)) (0, + 0/2) - (a(--))o,HH-4t)
10:
th (-1.) f argmax,, An (2(())), m1 p2( + (,
11: end for
Lemma 5.1 (Range Shrinkage). For any (p, h) E (0, 1] 11 x [H]. we have
max (s) min h (s) - 1- - (1 p) -+1
(5.1)
SES
P
This phenomenon only appears in DRMDPs since the range of value function generally [0, H) in standard MDPs. A similar phenomenon is first observed in infinite horizon tabular DRMDPs [42, Lemma 7]. One important implication of Lemma 5.1 is that the conditional variance of any value function shrinks accordingly. In particular, when p O(1,, the range of any robust value function would shrink to constant order, which leads to constant order conditional variances. This motivates us to leverage the variance information in both algorithm design and theoretical analysis. Inspired by the crriance-weighter ridge regression in standard linear MDPs [65, 27, 60, 54], we propose to improve the vanilla ridge regression in (4.2) by incorporating variance weights. To this end, first propose an appropriate variance estimator, whose form is specifically motivated by our theoretical analysis framework, quantify the variance information.
Variance estimation We first run Algorithm I using an offline dataset D' that is independent of D to obtain estimators of the optimal robust value functions (V"")e[ By Assumption 3. the variance of 17/4 under the nominal enviromment is [Vary, [V, h+ [a) a) = | (FF V 1 (asss, a))² = (ø(s. a), 21 - (10(s, =1.))) We estimate Zh.1 and 21,2 via ridge
regression similarly as (4.2):
(a) = argmin ZER Σ
h+1 (8 (s4++) (1 17 2)² + x| 12
T))²
(5.2a)
2 (a) = argmin ZERd Σ (1 1+1 (8)+ t7 x)² + >| 1
(5.2b)
We then construct the following truncated variance estimator
as) = max L, [d(ssa) a) 2n.) ,, [Ø(s,a) 2n, (a)) j. - 0 dHF
(5.3)
VKK
where the last term is penalty to achieve pessimistic estimations of conditional variances.
Variance-Aware Function Approximation Mechanism Similar to the two-step estimation proce- dure of Algorithm first estimate (a) by the following variance- weighttd ridge regression under the nominal enviroument:
([V (5h+1)) 2 2)² + >||=
(n(a) = argmin
=ERd
(a)
(5.4)
8

---

where (a)a== -== Σ / ( a):a) + AI is the empirical variance-weighted covariance matrix, which can be deemed as an estimator of the following variance- weiigttd covariance matrix
Σx = 0 / W. (%) + AI.
(5.5)
In the second step, we estimate 1/,30 Vi E [d] in the same way as (4.4), We then add a pessimism penalty based on (a). We present the full algorithm details in Algorithm 2.
Theorem 5.2. Under Assumptions 3.1 and 4.3, for K > max( Ho /x), ((H*/K)))) and (0, 1), if set 1/11² and 32 = Ö(vd) d) in Algorithm then with probability at least the suboptimality of VA-DRPVI satisfies
H Σ
d EE PP
SubOpt f. 8, S B2
sup PEUP(P))
Σ (1, an [n)11,12;;,111111111
= 8).
(5.6)
where ΣS is the population variance-weighted covariance matrix defined as in (5.5).
Note that the bound in Theorem 5.2 does explicitly depend H anymore compared with that in Theorem 4.4. A naive observation is that (Va VA++1 (s, a) E [1, H&). By comparing the definitions in (4.3) and (5.5), have Σ H A,," Thus the upper bound of Algorithm 2 is never worse than that of Algorithm 1. This improvement brought by variance information is similar to that standard linear MDPs [54, Theorem 2]. However, thanks to the range shrinkage phenomenon, show that VA-DRPVI is strictly better than DRPVI when the uncertainty level is of constant order.
further
Corollary 5.3. Under the same assumptions and settings as Theorem 5.2, given the uncertainty level we have with probability at least 1 - 6, for all E S, the suboptimality of VA-DRPVI satisfies
(PO) SubOpt R, s) S B2 (1- -))
H
sup
E
|1o: 04 11)1111a,, 1s1
P
PELL
h=
Remark 5.4. Note that (1 (1-11p)pp (1-(1-p))/p== (min H)). When p O(1,, the suboptimality of Algorithm is strictly smaller than that of Algorithm by H. With a similar argument as in Remark 4.6, if we assume there exist constant < ct < 1, such that ct cl/d in Assumption 4.3, then the instance-dependent upper bound can be simplified Ö(dH min (1/p, H)HH vK)). which improves the state-of-the-arr [4, Theorem 6.3] by O(dH) when p = O(1).
6 Information-Theoree Lower Bound
For matrix E Raxd and a state s E S, we define function .)(.)) Rdxd x - as follows.
H
((A,)) = sup (EU
Σ
E
Σ (s an 1 =
(6.1)
h=1
It can be seen our upper bounds in previous sections primarily depend on quantities such as $(A,, s) and 4 (0 s). Roughly speaking, these quantities characterize the discrepancy between the (weighted) covariance matrix of the offline dataset and the state action pairs generated from the transition probability in the uncertainty set. Hence we call ((--)) the uncertainty function.
We now establish an information informationnthhorrtiic lower bound to show that the uncertainty function is unavoidable for d-rectangular linear DRMDPs. Let M be class of DRMDPs and we define SubOpt(M, R, s, p) as the suboptimality gap specific one DRMDP instance M E MM.
Theorem 6.1. Given uncertainty level E (0. 3/4] dimension d, horizon length H and sample size K Ó(d),, there exists class of d-rectangular linear DRMDPs M and an offline dataset D of size K such that for all s E S, with probability at least 1 - 8, inf SuPMEM SubOpt( M, म. s. 2 c- 4 2 - s), where is universal constant.
Theorem 6.1 shows that the uncertainty function & (<En11,0 8) is intrinsic to the information-theoree lower bound, and thus is inevitable. It is noteworthy that the lower bound Theorem 6.1 aligns with the upper bound in Theorem 5.2 up to factor of B2, which implics that VA-DRPVI is minimax

---

optimal in the sense of information theory, but with a small gap of Ö(vd). Consequently, we affirm that, in the context of robust offline reinforcement learning with function approximation, both the computational efficiency and minimax optimality are achievable under the setting of d-rectangular linear DRMDPs with TV uncertainty sets. Moreover, Theorem 6. also suggests that achieving a good robust policy necessitates the worst case coverage of the offline dataset over the entire uncertainty set of transition models, which is significantly different from standard linear MDPs where a good coverage under the nominal model is enough [15, 60, 54]. Such a distinction indicates that learning in linear DRMDPs may be more challenging in comparison to standard linear MDPs.
Further, we highlight that the hard instances we constructed also satisfy Assumption 4.3. It remains an interesting direction to explore what would happen if the nominal and perturbed environments don't t share exactly the same state-action space. We conjecture that since there could be absolutely new states emerging in perturbed environments that can never be explored the nominal environment, the policy learned merely using data collected from the nominal environment could be arbitrarily bad.
Challenges and novelties in construction of hard instances Existing tight lower bound analysis in standard linear MDPs [62, 60, 54] generally depends the Assouad's method and family of hard instances indexed by 5 E (-1,1) 1]. However, they do not consider model uncertainty, which largely hinders the derivation of explicit formulas for the robust value functions. Further, one prerequisite of the Assouad's 's method is switching the initial minimax suboptimality inf MMXMEM SubOpt(fi,) s. to a risk of the form infe maxe DH (E. E'). where DH is the Hamming distance. The model uncertainty significantly complicates this procedure, as the nonlinearity involved disrupts the linear dependency between the value function and the index &. At the core of Theorem 6.1 is novel class of hard instances M. At a high-level, the hard instances should (I) fulfill the d-rectangular linear DRMDP conditions, (2) mitigate the nonlinearity caused by model uncertainty, (3) achieve the prerequisite for Assouad's 's method, and (4) be concise enough to admit matrix analysis. We postpone details on the construction of hard instances and the proof of Theorem 6.1 to Appendix
As a side product of Theorem 1, we show in the following corollary an information-theorel lower bound in terms of the instance-dependent uncertainty function (AA,, s) in Theorem 4.4.
Corollary 6.2. Under the same setting in Theorem 6.1, the class of hard instances M and offline dataset D in Theorem 6.1 also suggests that, with probability at least 1 8, inf SuPMEM SubOpt(ft,s, s) 2 c- ((A,,'
-1 s), where c is a universal constant.
This implies that the uncertainty function + (A,,7,,) 8) in Theorem 4.4 also arises from the information- theoretic lower bound. We note the lower bound in Corollary 6.2 matches the upper bound in Theorem 4.4 up to 31, thus DRPVI is also minimax optimal in the sense of information theory, but with larger gap of Ó(VāH). Moreover, the only difference between Theorem 6. and Corollary 6.2 the covariance matrix. Due the fact that A, = -x-1, the information-theoreti lower bound in Theorem 6.1 is indeed tighter than that in Corollary 6.2.
7 Conclusions
We studied robust offline RL with function approximation under the setting of d-rectangular linear DRMDPs with TV uncertainty sets. We first proposed the DRPVI algorithm and built up a theoretical analysis pipeline to establish the first instance-dependent upper bound on the suboptimality gap in the context robust offline RL. We then showed an interesting range shrinkage phenomenon specific to DRMDPs, and we proposed the VA-DRPVI algorithm, which leverages the conditional variance information of the optimal robust value function. Based on the analysis pipeline built above, we show that the upper bound of VA-DRPVI achieves sharp dependence addition, we found that an uncertainty function consisting of two crucial quantitics-a supremum over uncertainty set and diagonal- lower bound to prove that the uncertainty function is unavoidable
the horizon length H. In
normalization-appell in all upper bounds. We further
established an information-theott for robust offline RL under the setting of d-rectangular linear DRMDPs.
remains an interesting future research question whether the computational and provable efficiency can be achieved in other settings for robust offline RL with function approximation. Another interest- ing future direction to explore the unique challenges of applying general function approximation techniques in standard offline RL [6] to DRMDPs.
10

---

Acknowledgments
We would like to thank the anonymous reviewers for their helpful comments. ZL and PX was supported in part by the National Science Foundation (DMS-2323112) and the Whitehead Scholars Program at the Duke University School Medicine. The views and conclusions this paper are those of the authors and should not be interpreted as representing any funding agency.
References
[1] Yasin Abbasi- Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011. (p. 46.)
[2] Alekh Agarwal, Yuda Song, Wen Sun, Kaiwen Wang, Mengdi Wang, and Xuezhou Zhang. Provable benefits of representational transfer in reinforcement learning. In The Thirty Sixth Annual Conference Leurning Theory, pages 2114-2187. PMLR, 2023. (p. 16.)
[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 5-2-5 PMLR, 2021. (pp. 3, and 4.)
[4] 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 23X,:23005.0959, 2023. (pp. 2, 3, 4, 7, and 9.)
[5] Avinandan Bose, Simon Shaolei Du, and Maryam Fazel. Offline multi-task transfer rl with representational penalization. arXiv preprint arXiv:2402.12570, 2024. (p. 16.)
[6] Jinglin Chen and Nan Jiang. Information-theored considerations in batch reinforcement learning. In International Conference on Machine Learning, pages 1042-1051. PMLR, 2019.
(p. 10.)
[7] Yuan Cheng. Songtao Feng, Jing Yang. Hong Zhang, and Yingbin Liang. Provable benefit of multitask representation learning in reinforcement learning. Advances in Neural Information Processing Systems, 35:31741-31754 2022. (p. 16.)
[8] Jing Dong, Jingwei Li, Baoxiang Wang, and Jingzhao Zhang. Online policy optimization for robust mdp. arXiv preprint arXiv:2209.13841, 2022. (p. 3.)
[9] Yaqi Duan, Zeyu Jia, and Mengdi Wang. Minimax-optimal off-policy evaluation with linear function approximation. In International Conference on Machine Learning, pages 2701-2700 PMLR, 2020. (p. 7.)
[10] Jesse Farebrother, Marlos C. Machado, and Michael Bowling. Generalization and regularization in dqn. arXiv preprint arXiv:1810.00123, 2018. (p. 1.)
[11] Omer Gottesman, Fredrik Johansson, Matthicu Komorowski, Aldo Faisal, David Sontag, Finale Doshi-Veles and Leo Anthony Celi. Guidelines for reinforcement learning in healthcare. Nature medicine, 25(1):16-18) 18, 2019. (p. 1.)
[12) Vineet Goyal and Julien Grand-Clement. Robust markov decision processes: Beyond rectangu- larity. Mathematics of Operations Research, 48(1):203-226, 2023. (pp. 3 and 4.)
[13] Garud N Iyengar. Robust dynamic programming. Mathematics of Operations Research, 30(2): 257-280, 2005. (pp. and 4.)
[14] Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference Learning Theory, pages 2137- 2143. PMLR, 2020. (pp. 5 and 43.)
[15] Ying Jin, Zhuoran Yang, and Zhaoran Wang. Is pessimism provably efficient for offline rl? In International Conference on Machine Learning, pages 5084-5096. PMLR, 2021. (pp. 1, 2, 3, 7. 10, 16, 17, 27, and 28.)

---

[16] 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. (p. 1.)
[17] Sascha Lange, Thomas Gabel, and Martin Riedmiller. Batch reinforcement learning. In Reinforcement learning: State-of-the-arl, pages 45-73. Springer, 2012. (p. 1.)
[18] Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu. Offline reinforcement learning: Tutorial, review, and perspectives on open problems. ar preprint WrXiv22055006443 2020.
(p. 1.)
[19] Zhipeng Liang, Xiaoteng Ma, Jose Blanchet, Jun Yang, Jiheng Zhang, and Zhengyuan Zhou. Single-trajectory distributionally robust reinforcement learning. In Forty-first International Conference on Machine Learning. (p.3.) 3.)
[20] Zhishuai Liu and Pan Xu. Distributionallly robust off-dynamics reinforcement learning: Prov- able efficiency with linear function approximation. In International Conference on Artificial Intelligence and Statistics, pages 2719-2727. PMLR, 2024. (pp. 2, 5, 6, 17, and 43.)
[21] Zhishuai Liu, Zishu Zhan, Cunjie Lin, and Baqun Zhang. Estimation in optimal treatment regimes based on mean residual lifetimes with right-censored data. Biometrical Journal, 65(8): 2200340, 2023. (p. 1.)
[22] Zhishuai Liu, Zishu Zhan, Jian Liu, Danhui Yi, Cunjie Lin, and Yufei Yang. On estimation of optimal dynamic treatment regimes with multiple treatments for survival data-with application to colorectal cancer study. arXiv preprint arXiv:2310.05049, 2023. (p. 1.)
[23] Rui Lu, Andrew Zhao, Simon Du, and Gao Huang. Provable general function class repre- sentation learning in multitask bandits and mdp. Advances in Neural Information Processing Systems, 1577 2022. (p. 16.)
[24] 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:2209.066 066200 2022. (pp. 4 and 6.)
[25] Ajay Mandlekar, Yuke Zhu, Animesh Garg, Li Fei-Fei, and Silvio Savarese. Adversarially robust policy learning: Active construction of physically-plausibe perturbations. In 2017 IEEE/RS/ International Conference on Intelligent Robots and Systems (IROS), pages 3932-3939 IEEE, 2017. (p. 1.)
[26] Shie Mannor, Ofir Mebel, and Huan Xu. Robust mdps with k-rectangular uncertainty. Mathe- matics of Operations Research, 4 41(4):1484-1500 2016. (.)
[27] Yifei Min, Tianhao Wang, Dongruo Zhou, and Quanquan Gu. Variance-aware off-policy evaluation with linear function approximation. Advances in neural information processing systems, 34:7598-7610, 2021. (pp. 8 and 46.)
[28] Jun Morimoto and Kenji Doya. Robust reinforcement learning. Neural computation, 17(2): 335 335-359,20 2005. (p. 1.)
[29] John A Nelder and Roger Mead. A simplex method for function minimization. The computer journal, 7(4):308-313, 1965. (p. 6.)
[30] Arnab Nilim and Laurent El Ghaoui. Robust control of markov decision processes with uncertain transition matrices. Operations Research, 53(5):780-798, 2005. (p. 1.)
[31] Charles Packer, Katelyn Gao, Jernej Kos, Philipp Krähenbühl, Vladlen Koltun, and Dawn Song. Assessing generalization in deep reinforcement learning. arXiv preprint arXiv: /800./ 12282, 2018. (p. 1.)
[32] Yunpeng Pan, Ching-An Cheng, Kamil Saigol, Keuntak Lee, Xinyan Yan, Evangelos Theodorou, and Byron Boots. Agile autonomous driving using end-to-end deep imitation learning. In Robotics: science and systems, 2018. (p. 1.)
12

---

[33] Kishan Panaganti and Dileep Kalathil, Sample complexity of robust reinforeement learning with generative model. In International Conference on Artificial Intelligence and Statistics, pages 9582-9602. PMLR, 2022. 3.)
[34] Kishan Panaganti, Zaiyan Xu, Dileep Kalathil, and Mohammad Ghavamzadeh. Bridging distributionally robust learning and offline rl: An approach to mitigate distribution shift and partial data coverage. In ICML 2024 Workshop: Foundations of Reinforcement Learning and Control-Connectonss and Perspectives. (p. 4.)
[35] Kishan Panaganti, Zaiyan Xu, Dileep Kalathil, and Mohammad Ghavamzadeh. Robust rein- forcement learning using offline data. Advances neural information processing systems, 35: 32211-32224, 2022. (pp. 1, 3, and 4.)
[36] Anay Pattanaik, Zhenyi Tang. Shuijing Liu, Gautham Bommannan, and Girish Chowdhary. Robust deep reinforcement learning with adversarial attacks. In Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, pages 2040-2042, 2018. (p. 1.)
[37] Lerrel Pinto. James Davidson, Rahul Sukthankar, and Abhinav Gupta. Robust adversarial reinforcement learning. In International Conference on Machine Learning, pages 2817-2826. PMLR, 2017. (p. 1.)
[38] Aurko Roy, Huan Xu, and Sebastian Pokutta. Reinforcement learning under model mismatch. Advances in neural information processing systems, 30, 2017. (p. 2.)
[39] Jay K Satia and Roy E Lave Jr. Markovian decision processes with uncertain transition probabilities. Operations Research, 21(3):728-740 1973. (p. 1.)
[40] Yi Shen, Pan Xu, and Michael Zavlanos. Wasserstein distributionally robust policy evaluation and learning for contextual bandits. Transactions on Machine Learning Research, 2024. ISSN 2835-8856 8856. URL https: https:///penniie /ttp:/:////p//eee//ee//e tion. (p. 1.)
jMWiVVVVV Featured Certifica-
[41] Laixi Shi and Yuejie Chi. Distributionally robust model-based offline reinforcement learning with pear-optimal sample complexity. Journal of Machine Learning Research, 25(200):1-91, 2024. (pp. 1, 2, 3, and 6.)
[42] Laixi Shi, Gen Li, Yuting Wei, Yuxin Chen, Matthieu Geist, and Yuejic Chi. The curious price of distributional robustness in reinforcement learning with a generative model. Advances in Neural Information Processing Systems, 36, 2024. (pp. 3, 8, and 40.)
[43] Pei Sun, Henrik Kretzschmar, Xerxes Dotiwalla, Aurelien Chouard, Vijaysai Patnaik, Paul Tsui, James Guo, Yin Zhou, Yuning Chai, Benjamin Caine, et al. Scalability in perception for autonomous driving: Waymo open dataset. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 2446 2254,,44, 2020. (p. 1.)
[44] Aviv Tamar, Shie Mannor, and Huan Xu. Scaling up robust mdps using function approximation. In International conference on machine learning, pages 181-189. PMLR, 2014. (pp. 2 and 4.)
[45] Chen Tessler, Yonathan Efroni, and Shie Mannor. Action robust reinforcement learning and applications in continuous control. In International Conference on Machine Learning, pages PMLR, 2019. (p. 1.)
[46] Alexandre B. Tsybakov. Introduction to Nonparametric Estimation. Springer, New York, 2009.
(p. 37.)
[47] Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47, Cambridge university press, 2018. 28.)
[48] He Wang, Laixi Shi, and Yuejie Chi. Sample complexity of offline distributionally robust linear markov decision processes. arXiv preprint arXiv:2403.12946, 2024. (p. 4.)
13

---

[49] 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. (p. 1.)
[50] Ruosong Wang, Dean Foster, and Sham M Kakade. What are the statistical limits of offline rl with linear function approximation? In International Conference on Learning Representations,
2021. (p. 7.)
[51] Yue Wang and Shaofeng Zou. Online robust reinforcement learning with model uncertainty. Advances in Neural Information Processing Systems, 34:7193-7200 2021. (pp. 2 and 3.)
[52] Wolfram Wiesemann, Daniel Kuhn, and Berç Rustem. Robust markov decision processes. Mathematics of Operations Research, 38( (1)11155-183 2013. (pp. and 3.)
[53] 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. (pp. 1, 2, 6, and 16.)
[54] Wei Xiong, Han Zhong, Chengshuai Shi, Cong Shen, Liwei Wang, and Tong Zhang. Nearly minimax optimal offline reinforcement learning with linear function approximation: Single- agent mdp and markov game. In International Conference on Learning Representations (ICLR), 2023. (pp. 2, 3, 7, 8, 9, 10, 16, 28, and 32.)
[55] Huan Xu and Shie Mannor. The Advances in Neural Information Processing Systems, 19, 2006. (pp. 1 and 3.)
tradeoff in markov decision processes.
[56) Zaiyan Xu, Kishan Panaganti, and Dileep Kalathil. Improved sample complexity bounds for distributionally robust reinforcement learning. In International Conference on Artificial Intelligence and Statistics, pages 9728-9754. PMLR, 2023. (pp. 3 and 4.)
[57] Wenhao Yang, Liangyu Zhang, and Zhihua Zhang. Toward theoretical understandings of robust markov decision processes: Sample complexity and asymptotics. The Annals of Statistics, 50 (6):3223-3248, 2022. (pp. 1, 3, and 4.)
[58] Wenhao Yang, Han Wang, Tadashi Kozuno, Scott M Jordan, and Zhihua Zhang. Robust markov decision processes without model estimation. arXiv preprint arXiv:2302.01224. 2023, (p. 3.)
[59] Zhouhao Yang, Yihong Guo, Pan Xu, Anqi Liu, and Animashree Anandkumar. Distributionally robust policy gradient for offline contextual bandits. In International Conference on Artificial Intelligence and Statistics, pages 6443-6462. PMLR, 2023. (p. 1.)
[60] Ming Yin, Yaqi Duan, Mengdi Wang, and Yu-Xiang Wang. Near-optimal offline reinforcement learning with linear representation: Leveraging variance information with pessimism. arXiv preprint arXiv:2203.05880 2022. (pp. 2, 7, 8, 10, and 16.)
[61] Pengqian Yu and Huan Xu. Distributionally robust counterpart in markov decision processes. IEEE Transactions on Automatic Control, (19))2253-25444 2015. 3.)
[62] Andrea Zanette, Martin J Wainwright, and Emma Brunskill. Provable benefits of actor-critic methods for offline reinforcement learning. Advances in neural information processing systems, 34:13626-13644
2021. (pp. 2. 10, and 16.)
[63] Huan Zhang, Hongge Chen, Chaowei Xiao, Bo Li, Mingyan Liu, Duane Boning, and Cho- Jui Hsieh. Robust deep reinforcement learning against adversarial perturbations state observations. Advances in Neural Information Processing Systems, 33:21024-21037, 2020. (p. 1.)
[64] 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. (p. 1.)
[65] Dongruo Zhou, Quanquan Gu, and Csaba Szepesvari. Nearly minimax optimal reinforcement learning for linear mixture markov decision processes. In Conference on Learning Theory, pages 4576. PMLR, 2021. (pp. 3, 8, and 46.)
14

---

[66] Ruida Zhou, Tao Liu, Min Cheng, Dileep Kalathil, PR Kumar, and Chao Tian. Natural actor- critic for robust reinforcement learning with function approximation. Advances neural information processing systems, 36, 2024. (pp. 2 and 4.)
[67] 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 Artificial Intelligence and Statistics, pages 3331-3339. PMLR,
2021. (p. 3.)
15

---

A Additional Related Work
Offline Linear MDPs. Our work focuses on the offline linear MDP setting where the nominal transition kernel, from which the offline dataset is collected, admits the linear MDP structure. Numerous works have studied the provable efficiency and statistical limits of algorithms under this setting [15, 62, 53, 60, 54]. The most relevant study ours is the recent work of [54], which established the minimax optimality of offline linear MDPs. At the core of their analysis is an iivaantage-refrrence technique designed for offline RL under linear function approximation, together with a variance aware pessimism-hane haased algorithm. However, the offline linear MDP setting still remains understudied in the context of DRMDPs.
Transfer-Learnin in Low Rank MDPs. Besides the distributionally robust perspective solve the planning problem in a nearly unknown target environment, another line of work focuses on transfer learning in low-rank MDPs [7, 23, 2, 5J. Specifically, the problem setup assumes that the agent has access to information of several source tasks. The agent learns a common representation from the source domains and then leverages the learned representation to learn a policy performing well in the target tasks with limited information. This setting is in stark contrast to DRMDPs, where the agent only has access the information of a single source domain, without any available information of the target domain, assuming the same task is being performed. This motivates the pessimistic principle of the distributionally robust perspective. Among the aforementioned works, Bose et al. [5] studied the offline multi-task RI., which is the most closely related to our setting. In particular, they investigate the representation transfer error in their Theorem 1, stating that the learned representation can lead to a transition kernel that is close to the target kernel in terms of the TV divergence. Note that the uncertainty is induced by the representation estimation error, which different from our setting assuming that the uncertainty comes from perturbations Nevertheless, this work provides evidence that TV divergence is a reasonable measure to quantify the uncertainty in transition kernels and motivates future research direction in learning robust policies that are robust to the uncertainty induced by the representation estimation error.
underlying factor distributions.
B A More Computationally Efficient Variant of VA-DRPVI
In this section, we propose a modified version of Algorithm 2, which reduces the computation cost in the ridge regressions for variance estimation and achieves the same theoretical guarantees.
Variance Estimator. In Section 5, we estimate the variance of the truncated robust value function 1V Thus, for different a, we need to establish different variance estimators, which signifi- cantly increases the computational burden. The theoretical analysis of Algorithm 2 suggests that it
suffices to estimate the the variance of V'p V instead of the truncated one. In particular, we know [Var, 1/d 1(s,)) (V (s, (9s,,, a) - (IP9 4+ (s,a))² (s a), 2x.2) ((0(s, a), 2).
Then estimate #4,1 and Z4,2 via ridge regression:
2, argmin zcRd
(5++))))))) x)²²²²² + >1|=112
(B.la)
1 argmin
15 xT²²²²² + 111212
(B.1b)
#ERd
We construct the following truncated variance estimator:
dH3
(s, = max { (((s,a) 2x.2] 0, - [dbss, a) 2 [0.
Ō
(B.2)
VRR
The modified variance-aware algorithm is presented in Algorithm 3 and the theoretical guarantee is presented in Theorem B.I.
Theorem B.1. Under Assumptions 3.1 and 4.3, for K > (f O() Ō(H*)(²))) (0, 1). if we set À 1/H1² and 82 Ō(Vd) in Algorithm 3, then with probability at least 1 6, for
and 8 e
16

---

Algorithm 3 Modified VA-DRPVI
Require: Input dataset D, D' and 82; V H++ (.) 0
1: Run Algorithm 1 using dataset D' to get (V/ )
2: for = H,.... : do
3: Construct variance estimator (; using D' by (B.1) and (B.2)
4: Σn Σ T /0 (s) 0,) + AI
(a) Mn Σ 0% 1/ (8 (+ / (5 a5)
5:
6:
arg (a) p(a min (8))(()))))))))) Vi
7:
ph = {a;) - p(a; min, [6 (o))),), ViE E [d]
8:
Ta(:.) - 32 E/= [1:
9:
OR(s') = -(((-)) (0, + ( - -Ta(:-)oon
10: #n (-I.) f argmax, vn (%(( m. (+1))) P2(() + (.
11:
end for
all 8 E S, the suboptimality of VA-DRPVI satisfies
H Σ
SubOpt(# (, s B2-
S sup (PU)(
E
11 an (ellll:;) = (B.3)
where E = "5 VVVV o7 AI.
Remark B.2. The computation cost of Algorithm variance estimators are not related to a anymore. Notably, Algorithm 3 shares the same upper bound as Algorithm 2. According to Theorem 6. we know the modified algorithm is also minimax optimal.
much smaller than Algorithm 2, as the
C Experiments
We conduct numerical experiments to illustrate the performances of our proposed algorithms, DRPVI and VA-DRPVI, and compare with the their non-robust counterpart, PEVI[15) All numerical exper- iments were conducted on a MacBook Pro with 2.6 GHz 6-Core Intel CPU. The implementation of our DRPVI algorithm is available at https: /ttps:///ittiann github...... com/ wataa//axulaab//aa /ftfffffliim Sereeiine--nnearrr Linear-DRMDP.
Construction of the simulated linear MDP We leverage the simulated linear MDP setting pro- posed by Liu and Xu [20] and modify it as an offline RL problem. In particular, the source and target linear MDP environment are shown in Figure ((a) and Figure ((b). The state space is set to be S {ar, ... .t5) and the action space to be A == (-1,11) C TR., At each episode, the state always starts with .1, and then transits to 22, F4, intermediate state, and it can transit to æ3, T4 Vs with probability defined on the lincs. Morcover, Both 24 and 26 are absorbing states. I4 (æx) is the fail state (goal state), and the reward starting from which is always (I). The reward functions and transition probabilities are designed to depend on IR shown in the figure. The target environment is constructed by only perturbing the transition probability at T1 of the source environment, and the extend of perturbation is controlled by the hyperparameter simulated linear DRMDP to the Supplementary A.1 of [20].
with probability defined in the figures. 22 is an
the hyperparameter
(0, 1). We refer more details the construction of the
Implementation We simply use the random policy that chooses actions uniformly at random at any (s, h) E S x A x [H] to collect offline dataset. The offline dataset containing 100 trajectories collected by the behavior policy from the source environment. We conduct ablation 1/ and consider different heterogeneous uncertainty level for our two algorithms. Specifically, we set P1.4 0.5 and Pa.i = 0 for all other cases. The experiment results shown in Figure 2.
study by setting the hyperpameter & = (1/ 1, 1/Il 1 El,,
choices of || {0.1, 0.2, 0.3). Following [20].
Figure 2 shows the performances of the learned policies of three algorithms. We conclude that both of proposed algorithms robust to environmental perturbation compared to the non-robust PEVI.
17

---

44
T4
M(
m))
F01 (3)
P(1
16, n3)
((,a)
ol + (()a))
(6.a)
11
22
I3
I1
J2
33
pi(1 - (6.a)
p)(1 5 (E.a)
(1 (1-6 6 (6.
p][l (6.0)
84 (E.a)
6 (5,a)
(1 - 93(6 + ((:
+ (6,0)
5 (5.
(5.
FS
I'S
(a) The source MDP environment.
(b) The target MDP environment.
Figure 1: The source and the target linear MDP environments. The value each arrow represents the transition probability. For the source MDP, there are five states and three steps, with the initial state being F1, the fail state being T4. and 2; being absorbing state with reward 1. The target MDP on the right obtained by perturbing the transition probability at the first step of the source MDP, with others remaining the same.
Furthermore, VA-DRPVlslightly outperforms DRPVI in most settings. These numerical results are consistent with our theoretical findings.
D Proof of Theorem 4.4
Our analysis mainly deals with the challenges induced by the model uncertainty, inf (P)) and the need to maximally exploit the information in the offline dataset. More specifically, the proof of Theorem 4.4 mainly constitutes of two steps.
Step 1: suboptimality decomposition. We first decompose the suboptimality gap in the following lemma to connect it with the estimation error, the full proof of which can be found in Appendix G.1.
Lemma D.1 (Suboptimality Decomposition for DRMDP). the following holds
inf (a.
PA Whiielss, - a(s, s
ESx (D.1)
then we have SubOpt(ft, s, p) & supprau< ET (sh. an))s1 = =s]
The main challenge in deriving Lemma D.I lies in the dependency the robust Bellman equation (3.1) the nominal kemee p3, which is not linear and does not have an explicit form. It should be noted that the term inf inf (e.))
[P (s, a) ((s, a) TT D in condition (D.1) stands for the estimation error of the estimated robust Q-function in (4.5), which we refer to the robust estimation uncertainty. Lemma D.1 shows that under the condition that the robust estimation uncertainty is bounded by (8, a), the suboptimality gap can be upper bounded in terms of T (s, a). To conclude the proof, remains derive [ (s, a) and then substitute it back into the result in Lemma D.I.
Step bounding the robust estimation uncertainty. We now bound the robust estimation uncer- tainty in Lemma D.I by the following result, the full proof of which can be found in Appendix G.2.
18

---

12-
PEVI DRPVI
DRPVI VA.DRPVI
DRPVI
Average reward
VA- VA-DRPVI
VA-DRPV
Averaae
0.9
Perturbation
Perturbation
Perturbation
(a)
||E|| 0.1, P1,4
0.3
(b) ||<|] = 0.1, P1, = 0.4
(c) |K<|| 0.1, P1,4 0.5
PEVI
PEVI DRPVI
PEVI DRIVI VA-DRPVI
Averrae reward
DRPVI VA-DRPVI
Average reward
Average Roward
1.3-
VA-DRPVI
E
03-
C6 Perturbation
02
15
Perturbation
Perturbation
(d) [|]l = 0.2, M1, = 0.3
(c) ||E|| p1,4 = 0.4
(f)
| = 0.2, p1,4 = 0.5
Aversoe reward
Average reward
Average reward
3.4
2.2
PEVI
PEVI
366
DRPVI
DRPVI
3.0
DRPVI
VA-DRPVI
DRPV
VA DRPVI
02
C4
16
66
62
Q4
04
66
16
34
04
66 10
Perturbation
Perturbation
Perturbation
(g) ||E||= 0.3, P1,4 0.3 (h) ||E||
0.3, P1
0.4
ii
||E||
0.3, P1,4 0.5
Figure 2: Simulation results under different source domains. The z-axis represents the perturbation level corresponding to different target environments. P1.4 is the input uncertainty level for our VA-DRPVI algorithm. ||E||| the hyperparameter of the linear DRMDP environment.
Lemma D.2 (Robust Estimation Uncertainty Bound). For any sufficiently large sample size K satisfying K > max log(2dH² 2 /k}. and any fixed 8 E (0, 1). if we set in Algorithm 1, then with probability at least 1 - 6, for all (s,a,h) E S x
x [H], we have
inf PACle.))El((sssap)
[P PP De (4 a) ((s,)) og < <Ta(s,a),
(D.2)
where (=( 4VTH v Vi (o((s, and 1. = 1og(2dH2KK06)
(s a) provides an explicit bound for the robust estimation uncertainty, which also serves as the penalty term in Line of Algorithm 1. The main challenge of deriving Lemma D.2 lies in inferring the worst-case behavior using information merely from the nominal environment. Our idea is to first transform the robust estimation uncertainty to the estimation uncertainty of ridge regressions (4.2) on the nominal model po, where the samples are collected and statistical control is available. We then adopt reference-ate advantage decomposition technique, which new in the linear DRMDP literature, to further decompose the estimation uncertainty on the nominal model into the reference uncertainty and the advantage uncertainty. The remaining proof is to bound the reference uncertainty and advantage uncertainty respectively using concentration and union bound arguments under an induction framework to address the temporal dependency. We highlight that all these arguments are specifically designed for the unique problem of DRMDP, which is novel and nontrivial.
19

---

E Proof of the Suboptimality Upper Bounds
In this section, we prove the main results in Corollary 4.5, Remark 4.6, Theorem 5.2, and Corollary 5.3, which give out the instance-dependent upper bounds of the proposed algorithms. Before the proof, we introduce some useful notations. For any function f - [0, H 1]. define
inf P. al (s.ap)))))
Ph.l(s. Φ(s. a) og(())
(E.1)
where for each i [d]. we have
(f) = max
{
p(a minif(s')aa)
*'s
aE|u.H]
([()) A Σ (b1l(oh+1)aa
E.1 Proof of Corollary 4.5
The proof of Corollary 4.5 is straightforward given our result in Theorem 4.4.
Proof. Define A, = Ex .Pa (cb an (<()), an J], wh E [H]. By Assumption 4.3, we have Ar z
I. We further bound (6.1) follows,
sup (P))
Σ 1ET
(o an anll: =
H
sup PEUP((P)) PO)
E= .P
1 an 10:l)1l11
=
(E.2)
VK
1=1 ==
sup
2
E= ,P
(s a)y A, 1, $1
VK
S sup
B=",P
di (s a)v Amax Amax (A (A =
(E.3)
PPO)(PP) VK
H
sup
B ,P
de (s)
81
PEMP((P) VK
Amin (An)
h= 1=1
2
sup (PO)
E=' PP
(E.4)
VK
2H
VK.
where (E.2) is due to Lemma I.3, (E.3) is due the fact that for any matrix A, Amin S Au S Amax-
where Aü is the i-th diagonal element of A. (E.3) holds due to Assumption 4.3 and the fact that - á1(s, a) = 1. We conclude the proof by invoking Theorem 4.4.
E.2 Proof of Theorem 5.2
The proof idea is similar to that of Theorem 4.4, except that additionally analyze the variance estimation and apply the Bernstein-type self-normalized concentration inequality to bound the reference uncertainty, which is the dominant term. We start from analyzing the estimation error of conditional variances in the following lemma.
Lemma E.1. Under Assumptions 3.1 and 4.3, when K 2 Ō(H*/OH** /x²), then with probability at least 1- 8, for all (s, a,,.,)) E x A [H] and any fixed a, have
[VaV (s, 0 VKK ) I (), S [W[V (s,
dH3
20

---

The following lemma bounds the estimation error by Decomposition), There exist {as (astveld) where Lemma E.2 (Variance-Awart
decomposition.
og [0, HJ, Vi [d], such that
inf Eu (,,00
[P Vh 1
inf
[ P (ttl
Pa P. (s.0ssh
| (118, S
| [V (s)laa) (a.)
(ac)
t (IV k+llaa)
as, [(a))
Σ
th (s% aii as) (ac)
(1((,,,)),lls,,-(a) (as))
Eua [1h+1 (s)lar [V)l(
I (as)
ti (s)la [V
Σ
( d7:0s)) as)
where (ifl..)) (1 (5% a7) Ma))) for any function f - 1].
Now we are ready to prove Theorem 5.2
Proof of Theorem 5.2. To prove this theorem, we bound the estimation error by [s, a), then invoke Lemma D.1 to get the result. First, we bound terms i-iv in Lemma E.2 to deduce T' (s, a) at each step E [H. respectively.
Bound and ii:: We set A = 1/H2 to ensure that for all (s,a,h) E x Ax H..
we have
i VAVaH
|1.(s, 1)) (1ll))))) Vd Σ 11 a) (a.)
(E.5)
Bound ii: For all (s, a) S Ax H) by definition we have T a) 2 1. Thus, for all (h, i) E [H] x [K] x [d], we have (VV: (a. l/. ( ah. as)l I H. Note that V is independent of D, we can directly apply Bernstein-type self-normalized concentration inequality Lemma 1.2 and union bound to obtain the upper bound. In concrete, we define the filtration Fr-1, (((),, J=) U (5E+)) Since V and (s o; a) are independent of D, thus 77 ([V (V: (5%, ah os) is mean-zero conditioned on the filtration Fr-1,h. Further, we have
7r (8% a7; as)) )² [
17, (1T441l))))))
[Var|V 0%)
E
(E.6)
(V (1) Ö(dH3/
Ö(dli/VKK /VKR)
( ()13))
(5 07110000 as)
Ō(dH' /VKK)
<1+
(E.7)
(s (T: O(dH3//T
dH
< + 20
(E.8)
VKR
21

---

where (E.6) holds by the fact that 0% (--))) is independent of D and (5) 07 is F=11A measurable.
(E.7) holds by Lemma E. and (E.8) holds by setting K 2 (2(c 11 / /K) such that 0% (5% a as) Ódd' /VKK) 2 O(dH///HH/V //x)) 2 1/2. Further, by (E.8), our choice of also ensures that E (1 b+1la.) 1A O(1). Then by Lemma I.2, we have
0 (
<ó(Vd).
( o3 a4)))) a4)
1 (oE)
This implies
ii - Ō(Vd) d)
(E.9)
Bound iv: Following the same induction analysis procedure, have I1 111.. [V S
O(VāH²/VKKr Then, using standard e-covering number argument and Lemma 1.1, we have
iv S ò H222H² VKK
Σ 11oi(s, ())(s,
(E.10)
To make it non-dominant, require K 2 Ω H*/)) By Lemma E.1, for any a E [0, H). we have (5 [VlV a
Va a.).
this implies that
K
K
JT T W. h+1 (5% a
Σ
+ AT)
= Σ/ AI
Combining (E.5), (E.9) and (E,10), we have
inf Pa
PP Vp (ls,
inf
[P
Vp h+ ((,
P.(.)a.)) (l (,,
< <((Vd) (1)((;
Define (n(s,a) = Ō (1) we concludes the proof by invoking Lemma D.1.
L
E.3 Proof of Corollary 5.3
In this section, we prove Corollary 5.3. We start with interesting phenomenon, call 'range shrinkage', stated in the following lemma.
Lemma E.3 (Range Shrinkage). For any (a, n. hi) E (0, 1] x II [H], we have
p) n- h+1
max V (s) min VT < SES
(E.11)
#ES
Proof of Corollary 5.3. By the fact that the variance of a random variable can be upper bounded by the square of its range and Lemma F.3, for all (s, a, h) E S A [H), we have
[V S (1-(1-))* -
(1
1 (1
P
Then we have
1
I
Σ
I. H²
(V at)
H²
1-(1-p) y2
P
22

---

Thus we have
2 -
0 T
+
H²² 1) -1
1 11 -1--1-
3
2
Σ
TT
+
1 H2
1/2
VA 16 1
P
By Theorem 5.2, we have
H
= pf) SubOpt(f1, (t, 8,
sup
Σ
E
(1 on an)1ills;-1100
PELL (Po)
h=1
im
1 (1 p)H
H ET
< o((d)
P
sup (EUP((P)
p
Am
This concludes the proof.
F Proof of the Information-Theoreti Lower Bound
In this section, we prove the information-theorele lower bound. We first introduce the construction of hard instances in Appendix F.I, then we prove Theorem 6.1 in Appendix F.2, and prove Corollary 6.2 in Appendix F.3.
F1 Construction of Hard Instances
We design family of d-rectangular linear DRMDPs parameterized by a Boolean vector & {EA hnjHH) where &Λ E {-1,1)á. For given & and uncertainty level (0, 3/4), the corresponding d-rectangular linear DRMDP M has the following structure. The state space S = {x1, and the
action space
(0, 13d. The initial state distribution 140 is defined as
d+1 and (o(2)) d 2
1
(o(21)
+ 2
The feature mapping 8
- + R is defined as
Φ(x1,a) (1 02
ad
Σ
0 d
0)
Φ(02, a) =0,00, ... 0000,1).
which satisfies (x, 2 0 and Ed (x,5,a) = 1. The factor distributions (14 (PAA) are defined
H1 6z 8e, Sel, Sn, Soz). wh E [H]
so the transition is homogeneous and does not depend on action but only on state. The reward
parameters (0n heem are defined
o = E11
+
EN2
End 1 1 vh E [H]
2
where a parameter to control the differences among instances, which is to be determined later. The reward T4 is generated from the normal distribution Th ((rn(S,, an), 1), where Th (1(8, a) ((8,a) Op- Note that
(x) = Φ(21. a) 0 = 6 (EEn, a) + dd) 2 0 and (x(22, a) = 0 x2 a) 0, = 0, Va E A,
8
2d
which means that 22 is worst state in terms of the mean reward. Thus, the worst case transition kernel should have the highest possible transition probability to x2- This construction is pivotal in achieving concise expression of robust value function. Further, we only consider model uncertainty
23

---

(a) The nominal environment.
(b) The worst case transition at the first step.
Figure 3: The nominal environment and the worst case environment. The value on each arrow represents the transition probability. The MDP has two states and H steps. For the nominal environment, both Iı and 22 absorbing states, which means that the state will always stay the initial state in the nominal environment. The worst case environment on the right obtained by perturbing the transition probability the first step of the nominal environment, with others remain the same.
the first step. By the fact that 22 is the worse state, we know the worst case factor distribution for the first step is
ii ((1 p)om, + pdaz (1 p)o., + pdma:" (1 p))m; + pózz (1 p)82, + pdmg 6 )
We illustrate the designed d-rectangular linear DRMDP M in Figure 3(a) and Figure 3(b).
Finally, we design the procedure for collecting the offline dataset. We assume the K trajectories are collected by behavior policy nb [ he|M defined as
T ~ Unif(fe1.... ea. 0}), wh E [H],
where hei are the canonical basis vectors in Rd. The initial state is generated according to μoo It is straightforward to check that the constructed hard instances satisfy Assumption 4.3. We denote the offline dataset as D.
F22 Proof Theorem 6.1
With this family of hard instances, are ready to prove the information-theoredd lower bound. First, we define some notations. For any E {-1,,1) let Qe denote the distribution of dataset D collected from the MDP Me. Denote the family of parameters as Ω 1- and the family of hard instances as M {Me & 22}.
Proof of Theorem 6.1. The proof constitutes three steps. the first step, we lower bound the minimax suboptimality gap by testing error in the following Lemma F.1, the full proof of which can be found Appendix G.6.
Lemma E1 (Reduction to testing). For the given family of d-rectangular linear DRMDPs, we have
ödH min inf $
inf sup SubOpt(#t, 21. 2 (1 p)- p) 8d
Qe(()(D) + <) Qe (v(()))) # E')
MEM
E.E'ER
D=((,6)==1
(F.I)
where for tixed indices & and E', eb is any test function taking value in {'.
In the second step, we lower bound the testing error on the right hand side of (F.1) in the following Lemma F.2, the full proof of which can be found in Appendix G.7.
Lemma F2 (Lower bound on testing error). For the given family of d-rectangular linear DRMDPs, let 5 = 3/2 //2K, then we have
min inf QQ((V(D) # + (VDD) + E E.E" (E.E)))=
1
By Lemma F.1 and Lemma F2, we have
/ H
inf sup SubOpt(F x1, # MEM
(F22
128 K
In the last step, we upper bound the uncertainty function t bbEE, 8) in the following Lemma F.3, full proof of which can be found in Appendix G.8.
the
24

---

Lemma F.3. For all Me E M, when K 2 Odd'), then with probability at least 1 5, we have
H
4d
E
( an) M1ll:, =/s1 m1
sup (EUP((P)
vK
h=1
By Lemma F.3 and (F22), we know that with probability least 1 6, there exist universal constant
such that
inf sup SubOpt(ft, p) c. MEM
sup (P
E
1s an an) - m1
This concludes the proof.
F.3 Proof of Corollary 6.2
Proof. The result in Corollary 6.2 directly follows from the fact shown in (G.38): for the constructed hard instances, we have Σ; = A₁. Thus, we complete the proof by directly substituting Σj, in the result of Theorem 6.1 by As.
G Proof of Technical Lemmas
G.1 Proof of Lemma D.1
Proof. First, decompose SubOpt(f,,, as follows
SubOpt(#t, 8, VI
(ss) Vs"
Vp(s)+ Df(s)) (s),
11
then we bound term and term respectively.
Bounding term I: Note that
1 (s) - Vf((s) Qh 1P (T) - (s (n)))
Q o (s. (8(8, + (s,
(s
2h (s) (())).
(G.1)
Here (G.1) holds by the faet that (x (s) the greedy policy corresponding to Q7 a), which leads to Q% (s)) (s, ft (s)) < O. Further, by the robust Bellman equation (3.1), we have
0% (sss, (5, ()))
inf rn(s, (()) + Pa Pa(l
PA PAV hti (' (s, (+)) (i(s
rn(s,
inf Pa (a
PP PPAV (s, m+()) rs(s, mT
inf (u
PA VP (s, T4
inf (=
[I Vo V. ((,, ())
- Q (s)).
To proceed, we define the robust Bellman update error as follows
(h(,, = ra(sa +
inf (o
[Px ( Qf,
and denote the worst transition kernel with respect to the estimated robust value function as P (Pn)n where Pr(-Is, a) arg inf Px( so))uf(e [P, V2 (s,, V(s,a) e 8 A.
Then we have
07 (ss - (5,s)
25

---

inf Pn V h+1 (' m+()))
inf
[Px VP Pa (() + (s ()())
<PPn(VTT1 Vi (8, x (+)) + (s (+)).
(G.2)
Combining (G.1) and (G.2), we have for any [M].
V (s) (s) & [PA(V - Vi (s, + (((s,
(G.3)
Recursively applying (G.3), we have
H VT - Vp(()) S Σ -
RdT [ISh(sn, =s].
(G.4)
h=1
Bounding term II: Note that (s)(s) - 10.--v,--00 (s) = (8, tr (8)) Q tn (8)), by the robust
Bellman equation (3.1), we have
(x())) - (s)
(h, (s)) (r((8,n(s)) (s())
inf Pu (aaug,
Pr VE (8,
inf
Ph ve
(s,
inf (f
[P (s (s))
= -- ())()s(((s))))) (s)) +
inf (s..p
[P Vo 44 (s))
inf P. (3..
PA Weiilss fn)).
To proceed, we denote the worst case transition kernel with respect to the robust value function of म as P (PA [M), where PV (+|s, a) arg inf Pa P. (P, V7 a), then we have
(s)) - V - (s) - (x (s)) + ( - (s,
(G.5)
Applying (G.5) recursively, have
((((s) - V (s)
E E pd [ (h(ssn =
(G.6)
Now it remains bound the robust Bellman error c.(.,-). In particular, we aim show that for all (s, h) E x Ax H].
0 (h(ss))) S 21 (s,
Note that (8 a) = (s. a) + inf Pa (s.. .,. VP [s, - a). Recall the defi- nition of (s, a) in Algorithm and the notation in (E.1), 1), and have
(5(s, a) = (s) +
inf (e - max (r)(s,a)+ +
Ph Do (ss,,a))
inf (1..0
PA Do ( - ()(
If (a(s,a) + inf p (1) PA Do b+ (s, (n S 0. then ch(s,a) (s) +
inf infpa. (P,, / (s.a) 2 If (s, inf (ni 1/
(s) > 0, then we have 5 s, a) = () (ills)/))n (PA VP (P ())
int P. (ls.) [P, V% (s, + (s) - + (s, = 0. where we used the
condition in (D.1). In conclusion, we have ()( 20
On the other hand, we always have
PP Ph Sh (8, a) 5 Pa
inf
inf (.Chaa
[PA DP (s, (a(s,a)
< 2T, , (s)
26

---

Thus, for all (s,a,h) S x A x [H]. we have
S (8) S (T)(s
(G.7)
Combining (G.4), (G.6) and (G.7), we have
H
11 =
SubOpt(ft f, p) s
E
P
E B [
h=1
h=1
E
P
on)ss= =s]
H
ET . (Sh, =
sup (PL)
1=1
2
sup PEUP((P)
18 (Tn(sh;a))) =
h=1
This concludes the proof.
G.2 Proof of Lemma D.2
In this section, prove Lemma D.2. Before the proof, first present several auxiliary lemmas. Lemma G.1 Sefference-Avvantaeee Decomposition). There exist real values {as {as)) where [0, HJ. Vi E [d]. such that
inf [N V (s) P., (xp,,
inf
PA Pp
P2 (s,
K
10, () A.- [EM (s) (s)aal)
oi (1Vt)lla))
(
A
|or(s, ()): A,
( 1| [1)2t - (V A,
iii
d
K
os) A
Th (I - (V)2a)) A
||A?"
[f( 1)).)) for any function f: S + +0, - 1]. where ni, ([f).) = ([P (5% ah)
Lemma G.2 (Bound of Weights), For any E [H]. denote the weight wof = 0₂ + Df in Algorithm 1, then wh. satisfies
|l < 2/ / dK/A.
Lemma G.3. [15, Lemma B.2] Let f S [0. R be any fixed function. For any & E (0, 1). we have
P
Σ o%
Th
2 R2 2 2og ( + d (1
K ))) s 6.
A
Lemma G.4 (Covering number of function class VR.). For any h [H], let V/, denote class of functions mapping from E with the following parametric form
(s) max { aEd (0s
-,, diss, a)) Σz ())
(0.H-
27

---

where the parameters (0.3, mn) satisfy ||0]| S L, 3 e [0, B). (min(E)) 2 A. Assume || - 1 for all (s.a) pairs, and let N₁ (e) be the e-covering number of V with respect to the distance (Vi, V22 sup, (z) - (= Then
log (c) Σ d do + 4L/c) + d' log [1+ Bdl/322/(X2)
Lemma G.5. [47, Covering number of an interval] Denote the e-covering number of the closed
interval [a. b] for some real number b > with respect to the distance metric d(a1, a2) |ai agl
as (N,, bl). Then we have NC 6)) = 3(b a)/e.
Proof of Lemma D.2. To prove this lemma, we bound terms i-iv in Lemma G.1 at each step h E [H] respectively. To deal with the temporal dependency, we follow the induction procedure proposed in [54] and make essential adjustments to adapt to the robust setting.
The base case. We start from the last step H. By the fact that any robust value function is upper bounded by H, then with À = 1, for all (s, a) E S x A, we have
+ S 2H
Σ 1=1
10:(s, a)lill,,"
(G.8)
Next, we bound term ii. Note that V is independent of D, we can directly apply Hoeffding- self-normalized concentration inequality Lemma 1.1 and union bound to obtain the upper bound. In concrete, define the filtration F, (f d U ( J==)) Since V# is independent of 'D and is upper bounded by H, thus we have TH [[v+1la))) ie., E( (a.
mean zero, = 0 and HusuGaausiaa.. By Lemma I.1, for any fixed index i E [d] with probability at least - 5/2dH2 we have
Σ
K
TH (VV
12 A
S 2HH log 2dH2 del (e det 1/2
By the proof of Lemma B.2 in [15], we know det(An) S (A + Ky". Thus, we have
Σ
K
(IV Air 2
log A
A
log 2dH² S dH2 log
2dH K
5
Then by union bound over i [d]. with probability at least 8//2H2 we have
VAH Vo Σ ||,,(1, (1)(ls
(G.9)
where , = log 1/8)2 2 1. As for the term iv, by construction we have #+1 =
Ve
H+1
with probability 1. Thus, we trivially have
i VdH f
(s
(G.10)
Combining (G.8), (G.9) and (G.10), for all (s,a) E S x A, with probability at least 1 - -8/2H2, we have
inf Pa Pall (
Ph Ve 16)
inf
PH Ve +
Pu a.)) (s.an)
4VdHH Vi (lor(s,
(G.11)
Thus, we define (s) = 4VdH 4VdH Ii By the definition of Q (s. a) in Algorithm 1, we have
(s, = (rn(s,a) (s. S <n((s, (s,
28

---

which implies that pessimistic estimation is achieved at step H, i.e., (s) 2 Vs e S. Next, study ( (s). The intuition is that given the estimation error bound in (G.11),
with sufficient data, the difference between ( and (s(s) should be small. Specifically, we have
(s) - (s)ss = (s, - 2t (8, (b) + (i (8)) + Pu( (x,0:)))))) (H( (+))
- 2% (s, R(s))
inf
[H (1(,a))
inf Pa Pu(lba)Eugg
PH v (1,, a) + (n (+))
(G.12)
S 2
where (G.12) holds by the robust Bellman equation (3.1) and the fact that Qn (s)) (n (s)) O. Then we bound the pessimism term F (s, a) in terms of the sample size K. By Lemma L3, when K 2 (oggdH / 4/K), with probability least 1 6/2H?
we have
16 V & = V ( S
oosss
VK
where A = Ex az ( aH) Note that for any positive definite matrix A, we know (A) S Au Amax (A). Thus, by Assumption 4.3, we have
16vdH 2s{(
== Rs-
(G.13)
VK
To summarize, we define the event
En = (0s (/ Vp()) Rn, Vo S).
Then by union bound over (G.11) and (G.13), know En holds with probability least 1 -g 1 - 8/H2. This concludes the proof of the base case.
Inductive Hypothesis.
Suppose with probability at least 6 we have
inf P.))(( ( (2.1)
Pa+1 Do (s,
inf Para(1a,) (1 (1
PA+2 DP (
< <4vdH [ = =s,,,
(G.14)
and
16VdH(H - h)vi
Ext1 = (0 (8) - Vs+1(8)= S Rat1=
as E S}.
(G.15)
VKn
Inductive Step. Next, we establish the result for step h. First, terms i, ii and at step h can be similarly bounded as in the base case, i.c., we have
+ ii S 3VTH Vi M (
(G.
with probability at least 1 - 8/3/12. 2 It remains to bound the term iv and ensure it is non-dominating. Here, need deal with the temporal dependency, [Vr ( (s)]. [V (s)]. is correlated to
(1% Th + thus we need a uniform concentration argument. Consider the function class
(D, B, A) VV 6 8, Σ) + [0. H with ||||| < D, e [o. Ez AI).
29

---

- where 0, = m 0 E Voi(s, Σ (s, No For simplicity, we denote fa,(8) (8) = 1 (6) - [V (s)]ar then sa, Fh+1 (a;), where
Fa+i(a) = (1Vh+1 - (s) Vh+1(Du. B).
Note that for any fixed a, the covering number of Fh+1(a) (a) is the same as that of Vn (Do, Bo, A). By Lemma G.2, we have Do = H / Kd/A. By the induction assumption (G.14), we have Bo = 4vdHI vs. Denote the e-covering of the interval [o, H!] with respect to the distance dist(aj, 02) = |a: - 0g) as (e), and its e-coeernng number as (n For each a E [0, H., we can find ag E Mo. (e) such that a 1--a ael S c. For any fixed E [0, H). we denote the e-covering of Fa+1(a (a) with respect to the distance dist f1, f2) sup, (f( f2(x)] as (e) (short for N D, X)) and its e-covering number as [N)+1(e)]. For each fa E Fa+1(a), we can find
fa E NN++(E) such that sup, (s) fa()) S e. It follows that
K
Σ
th (Ja.))
(llfaello S Rat1} A
<
K
Hink (f (aarn) 11
{ llo S Rat1 +c] + +2
Σ
K
0% (fa()a))
Th (ann))
Rm
Note that
K Σ
2
Σ
S 262 27 (T% - (ot.)))) AT*
f s 222KK//>
7,7'=1
Then we have
K
Σ
(Fa)
1 (llfaulloo S Rnt1)
A5"
k=1
Tinn (san ||
4
1 {llfa 1lo S Ra+1 + 22
Σ tt (far)) nh (f. )) 1)|2=
2e 20² A,²1
+ 4
+
Σ (Fa,) || 1 {1lfa,,loa S Ra+1 + 2c + 6-2
K
<
A
where the last inequality holds by the fact that
k
K
(nT ma
)) 1| S 4e
Σ
$ズ t5 S 122
k=1
7,7'=1
With a union bound over (n) and (1) and by Lemma G.3, we have
K Σ Con II 1 {1lfa, 1oc I Ra+1 + 22}
P
sup ac, ENi. (c) la (Na-1(e)
r=1
K (RA+1 + +cc)2 +2c)2(2log 3dH (c) (M dlog (1 K))}
5
8
3dH?²
Then with probability least 1 8/3dHz for all Sa; E Fnti(as), have
K
1|2 A-
TTn
(llfalloo I Rn+1}
30

---

S 4 inf (Ra+1 + 20)2((11))))) ( 3dHf2 [ + d log (1 ) 600
+ 6c
6e²K² k2
By Lemma G.4 and Lemma G.5 together with Do = H HKdd/A and Bg 4VdH Vi, setting
d3/2 22/2/// H///H//////// (K3// vR) and K 2 V3HH/32/Fk we have log ( - 2d log 1 Thus, we have
AT Σ Ton 1 lbo S Ra+i)
512dH*
(2log
2dH2
4d log
512K 1
KK.
/ H?
20480d 1142
KK
Then, with a union bound over E [d], we have
K
143/ H2,
143x9/2121)
P
sup
T
(IV
24 lla, - (xtilaa))
VK
sE[d]
K
TP
sup iE(d
Σ
(1ll 11 (1V (Vtfila.)
[Vitilai S Rn-13
Ax
1 143/3/2
+ +
IV
Rxt1))
VKK
8
5h+1.
3H²
which implies with probability at least 8 8441, the term iv at step h can be bounded as
143d\/2 d <
Σ
(s)
(G.17)
VKx
Then by union bound over (6.16) and (G.17), if K 20449d H2 /k. then with probability at least
1 25/3H² d have
inf (
Ph P. 1
inf
[P Ve (s.
< <4VaH V Σ ( (n)s,a).
(G.18)
Further, when K (oxx(51log(311///// /0)/ /²2 4/x), by Lemma I.3, with probability least 6/3112, we have
SVaH
Pa(s, S 4v Vo [
(G.19)
VKK
Then by union bound over (G.18) and (G.19), under the event Ert1, with probability at least
1 5/ H 8h+1, we have
V/ (ssss)
(s))
(s)) + (3,
[P (PAVitllsssT Pu
inf
inf
[P ( + +
inf PA(
[A WP (s))
inf
[P Vo V
inf
PA Do 1 (s))
inf
PA Do 16,, a) + Tn(s,
Ra+1 + (s,
(G.20)
31

---

16 - -hvi
16
VKK
VKn
-H
Rh:
VKw
where (G.20) holds by the following argument
inf
Pr Vh क (s))
inf (a
Vp PP
h+ 1 (s))
(
- [P,, Wi xt (s)) [P Ve 1st,
sup (s) (s)
R
(G.21)
where Pr(-|s. a) = anginf P,, (s. PP Ph P h v(s,a) E A, and (G.21) is due to the induction assumption (G.15). Finally, denote
En (0 S h+1 (8) (5+ S Rn Vs E S},
then have P(Ex) S 8u+1 + 8/HH H == dn.
Generalization. By induction and union bound over [H), setting
a) V
10, a) a)1;;la,"
then with probability least 1 26/H²+28// for all (s, a, h) S x A x [H). we have
H6/H²) - 1-dH(H++)0/2H 1-8. 8,
inf Pa (ls,a)))) (s.an)
P V2 ( (
[P Vo 1 a) STn(s,a).
This concludes the proof.
G.3 Proof Lemma E.1
Proof. Note that the conditional variance estimation does not involve any element of model uncer- tainty, and thus the proof follows from Lemma of [54]. Recall that we estimate 1 based on D' as
( Ba)) (0.m - 0 vdH3 (1, (Bn2()))))B)())))o))))))
a)) max (1, [0(s (1,s a)
vKr }
Note that
(p(s,0) a)T Bn)((a)] [0, [ a) [a)] |. - (2)) (PP -PPl)(aaa)((P)xxxlllllllla)))))
()(s,a) ((h2aa)TT).(a)) [r |P | (2, a)
[0( (a.) [0.1] 1al
Φ(s, a)T Bl, 1P +2H ((s, Ba, ((s,a))BB..(a)) (
Note that the estimation error i and ii both come from regular ridge regressions with targets I7/ (s)] and (7 p (*)]ar respectively. Thus, the analysis is standard and for simplicity we omit the details h+1
here and focus on the results: with probability at least 1 8/2,, we have
[ T)TTT 3r, [0. [Ø(s, a)T (a)
0 dH²
(G.22)
VKr
32

---

Then by Theorem 4.4 and Lemma I.3, for all (s,a, 8 A x [H], with probability at least
1 8/2, we have
|Varn VV (s,,)(ss,
< [ h- (s,
- 2H| (P [Vlilla) 2H [Px - [V a)l
VaH
5 VKK
(G.23)
By (G.22) and (G.23) and union bound, know that with probability at least 8, have
(ssssa) aa (a)) [0. - ([(s, a) Br (a)] (o.H| [Vara(V
[ a) T (a)) (0.01 a) 3x.1 (a)] [Var, [Varn
||Var 1 h4 [Var, (a1aals1)))
<0( dH3
VKR
which implies that
dH3
[o((s,) a)
( Br.((a) (0.1 - [ a) (an [o.1 Ō
S
[ara
K
By the fact that the operator min [1, } is order preserving, thus we have
(s a; a) S [ValVi41aalsssd
Further, by the fact that the operator min + is contraction map, (G.22) and (G.23), we have
(s, V (s)
s 1 (s. a) (V. | [V -V (s,
< [bss, a) (a)) [0.113]
Φ0ss a) (.) 10.m1
-
dHH
[Var, Va
VKk
+ ||Varn V7 1ol a)
[Varn[V
dH2
dH3
vdH3
<
+ δ
+ +
VKR
VK
VKx
= =0 dH
VKK
This concludes the proof.
G.4 Proof of Lemma E.2
Proof.
Note that the iiference-advantee decomposition is exactly the same as that in the proof of Lemma G.I, thus have
inf (Cl
inf [P Do 1s) r.(()s.)) (
PA (hui(()))
< (ss (Eth (VAn - - (MMP))))))
reference uncertainty
p (3, 1) (1ER) [1 (s))ar IVA1 (s)]o.] B4h [IV (s)]a, -VVA (s)lo..)
advantage uncortainty
Next, we further decompose the reference uncertainty and the advantage uncertainty, respectively.
33

---

The Reference Uncertainty. Specifically, we have
al (B4M (+))
2 [PPl h- Jo.] (7)
di a)l; (BAR (s)lo. (ai(
0% o2; (1ss))
6 P P 1+11 18%, ap)
K 2 hi (6 Ma:
2/ (as)
En (a:)
( o7:
( oh ac)
K a)1 Mn (a.) (V (s) + Σ oi a)]; 1/ (as)
oh (1V
( as)
| ()):)) (a, E [V
(s) (a))
(hn h+1lm,) (5 a as) (2y((a))
The Advantage Uncertainty.
Similar the argument decomposing the reference uncertainty,
we have
Σ (1 1 B (s)]a (s)a() P.c [1 (s) (s)aa)
<
18, ()s,,))1:lss (11:11))))))
E2 [1)]+ (1)a(())aa) (as)
1=1
K Σ
1 nz (V (s) (s))a))
(0,(8, a));),,)))),))))))))
2 (1)
(oz)
Put terms i-iv together, have
inf
[P Dp
inf Pall (a
Ph Dp ((s
d
<
K
2h (VVi lai
Σ
Th (sh, a7, ac))
(a))
d
A
(0(,s)))1,ll (ae))
E [[Vh (s)lar -VVit [s) (oc)
1=1
K
Thn (LV P (5)]., (V
(
Σ
(%% (z)
E (as)
7=1
34

---

By similar argument as Lemma G.I, we know there exist {āz heeld) such that
inf (e
Ph Ve Pa 1+))
inf
[T Vi 1en (().a))
P E [V (
10: a))(ll)
( h+1la))
pi (8,)))
Σ
(5% O7t: as)
Dx (o))
a1),ll (as)
pua [[ (s))a: (V
x (as)
2 th
h+1 (8))a, -VV+i (s)]ac)
Σ
(5% o7/ os))
m (ā.)
This concludes the proof.
G.5 Proof of Lemma E.3
Proof. By the robust bellman equation (3.1), we know
V (s) Easa (+18) a(),a) +
inf (.
PP h+1 (8,)
(G.24)
Then, we can trivially bound max,es ViT.((s as
max V (P (s) S max (1+ 8.0
inf Pallsaa)
PA (4
(G.25)
S
Further, by the definition of the d-rectangular uncertainty set, we have
inf (l (s.agg))
PA WTil = Σ (1(5,a)
inf PM (eR,)
Eonpa, (s)]
(G.26)
Denoting Smax argmax, sES h+1 (s) and 8min argmin Vo (s), and for all i [d]. we construct a distribution juni (1 p)ln, + pdmmin where 8, is the Dirac Delta distribution with mass on x. Note that üh,s E Uh, (Ph.)), thus we have
inf Eampa, (VTz((s) (s) & Bsnin [+)+(()) s p) max (i pimnn V (s). sES
El, (K..)
(G.27)
Combining (G.25), (G.26) and (G.27), we have max V (s) (1 p) max V (s) + pmn VTT.P (s) + 1. sES
(G.28)
.ES
On the other hand, by (G.24), we can trivially bound min, ViT (s) as min VTT 2 min s.a (e
inf
[P VTT.I((ss))
(G.29)
By the fact that
inf Euf
Esppa, (VT 2 min V (s), SES
(G.30)
35

---

combining (G.26), (G.29) and (G.30), we have
min V (s)
min /+1 (s).
(G.31)
sE$
For any h E [H]. by (G.28) and (G.31), we have
max
VA (
min (s) #ES
#E8
$ 1 (1 p) max V M (s)
min A+1 (s) + p pmin h+i (s)
sES
$E8
= 1 + (1 p) max
TP h+1 (s)
min W (s)]. SES
(G.32)
sES
For step H, by the definition of the value function, have 0 < (TT I 1, E Applying (G.32) with & = H - 1 leads to max,es V (8) min,es V (3) S 11+ (1 - p) 1. We finish the proof by recursively applying (G.32).
G.6 Proof of Lemma F.1
Proof. The proof of Lemma F.l consists of the following two steps:
Step 1: lower bound the suboptimality by Hamming distance. For any & E {-1, denote yy*i(s (s) as the optimal robust value function for the MDP instance Mg. For any function т, denote
V R. as the robust value function corresponding to a policy л. Then by definition, we have
V = max inf (PU)
E (rr((ss),))) + ... + +rH(sH (s) = x1),
a
(x1)= = inf (PO)(
E.. P (11(s1. + ww(ss,, 21).
For any given &, the optimal action at step is
0j = ((1 + f21) ... (1 End)/2).
The worst case transition at the first step is known as
P1 a) = (1 p). (1 a) = p, P1 (222212 = 1, Va E A,
and from the second step on, the state always stays at s2. With these facts in mind, we have
Ve
(x1)
d
d
= of
[1_
+
E11
+ (1 - p) +
Σ
1 E2i
+ .... + (1 - p){ +
+ Eni
+
2
4d
4d
4d
i=1
i=1
i=1
8
[
d
Σ
1 + Eir
+ (1 - p) d
+ E2i
+... + (1 - (1-m)) [p d
+ E11i
2d
2
2
2
1=1
1=1
==1
and
T.
(z1)
RT {
[1a
Σ
+ (1 -
(p)))
p)(a
E202
... (1 (1-p)
[)[[++
d+ Σ Emam
2d
Then we have
Vis
(x))
V
(TT.P((z))
H
5
+ E1i
+ Eni
G.. d1i
+
2d
2
2
1=1
hm2 i=1
8
1 +
Eni
(1
p)
Ere ani
2d
36

---

H
+ EnilE" ( and
p)
2d
h= 1
(1 p)
Σ Σ [1
(2ani 1))-
(G.33)
4d
h=1 i=1
Note that for any (h, i) E [H] x [d]. by design we have 1 Shi thus
8
(2ani 1))
(1
p)
(Eni E (2ans 1))
4d
4d
h=1
1=1 ==1
8
(1 p)
She E7 (2 1)1, (G.34)
4d
where (G.34) holds due to the fact that IE" (2an: - 1) E [-1, 1].
To continue, we have
6
(1
Ehi E= 1)1
4d
8
H
d
p)
Eh - B"(2ans 1)1 1 {E + sign(EE* (2an,; 1))}
4d
h=1 i=1
6
H
(1 p)
11 (Eni * (a 1))}
4d
i=1==
6 (1 - (H.
(G.35)
4d
where D is the Hamming distance, E" = (E% hhe hee and E% sign (ign(EF(2anr) 1)), Vi [d]. Combining (G.33), (G.34), (G.35) and the definition of the suboptimality gap, we have
8
SupOpt(Me 31, u, 4d (E.EEE
(G.36)
Step lower bound the hamming distance by testing error. Lemma 2.12], we have
Applying Assouad's method [46,
inf sup E& (E.(EE)))) EEE
2
dH 2
min En D (E:")))==
inf [Qc(V(D) * E) + (v(D) x5)
(G.37)
where inf denotes the infimum over all test functions taking values in ( We conclude the proof by combining (G.36) and (G.37).
G.7 Proof of Lemma F.2
Proof. By the Theorem 2.12 in [46], we lower bound the testing error as follows
min inf Ce(()(D) + {) Qe (L)(D) # EA) E (..
(1 max 2...
21
DEL (Qel (Qel)
where (-I.::Il)) is the Kullback Leibler divergence. Then remains bound DRI. (Qel) According to the definition of Qg (D). we have
K H
Qg (D) = III
II
o Th ( Pa R(st df:r)))
Am/
37

---

AL. where R(sh: o is the density function of (r (s) ), 1) at rx Note that the difference between the two distribution Qe (D) and (D) lies only the reward distribution corresponding to the index where and ç' differ. Then, by the chain rule of Kullback-Leeible divergence, we have
DEL (D) (D)) = Σ
DKL (N(
(N
(
++1 5,1)
d (1-1 I
0.1)) 2d
K 8²
2d
d + 2 d2
1=1
Then by our choice have
K8a
1/2
inf Cc(W(D)+ +E) Qe 5 (.
min
21
2(d + 2)d
K8a 1/2
2 1
2d
2
This completes the proof.
G.8 Proof of Lemma F.3
Proof. Recall that
TTTT VAV (3% x
We first show that with sufficiently large K, the clipped conditional variances of the optimal robust value functions are always Note that (**((())) (xz)
0, vh [H], and
5
+ EHi
(z1)
d 8
2d
2
5
EH-
V (x1)
+ d + VH S 26,
2d
d
+
Ezi
(g 2d
+ + V33 (x1) & (H - -)
1=1
Then, when K 2 2 we have
Var, 1a (I1, a) =
((P((1()))))) (2), s (1-p) $
and by design we have,
|Vari V22 (x22 a) = and [Vara =)) V(s,a, ES (1/[11.
=
Thus, we have VV.V (1%, af)) 1, which implies
M = An.
(G.38)
Define
A
F E p
(ss (nnn on) J1
then by definition we have
0
2
))
0
0
0
0
0
0
0
1
1
1
A
+
2
0
0
0
d + 2
4
0
0
(1
-
2
0
1
)))
0
(1
1
38

---

0
0
0
222
d
0
0
0
0
0
0
0
0
d 2
100
1
de
0
(1
00
d
+
0
(1
7
2
1
(1
4
4
0
0
Denote
0
0
2
2
D
4)
4)
4)
d
4)
2) +
then by Gaussian elimination, have
2d 2d + d
d3 - 22 + d
d
2d + d d - d
d3 21 + d
28
28 + d
2d +
- d
D-1
d3 8 21 d
d - 2 +
28 28
d d
d - &
d- d
d d2
d
Note that
D 0
A
=
d+2
0 1
then we have
A d+2 2
D-1
0
d
Note that Amin (D) O(1/d)), thus || = (dd)). Then when K Ö(d)), for any (s,a,i,h)
S A x [d] [H). with probability at least 1 - 8, we have
2
(1b((s,a):llan S
(G.39)
K
With this in mind, have
E P
|1 a) (1)l:;)))1 x11
sup
PEMe(PP)
h=1
i=1
H
sup PPU)
1
[ an 1i)l,,,, 21
4=1
39

---

H
d
sup
13
[ an)1,a/ R, 1181 21
(G.40)
PEMP((P) (PO)
K
h=1
H
2
(sh,, an ) )A 1/22
sup
81
(P
K
h=1
1=1
4/2
VK
where (G.40) is due to (G.39). This concludes the proof.
H Proof of Supporting Lemmas
H.1 Proof of Lemma G.1
To prove Lemma G.I, we need the following proposition on the dual formulation under the TV uncertainty set.
Proposition H.1. (Strong duality for TV [42, Lemma 4)). Given any probability measure dº S, a fixed uncertainty level p. the uncertainty set (1)) = {1= : E (SS), (rv(u))")) S p). and
any function V [0, H]. we obtain
inf pE
Esng (s))
max
{ (V - p(a (ain(V(s')la))
(H.1)
Qe[Vmin. V Viao]
where (s)]a min (().. a), Vinin min, (s) and Viax max, V(s). Notably, the range of can be relaxed to [0, H] without impacting the optimization.
Proof of Lemma G.I. By Assumption 3.1 and Proposition H.I, we have
inf
Pr V 1
inf (1.001)
[P VP Ph
(s a)
p(a (minmi](//+1s)))) max 1 [1/ h+1 (s)la (1/22
at [.H
1=1
(ith [V (8)] p(aa- (
max
eE
Denote 0; argmax (E [T ppla minn 1V (8 (a)) then we have
inf (C
PA (s
inf
P Vp 1e
PA (
(s (4 (s)]a, - Ech. (1 (s)lar)
Σ
( a) 1 Fd (i 1. Tu (VP (s)
E
Here we do reference-advanteen decomposition by using the optimal robust value function as the reference function. Specifically, have
inf Ph PaCl (s.a
[P Di 1(,
inf (r.
IP Ve ((s,,
(1(8 [1] ( [[ (s)lo, IVA (+)]o, +
1. [ [ [1 (s)lo (s) + [V (s)lor))
40

---

a)) (Buh (s)la, - EuR [v (s)las)
reference uncertainty
(s(s,a)17 (B (V (s)]o.]
Buh [1V (t))aa -IV (s)lo.))
advantago uncortainty
(H.2)
The Reference Uncertainty.
First, we bound the reference uncertainty. Specifically, we have
(B
Buui [V (s)la)
(s
E [V -A, Σ
Φ P 2411a (5% a7))
K
K
0% PP (sh - A
Φ V h+1 (s Ma.
(1 m) [B4 - -A, Σ
E
[V h+1 (8)]ac
1
[V (sa+)))as))
For any function f + 10, H - 11. we define mh (1f)a.) = ([PR[))..] (8) - 10(5%+1)la.).
Then, have
( a)1 ( [V14 - Tua (1))())))))
( a) A A (Vin
(1(5 A Σ Ti (VV
l6:(ss A5 [V+
Σ कinn (IV
(H.3)
The Advantage Uncertainty. Next, bound the advantage uncertainty. By similar argument in bounding the reference uncertainty, we have
(1 ?
[V (s)la,
Bug
(s)aa))
<
A
10 [12 -1l
[
K Σ
+
[0,(8, ((6,a))1llA,-11
-V (ViHH( |AA;"
(H.4)
1=1
41

---

Combining (H.2), (H.3) and (H.4), we have
inf (s,
PA PP Ve (s)
inf (
PA D (+t)(s,
K
|B (+)a(()) (0,(s, ailll,
Σ
oh th (V (+1la:) A5
1
a):sl N..
B k
(s) (())
1V (s) I|
A5
2=1
ii
d
K
(d:(s,a)1illx
Σ
ohnn (
(+)z)))) ( |AA
On the other hand, we can similarly deduce
inf
[P 1ls,
inf PaClo.0)Elf
[P V. ((),0)
(d)(s,a)111)
|BM (+)) +
10:(s, a0
Σ
कx n (VV (+tll;)) A5
ii
( al)lll A7,
B [IVR (s)la; (+)9(())a A.
21
ii
d ( | oh (1V -1 I|, Σ
K
where a; argmax (Eah. ( p(a min (s')ll))aa)) Then for all [d].
there exist 0; {ar, ). such that
inf (a. [P De (8)
inf (1
[Px Dp ((s
K
[0,(3, ())ss,))ill | ( (s)]a, + Σ 10: a))saa)):l
Σ को (1Vtlaa)))))
A7
()) A..
| [1Ve (s)]a. - (Vr (s) Ar
1=1
K
(0)(),))1:ll1=)
Σ
th (PP - (V)2
This concludes the proof.
H.2 Proof Lemma G.2
The proof of Lemma G.2 will use the following fact.
42

---

where Φ; E R² and À > 0. Then: Lemma H.2. [14, Lemma D.1] Let A, = + Ei=1 0
Φ (At) (At) (At) 8: S d.
Proof of Lemma G.2. The proof of Lemma G.2 is similar to that Lemma E.1 in [20]. Denote
ag = argmax (a, p(a ming [V [ (s la)),, E [d]. For any vector v E R we have
[ =
v On +
max (a) - p - min [V (5 1o)3 1E[4]
aE(0.H]
$ |O
0^ + p
max (a) - p(a - min| Vi ]a]] iE(d]
aE(0.11
s Vallul12 H1 1
1
A
mmxx 1 (8h+1:
(H.5)
iE(d]
K
K
I /d + Hvdluul22 +
Σ
v
A
Σ (Ø))) A 0
(H.6)
22H1O0|22 dK/A.
(H.7)
We note that the term KA, Σx= Imax, a)) )ilied)
taking out the i-th coordinate of the ridge solution vector, A Σ [mmxx Qh+1 ( a)la, e a))a, in (H.5) is constructed by first
Rd. Vi [d]. and then concatenating all d values into vector. Inequality (H.5) is due the fact that P.S. (H.6) is due to the fact that Q/++1 S H. and (H.7) is due Lemma H.2 with K and the fact that the minimum eigenvalue of A is lower bounded by A. The remainder of the proof follows from the fact that ||r maxp:||o||a=] (v wfl.
H.3 Proof Lemma G.4
The proof of Lemma G.4 will use the following fact.
Lemma H.3. [14, Covering Number of Euclidean Ball] For any 6 > 0, the c-covering number the Euclidean ball in Rd with radius R is upper bounded by + 2R/e)
Proof of Lemma G.4. The proof is similar to the proof of Lemma E.3 in [20]. Denote A -3 so we have
Vx(+) = max (b(s a) a aEA
Σ V a 1=1
a)) [oH
(H.8)
for ||0|| < L, ||||| S B2X-1 For any two functions V,, V/2 E V, let them take the form in (H.8)
with parameters (01, A1) and (0z, A2), respectively. Then since both (-)0.--441) and max, contraction maps, we have
d
dist(Vi, 1/2) < sup 2,a
0 (Tx
Σ
A A
i=1
0 (1) a)
Σ
V [1(x,
(201
1
sup 0:1101<11
0 TT
Σ
V
1.11
A db.,
00 Σ V d211 A20.1;
i=1
i=1
sup d:110111
(0) - 02) Φ +
sup
Σ
6117 (Ai - A2)
(A,
(H.9)
i=1
43

---

d
- |10 0211 + VIIAA
Agl
sup *1
|+11
|00 021 VIA A2
(H.10)
where (H.9) follows from triangular inequlaity and the fact that | V S V y/, Yx, y 2 0. For matrices, -| and -1e denote the matrix operator norm and Frobenius norm respectively.
Let Co be an e/2-cover of (0 R2
||0112 S 1.} with respect to the 2-norm, and CΛ be an e² /4-cover with respect to the Frobenius norm. By Lemma H.3, we know:
of {A E [|A||r & / B
Col (1+ 4L/e |Ca S [1 + /2 (>xe)]
By (H.10), for any V/1 E V, there exists 02 E Cg and Ay CA such that 122 parametrized by (02, A2) satisfies dist(V, V1, 1/2) S Hence, it holds that No S |Col [Cal, which leads to
log I log [Cw, log [Cal S d + 4L/e) + de log [1 /2 / (AE?)
This concludes the proof.
H.4 Proof of Theorem B.1
In this section, we give the proof of Theorem B.1, which largely follows the proof of Theorem 5.2, only with minor modifications of the argument of the variance estimation.
The following lemma bounds the estimation error by reference- advanttage decomposition. Lemma H.4 (Modified Variance-Aware Reference-Advantage Decomposition). There exist (as)iejat where a; E [0, HJ, Vi E [d]. such that
inf Patlssa)E3 (s.
Ph PP (s)
inf PA. (
Ph V/ 11t,a()saa))
2 m (1
10, a) E | 1 (8))as 1 + <
Σ (10
( (5)
| [1V2 (s)lo.
(V)2(())an x
iii
K Σ
TTnn
(s) -IV (s)lar) /
as) x
(3% (7))
E
1v
where TT, (ff...) ([P9 (5% a7) - [f 1),.), for any function + 1].
Proof of Theorem B. I. To prove this theorem, bound the estimation error by Tn(ss, a), then invoke Lemma D.1 to get the results. First, we bound terms i-iv in Lemma H.4 at each step h e [M] respectively to deduce (s)
Bound and ii:: We set = 1/H² to ensure that for all (8,a, h) E S x Ax [H],
we have
it VAvaH dh
a)) Vd Σ 10,(s, 1z,
(H.11)
[0. HJ. by definition we have o (8. > 1. Thus, for all T,i) E [ x [K] x [d], we have 7 (VVt))))))/ (87,,7) S H. Note that V is in- dependent of D. we can directly apply Bernstein-type self-norme norm-norma concentration inequality
Bound ii: For all (8, a) E S A
44

---

Lemma I.2 and a union bound to obtain the upper bound. In concrete, we define the filtration Fr-1, (f(5), ) U (+ Since V and 2 (8, are independent of D, thus
oh (VV-- //0 (8%, ( is mean-zero conditioned on the filtration F4 By Lemma E.1 with H, we have
V (i. 0
dHf
S (s,
[VVV
(H.12)
KK
thus, for any or E [0, HJ. we have
dH3
dH3 VKR S (8)
ValV (s, -
VVVVit (8, 0
(H.13)
VKR
Further, we have
Mh (1V (+1l,))
32 [
E
(H.14)
(5h 07)
(5 o
( a%)
M (7)
Ō(dH Ō(dH² /VK))
( aT))
(5 a5)
Ó(dII //////KK)
< +
(H.15)
(5% ag)) ((d13/VKK)
dH3
< 1 20
(H.16)
VKK
where (4.14) holds by the fact that (: is independent of D and (%)))%) is Fr measurable. (H.15) holds by (H.13), and (H.16) holds by setting K 2 (d(d (o/(HH/K)) such that (5% ox)) O(dH3/VKK)) 2 - ((dHH//VK 2 1/2. Further, by (H.16), our choice of also ensures that E (n [ | O1). Then by Lemma I.2, we have
(VV+ ( a7))
|
1..50n Ö(va). E
This implies
d s v Σ
(H.17)
Bound iv:
Following the same induction analysis procedure, we know that Ö(VaH² /VK)). Using standard c-covering number argument and Lemma I11, we have
<
S Ö 1
(H.18)
VKR
To make it non-dominant, we require V a,),, which implies that
2 H(d2H*/k) /k). By (H.12), we have (3 aj)) s
+M)
क
+ +a1)
Vv V 15 o.
Combining (H.1l), (H.17) and (H.18), we have
inf (5.
P. D (s,,
inf P.(lss.) (s.oph..))
[P iR ( a)
s <Ō(vd) Σ | 1)llly
Define (s) Ō(v En 11,: ())lss) we concludes the proof by invoking Lemma D.I.
45

---

I
Auxiliary Lemmas
Lemma 1.1 (Concentration of Normalized Processes). [1, Theorem Let {&]f= be real- valued stochastic process with corresponding filtration (Fi) Let e be mean-zero and o-subGaussian; i.e. Fe-1 0, and
E R Ele Fr-1l S 2902/2
Let (0t) be -aluee stochastic process where Φ; is F measurable. Assume Ag is x d positive definite matrix, and let A, Ag +EE Φ. Then for any 0, with probability least 1 - 8, we have for all 2 0:
- 20² log del(AA) den) -1/21
Σ SSE
A,
Lemma 1.2 (Bernstein inequality for self-normalized martingales), [65, Theorem 2] Let (mdee be real-valued stochastic process. Let {Fi)i=o be filtration, such that n/ is Fr-meaurabbl. Assume also satisfies
Ie S R, Em F = 0, Fi-1l 5
Let (ata) 1 be an RRd -vauued stochastic process where is F;-1 measurable and | S L. Let
A, ALa + E s=1 T.x.. Then for any 5 > 0, with probability at least 6, for all > 0,
tL? )L2) Ad
4t2
4t
Σ Jg
S 80 d 11+
log
4R log
Lemma L3. [27, Lemma H.5] Let Φ : S AxAAA - Rdd satisfying |1 a)l s C for all (z, a) E SxA. For any K> and À > O, define GK Ex= Φ( ax) (x)(( ax) + AI where (It, ak) 's are
ii.d. samples from some distribution over S x A. Let C pl, a) ol a) J. Then, for any 5 e (0, 1), if K satisfies that
K max 512C log
2d
41
|-
then with probability at least 1 - 8, it holds simultaneously for all u E Rd that
2
|| Gx 5
|uull 1.
VK
46

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We accurately summarize the paper's contributions and scope the abstract and introduction (Section 1).
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: In Section 6, we claim that there are small gaps between the upper bounds in Theorem 4.4 and Theorem 5.2 and lower bound in Theorem 6.1. The computation tractability is discussed in Remark 4.2 in Section 4. The assumptions are formally stated in Assumption 3.1 and Assumption 4.3.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged
the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
47

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: The assumptions are formally stated in Assumption 3.1 and Assumption 4.3. Complete proofs are provided in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification:
The code of our implementation is available at https://githe: com/ panxulab/Offline Linear-D-D-n-
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access hosted model (e.g.. in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (c.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
48

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
The code of our implementation is available at panxulab/Offline Linnne--nn-r--
Justification:
com/
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips. cc/
weaibbmissiooooiccyy... for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: / //iiss... wwwpccccppc/..ec..c...ccce.cetle caublic/guides.//e/ /ttgggguiee/eeeuuaiiiiiii SCodeSuumissionn seiobbiiiisiooocccccc..oo for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification: The code of our implementation available at https://github..om com/ httpaaaa/ettiiiiiii-er--r-----aa
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer:
[NA]
Justification:
Not applicable to our experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
49

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: All information is provided in the experiment section and the code of our imple- mentation is available at https: / / thub. com www.:cwww..acccccco hiie/offiine--ieerrrr
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: attps://neur: //terr/ps....eeeeeeeeeee wwwpuriis.ccpppullpeeee cc/public/ Etthi csGuidelines"
Answer: [Yes]
Justification: the authors had reviewed the NeurlPS Code of Ethics and confirm that the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: this work focuses on the theoretical side of robust RL, and methods this paper do not lead direct path any negative applications.
Guidelines:
50

---

The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g.. gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: the paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: the paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
51

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: the paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/codeemoodel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: the paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: the paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
52

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
53


Reviews:
[{"review_id": "bEt4ZZIoti", "reviewer": "Reviewer_mtm1", "summary": "This paper presents a theoretical study of distributionally robust MDPs. Their findings show that function approximation is both different and harder in robust RL as compared to offline RL. They show matching information theoretic lower bounds for their novel algorithm.", "questions": "There is also literature on theoretical multi-task RL, which while not focussed on the distributional robustness aspect, still tackle the problem of planning in an environment with uncertain dynamics. For example see : https://arxiv.org/pdf/2402.12570 and follow up works. I'd like the authors to cite and write the differences to Theorem 1 of the referenced paper, which use function approximation for the representation as well, and come up with uncertainty gaps for different state action pairs of the transition model, and still give a suboptimality gap on the policy planning in the downstream target task (see Theorem 2).", "limitations": "There are no significant technical limitations of this paper.", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper has positioned itself and it's improvement over past work really well (Table 1).\n2. The paper's result about the information theoretic lower bound has a lot of theoretical value.\n3. The appendix is well written and the proofs are sound.", "weaknesses": "1. More motivation on practical scenarios where DRMDPs are applicable will be useful.\n2. Small simulation examples would further strengthen the paper to ensure that the constants in the sample complexities are reasonable.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for your positive feedback on our work. We hope our response fully addresses all of your questions. \n\n---\n### 1. More motivation on practical scenarios where DRMDPs are applicable.\n\nIn many real-world applications, the agent only has access to a **single** source domain, which can be different from target domains where the policy is deployed, assuming the same task is being performed. Importantly the target domains are **unknown** and can vary during deployment. Given the limited information and large uncertainty, one may hold a pessimistic perspective hoping the learned policy is robust enough that would perform well even under the worst-case transition. This basic idea leads to the DRMDP framework, which models the unknown target domain in an uncertainty set defined around the source domain.\n\nWe take the control of infectious diseases for an example. Suppose we have access to a simulator (source domain), which emulates one specific real-world disease infection process (target domain). However, the simulator does not have perfect knowledge about the complex real-world environment, but it is reasonable to assume that the real-world environment is close to the simulator, thus lying in an uncertainty set around it. Notably, the real-world environment can be any environment in the uncertainty set, and the DRMDP framework provides a worst-case guarantee for policies learned merely through the simulator. \n\n---\n### 2. Sample simulation examples.\nThanks for your suggestion. We have done some experiments to verify our proposed algorithm. Please see the overall response for more details.\n\n---\n### 3. Literature on theoretical multi-task RL.\n\nThank you for bringing this work to our attention. We will add the following paragraphs to the related work section.\n\nBesides the distributionally robust perspective to solve the planning problem in a nearly unknown target environment, another line of work focuses on transfer learning in low-rank MDPs (Cheng et al., 2022; Lu et al., 2022; Agarwal et al., 2023; Bose et al., 2024). Specifically, the problem setup assumes that the agent has access to information of several source tasks. The agent learns a common representation from the source domains and then leverages the learned representation to learn a policy performing well in the target tasks with limited information. This setting is in stark contrast to the setting of DRMDP, where the agent only has access to the information of a single source domain, without any available information of the target domain, assuming the same task is being performed. This motivates the pessimistic attitude of the distributionally robust perspective.\n\nAmong the aforementioned works, Bose et al. (2024) studied the offline multi-task RL, which is the most closely related to our setting. In particular, they investigate the representation transfer error in their Theorem 1, stating that the learned representation can lead to a transition kernel that is close to the target kernel in terms of the TV divergence. Note that the uncertainty is induced by the representation estimation error, which is different from our setting assuming that the uncertainty comes from perturbations on underlying factor distributions. Nevertheless, this work provides evidence that TV divergence is a reasonable measure to quantify the uncertainty in transition kernels and motivates a future research direction in learning robust policies that are robust to the uncertainty induced by the representation estimation error.\n\t\t\t\t\n\n---\nWe hope we have addressed all of your questions/concerns. If you have any further questions, we would be more than happy to answer them and if you don’t, would you kindly consider increasing your score?\n\n---\n\n**References**\n\n[1] Rui Lu, Andrew Zhao, Simon S Du, and Gao Huang. Provable general function class representation learning in multitask bandits and mdp. Advances in Neural Information Processing Systems, 35:11507–11519, 2022. \t\n\t\t\t\n[2] Yuan Cheng, Songtao Feng, Jing Yang, Hong Zhang, and Yingbin Liang. Provable benefit of multitask representation learning in reinforcement learning. Advances in Neural Information Processing Systems, 35: 31741–31754, 2022. \t\n\n[3] Alekh Agarwal, Yuda Song, Wen Sun, Kaiwen Wang, Mengdi Wang, and Xuezhou Zhang. Provable benefits of representational transfer in reinforcement learning. In The Thirty Sixth Annual Conference on Learning Theory, pages 2114–2187. PMLR, 2023.\n\n[4] Bose, Avinandan, Simon Shaolei Du, and Maryam Fazel. \"Offline multi-task transfer RL with representational penalization.\" arXiv preprint arXiv:2402.12570 (2024).\n\n[5] Zhishuai Liu, and Pan Xu. \"Distributionally robust off-dynamics reinforcement learning: Provable efficiency with linear function approximation.\" In International Conference on Artificial Intelligence and Statistics, pp. 2719-2727. PMLR, 2024.\n\n[6] Ying Jin, Zhuoran Yang, and Zhaoran Wang. Is pessimism provably efficient for offline rl? In International Conference on Machine Learning, pages 5084–5096. PMLR, 2021.", "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": "TkRqWMZDW2", "reviewer": "Reviewer_Qkxw", "summary": "This paper considers the distributionally robust Markov decision process (or sometimes robust MDP in the literature). In particular, it considers the linear RMDP with $d$-rectangularity TV uncertainty set, which decouples the uncertainty set from the state-action pair. Two algorithms are proposed to solve this, with the second algorithm being an improvement to the first. Extensive analysis is provided.", "questions": "1. Can authors provide more comparison with existing linear MDP with $d$-rectangularity? So besides the difference in the type of uncertainty set used, can you compare your work with [1] in details, especially the results and methodologies? \n2. Continuing the first question, in particular, I noticed that your coverage assumption is stronger than [1]. It seems that you need the behavioral policy to cover states and actions that the optimal policy seldom visits as well. [1] states that with pessimism, they are able to achieve single-policy concentrability (w.r.t. only optimal policy). Could you share some insights?\n\n[1] 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:2209.06620, 2022.\n\nMinor things\n1. Question marks on line 618", "limitations": "No other limitation I'd like to bring up", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is well-written and easy-to-follow\n2. Results are strong and thorough\n3. Problem is well-motivated by introducing a hard instance (lower bound results)", "weaknesses": "1. Comparison with other existing works is a bit unclear", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for your positive feedback on our work. We hope our response will fully address all your questions. \n\n---\n### 1. Comparison with Ma et al. (2022).\n\nWe acknowledge that Ma et al. (2022)’s work is most closely related to ours. However, we note that there are several technical flaws in their paper. We summarize the main issues here:\n\n  (i) The proofs of their main lemmas (Lemma D.1 and Lemma D.2 in the arXiv version) related to suboptimality decomposition and the proof of theorems are incorrect.\n\n  (ii) The sample complexity results for the two algorithms are both incorrect on the order of $d$.\n\n  (iii) Assumption 4.4 on the dual variable of the dual formulation of the KL-divergence is too strong to be realistic.\n\n  (iv) The concept of mis-specification in Section 5.2 is not well-defined, which makes results in Section 5 vacuous.\n\nGiven these technique flaws, we believe the fundamental challenges of $d$-rectangular linear DRMDPs are not properly addressed in their work. It is also unsure whether $d$-rectangular linear DRMDPs with KL-divergence uncertainty set are solvable by their current methodologies. \nMoreover, in our work, we start with the setting of $d$-rectangular linear DRMDPs with TV-divergence uncertainty sets. We address the essential challenges and explore the fundamental limit of $d$-rectangular linear DRMDPs. In the next version of our manuscript, we plan to add a paragraph discussing the comparison with Ma et al. (2022) in detail and further elaborate on our contributions.\n\n---\n### 2. Stronger coverage assumption.\n\nFirst of all, Assumption 5.1 in Ma et al. (2022) is problematic, since the right hand side has an additional dependence on $d$, which makes the right hand side unreasonably large. The assumption 5.1 should be in this form: there exists some absolute constant $c>0$, such that for any $(i, h, s, P) \\in [d]\\times[H] \\times \\mathcal{S} \\times \\mathcal{U}^{\\rho}(P^0)$, we have\n$$\n\\Lambda_h \\succeq \\lambda I + K\\cdot c \\cdot \\mathbb{E}^{\\pi^{\\star},P}\\big[(\\phi_i(s,a)\\mathbf{1}_i)(\\phi_i(s,a)\\mathbf{1}_i)^\\top |s_1=s \\big],\n$$\nwhich is exactly the robust partial coverage assumption in Blanchet et al. (2023, Assumption 6.3).  \nOn the one hand, a closer examination of Assumption 3.3 in our paper reveals that it guarantees a weaker version of the robust partial coverage assumption: there exists some constant $c^{\\dagger}>0$, such that for any $(i, h, s, P)\\in[d]\\times[H]\\times \\mathcal{S} \\times \\mathcal{U}^{\\rho}(P^0)$, we have \n\\begin{align}\n     \\Lambda_h \\succeq \\lambda I + K\\cdot c^{\\dagger}/d \\cdot \\mathbb{E}^{\\pi^{\\star},P}\\big[(\\phi_i(s,a)\\mathbf{1}_i)(\\phi_i(s,a)\\mathbf{1}_i)^\\top |s_1=s \\big].\n\\end{align}\nNevertheless, Assumption 3.3 does not directly imply the robust partial coverage assumption. On the other hand, assumption 3.3 is essential in achieving the minimax optimality of our algorithm. A similar phenomenon also appears for the non-robust offline RL with linear function approximation. Specifically, leveraging the pessimism principle, Jin et al. (2021) show that the partial coverage assumption is enough for the provable efficiency of offline RL with linear function approximation. However, to achieve minimax optimality, Yin et al. (2022) and Xiong et al. (2022) show that a stronger full-type coverage is needed.  Lastly, in a concurrent work (Wang et al, 2024) of ours, the same assumption is also required to achieve tighter dependences on $d$ and $H$ (see Assumption 4 and Theorem 2 of their paper).\n\n---\n### 3. Question marks on line 618.\n\nThanks for pointing out this typo. We have fixed it in our manuscript.\n\n\n---\nWe hope we have addressed all of your questions/concerns. If you have any further questions, we would be more than happy to answer them and if you don’t, would you kindly consider increasing your score?\n\n---\n\n**References**\n\n[1] Ying Jin, Zhuoran Yang, and Zhaoran Wang. Is pessimism provably efficient for offline rl? In International Conference on Machine Learning, pages 5084–5096. PMLR, 2021. \n\n[2] Xiong, Wei, Han Zhong, Chengshuai Shi, Cong Shen, Liwei Wang, and Tong Zhang. Nearly Minimax Optimal Offline Reinforcement Learning with Linear Function Approximation: Single-Agent MDP and Markov Game. In International Conference on Learning Representations (ICLR). 2023.\n\n[3] Blanchet, Jose, Miao Lu, Tong Zhang, and Han Zhong. Double Pessimism is Provably Efficient for Distributionally Robust Offline Reinforcement Learning: Generic Algorithm and Robust Partial Coverage. In Thirty-seventh Conference on Neural Information Processing Systems. 2023.\n\n[4] Wang, He, Laixi Shi, and Yuejie Chi. Sample complexity of offline distributionally robust linear Markov decision processes. arXiv preprint arXiv:2403.12946 (2024).", "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": "4TlfQaR8SI", "reviewer": "Reviewer_nZV5", "summary": "This paper proposes minimax optimal and computationally efficient algorithms with linear function approximation in the context of distributionally robust offline RL. The authors incorporate multiple new techniques in theoretical analysis, e.g., variance information, suboptimality and estimation uncertainty decomposition, robust value function shrinkage, and family of hard instances.", "questions": "Please see the details in \"weakness\".", "limitations": "There is no potential negative social impact of this work.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. The paper is technically sound with most claims supported sufficiently.\n2. The theoretical analysis seems novel.", "weaknesses": "Quality:\n1. In Line 175, the expression requires calculating the minimum value of the entire space. This operation is computationally intractable when considering continuous state space, which violates the \"computationally efficient\" claim made by authors. \n2. In Line 202, I don't find Assumption 4.1 and Remark 4.2 in the paper. Additionally, the \"fail-state\" assumption doesn't necessarily hold in multiple MuJoCo environments, i.e., some environments have negative minimum values.\n3. There are no experimental results provided in the paper. Although it is a theoretical paper, it is better to include some toy experiments to verify the proposed algorithm.\n\t\nClarity:\n1. Since the authors only focus on linear function approximation, it is better to clarify it in the open questions (Lines 51-52).\n2. (Lines 97-98) Assoud's method -> Assouad's method? Additionally, it is better to provide references about Assouad's method.\n3. (Lines 201-203) It is better to provide references about the Nelder-Mead method.\n\nSignificance:\nThere are several works providing theoretical guarantees for general function approximation in online robust RL (e.g., [58]) and offline RL (e.g., [Chen and Jiang, 2019]). Some discussions are missing about why general function approximation is not considered here for offline robust RL settings. \n\t\t\n[Chen and Jiang, 2019] Information-Theoretic Considerations in Batch Reinforcement Learning, ICML 2019.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for your valuable time and effort in providing detailed feedback on our work. We hope our response will fully address all your questions. \n\n---\n### 1. Computational tractability.\n\nWe would like to note that we discussed the computational tractability of our algorithm on Line 178 - Line 203. Specifically, if the ‘fail-state’ assumption holds, then the minimal value is trivially equal to zero hence no computation is needed. If the ‘fail-state’ does not hold, we can use some heuristic methods, such as the Nelder-Mead method, to search for the minimal value. Thus, our algorithms are in general computationally tractable. We have also conducted numerical experiments to show the computational tractability of our algorithm.\n\nIn terms of computation efficiency, 1) our algorithms leverage the linear function approximation, and do not need to estimate the robust value at each state-action pair as those methods developed for the tabular DRMDP setting; 2) Moreover, thanks to the structure of linear DRMDPs, we do not need to solve the dual problem at each state-action pair. Thus, our algorithm is computationally efficient compared to those methods developed for tabular DRMDPs and general $(s, a)$-rectangular DRMDPs. This is consistent with the claim of computationally efficient algorithms in theoretical RL (Jin et al., 2019, Xiong et al. 2022, Yin et al. 2022), which stating the runtime and the sample complexity should not depend on the number of states, but should depend instead on an intrinsic complexity measure of the function class.\n\n\n\n\n---\n### 2. In Line 202, I don't find Assumption 4.1 and Remark 4.2 in the paper. Additionally, the \"fail-state\" assumption doesn't necessarily hold in multiple MuJoCo environments, i.e., some environments have negative minimum values.\n\nWe believe there is a misunderstanding. Here we are discussing previous work’s assumption 4.1 and remark 4.2 (Liu and Xu, 2024:  https://proceedings.mlr.press/v238/liu24d/liu24d.pdf).\nWe highlight that our work does **not** need the fail-state assumption. For environments that the fail-state does not hold, we can 1) either modify the reward of the environment to rescale the minimal value (of an absorbing state) to zero, which creates a fail-state, or 2) use heuristic methods to search for/approximate the minimal value.\n\n---\n### 3.  Numerical experiments\n\nThanks for your suggestion. We have done some experiments to verify our proposed algorithm. Please see the overall response for more details.\n\n---\n### 4. Clarify the linear function approximation in the open question.\nWe will revise the open question as follows: Is it possible to design a computationally efficient and minimax optimal algorithm for robust offline RL with linear function approximation? \n \t\t\t\t\t\t\n---\n### 5. Typos and references.\nThanks for pointing out these issues. We have revised the typo and added the references.\n\n---\n### 6. Justification of why linear function approximation rather than the general function approximation is considered in this work.\nIn this work, we focus on offline DRMDPs with linear function approximation under the setting of $d$-rectangular linear DRMDPs with TV-divergence uncertainty sets, which is an understudied area with unique fundamental challenges compared to standard offline RL. It would be an interesting future research direction to incorporate general function approximation techniques, such as those in Chen and Jiang (2019) into offline DRMDPs. We would add the following paragraph in the introduction section to motivate our setting: \n\nAlthough standard offline MDPs based on linear function approximation have exhibited theoretical success (Jin et al., 2021; Yin et al., 2022; Xiong et al., 2022), DRMDPs with linear function approximation remain understudied. In particular, DRMDP encounters unique difficulties when applying linear function approximations, even when the source domain transition kernel is linear. The dual formulation in worst-case analyses induces extra nonlinearity for the function approximation. Consequently, the theoretical understanding of offline DRMDPs with function approximation remains elusive, even when the approximation is linear. In this work, we aim to address the essential challenges and explore the fundamental limit of this setting.\n\nIn the conclusion section, we will add the following sentences to explore future research directions:\n\nMoreover, we would like to extend the pessimism principle utilized in this work beyond linear function approximation to explore general function approximation in DRMDPs. Leveraging the techniques for general function approximation in standard offline RL (Chen and Jiang, 2021), we would explore the unique challenges and fundamental limits of practically solving DRMDPs with general function approximation. \n\n---\nWe hope we have addressed all of your questions/concerns. If you have any further questions, we would be more than happy to answer them and if you don’t, would you kindly consider increasing your score?\n\n---\n**References**\n\n[1] Zhishuai Liu, and Pan Xu. \"Distributionally robust off-dynamics reinforcement learning: Provable efficiency with linear function approximation.\" In International Conference on Artificial Intelligence and Statistics, pp. 2719-2727. PMLR, 2024.\n\n[2] Yin, Ming, Yaqi Duan, Mengdi Wang, and Yu-Xiang Wang. (2022). \"Near-optimal Offline Reinforcement Learning with Linear Representation: Leveraging Variance Information with Pessimism.\"\n\n[4] Ying Jin, Zhuoran Yang, and Zhaoran Wang. (2021). Is pessimism provably efficient for offline RL? \n\n[4] Xiong, Wei, Han Zhong, Chengshuai Shi, Cong Shen, Liwei Wang, and Tong Zhang. (2022). Nearly Minimax Optimal Offline Reinforcement Learning with Linear Function Approximation: Single-Agent MDP and Markov Game. \n\n[5] Jin, Chi, Zhuoran Yang, Zhaoran Wang, and Michael I. Jordan. (2019). Provably efficient reinforcement learning with linear function approximation.", "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": "KQhlmRV0wU", "reviewer": "Reviewer_d55R", "summary": "This paper studies robust offline RL with function approximation under the specific setting of $d$-rectangular linear DRMDPs, where the nominal environment is a linear MDP with simplex feature space. The authors propose two learning algorithms and establish instance-dependent upper bounds for the suboptimality. The derived information-theoretic lower bound shows that the proposed VA-DRPVI algorithm is near-optimal up to a factor of $\\widetilde{O}(\\sqrt{d})$.", "questions": "1. Is it possible to establish suboptimality bounds and the lower bound for universal $K$? I guess there would be some \"burn-in\" terms.\n2. Ma et al. (2023) consider a similar setting, except that the model uncertainty is measured by the KL divergence instead of the TV divergence in this paper. Can you point out the differences between this work and theirs? Also, are there any specific reasons for considering the TV divergence, and what are the unique challenges in the analysis?\n3. The paper considers linear MDPs with simplex feature space. Can you explain the challenges in extending the results to general linear MDPs?\n4. A minor suggestion on wording: In part 3 of the contribution section (the last paragraph on p.g. 2), the paper claims that \"...which implies that VA-DRPVI is minimax optimal in the sense of information theory\". However, as parameter $\\beta_2$ scales with $\\widetilde{O}(\\sqrt{d})$, it can be better to switch to the word *near-optimal* instead of *minimax optimal*.", "limitations": "Limitations have been addressed in the paper.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "(+) The paper derives an information-theoretic lower bound, which depends on the novel uncertainty function $\\Phi((\\Sigma_h^*)^{-1},s)$ and could be of independent interest to the community.\n\n(+) The suboptimality for the proposed VA-DRPVI algorithm nearly matches the lower bound.", "weaknesses": "(-) The derived suboptimality bounds (in Theorems 3.4 and 4.2) and the lower bound (in Theorem 5.1) require the number $K$ of the trajectories in the offline dataset to scale with $\\text{poly}(d,H)$, which could be quite restrictive in the offline setting.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for your positive feedback on our work. We hope our response fully addresses all your questions. \n\n---\n### 1. Requirement of the number of trajectories $K$ to be poly(d,H).\n\nThis is an interesting question. We acknowledge that our current analysis requires the sample size $K$ has a large order dependence on $d$ and $H$. Similar requirements are also necessary for standard offline RL with linear function approximation (Yin et al., 2022, Xiong et al. 2022). It is still unsure if we could construct upper and lower bounds for full-range $K$ in the robust linear function approximation setting. We will leave this problem for future study.\n\n---\n### 2. Comparison with Ma et al. (2022).\n\nWe acknowledge that Ma et al. (2022)’s work is the most closely related to ours. However, we note that there are several technical flaws in their paper. We summarize the main issues here:\n\n* The proofs of main lemmas (Lemma D.1 and Lemma D.2 in the arXiv version) related to suboptimality decomposition and the proof of theorems are incorrect.\n\n* The sample complexity results for the two algorithms are both incorrect on the order of $d$.\n\n* The Assumption 4.4 on the dual variable of the dual formulation of the KL-divergence is too strong to be realistic.\n\n* The concept of mis-specification in Section 5.2 is not well-defined, which makes all results in Section 5 vacuous.\n\nGiven these technique flaws, we believe the fundamental challenges of $d$-rectangular linear DRMDPs are not properly addressed in their work. It is also unsure whether $d$-rectangular linear DRMDPs with KL-divergence uncertainty set are solvable by their current methodologies. Moreover, in our work, we start with the setting of $d$-rectangular linear DRMDPs with TV-divergence uncertainty set. We address the essential challenges and explore the  fundamental limit of $d$-rectangular linear DRMDPs.\n\n---\n### 3. Reasons for considering TV-divergence and challenges in the analysis.\n\nThere are two main reasons we consider the TV-divergence: 1) TV-divergence in a commonly studied distance in the field of DRMDPs, it serves as a proper “start” setting to address the fundamental challenges of DRMDPs with linear function approximation; 2) We also tried the KL-divergence uncertainty set, however the analysis heavily relies on an unrealistic assumption on the dual variable of the duality for KL. Thus, it requires further effort to figure out if the linear DRMDP with KL-divergence uncertainty set is both theoretically and practically solvable.\n\nThanks to the simple format of the duality for TV, we can simply focus on the essential challenges of the linear DRMDP setting. To see the main challenge of the analysis, we first note that existing analysis of standard linear MDPs highly relies on the linear dependency of the Bellman equation on the nominal kernel. However, the consideration of model uncertainty of DRMDPs disrupts the linear dependency (see (2.1a)) of the robust Bellman equation on the nominal kernel, where the offline dataset is collected.\nThis nonlinearity leads to unique challenges in both upper bound and lower bound analysis, and we are the first to solve those challenges.\n\n---\n### 4. Extending the results to general linear MDPs.\n\nGeneralizing the results to standard linear MDPs presents challenges primarily due to the construction of  uncertainty sets. In particular, the design of the $d$-rectangular uncertainty set relies on the fact that the factor uncertainty sets are defined around probability distributions, since the total variation distance $D_{\\text{TV}}(\\cdot||\\cdot)$ is a distance measure for probability distributions. Further, it is non-trivial to define uncertainty sets for the standard linear MDP to ensure (1) it contains valid probability distributions and (2) the optimization among the uncertainty set can be efficiently solved (by duality for example). We leave this extension for future research.\n\t\t\n---\n### 5. Wording suggestion.\nThanks, we will take your advice and revise the “minimax optimal” to “near-optimal”.\n\n---\nWe hope we have addressed all of your questions/concerns. If you have any further questions, we would be more than happy to answer them and if you don’t, would you kindly consider increasing your score?\n\n---\n**References**\n\n[1] Yin, Ming, Yaqi Duan, Mengdi Wang, and Yu-Xiang Wang. \"Near-optimal Offline Reinforcement Learning with Linear Representation: Leveraging Variance Information with Pessimism.\" In International Conference on Learning Representation. 2022.\n\n[2] Xiong, Wei, Han Zhong, Chengshuai Shi, Cong Shen, Liwei Wang, and Tong Zhang. Nearly Minimax Optimal Offline Reinforcement Learning with Linear Function Approximation: Single-Agent MDP and Markov Game. In International Conference on Learning Representations (ICLR). 2023.", "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:
## Overall Response 

We would like to thank all reviewers for their insightful and detailed reviews and comments. We have addressed the comments from the reviewers and revised the manuscript accordingly. In the following, we would like to provide overall responses to several common questions raised by reviewers.

### 1. Experimentation

Per reviewers’ requirements, we conduct numerical experiments to illustrate the performances of our two algorithms. In the attached PDF, we present additional experimental results. Specifically, we leverage the simulated linear MDP (Figure 1) proposed by Liu and Xu (2024) and adapt it to the offline setting. In particular, we set the behavior policy as the random policy that chooses actions uniformly at random at each state-action pair $(s, a)$ and stage $h$. The number of trajectories (i.e., sample size) of the offline dataset is set to 100. We compare our algorithms with their non-robust counterpart, PEVI, proposed by Jin et al. (2021). Figure 2 shows the performances of the learned policies of three algorithms. We conclude that both of our proposed algorithms are robust to environmental perturbation compared to the non-robust PEVI. Furthermore, VA_DRPVI slightly outperforms DRPVI in most settings. These numerical results are consistent with our theoretical findings. 


### 2. Comparison with Ma et al. (2022)

We acknowledge that the work of Ma et al. (2022) is the most closely related to ours. However, we note that there are several technical flaws in their paper. We summarize the main issues here:

* The proofs of main lemmas (Lemma D.1 and Lemma D.2 in the arXiv version) related to suboptimality decomposition and the proof of theorems are incorrect.

* The sample complexity results for the two algorithms are both incorrect on the order of $d$.

* Assumption 4.4 on the dual variable of the dual formulation of the KL-divergence is too strong to be realistic.

* The concept of mis-specification in Section 5.2 is not well-defined, which makes all results in Section 5 vacuous.

Given these technique flaws, we believe the fundamental challenges of $d$-rectangular linear DRMDPs are not properly addressed in their work. It is also unsure whether $d$-rectangular linear DRMDPs with KL-divergence uncertainty set are solvable by their current methodologies. Moreover, in our work, we start with the setting of $d$-rectangular linear DRMDPs with TV-divergence uncertainty sets. We address the essential challenges and explore the fundamental limit of this setting.

---
**References**

[1] Liu, Zhishuai, and Pan Xu. "Distributionally robust off-dynamics reinforcement learning: Provable efficiency with linear function approximation." In International Conference on Artificial Intelligence and Statistics, pp. 2719-2727. PMLR, 2024.

[2] Ying Jin, Zhuoran Yang, and Zhaoran Wang. Is pessimism provably efficient for offline RL? In International Conference on Machine Learning, pages 5084–5096. PMLR, 2021. 

[3] Ma, Xiaoteng, 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.06620 (2022).

Meta-review: The paper provides instance dependent upper and lower bounds under the setting of offline linear DRMDPs. The reviewers all agree with the contribution of the paper. I recommend acceptance.
Decision: Accept (poster)