A Unified Principle of Pessimism for Offline Reinforcement Learning under Model Mismatch

Authors: yue  wang
zhongchang  sun
shaofeng  zou
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 04:29:18

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.

Main paper: 
 introduction: 
 Reinforcement learning (RL) [40] learns a 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 can be both costly and dangerous, rendering online learning impractical. To circumvent these challenges, the concept of offline RL has emerged [17, 18] , seeking to learn an optimal policy from a pre-collected dataset, eliminating the need for real-time interaction with the environment. 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, as exemplified by [41, 9, 52, 18] . However, in most RL scenarios, the data collection process can be expensive, constrained, and subject to specific behavior policies. This often results in a dataset with insufficient samples and limited coverage. The limited coverage of state-action pairs in the dataset presents a substantial hurdle, making it challenging to fully learn the environment model and the model learned may be inaccurate, leading to a poorly performing policy. and hindering the discovery of the optimal policy, particularly when 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 RL.The second critical challenge in offline RL pertains to its vulnerability to model mismatch. As the offline dataset is collected in advance, it 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 non-stationarity. This inherent variability 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 a 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-mismatch: This arises from distribution shifts between data-collection and deployment environments, as well as between data-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, 5, 24] , leading to methodological redundancy or complexity (more discussions and comparisons can be found in Section 5) . In this paper, we propose a unified framework that integrates both principles of pessimism into a 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.A unified distributionally robust formulation for offline RL under model mismatch. As discussed 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, χ 2 or Kullback-Leibler divergence. We then show that the uncertainty from data sparsity can be transformed into a 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 is 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 a meticulous analysis to 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, χ 2 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 metricbased and non-metric-based models. Moreover, our designs enable us to derive tight theoretical guarantees. Specifically, we improve upon existing results for robust offline RL under the total variation model [5] , match the state-of-the-art performance under the KL divergence model [36] , and present the first result under the χ 2 divergence model. 
