Achieving the Asymptotically Minimax Optimal Sample Complexity of Offline Reinforcement Learning: A DRO-Based Approach
Authors: Yue Wang
Jinjun Xiong
Shaofeng Zou
Venue: Accepted by TMLR ()

Abstract: Offline reinforcement learning aims to learn from pre-collected datasets without active exploration. This problem faces significant challenges, including limited data availability and distributional shifts. Existing approaches adopt a pessimistic stance towards uncertainty by penalizing rewards of under-explored state-action pairs to estimate value functions conservatively. In this paper, we show that the distributionally robust optimization (DRO) based approach can also address these challenges and is {asymptotically minimax optimal}. Specifically, we directly model the uncertainty in the transition kernel and construct an uncertainty set of statistically plausible transition kernels. We then show that the policy that optimizes the worst-case performance over this uncertainty set has a near-optimal performance in the underlying problem.  We first design a metric-based distribution-based uncertainty set such that with high probability the true transition kernel is in this set. We prove that to achieve a sub-optimality gap of $\epsilon$, the sample complexity is $\mathcal{O}(S^2C^{\pi^*}\epsilon^{-2}(1-\gamma)^{-4})$, where $\gamma$ is the discount factor, $S$ is the number of states, and $C^{\pi^*}$ is the single-policy clipped concentrability coefficient which quantifies the distribution shift. To achieve the optimal sample complexity, we further propose a less conservative value-function-based uncertainty set, which, however, does not necessarily include the true transition kernel. We show that an improved sample complexity of $\mathcal{O}(SC^{\pi^*}\epsilon^{-2}(1-\gamma)^{-3})$ can be obtained, which asymptotically matches with the minimax lower bound for offline reinforcement learning, and thus is asymptotically minimax optimal.

Published in Transactions on Machine Learning Research (06/2024)
Achieving the Asymptotically Optimal Sample Complexity of Offline Reinforcement Learning: A DRO-Based Approach
Yue Wang
yue. wwe.wangreeffce
Deportment of Electrical and Computer Engineering
University of Central Florida
Jinjun Xiong
jinjun&buuffllo. edu
Department of Computer Science and Engineering University at Buffalo
Shaofeng Zou
szouJd@buffalo.c edu
Department of Electricol Engineering University at Buffalo
Reviewed on OpenReview: https: // oppnrevvee.. net/ forum? id- Y7FoGej0uD
Abstract
Offline reinforcement learning aims to learn from pre-collected datasets without active exploration. This problem faces significant challenges, inchuding limited data availability and distributional shifts. Existing approaches adopt a pessimistic stance towards uncertainty by penalizing rewards of under-cxplored state-action pairs to estimate value functions conservatively. In this paper, we show that the distributionally robust. oplimization (DRO) based approach can also address these challenges and is asymptotically minimax optimal. Specifically, directly model the uncertainty in the transition kernel and construct uncertainty set of statistically plausible transition kernels. We then show that the policy that optimizes the worst-case performance over this uncertainty set has near-optimal performance in the underlying problem. We first design a metric-based distribution- based uncertainty this set. We prove
set such that with high probability the true transition kernel that to achieve sub-optimality gap of e, the sample complexity is ( 622 -1 where y the discount factor, S is the number of states, and O is the single-policy clipped concentrability coefficient which quantifies the distribution shift. To achieve the optimal sample complexity, we further propose less conservative value-finetion-bassed uncertainty set, which, however, does not necessarily include the true transition kernel. We show that an improved sample complexity of O(SC** - -7)-3) can be obtained, which asymptotically matches with the minimax lower bound for offline reinforcement learning, and thus is asymptotically minimax optimal.
1 Introduction
Reinforccment learning (RL) has achicved impressive empirical success in many domains, o.g., (Mnih al. 2015; Silver al.] 2016). Nonetheless, most of the success stories rely on the premise that the agent actively explore the environment and receive feedback to further promote policy improvement. This trial-and-error procedure can be costly, unsafe, or even prohibitory in many real-world applications, e.g., autonomous driving (Kiran et al. 2021b and health care Yuu et al. 2021a). To address the challenge, offline (or batch) reinforcement. learning Lange et al. 2012 Levine et al. 2020) was developed, which aims to learn a competing policy from a pre-collected dataset without access to online exploration.
A straightforward idea for offline RL is to use the pre-collected dataset to learn an estimated model of the environment, and then learn optimal policy for this model. This approach performs well when the dataset.

---

Published in Transactions on Machine Learning Research (06/2024)
sufficiently explored the environment, c.g., (Agarwal et al. 2020a). However, under more general offline settings, the static dataset can be limited, which results in the distribution shift challenge and inaccurate model estimation (Kidambi et al. 2020 Ross & Bagnell 2012 Li et al., 2022). Namely, the pre-collected datasct is often restricted to a small subset of state-action pairs, and the behavior policy used to collect the datasel induces a state-action visitation distribution that is different from the one induced by the optimal policy. This distribution shift and the limited amount of data lead to uncertainty in the estimation of the model, i.e., transition kernel and/or reward function.
To address the above challenge, natural approach is to first quantify the uncertainty, and further take pessimistic (conservative) approach in face of such uncertainty. Despite of the fact that the uncertainty exists in the transition kernel estimate, existing studies mostly take the approach to penalize the reward function for less-visited state-action pairs to obtain a pessimistic estimation of the value function, known as
the Lower Confidence Bound (LCB) approach (Rashidinejad et al. 2021: Li et al. 2022 Shi et al. 2022 Yan ct al., 2022). In this paper, we develop a direct approach to analyzing such uncertainty in the transition kernel by constructing a statistically plausible set of transition ion kernels, i.e., uncertainty sel, and optimizing the worst-case performance over this uncertainty set. This principle is referred to as 'distributionally robust optimization (DRO)' in the litcrature (Nilim & El Ghaoui 2004 Iyengar 2005). This DRO-based approach directly tackles the uncertainty in the transition kernel. We show that our approach asymptotically achieves the minimax optimal sample complexity (Rashidinejad et al. 2021 We summarize our major contributions
as follows.
1.1 Main Contributions
In this work, we focus on the most general partial coverage setting (see Section 2.3 for the definition). We develop a DRO-based framework that efficiently solves the offline RL problem. More importantly, we design a value-function-base uncertainty set and show that its sample complexity is minimax optimal.
DRO-based Approach Solves Offline RL. We construct a distribution- based uncertainty set centered at the empirical transition kernel to guarantee that with high probability, the true transition kernel lies within the uncertainty set. Then, optimizing the worst-case performance over the uncertainty set provides a lower bound on the performance under the true environment. Our uncertainty model enables easy solutions using the robust dynamic programming approach developed for robust MDP in [Lyengar] 2005 Nilim & El Ghaoui 2004) within a polynomial computational complexity. We further show the sample complexity to achieve an e-optimal policy using our approach is O S2Cm" (1-7)+
(up to log factor), where is the discount factor, and C*' is the single-policy concentrability for any comparator policy x¹ (see Definition D.. This sample complexity matches with the best-known complexity of the distribution-basee modelluncertainty method (Rashidinejad et al., 2021 Uehara & Sun 2021), which demonstrates that our DRO framework can directly tackle the model uncertainty and effectively solve offline RL.
Achieving Asymptotic Minimax Optimality via Design of value-functionn-based Uncertainty Set. While the approach described above is effective in achieving an e-optimal policy with relatively low sample complexity, it tends to exhibit excessive conservatism its complexity surpasses the minimax lower bound for oflline RT algorithms (Rashidinejad et al. 2021 by a factor of S(1 - To close this gap, we discover that demanding the true transition kernel to be within the uncortainty set with high probability, i.c., the true environment and the worst-case one are close, can be overly pessimistic and unnecessary. What is of paramount importance is that the value function under the worst-case transition kernel within the uncertainty set (almost) lower bounds the one under the true transition kernel. Notably, this requirement is considerably less stringent than mandating that the actual kernel be encompassed by the uncertainty set. We then design colueeffnctioon-ban
less conservative the distribution-baat based uncertainty set. We prove that to obtain e-optimal policy, the order of the sample complexity is O
uncertainty set, which has a smaller radius and thus is subset of
[1->]>>> This complexity indicates the asymptotic minimax optimality of our approach by matching with the minimax lower bound in asymptotic order of the sample complexity for offline RL
SS**
(Rashidinejad et al. 2021) and the best result from the LCB approach (Ti et al. 2022).
2

---

Published in Transactions on Machine Learning Research (06/2024)
1.2 Related Works
There has been proliferation of works on offline RL. In this section, we mainly discuss works on model-based approaches. There are also model-free approaches, e.g., (Liu et al. 2020 Kumar et al., 2020 Agarwal et al.,
2020b Yan et al. 2022 Shi et al. 2022). which are not the focus here.
Offline RL under global coverage. Existing studies on offline RL often make assumptions on the coverage of the dataset. This can be measured by the distribution shift between the behavior policy and the occupancy
measure induced by the target policy, which is referred to as the concentrability coefficient (Munos
2007
Rashidinejad et al.
2021). Many previous works, e.g., (Scherrer)
2014
Chen & Jiang 2019:
Jiang 2019
Wang et al.
2019: Liao et al.
2020 Liu et al. 2019 Zhang et al.
2020a.
Munos & Szepesvari 2008
Uehara
lt al. 2020 Duan et al.
2020
Xie & Jiang 2020 Levine et al.
2020 Antos et al.) 2007 Parahmand et al.
2010), assume that the density ratio between the above two distributions is finite for all state-action pairs
and policies, which is known as global coverage condition. This assumption essentially requires the behavior
policy to be able to visit all possible state-action pairs, which often violated in practice (Gulcchre et al.
2020
Agarwal et al., 2020b Fu et al. 2020).
Offline RL under partial coverage. Recent studies relax the above assumption of global coverage to partial coverage or single-policy concentrabilityy Partial coverage assumes that the density ratio between the distributions induced by a single larget policy and the behavior policy is bounded for all state-action pairs. Therefore, this assumption does not require the behavior policy to be able to visit all possible state-action pairs, as long as it can visit those state-actions pairs that the target policy will visit. This partial coverage assumption is more feasible and applicable in real-world scenarios. In this paper, we focus on this practical partial coverage setting. Existing approaches under the partial coverage assumption can be divided into three categories as follows.
Regularized Policy Search. The first approach regularizes the policy so that the learned policy is close to the behavior policy (Fujimoto et al. 2019b Wu et al.
2019 Jaques et al. 2019 Peng et al.,
2019
Siegel ct al., 2020 Wang et al. 2020 Kumar ct al. 2019
Fujimoto et al.] 2019a, Ghasemipour
Thus, the learned policy is similar to the behavior policy which generates the dataset, hence this approach works well when the dataset is collected from experts (Wu et al. 2019 Fu et al. 2020
el. al. 2020: Nachum el al.] 2019 Zhang al.
2020b 2023).
Reward Penalization or LCB Approaches. One of the most widely used approaches is to penalize the reward in face of uncertainty due to the limited data, to obtain an pessimistic estimation that
lower bounds the real value function, c.g., (Kidambi et al. 2020: Yu et al.,
2020
2021b Buckman
lel. al. 2020
Jin et al. 2021: Xie et al., 2021b Yin & Wang 2021 Liu et al.
2020 Cui & Du 2022
Chen et al.
2021 Zhong et al.) 2022). The model-based approaches, e.g., VI-LCB (Rashidinejad
et al.) 2021
Li al. 2022) penalizes the reward with a term that is inversely proportional to the mumber of samples. The tightest sample complexity is obtained in (Li et al.
2022) by designing
value-fucction-base penalty term, which matches the minimax lower bound showed in RRashidinejad
et al. 2021
DRO-based Approaches. Another approach is to first construct a set of "statistically plausible" MDP models based on the empirical transition kernel estimated using the dataset, and then find the policy that optimizes the worst-case performance over this set (Zanette et al.] 2021 Cehara & Sun 2021
Rigter et al.] 2022 Bhardwaj et al., 2023 Guo et al.] 2022 Hong al. 2023 Chang et al.
2021
Blanchet et al.) 2023). However, finding such policy under the models proposed in these works can be NP-hard, hence some hcuristic approximations without thcoretical optimality guarantce are used to deploy their approaches. Our work falls into this category, but the computational complexity is polynomial, and the sample complexity of our approach is minimax optimal. A recent work (Panaganti et al. 2023) also proposes a distribution-basee DRO framework similar to ours, and their sample complexity results match ours in the first part but fail to obtain the minimax optimality as our improved results in the second part.
Offfine RL with function approzimation. There is another substantial interest in combining offline reinforcement learning with function approximation (e.g., deep neural networks) in order to encode
3

---

