A Unified Principle of Pessimism for Offline Reinforcement Learning under Model Mismatch
Authors: Yue Wang
Zhongchang Sun
Shaofeng Zou
Venue: NeurIPS 2024 poster (2024)
Keywords: reinforcement learning
offline
robust
Primary area: reinforcement_learning

Abstract: In this paper, we address the challenges of offline reinforcement learning (RL) under model mismatch, where the agent aims to optimize its performance through an offline dataset that may not accurately represent the deployment environment. We identify two primary challenges under the setting: inaccurate model estimation due to limited data and performance degradation caused by the model mismatch between the dataset-collecting environment and the target deployment one. To tackle these issues, we propose a unified principle of pessimism using distributionally robust Markov decision processes. We carefully construct a robust MDP with a single uncertainty set to tackle both data sparsity and model mismatch, and demonstrate that the optimal robust policy enjoys a near-optimal sub-optimality gap under the target environment across three widely used uncertainty models: total variation, $\chi^2$ divergence, and KL divergence. Our results improve upon or match the state-of-the-art performance under the total variation and KL divergence models, and provide the first result for the $\chi^2$ divergence model.

A Unified Principle of Pessimism for Offline Reinforcement Learning under Model Mismatch
Yue Wang
Zhongehang Sun
Department of Electrical and Computer Engineering University Central Florida Orlando, FL, 32816 yue wwngwucf.uc...o.o edu
Department of Electrical Engineering University at Buffalo Buffalo, NY, 14260
zhongcha@buffalo..ee
Shaofeng Zou
School of Electrical, Computer and Energy Engineering Arizona State University
Tempe, AZ 85287 zou@asu. edu
Abstract
In this paper, we address the challenges of offline reinforcement learning (RL. under model mismatch, where the agent aims to optimize its performance through an offline dataset that may not accurately represent the deployment environment. We identify two primary challenges under the setting: inaccurate model estimation due to limited data and performance degradation caused by the model mismatch between the dataset-collecting environment and the target deployment one. To tackle these issues, we propose a unified principle of pessimism using distribu- tionally robust Markov decision processes. We carefully construct robust MDP with a single uncertainty set to tackle both data sparsity and model mismatch, and demonstrate that the optimal robust policy enjoys near-optimal sub-optimality gap under the target environment across three widely used uncertainty models: total variation, x divergence, and KL divergence. Our results improve upon match the state-of-the-ar performance under the total variation and KL divergence models, and provide the first result for the x² divergence model.
Introduction
Reinforcement learning (RL) 40 learns policy to maximize cumulative rewards through online interactions with the environment. However, in real-world applications such as autonomous vehicles [16] and health care [61]. the trial-and-error nature of interacting with the environment costly and dangerous, rendering online learning impractical. To circumvent these challenges, the concept of offline RL has emerged [17 [8), seeking learn optimal policy from a pre-collected dataset, eliminating the need for real-time interaction with the environment.
be both
Despite its potential, offline RL faces two significant challenges that impact its performance. The first challenge stems from the nature of the offline dataset itself. Offline RL demonstrates impressive performance only when the dataset is of high quality, exemplified by 941,9 [8]. However, in most RL scenarios, the data collection process can be expensive, constrained, and subject to specific behavior policies. This often results in dataset with insufficient samples and limited coverage. The limited coverage of state-action pairs in the dataset presents substantial hurdle, making challenging fully leam the environment model and the model learned may be inaccurate, leading to poorly performing policy. and hindering the discovery the optimal policy, particularly when
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

the behavior policy is sub-optimal. Existing solutions involve introducing pessimism during policy learning, by penalizing the reward function for state-action pairs that are not adequately covered by the dataset, known as the lower confidence bound (LCB) approach 15 33 19] demonstrating potential both numerically and theoretically in solving offline RI..
The second critical challenge in offline RL pertains to its vulnerability to model mismatch. As the offline dataset is collected advance, only encapsulates the environment's information at the time of data collection. In practical applications, environments often undergo variations due to e.g., unexpected perturbations, heterogeneity, or san-ssttionartt.. This inherent variabilityy introduces a model mismatch between the target environment and the one where the dataset is collected, leading to significant performance degradation when deploying the learned policy in the real environment. Robust RL or distributionally robust optimization (DRO) framework is then proposed to address this challenge 13 28,, which incorporates the pessimism principle to effectively tackle model uncertainty. By constructing an uncertainty set containing 'plausible" environments, robust RL optimizes the worst-case performance among them, providing performance guarantee for the real environment.
To summarize, there are two sources of uncertainty in offline RL: Uncertainty from limited data: This stems from the inherent uncertainty introduced by limited offline datasets and lack of exploration; Uncertainty from model-mismatte and deployment environments, as well as between cata-collection distribution and the distribution induced by the optimal policy. Each challenge can be addressed through its corresponding principle of pessimism, as in previous works: limited data coverage can be mitigated with reward estimation penalties (LCB), while model mismatch can be tackled with distribution estimation penalties (DRO). However, existing approaches often address these uncertainties separately, e.g., [36] 24), leading to methodological redundancy or complexity (more discussions and comparisons can be found in Section5)). 5). In this paper, we propose a unified framework that integrates both principles of pessimism into single robust Markovian decision process (MDP) model for offline RL, offering a clear and streamlined conceptual formulation and providing improved or matched theoretical guarantees compared to existing methods. Our major contributions can be summarized as follows.
This arises from distribution shifts between data-collection
unified distributionally robust formulation for offline RL under model mismatch. As dis- cussed before, offline RL faces challenges including limited dataset coverage and model mismatch. Specifically, we first tackle the challenge of model mismatch using the approach of distributionally robust MDP, which optimizes the worst-case performance over an uncertainty set specified by e.g.. total variation, x2 or Kullback-Leibler divergence. We then show that the uncertainty from data sparsity can be transformed into data-dependent penalization term that is added to the radius of the constructed uncertainty set. Our formulation hence unifies the two principles of pessimism to a single DRO problem that tackles both sources of uncertainty without additional structures and enjoys an easier implementation compared to existing works.
Augmented design of radius to achieve tight theoretical guarantees. Designing the uncertainty set for the model mismatch typically straightforward. often relying on domain knowledge [39]. However, incorporating an additional penalty term to address data sparsity presents significant challenges. Balancing the conservativeness for less-visited state-action pairs estimation and the overall performance of learned policies requires careful consideration. In our work, we conduct meticulous analysis understand how the penalty radius impacts the performance of the learned policy. We then design penalty radii for three widely studied uncertainty set models: total variation, x" divergence, and KL divergence, Our analysis provides insights into the performance of learned policies under these penalty radii, showcasing the versatility of our framework across both metric- based and non-metric- guarantees. Specifically, variation model [5), match the state-of-the-an performance under the KL divergence model [36]. and present the first result under the x² divergence model.
models. Moreover, our designs enable us to derive tight theoretical improve upon existing results for robust offline RL under the total
2

---

2 Preliminaries
2.1 Markov Decision Process (MDP)
An MDP is specified by tuple AS,A, 2.).)) where 8 and A are the state and action spaces, respectively, P = (P: E A(8), the reward function, and y E [0, 1) is the discount factor. Let S be the number of states and A be the number of actions. For any transition kernel P. P = (P where pa..' denotes the probability of transiting from state s to state s' after taking action a. The reward of the transition when taking action at state is denoted by rs,
8,a E A the transition kernel, r 8
[0, 1] denotes
For stationary policy ı that maps from state s E 8 distribution over action a A, specifies the probability of the agent taking actions at each state. The value function of a policy π is defined as
VP (8) (8) 2 Ep Σ 2'r(s 4s) 8,
where Ep denotes the expectation with respect to the distribution induced by the transition kernel P. Let o be the distribution of the initial state s. the value function under the distribution p is denoted by Vir( (p) = [Vp (s)]- Let (s) and ds a) denote the state occupancy measure and state-action occupancy measure of policy when the initial state s follows distribution p: (s) = (1 7) Ei=o 7 P(s: = s s/30 p, n,, P), dø a) = dz (a)ss.
2.2 Distributionally Robust MDP
robust MDP defined as A8, r, 7), where the transition kernel not fixed but lies in some uncertainty set P. In this work we consider the (s, -reettnuullll uncertainty set:
Po. P = (1 E E 8,0
D(g. P?) - R),
(2)
where x s.a means the uncertainty sets for every state-action pair are independently defined, P some nominal transition kernel for (s, a)-pair,, D is some function that measures the difference between two distributions, e.g., total variation and KL divergence, and /t is the radius of the uncertainty set. The robust MDP aims to find the policy that optimizes the worst-case performance among all possible transition kernels from P. Such worst-case performance can be characterized by the robust value function V15 (s):
V (s) A min V (s).
(3)
CEP
which is shown to be the unique solution to the robust Bellman equation 13]
Vi = Σ (als) (r(s,a) yor; (VF))
(4)
with or; minge: V being the support function of a vector V on the uncertainty set Pgg
Similar to the standard MDP setting, V (p) can also be defined w.r.t. the initial state distribution p. The goal here is then to find the optimal robust policy arg max, V (p).
3 Problem Formulation
In offline RL, the agent does not receive new samples by interacting with the environment. Instead, it given a previously collected dataset D which consists of N tuples {(s a, s r.) : -... .N). The dataset is generated according to some distribution μt, i..., (s,, a,) μ4, and 8 ~ Pa: follows the nominal transition kernel P, and r; = r(8;, a;) is a deterministic reward function. As discussed, due the potential model mismatch between the environment that generates the offline dataset and the one in which the learned policy is going to be deployed, we design an uncertainty set that
(8) denotes the probability simplex detined on 8.
3

---