preliminaries 2.1 markov decision process (mdp): 
 An MDP is specified by a tuple (S, A, P, r, γ), where S and A are the state and action spaces, respectively, P = {P a s ∈ ∆(S), s ∈ S, a ∈ A}1 is the transition kernel, r : S × A → [0, 1] denotes the reward function, and γ ∈ [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 a s = (p a s,s ′ ) s ′ ∈S , where p a s,s ′ denotes the probability of transiting from state s to state s ′ after taking action a. The reward of the transition when taking action a at state s is denoted by r(s, a).For a stationary policy π that maps from state s ∈ S to a distribution over action a ∈ A, it specifies the probability of the agent taking actions at each state. The value function of a policy π is defined asEQUATIONwhere E P denotes the expectation with respect to the distribution induced by the transition kernel P. Let ρ be the distribution of the initial state s, the value function under the distribution ρ is denoted by V π P (ρ) = E s∼ρ [V π P (s)]. Let d π P (s) and d π P (s, a) denote the state occupancy measure and state-action occupancy measure of policy π when the initial state s follows distribution ρ:d π P (s) = (1 -γ)∞ t=0 γ t P(s t = s|s 0 ∼ ρ, π, P), d π P (s, a) = d π P (s)π(a|s).A robust MDP is defined as (S, A, P, r, γ), where the transition kernel is not fixed but lies in some uncertainty set P. In this work we consider the (s, a)-rectangular uncertainty set:P = s,aP a s , P a s = {q ∈ ∆(S) : D(q, P a s ) ≤ R},where s,a means the uncertainty sets for every state-action pair are independently defined, P a s is 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 R 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 a worst-case performance can be characterized by the robust value function V π P (s):EQUATIONwhich is shown to be the unique solution to the robust Bellman equation [13] :EQUATIONwith σ P a s (V ) ≜ min q∈P a s q ⊤ V being the support function of a vector V on the uncertainty set P a s . Similar to the standard MDP setting, V π P (ρ) can also be defined w.r.t. the initial state distribution ρ. The goal here is then to find the optimal robust policy arg max π V π P (ρ). 
problem formulation: 
 In offline RL, the agent does not receive new samples by interacting with the environment. Instead, it is given a previously collected dataset D which consists ofN tuples {(s i , a i , s ′ i , r i ) : i = 1, • • • , N }.The dataset is generated according to some distribution µ, i.e., (s i , a i ) ∼ µ, and s ′ i ∼ P ai si follows the nominal transition kernel P, and r i = r(s i , a i ) is a deterministic reward function. As discussed, due to 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 captures such a 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 = s,a P a s , P a s = {q ∈ ∆(S) : D(q, P a s ) ≤ R}.(EQUATIONwhere R represents the similarities of the two environments. D and R are generally designed by domain experts, so we do not focus on their design and consider them as pre-settled in this work.A key challenge here is that the nominal transition kernel P 0 is unknown, but only an offline dataset generated from P 0 is given. Due to the limited exploration and distributional shift, the dataset D may not cover all possible states or transitions that the agent might encounter in the environment.To guarantee that a provable efficient algorithm can be designed based on the dataset D, we adopt an assumption on the distributional mismatch between the dataset distribution and the occupancy measure induced by a comparator policy π * . A comparator policy refers to a policy having satisfying worst-case performance and is set to be the optimal robust policy in many cases, but our approach can be applied to an arbitrary policy that may not be optimal. Assumption 1. (Robust single-policy clipped concentrability [36] ). The data distribution µ satisfiesEQUATIONIn Assumption 1, 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 1 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 1. 
framework design and main results: 
 To simultaneously address the two sources of uncertainty (1) uncertainty arising from the model mismatch 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 a 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 or matching results.Denote N (s, a) = N i=1 1 (si,ai)=(s,a) as the number of samples that transit from (s, a) in D, where 1 is the indicator function. The empirical transition kernel is then obtained asEQUATIONand we also define the empirical reward function asEQUATIONThe MDP M = (S, A, P, r) with the empirical transition kernel P and empirical reward function r is referred to as the empirical MDP, representing our estimation of the nominal model from the dataset. A straightforward approach is to construct an uncertainty set P by replacing the nominal kernel P in (5) by P:EQUATIONand solve the corresponding robust RL problem. Although it tackles the model mismatch uncertainty through the uncertainty set, it generally results in a sub-optimal performance due to the lack of consideration of the estimation error within the empirical model.To tackle this estimation error, previous works introduce some additional structures other than the above DRO framework (9) , including a penalty term in reward [36] or an additional uncertainty set and making it a bi-level DRO [5] (more discussions and comparisons can be found in Section 5).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 a unified principle of pessimism to address both uncertainties. Specifically, for any s ∈ S and a ∈ A, we setEQUATIONwhere κ a s is a function (will be specified later) inversely proportional to N (s, 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, κ a s becomes larger and we are less confident and more pessimistic when estimating the transition kernel Pa s , 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 a 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, 13] . Our algorithm is presented as Algorithm 1. 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 a tighter analysis of the sub-optimality gap. It is also worth noting that for all the uncertainty set models we consider, our Algorithm 1 can be efficiently applied with a polynomial computational complexity and a linear convergence rate [13] . In the following sections, we consider three widely used uncertainty set models: total variation, χ2 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 π obtained has a near-optimal performance under the target uncertainty set P, i.e., our approach effectively and efficiently solves the offline RL problems under model mismatch.We first consider the case of TV defined uncertainty set 2 . Specifically, the uncertainty set is constructed using D(q, p) = 1 2 ∥q -p∥ 1 in eq. (10) . Note that when the radius is greater than 2, the defined uncertainty set reduces to the whole probability simplex ∆(S). Our first attempt is to set κ a s 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 V π P , as a conservative estimation. We note that as long as the true nominal transition kernel P and the empirical transition kernel P are close: ∥P a s -Pa s ∥ ≤ κ a s holds with high probability, the triangle inequality implies P ⊆ 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. Then with probability at least 1 -2δ, the output policy π of algorithm 1 satisfies thatEQUATIONwhere Õ notation absorbs universal constants and log terms.Remark 1. To achieve an ϵ sub-optimality gap, a dataset of size N = Õ(S 2 C π * (1 -γ) -4 ϵ -2 ) is required. This result matches the previous one in [5] .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-based construction can result in an overly large uncertainty set and an overly pessimistic policy, as observed in [47, 19] . To improve, one observation is that we can design a smaller uncertainty set such that the resulting robust value function V π P approximately lower bounds the true robust value function, without using the distribution-based framework. We hence further design a novel uncertainty set that turns out to be less conservative (the intuition of such a design will be discussed in the next section).Theorem 2. For any (s, a), let κ a s = log SA δ N (s,a) . For the output policy π of algorithm 1, with probability at least 1 -4δ, it holds thatEQUATIONHere, µ min ≜ min s,a {µ(s, a) : µ(s, a) > 0} denotes the smallest non-zero entry of the distribution µ that generates the dataset. Remark 2. Combining the two results, we showed that our approach can obtain an ϵ-optimal robust policy when the dataset is of size Õ C π *(1-γ) 3 ϵ 2 min{ S 1-γ , 1 µmin } for the TV defined model. This result is better than the previous result in [5] , illustrating our approach is more efficient. Moreover, our framework is much simpler than the one in [5] and can be effectively solved in a polynomial time (see detailed discussion in Section 5).We then study the uncertainty models with the χ 2 divergence: D(p, q) = s q(s) 1 -p(s) q(s). Note that χ 2 divergence is not a metric, implying the failure of the triangle inequality and the distributionbased design as in the previous section. While it is possible to design κ such that D( Pa s , P a s ) ≤ κ a s [31] , it does not imply P a s ⊂ Pa s and no lower bound guarantee can be obtained. To address this issue, we similarly adapt the value function-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 to construct an uncertainty set that is large enough to include the true transition kernel with high probability. Then the sub-optimality gap can be decomposed asEQUATIONand ∆ 2 ≤ 0 from P a s ⊂ Pa s , which however fails under non-metric models. On the other hand, if we further decompose ∆ 2 asEQUATION)where P is the empirical uncertainty set (9) . We note that ∆ 22 is the concentration error due to the limited dataset, which is independent of the term κ a s (ignoring the dependence of π on κ for discussion connivance); ∆ 21 will be a negative term since P ⊂ P, thus we should set the term κ such that the negative bound on ∆ 21 cancels out with the concentration bound on ∆ 22 , leading to a non-zero yet tight overall bound on ∆ 2 . Instead of ensuring the uncertainty set inclusion, we directly ensure the bound on the value function difference ∆ 2 is small. Clearly, the clue function-based design can be applied to both non-metric and metric models, and is less conservative than the distribution-based for the metric models, since closeness in distribution is 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 in sample complexity.Based on this intuition, we present our radius design and results.Theorem 3. Consider χ 2 divergence-defined uncertainty set. For any (s, a), letκ a s = Õ 1+R N (s,a) . When N ≥ Õ S C π * µ 2 min, with probability at least 1 -4δ, the output policy π of algorithm 1 satisfiesEQUATION)Remark 3. To achieve an ϵ-optimal robust policy under the χ 2 model, our approach requires the total number of samplesN = Õ C π * S (1 -γ) 4 ϵ 2 ϵ-dependent + S C π * µ 2 min burn-in cost .Our sample complexity has two parts: the ϵ-dependent part which dominates as the accuracy ϵ decreases, and a fixed amount of burn-in cost, whose existence is because we cannot expect to learn a near-optimal policy when the dataset is too limited. When the desired accuracy ϵ decreases, the first term dominates the overall complexity, resulting in the asymptotic result presented in the theorem.Our approach and result stand for the first concrete study for offline robust RL with χ 2 divergencedefined uncertainty sets. It is also worth noting that our sample complexity asymptotically matches the sample complexity of the model-based robust RL with a generative model [38] . These observations hence demonstrate the optimality of our results and the effectiveness of our approach.In this section, we consider the KL divergence defined uncertainty set, i.e., D(p, q) = s p(s) log p(s) q(s) . Similarly, KL divergence is not a metric, we hence adapt our design discussed above for χ 2 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, a), let κ a s =C 1 log 2(1+R)N 3 S (1-γ)δ N (s,a) Pmin , if N ≥ 8 log 1 δµminPmin , then with probability at least 1 -4δ, the output policy π of algorithm 1 satisfiesEQUATION)Here, P min and Pmin 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 a total number of ÕC π * S (1-γ) 4 Pminϵ 2 + 1 Pminµminsamples to find an ϵ-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 a more efficient 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 a smaller or similar sample complexity compared to LCB approaches, and always outperform the non-robust dynamic programming approach.5 Related Works 
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: (1) . 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 a reward penalty term b is used to penalize less visited state-action pairs in addition to the uncertainty set that accounts for the model mismatch, and the update rule isEQUATION)Our approach, on the other hand, enjoys a straightforward and simple formulation. Specifically, we incorporate the two principles of pessimism into a single uncertainty set, developing our unified principle. Moreover, it is noted that design of the penalty term b is complicated, whereas our addition term κ has a 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 b is designed such that the resulting estimation V is less than the true robust value function V π P , to ensure the conservativeness of LCB approaches; Whereas our resulting estimation V π P is not necessarily less than V π P , since we directly tackle the distribution uncertainty but not through value function estimations. This hence requires novel technique innovations in our analysis.In another closely related work [5] , a 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 P is first constructed to tackle the model estimation uncertainty from the dataset; Then centered at each transition kernel P ∈ P, a second layer of uncertainty set Φ( P) to reflect the distributional robustness to model mismatch. They then take the optimal policy ofEQUATION)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 a single uncertainty set with a composed design of the radius to address both the model estimation uncertainty and the model mismatch.Improved or Matched Sample Complexity. In terms of sample complexity, the comparison are included in Table 1 . 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 not 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 in both KL and TV models. In the TV model, our sample complexity outperforms [5] in terms of dependence on S and (1 -γ); 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 µ min , while our (asymptotic) complexity result depends solely on P min .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 [5] is an extension of the model studied in [42] to the robust setting, both involving non-rectangular uncertainty sets that are NP-hard to solve [50] . This creates TV DISTANCEχ 2 DIVERGENCE KL DIVERGENCE [36] × × Õ C π * S (1-γ) 4 ϵ 2 P min [5] Õ C π * rob S 2 (1-γ) 4 ϵ 2 × Õ C π * rob S 2 exp((1-γ) -1 ) (1-γ) 4 ϵ 2 OUR WORK Õ C π * S (1-γ) 3 ϵ 2 min{ S 1-γ , 1 µ min } Õ C π * S (1-γ) 4 ϵ 2 Õ C π * S (1-γ) 4 ϵ 2 P minTable 1 : Comparison with related works on offline RL under model mismatch. In [5] , C π * rob is the robust partial coverage coefficient [5] , which is similar to C π * , and the exp((1 -γ) -1 ) term can be eliminated with an additional cost on P -1 min and µ -1 min .uncertainty regarding the solvability of their models. Specifically, due to the unsolvability of the non-robust model in [42] , an adversarial training-based 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 are O(S 2 A log S),O(S 2 A log S), and Õ(S 2 A).Compared to [36] , our algorithms also offer better computational complexity. Specifically, the penalty term in [36] 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. We also use numerical experiment to further illustrate our enhanced computational efficiency, in Appendix A.We then discuss some of the other related works.Offline RL without model mismatch. Offline RL focuses on learning an optimal policy from a pre-collected dataset, and the target deployment environment is identical to the one where the dataset is 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, 58, 59, 14, 45, 20, 21, 64, 41, 9, 52, 18, 2, 10] . This assumption is too restrictive and is often violated in practice since it requires the history data to cover all the state-action pairs [12, 1, 11] . Recently, a relaxed partial coverage setting was 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 no 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, e.g., [15, 42, 51, 53, 33, 62, 60, 37, 19, 63, 47] . However in our setting, we 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.Robust RL. Robust RL [13, 28, 54] aims to tackle the model mismatch in RL, by optimizing the worst-case performance over the uncertainty set. Existing works mainly focus on the online setting [48, 49, 46, 4, 8, 25, 23] or with a generative model [57, 55, 29, 38] . Studies for robust RL with an offline dataset, besides the two mentioned above [36, 5] , are developed in recent works including [24, 44, 65, 30, 56, 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, we focus on general MDPs and develop our unified framework. 
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 of uncertainty are presented: inaccurate estimation of transition dynamics due to limited dataset coverage, and model mismatch between training and testing environments. We developed a unified DRO-based framework containing a single uncertainty set with a composed radius of two parts to tackle the two sources of uncertainty discussed above. Our approach can be implemented in a much easier and more straightforward way than existing approaches and can be applied to both metric-based and non-metric-based uncertainty models. Specifically, we investigated three types of uncertainty sets defined by total variation, χ 2 divergence, and KL divergence. Our methodology can be easily extended to handle other uncertainty set models. Among them, we 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 χ 2 divergence.Limitations. It is 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 LCB + DRO framework, for example [24, 44] , and more general MDPs with function approximation techniques. 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: The paper poses no such risks.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a 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 to 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 a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [NA] Justification: We do not use any existing assets.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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. 
 
 Appendix: In this section, we provide simulation results to demonstrate the performance of our algorithm. We consider two problems: the Frozen-Lake problem [6] and the gambler problem [40, 65, 36] .For the Frozen-Lake problem, an agent aims to cross a 4 × 4 frozen lake from Start to Goal without falling into any Holes. The reward is set to be 1 when the agent reaches Goal and 0 otherwise. Due to the slippery nature of the frozen lake, the agent may not always move along the intended direction.We formulate the gambler problem as an infinite-horizon MDP. A gambler engages in a betting game based on a sequence of coin flips. The gambler wins the stake when the coin lands on heads and loses it 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 balance either reaches 20 or 0. The reward is set to be 1 when the state reaches 20 and 0 otherwise.We first evaluate our algorithm under the total variation uncertainty set. We adapt the construction in [36] to design an DRVI-LCB approach for the TV defined uncertainty set as a 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 µ(s, a) =1 a=π * (s) 2 + 1a=η 2where η is a random action, and π * (s) denotes the optimal robust policy. Clearly the dataset satisfies the partial coverage assumption 1.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 as the envelop. It can be seen from Fig. 1 and Fig. 2 that the value function-based construction has a smaller sub-optimality gap and converges faster than the distribution-based construction and the DRVI-LCB, which demonstrates that our algorithm is less conservative and more effective. We then compare our algorithm with the DRVI-LCB under the χ 2 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 a similar convergence rate to the DRVI-LCB to the optimal policy, which validates our theoretical results. 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. 5 and Fig. 6 that the non-robust DP converges much slower to the optimal policy, whereas our approach has a similar convergence rate to the DRVI-LCB to the optimal policy, which validates our theoretical results. 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. 4 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 a similar performance and convergence rate, further demonstrating the effectiveness and efficiency of our approach.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 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 Appendix A.4, our algorithm consistently requires less execution time across all three environments, demonstrating lower computational complexity. Then with probability at least 1 -δ, P a s ⊆ Pa s .We then present the sub-optimality gap in the following theorem.Proof. For the (s, a) pairs with N (s, a) = 0, the statement is trivial due to the fact that Pa s = ∆(S). It is hence sufficient to consider the pairs with N (s, a) > 0.By directly applying the Hoeffding's inequality [22] , we have that for each pair (s, a, x),EQUATION)It hence can be further shown thatEQUATIONsimultaneously for any (s, a)-pair with probability at least 1 -δ. Now consider any q ∈ P a s , it holds that ∥q -P a s ∥ ≤ R. HenceEQUATIONwhich implies that P a s ⊆ Pa s for any (s, a) with probability at least 1 -δ. Theorem 5. For the output policy π of algorithm 1, with probability at least 1 -2δ, it holds thatEQUATIONProof. First note thatEQUATIONDue to the fact that P a s ⊆ Pa s with probability 1 -δ, it holds thatEQUATIONand henceEQUATIONIt can be further bounded asEQUATIONwhere (a) is from π = arg max π V π P , and the last inequality is from the fact P Ṽ ∈ P * s and hence σ * s (V π * P ) ≤ (P Ṽ ) * s V π * P . Applying the inequality above recursively impliesEQUATIONNote thatEQUATIONwhere the last inequality is fromEQUATIONwhere (a) is from the dual form of σ P (V ) and(b) is from the fact that | max x F (x) -max x G(x)| ≤ max x |F (x) -G(x)|.From the definition of κ a s =S log SA δ 2N (s,a) , it holds that κ * s = S log SA δ 2N (s,π * (s)) ≤ 8S log 4SA δ log SA δ 2N µ(s,π * (s))and henceEQUATION)To further bound (28) , we first note thatEQUATIONwhich is from the dual form of σ P (V ), i.e.,EQUATIONand [V ] λ (s) = min{V (s), λ}. We then involve (20) , and it holds thatEQUATION)Plugging this inequality to (27) and from the definition of C π * , we have thatEQUATIONwhich completes the proof.Theorem 6. For the output policy π of algorithm 1, with probability at least 1 -4δ, it holds thatEQUATION)Proof. Note that Lemma 8 of [36] states that with probability 1 -δ, for any (s, a) pair,EQUATIONWe hence conduct our proof under the occurrence of this event. Note that for any s,EQUATIONFrom Lemma 2 and Lemma 3, the above bound can be bounded asEQUATIONwhich completes the proof.Lemma 2. (Bound on Term A) With probability at least 1 -2δ, it holds thatEQUATIONProof. To bound term (A), note thatEQUATIONwhere (a) is from π = arg max π V π P , and the last inequality is from the fact P Ṽ ∈ P * s and hence σ * s (V π * P ) ≤ (P Ṽ ) * s V π * P . Applying (40) recursively impliesEQUATIONNote thatEQUATIONwhere the last inequality is fromEQUATIONwhere (a) is from the dual form of σ P (V ) and (b) is from the fact that | maxx F (x) -max x G(x)| ≤ max x |F (x) -G(x)|.Since N (s, a) ≥ N µ(s,a)8 log 4SA δ, from Assumption 1, we have thatEQUATION)From the definition ofEQUATIONTo further bound (42) , we first note thatEQUATIONwhich is from the dual form of σ P (V ), i.e.,EQUATIONand [V ] λ (s) = min{V (s), λ}. We then utilize Lemma 15 and (44) , and it holds that1 1 -γ s,a d * P Ṽ (s, a)|σ * s (V π P ) -σ * s (V π P )| ≤ 1 1 -γ s,a d * P Ṽ (s, a) max 0≤λ≤ 1 1-γ |P a s [V π P ] λ -Pa s [V π P ] λ | ≤ 1 1 -γ s,a d * P Ṽ (s, a)   K 1 (1 -γ)N (s, a) + K 2 Var P a s (V π P ) N (s, a)   ≤ 1 1 -γ s,a d * P Ṽ (s, a)   8K 1 C π * log 4SA δ (1 -γ)N S + 1 d * P Ṽ (s, a) + K 2 Var P a s (V π P ) N   ≤ 16K 1 C π * S log 4SA δ N (1 -γ) 2 + K 2 1 -γ s,a d * P Ṽ (s, a) Var P a s (V π P ) N (s, a) ≤ 16K 1 C π * S log 4SA δ N (1 -γ) 2 + K 2 1 -γ s,a d * P Ṽ (s, a)EQUATION)We then bound the two terms as follows.We first claim the following inequality:EQUATIONTo prove (49) , we note thatEQUATIONand hence for any s ∈ S,EQUATIONwhich proves (49) .Now with (49) , we first note thatEQUATIONwhere the last inequality is due to the fact ∥V π P + γP * Ṽ V π P ∥ ≤ 2 1-γ and (49). We first have thatEQUATIONwhere (a) is from ( 52), (b) is due to γ < 1, (c) is from the definition of visitation distribution. Var (P Ṽ ) a s (V π P ) N (s, a) ≤ s,a d * P Ṽ (s, a) 8C π * S + 1 d * P Ṽ (s,a) log 4SA δ Var (P Ṽ ) a s (V π P ) N = 8C π * log 4SA δ N s,a d * P Ṽ (s, a) S + 1 d * P Ṽ (s, a)EQUATIONwhere the first inequality is from (44) and the last inequality follows similarly as (42) .Hence, Term A 1 can be bounded asEQUATION)Bound on Term A 2From Lemma 10, it is straightforward to see that for any transition kernel q a s ∈ P a s ,EQUATIONHence s,aEQUATIONThus Term A 2 can be bounded asEQUATIONCombine the bounds we obtained for terms A 1 and A 2 in ( 55) and ( 58), we have thatEQUATIONwhich further implies thatEQUATIONThen, combine (41), ( 42) and the inequality above, we have thatEQUATIONwhich completes the proof.Lemma 3. (Bound on Term B) If N ≥ 196c1 log 4SAN δ log 4SA δ (1-γ) 2 N µmin, then with probability at least 1 -2δ, it holds thatEQUATION)Proof. From the robust Bellman equation, it holds thatEQUATIONwhere (P V ) (P V ) π(s) s ∈ P π * (s) s and (P Ṽ ) π(s) s V π P = σ P π(s) s (V π P ) ≤ (P V ) π(s) s V π P .On the other hand,EQUATIONwhere (a) is from the fact that P Ṽ ∈ P and hence σ π s (V π P ) ≤ (P Ṽ )π(s) s V π P .Hence we have thatEQUATION)We then bound terms (I) and (II). Note that the only difference between the two terms are the visitation distributions, i.e, d π P V and d π P Ṽ .We first note thatEQUATION)hence it is sufficient to bound B 1 , B 2 .To bound B 1 , note thatEQUATION)where (a) is from the dual form of the support function [13] and the last inequality is because Span(V ) ≤ 1 1-γ for any 0 ≤ V ≤ 1 1-γ . We then bound B 2 . Similarly from the dual form, it holds thatEQUATION)We then apply Lemma 15, it holds thatEQUATIONwith probability at least 1 -δ andK 1 = 2 + c 2 log 4SAN 2 δ + 2c 1 log 4SAN 2 δ .Note that for any s, a,EQUATIONFirstly, Lemma 7 of [38] and Lemma 10 imply thatEQUATION)To boundEQUATION)And the last term can be bounded as|Var P a s (V π P ) -Var (P V ) a s (V π P )| ≤ 2 γ 2 max{R, 1 -γ} (74)using ( 56), and henceEQUATION)Hence by combining ( 72),( 73) and (75) we have thatx d π P V (x) Var P π(s) s (V π P ) N (s, π(s)) ≤ x d π P V (x) 8 log 4SA δ Var P π(s) s (V π P ) N µ min ≤ 8 log 4SA δ N µ min ∥V π P -V π P ∥ + (8 + √ 8) 1 max{R, 1 -γ} (76)Thus plug the inequality above and the bound of B 1 in (63), we have thatI ≤ γ 1 -γ x d π P V (x)(σ π s (V π P ) -(P Ṽ ) π(s) s V π P ) ≤ 16c 1 log 4SAN δ log 4SA δ N µ min (1 -γ) 2 ∥V π P -V π P ∥ + (8 + √ 8) 1 max{R, 1 -γ} + 4K 1 log 4SA δ N µ min (1 -γ) 2 + 8 log 4SA δ (1 -γ) 2 N µ min (77)Similarly to the analysis in bounding the Term (I), we have thatEQUATIONwhere B 1 can be bounded asEQUATION)The bound on B 2 similarly follows as in Term (I). Note thatEQUATIONwith probability at least 1 -δ andK 1 = 2 + c 2 log 4SAN 2 δ + 2c 1 log 4SAN 2 δ .Note that for any s, a,EQUATIONHenceEQUATIONSimilarly, Lemma 13 of [38] and Lemma 10 imply thatEQUATION)And to bound Var P a s (V π P ) -Var (P Ṽ ) a s (V π P ), note that|Var P a s (V π P ) -Var (P Ṽ ) a s (V π P )| ≤ 2 γ 2 max{R, 1 -γ} (84)from ( 56), and henceEQUATION)Hence by combining ( 83) and (85) we have that s d π P Ṽ (s)Var P π(s) s (V π P ) N (s, π(s)) ≤ s d π P Ṽ (s) 8 log 4SA δ Var P π(s) s (V π P ) N µ min ≤ 8 log 4SA δ N µ min (8 + √ 8) 1 max{R, 1 -γ} (86)Thus plug the inequality above and the bound of B 1 , we have thatII ≤ γ 1 -γ s d π P V (s)(σ π s (V π P ) -(P Ṽ ) π(s) s V π P ) ≤ 16c 1 log 4SAN δ log 4SA δ N µ min (1 -γ) 2 (8 + √ 8) 1 max{R, 1 -γ} + 4K 1 log 4SA δ N µ min (1 -γ) 2 + 8 log 4SA δ (1 -γ) 2 N µ min (87)Then we combine the bounds of terms (I) and (II) together, and we have thatEQUATION)and hence completes the proof.C Proofs of Section 4.2Theorem 7. With probability at least 1 -4δ, the output policy π of algorithm 1 satisfiesEQUATION)Proof. Using the similar decomposition implies thatEQUATION)The proof is then completed by combing the following two lemmas.T Lemma 4. (Bound on Term A) With probability at least 1 -4δ, it holds thatEQUATIONProof. To bound term (A), note thatEQUATIONwhere (a) is from π = arg max π V π P , and the last inequality is from the fact P Ṽ ∈ P * s and hence σ * s (V π * P ) ≤ (P Ṽ ) * s V π * P . Applying (93) recursively impliesEQUATIONNote thatEQUATIONThe first term in (95) can be bounded as follows. Recall the dual form of the support function w.r.t. the uncertainty set P = {q ∈ ∆(S) : χ 2 (q||p) ≤ R} as follows:EQUATIONwhere V α (s) = min{V (s), α}.Applying the dual form further implies thatEQUATIONwhere the last inequality directly follows from the Hoeffding's inequality [38] and 1 N -net technique used in Lemma 15.As for the second term in (97), we utilize Lemma 7 and the technique of ϵ-net, which implies thatEQUATION)This hence bounds the first term in (95). For the second term in (95), similarly apply the dual form and we have thatEQUATIONwhere the last inequality is from the fact that Var(V α ) ≤ 1 (1-γ) 2 for any V ≤ 1 1-γ and any α ≤ 1 1-γ . We now plug (98) and (99) to (95) and (94), and we have thatEQUATIONwhere the last inequality is from (44) . This hence completes the proof.Lemma 5. (Bound on Term B) With probability at least 1 -4δ, it holds thatEQUATIONProof. Similarly to the proof of Lemma 4, note thatEQUATIONwhere ( PV )π(s) s = arg min q∈ Pπ(s) s qV π P .We then bound the term σπ(s)EQUATIONwhich completes the proof. Lemma 6. With probability at least 1 -δ, it holds that for any s ∈ S,EQUATIONProof. We first consider a vector V that is independent from P.σπ(s)EQUATIONwhereα * ≜ arg max α { Pπ(s) s (V α ) -(R + κ π(s) s)Var Pπ(s) s (V α )}, and the last inequality is from the fact that -max f ≤ -f (x) for any x.We then construct an ϵ 1 -net over [0, 1 1-γ ], such that there exists β with ∥V α * -V β ∥ ≤ ϵ 1 . Then we further have that σπ(s)EQUATIONwhere we use the Bernstein inequality and the technique of ϵ 1 -net. To bound the last two terms, we note thatEQUATIONwhere we again use the ϵ 1 -net technique in (a), and apply Lemma 7 in (b). Combining ( 106) and (107) implies that σπ(s)EQUATIONClearly, if we setEQUATIONthen c2 N (s,π(s)) + RC1 N (s,π(s)) + √ R -R + κ π(s) s≤ 0, and henceEQUATIONby setting ϵ 1 ≤ Õ( 1 N ). Now to show the claim for V π P , we construct an ϵ 2 -net over [0, 1 1-γ ] S . By applying the similar trick, we complete the proof. Lemma 7. For any vector V ∈ [0, 1 1-γ ] that is independent with P, with probability at least 1 -δ, it holds thatEQUATIONProof. This result can be derived from the Bernstein inequality for U -statistics [3, 32] , by noting that the sample standard deviationEQUATIOND Proofs of Section 4.3Theorem 8. If N ≥ 8 log 1 δµmin , then there exists some universal constants C 1 , C 2 , such that with probability at least 1 -4δ, it holds thatEQUATION)Proof. Note thatEQUATIONThe proof completes by combining the bounds on the two terms, shown in the following two lemmas.Lemma 8. There exists a constant C 2 , such that with probability at least 1 -δ, it holds thatEQUATIONProof. From the definition,EQUATIONhenceEQUATIONwhere q a s is the worst-case transition kernel of V π P in P a s , and (a) is from σ P π * s (V π * P ) -σ P π * s (V π P ) = σ P π * s (V π * P ) -(q π * s )(V π P ) ≤ (q π * s )(VEQUATIONWe moreover rewrite c as c(s)EQUATIONMoreover, we introduce two sets S 1 = {s : maxEQUATIONEQUATIONFor s ∈ S 1 , (216) of [36] implies that d π * q (s) = 0. We then focus on s ∈ S 2 . It has been shown in [36] that µ(s, π * (s)) > 0 and N (s, π * (s))≥ N min{ 1 S ,d π * q (s)} 12C π * .Thus Lemma 17 first implies thatEQUATIONTo bound ∆ 1,2 , note thatEQUATION)where (a) is from the dual solution of KL-divergence, and (b) is due to the fact that the optimal solutions to both dual forms satisfy λ * ≤ 1 (1-γ)(R+κ π * (s) s ) [65] , and (c) is due to max f -max g ≤ max |f -g|.Then we plug in the definition of κπ * (s) s = C 1 log 2(1+R)N 3 S (1-γ)δ N (s,π * (s)) minx Pπ * s,xand using (202) of [36] , we have thatEQUATIONCombine ( 122) and (124), we have thatEQUATION)Thus we have thatEQUATIONwhere (a) is from Cauchy inequality, and (b) is from (220) of [36] , which hence completes the proof.We then bound the term ∆ 2 . Lemma 9.EQUATION)Proof. First, note thatEQUATIONwhere q π s is the worst-case transition kernel of V π P in P π s , and b(sEQUATIONWe further introduce two sets as follows.S 1 = {s : µ(s, π(s)) = 0}, (130) S 2 = {s : µ(s, π(s)) > 0}.(131)EQUATIONFor s ∈ S 2 , we have thatEQUATIONHence invoke Lemma 17, we have that for s ∈ S 2 , with probability at least 1 -δ,EQUATION)To further bound the RHS of (134), we first note that Lemma 8 of [36] states that if N µ(s, a) ≥ 8 log 1 δ , then with probability 1 -δ, for any (s, a) pair,EQUATION)This moreover implies that with probability 1 -δ, for s ∈ S 2 ,EQUATION)On the other hand, (202) of [36] states that with probability at least 1 -δ,EQUATIONHence by plugging ( 136) and ( 137) in (134) we have thatEQUATIONOn the other hand, similarly to (123), it holds thatEQUATIONwhere the last inequality is from the fact that max F -max G ≥ F (x) -G(x), ∀x.Combining with(134) further implies thatEQUATIONby combining (138) and (139). ThusEQUATIONHence combine with (129) and (132), we further have thatρ ⊤ ∆ 2 ≤ 4 N R(1 -γ) 2 .(142)Lemma 10. It holds thatEQUATIONProof. Note that when N > EQUATIONDenote s * = arg min s V π P (s). Then it holds thatEQUATIONWe denote the optimal action π(s) by a in the following proof. Note that there exists a vector q a s ∈ R S , such that Pa s ≥ q a s ≥ 0, and s ′ q a s (s ′ ) = 1 -R -κ a s . This is doable because s ′ Pa s (s ′ ) = 1 and R + κ a s ≤ 1. Hence it implies that the transition kernel q a s + (R + κ a s )1 s * ∈ Pa s , sinceEQUATIONwhere the last equation is from s ′ q a s (s ′ ) = 1 -R -κ a s and ∥V π P ∥ = max s V π P = V π P (s * ). Plug this inequality in (145), and it holds thatEQUATIONThusEQUATIONwhich implies thatEQUATION)Lemma 11. Recall the set S 0 ≜ {s ∈ S : N (s) = 0}. Then (1). For any policy π and s ∈ S 0 , V π P (s) = 0; (2). There exists a deterministic robust optimal policy π, such that for any s / ∈ S 0 , N (s, π(s)) > 0.where Pb s is a modified uncertainty set defined asEQUATIONEQUATIONNow we have thatEQUATIONwhich further implies V f s b (π) Pb s (s) = 0. Note that in eq. ( 152), we have shownV π P (s) = 0, hence V f s b (π) Pb s (s) = V π P (s) = 0. Now consider the two robust Bellman operator T s b V (x) = a f s b (π)(a|x)(r(x, a) + γσ ( Pb s ) a x (V ))and TV (x) = r(x, π(x)) + γσ Pπ(x) x (V ). It is known that V f s b (π) PbEQUATIONwhere(a) is from f s b (π)(x) = π(x) when x ̸ = s, (b) is from ( Pb s ) π(x) x = Pπ(x) x .And for s, it holds thatEQUATIONwhere eq. ( 160) and eq. ( 161) further imply that V π P is also a fixed point of T s b . Hence it must be identical to Vf s b (π) Pb s , i.e., V f s b (π) Pb s = V π P .Combine with eq. ( 156), we haveEQUATIONwhich implies that f s b (π) is also optimal with N (s,f s b (π)(s)) = N (s, b) > 0. And since f s b (π)(x) = π(x) for x ̸ = s, then N (x, f s b (π)(x)) = N (x, π(x)). This thus completes the proof.Lemma 13 (Lemma 4, [19] ). For any δ, with probability 1 -δ, max{12N (s, a), 8 log N S δ } ≥ N µ(s, a), ∀s, a. Lemma 14 (Lemma 9, [19] ). For any (s, a) pair with N (s, a) > 0, if V is an vector independent of Pa s obeying ∥V ∥ ≤ 1 1-γ , then with probability at least 1 -δ,EQUATIONEQUATION)Lemma 15. For the total variation uncertain set and for any fixed s, a and δ, with probability at least 1 -δ, it holds thatEQUATIONandEQUATIONProof.Step 1: Construct an auxiliary robust MDP. For the state s ∈ S and any constant u ∈ [0, 1], we construct the following MDP M s,u = (S, A, r s,u , P s,u ) with transition kernel P s,u and reward r s,u :EQUATIONEQUATIONandEQUATIONCentered at M s,u , we further construct the following robust MDP M s,u = (S, A, Ps,u , r s,u ):EQUATIONThe robust Bellman operator associated with this robust MDP is henceEQUATIONand we denote the robust value function w.r.t. it by V s,u .Step 2: Prove V π P is a robust value function w.r.t. M s,u * for some u* ∈ [0, 1]. We claim that if we set u * = (1 -γ)V π P (s) ∈ [0, 1], then the robust value function w.r.t. M s,u * is equal to V π P .To prove the claim, recall that V π P is the unique fixed point of the optimal robust Bellman operator TV (x) = max a {r(x, a) + γσ ( P) a x (V )}.(175) For the state s, note that Ts,uEQUATIONwhich is due to the construction of M s,u * ; And for states x ̸ = s, we have thatEQUATIONwhich is from the construction of M s,u * and the fact that V π P is the fixed point of T.These two equations hence imply that V π P is a fixed point of the robust Bellman operator T s,u * , which further proves the claim.Step 3: Decouple the dependence of V π P on P by constructing an 1 N -net. [43] of the interval [0, 1], i.e., for any u ∈ [0, 1], there exists u i ∈ U, such that |u -u i | ≤ 1 N . Clearly, each u ∈ U is a constant independent with Pa s , hence applying Lemma 14 implies that for any u ∈ U,Define U = { i N : i = 0, 1, ..., N }. Clearly, U is a 1 N -netEQUATIONTake the union bound over any (s, a, u) ∈ S × A × U, and we have the following inequality holds with probability at least 1 -δ:EQUATION)Step 4: Approximate |P a s V π P -Pa s V π P | using the 1 N -net. As we showed above, there exists u ∈ U such that |u -u * | ≤ 1 N . Moreover, note thatEQUATIONwhere the last inequality is from σ ( Ps,u ) a x (V s,u * ) = σ ( Ps,u * ) a s (V s,u * ) for any x, a. Hence we have thatEQUATIONWe further have that|P a s V π P -Pa s V π P | ≤ |P a s V s,u -Pa s V s,u | + |(P a s -Pa s )(V s,u -V s,u * )| ≤ 2 (1 -γ)N + c 2 log( 4SAN 2 δ ) (1 -γ)N (s, a) + c 1 log( 4SAN 2 δ )Var P a s (V s,u ) N (s, a) = 2 (1 -γ)N + c 2 log( 4SAN 2 δ ) (1 -γ)N (s, a) + c 1 log( 4SAN 2 δ )(Var P a s (V s,u * ) + (Var P a s (V s,u ) -Var P a s (V s,u * ))) N (s, a) ≤ 2 (1 -γ)N + c 2 log( 4SAN 2 δ ) (1 -γ)N (s, a) + c 1 log( 4SAN 2 δ )Var P a s (V s,u * ) N (s, a) + c 1 log( 4SAN 2 δ )|Var P a s (V s,u ) -Var P a s (V s,u * )| N (s, a) ≤ 2 (1 -γ)N + c 2 log( 4SAN 2 δ ) (1 -γ)N (s, a) + c 1 log( 4SAN 2 δ)Var P a s (V s,u * ) N (s, a)EQUATION)where the last inequality is fromEQUATION)Thus (182) can be further bounded as |P a s V π P -Pa s V π P | ≤ 2 (1 -γ)N + c 2 log(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, a) satisfying N (s, a) > 0, and any vector V ∈ R |S| independent of Pa s obeying ∥V ∥ ≤ 1 1-γ , with probability at least 1 -δ, it holds that Step 1. We first construct a robust MDP with state-absorbing empirical nominal transition kernels. More specifically, for each state s and a constant u ≥ 0, define the following transition kernels for any a ∈ A, x ∈ S:|σ P a s (V ) -σ Pa s (V )| ≤ C 1 R(1 -γ)EQUATION(P s,u ) a s,x = Pa s,x , if x ̸ = s.(188) Moreover, define the modified reward function: r s,u (s, a) = u, (189) r s,u (x, a) = r(x, a), if x ̸ = s.(190) We then define the following uncertainty set (P s,u ) ax for any a ∈ A, x ∈ S as follows: (P s,u ) a s = {1 s }, (191) (P s,u ) a x = {q ∈ ∆(S) : D(q||(P s,u ) a x ) ≤ R + κ a x }, if x ̸ = s.(192) The auxiliary robust MDP is then defined as M s,u = (P s,u = s,a (P s,u ) a s , r s,u ).Step 2. We next show that if we set u * = (1 -γ)V π P (s), then the optimal robust value function of M s,u * is identical to V π P .For any state x ̸ = s and action b, it can be verified from the definitions that (P s,u ) b x = Pb Thus we verified that V π P is the fixed point of the robust Bellman operator of M s,u , and hence identical to the optimal robust value function of M s,u .Step 3. Define the set U ≜ i N : 1 ≤ i ≤ N . The set U is then a 1 N -net of the interval [0, 1]. Since it is clear that u * ≤ 1, there exists u 0 ∈ U, such that |u 0 -u * | ≤ 1 N . On the other hand, for any u ∈ U, since u ≤ 1, the optimal robust value function ∥V s,u ∥ ≤ 1 1-γ ; Moreover, from the construction, the uncertainty set P s,u is independent of Pa s , hence invoking Lemma 16 implies with probability at least 1 -δ.Step 4. We further show the following claim:EQUATIONTo show (196), for s, we have that |V s,u0 (s) -V s,u * (s)| ≤ γ∥V s,u0 -V s,u * ∥,where (a) is from (P s,u ) b x = Pb x and r s,u0 (x, b) = r s,u * (x, b) for any b ∈ A and x ̸ = s. Hence together we proved (196) , which is identical to (240) of [36] . The remaining proof hence follows exactly the same as [36] .• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a 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 is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).38th Conference on Neural Information Processing Systems (NeurIPS 2024).∆(S) denotes the probability simplex defined on S.Our approach described can also be applied to uncertainty sets defined by other metrics, e.g., Wasserstein distance and Hellinger distance. 