Published in Transactions on Machine Learning Research (06/2024)
inductive biases and enable generalization across large, potentially continuous state spaces, with recent progress on both model-free and model-based approaches Ross & Bagnell 2012 Laroche et al. 2019; Fujimoto et al. 2019b Kumar et al. 2019 Agarwal et al. 2020bj. Besides the aforementioned challenges, an additional issuc regarding the representational conditions of the function class is introduced, which assert that. the function approximator flexible enough to represent value functions induced by certain policies. A huge body of recent works aims to understand the condition for the function classes, including Bellman completeness condition (Liu al.) 2020 Jin et al., 2021; Xie et al.] 2021a| Yin et al., 2021 Rashidineead et al. 2021 Bellman realizability (Xie & Jiang, 2021 Chen & Jiang, 2022 Rashidinejad et al.) 2022 Jiang & Huang, 2020). However, in this paper, we mainly consider the tabular setting, where no requirement on the function class is needed.
Robust. RL with distributional uncertainty. In this paper, our algorithm is based on the framework of robust MDP [Iyengar] 2005; Nilim & El Ghaoui 2004 Bagnell et al.) 2001 Satia & Lave Jr, 1973; Wicsemann et al. 2013), which finds the policy with the best worst-case performance over an uncertainty set of transition dynamics. When the uncertainty set is fully known, the problem can be solved by robust dynamic programming. The sample complexity of model-based approaches without full knowledge of the uncertainty sets was studied in, e.g.; (Yang al., 2021 Xu et al. 2023 Panaganti & Kalathil 2022 Shi et al. 2023 Panaganti & Kalathil 2022), where generative model is typically assumed. This model-based approach is further adapted to the robust offline setting in (Panaganti et al.) 2022: Shi & Chil 2022). Yet in these works, the challenge induced by the offiine setting is addressed using the LCB approach, i.e., penalizing the reward functions. In contrasi, we show that the DRO framework itself addresses the challenge of partial coverage in the offline setting.
2 Preliminaries
2.1 Markov Decision Process (MDP)
An MDP can be characterized by a tuple P,r,, where S and A are the state and action spaces, P == =P e A(8), a A, E S is the transition kernel, 8 x A + [0, 1] is the deterministic reward function and 7 E [0, is the discount factor. Specifically, P. (v',s)))'s, where ph,./ denotes the probability that the environment transits to state s' if taking action at state s. The reward of taking action a at state 8 is given by r(s,a). A stationary policy π is a mapping from 8 to a distribution over A, which indicates the probabilities of the agent taking actions at each state. At each time t, an agent takes an action a ~ T (s;) at state St; the environment then transits to the next state $441 with probability phi and the agent receives reward ac).
The value function of policy starting from any initial state E S is defined as the expected accumulated discounted reward by following (s)(s) (8) 2 Ep IEi 7'r(S., A.) J.S = 8, mr, where Ep denotes the expectation when the state transits according to P. Let denote the initial state distribution, and denote the value function under the initial distribution p by Vp (p) & [V (s)].
2.2 Robust Markov Decision Process
In the robust MDP, the transition kernel is not fixed and lies in some uncertainty set P. Define the robust value function of a policy æ the worst-case expected accumulated discounted reward over the uncertainty set: (s) e minper Ep / ('r Ar)[So = 5, s. Similarly, the robust action-value function for policy is defined as (s, minper Ep 1 3'r(S,, A:) 8, Ao a, m]. The goal of robust RL is to find the optimal robust policy that maximizes the worst-case accumulated discounted reward, i.e., Tr arg max, V (s), Vs E 8. It is shown in (Tyengar 2005; Nilim & El Ghaoui 2004 Wicscmann et al.) 2013 that the optimal robust value function is the unique solution to the optimal robust Bellman equation
1 AA( denotes the probability simplex defined on S. 2To streamline our presentation and emphasize our novelty solving offline RL through DRO formulation, assume the reward function deterministic. However, our DRO approach directly extends the stochastic reward setting by constructing similar uncertainty set for the reward estimation.
4

---

Published in Transactions on Machine Learning Research (06/2024)
V (s) maxa(r(s, +000 (V where )o - minpevs VV denotes the support function of V on set Pg and the corresponding robust Bellman operator is a y-contraction.
2.3 Offline Reinforcement Learning
Under the offline setting, the agent cannot interact with the MDP and instead is given a pre-collected dataset D consisting of N tuples {(8;, 04, 84, ri) =1, I,, where ri = r(8;, a:) is the deterministic reward, and s ~ -P:; follows the transition kernel of the MDP. The (s,, a,) pairs in 2) are generated i.dd, according to an unknown data distribution f over the stato-action space. In this paper, we consider the sctting where the reward funetions deterministic but unknown. We denote the number of samples transitions from (s, a) in D by a)s ie., [ss, a) Ei= (=x,a))=(s.a)) and 1x=z is the indicator function.
The goal of offine RL is find a policy π which optimizes the value function VP based on the offline dataset
D. Let d denote the discounted occupancy distribution associated with л: d= (s) (1 7) - SS p. n., P). In this paper, we focus the partial coverage setting and adopt the following definition from (Li el al. 2022) to measure the distribution shift between the dataset distribution and the occupancy measure induced by a deterministic single policy π²:
Definition 1. (Single-policy clipped concentrability) The single-policy clipped concentrability coefficient of policy n² is defined
min as.
C A max
(1)
8,0
((s,a)
where S A denotes the number of states.
We note another unclipped version of O is also commonly used in the literalure, e.g., |Rashidineaad el. al. 2021
Uehara & Sun 2021), defined as Ö"' max,,a p(s.a)
d' (s,a). It is straightforward to verify that C < Č
and all of our results remain valid if C*" is replaced by O A more detailed discussion can be found in Li et al. 2022 Shi & Chi 2022).
In this paper, we always assume that C* < 00 being a finite number, under which we aim to find a policy w that minimizes the sub-optimality gap compared to a comparator policy x" under some initial state distribution p: V/p (p) - Vp (p). It worth noting that some references, the comparator policy is set to the optimal policy, but our results hold for arbitrary deterministic policics.
3 Offline RL via Distributionally Robust Optimization
Model- Modellbased methods usually commence by estimating the transition kernel employing its maximum likelihood estimate. Nevertheless, uncertainties arise in these estimations due to the inherent challenges associated with distribution shifts and limited data in the offline setting. For instance, the dataset may not encompass every state-action pair, and the sample size may be insufficient to estimate the transition kernel accurately. In this paper, we directly quantify the uncertainty in the empirical estimation of the transition kernel and construct a set of 'statistically possible" transition kernels, referred to as uncertainty sets, to encompass the actuaal environment. We then employ the DRO approach to optimize the worst-case performance over the uncertainty set. This formulation transforms the problem into robust Markov Decision Process (MDP), as discussed in Section 2.2
In Section 3.1 we first introduce direct distribution- approach to construct the uncertainty set such that the truc transition kernel is in the uncertainty set with high probability. We then present the robust value iteration algorithm to solve the DRO problem. We further theoretically characterize the bound on the sub- optimality gap and show that the sample complexity to achieve an e-optimality gap is O(1 -ee1---)--- =522=00==* ). This gap matches with the best-known sample complexity of the DRO-basod approach in [Uehara & Sun) (2021), but with a polynomial complexity. This result shows the effectiveness of our DRO-based approach in solving the offline RL problem.
5

---