captures such model mismatch as in 2 aiming to learn a policy that performs well under the true deployment environment through the robust RL framework:
arg max V (p), where P
Pa Po {qg A(8) D(g. Pt) R).
(5)
where R. represents the similarities of the two environments. D and are generally designed by domain experts, so we do not focus on their design and consider them as pre-settled in this work.
key challenge here is that the nominal transition kernel Po is unknown, but only an offline dataset generated from Po is given. Due to the limited exploration and distributional shift, the dataset D may not cover all possible states transitions that the agent might encounter in the environment.
To guarantce that a provable efficient algorithm can be designed based on the dataset D, we adopt an assumption the distributional mismatch between the dataset distribution and the occupancy measure induced by a comparator policy x² A comparator policy refers to policy having satisfying worst-case performance and is set to be the optimal robust policy in many cases, but approach can be applied to an arbitrary policy that may not be optimal.
Assumption (Robust single-policy clipped concentrability (361). The data distribution μ satisfies
min (s, }} +00. ())
C
(6)
(s,a, AXx
In Assumption [ we only require that the dataset covers the state-action pairs that are visited by the comparator policy, known as partial coverage. When there is no model mismatch, Assumption [ reduces to the single-policy clipped concentrability assumption in [19] for non-robust offline RL.
We hence formulate the offline RL problem with model mismatch as the following concrete problem:
Solve the robust RL problem
(5) using only a fixed offline dataset 'D satisfying Assumption
4 Framework Design and Main Results
To simultaneously address the two sources of uncertainty (1) uncertainty arising from the model mis- match between the data-collected environment and the deployment environment; and (2) uncertainty in the nominal (data-collection) model estimation attributed to an insufficient amount of data and limited coverage of the offline dataset, we develop unified principle of pessimism, and theoretically characterize the finite sample complexity of the proposed algorithms. Our algorithms are easier and more efficient to implement than existing approaches, and yield improved matching results.
Denote (ss, a) = E 1 (s,,a))=(sp)) as the number of samples that transit from (s, a) in D, where 1 the indicator function. The empirical transition kernel is then obtained as
o0 N(3.0)
pa S,8'
if N a) > if N a) = 0,
and we also define the empirical reward function
{
E Dosaa)) N(s.o)
if ( (s, a) > 0 if ((, = 0.
F(s, a) -10
(8)
The MDP M = A8
P) with the empirical transition kernel P and empirical reward function 2 is referred to as the empirical MDP, representing our estimation of the nominal model from the dataset. straightforward approach to construct an uncertainty set + by replacing the nominal kernel P in
5 by
ju = (q E A(8) D(g. P.) R)
and solve the corresponding robust RL problem. Although it tackles the model mismatch uncertainty through the uncertainty set, it generally results sub-optimal performance due to the lack of consideration of the estimation emror within the empirical model.

---

To tackle this estimation error, previous works introduce some additional structures other than the above DRO framework (9). including penalty term in reward [66 or an additional uncertainty set
and making it bi-level DRO [5 (more discussions and comparisons can be found in Section ( In this work, we construct a single, unified uncertainty set of environments, showing that such an estimation error can be incorporated into the distribution uncertainty set and developing unified principle of pessimism to address both uncertainties. Specifically, for any E 8 and a E A, we set
P {q E A(S) D(g, R + K
(10)
where xi is a function (will be specified later) inversely proportional to ( a) that measures the degree of confidence when estimating the empirical transition kernel; and R accounts for the model mismatch. Intuitively, for the less-observed state-action pairs, Kg becomes larger and we are less confident and more pessimistic when estimating the transition kernel Pg. and vice versa.
We claim and show later that the additional uncertainty or pessimism by enlarging the uncertainty set effectively tackles the uncertainty from the limited dataset, and the whole uncertainty set results in conservative estimation of the worst-case performance. We then optimize the worst-case performance under this uncertainty set P, which can be efficiently solved through the standard robust dynamic programming approach [28 [3]. Our algorithm is presented Algorithm [ For the convenience of analysis, we modify the vanilla robust value iteration algorithm [13 by setting the output policy to select actions that occur in the dataset when there is a tie. Such an output policy always exists (shown in Lemma 11 in the Appendix) and enables us to derive tighter analysis of the sub-optimality gap. It is also worth noting that for all the uncertainty set models we consider, our Algorithm [ can be efficiently applied with a polynomial computational complexity and a linear convergence rate 13
Algorithm 1 Robust Value Iteration for Offline RL with Model Mismatch
Input: D, V == 0
Estimate the empirical reward f and empirical uncertainty set P according to repeat
8 and I0)
V(.) + a (f(5 + yog.
until convergence
for E do
*(s) E { (arg max f(s, 10 (V) naa N(s, 0}
end for Output: म
In the following sections, we consider three widely used uncertainty set models: total variation, x2 divergence, and KL divergence models. We show that, for all three models, the uncertainty from the dataset can be incorporated into the uncertainty set as an additional term in the radius, and with a carefully designed uncertainty set, the optimal robust policy f obtained has a near-optimal performance under the target uncertainty set P, i.e., our approach effectively and efficiently solves the offline RI. problems under model mismatch.
4.1 Total Variation (TV)
We first consider the case of TV defined uncertainty se Specifically, the uncertainty set is con- structed using D(g.p) p) Y وig 1|l in eq. 110.. Note that when the radius is greater than 2, the defined uncertainty set reduces to the whole probability simplex A(8). Our first attempt is to set ny large enough such that the true uncertainty set P falls into the constructed one P. such that the robust value function of 'P lower bounds the true robust value function Vi3, as conservative estimation. We note that long the true nominal transition kernel P and the empirical transition kernel P are close: |IP: - S Kg holds with high probability, the triangle inequality implies P S P with high probability, Therefore, the optimal robust policy गे provides a performance guarantee for the original problem (5) Following this approach, we can show the following results.
2 *Our approach described can also be applied to uncertainty sets defined by other metrics, e.g., Wasserstein distance and Hellinger distance.
5

---

Theorem 1. Consider TV defined uncertainty set. For each state-action pair (s,a), set K
1lg & Then with probability at least 28, the output policy कt of algorithm / satisfies that
(N(x.))
V8 (p) - V3) =ō (1 (1-7(NN
S2C=F
(11)
where Ô notation absorbs universal constants and log terms.
Remark 1. To achieve an sub-optimality gap, a dataset of size = -1-))0((11))) (1-7)* --- -2 is
required. This result matches the previous one in 15V.
The construction above is based on distribution, to ensure the resulting uncertainty set P is larger than the target one P. However, such a distribution-bart construction can result in an overly large uncertainty set and overly pessimistic policy, as observed [47 [9]. To improve, is that we can design a smaller uncertainty set such that the resulting robust value function V approximately lower bounds the true robust value function, without using the distribution-basee framework. We hence further design novel uncertainty set that turns intuition of such a design will be discussed in the next section).
observation
be less conservative (the
log SA [ssaa)
Theorem 2. For any (s, a), let Ki at least 46, it holds that
For the output policy स of algorithm 1 with probability
V (0) - (p)) (1
C S Pmia
(12)
W((1-)²
Here, pmin minss (u(s, a) u(s, a) 0} denotes the smallest non-zero entry of the distribution that generates the datasel.
Remark Combining the two results, we showed that our approach can obtain an e-optimal robust policy when the dataset is of size O C=
21--)322 min 8 1-7¹ punia 1) for the TV defined model. This result better than the previous result in (5V. illustrating our approach is more efficient. Moreover our framework is much simpler than the one in (5) and can be effectively solved in polynomial time
(see detailed discussion in Section
4.2 x
Divergence
We then study the uncertainty models with the x² divergence: D(p. =. (s) (1
p(a) 2
a(*) Note
that x2 divergence is not metric, implying the failure of the triangle inequality and the distribution- based design as in the previous section. While it is possible to design such that D(Pa Po. S xg
31 it does not imply Pe C TP and no lower bound guarantee can be obtained.
To address this issue, we similarly adapt the value funetion-based construction, by taking a closer look at the error decomposition. The main idea of our distribution- based construction for the TV defined model is construct an uncertainty set that is large enough include the transition kernel with high probability. Then the sub-optimality gap can be decomposed as
V
V
(13)
4.50
and A2 < 0 from Pa C .pg. which however fails under non-metric models. On the other hand, if we further decompose A2 as
V
V
(14)
where P is the empirical uncertainty set We note that Agz is the concentration error due to the limited dataset, which is independent of the term xi (ignoring the dependence of स on for discussion

---

connivance); A21 will be negative term since C P., thus we should set the term x such that the negative bound on A21 cancels out with the concentration bound on 422, leading to non-zero yet tight overall bound on 42. Instead of ensuring the uncertainty set inclusion, we directly ensure the bound on the value function difference 4g small, Clearly, the clue function-based design can be applied to both non-metric and metric models, and is less conservative than the distribution-basee the metric models, since closeness distribution stronger than the closeness in value functions [47]. This observation results in our second design for the total variation model in Theorem 2 showing an improvement sample complexity.
for
Based on this intuition, we present our radius design and results.
Theorem 3. Consider x² divergence-defined uncertainty set. For any (s,a), let k² = = (
I+R
N(s.a)
When N 2 0 Hani ) with probability least 1 46, the output policy it of algorithm satisfies
CT'S
V (p) (p) =
(V
(15)
Remark 3. To achieve 6-optimal robust policy under the x² model, approach requires the total number of samples
C
S
N= N
(1 (1-7)42
C
e-dependent
Our sample complexity has two parts: the e-dependent part which dominates as the accuracy decreases, and fixed amount burn-in cost, whose existence is because we cannot expect learn near-optimal policy when the dataset is too limited. When the desired accuracy decreases, the first term dominates the overall complexity, resulting the asymptotic result presented the theorem.
Our approach and result stand for the first concrete study for offline robust RL with x² divergence- defined uncertainty sets. is also worth noting that our sample complexity asymptotically matches the sample complexity of the model- based robust RL with generative model [38]. These observations hence demonstrate the optimality our results and the effectiveness of our approach.
4.3 KL Divergence
In this section, we consider the KL divergence defined uncertainty set, i.e., D(p.9) P(s) log p(a) q(a)' Similarly, KI. divergence not metric, we hence adapt our design discussed above for x² models here. The following theorem presents our design of the uncertainty set and sample complexity results.
Theorem 4. Consider KL divergence defined uncertainty set. For any (s,u), a), let xy
20445 (1-7)6
8log's then with probability at least 48, the output policy ñ Musiu min'
Ci N(s.a)P if 2
of algorithm 7 satissies
Ca'S
(g (0) (g) <ō
(16)
(1-7)aNP
Here, Prain and Pmii represents the minimal non-zero entry of the nominal transition kernel P and empirical nominal kernel P.
Remark 4. Similarly, for the KL divergence model, our approach requires total number of CF' P + PminnPait samples to find an c-optimal policy. The sample complexity also
contains two parts, an asymptotically dominated term and a fixed burn-in cost. Our result matches the one of (36] and is better than the one of (5].
To summarize, our unified framework can be adapted to different uncertainty models and solve offline robust RL problems, offering improved or matched sample complexity results and more efficient
7

---

implementation. More discussion can be found in Section 5 We also provide some numerical experiments to verify the effectiveness and efficiency of our algorithm. which can be found in Appendix A Under all three uncertainty set models, our algorithm enjoys smaller or similar sample complexity compared to LCB approaches, and always outperform the non-robust dynamic programming approach.
5 Related Works
5.1 Comparison with prior art
In this section, we compare our works with the most related existing works [36] 5), where offline RL with model mismatch is studied. Compared to them, our methods enjoy three major advantages: (I). A more unified and straightforward framework of single pessimism principle; (2). Improved or matched sample complexity; And (3). Enhanced computational complexity.
Unified framework for double pessimism principles. In 36), the two principles of pessimism are separately employed, where reward penalty term b is used to penalize less visited state-action pairs in addition the uncertainty set that accounts for the model mismatch, and the update rule is
V(s) max (r(s,a) + go (V) b(s,a)}-
(17)
Our approach, on the other hand, enjoys a straightforward and simple formulation. Specifically, we incorporate the two principles of pessimism into single uncertainty set, developing our unified principle. Moreover, it is noted that design of the penalty term b is complicated, whereas our addition term A has simple and clear form. It is worth noting that although the LCB approach and ours share a similar updating rule, there is a fundamental difference in the algorithm design motivation and analysis. In the LCB approach, the penalty term is designed such that the resulting estimation V is less than the true robust value function Vy. to ensure the conservativeness of LCB approaches; Whereas our resulting estimation V is necessarily less than Vp. since we directly tackle the distribution uncertainty but through value function estimations. This hence requires novel technique innovations in our analysis.
In another closely related work 15), double pessimism principle is adopted to address the two sources of uncertainty, under TV and KL divergence models. Specifically, a TV distance-based uncertainty set JP is first constructed to tackle the model estimation uncertainty from the dataset; Then centered at each transition kernel P E ÿ a second layer of uncertainty set (PP) to reflect the distributional robustness to model mismatch. They then take the optimal policy of
V pess?
inf inf V PEP PE((P)
(18)
as the output policy. Although their approach indicates that the data estimation uncertainty can also be captured by a distributional uncertainty set, they still employ the two principles separately, although both in the form of DRO formulations. Instead of designing two uncertainty sets as in [5), we unify the two types of pessimism and use single uncertainty set with composed design of the radius to address both the model estimation uncertainty and the model mismatch.
Improved Matched Sample Complexity. In terms of sample complexity, the comparison included in [ Compared to (36), our theoretical result matches theirs under the KL divergence model, and we moreover develop results for the other two uncertainty set models that are considered therein. The numerical experiment results can be found in Appendix A which further verify our discussion. Compared with (5), our results achieve better sample complexity both KL and TV models. In the TV model, our sample complexity outperforms (5) in terms of dependence on S and (1 7); For the KL model, our complexity is linearly dependent on S, while (5] has quadratic dependence. Furthermore, as noted in [3). their result's 's exponential term can be replaced by utilizing both Pumin and Amin, while our (asymptotic) complexity result depends solely on P Pmii-
Enhanced Computational Complexity. Our algorithms are also better in terms of computational complexity or practical implementations than both baselines.
The two-layer optimization problem in ( is an extension of the model studied in to the robust
setting, both involving ron-rectan uncertainty sets that are NP-hard to solve 50 This creates

---

TV DISTANCE
X DIVERGENCE
KL DIVERGENCE
X
Ô C exp((2
(1-g)ee
X
(1-7)'6²
OUR WORK
IIIIIL
(1-9)
Table I:
Comparison with related works on offline RL under model mismatch. In [5], Crob is the and robust partial coverage coefficient [S], which is similar to C*", and the exp((1 - -2) ")= term can be eliminated with an additional cost on P Pmii and Mmin'
uncertainty regarding the solvability of their models. Specifically, due the unsolvability of the non-robust model in [42]. an adversarial training-basee algorithm is designed in [34] with only an experimental convergence guarantee, highlighting the implementation challenges of [5]. In contrast, our algorithm can be implemented with polynomial complexity. Specifically, the total computational complexity of our algorithm in the TV, CS and KL models O(S log (5,0 log S), and Ö(S2A) A).
Compared to 36.. our algorithms also offer better computational complexity. Specifically, the penalty term in 36 requires a complicated computation involving minimum operator, resulting in additional max-min structure in their algorithm update. The comparison/max- operator in the LCB algorithm is executed SA times per step, significantly increasing computational complexity. In contrast, our algorithms have a simple structure and do not require additional operators, making them more computationally efficient. We also use numerical experiment further illustrate our enhanced computational efficiency, in Appendix A
5.2 Other related works
We then discuss some of the other related works.
Offiine RL without model mismatch. Offline RL focuses on learning an optimal policy from pre-collected dataset, and the target deployment environment is identical to the one where the dataset collected. Many previous works make the global coverage assumption, i.e., the behavior policy
can cover all state-action pairs, e.g., [35 7 27 assumption is too restrictive and is often violated in practice since requires the history data to cover proposed, which assumes that the density ratio between the occupancy measure induced by a single target policy and the behavior policy is finite for all state-action pairs, and the goal is to learn a policy that is worse than the target policy. The partial coverage assumption only requires that the history data visit the state-action pairs that the target policy will visit. Under the partial coverage assumption, optimal policy can be learned for offline RL incorporated with the pessimism principle facing the uncertainty.
58
59
14 45 20
21
64 41
9 52 18 2 [0]. This
all the state-action pairs 2 I.. Recently, relaxed partial coverage setting
63 47]. However in setting, also consider the potential model mismatch between the two environments, which possibly due to e.g., non-stationarity. heterogeneity and sim-to-real gap, and formulate the problem as offline RL under model mismatch.
e.g.. [15] 42
[5 53 33
62
60
37
19
Robust RL. Robust RL 13 54] aims to tackle the model mismatch in RL, by optimizing the worst-case performance over the uncertainty set. Existing works mainly focus the online setting 38). Studies for robust RL. with an developed in recent works including 26 57]. These works either focus on the linear MDPs, or adapt strong assumptions including global coverage or absorbing states. More importantly, all these works employ the two pessimism principles separately through the LCB penalty and DRO uncertainty set. Compared to them, focus general MDPs and develop our unified framework.
48
49 46
g 25 23 or with a generative model (57 55
offline dataset, besides the mentioned above 36 5
24 44
65]
30
(5)]
6 Conclusion and Discussions
In this paper, we investigated the offline RL problem under model mismatch under the most general partial coverage setting, where two sources uncertainty are presented: inaceurate estimation of transition dynamics due to limited dataset coverage, and model mismatch between training and testing

---

environments. We developed unified DRO-based framework containing a single uncertainty set with composed radius two parts tackle the sources of uncertainty discussed above. Our approach can be implemented in much easier and more straightforward way than existing approaches and can be applied to both metric-based and non-metric-hased uncertainty models. Specifically, we investigated three types of uncertainty sets defined by total variation, x² divergence, and KI. divergence. Our methodology can be easily extended to handle other uncertainty set models. Among them, obtain near-optimal sample complexity results that improve or match the existing results under the total variation and KL divergence models and provide the first algorithm and finite sample complexity analysis for the uncertainty set defined by the x² divergence.
in our future interest to extend our unified framework to address large-scale problems. This includes robust MDPs with latent structures, such as linear MDPs, as opposed to previous work that uses the ICB + DRO framework, for example (24 and more general MDPs with function approximation techniques.
Limitations.
7
Acknowledgements
Yue Wang is supported by DARPA under Agreement No. HR00111-24-9-022 The work of Zhongchang Sun and Shaofeng Zou is supported by the National Science Foundation under Grants CCF-2438429 and ECCS-2438392 (CAREER).
References
[1] A. Agarwal, S. Kakade, and I.. F. Yang. Model-based reinforcement learning with a generative model is minimax optimal. In Conference Learning Theory, pages 67-83. PMLR, 2020.
[2] A. Antos, R. Munos, and Szepesvari. Fitted Q-iteration continuous action-space mdps. In Neural Information Processing Systems, 2007.
[3] M. A. Arcones. A bemsstinn-tye inequality for u-statistics and u-processes. Statistics & probability letters, 239-)2239-247, 1995.
[4] K. P. Badrinath and D. Kalathil. Robust reinforcement learning using least squares policy iteration with provable performance guarantees. In Proc. International Conference on Machine Learning (ICML), pages 51 511-520. PMLR, 2021.
[5] Blanchet, M. Lu, T. Zhang, and Zhong. Double pessimism is provably efficient for distributionally robust offline reinforcement learning: Generic algorithm and robust partial coverage. arXiv preprint arXiv:2305. 09659, 2023.
[6] G. Brockman, V. Cheung, L. Pettersson, Schneider, J. Schulman, Tang, and W. Zaremba. OpenAl Gym. arXiv preprint 1606v: 000.0/5400 2016.
[7] Chen and N. Jiang. Information-thhorret considerations in batch reinforcement learning. In International Conference Machine Learning, pages 1042-1051. PMLR, 2019.
[8] Dong, J. Li, B. Wang, and J. Zhang. Online policy optimization for robust mdp. arXiv preprint arXiv:2209.1385 2022.
[9] Y. Duan, Z. Jia, and M. Wang. Minimax-optimal off-policy evaluation with linear function approximation. Proc. International Conference on Machine Learning (ICML), pages 2701- 2709. PMLR, 2020.
[10] A. M. Farahmand, R. Munos, and Szepesvári. Error propagation for approximate policy and value iteration. In Advances in Neural Information Processing Systems, 2010.
[11] Fu, A. Kumar, O. Nachum, G. Tucker, and S. Levine. D4RL: Datasets for deep data-driven reinforcement learning. arXiv preprint arXiv:2004.072/99 2020.
[12] C. Gulcehre, Z. Wang, A. Novikov, T. L. Paine, S. G. Colmenarejo, K. Zolna, R. Agarwal, J. Merel, Mankowitz, C. Paduraru, et al. RL unplugged: Benchmarks for offline reinforcement learning, arXiv preprint arXiv:2006.1 2388::20006..888. 2020.
10

---

[13] G. N. Iyengar. Robust dynamic programming, Mathematics of Operations Research, 30(2):257- 280, 2005.
[14] N. Jiang. On value functions and the agent-environment boundary. arXiv preprint arXiv: 1eXiv:1955.13344 2019.
[15] Y. Jin, Z. Yang, and Z. Wang. Is pessimism provably efficient for offline RL? In International Conference on Machine Learning, pages 5084-5096, 2021.
[16] B. Kiran, Sobh, V. Talpaert, Mannion, A. A. Al Sallab, S. Yogamani, and P. Pérez. Deep reinforcement learning for autonomous driving: A survey. IEEE Transactions on Intelligent Transportation Systems, 23(6):4909-499) 2021.
[17] Lange. T. Gabel, and M. Riedmiller. Batch reinforcement learning. In Reinforcement learning. pages 45-73. Springer, 2012.
[18] S. Levine, A. Kumar, G. Tucker, and J. Fu. Offlin reinforcement learning: Tutorial, review, and perspectives on open problems. arXiv preprint arXiv:2005.01643 2020.
[19] G. Li, Shi, Y. Chen, Y. Chi, and Y. Wei. Settling the sample complexity of model-based offline reinforcement learning. in preparation, 2022.
[20] P. Liao, Z. Qi, and S. Murphy. Batch policy learning in average reward Markov decision processes, arXiv preprint arXiv:2007.11771 2020.
[21] B. Liu, Q. Cai, Z. Yang, and Wang. Neural trust region/proximal policy optimization attains globally optimal policy. In Proc. Advances in Neural Information Processing Systems (NeurIPS), 2019.
[22] Z. Liu, Q. Bai, J. Blanchet, Dong, W. Xu, Z. Zhou, and Z. Zhou. Distributionally robust Q-learning. In International Conference on Machine Learning, pages 13623-13643. PMLR, 2022.
[23] Z. Liu and P. Xu. Distributionally robust off-dynamics reinforcement learningg Provable efficiency with linear function approximation. arXiv preprint arXiv:2402. 153399 2024.
[24] Z. Liu and P. Xu. Minimax optimal and computationally efficient algorithms for distributionally robust offline reinforcement learning. arXiv preprint arXiv:2403.09621, 2024.
[25] M. Lu, H. Zhong, Zhang, and Blanchet. Distributionally robust reinforcement learning with interactive data collection: Fundamental hardness and near-optimal algorithm. arXiv preprint arXiv:2404.03577 03578, 2024.
[26] X. Ma, Liang. J. Blanchet, M. Liu, Xia, J. Zhang, Q. Zhao, and 7. Zhou. Distributionally robust offline reinforcement learning with linear function approximation. arXiv preprint arXiv:2209.0m 066200, 2022.
[27] R. Munos. Error bounds for approximate value iteration. In Proceedings of the National Conference on Artificial Intelligence, volume 20, page 1006. Menlo Park, CA; Cambridge, MA; London; AAAI Press; MIT Press; 1999, 2005.
[28] A. Nilim and L. El Ghaoui. Robustness in Markov decision problems with uncertain transition matrices. In Proc. Advances in Neural Information Processing Systems (NIPS), pages 839-846, 2004.
[29] K. Panaganti and D. Kalathil. Sample complexity of robust reinforcement learning with generative model. In International Conference Artificial Intelligence and Statistics, pages 9582-9602. PMLR, 2022.
[30] K. Panaganti, Z. Xu, D. Kalathil, and M. Ghavamzadeh. Robust reinforcement learning using offline data. arXiv preprint 2208::2208.01299 2022.
[31] K. Panaganti, Z. Xu, D. Kalathil, and M. Ghavamzadeh. Bridging distributionally robust learning and offline rl: An approach to mitigate distribution shift and partial data coverage. arXiv preprint 4xXiv:2310.18444 2023.

---

[32] Y. Pitcan. A note on concentration inequalities for u-statistics. arXiv preprint arXiv: 2017.
[33] Rashidinejad. B. Zhu, Ma, Jiao, and S. Russell. Bridging offline reinforeement learning and imitation learning: A tale of pessimism. Advances in Neural Information Processing Systems, 14:11772-1, 2021.
[34] M. Rigter, B. Lacerda, and N. Hawes. Rambo-rl: Robust adversarial model-based offline reinforcement learning, arXiv preprint arXiv:2204. 2022.
[35] B. Scherrer. Approximate policy iteration schemes: A comparison. In Proc. International Conference on Machine Learning (ICML), pages 1314-1322, 2014.
[36] L. Shi and Y. Chi. Distributionally robust model- based offline reinforcement learning with near-optimal sample complexity. arXiv preprint arXiv:2208.05767, 2022.
[37] L. Shi, G. Li, Y. Wei, Y. Chen, and Y. Chi. Pessimistic Q-learning for offline reinforcement learning: Towards optimal sample complexity. International Conference on Machine Learning, pages 19967-20025, 2022.
(38] L. Shi, G. Li, Y. Wei, Y. Chen, M. Geist, and Y. Chi. The curious price of distributional robustness in reinforcement learning with a generative model. arXiv preprint arXiv:2305. 166899,,,.168,, 2023.
[39] Siddique. L. Hau, S. Atallah, and M. Petrik. Robust pest management using reinforcement learning. The Milti-disciplinary Conference on Reinforcement Learning and Decision Making, 2019.
[40] R. Sutton and A. G. Barto. Reinforcement learning: An introduction. MIT press, 2018.
[41] M. Uehara, J. Huang, and N. Jiang. Minimax weight and Q-function learning for off off-policy evaluation. In Proc. International Conference on Machine Learning (ICML), pages 9659-9668 PMLR, 2020.
[42] M. Uehara and W. Sun. Pessimistic model-based offline reinforcement learning under partial coverage. arXiv preprint arXiv:2107.06226 2021.
[43] R. Vershynin. High-dimenssionll probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018
[44] H. Wang, L. Shi, and Y. Chi. Sample complexity of offline distributionally robust linear markov decision processes. arXiv preprint 20Xv:24433.12940 2024.
[45] L. Wang, Q Cai, Z. Yang, and Z. Wang. Neural policy gradient methods: Global optimality and rates of convergence. In International Conference on Learning Representations, 2019.
[46] Q. Wang, C. P. Ho, and M. Petrik. Policy gradient in robust mdps with global convergence guarantee, 2023.
[47] Y. Wang, J. Xiong, and S. Zou. Achieving the minimax optimal sample complexity of offline reinforcement learning: A dro-based approach, 2023.
[48] Y. Wang and S. Zou. Online robust reinforcement learning with model uncertainty. In Proc. Advances in Neural Information Processing Systems (NeurIPS), volume 34, pages 7193-7206. 2021.
[49] Y. Wang and S. Zou. Policy gradient method for robust reinforcement learning. In Proc. International Conference on Machine Learning (ICML), volume 162, pages 23524.33526. PMLR, 2022.
[50] W. Wiesemann, D. Kuhn, and B. Rustem. Robust Markov decision processes. Mathematics of Operations Research, 3811)1533-183 2013.
[51] Xie, C.-A. Cheng, N. Jiang, Mineiro, and A. Agarwal, Bellman-consistent pessimism for offline reinforeement learning, arXiv preprint arXiv:2106.0691 2021.
12

---

[52] T. Xie and N. Jiang. Batch value-function approximation with only realizability, arXiv preprint arXiv:2008. 04990, 2020.
[53] T. Xie, N. Jiang, H. Wang, C. Xiong, and Y. Bai. Policy finetuning: Bridging sample-efficient offline and online reinforcement learning. Advances in neural information processing systems, 34:27395-27444 2021.
[54] H. Xu and S. Mannor. Distributionally robust Markov decision processes. In Proc. Advances in Neural Information Processing Systems (NIPS), pages 1-505-251,, 2010.
[55] Z. Xu, K. Panaganti, and D. Kalathil. Improved sample complexity bounds for distributionally robust reinforcement learning. In International Conference on Artificial Intelligence and Statistics, pages 9728-9754. PMLR, 2023.
[56] R. Yang, C. Bai, X. Ma, Z.. Wang. C. Zhang, and I.. Han. Rorl: Robust offline reinforcement learning via conservative smoothing. Advances in neural information processing systems, 01223811-23866 2022.
[57] W. Yang. L. Zhang, and Z. Zhang. Towards theoretical understandings of robust Markov decision processes: Sample complexity and asymptotics. arXiv preprint arXiv:2105.03863 2021.
[58] M. Yin, Y. Bai, and Y.-.. Wang. Near-optimal offline reinforcement learning via double variance reduction. arXiv preprint arXiv:2102.01748, 2021.
[59] M. Yin and Y.-X. Wang. Optimal uniform ope and model-based offline reinforcement learning in timehoomogenoou reward-free free and task-agnostic settings. arXiv preprint arXiv:2105.0602 2021.
[60] M. Yin and Y.-X. Wang. Towards instance-optimal offline reinforcement learning with pes- simism. Advances in neural information processing systems, 34, 2021.
[61] C. Yu, J. Liu, S. Nemati, and G. Yin. Reinforcement learning in healthcare: A survey. ACM Computing Surveys (CSUR), 55(1):1-36, 2021.
[62] A. Zanette, M. J. Wainwright, and E. Brunskill. Provable benefits of actor-critic methods for offline reinforcement learning. Advances in neural information processing systems, 34, 2021.
[63] W. Zhan, B. Huang, A. Huang. N. Jiang, and D. Lee. Offline reinforcement learning with realizability and single-policy concentrability, arXiv preprint arXiv:2202. 046444 2022.
[64] J. Zhang, A. Koppel, A. S. Bedi, C. Szepesvari, and M. Wang. Variational policy gradient method for reinforcement learning with general utilities. In Proc. Advances in Neural Information Processing Systems (NeurIPS), volume 33, pages 4572-4583, 2020.
[65] Z. Zhou, Q. Bai, Z. Zhou, L. Qiu, J. Blanchet, and P. Glynn. Finite-sample regret bound for distributionally robust offline tabular reinforcement learning. In Proc. International Conference on Artifical Intelligence and Statistics (AISTA7S), pages 3331-3339. PMLR, 2021.
13

---

A Experiments
In this section, we provide simulation results demonstrate the performance of our algorithm. We consider two problems: the Frozen-Lake problem 6 and the gambler problem 440 65 36
For the Frozen-Lake problem, an agent aims to cross a 4 x 4 frozen lake from Start to Goal without falling into any Holes. The reward the slippery nature of the frozen lake, the agent may not always move along the intended direction.
to be when the agent reaches Goal and otherwise. Due to
We formulate the gambler problem based on a sequence of coin flips. The gambler wins the stake when the coin lands on heads and loses when the coin lands on tails. The probability of heads for the coin flip is p = 0.6. The game begins with an initial balance and ends when the gambler's 's balance either reaches 20 or 0. The reward is set be when the state reaches 20 and 0 otherwise.
infinite-horizon MDP. A gambler engages in betting game
A.1 Comparison under the total variation uncertainty set model
We first evaluate our algorithm under the total variation uncertainty set. We adapt the construction in (36] design an DRVI-LCB approach for the TV defined uncertainty set as baseline, and implement the two variants of our algorithm: distribution-based design and value function-based design. The robustness level R is set to be 0.1. We generate the dataset according to uuss, a) (a=rr()) + L--x where 7) is a random action, and x (s) denotes the optimal robust policy. Clearly the dataset satisfies the partial coverage assumption T.
We run the algorithms independently for 10 times and plot the mean of the sub-optimality gap and mean plus and minus the standard deviations of the 10 runs the envelop. It can be seen from F and Fig. 2 that the value function- -based construction has smaller sub-optimality gap and converges faster than the distribution- based construction and the DRVI-LCB, which demonstrates that our algorithm less conservative and more effective.
Vidur function bawd Datn button baaed DRV-LLC LCB
Walue fa bavel Detmibution baxed DRVVLCC
12-
0.9
1.-
0.6-
02-
200
400
COC
00D daseset
1000
1806
14:0
0
200
400
500
0.0
3000
1200
I600
Size
Sue of datine:
Figure 1: Frozen-Lake: TV Distance Defined Uncer-
Figure 2: Gambler: TV Distance Defined Uncertainty Sct
tainty Sct
A.2
Comparison under the x2 divergence uncertainty set model
We then compare our algorithm with the DRVI-LCB under the x2 divergence model. Similarly, we adapt their penalty term design for the uncertainty set, and run the experiment under the two environments. We similarly generate dataset following μ constructed above and run the algorithm for 10 times. The robustness level R is set to be 0.1. It can be seen from Fig 3 and Fig 4 that the non-robust DP converges much slower to the optimal policy, whereas our approach has similar convergence rate to the DRVI-LCB to the optimal policy, which validates our theoretical results.
14

---

Netust Ne robuutt 3RW
Rotustt
Non--mbuuz
10-
DRVHUCB
20-
9th
0.
15-
60-
-0.
300
400
60.0
500
2000
1200
3400
100
200
300
400
500
500
700
Size detinet
Sun of ditioe:
Figure 3: Frozen-Lake: x² Divergence Defined Uncer-
Figure 4: Gambler: Divergence Defined Uncer-
lainty Set
lainty Set
A.3
Comparison under the KI. divergence uncertainty set model
We then compare the performance of our algorithm and the one in [36 under the KL divergence model. We similarly generate dataset following μ constructed above and run the algorithm for 10 times. The robustness level R is set to be 0.1. It can be seen from Fig and Fig that the non-robust DP converges much slower to the optimal policy, whereas our approach has similar convergence rate to the DRVI-LCB to the optimal policy, which validates our theoretical results.
Pelust D2
Robust BP Non-mbaad DP DRVHUCB
kir-rabuat UP 3RBI-LCB
2.-
0.-
2.0
0.0
-05
200
100
560
1000
1200
3400
100
200
200
500
Figure 5: Frozen-Lake: KL Divergence Defined Uncer-
Figure 6: Gambler: KL Divergence Defined Uncer-
lainty Set
tainty Set
We further run the three algorithms on the two uncertainty sets for the gambler problem. The robustness level R is set to be 0.2. From Fig. and Fig. 6 it can be seen that the non-robust DP converges much slower, whereas our approach solves the problem efficiently. Compared to LCB approaches, our method enjoys similar performance and convergence rate, further demonstrating the effectiveness and efficiency of our approach.
A.4 Execution time
To illustrate our computational efficiency, we implemented the LCB algorithm from [36 and our DRO algorithm under the KL model, monitoring the execution time of both methods while learning the same policy from same dataset. We plotted the execution time for each dataset versus size of the dataset in three environments: Gambler's game, Frozen Lake, and N-chain. As shown in Appendix A.4 our algorithm consistently requires less execution time across all three environments, demonstrating lower computational complexity.
15

---

Froee Late RLChergecc
Sar Game
N-Che: 2o
Figure 7: Execution time: DRO vs LCB
36
B Proofs of Section 4.1
Lemma 1. For each state-action pair (s, a). set
S log SA
2N)
Then with probability at least Pe Po.
We then present the sub-optimality gap in the following theorem.
Proof. For the (8, a) pairs with N(s, a) = 0, the statement is trivial due to the fact that Po A(8).
hence sufficient to consider the pairs with ((s a) O.
By directly applying the Hoeffding's s inequality
22 we have that for each pair (8, a, a)
P(IP:.
S.z Pa s.ar
2 k)
< exp
2N a))²))
(19)
hence can be further shown that
SA Slog 2N a)
||P: - P <
(20)
simultaneously for any (s, aa-iiir with probability least 6.
Now consider any q E Pa. holds that ||q P < R. Hence
S log SA o V (N,
||q | 11g
Poll + |IP: P S R+
(21)
which implics that Po S Tog for any (s, a) with probability at least 8.
Theorem 5. For the output policy of algorithm 7 with probability at least 25, it holds that
2
8log SA log 45A 2N pmin
V (p) (p) - (1 7)2
(22)
Proof. First note that
V V
V V
Víj
(23)
Due to the fact that Pa C PP with probability - 8, it holds that
v < V
(24)
and hence
VS V < VS V
(25)
can be further bounded as
V (s)
V.J5
16

---

=r(s, (s)) + 2o, -
(
S (s)) ((s,
) -o (0:
S <P(P)) VV -V (v)
(26)
where (a) is from # arg max, Vz. and the last inequality is from the fact Pp Pg and hence of (V3")) S (Pv)
Applying the inequality above recursively implies
(s) S
1
Σ dr (
(27)
Note that
(o)0 -
( (V - ( E (p -
Σ (1) -005) Σ dp (z))) {V
8log 4SA log SA
$ (0) + V
(28)
2N x- (6))
where the last inequality is from
l1ō* (V
5
(P: -4) - RSRRapaaa V3J ->13
max
max OSAS
PP: - -
- (N, + R) S)an (zz - [
max OSA5 +
(P:(Vz A) RSpan(V A) -P: A) - (N= + R)ap (V -1)
max
max oSAs 1-
< max
max TSAS
Span (V - X)1 -2)1
(29)
where (a) is from the dual form of (V) and (b) is from the fact that max F(x) max, G(x) <
max, [x()) G(z)].
Slog 2A From the definition of A V 2N(x.)) hence
9 log 24 2N (x))
log 4 log 34
it holds that K V
2Nu(e.m and
8S log 1SA log SA
k Sp
X) S
1- 1--\ V ANp(s,TT(0
(30)
To further bound
28
first note that
1 Σ de o (s,a)lo;(V3) )3(555
< 1
(s,
max
|
(31)
17

---

which is from the dual form of o.p (v((V. i.e.,
Oeg (V) = max
[V][V]> Span([V] [V]x)),
(32)
T
and [V]a(s) min (Vn)( A). We then involve 20 and holds that
1 Σ
dp (V
(VF))
(8, a)
max OSAS
P 2 90 A
5,a
Slog SA 1
Σ
dp (s,
5 (2((s, a) 1 1-7
85 85 log 2N (s))
SA log 154 8
<
dp.. (8,a)
8
7)²
85 log SA log 45A 5
(33)
(1 7)2
2NV 2Nu((s, (s))
Plugging this inequality (27 and from the definition of C"" we have that
45 1o5log 5
4SA Ca"
(s) - V
(34)
(1 7) N
which completes the proof.
Theorem 6. For the output policy ä of algorithm
with probability at least 46, it holds that
(O" S ) N(1 y)
(C** S -
(p) (p) -p) Sō
(35)
N(1 10---1 7)3
Proof. Note that Lemma 8 of 36 states that with probability 1 6, for any (s, a) pair,
N(s Np(s,a a)
(36)
loo
We hence conduct our proof under the occurrence of this event. Note that for any s.
ViJ
(s)
V (s)
ViJ (s)
V (s).
(37)
(A)
(1))
From Lemma and Lemma
3 the above bound can be bounded as
V (s) Vi (s)
16c1 log 19AN log 4SA
1 max R, 1 }
< (32 4V8)
(1 7)2 Umin
N
2(8Ki 16) log 454
NMmin (1 7)
16K3 T S Slog 8
4SA
(128K3 + 32K1 + 32) Slog 4SA
4V
72(1 (1
(1-7)2N
80 S llog 4SA
2
+ 4K21
N
721 - 7)2 max (1 77, R)
18

---

Ü (C" + 1 N(1 7)2
(C*t (C S pminn
(38)
N(1 - 7)3
which completes the proof.
Lemma 2. (Bound on Term A) With probability at least - 26, it holds that
VΦ (s)
VI (s)
16K3 Sloo 4SA
(128K3 32K1 + 32) S Slog 49A 5
21 N
(1-7)
80* Sloog 4SA N
+ \
(39)
V 72 - 7)2 max - -), R]
Proof. To bound term (4), note that
V (s) - (s)
r(s,, n (1)) + 70, -mxx)())))+)
(0)
S ((0,='())) 10 ((,, (á
)
( + rō;
S ((V - -V)) 70 -
(40)
where (a) is from # = arg max, V5. and the last inequality is from the fact Pv E P and hence
(V - (Py)
Applying 40
recursively implies
V (8)
1 S 1-
Σ
di -
(41)
Note that
(o -1 + (V²) (3()
(5)00))) 005 Σ c (z) - (V
160 S log 1SA
Σ ( -
6
(42)
(1 - 7)N
where the last inequality from
||a (V
(V
(0)
{P:(V A) RSpan( VV² - -11}
max
max OSAS
IP: 2) - -kx + Span (V - 2)}1 |
-
max
USA
T
(b)
{P:(V z - A) + RSpan
>) P= 5 - A) - -n=; + Span -1)
<
max
max OSAS
19

---

I max
max TSAST
><SSaan (V
(43)
where (a) is from the dual form of o. (V))) and (b) is from the fact that maxe F(x) max, G(z) -
max, [f(x)) G(z)].
Since N(s, 2
Nu(s.)
from Assumption
1 we have that
8 slog 2
log 4SA 8 min (di, (s, (+xx(())) (s)),
80"" log 4SA
S0 log
4SA 5
(st
(s) S
xs)ss
N
dp, (s, x (s))
(44)
1 From the definition of x² N(,ay it holds that 1² N(a.=' (s))
&log 484
80 log a
S
No(s,
N
p0p (8,7 (s)) and hence
48A 80"" log
160** Sllog 4SA
Σ dp, (s.n)Span A)n S Σ dpp (8,
6 (s
dp. (8, (1)7((s))) 5
(1 (1-7) N)N
(1 - NN
(45)
To further bound
42
we first note that
Σ dp (s, -
1
8,8
dp p (s, a)
max
PlIV P
(46)
OSAS --
8,a
which is from the dual form of og (V),
Jag (V) = max
[P*[V]> - Span([V)x),,
(47)
05AS 1
and [V](s) = min m (V(s, AJ. We then utilize Lemma 15 and 44
and it holds that
dp (s, al)o()))(()))) -
<
dp (8,a)
max
PH[V P J
OSAS
8,a
K1
Varps (V
dp ()
+ K2
(1 (1-r)
N(s.a)
Σ dp (s)
OK, log 1SA (1 (1-7)N
(S dpp (s,a)
1
+ K2
Varp (V
N
16K, OF' Slog 4SA
K2 Σ dp (8,0))
Varpy (V²) N(s,a)
N(1 7)
1-7
16K,0* Slog 1SA
K₂ Σ de (s
(ar (V,))
N(1 - 7)2 1-1
7
((s
5,a
K2 Σ
Varp.. (V
(ar
dp dpp()s))) (s.
(48)
1 1-9 7 8,a
((s.a)
20

---

We then bound the two terms as follows.
Bound on Term A
We first claim the following inequality:
V >p VT + 21z) (o0))) 0.
(49)
To prove
(4). we note that
$ (s) max 02
2 (s)
= i( (s)) - (V))
=(s, (s)) (Pp))V -P + 1
= f(s, (=(s)) - + 10
2 ((s))((s) - V 2/700(1))) (0,(1
(50)
and hence for any 8 E S,
V (s) -
(Pv) ( - - 2 (s)) 2 0.
2
(51)
which proves 49
Now with
49
we first note that
(V VT) () (PPP)))
= (V PP:V o (V 13)
< (VF V2 +2/0 - -033) (V3 +)p(
2
< 1 (V -Pp V 2 (V) - ~00 (V)))
(52)
where the last incquality is due to the fact ラ + PP v S ش and 49
We first have that
Σ dp, (s) Var(p (V7))
SE8
(dp, p, (V p - (P/V7))
dp (V vg+ z (Vă VS)
1
+
72 7) (Vz .Pv VØ + 22)700(V;5) -70 (V25))
2
700
(0)
1
2
4
dp. Pv vz)
(V
VS))
(I - -Pp))
72(1 - 7) hō (V²) 70 (v
7
72 7)
fp. 1 (xpp (VF v/+++ + 72(1 7)
2
4
72(1 - ho² [Vz" 70 (1331)))
(4b,) [1 7pp) (- (V o VT)) + 72(1 - 77)
2
4
V
72 7) (dpp .. 1/00000 (V7)) (V35))
@ (1 ( V VSJ + 72(1 イ
2
4
V
(dp 160 (o3) - 7 (Vz)))
72(1 - 7)
2 V +
4
dd hō (V 70 (V*)))
70
21
$ 71 77)
(d l/² (V7 - 70 -V, (V
(53)
72
where (a) is from
52 (b) is due to 7 < 1, (c) is from the definition of visitation distribution.
21

---

Note that by Cauchy's inequality, E, (s) Var s VE. App (s) Var (V7).
hence
Varip (VF)
Σ dp, (3.00y
a))
3,a
80"" (S + a7 (oa))
log
4SA
Var (ar(p (Pp):
Σ dp p (s, (s 8,0
N
4SA 80 log
Σ dp, (5,0)/
(S+ dp, (s,a)
Var (V)
N
80" log 4SA N
Var(pp)) (v)) (VS+ + Σ dp (5, (
v d2p (8,
3,a
80 log 1SA N
(Po (V + Σ dp, (V. 8,a
dpp Var (V3)
V
8,a
3 S Slog
1SA
dp Var (V
N
8,a
x2 Slog 48A
2 72 77)
+ 72 - 7) (dp (dpp. -v=
N
64C S Slog
4SA 8
48A 128C Sloog -
Vdpp, 1ā oz (v33))
72(1 N
7(1 N
64C** Sog 0
1SA
18A 64KgO*' S Slog
x
+
(dp 10' - 0² (Vgg))
71 10--)) N
7(1 1 N)NV
2K₂
19A 64C** Slog
1SA 64KgC** S Slog 8
5
(dp p 15 - o" (vz3)))
72(1 N
7(1 NN)
2K₂
2K₂ (dp 1 10" (VV)) -V3()))
64 Slog 4SA
64C* "4C""SKKli log 48A
+ 2K₂
(dp (dp 10 - 6- (V(xx))
72(1-7). 11--) N
7(1 - N
16C" Slog 48A
(54)
K2
where the first incquality is from 44) and the last incquality follows similarly as 422
Hence, Term A₁ can be bounded as
A S 64K3C* S log 15A
64K3CF* Slog 1SA
y(1 11--)) 7 pmmin 2(1 7) (db
(dbp,11'' 1o 8² (V35)
- 3 + 160 Slog 15A
72(1-2)33
(55)
71
Bound on Term A2
From Lemma 10 it is straightforward to see that for any transition kernel of E Pg.
VVrry (V35)
Var.; (V/5)
22

---

Varpy (V min V (s)) Var 5z (VF
min V (s))
|IP: &.111l1 min V (s)]?
(pan((pn)))))))
(56)
72 max (11 - 7), 12)
Hence
Varpy (V.) Var PP (V
di (s,00
N(s,a)
32C Slog 4S.AA Varpy (VT)
Var p (V))
Σ dp (
N
r2 S llo 1SA
Σ dpp (8, (s,
Varpy (V
(ar(p))2(
8,0
4SA T2 Slog N
8
Σ dp, (8,a))
2
72 max - 7) R.
8,0
T2 Slog 1SA
2
(57)
2 max (1 - 7) R.
Thus Term Ag can be bounded as
=2 Slog 1SA 8
2 72(1 72 max (1 7), R
A2 S Ka
(58)
N
Combine the bounds we obtained for terms A and Ag in (55) and 58). have that
Σ op (s, aV)o - (V (
8,0
64K3C* OF' Slog 1SA
6'K3C==' Slog 1SA
+
1
Σ
dp (s,a)lo (V
22 - 7
7(1 2
2(1 7)
5,a
160 8 Slog 4SA (1 (1-7)²N
32C** S 'log 4SA
2
16K C S Slog 45A
Ke
N
72 - 7 max ( (1 7), R}
N 7)2
(59)
which further implies that
Σ de (s,a))o -3((5))
8.a
16K3C= Slog 4SA
6AK3C**, Slog 48A
(32K, log 48A1 + 16 16log 4SA C S
<//
7(1 2 +
72 - 3)3N
11-71 -
80 S Slog
49A à
2 72 22 max ( 7), R)
+ 4K2
(60)
N
Then, combine
and the inequality above, we have that
V (s)
23

---

< Y Σ
4 -
8C" Slog 48A
E
bpp (1) 1 [v
(1 - 7
16K30= log 1SA
(128K3 + 32K1 + 32 loog 1SA
4
8
72 N)
(1 (1-7)2
4SA 80" Slog
6 N
+ \
V 72 7)2 m (1 - -7), R}
(61)
which completes the proof.
196s; log 48AM log (1- Mantn
Lemma 3. (Bound on Term If 2
then with probability at least
28,
holds that
B S (32 + \ 16c, log
4SAN 0
log 45A
(1- 2 N Umin
max (R 1 - }
2(8K1 + 16) log 49A 5
(62)
Numin (1 7)
Proof. From the robust Bellman equation, it holds that
(*) - (s)
((s) - (() -50
- o
- (P - (VV5))
= =>(Pv) - v3) (v, - (Py)
Σ d -P V
(Pv)
< 7 Σ dp (z) - (P 2 ( VF)
(63)
1
where (Pv) (()) arg min vegioo qVFr, and (Pv); (())) arg min geoi( (ot VV and the last inequality
from (Pv).(o) p. (+) and (P (x))) V
f. ) (V
(Py ) V
On the other hand,
($() (s)
-f(,,((s)) + -()))) (o=
=>(0.(V)) (V²))
) - (Pt) (((5)))
(
2
- - ) -PP)
(Pp) [ (
>Ppp) (V; - () - (Pp)
Σ 4 (z)
(Py) V
(64)
where (a) is from the fact that P. p and hence of of (V (Pp). [(0) (g)
24

---

Hence we have that
S max
1-7 -
7
(P )P 1
7
(x) (V (Pv) (
(65)
We then bound terms (I) and (II). Note that the only difference between the two terms are the visitation distributions, i.. db, and de
Bound on Term (I) We first note that
105(V;) (Pv) )
-V, 00 a(() (V
(V o. (V
(V o (V,)
(66)
(Bi)
(B:)
hence it sufficient bound B1, B2.
To bound Bi, note that
p (V
max
(*
(+) (V3 A) (R + xx(() (pan))pa((( - -)} x
max((p A) RSpaan(V (V H)H
m
SVa - }}}}
*(x)
(67)
1 1-7"
where (a) is from the dual form of the support function 13 and the last incquality is because Span(V) - for any 0 S V < T-
We then bound Bz. Similarly from the dual form, it holds that
| (V
+()) (v S max ((P(()) pV()) A)).
(68)
We then apply Lemma 15 it holds that
max (P+()) p+(x) (V -+ ^)}
K2 N(s, (s)(5()))(1-))) +V
(a log( 4SAN2
Var
parp (V²) $
(69)
((s
with probability at least 8 and K1
2 + 02 log
4SAN²
2c, log
4SAN2
Note that for any
Varpy (Vz)
Var (v (V + (Var (V
Var (v): + (Varpy (V
Var (Vz)).
(70)
Hence
Varp: (V5) 1 (ar (V, + Var (V
Var (V/5)
25

---

Varpy (V
Var (v (V,)).
(71)
Firstly, Lemma of 38 and Lemma 10 imply that
Σ dp (1)
Var (V S
8Span V3)
64
(72)
max R, 7)
To bound
Var )g (Vī)) (a (VF)). note that it holds that (Vr (Vz)
(P
(V5)
- V VT112 thus
Σ dp (r) Var / (V Var (VF) s V V |.
(73)
And the last term can be bounded
2
Varpy (V (a 72 max R. - 7
(74)
using 56). and hence
8
E (z) Varp: (V
(V (V
(75)
V max R, - 7
Hence by combining 722
73 and 75
we have that
Var p (V
Σ dp, (1))
(ss, (s))
8log
4SA Var pp() (V+) 5
dp, (x)
N pmin
8log 4SA
1 - V +1+
(76)
N Pmmin
max f Rt 1 - 7}
Thus plug the inequality above and the bound of B₁ in 633 have that
15 py (V))) (P (
16c; log 8
1SAN
log 1SA
||V V - (8+ VBNV
N Mminn (1 7)2
max R2 1 - 7
4Kg log 18A
8 log 4SA
5
(77)
N Npmin (1 - 7)
(1 7) 22 Mmin
Bound on Term /1
Similarly to the analysis in bounding the Term (I), we have that
(V (Pv)).
(P)))(0)))) )+())))) ( +5(13)
0. (V
(78)
(B.)
(Bz)
where Bj can be bounded as
(())
(V 0. (V
<
Kis
(79)
1 -
The bound on B2 similarly follows in Term (f). Note that
26

---

K
log( 4SAN2
Varp,
p((0) (V
(V (5) -
+
(80)
((s, # (s)) -2)
(s,
with probability at least 8 and K1 2 + c2 log
1SAN2
2c log
19ANs
Note that for any s, a,
Varpa (VT)
Var (V²) + (Varp: (Vz) - Var (2)
(Vz)).
(81)
Hence
Varps (V S
Var (P)) (V
Varp: (V7))
Var (P&)) (ar(p
(V
(82)
Similarly, Lemma 13 of 388 and Lemma 10 imply that
8Span VBB
64
Σ dp (s) Var (V S
S
(83)
72
max Ri 1 1-11-1 7 7
And to bound V Varp (V+)
Var (V note that
Varp: (V5) - Var Var (V3)s 72 max R, 1 1-1-- 7
(84)
from (6). and hence
Edp (5) Varpy (V²)
(P 1
(85)
max R, 7
Hence by combining
and 85) we have that
Var pt (00 (V ((s. #())
Σ de (8)
8 log
3 4SA Var p p
Σ dp (s)
Mmmin
log 1SA
S N Mymin
(8 (8+ v8)
(86)
max{R,1
(R
Thus plug the inequality above and the bound of Bi, we have that
II II 2 Σ oe (s)
(P&) $
160 log 4SAN log 4SA
(8 + vB)
Numin (1 7)2
max ( R2 7
4K, log 45A 8
8 8log 4SA 5
N Pmmin (1 7)² +
(87)
(1 7) umin
Then we combine the bounds terms (I) and (II) together, and we have that
v
(s)
V (s)ll
p
16c, log 1SAN log 1SA
1 max R,, 1
|I - + (16 2V8)
N Numia (1 7)2
1
27

---

48A 8K1 log 0
+ 16 log 4SA
+ N Umin (1 7) (1 7) Mmin
(88)
196o, log A2AM log 234
Due to the fact that N
(1-7)* Nyuiii
160 log
4SAN log 49A
1
V < (32 + 4
- 7)2 pmin
max R, 1 - 7
2(8KI + 16) log 4SA
(89)
N Mmmin (1 7)2
and hence completes the proof.
C Proofs of Section 4.2
Theorem 7. With probability at least
48, the output policy ă of algorithm satisfies
(1 Rt) log 24SAN
log
48A C S
7K2S + Rlog 854
V (p) V (p) S 401
(90)
N(1 7)
(1 7)² pmin
Proof. Using the similar decomposition implies that
(8)
V (s)
V
V (8)
(+).
(91)
The proof is then completed by combing the following two lemmas.
T
Lemma 4. (Bound on Term A) With probability at least 45, it holds that
(1 + R)Cx Slog 24SAN log 4SA
V (s) V (s) S 40
(92)
N(1 - 7)2
Proof. To bound term (A), note that
V (s) - (s)
-r(, (+))
-)
(8)
2 =(( (s)) (V' 18, (8)) (1
To.(V3 (V;
1o; + -o
S <P(P)) (V)))
(93)
where (a) is from # = arg max, VTJ and the last inequality is from the fact P. Pt and hence (1 < V
Applying 93 recursively implies
(8)
Σ di -
(94)
Note that
28

---

- +6(0)) -2 (V,) + Σ 4 (+)1 - (1
1 Σ
- 02 -
(95)
The first term in
95 the uncertainty set PP {g A(8) x2((( (qllp) I R) as follows:
can be bounded as follows. Recall the dual form of the support function w.r.t.
(v max {DV. RVar)
(96)
aE
where (s) = min (in(V(s)) a).
Applying the dual form further implies that
(V 3
(( (RVVar:; ((V3))) - - RVarpp ((V3)a)
< max 050
(P - (V)
(P (V))
+ max
(V (( - RVaar (vz))a
< max 0saST
OsasTh
log 2SAN
(VeVarey ((VZ)a)
R
$ V N(s, a) - 7)²
max
V /RVarpp (Vzz)a)
Osas
(1 >)N
(97)
where the last inequality directly follows from the Hoeffding's inequality [88 and -net technique used in Lemma
As for the second term in 997 we utilize Lemma and the technique of e-net, which implies that
((V a)) 85 (V
log 2SAN
Ro 24SAN
$ 2/ N(s, a1 - 7)2 + 2
N(s, a) - 7)2
2(1 + R) log 21SAN
R
s </V ((s,a)11-9)) 7) 7)2
(98)
(1-
This hence bounds the first term in (55.. For the second term in 95 similarly apply the dual form and we have that
10 (V 05 (V
S max oSas
RVar,, (VVzaa) V(R + nzg) Varp. Varpg((V ((F))a)
Varp. ((V))a)
max
VR / R + Kg 0SaST
(1 + Rt) log 24SAN 8 N(s, a1s 7)
(99)
where the last inequality is from the fact that Var(V.)= I (1- for any V S T-y and any a S -
We now plug
98 and
99 to 95 and 94]. and we have that
Vs (8)
dp
(x)la
(V
24SAN 8 V (()
(1 R2) log
2(1 R) log 24SAN
2R
dp (x)
+ 1 ((z -
(1 - (1-7)N
29

---

(1 + R)C S Slog
24SAN log 4SA 8
S 40
8 7)
(100)
N(1
where the last inequality is from
44 This hence completes the proof.
Lemma 5. (Bound on Term B) With probability at least 46. it holds that
>K25vI+ Rlog
(s)
VS (s)
(101)
(1 - N Mmin
Proof. Similarly to the proof of Lemma note that
($) (s)
= (r(s5((s)) + -,, (V -(s, - 70,
70 (V²) (0
(V,) - 70. (V 70, 7(1) (V/) - -0, (V$)
I >P(Pv) ((() (Vz - V + (+) (V 70, {() (V²))
Σ (8) (V (0) (V
(102)
where (Pv) = arg min
ge V We then bound the term
0, (VØ))
From Lemma 6 it holds that
(+) (V (V( 7
1 1- Σ d (s) K25VI+R
(
7 K2S + Rlog SSA
(103)
(1 N pmin
which completes the proof.
Lemma 6. With probability at least 6, it holds that for any E 8,
K2Sv1+R (1 (s,,
(V + (+(+) (V
(104)
Proof. We first consider a vector V that independent from P.
(+(()(()) σ. ((())()) (V)
max(p=(oo(V_)) (R + #(() Varpew (Va)] maxx(P(()((aa)) - V /Raarpp poa (Va))
< (V.)) - v vI Kis
F(()
Varpzw (Va.) paii)) +
(105)
where a" a arg max, (p-(()) (Va) V (R k² #(s) the fact that max f < -x(x) for any x.
Varpato (Va)), and the last inequality is from
We then construct an -net over [0, r such that there exists 3 with ||V.- Vall S Si, Then we further have that
5x (V) (0(
< (Val)) V(B+ ris [(()) Varp (Va.) - -p(())(Va.) + RVarppoo
C2 Varpzeo (V))
9 ((s
E1
+
N(s,
(1 -17)) 7)
30

---

VR + k())) ((5) Varggto (Va)) (Va)) +
RVarppon (Va+):
(106)
where we use the Bernstein inequality and the technique of c1-net. To bound the last two terms, we note that
V (R + 12
#(s) Varpaw (Va.) + RVar p (Va-)
(0)
RR + A(8)
Varpaco (Vz) + v RVarp;(.) (Vz)
RVar patpp + RVar p; (Vz) + V V(1 71)
61
(6)
(R + 1ix
A(s) Var (Vz) + /RVar pr(0) (Vo) +
((1-7)
C1 Varp (Vo)
C2
+ VR
(107)
(s))
(1 (1s,))(
where we again use the enetet technique in (a), and apply Lemma 7 in (b). Combining (106) and 107 implies that
(s)) (V) 0, (V)
C2 Varpaco + (1-7)
C1 $ (1 - (s,
61
(ss)
- (R+ -V Ke
#(e)
Var (Va) + / RVVarpson (Vz) + v (11 (1-
E1
+ +VR (V
Ci Var (VB)
C2
+ (1 (1,,)
(ss)
C2VR
C1
61
V (1->) + (1 (s,,
(1 - 7s,(
(1-
RCI Var Varpsto (V))
C2 Var p3t0 (V3) N(s, (s))
(R+ Kis *(*)
Var Varpfio) (Vg) (VB))
RVVapsco + V
V(s,T(9)
C2VR
9
(1 (1- + V (1-7)* + (1 (s))
(1 (s,
+ Varppw
V
62 N (s,T((s)
*V (ss)
RC₁
+ +VR- V R rig #(*)
(108)
Clearly, if we set C = V02 + VRC and
C
CR
1 (VMos
+2/ ((s)
=
(109)
N(s, (s))
then [a))((A)
+
RC [())
+ VR v R+ xx()) #(s)
S and hence
CVVR
(V())(V) - (0(00(() (1 (1,))N(s,E(s)
41
+ (1-
+ V (1 (1-2)
+ (1 (1- #(s)
VI+R R
(110)
(1 (1-7), (1-7)N(s, a(s))
by setting e < O(
Now to show the claim for V we construct an ez-net over |0, 1-1 Js. By applying the similar trick, we complete the proof.
31

---

Lemma 7. For any vector V E [0, 1-y1 that is independent with P, with probability at least 1 5, it
holds that
C1 Var (V)
C2
V Varp: (V)
/ Varp (V)
((s,a) + (1 (s,
(111)
Proof. This result can be derived from the Bernstein inequality for U-statistics 3 32 by noting that the sample standard deviation
1=- Varpo (V) an U-statistics and
Varp (V)
Varp: (V)
Varp, (V) S
(112)
V
D Proofs of Section 4.3
8 $log 1
Theorem 8. If N
then there exists some universal constants C₁, C2. such that with
Menin
probability least
40, it holds that
2C CT" log 2(1+R)N2 (1-9)8
S
VT(e) (p)
V
(p)
(113)
NR(1 77
R(1 7))
NP
Mimin
Proof. Note that
V p
V
(114)
The proof completes by combining the bounds on the two terms, shown in the following two lemmas.
Lemma 8. There exists constant Cz such that with probubility least 1 8, it holds that
202 v T C log
2
0 A NR(1 7)2 +
(1-7)6
S
(115)
R(1 7)2
NP min
Proof. From the definition,
v $
(s)
max
Q (s, (s, f(s, (s)) + 10 (V²))
(116)
hence
(i(s) VJ (s) (s)
= i(8, x (8)) + 70 (V7) Vz)
S n (V7*) ) p0 (V²)
popp' (Vz) 70 (V "o (V7) - -70p-- (V
79" (V V + c(s).
(117)
where df is the worst-case transition kernel of V in Po. and (a) is from Ogg (V Opp (V/5 =
Opy- (V (g"" (V S (g." (V/" - V and c(s) A yo (V 30. (V )
Recursively applying
further implies that
1
4 Σ
(d c).
(118)
-
32

---

We moreover rewrite e as
c(s) = 10p3 (V))
30 (V))
+10 (V,) - - (Vg))
(119)
A1,1
A1.2
Moreover, we introduce two sets
SI = {8 max do (8,) = =0;,
(120)
QEP
S2 (8
(121)
For E 81, (216) of (36 implies that d (8)
We then focus E S2. It has been shown in [36 that =(,, > 0 and (s,
x"" (s)) >
N Wmin{+ $ a. (+))
12
Thus Lemma 17 first implies that
4
C1
log (1-7)6
21
10gz (V5) - ozg.
-gg (VJ)1=
NR(
7)
R(1 7)
N(s, TT (8) min, Pr.
4
C1
120 log (1 31-
2)N+S
(122)
NR(1
7)
R(1 7)
min. Pr N min g. dz (8))
8.
To bound 21,,, note that
(s) = 70 (s)
-a.j-- (s)
V p
max U.A
-Alog
PT. exp
AR
V $
max U5A
- -Alog
PJ exp
- X(R + K3
T (s)
))
(
max
-Alog
pT exp
AR
05A5
(1 [ [a)
A
V $
))
max
- -Alog
prr exp
A(R+ + Ki 135(0))
05A5 >)RIn n2 Cor
(ong
max
05A0
(1 (1-7XRRa2) (01)
Rig (s)
<
(1 () + K3 (0)
K3 (4)
(123)
(1-7)R'
where (a) from the dual solution of KI.-divergence, and (b) is due to the fact that the optimal
solutions to both dual forms satisfy X < (1->)(R+k2'"0 (y (65, and (c) is due to max ff - max g S
max If gl-
1 log
Then we plug in the definition of K3 (s) =Cy that
N(a.n min, p.r and using (202) of 33 we have
(1-718
80 log NS log 2 RIN
C1 (12(8) < (1- (1-7)R) \
(1-7)6
(124)
N Wminf 3,4 dz min
33

---

Combine 122 and 124
we have that
C
s0"T log NS log (1-7)6
2(1+RIN9S
C1
120 log (1-
2(1+RIN'S
d(s) - (1 R)
6
N min 1 81 d (s)) min
R(1 - 7)
minz Px N min $3 d (o))
(125)
NR x)
Thus have that
(d) c) = Σ
dy (s)c(s)
C log NS log (1-7)6
2(1+R)N3
C2
4
J (8)
(1-
(1 - R
NP Mini min min g. d (s))
NR(1 - 7)
2C2v C log² 2(1 111+N)
4
(1-7)0 R(1 -7)
(8)
NR - 7)
+
min ( ( dz (5) V NP
2 C log" 2(1 RYNa8
4
(1-736 R(1 (1)
S
+
(126)
N 7)
NP min
where (a) is from Cauchy inequality, and (b) is from (220) of [36]. which hence completes the proof.
We then bound the term A2- Lemma 9.
4
p A2 S NR(1 -7)
(127)
Proof. First, note that
A2(s) = V (s) (3)
(03g (Vz) Opy (V7))
(a03 (Vz) 03; (V opp (V3) o.. (V²))
>ooy (V₂) ogy (V²) )) (o (Vz) 0gg ( (Vz))
(0) $ (V - V + b(s);
- 7
(128)
where of is the worst-case transition kernel of V in p and b(s) >(00= (V - ozz (V )).
Recursively applying 128 implics
P T
42
1 1-7 (d (d b).
(129)
We further introduce two sets as follows.
81 {s : n(s *(s)) 0),
(130)
82 {s 11s, *())) > 0).
(131)
For E S1. 50. = A(S), hence
b(s) = 2(033 (V - ogg (V²)) 50.
(132)
For E S2, we have that
b(s) 2 (V7) ogg (V²))
34

---

(apz (Vz)
Dgg (V3) +
ogg (VF) - ozz (vz)).
(133)
Hence invoke Lemma
7 we have that for E S2, with probability least 1 8.
log 21
Jpg (V
(V
s min
1
4
C1
(1-7)8
NR ()) I-
R(1 (11-)) 7)
\
[ss, 9 (s)) ming P
a.
(134)
To further bound the RHS of (34). we first note that Lemma 8 of [36 states that if N Nu(s, a) 2
8 log 3. then with probability for any (s, a) pair.
N(s. 2 Np(s, a)
(135)
8 log 4
This moreover implies that with probability 1 1- 6, for E S2. Nu(s, (()) 8 log
(ss Rss)) 2
(136)
On the other hand, (202) of 33 states that with probability at least - 6,
p ming
8. 8 log NS/5)
S min P a. Sea min P
(137)
Hence by plugging (136) and 137 in (34) we have that
NS log (1-7)6 8 log 8
2(1+R)N'S
C2
Tbg (V - opg (V
(138)
NR( 7)
R(1
7)
N(s,, # (()))
On the other hand, similarly to 123 it holds that
Ojp
Op.
V 11
max
- -ooog
Poexp
XR
05 AS アা-
A
V
))
max
- log
exx
P
-((R + ((()))
05
A
(1-7)(R+x2
10)
(139)
R
where the last inequality is from the fact that max max G 2 F(x) - G(v)) Va.
Combining with
134
further implies that
Tgg (V J3g (Vz))
log 2(1+R)N83
4
Ci
(1-7)6
NR - 7) +
R(1 7) V
N(s,, i(s) min P+
4
+ +ggg (V₂))
J.jo (V,)),
(140)
NR(1 - 7)
by combining (138 and (139) Thus
Tgg (V Ogt (V
(141)
NR 7)
Hence combine with 129 and
132
we further have that
4
p A N NR - 7
(142)
35

---

E
Auxiliary Lemmas
Lemma 10. holds that
1
Span [V
(143)
? max R. 1 7}
8 log 48A
8 8log 48A
Proof. Note that when N
and the fact that a(s
holds that
[1 1)mmin
Mmmin
R + Kg
((5) S R +
((s, #())
8 log 48A
< R +
Nymin
< 1,
(144)
Denote 8" = arg min, 5 (s). Then it holds that
(s*) = [f((s", ;(()) + po (V)))
(145)
We denote the optimal action (s) by a in the following proof. Note that there exists a vector of E R
such that P 2 dh 2 0, and Σ. (s') = 1 - R -xx-- This is doable because E. Pg((') = 1
and R + ni I 1. Hence it implies that the transition kernel df + (R + 12) E Pa. since l1 + (R + 1,) P.ll < و Pall + (R+ xga) 2(R + kG).
Hence
Jpa (V S (a + (R+ k1)1
$ (R+ (
1 (R+
= (R
(146)
where the last equation is from Plug this inequality (145), and holds that
=1 (s))
K and | = max, V = V (s*).
V (s")
Vmaa
S f(s" a) 7 x V (s.) + R- (3**
$ 1 + 7 < + 7(1 +.))Vaxx.
(147)
Thus
+ N kG)) V
V Vmax v
1 1 7(1 - Kg)
+ 7R R + :: min
1 q + R + 7/k
< - 7 + 7( kgg)
Vuin
(148)
which implies that
1
1 7 mmx 7}
Span (1)
(149)
1- 7 (Rt + kg)
Lemma 11. Recall the set S 2 {s 8 N(s) = 0}. Then
(1). For any policy h and E 8D, Vg (s) 0;
(2). There exists deterministic robust optimal policy ã. such that for any So, (s,, 0.
36

---

Proof. Proof of (1),
For any 8 E 8 it holds that (s,, a) for any a E A. Hence f(s, a) = 0 and D2g = A(8).
Then for any policy and E A, it holds that
2 a) = f(s, + + (V S {)]
(150)
Thus
(8) xals) {V}
(151)
which implies (s) = together with the fact that V
3 2 0.
Proof of (2).
We prove Claim (2) by contradiction. Assume that for any optimal policy म, there exists & & 8 such that (s, [s)) O. We then consider a fixed pair (ū, s).
(s, * Rs)) 0 further implies f(s, # (s)) 0, (=(a) (8)), and
V (s) max (5, a) = (5 ((s)) = f(s, i())) + y0 (V S s
(152)
where the last inequality is from ))((() A(8), (()) = 0, and Jann (VF) S V VJ (s).
This further implies that $ (s) = 0 because V 2 0.
On the other hand, since & 8" there exists another action b + #(s) such that N(s, b) > 0, and hence F(s, b) = b)) We consider the following two cases. (I). If (s, > 0, then
(s.b)) (op
(V)) 0= Q5,,
(153)
which is contradict to (s) max, a)) (s),
(I). (f), = 0, Lemma 12 then implies the modified policy f(( is also optimal, and satisfies (2x (())))) = (2, ())) for any x # and
> 0.
Then consider the modified policy (T)
there still exists & 8 such that (( = 0, then similarly, there exists another action
B' + f8 (s') such that N(s', BB) 0. Then whether r(s', B') > which falls into Case (I) and leads contradiction, or applying Lemma 12 again implies another optimal policy f (fī( such that N(s, fo (Z)) = N(s, ((()(()) > 0 for x & (8,8)) N(s, f (f)) = (s,, (+)) > O and N(s', S (UE(#))(+)) > 0.
Repeating this procedure recursively further implies there exists optimal policy m, such that [sss, (s)) > 0 for any & 8", which is a contraction to our assumption.
Therefore it completes the proof.
Lemma 12. For a robust optimal policy म. if there exists a state $ S and an action b such that ((s, (s)) = 0, r(s,b) b) = 0 and N (s, b) > O, define modified policy (i) as
(+) [z))(()) (x), for x +
(154)
(155)
Then the modified policy f5( also optimal, and satisfies N(s, (E()(())) 0, N(x,
Na, a (x)), Yx + 8.
Proof. Recall that (R(0) = A(8) and jph C A(8), we have that
(+))
(R)
(156)
37

---

where Pd is modified uncertainty set defined as
(P = A(8),
(157)
(P))2 = ga for (x, a) & (s.
(158)
Now we have that
(8)
(8) Ph
(V-5 (s,b) b) = -r(s,)) b) + (sig)) P/
S (v (5) (5))
(s),
(159)
Dy
which further implies v=(((() (8) 0. Note that eq. (152), we have shown vs() = 0, hence
.P
f () = (s) =0. O.
Now consider the two robust Bellman operator (²)()) (a))) + ( (V))
and (*) = (x)) + yo (V). It is known that (() is the unique fixed point of the robust Bellman operator Tğ and V is the unique fixed point of T. z.
When x * 8,
TTV (z) Σ M(a)a + (1)) (V)))
(a) Σ H(al=)(f(z, + 10 (P:); (V
f(z, ((z)
@ ((x,((x)) 7 (V7))
(v) = V (z).
(160)
where (a) is from ((( = F(z) when x + s, (b) is from (fb) = -
And for s, it holds that
(s) f(s, + 70 (1y)) (V.)
( f(s, (s)) 10 (88) (V}))
f(s, 2o (V3))
(s)
(s).
(161)
where (a) is from ( = A(8) and f(s, b) = r(s, b) = = -ss, (s)), and (b) follows from the
fact (p(() A(8).
eq. 160 and eq. 161
further imply that V also a fixed point of Tū. Hence it must be identical
(.)) to 12b i.e., V (
V
gb
Combine with eq. (156), we have
R(t)
(- P
= V
(162)
which implies that (ū) also optimal with ((s, (s) = NN 6) > And since (z) (2) for x + then N(x, (z)) = N(z, (z)). This thus completes the proof.
Lemma 13 (Lemma 4, 19).. For any with probability 1 - 8, max (12N(s, a), 8 log NS N Np(s, a). Vs, a.
>
38

---

Lemma 14 (Lemma 9, [9]). For any (s, a) pair with (s.a) > O, if is an vector independent of P obeying |V - T-x then with probability at least 1 6.
48Vrr p. (V) log AN
48 log 4N
I(P2 - V1 =
(163)
N(8,a)
(1
(s,
5lg
4N b
Varpy (V) S 2Vrpp: (V)
(164)
3(1 - 7)
Lemma 15. For the total variation uncertain and for any fixed and ö, with probability at
least - 8, it holds that
(o%(V -6% - (V
1 $ N(s, a] 7]
[SSAN2
4SAN2
C1 log 4SAN2
Varpy (V
+ 02 log
+
201 log
N(s,a)
(165)
and
41 log (1-7)Ø
Varp. (Vz) S 2Vrrpy (V7)
(166)
(1 - 7
Proof. Step 1: Construct auxiliary robust MDP. For the state 8 and any constant [0, 1]. we construct the following MDP M A8, pa1 ps.) with transition kernel as;a and reward 5.80
(p os = 1,, if x
(167)
(pa P if #
(168)
and
(x (x, a) u, if 8;
(169)
s (z,0) r(x a), if +
(170)
Centered at M we further construct the following robust MDP M A, Po.u A,s.u r:a);
(JON)) "2 = ((P))))) =f
(171)
(DSS)) To if x: #
(172)
(173)
The robust Bellman operator associated with this robust MDP is hence
TT'V(() max(r** (z. a) + 2a ( (V)),
(174)
a
and we denote the robust value function w.r.t. it by Vesu
Step 2: Prove V is robust value function w.r.t M for some u² [0, 1]. We claim that if we
set u = (1 V E [0, 1], then the robust value function w.r.t. M is equal to V
To prove the claim, recall that V is the unique fixed point of the optimal robust Bellman operator
Tv(x) max(r(z, + 1o (5)g (V)).
(175)
For the state note that
T = max (s, + 70 ( (V)))
max + (()))
max{(1 max (3)
39

---

V (s).
(176)
which is due to the construction of Ma And for states 2 o 8, we have that
T (x)
(x) = maxi (I, a) + +777700 (bu.)) (Vz))
max(r(z,a) po (V
(a)
(x),
(177)
which is from the construction of M and the fact that V is the fixed point of T.
These two equations hence imply that V fixed point of the robust Bellman operator T which further proves the claim.
Step 3: Decouple the dependence of V on P by constructing an -
Define U = { i 0, ...;, N). Clearly, is + -net 43 of the interval [0, 1]. i.e., for any u E [0, 1], there exists u, E U such that Iu u, - N
N
Clearly, each u E U is a constant independent with Pg. hence applying Lemma 14 implies that for any u U
c1 log( 4N Varp; (Va.))
C2 log( 4N
P.VS.M pgys.ul S
+
(178)
N(s,a)
(1 Ns,,a)))
Take the union bound over any (s, u) E E A U, and have the following inequality holds with probability at least - 8:
log( 4SAN2
Varpy (Vo.u)
log( 4SAN2
(179)
(s,
[1 (1-7) N(s.a)
Step 4: Approximate IP Pgv p using the -net.
As we showed above, there exists E U such that 1u-ull u01 F. Moreover, note that |VSK V
TTs. - T Vs.""] ||
Tosuus. Ts. iT..uus"" -To.u"Vor Voi""
+ 711o (Vaun" (fpna ((jaan(VV (VV9)") I] < >/ Va. VVau" || + || - p.u
< Va/V - Va.u" || + N
(180)
where the last inequality from (ppng (Voi"") that
0 (pre (p (Vee." for any v, a. Hence we have
| | Vouu || 5 (1-7)N
(181)
We further have that
P
pavá &
paaye payau + (Pp - (Va) - Vou""
log( ASAN2
C1 log(
1SAN"
Varp: (Va.))
8
N
(1 ((,
(s,
2 log 4SAN2
C1 log
4SAN2 8
(Varp. (Von*) + (Varp, (Vsa) Varp. (V&.)) )))
(1-y)N N)N
(1 Ns,
N(s a)
40

---

02 log( 4S.AN²
ca log 4SAN2 6
Varp. (Va.")
+
7)
(1 [s, a)
(()
log( 1SAN2
Varp: (Vau)
Varpy (Va.**)
(s. a)
log 4S..N2
log( 48AN²
Varps (Va.*)
8
(1 7)
(1 (s,
(()
201 log( 4S.AN3
(182)
((s, a) - 7)
where the last inequality is from
Var (Vi) Var,(V2))
= 1a(1/ o Vi) - (gVi) (gV) <(22 12)++ + (4V2) o (gV2)
< (9[[ o Vi -V2 V2)1 1(9V (V2) 12)
s 2 + V2 V2ll
V V/2l
(183)
Thus 182
can be further bounded as
P
7
2
02 log( 1SAN2
log( 18AN2
Varp; (Vo,"))
(1 N)N
(1 N1-
(s)
20 log( 4SAN2
N(s, a) - 7)2
4SAN2
4SAN2
$ N(s, (1,,a)(1-7) 7)
2 + 02 log
+ | 2e1 log(
8
8
log
48.N2²
Varpa (Vo.")
(184)
((s.0) a)
We note that this inequality exactly matches (127) in 38 hence the following part directly follows, which is omitted here.
Lemma 16. (Lemma 14 of (36)) For any (s, satisfying N(s,a) 0, and any vector V R
independent of po obeying |V| T- with probability least 8, it holds that
C1
NS log
Jyy (V) Ja (V)
<
5
(185)
R(1 -)
N(s, a) ming
P 8.
Lemma 17. For the Kl--divereence uncertainty set, and for any (8, satisfying N(s, a) with probability at least - 8, it holds that
4
C1
log
B1+R)NNS (1-3)8
(op: ogy (V < min
+
(186)
I- NR(1-1 R(1 - 7)
N(s, a) ming Ps
Proof. Step 1. We first construct a robust MDP with state-absorbing empirical nominal transition kernels. More specifically, for each state and constant 0, define the following transition kernels for any a E A, x E 8:
ppsaa
Ja
1 1
(187)
41

---

(P 15. = = s if # s.
(188)
Moreover, define the modified reward function: r (s, = u,
(189)
r "" (z, a) r(z, if #s.
(190)
We then define the following uncertainty set (Pe.))z for any A, E 8 as follows:
(PP))) {1,}
(191)
(DaM)) x = {q E 4(8) ((gl((**)))) - + K if
(192)
The auxiliary robust MDP is then defined as M (1p,a sea (ps..)) pa)
Step We next show that if we set o² = - (1 (s), then the optimal robust value function of M is identical to V
For any state x + and action b, it can be verified from the definitions that (SPs.)) ) = .bb. and hence
max(r="0 bx (p (V}) max(r(x: b) + yo (V } V5(z).
(193)
For state have that max(r" (r" (s, b) + 70 (p (V (V)) = max + (s) (s).
(194)
b
Thus we verified that V the fixed point of the robust Bellman operator of M and hence identical to the optimal robust value function M
Step 3. Define the set U _ { 1 S S N). The set U is then -nne of the interval [0, 1]. Since is clear that u* < there exists ug E U, such that [uo- u'1 N
On the other hand, for any u E U. since u S the optimal robust value function |V**|| S - Moreover, from the construction, the uncertainty set pesu independent of Pg. hence invoking Lemma impplesss
C1 R(1 -1-)) \ N(s, a) ming Pa 8.
log
|0 (V*.)) Jig (VaN))
(195)
with probability at least
- 8.
Step 4. We further show the following claim:
||Ve Va.a" 1| 1 To show 196). for s, we have that
(196)
N(1 - 7)
V (s) Valu" (s)
max (uo0 u²) + 7 (ppo Coc.ooooVVV.e (Va.u0) (ppenu (V ))
(b)
N ( Vo.a" (8)
1
+ +/|lV/m00 (s) - (s)ll,
(197)
N
where (a) is from max f max gl S max Iʃ -g), and (b) is from the fact that (ps.u) {1.) for any u and b.
And for state x * s, we have that
V (z) V.."" (x) max u0 (x, - p..u
(x. (x, (g (Vs,uo) -pprna (V'sa" ))
(a) 7 Vo,uo Vo.u" ||,
(198)
where (a) is from (pe.u) Tbb and y=.0 (0.00 (xx b) = 8.u (x, b) for any b E A and +
Hence together we proved 196.. which is identical to (240) of (6). The remaining proof hence follows exactly the same 36
42

---

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

---

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

---

Answer:
[No]
Justification: The code will be released the paper is accepted. The experiments are straightforward and easy reproduce.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run reproduce the results. See the NeurlPS code and data submission guidelines (https /nipss.cc/pulli//uuui guwde//ddee/ee/ wwt.:Suumisssispoooooooooooooooe
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We clearly specify all the details for the experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented the core the paper to level detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We plot error bar/envelop to indicate the statistical significance. For 10 independence experiments, we plot the mean and the standard deviation of them as the error bar.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
45

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative emrr rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [NA]
Justification:
No computing resources are required.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
We have reciewed the Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There is no potential societal impact that needs to specified.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
46

---

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

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
We do not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/mooell as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
48


Reviews:
[{"review_id": "Yakuhngvrz", "reviewer": "Reviewer_cT4V", "summary": "This paper studies offline reinforcement learning (RL) under model mismatch. The authors propose a unified distributionally robust optimization (DRO) framework that effectively tackles both the uncertainty from limited dataset coverage and the model mismatch between the training and deployment environments.", "questions": "na", "limitations": "The authors have discussed the limitations in Section 6.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "A Unified DRO Formulation: The authors provide unified results for robust Markov Decision Processes (MDPs) with several types of robust sets.\n\nThe authors have carefully designed the uncertainty set radius, incorporating both model mismatch and data sparsity factors. The tight theoretical guarantees provided for three widely studied uncertainty set models (total variation, χ2 divergence, and Kullback-Leibler divergence) demonstrate the robustness and versatility of their approach.\n\nThe authors present the first finite-sample analysis for the χ2 divergence uncertainty set in the offline reinforcement learning (RL) setting with model mismatch. This contribution advances our understanding of this particular model and its applications in robust RL.\n\nThe paper is well-structured, with a clear problem formulation, comprehensive algorithmic description, and rigorous theoretical analysis.", "weaknesses": "It would be beneficial if you could elaborate on the advantages of your work compared to [35] and [5], especially regarding sample complexity under KL and total variation settings. A more detailed comparison would help readers fully appreciate the advancements your method brings to the field.\n \nGiven that [5] presents another unified framework for offline distributionally robust RL, it would be interesting to know if your framework can be extended to the χ2 case. If this extension is not possible, highlighting this limitation could actually strengthen your paper by emphasizing the unique contributions of your approach.\n\nAddressing the computational efficiency of your proposed algorithm, particularly in comparison to [35], would be valuable. If your method is computationally efficient, including experimental results similar to those in [35] could provide empirical support for your theoretical findings.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the helpful and insightful feedback. In the following, we provide point-to-point responses to the weaknesses and questions. \n\n**Weakness 1. Advantages compared to [5] and [35].**\nIn summary, our method has three major advantages compared to both baselines. Firstly, our work is applicable under three different uncertainty set models, whereas [35] is limited to the KL model and [5] addresses only the KL and TV models (please see Weakness 2 for further discussion). Secondly, our algorithms achieve better sample complexity results compared to [5], and match the SOTA complexity under the KL model in [35] (please see discussion in Weakness 1-1). Finally, our algorithms demonstrate superior computational complexity compared to both baselines, and are the most efficient (please also see Weakness 3).\n\nThese improvements further strengthens our paper, highlighting our novelty and contributions.\n\n\n**Weakness 1-1. Comparison of sample complexity with [5] and [35].**\nWe refer to Table 1 on page 8 for a comparison of the sample complexity results between ours and the two baselines. A more detailed comparison is provided below.\n\nCompared with [5], our methods and results achieve better sample complexity in both KL and TV models. In the TV model, our sample complexity outperforms [5] in terms of dependence on $S$ and $(1-\\gamma)$; For the KL model, our complexity is linearly dependent on $S$, while [5] has a quadratic dependence. Furthermore, as noted in [5], their result's exponential term can be replaced by utilizing both $P_{\\min}$ and $\\mu_{\\min}$, while our (asymptotic) complexity result depends solely on $P_{\\min}$. \n\nOur results match exactly those of [35] in the KL model, indicating that we are achieving SOTA. Additionally, we provide results for two other models, which cannot be obtained directly using the algorithm in [35] (also see Weakness 2).\n\n\n\n\n**Weakness 2. Extension of baselines to other models.**\nAlthough extending the method in [5] may seem straightforward at first glance, the concrete extension requires additional effort. More importantly, the extended sample complexity result under the CS uncertainty set is also expected to be proportional to $S^2$, similar to the results under the other two models, whereas our method exhibits a linear dependence on $S$. This difference arises because the method in [5] is distribution-based, designing the first-level uncertainty set to cover the true nominal kernel, which results in worse complexity than ours (a more detailed discussion can be found in  [46]). \n\nIn [35], the LCB-based algorithm is only designed for the KL model and requires additional efforts to extend to other models. Specifically, a careful study of the optimal solution to the corresponding DRO problem is needed to design the penalty term, ensuring a pessimistic estimation of the robust value functions. In contrast, our method can be directly applied from a uniform framework under all three uncertainty sets.\n\n \n\n\n**Weakness 3. Computational complexity comparison.**\nOur algorithms enjoy better computational complexity than both baselines. \n\nThe two-layer optimization problem in [5] is an extension of the model studied in [41] to the robust setting, both involving non-rectangular uncertainty sets that are NP-hard to solve [49]. This creates uncertainty regarding the solvability of their models. Specifically, due to the unsolvability of the non-robust model in [41], an adversarial training-based algorithm is designed in [a] with only an experimental convergence guarantee, highlighting the implementation challenges of [5]. In contrast, our algorithm can be implemented with polynomial complexity. Specifically, the total computational complexity of our algorithm in the TV, CS and KL models is shown in [13] to be $\\mathcal{O}(S^2A\\log S)$,$\\mathcal{O}(S^2A\\log S)$, and $\\tilde{\\mathcal{O}}(S^2A)$. \n\nCompared to [35], our algorithms also offer better computational complexity. Specifically, the penalty term in [35] requires a complicated computation involving a minimum operator, resulting in an additional max-min structure in their algorithm update. The comparison/max-min operator in the LCB algorithm is executed $SA$ times per step, significantly increasing computational complexity. In contrast, our algorithms have a simple structure and do not require additional operators, making them more computationally efficient.\n\n\nTo illustrate our computational efficiency, we include numerical experiments in the rebuttal PDF. We implemented the LCB algorithm from [35] and our DRO algorithm under the KL model, monitoring the execution time of both methods while learning the same policy from the same dataset. We plotted the execution time for each dataset versus the size of the dataset in three environments: Gambler's game, Frozen Lake, and N-chain. As shown in Fig. 1, our algorithm consistently requires less execution time across all three environments, demonstrating lower computational complexity.\n\nTherefore, our methods exhibit superior computational complexity compared to both baselines.\n\n\n\n\n[a] Rigter, Marc, et al. \"Rambo-rl: Robust adversarial model-based offline reinforcement learning.\" Advances in neural information processing systems 35 (2022): 16082-16097.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "zcByn5sjxD", "reviewer": "Reviewer_TydZ", "summary": "The authors propose a unified principle of pessimism using distributionally robust Markov decision processes (MDPs) to handle both data sparsity and model mismatch. They construct a robust MDP with a single uncertainty set and demonstrate that the optimal robust policy achieves a near-optimal sub-optimality gap under the target environment across three uncertainty models: total variation, χ2 divergence, and KL divergence. The proposed approach improves or matches state-of-the-art performance under these models and provides the first result for the χ2 divergence model.", "questions": "To summarize the main points/questions raised in the weaknesses section:\n\n- Could the authors provide empirical results on more complex tasks to validate the effectiveness of their method?\n- Could the authors compare the computational costs of their method with other existing methods?", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is well-structured and clearly written, making it easy to follow the main arguments and methodologies.\n- The paper provides detailed theoretical analysis and guarantees, showing that the proposed method achieves near-optimal performance.\n- The proposed framework is versatile as well as easier to implement.", "weaknesses": "- While the theoretical guarantees are strong, the empirical validation could be more comprehensive. The experiments are conducted on relatively simple tasks (Frozen-Lake and Gambler problems). It would be beneficial to see results on more complex and diverse benchmarks.\n- Computational Cost: The paper claims that the proposed method has a lower computational cost compared to existing methods, but this claim is not empirically validated. A comparison of computational costs (e.g., runtime) with other methods would strengthen this claim.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the helpful and insightful feedback. In the following, we provide point-to-point responses to the weaknesses and questions. \n\n**Weakness 1. Experiment results on more complex and diverse benchmarks.**\nWe further provide two more experiments on large-scale environments in the rebuttal PDF. We implement our algorithm with the two baselines under the KL divergence uncertainty set. \n\nIn this rebuttal, we further add the results under the Garnet problem G(64,16) [a] in Fig 2(a), where there are 64 states and 16 actions. The transition kernels and reward functions are generated following some Gaussian distribution $\\mathcal{N}(\\mu_{s,a},\\sigma_{s,a})$. The comparison under the N-Chain problem is presented in Fig 2(b). And the results under the Cartpole problem are in Fig 2(c).  We also implement a model-free algorithm under the American Option problem in Fig 3, where no model estimation is required, indicating the potential of our method in solving large-scale problems. \n\n\nAs the results show, our method performs similarly to the LCB algorithm, aligning with our theoretical results. Moreover, our approach also shows a great improvement compared to the non-robust method, which verifies the robustness of our method. \n\n\n\n\nWe will include more experiments under different environments and uncertainty sets in the final version. \n\n\n\n\n\n**Weakness 2. Computational cost.** Our algorithms are better in terms of computational complexity or practical implementations than both baselines. \n\nThe two-layer optimization problem in [5] is an extension of the model studied in [41] to the robust setting, both involving non-rectangular uncertainty sets that are NP-hard to solve [49]. This creates uncertainty regarding the solvability of their models. Specifically, due to the unsolvability of the non-robust model in [41], an adversarial training-based algorithm is designed in [b] with only an experimental convergence guarantee, highlighting the implementation challenges of [5]. In contrast, our algorithm can be implemented with polynomial complexity. Specifically, the total computational complexity of our algorithm under the TV, CS, and KL models is shown in [13] to be $\\mathcal{O}(S^2A\\log S)$,$\\mathcal{O}(S^2A\\log S)$, and $\\tilde{\\mathcal{O}}(S^2A)$. \n\nCompared to [35], our algorithms also offer better computational complexity. Specifically, the penalty term in [35] requires a complicated computation involving a minimum operator, resulting in an additional max-min structure in their algorithm update. The comparison/max-min operator in the LCB algorithm is executed $SA$ times per step, significantly increasing computational complexity. In contrast, our algorithms have a simple structure and do not require additional operators, making them more computationally efficient.\n\n\nTo illustrate our computational efficiency, we include numerical experiments in the rebuttal PDF. We implemented the LCB algorithm from [35] and our DRO algorithm under the KL model, monitoring the execution time of both methods while learning the same policy from the same dataset. We plotted the execution time for each dataset versus the size of the dataset in three environments: Gambler's game, Frozen Lake, and N-chain. As shown in Fig. 1, our algorithm consistently requires less execution time across all three environments, demonstrating lower computational complexity.\n\nTherefore, our methods exhibit superior computational complexity compared to both baselines.\n\n\n[a] Archibald, T. W., et al. \"On the generation of markov decision processes.\" Journal of the Operational Research Society 46.3 (1995): 354-361.\n[b] Rigter, Marc, et al. \"Rambo-rl: Robust adversarial model-based offline reinforcement learning.\" Advances in neural information processing systems 35 (2022): 16082-16097.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "dFeB9ZEuTN", "reviewer": "Reviewer_3D3w", "summary": "This paper proposes an algorithm that tackles the offline RL task (for tabular state and action space) under two key challenges (i) the mismatch between the environment dynamics used to generate the dataset and the environment used to run the learned policy (for evaluation), and (ii) the bias in the data-collection procedure where for certain (s, a) pairs there are only a few samples in the dataset. In contrast to prior approaches that tackle the two problems separately, this paper proposes a unified solution to both problems under the distributionally robust MDP framework. \n\nIntuitively, distributionally robust MDP aims to learn a policy/value function with the best possible expected return given the worst possible environment dynamics in a set of distributions. Specifically, the set contains all distributions that are close (i.e., smaller than R) under some metrics (this paper considered total variation, chi-squared divergence, and KL divergence). This paper also takes into account the scarcity of data for certain (s, a) pairs by changing the fixed bound R to an adaptive bound R + K_{s}^{a}, where K_{s}^{a} depends on the visit count of (s, a) in the offline dataset. \n\nWith this new formulation, the authors derive high-probability lower bounds of the optimality of the learned value functions, under three divergences: total variation, chi-squared divergence, and KL divergence). The bounds appear to be tighter than that in prior work.", "questions": "Does the proposed method achieve better empirical performance on tabular environments compared to baselines?\n\nAre there potential ways to make the algorithm more practical?", "limitations": "The authors discussed certain limitations in Section 6.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper proposes a theoretically useful offline RL algorithm that can handle model misspecification errors and data scarcity in a unified perspective. Specifically, it turns the task into a canonical algorithm for distributionally robust MDP. This can significantly simplify the analysis and inspire future work to find better connections between the two challenges in offline RL.\n\nThe paper contains a thorough introduction and comparison with prior work, which makes it much easier to see the contributions of this paper.", "weaknesses": "One major weakness of the proposed algorithm is its practicality. The proposed algorithm relies on tabular state and action representations and involves solving robust Bellman equations which could be prohibitively hard in practice. Also, to compute certain statistics, we need to record the state-action visitation count, which is impractical in practice.\n\nIt would be nice if the author can demonstrate potential ways to apply the algorithm in practice. For example, can the algorithm be used together with function approximations?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the helpful and insightful feedback. In the following, we provide point-to-point responses to the weaknesses and questions. \n\n\n\n**Question 1. Empirical performance in tabular environments** We first refer the reviewer to Section A of the appendix, where we compare our algorithms with two baselines. Additional results for large environments are provided in the rebuttal PDF, Fig. 2. Our method outperforms the non-robust method and demonstrates performance similar to the LCB approach [35], consistent with our theoretical results. Furthermore, as shown in Fig. 1 of the rebuttal PDF, in the tabular setting, our algorithms have a lower execution time and computational complexity than the LCB baseline. Hence we claim that our algorithms perform better than the baselines under tabular environments. \n\nIt is also important to note that there is no practical implementation of the baseline [5] due to the NP-hardness of their models. Consequently, we did not include a comparison with [5] (please also see our response to Reviewer 2 Weakness 2).\n\n\n\n**Weakness \\& Q2. Extend to practical settings.** We want to emphasize that our major contribution is to develop a methodological framework for offline RL with model mismatch, which incorporates both uncertainties from the limited dataset and model mismatch as a **single** distributional uncertainty set and tackles them through a unified DRO framework. To better illustrate our novelty and technique contributions, we present our results in the tabular setting, where we show the sample complexity of our algorithms improves upon or matches the SOTA. \n\nHowever, our method can be easily extended to large-scale problems with function approximation. For example, in d-rectangular robust linear MDPs [26,5], the nominal transition kernel is the inner product of some d-dimensional feature functions $\\phi$ and a d-dim vector $\\theta$: $\\mathsf{P}^a_{s,s'}=\\phi(s,a)^\\top \\theta_{s'}$. The uncertainty set for the model mismatch is set as $\\mathcal{P}=\\\\{(\\phi(s,a)^\\top \\tau_{s'}): D(\\theta_i,\\tau_i)\\leq R, i\\leq d\\\\}$. Our method can be adapted to solve offline robust linear MDP problems. Specifically, after estimating the parameter $\\hat{\\theta}$ from the offline dataset as in [5], we can design a similar enlarged uncertainty set $\\tilde{\\mathcal{P}}=\\\\{(\\phi(s,a)^\\top \\tau_{s'})_{s,a,s'}: D(\\hat{\\theta}_i,\\tau_i)\\leq R+\\kappa_i \\\\}$, where $\\kappa_i$ is some enlarged term that accounts for the uncertainty of the dataset. Hence our method will result in a standard robust linear MDP formulation, which can be solved as in [26].\n\nOur method can be further extended to robust MDPs with latent structure or function approximation. Specifically, the nominal transition kernel can be represented or approximated by some parameter function $\\mathsf{P}\\approx f_\\theta$, and the robust MDP for the model mismatch will be set as $\\mathcal{P}=\\\\{ f_{\\theta'}: D(\\theta,\\theta')\\leq R\\\\}$. Similarly, after estimating the parameter $\\hat{\\theta}$ from the dataset and designing a dataset dependent term $\\kappa$, solving the enlarged robust MDP $\\mathcal{P}=\\\\{ f_{\\theta'}: D(\\hat{\\theta},\\theta')\\leq R+\\kappa\\\\}$ will result in a policy tackling both two sources of uncertainty. Also, it is worth mentioning that such a robust MDP can be solved empirically using adversarial training approaches, as in [a,b].\n\n\nAnother extension to make our method more practical is to design model-free algorithms for our DRO formulation. Unlike the model-based approach presented in our paper, model-free algorithms do not require the model estimation or solving the Bellman equation but can directly learn the optimal policy in an online bootstrapping fashion, making them more suitable for large-scale problems. Existing robust Q-learning algorithms, e.g., [c,d], can be directly adapted by setting the uncertainty set radius to $R+\\kappa$ and solving our formulation, which further makes our method more practical. \n\n\nTo verify that our method can also be extended to practical settings, we further implement a model-free robust Q-learning as described in [c] to solve the American Option environment ([c], [64]) in the offline setting. For each dataset, we ran the robust Q-learning algorithm with the uncertainty set constructed as described in our paper and plotted the robust value function of the learned policy. The results, presented in Fig. 3 of the rebuttal PDF, demonstrate that our method can be combined with model-free algorithms to effectively solve offline problems under model mismatch, particularly for large-scale problems. We will add more discussion in our paper.\n\n\n[a] Rigter, Marc, et al. \"Rambo-rl: Robust adversarial model-based offline reinforcement learning.\" Advances in neural information processing systems 35 (2022): 16082-16097.\n\n[b] Pinto, Lerrel, et al. \"Robust adversarial reinforcement learning.\" International conference on machine learning. PMLR, 2017.\n\n[c] Liang, Zhipeng, et al. \"Single-trajectory distributionally robust reinforcement learning.\" arXiv preprint arXiv:2301.11721 (2023).\n\n[d] Liu, Zijian, et al. \"Distributionally Robust $ Q $-Learning.\" International Conference on Machine Learning. PMLR, 2022.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank the three reviewers for the helpful and insightful feedback. Besides the point-to-point responses, we provide some additional numerical results in the PDF, and a few responses to address some common questions. 


**Compare with baselines [5], [35].**
Our method has three major advantages compared to both baselines.  **(1). Improved Sample Complexity.** Our algorithms achieve better sample complexity results compared to [5] (under TV and KL models), and match the SOTA complexity under the KL model in [35]. **(2). Higher Computational Efficiency.** Our method is more computationally efficient compared to both baselines. Specifically, the approach in [5] is NP-hard, whereas ours can be implemented in polynomial time. Additionally, due to the complexity of the penalty term design in [35], our algorithms demonstrate superior computational efficiency. We developed three numerical experiments to demonstrate this, as shown in Figure 1. **(3). Broader Applicability.** Our work is applicable under three different uncertainty set models, whereas [35] is limited to the KL model and [5] addresses only the KL and TV models. Extending their methods to other models requires additional effort.


**Experiments under more environments.** 
We conducted three experiments with larger problem scales: the Garnet problem with 64 states and 16 actions, the N-Chain problem, and CartPole. The results, shown in Figure 2, indicate that our DRO-based approach achieves the best performance.


**Extension to practical settings.**
Since our main contribution is to develop a universal methodology to unify the two sources of uncertainty in offline RL with model mismatch, we mainly focus on the tabular setting to highlight our algorithm design and theoretical results in our paper. However, our method and framework can be easily extended to large scale problems with function approximation or model-free algorithm design (please also see our response to R3 for a detailed discussion).  We also conducted an experiment on the American option problem under the offline setting with model mismatch. Our method can be directly combined with model-free robust Q-learning to develop a more efficient and practical algorithm. The results, shown in Figure 3, demonstrate that our robust Q-learning outperforms the non-robust baseline, highlighting the potential of our method in practical applications.

Meta-review: This paper has a solid algorithmic/theoretical contribution,
Decision: Accept (poster)