Decision: This paper has a solid algorithmic/theoretical contribution,

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
 
Given 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.

Addressing 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.
questions: questions: na
limitations: limitations: The authors have discussed the limitations in Section 6.
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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.
- 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.
questions: questions: To summarize the main points/questions raised in the weaknesses section:

- Could the authors provide empirical results on more complex tasks to validate the effectiveness of their method?
- Could the authors compare the computational costs of their method with other existing methods?
limitations: limitations: N/A
paper_summary: paper_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. 

Intuitively, 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. 

With 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.
strength_weakness: strength_weakness: 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.

It 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?
questions: questions: Does the proposed method achieve better empirical performance on tabular environments compared to baselines?

Are there potential ways to make the algorithm more practical?
limitations: limitations: The authors discussed certain limitations in Section 6.

Comments: comment: Thank you very much for your positive feedback on our submission!

We’re glad to hear that you found our responses helpful, and we deeply appreciate your efforts and support. Thank you again!
Thank you for your response. My concerns have been addressed, and I would like to raise my score.
Thank you again for reviewing our paper!!

As the discussion period ends soon, we would like to ask if you find our rebuttal and response useful to address your questions and concerns. If not, we are more than willing to clearify them for you! 

Thank you very much for your time and support!
Thank you very much for your positive feedback on our submission!

We’re glad to hear that you found our responses helpful, and we deeply appreciate your efforts and support. Thank you again!
Thank you very much for your positive feedback on our submission!

We’re glad to hear that you found our responses helpful, and we deeply appreciate your efforts and support. Thank you again!
I thank the authors for their rebuttal and for the additional analysis using transition kernels as well as for discussing potential use cases of the proposed algorithm. I believe this strengthens the paper and will increase my score to 6.
Thank you for your reply. I still appreciate the contributions of the work and I am in favor of the acceptance of the paper. I have no further questions and will remain my positive score.
Dear Reviewers,

As the discussion period has started for a few days, we would sincerely appreciate your review of our response to ensure that your concerns have been thoroughly addressed. If so, we kindly inquire if the reviewer could consider providing stronger support for the paper. Moreover, we are more than willing to address any further questions you may have. Thank you very much for your time and effort!

Best,

The Authors