Published in Transactions on Machine Learning Research (06/2024)
We then design less conservative uncertainty set aiming to achieve the minimax optimal sample complexity in Section 3.2 We theoretically establish that our approach attains an enhanced and asymptotically minimax optimal sample complexity of O 2)) -)(=))) ). Notably, this sample complexity matches with the minimax lower bound (Rashidinejad et al. 2021) and stands on par with the best results achieved using the LCB approach
(Li et al. 2022 in asymptolic order.
Our approach starts with learning an empirical model of the transition kernel and reward from the dataset follows. These empirical transition kernels will be used as the centroid of the uncertainty set. For any (s, a), if [s, a) > 0, set
EisN (1, f(s,a) - r((ssa); ((8,a) a)
60 0,6'
(2)
And if N(s, a) 0, set
P 0,8' 1s'=s, f(s,a)
(3)
The MDP M- = A,,A, with the empirical transition kernel P and empirical reward ê is referred to as the empirical MDP. For unseen state-action pairs (s, a) in the offline dataset, we take a conservative approach and let the estimated P(s, a) = O, and set & as an absorbing state if taking action a. Then the action value function at (s, a) for the empirical MDP shall be zero, which discourages the choice of action a at state 8.
For each state-action pair (s, a), we construct an uncertainty set centered at the empirical transition kernel P with a radius inversely proportional to the number samples in the dataset. Specifically, set the uncertainty set as p0 2 s.a
f and
fe = (9 A(8) 4
Dlg. < R
(4)
where -)- :) is some function that measures the difference between two probability distributions, e.g,, total variation, Chi-square divergence, R. is the radius ensuring that the uncertainty set adapts to the dataset size and the degree of confidence, which will be determined later. We then construct the robust MDP M P).
As shall show later, the optimal robust policy
arg min (s), E S.
55)
n
PEB
w.r.t. M. performs well in the real environment and reaches a small sub-optimality gap. In our construction in eq. 4 the uncertainty set is (s, reeetagggg,,,,,, i.e., for different state-action pairs, the corresponding uncertainty sets are independent. With this rectangular structure, the optimal robust policy can be found by utilizing the robust. value iteration algorithm robust dynamic programming (Algorithm 1 and the corresponding robust value iteration each step can be solved in polynomial time (Wiesemann al. 2013). In contrast, the uncertainty set constructed in (Uehara & Sun 2021 Bhardwaj et al.) (022),, defined J T= (Q ED [ Q () does not enjoy such rectangularity. Solving robust MDP with such uncertainty set can be, however, NP-hard (Wiesemann et al. (0013). The approach developed in (Rigter et al. 2022) to solve it is based on the hcuristic approach of adversarial training, and therefore is lack of theoretical guarantee.
The algorithm converges to the optimal robust policy linearly since the robust Bellman operator is a 7- contraction [Iyengar] 2005). The computational complexity of the support function Tia (p. (V) in Lines 3 and 7 w.r.t. the uncertainty sets we constructed matches the ones of the LCB approaches (Rashidinejad et al. Li et al. 2022).
2021
In the following two sections, we specify the constructions of the uncertainty sets.
3 Here, s.a. denotes the Cartesian product of all state-action pains, i.c., the uncertainty set & is independently defined for each state-action pairs. This structure also known as the (s, re-rengang uncertainty set.

---

Published in Transactions on Machine Learning Research (06/2024)
Algorithm Robust Value Iteration Nilim & El Ghaoui 2004 Lyengar
2005)
INPUT: P,R.V,D
1: while TRUE do
2: for 8 e 8 do
3: V(8) t max. () +0 (V))
end for
5: end while
6: for s 8 do
7: (8) E arg ma (f(s, yo (V)})
8: end for
Output: Tr
3.1 Distribution-Basee Radius
In this section, we first consider straightforward, distribution-basee construction of the uncertainty set. Namely, we aim to construct an uncertainty set such that the true transition kernel falls into it, such that the DRO framework can provide a lower bound or conservative estimation of the true performance.
We employ the total variation to construct this uncertainly set. Specifically, our uncertainty set is construeted as follows:
S log SA 8N(s JJ
Pn
q E A(8) 511e - - S n. A (IV
(6)
With our design, fewer samples result in larger uncertainty set and imply that we should be more conservative in estimating the transition dynamics at this stale-action pair. Other distance function of D can also be used, contingent upon the concentration inequality being applied.
In Algorithm fpy (V) = min e {q VV} can be cquivalently solved by solving its dual form [yengar 2005), which is a convex optimization problem: maxigusv (V - μ) S"Sann(V -5---,) n)}, and Span(X) max, (t) - min, (t) is the span semi-norm of vector X. The computational complexity associated with solving is (S log(S)). Notably, this polynomial computational complexity on par with the complexity of the VI-LCB approach (Li et al., 2022).
We then show that with this distribution-based radius, the true transition kernel falls into the uncertainty set with high probability.
Lemma 1. With probability at least 1 - 6, it holds that for any a, Pa E Pgg i.e., ||P P - 2R
This result implics that the real environment falls into the uncertainty set f. with high probability, and hence finding the optimal robust policy of M provides worst-case performance guarantee. We further present our result of the sub-optimality gap in the following theorem.
Theorem 1. Consider an arbitrary deterministic comparator policy n" With probability at least 1 25, the output policy ny of Algorithm 7 satisfies
NS 8 165 log
96S log SA 3
(p) - (p) S (1 71-7)2
(7)
(1-7)²N
To achieve an e-optimality gap, a dataset of size N = 0 complexity matches with the sample complexity for LCB methods [Rashidinejad et al., 2021) and model uncertainty type approach (Panaganti et al. 2023 Uehara & Sun 2021). It suggests that our DRO-based approach can effectively address the offline RL problem.
is required. This sample
4In this paper, unless stated hehewwise, we denote the Jj-norm by ||

---

Published in Transactions on Machine Learning Research (06/2024)
However, there is still a gap between this sample complexity and the minimax lower bound in @Rashidinejad et al. 2021 ) and the best-known sample complexity of LCBB-ased method (Li et al. 2022). which is O ((1 - -) "s0"") We will address this problem via a value function-bass based uncertainty set design in the next subsection.
The choice of total varialion for constructing the uncerlainly set and oblain the results are not essential, and alternative distance functions divergence, e.g., including Chi-square diveryence, KL-diveryence and Wasserstein distance can also be used with their corresponding concentration incqualities (Canonné 2020, Bhandari & Rasso 2021 Arora et al., 2023). Our results and methods con be further generalized to large-scale problems when a low-dimensional latent representation is presented, e.g., linear MDPs or low-rank MDPs Panaganti et al. 2023).
Remark 1.
3.2 Value- Foine--Fnntioo-Bee Based Radius
As discussed above, using a distribution-based radius is able to achieve an c-optimal policy, however, with an unnecessarily large sample complexity. Compared with the minimax lower bound and the tightest result obtained in (Li et al. 2022), there exists a gap of order O(S(1 - -)) This gap is mainly because the distribution-based radius is overly conservative such that the true transition kernel P falls into P with high probability (Lemma Tb. Therefore, it holds that V S Vpr and the sub-optimality gap can be bounded as
Vp
Fr
Vp
S A
(8)
1
Ag
Since the radius is large, although 42 is bounded by 0, Vp is more conservative and hence the first term A becomes larger, resulting in a loose bound with an order of o
VN(1-))
This result can be improved from two aspects. Firstly, we note that the uncertainty set under the distribution- based construction is too large to include P with high probability. Although this construction implics A₂ S O, as the price of it, the large radius implies loose bound on A, Another observation is that both two terms are in fact the differences between the expectations under two different distributions. Instead of merely using the distance of the two distributions to bound them, we can utilize other tighter concentration inequalities like Bernstein's incquality, to obtain an involved but tighter bound.
Toward this goal, we construct a smaller and less conservative uncertainty set such that: (1). It implies a tighter bound on A combining with Bernstein's inequality; And (2). Although non-zero, the term Ag can also be bounded by some tight error bounds.
To do so, we further note that 42 = VT
V Term (b) can be viewed as an estimation error (6)
which is from the inaccurate estimation from the dataset, which is independent from the designing of the uncertaint set (ignoring the dependence of π,,); And Term (a) is the difference between robust value function and the value function under the centroid transition kernel P. which is always negative and can be bounded using the dual-form solutions for specific uncertainty sets [Tyengar 2005). We hence choose a radius such that: (1). the negative bound on (a) cancels with the higher-order terms in the bound on (b) and further implies tighter bound on A2; And (2). the bound on A is also tight by utilizing Bernstein's 's inequality.
Since our design is based on the value functions instead of distributions, we refer to it as the value-function basod construction. Our construction as follows.
{ g E A(8) (( < Ro
48 log 4SAN
pog
(1-7)8
(9)
N(s,a)
Note that for state-action pairs (s, a) with N(s, a) 0, the uncertainty set reduces the whole probability simplex A(8).
8

---

Published in Transactions on Machine Learning Research (06/2024)
In our construction, instead of the total variation, construct the uncertainty set using the Chi-square divergence, ie., g) = (p = E. 9(5) (1 9(s) As we will discuss later, adopting it can result in a tighter bound than total variation.
Remark 2. From Pinsker's inequality and the fact that (Kl(p)lg) S (pll)) (Nishiyama & Sason 2020 it holds that llp-9l gll I (22x((pl))) q)- Hence the bllue-function--aseed uncertainly set is subset of the distribution- based uncertainty set in Section 3.1 verifying
senee-ffftttion-bee construction is less conservative.
Similarly, we find the optimal robust policy w.r.t. the corresponding robust MDP M (S, f) using the robust value iteration with slight modification, which is presented in Algorithm - Specifically, the output.
Algorithm Robust Value Iteration
INPUT: D
V, 1: while TRUE do
2: for 8 E do
3:
N(s) + E (x))=s
4: V(s) f max (f(8) +70g (V))
5: end for
6: end while
7: for 8 8 do
if (s)) > 0 then
(s) E (arg aa (f(ss a) t (V))) (a: ((s, 0}
10: else
11: (s) E mag (f(s (V)))
12: end
13:
end for
Output:
policy v, in Algorithm| is set to be the greedy policy satisfying ((s, > 0 if (s) > 0. The existence of such a policy is proved in Lemma 2 in the appendix. This is to guarantee that when there is a tie of taking greedy actions, we will take an action that has appeared in the pre-collected dataset D, align with the pessimism principle.
The support function Tpa (V) w.r.t. the Chi-square divergence uncertainty set can also be computed using its Rg Varp. where (s(s) = min(a, V(s)}. The dual form is also a convex optimization problem and can be solved efficiently within a polynomial time O log S) [Lyengar 2005).
dual form Iyengar 2005:: Jz. (V) = maxne(Vmm..Vaat Vmaxs)
(P:Vo (
Remark 3. Using the Chi-square divergence enables smaller radius and yields tighter bound on A₂ (a) + (b). Namely, (b) can be bounded by a
bound according to the Bernslein's inequality (see Lemma 3 in the Appendirr.. Simullaneously, our goal is to oblain a bound with the same order on (a), which effectively offsets the bound on (b), and yields a tighter bound on A2. The robust value function w.r.t. the total variation uncertainty set, however, depends on R linearly (see the dual form we discussed above); On the olher hand, the solution to the Chi-square divergence uncerlainly set incorporales lerm of / Rg which enables to set lower-order radius (i.e., set R ()) to offset the -0..5-ordd bound on (b). Thus we choose Chi-square in our construction.
We then characterive the optimality gap obtained from Algorithm in the following theorem.
Thcorem 2. If N 2 0 (1- m )
then the output policy ot of Algorithm satisfies
KSC** log 4SAN (1-7)8
Vp (p) (1) (p)
(10)
(1 N
9

---

Published in Transactions on Machine Learning Research (06/2024)
with probability at least - 46, where Main min a) pls, a) > 0} denotes the minimal non-zero entry of Mb, and K is some universal constant. that is independent from S, C* and N.
Theorem 2 implies that our DRO approach can achieve an e-optimality gap, as long as the size of the dataset exceods the order of
0
SC
(1 21
+ (1 (1-7) (1-7)SCTT) Plmin
(11)
e-dependent
burn-in cost
The burn-in cost term indicates that the asymptotic bound of the sample complexity becomes relevant after the dataset size surpasses the burn-in cost. It represents the minimal requirement for the amount of data. In fact, if the dataset is too small, we should not expect to learn a well-performed policy from it. In our case,
if the dataset is generated under a generative model Panaganti et al.
(2022) 5 Yang et al.
[202]] : Shi et al.
2023 uniform distribution, the burn-in cost term is in order of SA
Burn-in cost also widely exists in the SC"
1-
sample complexity studies of RI, e.g., HSSC"* in [Xie et al. 2021b) ,
in (He et al.
2021 1, and (I-2)s
(1-33²
in Yan et al. 2022), PmiinPain in SSh & Chi 2022 Note that the burn-in cost. term is independent of the
accuracy level e, which implies the sample complexity is less than 0
SCn (1-1)² as long as is small. This
result matches the optimal asymptotic order the complexity according to the minimax lower bound in [Rashidinejad et al., (2021), and also matches the tightest bound obtained using the LCB approach (Li et al., 2022) asymptotically. This suggests that our DRO approach can effectively address offline RL while imposing minimal demands the dataset, thus optimizing the sample complexity associated with offline RL.
3.3 Further Comparison with LCB Approaches
We further discuss the major differences in our approach and the LCB approaches (Li et al. 2022 Rashidinejad ct al. 2021 in this section.
Firstly, the motivations of the two approaches are different. The LCB approach can be viewed as 'value function-based', which aims to obtain a pessimistic estimation of the value function by subtracting a penalty term from the reward, c.g., eq (83) in (Li et al.) 2022). It implics that the resulting estimation lower bounds the true value functions. Our DRO approach aims to construct an uncertainly set that contains the statistically plausible transition dynamics, and optimize the worst-case performance among this uncertainty set, which can be viewed as "transition model-based", meaning that we directly tackle the uncertainty from the model estimation, without using the value function we obtained, may not be a conservative estimation of the true value functions, but it utilizes the principle of pessimism through the DRO formulation.
intermediate step. The robust value function
Our proof techniques are also different from the ones in LCB. To clarify the difference, we first rewrite our update rule using the LCB fashion. The update in robust value iteration Algorithm [ can be written as
(is) + max(r(s, a) + 10g. (V)) max(r(s, + ppV - b(s. V)).
(12)
where b(s. a, v) 2 PPp - jo (V), and hence, our algorithm bears formal resemblance to an LCB approach.
However, this formal similarity does not imply that our approach and results can be derived from those of LCB methods. Specifically, in LCB approaches, a crucial step involves the meticulous design of the penalty term b(s,a, a, V) to satisfy the condition >/pgv - P V S b(s, a, V), ensuring that the obtained estimation V remains pessimistic compared to the true value function. This often leads to the development of a complex penalty term, which may incorporate variance (e.g., see equation (28) in Li et al. 2022
In contrast, within the DRO setting, designing an uncertainty set to uphold the aforementioned inequality either yields a loose bound on sub-optinality results in a highly intricate uncertainty set. On one hand, enlarging the uncertainty set sufficiently to accommodate P P (to ensure P.V 2 min gein qV =.. (V) and the inequality above) falls into the distribution-based construction, leading to sub-optimal sample complexity.
10

---

Published in Transactions on Machine Learning Research (06/2024)
On the other hand, adopting similar approach involving Bernstein incquality introduces dependence V into the radius, resulting in a time-varying and intricate uncertainty set akin to the one in the LCB method. Our method circumvents these issues by not mandating the above inequality for leveraging the pessimism principle. Instead, we harness the inherent pessimism of the DRO sctting and devise a straightforward yet effective uncertainty set. Although the above inequality may not hold, the robust value function we derive remains a pessimistic cstimation of the true value function, demonstrating its effectiveness and efficiency.
This underscores the fundamental disparity in motivation and design between our method and LCB approaches, highlighting the novelty of our approach.
We present a comparative analysis of our results alongside those of the most closely related works in Table ! As evidenced by the comparison, our approach stands out as the first model--uncertainly-beee the minimax optimal sample complexity in offline RL. Notably, we observe variations in the assumptions made across these works, particularly concerning the adoption of the clipped version of the singlepoolicy rabcentrability. We meticulously specify these variations in our comparison. However, as previously discussed, the single-policy clipped concentrability is inherently smaller than its unclipped counterpart. Consequently, our assumption is comparatively weaker, enabling our results to directly follow if we adopt the unclipped assumption.
method to achieve
Approach Type
Assumption
Asymplotic Sample
Computational
Complexity
Complexity
Our Approach
DRO
Single-policy, clipped
S0 [113-)3
Polynomial
Rashidinnjaad et al.]
LCB
Single-policy
0 S0 ((1-g)}
Polynomial
2021
(Uehara & Sun
DRO
Single-policy
0 $20
NP-Hard
2021)
PPanaganti et al.
DRO
Single-policy
0 S#C
Polynomial
[1-13²
2023)
Li et al. 2022
LCB
Single-policy, clipped
0
SC" (11-g)3
Polynomial
[Rshidineeadd et al.,
Minimax bound
Lower
Single-policy
SO"" 2[1-g}3
2021)
Table 1: Comparison with related works.
4 Experiments
We adapt our DRO framework under two problems, the Garnet problem 9(30, 20) (Archibald et al. 1995). and the Frozen-Take problem [Brockman et al. 2016) to numerically verify our results.
In the Garnet problem, 8] = 30 and |A| 20. The transition kernel P p= (P2, E 8,a E A} is randomly generated following normal distribution: P ~ N(wg, of) and then normalized, and the reward function r(s a) ~ N(vg, v where wi, og, Ui, w/ ~ Uniform(0, 100].
In the Prozen-Lake problem, an agent aim to cross a x 4 frozen lake from Start to Goal without falling into any Holes by walking over the frozen lake.
In both problems, we deploy our approach under both global coverage and partial coverage conditions. Specifically, under the global coverage setting, the dataset is generated by the uniform policy <(ass) = Å
And under the partial coverage condition, the dataset generated according to u(s.a) a) loaet(e) + 1a29 where yj is an action randomly chosen from the action space A.
11

---

Published in Transactions on Machine Learning Research (06/2024)
At each time step, generate 40 new samples and add them to the offline dataset and deploy our DRO approach it. We also deploy the LCB approach (Li et al. 2022) and non-robust model-based dynamic programming as the baselines. We run the algorithms independently 10 times and plot the average value of the sub-optimality gaps over all 10 trajectorics. We also plot the 95th and 5th percentiles the 10 curves as the upper and lower envelopes of the curves. The results are presented Figure [ can be seen from the results that our DRO approach finds the optimal policy with relatively less data; The LCB approach has similar convergence rate the optimal policy, which verifies our theoretical results; The non-robust DP converges much slower, and even converge to sub-optimal policy. The results hence demonstrate the effectiveness and efficiency of our DRO approach.
Maturstust
robuat
(CB
5e speppsty
roburt Rabust to LCB
dataset
dataent
Garnet
Problem under (b) Garnet Problem under par- (c)
Frozen-Lake under global (d) Frozen-Lake under partial coverage
global coverage
tial coverage
coverage
Figure 1: Sub-optimality gaps of Robust DP, LCB approach, and Non-robust DP.
5 Conclusion
In this paper, revisit the problem of offline reinforcement learning from novel angle of distributional robustness. We develop DRO-based approach to solve offline reinforcement learning. Our approach directly incorporates conservatism in estimating the transition dynamics instead of penalizing the reward of liss-visited state-action pairs. Our algorithms are based on the robust dynamic programming approach, which is computationally efficient. We focus on the challenging partial coverage setting, and develop two uncertainty sets: the distribution-base and the less conservative falttiofnntion--- based. For the distribution- uncertainty set, theorctically characterize its sample complexity, and show it matches with the best one of the LCB-based approaches using the distribution-best bonus term. For the value-function-base uncertainty set, we show its sample complexity is asymptotically minimax optimal, with a constant- burn-in cost. Our results provide a DRO-based framework, an alternative approach to efficiently and effectively solve the problem of offline reinforcement learning.
6 Acknowledgement
This work is supported by National Science Foundation under Grants CCF-2007783, CCF-2106560 and (CCS-2337375 (CAREER).
This material is based upon work supported under the AI Research Institutes program by National Science Foundation and the Institute of Education Sciences, U.S. Department of Education through Award # 2229873 National Al Institute for Exceptional Education. Any opinions, findings and conclusions recommendationss expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation, the Institute of Education Sciences, or the U.S. Department of Education.
12

---

Published in Transactions on Machine Learning Research (06/2024)
References
Alekh Agarwal, Sham Kakade, and Lin F Yang. Model-based reinforcement learning with generative model is minimax optimal. In Conference on Learning Theory, pp. 67-83. PMLR, 2020a.
Rishabh Agarwal, Dale Schuurmans, and Mohammad Norouzi. An optimistic perspective on offline reinforce- ment learning. In International Conference on Machine Learning, pp. 104-114. PMLR, 2020b.
András Antos, Csaba Szepesvári, and Rémi Munos. Fitted Q-iteration in continuous action-space MDPs. In Proc. Advances in Neural Information Processing Systems (NIPS), volume 20, pp. 9-16, 2007.
TW Archibald, KIM McKinnon, and LC Thomas. On the generation of Markov decision processes. Journal of the Operational Research Society, (033):34436.11 1995.
Vipul Arora, Arnab Bhattacharyya, Clément L Canonne, and Joy Qiping Yang. Near-optimal degree testing for bayes nets. Xixiv preprint arXiv:2344006733 2023.
J Andrew Bagnell, Andrew Y Ng, and Jeff G Schneider. Solving uncertain Markov decision processes. 09 2001.
Jalaj Bhandari and Daniel Russo. On the linear convergence of policy gradient methods for finite MDPs. In Proc. International Conference on Artifical Intelligence and Statistics (AISTATS), pp. 2386-2386 2386-2394. PMLR, 2021.
Mohak Bhardwaj, Tongyang Xie, Byron Boots, Nan Jiang, and Ching-An Cheng. Adversarial model for offline reinforcement learning. arXiv preprint arXie:2302.11048. 2023.
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 wxXiu:2305.0963) 2023.
Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. OpenAl Gym. arXiv preprint arXiv:1606. 01540, 2016.
Jacob Buckman, Carles Gelada, and Mare G Bellemare. The importance of pessimism in fixed-dataset policy optimization. Xrxiv preprint XrXi::2009. 06799, 2020.
Clément L Canonne. A short note on learning discrote distributions. arXiv preprint arXiv:2002.11457, 2020.
Jonathan D Chang, Masatoshi Uehara, Dhruv Sreenivas, Rahul Kidambi, and Wen Sun. Mitigating covariate shift in imitation lcarning via offline data without great coverage. arXiv preprint arXiv:2106. 03200,, 2021.
Jinglin Chen and Nan Jiang. -hhhroaciion-hheortticc considerations in batch reinforcement learning. In International Conference on Machine Learning, pp. 1042-1051. PMLR, 2019.
Jinglin Chen and Nan Jiang. Offline reinforcement learning under value and density-ratio realizability; the power of gaps. In Uncertainty in Artificial Intelligence, pp. 378-388, PMLR, 2022.
Minshuo Chen, Yan Li, Ethan Wang, Zhuoran Yang, Zhaoran Wang, and Tuo Zhao. Pessimism meets invariance: Provably efficient offline mean-field multi-agent, RL. Advances in Newral Information Processing Systems, 34, 2021.
Qiwen Cui and Simon S Du. When is offline two-player zero-sum Markov game solvable? ar Xiviv preprint arXiv:2201.03522 2022.
Yaqi Duan, Zeyu Jia, and Mengdi Wang. Minimax-optimal off-policy evaluation with linear function approximation. In Proc. International Conference Machine Learning (ICML), pp. 2701 2709. PMLR, 2020.
Amir Massoud Farahmand, Rémi Munos, and Csaba Szepesvári. Error propagation for approximate policy and value iteration. In Advances in Neural Information Processing Systems, 2010.
13

---

Published in Transactions on Machine Learning Research (06/2024)
Justin Fu, Aviral Kumar, Ofrr Nachum, George Tucker, and Sergey Levine. D4RL: Datasets for deep data-driven reinforcement learning. arXiv preprint wrXic:2044007110 2020.
Scott Fujimoto, Edoardo Conti, Mohammad Ghavamzadeh, and Joelle Pineau. Benchmarking batch deep reinforcement learning algorithms. arXiv preprint Xiv:19900.00 708, 2019a.
Scott Fujimoto, David Meger, and Doina Precup. Off-policy deep reinforcement learning without exploration. In International Conference on Machine Learning, pp. 2052 2062. PMLR, 2019b.
Scyed Kamyar Seyed Ghasemipour, Dale Schuurmans, and Shixiang Shanc Gu. EMaQ: Expected-max Q-learning operator for simple yel. effective offline and online RL. ar preprint arXiv:2007.1109) 2020.
Caglar Gulcchre, Ziyu Wang, Alexander Novikov, Tom Le Paine, Sergio Gómez Colmenarejo, Konrad Zolna, Rishabh Agarwal, Josh Merel, Daniel Mankowitz, Cosmin Paduraru, et al. RL unplugged: Benchmarks for offline reinforcement learning. arXiv preprint Xrx:::2006. 13888, 2020.
Kaiyang Guo, Shao Yunfeng, and Yanhui Geng. Model-based offline reinforcement learning with pessimism- modulated dynamics belief. Advances in Neural Information Processing Systems, 35:449 461, 2022.
Jiafan He, Dongruo Zhou, and Quanquan Gu. Nearly minimax optimal reinforcement learning for discounted MDPs. Advances in Neural Information Processing Systems, 34:22288 22300, 2021.
Mao Hong, Yue Wu, and Yanxun Xu. Pessimistic model-based acto------ for oflline reinforcement learning: Theory and algorithms, 2023. URL httpps//pooaaaaeeeeeeee////////s
Garud N Tyengar. Robust dynamic programming. Mathemalics of Operalions Research, 30(2):257 228-2800 2005.
Natasha Jaques, Asma Chandeharioum, Judy Hanwen Shen, Craig Ferguson, Agata Lapedriza, Noah Jones, Shixiang Gu, and Rosalind Picard. Way off-policy batch deep reinforcement learning of implicit human preferences in dialog. arXiv preprint arXie:1907.00455 2019.
Nan Jiang. On value functions and the agent-cnvironment boundary. arXiv preprint 19w5 2019.
Nan Jiang and Jiawei Huang. Minimax value interval for off-policy evaluation and policy optimization. Advances in Neural Information Processing Systems, 33:2747 2758, 2020.
Ying Jin, Zhuoran Yang, and Zhaoran Wang. Is pessimism provably efficient for offline RL? In International Conference on Machine Learning, pp. 5084-5096, 2021.
Rahul Kidambi, Aravind Rajeswaran, Praneeth Netrapalli, and Thorsten Joachims. MOReL: Model-based offline reinforcement learning. Advances in neural information processing systems, 03:21810-21822, 2020.
B Ravi Kiran, Ibrahim Sobh, Victor Talpaert, Patrick Mannion, Ahmad Al Sallab, Senthil Yogamani, and Patrick Pérez. Deep reinforcement learning for autonomous driving: A survey. IEEE Transactions Intelligent. Transportation Systems, 23(6):4909 4926, 2021.
Aviral Kumar, Justin Fu, George Tucker, and Sergey Levine. Stabilizing off-policy Q-lcarning via. bootstrapping error reduction. arXiu preprint arXiv: 1006:990.000 990.00949999 2019.
Aviral Kumar, Aurick Zhou, George Tucker, and Sergey Levine. Conservative Q-learning for ofllie reinforce- ment learning. arXiv preprint arxiv:0006.0 04779, 2020.
Sascha Lange, Thomas Gabel, and Martin Riedmiller. Batch reinforcement learning. In Reinforcement learning, pp. 45 73. Springer, 2012.
Romain Laroche, Paul Trichelair, and Remi Tachet Des Combes. Safe policy improvement with bascline bootstrapping. In International Conference on Machine Learning, pp. 3652 3661. PMLR, 2019.
Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu. Offline reinforcement learning: Tutorial, review, and perspectives on open problems. Xixio preprint 2r55::0005.01643, 2020.
14

---

Published in Transactions on Machine Learning Research (06/2024)
Gen Li, Laixi Shi, Yuxin Chen, Yuejie Chi, and Yuting Wei. Settling the sample complexity of model-based offline reinforcement learning. in preparation, 2022.
Peng Liao, Zhengling Qi, and Susan Murphy. Batch policy learning in average reward Markov decision processes. Xiv preprint arXiv:2007.11711, 2020.
Boyi Liu, Qi Cai, Zhuoran Yang, and Zhaoran Wang. Neural trust region/ / policy optimization attains globally optimal policy. In Proc. Advances in Neural Information Processing Systems (NeurIPS), 2019.
Yao Liu, Adith Swaminathan, Alekh Agarwal, and Emna Brunskill. Provably good batch reinforcement learning without great exploration. arXiv preprinl ar arv::2007..0880 2020.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. nature, 518(7540):529-333) 533, 2015.
R. Munos and C. Szepesvari. Finite-time bounds for fitted value iteration. Journal of Machine Learning Research, 9:815 857, May 2008.
Rémi Munos. Performance bounds in fy-norm for approximate value iteration. SIAM journal on control and oplimization, 46(2):5411566 561, 2007.
Ofir Nachum, Bo Dai, Nlya Kostrikov, Yinlam Chow, Lihong Li, and Dale Schuurmans. AlgaeDICE: Policy gradient from arbitrary experience. XrXiv preprint arXiv:191.002074, 2019.
Arnab Nilim and Laurent El Ghaoui. Robustness in Markov decision problems with uncertain transition matrices. In Proc. Advances in Neural Information Processing Systems (NIPS), pp. 639-846, 2004.
Tomohiro Nishiyama and Igal Sason. On relations between the relative entropy and x 2-divergence, general- izations and applications. Entropy, 22(5):563, 2020.
Kishan Panaganti and Dileep Kalathil. Sample complexity of robust reinforcement learning with a generative model. In International Conference on Arlificial Intelligence and Stalistics, pp. 9582 9602. PMLR, 2022.
Kishan Panaganti, Zaiyan Xu, Dileep Kalathil, and Mohammad Ghavanzadeh. Robust reinforcement learning using offline data. arXiv preprint S.fr:2208.051222 2022.
Kishan Panaganti, Xu Zaiyan, Kalathil Dilcep, and Ghavamzadeh Mohammad, Bridging distributionally robust learning and offline rl: An approach to mitigate distribution shift and partial data coverage. ar preprint ar 2rc::23310 18434, 2023.
Xue Bin Peng, Aviral Kumar, Grace Zhang, and Sergey Levine. iivaantag--eigghte regression: Simple and scalable off-policy reinforcement learning. arXiv preprint arXiv:1910.00 107.07777.. 2019.
Paria Rashidinejad, Banghua Zhu, Cong Ma, Jiantao Jiao, and Stuart Russell. Bridging offline reinforcement learning and imitation learning: A tale of pessimism. In Proc. Advonces in Neural Information Processing Systems (NewrIPS), volume 34, pp. 11702-11716, 2021.
Paria Rashidinejad, Hanlin Zhu, Kunhe Yang, Stuart Russell, and Jiantao Jiao. Optimal conservative offline Il with general function approximation via augmented lagrangian. ar preprint arXiv:2211.00716, 2022.
Mare Rigter, Bruno Lacerda, and Nick Hawes. Rambo-rl: Robust adversarial model-based offline reinforcement learning. arXiv preprint arXiv:2204. 12581, 2022.
Stephane Ross and J Andrew Bagnell. Agnostic system identification for model-based reinforcement lcarning. arXiv preprint arxiv:1209 1007, 2012.
Jay K Satia and Roy E Lave Jr. Markovian decision processes with uncertain transition probabilities. Operations Research, 21 (3):7228-77)) 1973.
15

---

Published in Transactions on Machine Learning Research (06/2024)
Bruno Scherrer. Approximate policy iteration schemes: A comparison. In Proc. International Conference
Machine Tearning (ICML), pp. 1314-1322, 2014.
Laixi Shi and Yuejie Chi. Distributionally robust model-based offline reinforcement learning with near-optimal sample complexity. arXiv preprint orXiv:2208.055: 057667 2022.
Laixi Shi, Gen Li, Yuting Wei, Yuxin Chen, and Yuejie Chi. Pessimistic Q-learning for offiine reinforcement learning: Towards optimal sample complexity. International Conference on Machine Learning, pp. 19967 20025, 2022.
Laixi Shi, Gen Li, Yuting Wei, Yuxin Chen, Matthieu Gcist, and Yuejie Chi. The curious price of distributional robustness in reinforcement learning with generative model. arXiv preprint or orXhu:2305.1658) 2023.
Noah Y Siegel, Jost Tobias Springenberg, Felix Berkenkamp, Abbas Abdolmaleki, Michael Neunert, Thomas Lampe, Roland Hafner, and Martin Riedmiller. Keep doing what worked: Behavioral modelling priors for offline reinforcement learning. Xrviv preprint arXiv:2002.06: 08396, 2020.
David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Dricssche, Julian Schrittwieser, Ioannis Autonoglou, Veda Panneershelvam, Marc Lanctot, et al. Mastering the game of Go with deep neural networks and tree search. nature, 529(7587)):48) 489, 2016.
Masatoshi Uehara and Wen Sun. Possimistic model-based offline reinforcement learning under partial coverage. arXiv preprint arX:m:2107.0622) 2021.
Masaloshi Uehara, Jiawei Huang, and Nan Jiang. Minimax weight and Q-function learning for off-policy evaluation. In Proc. International Conference on Machine Learning (ICML), pp. 9659-9668. PMLR, 2020.
Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47.
Cambridge university press, 2018.
Lingxiao Wang, Qi Cai, Zhuoran Yang, and Zhaoran Wang. Neural policy gradient methods: Global optimality and rates of convergence. In International Conference on Learning Representations, 2019.
Ziyu Wang, Alexander Novikov, Konrad Zolna, Josh S Merel, Jost Tobias Springenberg, Scott Reed, Bobak Shahriari, Noah Siegel, Caglar Gulechre, Nicolas Heess, et al. Critic regularized regression. Aduances in Neural Information Processing Systems, 33, 2020.
Tsachy Weissman, Erik Ordentlich, Gadiel Seroussi, Sergio Verdu, and Marcelo J Weinberger. Inequalities for the 11 deviation of the empirical distribution. Hewlett- Packard Labs, Tech. Rep, 2003.
Wolfram Wiesemann, Daniel Kuhn, and Berş Rustem. Robust Markov decision processes. Mathematics of Operations Research, 38(1):153 183, 2013.
Yifan Wu, George Tucker, and Ofir Nachum. Bchavior regularized offline reinforcement learning. arXiv preprint 1rX1e:1911.1191,, 2019.
Tengyang Xie and Nan Jiang. Batch value-funetion approximation with only realizability. arXiv preprint Stt::0088009900 2020.
Tengyang Xie and Nan Jiang. Batch valno-function approximation with only realizability. In International Conference on Machine Learning, pp. 11404-11413. PMLR, 2021.
Tengyang Xie, Ching-An Cheng, Nan Jiang, Paul Mineiro, and Alekh Agarwal. Bellman-consistent pessimism for offline reinforcement learning. arXiv preprint Xit:22066006926 2021a.
Tengyang Xic, Nan Jiang, Huan Wang, Caiming Xiong, and Yu Bai. Policy finetuning: Bridging sample- efficient offline and online reinforcement learning. Advances in neural information processing systems, 34: 27395-27407, 2021b.
16

---

Published in Transactions on Machine Learning Research (06/2024)
Zaiyan Xu, Kishan Panaganti, and Dileep Kalathil. Improved sample complexity bounds for distributionally robust reinforcement learning. In International Conference on Artificial Intelligence and Stalistics, pp- 9728 9754. PMLR, 2023.
Yuling Yan, Gen Li, Yuxin Chen, and Jianqing Fan. The efficacy of pessimism in asynchronous Q-learning. arXiv preprint arXtm:2203.074 07368, 2022.
Wenhao Yang, Liangyu Zhang, and Zhihua Zhang. Towards theoretical understandings of robust Markov decision processes: Sample complexity and asymptotics. arXiv preprint arXiv:2105.0883 2021.
Ming Yin and Yu-Xiang Wang. Towards instance-optimal offline reinforcement learning with pessimism. Advances in neurol informalion processing systems, 34, 2021.
Ming Yin, Yu Bai, and Yu-Xiang Wang. Near-optimal provable uniform convergence in offline policy evaluation for reinforcement learning. In International Conference Artificial Intelligence and Statistios, pp. 1567 1575. PMLR, 2021.
Chao Yu, Jiming Liu, Shamim Nemati, and Guosheng Yin. Reinforcement learning in healthcare: A survey. ACM Computing Surveys (CSUR), 55(1):1-36, 2021a.
Tianhe Yu, Garrett Thomas, Lantao Yu, Stefano Ermon, James Zou, Sergey Levine, Chelsea Finn, and Tengyu Ma. MOPO: Model-based offline policy optimization. Advances in Neural Information Processing Systems, 33:14129-144 14142, 2020.
Tianhe Yu, Aviral Kumar, Rafael Rafailov, Aravind Rajeswaran, Sergey Levine, and Chelsea Finn. COMBO: Conservative offline model-based policy optimization. arXie preprint arXiv:2102.0 00b:2102.00363, 2021b.
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, 2021.
Junjie Zhang, Jiafei Lyu, Xiaoteng Ma, Jiangpeng Yan, Jun Yang, Le Wan, and Xiu Li. Uncertainty-driven trajectory truncation for model-based offline reinforcement learning. arXiv preprint arXiv:234,046600 2023.
Junyu Zhang, Alec Koppel, Amrit Singh Bedi, Csaba Szepesvari, and Mengdi Wang. Variational policy
gradient method for reinforcement learning with general utilities. In Proc. Advances in Neural Information Processing Systems (NeurIPS), volume 33, pp. 4572-4583. 2020a.
Shantong Zhang, Bo Liu, and Shimon Whiteson. GradientDICE: Rethinking generalized offline estimation of stationary values. arxiv preprint arXiv:2001.11115, 2020b.
Han Zhong, Wei Xiong, Jiyuan Tan, Liwei Wang, Tong Zhang, Zhaoran Wang, and Zhuoran Yang. Pessimistic minimax value iteration: Provably efficient cquilibrium learning from offline datascts. arviv preprint
arXiv:2202.07511 2022.
17

---

Published in Transactions on Machine Learning Research (06/2024)
A Notations
We first introduce some notations that are used in our proofs. We denote the numbers of states and actions by S, A, i.e., |8| = 5, | = A. For a Iransition kernel P and a policy n, D denotes the transition matrix induced by them, ie., P (s) E. [ E A(S).
For any vector E RR$ V VoVe E R denotes the entry-wisc multiplication, i... Vo V(s) V(s) * V(s). For distribution g E A(8), it is straightforward verify that the variance of V w.r.t. q can be rewritlen (V) qVV V) (gV)².
B Proofs of Section 3.1
In this section, present our proofs of the results under the distribution- based construction.
We first note that Lemma 1 can be directly obtained from the existing results of concentration incquality,
e.g., Theorem from (Canonne) 2020 or Theorem 2.2 from [Weissman et al. 2003) Hence the proof is omitted here.
Thcorem 3. (Restatement of Theorem With probability at least 26, it holds that
8SC* log NS
2
248 log SA 8
VP' (p) - Vp- (p) - (1-
+ (1 - 7)
(13)
N
To oblain un 6-oplimal policy, dalaset of size
N N 0 (
SC (1-7)
(14)
is required.
Proof. In the following proof, we only focus on the case when
8SC" log NS
N 1-7
(15)
Otherwise, eq. follows directly from the trivial bound Vp (p) - (p) --
According Lemma with probability least hence
8, A क. Moreover, due to the fact r(s, f(s.a),
(s) 2 V.p(s)
V F.3 (s)
(16)
for any x and E 8, where VHP denotes the value function w.I.t. P and reward Thus Vp 2 V for any policy
Therefore,
Vr (F)( - (s)
Vp*
Vp (s) (s) VV -s) -Vp
(s)
< / (s) -V- (s)
= r (r(,,=(())) ppT p0m"(+) (+) VV
r((s, f(s, - (6)) (sl -70 (V (v
- rr(s,7((s)) f(s.m² + (5) vo (s) + 7p- "ppp"(() yr -
(5)
=r(s,7((s)) f(s, ((s,TT(()) , (9) (Vo"" - -V (p= ()) -ogr(1 (V5
18

---

Published in Transactions on Machine Learning Research (06/2024)
- ypr (VP - +bb(((
(17)
(s, where (a) is from v5)(s) max, (s, 2
f(s, + t (V and (s)) r(s, ((s,)*(s)) f(s, (s)) + + ( V 100rr
e
Recursively applying this inequality further implies
d 10-11-7 1-1(0
V (p) V
(p) = 1-7
(18)
where d dd Ei PP((s r'oo' -So p. T,, P) is the discounted visitation distribution induced by n and P.
To bound the term in eq.
17
we introduce the following notations.
NS
Sg Nu(s, T (s)) S 8 log
(19)
5
NS
Sj _ Np(s, T (s) 8 log 8
(20)
The two sets divide the state space into two sub-spaces. 8, contains the states that have less probability in the behavior distribution μ its corresponding optimal action, and are frasunreyy covered by the dataset; And 8 are the ones that have larger probability, and are more froquently covered.
For E S,, from eq.
15 we have that
min c (s),
(o),
1) 5J
SC xss) 1 8C" log NS
(21)
N
S
which further implies that d= (s) E
80 log
Hence
N
1 8SC* log
Σ sEa,
dt (V)6 <
(22)
1-7 N
which is due to (s) A (s), f(8 x5 (s)) + V
10 5 +1)
We then consider 8;. From the definition, (=(s,T((s)) 8log NS. probability 1 8,
According to Lemma with
max(12N T- (s)), 8 log N } 2 Np(s, x" xs))) > 8 8log 8
NS
NS
(23)
8
hence max(12N T" (s)). 8 Slog NS = 12N n" (s)) and N(s. a (s)) 2 log
NS 8
> 0. This hence implics
that for any s e St, N(s, (s)) > 0 and f(s, x* (s)) = (s)) (s)). Thus
1 (V(V 7 |P VT. opr ) - |PT (4) (1)
Q (5) - Ix
S log 3
SA
$ 1 1-7
min 2, 2 2N (s. T- (s))
25 2ogog SA 8
(24)
N(s, (8))
Moreover, from eq.
23
12
120T*
12
N minn (d (s), 11 5
+
(25)
N(a (s))
Np(s,T*(5)) π
g)
N
d (s)
19

---

Published in Transactions on Machine Learning Research (06/2024)
Combining with eq.
24 further implies
1
SA
12C**
1
16 (VT))
S
25 log
8
V
N
d (s)
+ +S)
1
SA
120**
1
SA
120
2S 2S log
2S log 8
S.
(26)
N
d= (8)
N
Thus
24SC** log SA
248aC log SA
Σ
d (8)b (s)
(V)
v d (s)
N
N
868
24 log
24 log 94
2
SA 24 log
0
(27)
Thus combining eq.
22
and eq. 27 implies
V/ (p) vp)
d=', 1bb'(( (V
2 8S0* log NS
1
2 log S4
+
(28)
(1 7)2
N
(1 7)2
N
which completes the proof.
C Proofs of Section 3.2
In this section, provide refined analysis of the sub-optimality gap using Bernstein's Inequality,
C.1 Existence of the Target Policy
In this section, first prove the claim made after Alg i.c., there exists an optimal robust policy æ to the constructed uncertainly set P, such that N(8, x()) 0, vs E S.
Lemma 2. Recall the set g0 E 8: N(s) 0}. Then
(1). For any policy and E 80, V (s) 00
(2). There erists deterministic robust optimal policy my, such that for any & 80, ((), 0.
Proof. Proof of (1).
For any E 80, it holds that N(s,, a) 0 for any a A. Hence f(s, and fे. A(8).
Then for any policy and A, it holds that
(s. f(s. a) + (V3 (0 <21))
(29)
Thus
(s) Σ x(als) (s)
(30)
20

---

Published in Transactions on Machine Learning Research (06/2024)
which implics VJ =0 together with Vig 2 O.
Proof of (2).
We prove Claim (2) by contradiction. Assume that for any optimal policy Tr, there exists & 8 such that ((s,, TH (s)) = 0. We then consider a fixed pair (T.
(ss, T (s)) further implies f(s, (s)) 0, (g)(()) A(8), and
Φ (s) = max a) Q (s, (x)) = =f(s, (s)) 20 (V²") S 7' (s),
(31)
where the last inequality is from p = A()), f(s, TT = o, and Jprial (V S 1.V (s). This further implies that 1 (s) 0 because V 2 0.
On the other hand, since 8 & 8", there exists another action + (8) such that N(s, b) > 0, and hence f(s, b) r(s,b). There can only be two cases as follows.
(I). If (s) b) 0, then
(s, = f(s, 1o
70 (V," > 0 = 2% (s,
(32)
which is contradict to v (s) = max, (s. = 07 (s)).
(II. If b)) 0, Lemma then implics the modified policy (T()) is also optimal, and satisfies (2, (f(x)) = (ar, (x)) for any + 8, and N(s, (T))( 0.
Then consider the modified policy fT(T)).
If there still cxists s' & 8 such that N(s', (((,)))) = O, then similarly, there exists another action V # (=)) such that N(s' > 0. Then whether r(s', b) O, which falls into Case (T) and leads to a contradiction, or applying Lemma 3 again implies another optimal policy f (ff(z,)), such that (ss, f (J)())))()) N(s' .5 (T.()))
(((x)) > 0 for x & {8. s'). N(s, SJ (f))))))))) N(s, f (x, (s)) 0 and
Repeating this procedure recursively further implies there exists optimal policy æ, such that N(s, T()) > 0 for any & 80, which is contraction to our assumption.
Therefore it completes the proof.
Lemma 3. For deterministic robust optimal policy Tr, if there erists state & 8 and an action b such that N(s, (s)) = 0, r(s, b) =0 and (s, > 0, define a modified policy fö (m,) as
[6) = (TT)) T., (x), for t
(33)
(34)
Then the modified policy (TT,) is also optimal.
Proof. Define modified uncertainty set Job
(T A(S),
(35)
(p)) = fa for (α, + (s,
(36)
Then we have that Po C (Pb)2. for any (z, a) 8 x A, which further implics that
Vll(
> (mm)
(37)
5b
Now we have that
v ( (Tr) (s)= - 10(m)) - (s, = r(s,
70 (
(V
S (1
(8),
(38)
21

---

Published in Transactions on Machine Learning Research (06/2024)
which further implies v (s) O. Note that in eq. (31), we have shown (g 0, hence V V (s) O.
(s)
P2
Py
Now consider the two robust Bollman operator (= -. (a(m))aa))((((z,))) a) + +ho ( (V) and TV
f(2z, Tr (z)) + t (V). It is known that v/((=)) is the unique fixed point of the robust Bellman operator T and V is the unique fixed point of T. When x #
(V).
/9
(x) Σ EMMAaaa) 7o (02) (V
@ Σ (alx)) (a (V (V)"))
f(x, (x)) +
(Vz))
f(2, Tr (x)) 10 (r
T (x) V (x),
(39)
where (a) from (xx) = ni (x) when x + 8, (b) from (Pa) -0)))(10 p).(())
And for recall that (ss TH. (8)) 0, hence f(s, ग (s)) and p-.(0) = A(8). Thus
TE (s) = f(. 70 ( (V²
f(s, ne (5)) 70 ((8) (17
@ f( (8)) + 70 p (V
TVT (s)
VTT(s))
(40)
where (a) from (Pb) = A(8) and (() = r(s,b) = 0 =0= -((8, n, (8)), and (b) follows from the fact (5)(6) A8)).
Combining eq. 39 and eq. [r V V 5
40
further implies that v is also a fixed point of Tg. Hence it must be
identical V i.e. Pb
Combine with eq.
have
((r)
(((())) VT.
(41)
pb
which implies that J8 (m,) is also optimal with N(s, (E (T) ((, 0. And since (T())) (T) for # s, then N(x, (T.) N(x,,,())) This thus completes the proof.
]
Theorem 4. (Restatement of Thm 2 Consider the robust MDP Mi, there exist an optimal robust policy Tि. and some universal constant K, such that if N (T (T-) mem holds that
KSC** log 4SAN (1-2)8
384 log 4SAN (1-7)8
VP (p)- - (p) S
(42)
(1-7)3N
7 Amin
with probability least 1 48.
Proof. We first have that
VT 1/
VI
V
(43)
1
A
4
22

---

Published in Transactions on Machine Learning Research (06/2024)
Note that equation 42 can be directly obtained if
SKC" T log NS 5
N
(44)
1 1-7 7
or
384 384 log"
48AN (1-7)8
N S (1 Pmin
(45)
Hence in the following proof, we only focus on the case when
N > max
SKC log NS
1
384 384 log2
(1-7)6
1SAN
(46)
1
(1 >)SC Miin
(1
7)/4minn
Clearly it holds that 8log A/ and thus Lemma 8 of Shi & Chi 2022) states that under eq. (46), with probability 1 - 6, it holds that
solds"thai
N(s.a) a) 2 Np(s, a)
8log 4SA a).
(47)
This morcover implics that with probability 1- 6, if p(s, a) > 0, then N(s, > 0. We hence focus on the case when this event holds.
The remaining proof can be completed by combining the following two theorems.
Theorem 5. With probubilily al least 26, il holds that
SC log
4SAN 11-
80Sq log NS
96
48SC log 4SAN (1-3)Ø
A S
+
(48)
2NN
21
(1 N
Proof. We first define the following set:
So (s:d' (8) = =0]-
(49)
And for E So, it holds that d= (s) > O.
We first consider 8 & Sg. Due to the fact d= (x) > 0, hence d= (s, (s)) = d= (s) > 0. Thus it
implics that p(s, x (s)) > O, and equation 47 further implics N(s, x (8)) > 0 and ((s) = r(ss, x (s)).
Hence we have that
VP (8) V (5) r(, (s)) + 7p- - Vs
(a) I Pp (p (5) pp (VZ)
$
-p: ->pp ->p 7p (0) va.
pp (VEr)
$
(V - -Vz") + 7T(p (PP''( (5) 1 -3gg (Vztt))
(50)
where (a) is from (T = max, 0F (s) 2 ((8 = f(a, (s)) + 30 (0) (V = =((8 =(8, (s)) +
No (V
For E Sg, it holds that
V (s) (s) = r(s, π (()) -ypT'(') Vs
>p-" (5) Vp- -703r' (V7 + r(s, ग. (s) f(s, (s))
< >p (5((') -V7 + (P. - (') ogr (VS")) +
(51)
23

---

Published in Transactions on Machine Learning Research (06/2024)
where (a) follows similarly from eq- (50) and the last inequality is from r(s, s 1.
Hence combining eq. 50 and eq. 51 implies
(8)
(s) S (p - +b((((s))))))))
(52)
where b*())ss) a (PT ( - pp (V) s & So: and (v) 1 + 7P (y - (0 for s E 8p.
Moreover we set
b(V))))) max 10, (V))
(53)
then it holds that (*(g"") S b(
Then apply eq. 52 recursively and we have that
A A S 1
d= d0" b(VZ)))
(54)
Not that for So it holds that d=d (s) 0, and
& (F..(VV'))
Σ d (s))(1)))s). 8480
(55)
This implies that we only need to focus on & Sg. We further defined the following sets:
NS
8, A
s Φ Sp x*)) < 8
(56)
NS
81
A
& 80 =)(8,='(s)) 8 log
(57)
For E 8,, we have that
1
80""
log NS (a)
1 S
min ds (5), 3 35)13}
TT u(s, (s))
(58)
where (a) is due to the fact eq. 46
This further implies that d=t (s) < SC log Hence
2 8SC#" log NS
Σ d" (() = 1-7 N
(59)
s
which is due to ||PT (1) |
Jggt (V -
We then consider E St. Note that from the definition and equation Sp.
47 it holds that N(s > 0 for
Therefore it holds that
(())))))) s 11pp" -o - (VFr))
S (0pp""))) - (s)
var -G) (VV" (V
log ASAN Var Varp- (V) (V77))
< (0 - p.. (.(()) +
{1-
(60)
N(s (s))
24

---

Published in Transactions on Machine Learning Research (06/2024)
where the last incquality is shown as follows.
Since P (4)
p**(*)
Sgg, we have that P (4) V 2 (v Now note that it is shown in lyengar
2005
Shi
et al. 2023 that
(10 (V3))
max MEJOV "1
x (1 - -1) -v 1t"s 1151(0) Varp: (c) (V - =H)
(61)
Thus
(7pp((0) VT. -0gr.cn (V)
1
=pp=' (0) (e)
V - -00 (V7))
=>pp"(0 v
( -7 max
(1) -M) R/
11-(() (+)
Varg: (V 1)
RElU.V
(a)
S pp: (5) (S 7 (V v R5 (+) Varpprco (VFT.)
= = R
Varp (VT"),
(62)
where (a) is due to the maximum term larger than the function value at μ = O, and this incquality completes the proof of Equation (6))
To further bound eq. 60 we invoke Lemma 6 and have that
V $
p (o) VT
Var (o)
(o) (V
4SAN log (1-7)8
74 log 4SAN (1-7)6
< 121
+
(88 (s))
(1 -1-71 N T- (s))
4SAN log (1-2)6
4SAN 41 log (1-7)8
4SAN 74 7o (1-y)8
$ 12
2Var (V3+)
N(s, T (s))
(1 - (1-7)2 N(s, (s, (s))
(1- (s, x (s))
4SAN 2 log [1-7]0 Var
(74 + 12 41) log 45AN
< 121
par):)))) (Va))= +
(1-7)6
(63)
N(s, x" (s))
(1 (s,
where the last inequality is from v2 + u Vo V Combinc eq. 660 and eq.
63), we further have that
(s) < 24
4SAN 2 log (1-218
Var p. ( (VTT)
(74 + 12) log
(1-7)6
ASAN
log
N(s, T (s))
(1 (1-27 Ns, (s))
(1- (s,
45AN 2oo [1-2]0 Var w (V +
log 4SAN
(I-7)Ø
< 24
(64)
N(s, (s))
(1 (s,
where 6 = 75 + 12
Note that in eq. 250, we showed that N( (a))
< N
120
(S + d= )=)))) (o)) ). Hence plugging in eq. (64) implies that
4SAN n log (1-7)8
Var pr (0 (VTx)) (VS+
((VT))s) (s) S 241
N
/ d= (8)
12c T log
4SAN (1-7)0
S d (s)
(65)
(1- N (1-7)N
25

---

Published in Transactions on Machine Learning Research (06/2024)
Firstly we have that
4SAN 24CT* log 118
Σ 24d (s){
Var p. (V
VSS
N
d (s)
sE8,
4SAN 24 log
24C log 4SAN
24dh (s)
[1-7]6
Var (r)) (V
Σ
12 d (s)
[1-7]6 Var pr (VT))
N
N
sE8,
SES
1SAN 24CTT log
-41
(1-7)6
Σ EES
V d (8) Var
parp:-111 (V + Σ
d (o) Sdd (3) Vorpar (V
N
BE
(a)
49AN 24C'* log
$ 241
(1-716
VS Σ
dt (V²+)
Σ
Sd Var (V
N
SES
8E8;
49.NN =4 log
V
(1-2)8
Σ d= d=' (s) Var (VT'),
(66)
N
SES;
where (a) is from Cauchy's s inequality and the fact Eses, d= (s) 1. In addition, we have that
12c O"" log
4SAN (1-3)6
24c,SC* log 4SAN
Σ
d (8)
S (s) <
(1-7)6
(67)
(1->)N
(1 (1-7)N
Combinc the two incqualities above and we have that
Σ d'' (s)b(V 5 (s)
8
F log 4SAN
24Sc; CTT log 48AN
< 481
(1-2]8
Σ d= d= (sr (VTT)) #ESI
(1-7)6
(68)
N
7
Then we combine eq.
59 and eq.
668 and it implies that
(d"t b(V))))
Σ d" (s)b(1 + Σ d=' (ss
SEB.
sE8,
16SC" log NS
ASAN n log (1 16
24Sc, C*' log 4SAN
N + 481
Σ d (8) Var + sEBi
(1-7)6
N
(1 11-7)) >)N
S0 log NS
4SAN af log (1-7)6
+ 48
d= (s) (a) (V
(69)
(1 N
We then bound the term Eves d=d Var pT
(6) (VT)). ). We first claim the following incquality:
v - pp var
25(V 3/ 2 0.
(70)
To prove eq.
70
we note that
V (s) (s) = max (8, a)
(5,
26

---

Published in Transactions on Machine Learning Research (06/2024)
2 (s,,
+ +s)
=
- =(s, + pp=" (s) v - -pp (+) V + t20 po ( (V7))
E f(s, x (8)) + pp: (0) V - -b (VV) (s)
2 f(8, (s) + pp- (s) v5 - 26(V5 (s).
(71)
where (a) is from by (V)) (s) 2 y pp (5) Vg 7 ワ (0) (V
Hence for any s E S,
VT (x) (8) - - 3 + 2b(V) 2 ((8,=((b)) 2 0,
(72)
which proves eq. 70
Now with eq. 70
we first note that
( v) - (7/"* (V o (7p=* V3 )
z - -7p" >/'''"") o (Vz + -pبب (ig)))
< (V - -pp=" V + (²x )) (Vz + + V
< 2
7 (V - 7p" V + 25(1 ( )),
(73)
where the last inequality is due to the fact 11 + + - || S - and eq. 70
We then have that
Σ d' (s) Var (VTr)
S88
(d"), pr (V o 3 - (p=') (pr' 'イ")))
3
dm px T 3
1
(
)) + 72(1 7)
(V - -7p" V + 226( (6((3-1))
(
d pr (v V
1
V + 72(1 7)
2
(I - -pp= VV + 7211 7) ((V7-))
4
?
nr. ? (pp** - 1)( )ot)) + 22(1 7) (T 7p*
V + 72(1 7) b(V5'1)
4
(d=)) 11 - >
/
( V +
2
+ 72 7) (at (
4
?
72(1 - 7)
@ 71
1 (->
(v v + 72
2
+ 21
4
1/00t .VV;"')
2
4
S 32 VV
+
(a=', ((Vz.))
22 7)
2
4
(d=', (V )),
(74)
(1 7)
72
where (a) is from eq.
73 (b) is due to 7 < 1, (c) is from the definition of visilation distribution.
Hence by plugging eq.
74 in eq. 69 we have that
(d"" .b(V..)) ))
40c, 40c,50t** = log NS 5
ASAN 24SOT log (1-7)8
Σ d (s) Var (VT)))
(1 N + 48
N
SE8
27

---

Published in Transactions on Machine Learning Research (06/2024)
40c, SC log N
+ /
4SAN 24 log (1-7)é
2
+ 72 - 7)
(dt (((
(1 N
N
72 7)
40c 40c]SC** log
24
48SO* log ASAN
(1-7)0
48 ?
96SO log ASAN
(1-7)8
(dtt" b(V))))
+
(1 N
(1-7)A
-1- -
(4) 1
2 マ (d" B(VF))) + C2
ASAN SC" log (1-7)6
405c C log
48
48SC* log 1SAN (1-1)6
(75)
(1 >)N
(1-
7
(1 (1-7)N
where (a) is from x + y 2 va and 02 8 24 110592. This inequality moreover implies that
SC log 4SAN
80Sc, log NS
48SC** log 4SAN (1-216
(d () 202 (1 N
(1-216
(76)
-1-77 7)N
(1-
Recall the definition of A1, we hence have that
p A A < (1-7)
4SAN 20² log (I (1-2)8
S0Se log NS
96 +
48SC log 49AN
(1-2)8
(77)
(1-
(1-7)aN
This hence completes the proof of the lemma.
Theorem 6. With probobility at least 26, it holds that
384 log² 4SAN (1-288
4SAN 384 384 log
384 384 log? 4SAN
p
21
+ 2/ (1 71-3)3 umin
(1-7)8
[1-7]Ø
(78)
N2 Umin
(1-7)2N pmin
Proof. We first define the following set:
8 A E = 0}.
(79)
Note that N(s) = Ea NNss, a), hence it holds that N(s, a) = 0 for any & E 8 E A.
We moreover construct an absorbing MDP M = (8,A, f, P) as follows. For s E 8D, Pa lo=ei And for
& 80, set Ps s,
Pa P
Then for any s E 8", from Lemma 2 it holds that (s) = 0, and hence
(x) (8) - vp*((s) (x) S 0.
(80)
It further implics that
(s) 1p PT. (V +
V I 7p 3
(V= Vp
(81)
On the other hand, for & S Lemina 2 implies that N(s, (s)) 0, hence equation
47
implies N(s, n, (+)) >
0, f(s, (s)) = (s)).. Hence
(8) Vp (s)
ppg (VT)) 7PT-(s)
=7p (V -v,r) + (a (V p -p
7(apTria) (V pm-(+) + (T)
-Pt.)(
A 2 vp+)) + c(8),
(82)
where (a) is from (T) f(s, (s)). and c(s) & (0 (V (..(
28

---

Published in Transactions on Machine Learning Research (06/2024)
According to the bound we obtained in Lemma
it holds that
ASAN 48 log
(1-7)0 C1
48 1o [I-7]8
ASAN
48 log (1-2)8
1SAN
c(s) S V (1 (T) 2011
(83)
N(s, (s))
(1 (s,,) (T)
Combine eq. 81 and eq.
82 then
V3 (s) (s) S 7pT (V - VVp)) + E(s),
(84)
where
c(s)
2
48 log (I (1-530
(2,,) + 201
48 18g [1 110
((s.a.(s))
+ (1-3))(e..m
48 log [1
$ 80
(85)
80
Applying eq- (4 recursively further implies
1 (d (d",, ,),
p A S
(86)
where dh is the discounted visitation distribution induced by क. and P.
Note that eq. 466 and Lemma 8 of (Shi Chi 2022 state that with probability 1- 8, for any (s, a) pair,
Np(s,a a) llog
a(s,a)
(87)
Hence under this event, ē(s) can be bounded
4SAN 384 (1-2)8 c
45AN 384 384log²
384 log 4SAN
(1-7)6
(1-7)6
ē(s) < 21
+ 261
+ (1-7)N Mmin
(88)
N Mmin
N Npmin
Hence we have that
p A < 1
- (d"r, 2)
4SAN 384 log² (1-7)8 6
4SAN 384 log (1-
2 4SAN 384 log (1-5)8
//
2211
(1 7)a NMmin
(1 7) Munn
- (1- 2) N
ASAN 384 log
384 19AN
384 49AN
5 2V
7)- (1 33333N22 24min
+ 2V
(1-7)6
(1-2)8
(89)
(1 73 Priin
(1 - (1 Mmmn
0
D Auxiliary Lemmas
Lemma 4 (Lemma 4, et al. 2022 For any 8, with probability 1-6, max(12N(ss,)) Blog NS Nu(s,a), Vs.a.
Lemma 5 (Lemma 9, Li et al. of Pa obeying [V]] < y then with probability at least 1 1-6 8,
2022 For any (s, a) pair with N(s, > 0, if is an vector independent
48 Varp. (V) log 4N N(s,a)
48 log AN
I(Pa PIV 1
8 (1 7) (s,
(90)
5 5log
Varpa (V) 2 Varps (V) + 3(1 -
(91)
(s,a) (s(saa)
29

---

Published in Transactions on Machine Learning Research (06/2024)
Lemma 6. Suppose y [0.5, 1), with probability at least 6, it holds
4SAN Varp. (V log (1-7)6
74 74 (1 (1-716
4SAN
I(P: v - 1
(92)
((s,a) a)
(1 7) a)
4SAN 41 log (1-7)8
Varp, (Vg)) S 2 Varpy (V +
(93)
(s,
simultaneously for any pair (s, a) E S x A.
Proof. When ((s, a) = O, the results hold naturally. We hence only consider (s, a) with ((s, a) > 0. Part 1. Recall that M = P, F) is the estimated MDP. For any state and positive scalar u >> 0, we first construct
auxiliary stato-absorbing MDP M A8 pa. ra))) as follows.
For all states except 8, the MDP structure of Ma is identical to M, iee. for any x # and A,
(p&.)e, = r (x f(z
(94)
State 8 is an absorbing state in M namely, for any a E A,
(pei)) = 1==:: ( a) = u.
(95)
We then define robust MDP M = (8,A, ra") centered at M as following: the uncertainty set Pe.. is defined as f 8 x.a wa where if x # 8,
(Pei)),
(Pea)a = {4 E A(8) D(g. (PS.))) S R
(96)
and
(pa.u)g = {1.}.
(97)
The optimal robust. value function of M is denoted by Ve,u
Part 2. We claim that we choose u' (1 (1-11000 (5)( (s), then Va," V We prove this follows.
Firstly note that the function Vs." is the unique fixed point of the operator Te." (V)(z) max, fr (x, a) + (po.))) (V)).
For x # 8, we note that
T (z)))()) = max(1""" (I, + (pan")) (VTr))
= a) + 70 (V))))
(x).
(98)
which is because yr (x, = f(z, a) and (pe,"" ) = gog for x + 8.
For 8, we have that
Te..u (x) = max(r (8, + 7o (V=r))
a
max(u" + yo (V
a
V) max{(1 () (s) + +V (s))
(s),,,),
(99)
which from (pe.u") }g {1.).
30

---

Published in Transactions on Machine Learning Research (06/2024)
Hence combining with eq. (98) implies that Vig is also a fixed point of T".",, and hence it must be identical to V which proves our claim.
Part Define a set U _ { i = 1, NJ. Clearly, Ue is a x n-n net Vershynin 2018 et al. 2022 of the interval [0.
Note that for any u E Ue, Pa. is independent with p., hence V** is also independent with P Also, since u I 1, |V* S
Then invoking Lemma implies that for any N(s, a) > O, with probability at least 1 - ō, it holds simultaneously for u E Ue that
I(P: P 48 p2 (Vs.)) log 1N2 0
48 log 4N2 8 (s,
(100)
((s,a)
(1
5 4N2
Varp, (V+a) S 2Varp (Va.)) + 3(1 - N
(101)
1. N. Part 4. Since u² = (1 - V- < 1, then there exists no E Uc, such that ani u that
Moreover, we claim
||S"" 110 N(1 - 7)
(102)
To prove eq.
102
first note that
Vvs (s) - V (s) S
max (u- - u0) + (0 (V=aa) appr (VSMo))
IA WVE
uol 7 max (o (Vs,a") o (ppnnn )2 (Vo,uo))
1u" mol + >/|V//" - V5,
(103)
where (a) is because (PSN (Tss.u y {1,}, and (b) is due to the non-expansion of the support function
(Lemma 1, |Panaganti & Kalathil 2022
For x A s, we have that
V - (z) & max |(x, a) - f(x, a) + (a (V3.*) ogg (Vo:9)))
Va."" Vo.u0 1bo-
(104)
Thus by combining eq. (103 and
104), we have that
1 V8.00 11o0 S N
|Va'""
+
Veaa 1oo V/lV
(105)
and hence proof the claim eq. 102 Therefore,
Varp: (V&N10) Varp Varp:(Va.")
Pd (V* - p.y/suo)) (Vs,uo pP - (Va,.' - -Pqys.") (Vs,a' -PgVs..))
(4)
Pa (V8,00 pgVa.") - pgy "ys."--pgaan (Vou" -PV
pa
(Va,u paveu" + +Va." - poveeu") o (Vo,u0 vor²))
2
p. - Vs*'))
1 1-7
31

---

Published in Transactions on Machine Learning Research (06/2024)
2 N( - 7)1
(106)
where (a) is due to the fact [[[] arg min, B((X - =c)3, and the last inequality due to |V 1 S -- V| loo S -
Similarly, swapping Va,.0 and Veu implies
2 N(1 7))
Varp: Varp:(Vew') -arr; (Vo,00) $
(107)
and further
2 Varp:(Veur) Varp; (Vo:00)) S N(1 7)2
(108)
We note that eq. 108) is exactly identical to (159) in Section A.4 of (Li et al. 2022) and hence the remaining proof can be obtained by following the proof in Section A.4 in LLi et al. 2022), and is omitted here.
Lemma 7. With probability least 1 - ô, it holds that for any 8, a,
Pay 3 - PVV
48 log 4SAN
1SAN 48 log (I-2)6
96 49AN
$2V x Jgg (VT
(1 11-7) (1-7))(s.o)) 2
(1-1)6 E1
+ 2e11
(1->)5
(109)
(s,
(1 (1-7)N(s,)))
Proof. We first show the inequality above holds for any (0 _ that independent with Pg.
From the duality form of the oz (V) Tyengar 2005 it holds that
Pgv. V Rs Varpa (Va)
PaV Dig (V) PgV
max o oE[Vitn, Vinae]
p::Vv - Va) + v RS Varpa (Va)
min aE(Vuing Vanaa]
(110)
where Va R and Vs(s) = m))
We denote the optimum of the optimization by a", i.e.,
p:c(v -Va) + v Rog Varp. [Va)
PV Va+) v Rg Varpy (Va-)=
min oe(Vaniu Vanax]
(111)
Then eq. 1110 can be further bounded as
P.V Jigig (V) = PV Va.) / |R. Varpa (Va-)
> PV(V - Va.) P-((V - Va. + Varp. (Va.),
(112)
where the incquality is due to the fact that V(s) (s).
On the other hand, for any a E [Vnin Viax that fixed and independent with Pa. we have that
PgV - P.V = -oyv, P.V. + PC Va) P.(V - V.)
48 log 4SAN (1-7)8
48 log (1-7)6
4SAN Varp. (Va)
< P. - Va) PV Va) + (1 - 7) (s,
(113)
Ns,
32

---

Published in Transactions on Machine Learning Research (06/2024)
which is due to is independent from Po and applying the Bernstein's inequality and (102) of (Shi et al. 2023 Moreover, it implies that
PgV PVV
48 log ASAN (1-710
48 log 1SAN [1-7]6
Varp, (Va+)
PV Vo.) - PV Vo-)+ +
NN,N))
N(8,a)
48 log 4SAN Varp. (Va) (1-7)8
48 log (1-3)8
4SAN Varpy (Va:)
+ (P= Vo) -P2(V- - Va)). (114)
(s)0)
(s,,0)
We now construct an ei-Net (Vershynin 2018 of 0, 1-7 [11, o2, am, 00, - } such that for any a E
with el Nे. Specifically, there exists U
0. there exists a, E l with |a ayl $ 61 Since
0, 1 there exists 3 E U with | a*1 S 61
It is straightforward to see that
V& S |8 a²1 S é1,
(115)
and similarly following (207) of (Shi et al. 2023 implies that
Varp. (V3) v Varp, (Va:) s 52 /2/1-- 1-7
61
(116)
Hence we set a = 3 in eq. 114 take the union bound over S,A and U, and plug in the two incqualities above, we have that
pgv P.V
48 log (I-4)8
48 log (1-1)8
4SAN Varpy (Va))
Pv Va-) PP Va-) +
(1 - (s,,a)
N(s,a)
ASAN 48 log
48 log ASAN
+ 2V
[I- E (1 (1-7) a)
+ 2011
(1-736
(117)
N(s. a)
Involving eq. 112 further implics that
P.V - VV
4SAN 48 log [1- E1
log [1-716
4SAN
48 log 45AN
< p.g - Bjy (V) + 22
+ 2611
(1-9)8
(118)
(1 (s,
N(s.a)
(1- N
and hence
49AN 48 log (1->)5 C
49AN 48
48 log 4SAN (1-7)6
P.V s 2 (1 (1,7) + 2011
(1-2)6
(119)
N(s.a)
(1 N1-7)N(s,0)
Now we consider r Following the -eet Up we constructed in Lemma Hence there exists some u, U2 with lu uil S 1 Note that
V = ya.u for some u E [0, 1].
Bg (VT PoVX-
=0pg(Va PqVs."
= (Vsiu) p.
+ (Ve.)) Jzg. (Va,u)) + Pa paye.u
33

---

Published in Transactions on Machine Learning Research (06/2024)
48 log 1SAN E1
48 log 49AN
48 log 1SAN
[I-
(1-216
(1-2)8
S 21 (1 (s,
+ 2011
(ss,0 a)
(1- N1,
Jbgy (V Jby (V Pove, PaVeN
(120)
which is due to Vaa is independent with Pg. Moreover, note that both apy (V) and PgV are 1-Lipschitz, thus
Jpy (V*.)) Jbg (Veu) - |V Vs,uillo
(121)
p. - PVVe I || Vea Va 1100
(122)
Now from Equation 102 it follows that
B (V%u) Jigg (Vaai)
(123)
N(1 -)
Pava. PVVo.
(124)
N(1 7))
Hence combine with Equation 120 and we have that
Jbg (1 P.V
log 4SAN
(1-7)8 61
49AN 48 log (1-2)8
48 18log (1-3)8
21
(1 - (3,)) 261
(1)
(1 V)
+ Jig (Va.2)) Jgg (VaN))
Pava PaySu
48 log 4SAN
4SAN 48 lolog (1-7)6
4SAN 48 log (1-7)ø
(1-7)6
2 N(1 -)
2
2c1
7) (s,
((, a)
(1 N)
4SAN 48 log (1-7)8
48 log 4SAN (1-2)6
48AN 96 96log (1-7)8
2
2c
(125)
(s,
((s
(1 (1-7)
which completes the proof.
34


Reviews:
[{"review_id": "IzbBRLLFuQ", "reviewer": "Reviewer_hguE", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\n- This paper establishes that minimax optimal sample complexity can be achieved from the perspective of distributionally robust optimization.\n- This work clearly delineates the inherent technical challenges of the direct Hoeffding-style algorithm and addresses them through careful error bounding via utilizing the Bernstein-style uncertainty set.\n- They also provide a detailed comparison between their proposed approach and the existing LCB (value-based) approaches, and this strengthens the need for DRO.\n\n**Weaknesses**\n- The assumption about deterministic reward functions appears quite strong in this setting. For instance, in the proof of Theorem 2, the authors leverage the fact “r(s,a) >= \\hat{r}(s,a)”, however, this does not hold under the random reward function setting, which makes the assumption quite hard to be lifted.\n- DRO has been studied in several recent works on offline RL, e.g., (Uehara & Sun, 2021) and (Panaganti et al., 2023), under various assumptions. Similarly, this paper also takes a DRO approach, under somewhat different assumptions. As a result, to make the comparison fair, it is required to also compare the assumptions used in different works (and discuss this in Table 1 as well).\n- In Theorem 6 of (Rashidinejad et al., 2021), they introduced a tighter bound (linear dependence of \\epsilon) under specific C that lies in [1, 1 + O(lnN / N)]. It would be good to discuss the role of specific C in your algorithm and analyses, and then compare the results with the bound in (Rashidinejad et al., 2021).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper investigates the sample complexity of offline reinforcement learning from the perspective of Distributionally Robust Optimization (DRO). The central idea involves utilizing empirical model estimation (model-based) as the center of the uncertainty set and appropriately determining the uncertainty radius for transition dynamics. The main contributions are mainly two-fold:\n(i) By employing a Hoeffding-style radius, this paper leverages Robust VI (cf. Algorithm 1) with an uncertainty set induced by this radius and establishes a sample complexity of O((1-\\gamma)^{-4} \\epsilon^{-2} S^2 * C).\n(ii) The sample complexity is further enhanced by considering a Bernstein-style uncertainty set, resulting in a sample complexity of O((1-\\gamma)^{-3} \\epsilon^{-2} S * C), which has been proven to be minimax optimal by [Rashidinejad et al., 2021].\nAdditionally, the authors validate their algorithms through experimentation on the Garnet Problem.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- Based on (8), the corresponding sample complexity in (9) shall also depend on K?\n- Is the burn-in cost in [Xie et al., 2021] H^9SC? Should it be 8 in Theorem 4 of [Xie et al., 2021]? (page 9).\n- Appendix B, Lemma 2 is the same as Lemma 1? (If yes, please mark them as the same statement.)\n- Please define the circle cross notation over sets in page 5.\n- What is the norm defined in Lemma 1? (I think it should be L1-norm here) This should be specified in the preliminaries section.\n- In Line 11 in Algorithm 2, there should be an “else”? (Otherwise, the pseudo-code will always execute Line 11 to overwrite Line 9 even the condition of Line 8 is satisfied)\n- Do the results hold under the less stringent $s$-rectangular setting for the uncertainty set? How much will the sample complexity degenerate when using a general s-rectangular uncertainty set as (Wiesemann et al., 2013)?\n- The radius on page 8 should take a min with the Bernstein radius, otherwise the radius is not defined under the (s,a) that satisfies N(s,a) = 0.\n- The penalty term in (10) should have a negative sign?", "broader_impact_concerns": "There is no Broader Impact Statement section in this paper, and I do not find any immediate concern on the ethical implications of the work .", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "AG1z0RbNJZ", "reviewer": "Reviewer_h2UY", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strength**\n\nThe overall presentation and contribution are clear. I believe the major contribution of this paper is it tells readers that DRO-based method can achieve minimax optimal sample complexity bound in offline RL with partial coverage. In addition, the experiment is a plus to this paper.\n\n**Weakness**\n\nThe connection between the DRO method and LCB method is unclear (see the section below).\n\nThe result only matches the existing (though already minimax optimal) method, and both Hoeffding’s and Bernstein’s bonus/uncertain set construction have been widely investigated in the literature. \n\nAlthough the rectangular set in DRO yields better computational complexity, I believe it is more restricted than other uncertain set construction.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper investigates offline RL with distributionally robust optimization (DRO) based methods. In this robust MDP framework, the transition function is assumed to come from an uncertainty set, and the performance of a policy is measured by its worst performance over all possible transition functions in this set. The goal is to find a policy that obtains the optimal robust performance. \n\nTwo sample complexity upper bounds are provided for the discounted tabular MDPs, one with Hoeffding-style uncertainty set and the other with the Bernstein-style uncertainty set. The sharper one with the Bernstein-style uncertainty set matches the minimax lower bound (Rashidinejad et al., 2021) and stands on par with the best results achieved using the LCB approach (Li et al., 2022). The proposed algorithm has a polynomial computational complexity, which is the same as Li et al., 2022 and is better than many other DRO based method that applies more complicated uncertainty set.\n\nExperimental results on Garnet problem and the Frozen-Lake problem are provided to support the theoretical finding.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Some discussions can be added to make this paper stronger.\n\nIn offline RL, it is well known that that there is an equivalence between the value-based method like FQI and the model-based method (using the dataset to construct estimated transition and reward functions and then use the model to do planning like value iteration). The authors remark in the paper that LCB can be viewed as a value-based method where the reward is subtracted by a pessimistic term, while the proposed approach can be viewed as a model-based approach where a transition is first constructed and the planning is conducted (ref eq (10)). Therefore, I was wondering whether a direct equivalence or connection between LCB and the proposed algorithm can be shown.\n\nThis paper only assumes that the transition function comes from an uncertainty set. Will the results also hold if the reward function also comes from an uncertainty set?\n\nThere’s more related work in offline RL with pessimism:\n\nChen, Jinglin, and Nan Jiang. \"Offline reinforcement learning under value and density-ratio realizability: the power of gaps.\" In Uncertainty in Artificial Intelligence, pp. 378-388. PMLR, 2022.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "l6snJOrkQR", "reviewer": "Reviewer_57y6", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The main strength of this work is in considering an alternative approach to (provably efficient, tabular) offline RL (robust optimization rather than pessimistic penalties). Equivalently, it could be seen as a retelling or an actualization of robust RL using recent concepts from the offline RL literature. Although this alternative method does not improve over the more common LCB approach, in the spirit of TMLR, it shows an interesting and (I believe) correct alternative path.\n\nRegarding correctness, I checked carefully the proof Theorem 1 (Hoeffding-style uncertainty set) and I did not find any significant errors, although there are some minor issues (likely just typos). A sketch of the Bernstein-style extension is provided in Section 3.2. and it seems correct on a high level. I found the use of the chi-square divergence very interesting from the technical point of view.\n\nMy main concern is with the \"burn-in\" cost from Theorem 2, which scales with the minimum positive probability of the behavior distribution. Although, as correctly observed by the authors, this does not affect in any way the asymptotic convergence, I still think it defies the partial coverage requirement in a way. It looks like it is possible to construct examples where the coverage of the comparator policy is very good, yet the burn-in cost is arbitrarily large. I think this point has been overlooked in the discussion of the result. Moreover, if I am not mistaken, the LCB algorithm by Li et al. does not have this issue, so this raises some doubts on the equivalence of the LCB and the DRO approaches, doubts that are reinforced by the experimental results (see next section).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes a solution to offline reinforcement learning in discounted tabular MDPs,  based on distributionally robust optimization (DRO), and robust value iteration in particular. The proposed algorithm is conceptually simple: use offline data to build an uncertainty set of plausible transition kernels, use it to define a robust MDP, run robust value iteration, and return the optimal robust policy. \nThis algorithm is shown to achieve similar sample complexity results as LCB-style pessimistic algorithms under a partial coverage assumption. It is also computationally efficient.\nA first version, based on rectangular, Hoeffding-style uncertainty sets measured in total-variation, has $O(S^2 C (1-\\gamma)^{-4}\\epsilon^{-2})$ sample complexity, where S is the number of states and C is the (clipped) single-policy coverage ratio. This is comparable with pessimistic methods based on Hoeffding-style penalties.\nA second version, based on Berstein's inequality and chi-square divergence, has $O(SC(1-\\gamma)^{-3}\\epsilon^{-2})$ sample complexity, matching a minimax lower bound by Rashidinejad et al. (2021) and the best LCB-style algorithms.\nThe proposed algorithm is tested on two tasks (Garnet and Frozen Lake) in conditions of full and partial coverage, showing performance comparable with LCB.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Critical:\n1. The role of the burn-in cost in Theorem 2 should be discussed more, as it seems to defy partial coverage falling back into a uniform-coverage requirement (see the previous section)\n2. In the Frozen-Lake environment with partial coverage, LCB improves much faster in the beginning. This deserves at least a comment. Could it be due to the burn-in cost?\n\nLikely just typos:\n3. Proof of Thm 1: in the row after Equation (20), in the very last inequality, the $2$ factor seems unnecessary, but actually I think it's the previous inequality that is incorrect.\n4. Equation (25), second inequality: this seems off, but likely it's just typos, and the final result seems correct.\n\nNon-critical:\n- The proofs could benefit from more comments. For instance, in the proof of Thm3: some intuition could be given on the two-case study (Eq. 17,18); The second inequality of Eq. (22) is a crucial passage and deserves a comment.\n- Remark 1 is quite vague. What are the advantages of alternative distance functions? What are the ideas to generalize the proposed method to large-scale problems?\n- The second two paragraphs of Section 3 are a needless repetition\n- Remark 3: \"the motivations are different\"...I would rather say that the motivation is the same, but the methods are different. One could even argue that your method is still pessimistic, just with a different implementation of pessimism.\n- Experiments: the \"partial coverage\" setting could be a bit misleading, since full coverage may still be pretty good (every action is played with probability at least $1/(2|A|)$). Of course state coverage heavily depends on the environment, but a comment would be useful here.\n\nTypos etc:\n- \"transits\" page 4\n- last equation of page 18: missing plus sign", "broader_impact_concerns": "Not needed.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers were largely satisfied with this paper, and all their minor concerns were addressed appropriately by the rebuttal. One recurring criticism regarding the contribution has been that the results do not clearly indicate the benefits of the proposed DRO-based approach as compared to the more common LCB-style methods. Despite this limitation, the perspective offered in the paper was deemed interesting, and potentially valuable as a starting point for future research. As all reviewers agreed to publish the paper without further changes, I recommend to go ahead with this decision.
Decision: Accept (poster)