Model-Free Offline Reinforcement Learning with Enhanced Robustness

INTRODUCTION

Traditional reinforcement learning (RL) (Sutton & Barto, 2018) optimizes an agent's performance through iterative trial-and-error interactions with the environment, and has shown significant success in many areas such as video games (Wei et al., 2022;Liu et al., 2022a). However, such an online learning scheme can be costly or unsafe in real-world applications. For instance, in domains including autonomous driving (Kiran et al., 2021), stock market trading (Kabbani & Duman, 2022), and healthcare (Yu et al., 2021), poor decisions can have significant consequences, making extensive explorations impractical. To address them, offline RL has been developed (Lange et al., 2012;Levine et al., 2020), enabling agents to learn from pre-collected datasets, offering a more reliable framework.

Since offline RL relies heavily on pre-collected datasets, the quality of these datasets largely determines performance. It is hence unclear whether satisfactory performance can be achieved for complex problems with a relatively limited dataset. In this context, two key challenges in improving offline RL performance have been studied. The first is scalability-the ability to handle large-scale problems. Without real-time interaction, learning an effective policy for large-scale problems from a limited dataset, which may not fully cover the entire state-action space, can be challenging. Recent research has focused on improving scalability by adapting model-free algorithms (Shi et al., 2022;Yan et al., 2022;Laroche et al., 2019;Fujimoto et al., 2019;Ghasemipour et al., 2021;Kumar et al., 2019;Wu et al., 2019;Siegel et al., 2020) and leveraging function approximation techniques (Ross & Bagnell, 2012;Liu et al., 2020;Xie et al., 2021a;Yin et al., 2021a;Xie & Jiang, 2021;Jiang & Huang, 2020). However, due to the complexity of large environments, many of these approaches assume that the dataset sufficiently represents the full deployment environment, typically presuming that the deployment environment is identical to the one from which the data was collected.

However, this assumption can be too restrictive. Static datasets only capture the environment at the time of data collection, but real-world applications frequently face environmental uncertainty due to perturbations or non-stationarity. This mismatch between the data collection and deployment environments, commonly known as the sim-to-real gap (Zhao et al., 2020), can cause significant performance degradation during deployment. Therefore, it is crucial to enhance the robustness of offline RL to ensure that the learned policies can perform reliably in the presence of such uncertainties. A promising solution is to adapt robust RL frameworks (Iyengar, 2005;Nilim & El Ghaoui, 2004) to the offline setting, as explored recently in (Shi & Chi, 2022;Blanchet et al., 2023). However, these methods often come at the cost of scalability. Due to their inherent structure, robust RL methods typically rely on dynamic planning, which requires knowledge of the full transition dynamics, and are predominantly model-based. This necessitates learning and storing a complete transition model, which is resource-intensive (Zhang et al., 2021a) and limits scalability for large-scale problems.

Recognizing the limitations of current methods and the challenges posed by large-scale problems and model uncertainty, a trade-off between robustness and scalability becomes apparent. Enhancing one typically comes at the expense of the other. This naturally leads to the following question:

Can we develop a unified framework that enhances both scalability and robustness in offline RL?

In this paper, we address this question by presenting a model-free algorithm to learn a policy that is both robust to model uncertainty and scalable to large-scale problems. Our method introduces a principle of double pessimism to simultaneously address two key sources of uncertainty: (1) the uncertainty arising from inaccurate estimations due to the underexplored datasets, and (2) model mismatch between the data collection and deployment environments. We then propose a streamlined conceptual framework, design a model-free algorithm, and provide the first theoretical guarantee of convergence and robustness of our approach. Our contributions can be summarized as follows.

• A Double-Pessimism Principle for Offline RL with Model Mismatch. We begin by framing the challenge of enhancing robustness in offline RL within an offline robust RL framework, where an uncertainty set captures potential environmental mismatches. To solve offline robust RL in a scalable manner, we propose the double-pessimism principle that does not require transition kernel estimations. This principle maintains a conservative estimate of robust performance, obtained directly from data collection without requiring model estimation. We then introduce the first model-free pessimistic robust Q-learning algorithm.

Our algorithm optimizes performance under model mismatch using an offline dataset, while offering greater memory efficiency and more scalability than previous methods.

• First and Near-Optimal Model-Free Algorithm for Offline Robust RL. We provide a rigorous sample complexity analysis for our model-free double-pessimistic robust Q-learning algorithm under the widely used l α -norm uncertainty set. Our analysis shows that, given a dataset satisfying the partial coverage condition (to be introduced later), our algorithm can identify an optimal robust policy with near-optimal sample complexity, comparable to that of model-based offline robust RL and model-free offline non-robust RL. This represents the first sample complexity analysis for model-free robust offline RL, demonstrating its applicability to large-scale problems that require high data efficiency.

• Numerical Experimental Verification of Enhanced Robustness. We conduct extensive numerical experiments to demonstrate the improvements in robustness achieved by our algorithms in both simulated environments (Archibald et al., 1995) and real physics-based Classic Control problems (Brockman et al., 2016). In each case, our algorithm consistently outperforms existing methods in handling model uncertainty, showcasing its enhanced ability to maintain stable performance across a wide range of environmental perturbations. Moreover, our approach demonstrates superior scalability stemming directly from our modelfree algorithm design, as shown by its effectiveness in solving more complex Classic Control problems with robustness guarantees, which have proven difficult or unsolvable for previous model-based robust methods.

The probability transition kernel P h : S × A → ∆(S) and the reward function r h : S × A → [0, 1] are defined at each step h (1 ≤ h ≤ H). At each step h, the agent starts in state s h , takes action a h , transitions to the next state s h+1 according to the transition kernel P h,s h ,a h , and receives a reward r h (s h , a h ). This process terminates after H steps when the agent reaches state s H+1 .

A policy π = {π h } H h=1 defines the strategy for selecting actions in different states, where π h : S → ∆(A) specifies the probability distribution over actions at step h. The performance of an agent following a policy π is measured by the value function V π,P = {V π,P h } H h=1 , where

The expectation is taken over the trajectory {s h , a h , r h } H h=1 generated by executing the policy π and transitioning according to the transition kernel P : a h ∼ π h (s h ) and s h+1 ∼ P h,s h ,a h .

DOUBLE-PESSIMISM PRINCIPLE

In this section, we introduce our model-free algorithm for learning an optimal robust policy from an offline dataset. As we mentioned, two major challenges in offline RL are the two sources of uncertainty: one arising from the limited and under-explored dataset, and the other from the mismatch between the data collection and target environments. We aim to develop a unified double-pessimism principle to address both of them.

As suggested by previous studies on offline RL, e.g., (Rashidinejad et al., 2021;Li et al., 2022;Shi et al., 2022;Yan et al., 2022;Wang et al., 2024c), the uncertainty arising from the dataset can be addressed using a single-pessimism principle. This involves introducing a penalty term b n , which depends on the visitation frequency of each state-action pair, to penalize less frequently visited pairs. By doing so, we obtain a conservative estimate of the value function under the nominal kernel.

However, addressing the uncertainty arising from model mismatch is particularly challenging, especially with a model-free approach. Most previous robust RL studies require that the estimation of the worst-case transition, σ P (V ) ≜ min p∈P pV , be unbiased. This can be satisfied when the agent can freely generate data as needed (e.g., (Wang et al., 2023d;Liu et al., 2022b;Wang et al., 2023c;b)), yet is impractical in offline settings. To address this issue, we argue that another pessimism principle can be adopted, and that learning a policy robust to model mismatch does not require an unbiased estimator or an accurate solution to the worst-case. As long as the estimator provides a (not too pessimistic) lower bound on the worst-case, it is sufficient to account for the uncertainty due to model mismatch and still learn a robust policy. We therefore propose a model-free estimator that lower bounds σ(V ) to produce a conservative estimation as follows.

Definition 1. For the uncertainty set P s,a , a function κ is referred to as a model-mismatch penalty function if for any non-negative vector V and a sample s ′ ∼ P s,a from the nominal kernel,

A universal design of the penalty function κ is provided in Appendix C. Such a penalty function ensures that at each step, the updated estimate represents a lower bound on the true worst-case scenario, resulting in a conservative estimation and enhancing robustness. We note that this additional pessimism may result in a more conservative policy, as the algorithm will estimate the robust value function more pessimistically. However, we argue that as long as the pessimism level is not too large, the learned policy will not be too conservative, maintaining a satisfactory performance and enhancing the robustness. More importantly, calculation of κ does not require any information of the model, but can be done in a data-driven and model-free fashion.

We then combine the two pessimism principles together, to develop our double-pessimism algorithm based on the Q-learning algorithm. For each sample (s, a, s ′ ), we update the Q table by

As we will show later, such an update rule incorporating the double-pessimism principle ensures that our estimation is conservative, and can effectively tackle the uncertainty in offline robust RL. More importantly, such an update rule does not require any information on the transition model, and hence can be adapted in a model-free manner and is more suitable for large-scale problems.

Based on this, we develop our model-free offline algorithms for both finite and infinite horizon cases.

In the following sections, we present these algorithms and develop their sample complexity analysis.

DOUBLE-PESSIMISM Q-LEARNING FOR FINITE-HORIZON MDPS

Adopting the double-pessimism principle, we propose our algorithm for finite-horizon MDPs.

Algorithm 1 Double-Pessimism Q-Learning for finite-horizon RMDPs.

Input: D, target success probability 1 -δ, uncertainty set radius R, penalty function κ Initialize:

In our algorithm, the term κ is for conservative estimation of the worst-case performance within the uncertainty set, while the term b addresses the pessimism of the limited dataset. We track the visitation count of each state-action pair and construct the penalty term b based on these counts. As the dataset visits a pair more frequently, the associated uncertainty decreases and b decreases. Remark 2. Our algorithm design is universal and works for any uncertainty set models, as long as we have a penalty function κ satisfying equation 15, which is provided in Appendix C. However, since κ for different models requires individual studies, we mainly derive our theoretical analysis for the l α -norm models (Kumar et al., 2023;Derman et al., 2021):

We again emphasize that our double-pessimism principle and algorithm design can be extended further to other uncertainty set models. We provide a detailed discussion on κ in Appendix C.

Next, we develop our theoretical results for l α -norm sets. We first show that equation 15 is satisfied by our design, and the algorithm results in a conservative estimation of the robust value function. Lemma 1. For the l α -norm uncertainty set, set the penalty function κ as

where β = 1 1-1 α is the Hölder conjugate of α, and e = (1, 1, ..., 1) ∈ R S . Then, equation 15 is satisfied. Moreover, it holds that for all (k, h, s)

The lemma provides a concrete construction of the penalty function for the l α -norm model. More importantly, our model-free estimator and algorithm result in pessimistic estimations of robust value functions, tackling both uncertainty sources. In our next result, we show that our double-pessimism principle is effective in learning the optimal robust policy from the mismatched offline dataset. Theorem 2. For the l α -norm uncertainty set, and any δ ∈ (0, 1), suppose that the behavior policy µ satisfies Assumption 1. When T ≜ HK > Õ(SC ⋆ ), the policy π returned by Algorithm 1 satisfies

with probability at least 1 -δ. Here, π * is the optimal robust policy w.r.t. a (possibly) relaxed l α -norm uncertainty set (see Appendix C.2 for detailed discussion).

) k for some constants C > 0 and k ≥ 0, when T is sufficiently large.

Our algorithm is the first model-free algorithm for offline RL under model mismatch with suboptimality gap analysis. The sub-optimality gap we obtain in the previous result further implies that we can learn an ϵ-optimal policy as long as the size of the offline dataset T exceeds

Note that in the sample complexity, the second term, referred to as the burn-in cost, is a universal constant that does not depend on ϵ, while the first term asymptotically depends on ϵ. When ϵ becomes smaller, the first term dominates the overall complexity, resulting in an asymptotic complexity of

. A more detailed discussion of the complexity will be provided in Section 7.

Remark 3. When the radius R is small, it holds that E[V (s ′ ) -κ s,a (V )] = σ Ps,a (V ) (see Theorem 1 in (Kumar et al., 2023)), hence Algorithm 1 converges to the optimal robust policy w.r.t. the original uncertainty set. For general uncertainty set and corresponding penalty function κ, Algorithm 1 may converge to the optimal robust policy w.r.t. a relaxed uncertainty set, as the estimation may be inaccurate. However, robustness can still be enhanced due to the additional pessimism. See Appendix C for further discussion.

COMPARISON WITH PRIOR ARTS

In this section, we compare our work to the most closely related studies for tabular offline robust RL (Shi & Chi, 2022;Blanchet et al., 2023). The results are summarized in Table 1, where we only include the infinite horizon ones. Compared to previous studies, our method offers improved memory and computational complexity, while maintaining comparable sample complexity.

Reference Memory complexity Sample complexity Computational complexity

Polynomial Table 1: Comparison with offline robust RL works. (Shi & Chi, 2022) is for the KL-divergence set.

First, both related works are model-based, which involves estimating and storing the transition model { Ps,a : (s, a) ∈ S × A} ∈ R S 2 A . This approach thus requires an additional memory of size O(S 2 A) to store the model, along with O(SA) space for the number of visited state-action pairs from the dataset. As a result, it becomes inefficient for large-scale problems or environments with complicated transition dynamics. In contrast, our model-free algorithm only requires O(SA)-sized space for the number of visits. Such a reduced memory complexity enables our model-free algorithms to handle large-scale problems, scaling effectively to large-scale or even continuous problems.

In terms of computational complexity, the most related work (Blanchet et al., 2023) requires to solve a non-rectangular RMDP, which is generally NP-hard (Wiesemann et al., 2013). In contrast, our algorithm can be effectively implemented in polynomial time, which is much more practical. Compared to (Shi & Chi, 2022), our algorithm still enjoys lower computational complexity, since the update rule of the model-based approach requires computing the inner product Ps,a V , whereas our model-free approach eliminates this computation and only requires a single vector entry V (s ′ ). See Appendix C for a more detailed discussion.

In terms of sample complexity, both of our sample complexity results match the ones for offline non-robust Q-learning without variance reduction, illustrating our data efficiency and near-optimality. Our result improves the dependence on S compared to (Blanchet et al., 2023) under the l ∞ -norm uncertainty set, showing the enhanced scalability to large-scale problems. On the other hand, it is the general observation that model-based methods tend to demonstrate better sample complexity in terms of (1 -γ) than model-free methods, especially when additional techniques like variance reduction are not employed. Such findings have been widely noted in various settings, for instance, when comparing robust RL with generative models ( (Wang et al., 2024a) vs. (Shi et al., 2023)) and non-robust offline RL ( (Yan et al., 2022) vs. (Li et al., 2022)).

On a side note, we note that our result for the finite-horizon setting exhibits a higher-order dependence on H (where we set H = 1 1-γ as the effective horizon in infinite setting). This is due to the nonstationary environment inherent in the finite-horizon setting, which is also consistent with findings from previous studies, such as in (Shi & Chi, 2022).

To summarize, our approach addresses existing gaps in offline RL by enhancing robustness to model mismatch, reducing memory requirements, and providing adaptability to large-scale problems, establishing a state-of-the-art method in the field.

OTHER RELATED WORKS

Offline RL without model mismatch. A significant body of offline RL works assumes identical collection and deployment environments. Based on that, many early works further rely on the global coverage assumption, where the behavior policy covers all state-action pairs (Scherrer, 2014;Chen & Jiang, 2019;Munos, 2005;Yin et al., 2021b;Yin & Wang, 2021a;Jiang, 2019;Wang et al., 2019;Liao et al., 2020;Liu et al., 2019;Zhang et al., 2020;Uehara et al., 2020;Duan et al., 2020;Xie & Jiang, 2020;Levine et al., 2020;Antos et al., 2007;Farahmand et al., 2010). This assumption is often too restrictive and unrealistic, as it requires complete coverage of state-action pairs in historical data (Gulcehre et al., 2020;Agarwal et al., 2020a;Fu et al., 2020). A more practical partial coverage setting is later proposed, allowing to learn from a less explored dataset. Under partial coverage, the optimal policy can still be learned by incorporating the pessimism principle to handle dataset uncertainty (Jin et al., 2021;Uehara & Sun, 2021;Xie et al., 2021a;b;Rashidinejad et al., 2021;Zanette et al., 2021;Yin & Wang, 2021b;Shi et al., 2022;Li et al., 2022;Zhan et al., 2022;Wang et al., 2023e;Kumar et al., 2020). Differently, we consider potential model mismatches.

Robust RL. Robust RL (Iyengar, 2005;Nilim & El Ghaoui, 2004;Xu & Mannor, 2010) aims to tackle the challenge of model mismatch in RL, by optimizing the worst-case performance over an uncertainty set. Existing work focuses mainly on the online setting (Wang & Zou, 2021;2022;Wang et al., 2023a;Badrinath & Kalathil, 2021;Dong et al., 2022;Lu et al., 2024;Liu & Xu, 2024a) or with a generative model (Yang et al., 2021;Xu et al., 2023;Panaganti & Kalathil, 2022;Shi et al., 2023;Wang et al., 2024a;b;2022). Offline robust RL, except for the two mentioned above, either relies on strong assumptions, such as global coverage or absorbing states (Panaganti et al., 2022;Yang et al., 2021), or employs fitted type algorithm designs (Yang et al., 2022;Panaganti et al., 2022;Liu et al., 2023). More importantly, most of them are model-based, while we develop the first model-free algorithm for offline robust RL. Another line of research aims to improve robustness and scalability through function approximation (Liu & Xu, 2024b;Wang et al., 2024a;Ma et al., 2022), yet we focus on the tabular setting to develop a more fundamental understanding of offline RL. Another line of robust RL aims to optimize the performance under the environment from a corrupted dataset collected under the same environment (Yang et al., 2023;Zhang et al., 2021b;2022), which is different from our setting.

CONCLUSION

We explored offline RL with a focus on improving scalability and robustness simultaneously. We framed the problem as offline robust RL and developed a model-free algorithm to optimize the worst-case performance within an uncertainty set accounting for the possible model mismatch. To address two key challenges-uncertainty from the under explored dataset and model mismatch between data collection and deployment environments-we introduced a double-pessimism principle that conservatively estimates the agent's performance in a model-free manner. Building on this, we designed a universal model-free algorithm that eliminates the need for model estimation, adapts to various uncertainty sets, and scales to large problems. We further analyzed its performance for the widely studied l α -norm uncertainty set, showing near-optimal data efficiency of our approach. Our approach significantly improves the robustness, scalability, and efficiency of offline RL compared to existing methods, pushing the boundaries of offline RL research.

Peng Liao, Zhengling Qi, and Susan Murphy. Batch policy learning in average reward Markov decision processes. arXiv preprint arXiv:2007.11771, 2020. Boyi Liu, Qi Cai, Zhuoran Yang, and Zhaoran Wang. Neural trust region/proximal policy optimization attains globally optimal policy. In Proc. Advances in Neural Information Processing Systems (NeurIPS), 2019. Ruo-Ze Liu, Zhen-Jia Pang, Zhou-Yu Meng, Wenhai Wang, Yang Yu, and Tong Lu. On efficient reinforcement learning for full-length game of starcraft ii. Journal of Artificial Intelligence Research, 75:213-260, 2022a. Xiao-Yin Liu, Xiao-Hu Zhou, Guo-Tao Li, Hao Li, Mei-Jiang Gui, Tian-Yu Xiang, De-Xing Huang, and Zeng-Guang Hou. Micro: Model-based offline reinforcement learning with a conservative bellman operator. arXiv preprint arXiv:2312.03991, 2023. Yao Liu, Adith Swaminathan, Alekh Agarwal, and Emma Brunskill. Provably good batch reinforcement learning without great exploration. arXiv preprint arXiv:2007.08202, 2020. Zhishuai Liu and Pan Xu. Distributionally robust off-dynamics reinforcement learning: Provable efficiency with linear function approximation. arXiv preprint arXiv:2402.15399, 2024a. Zhishuai Liu and Pan Xu. Minimax optimal and computationally efficient algorithms for distributionally robust offline reinforcement learning. arXiv preprint arXiv:2403.09621, 2024b. Zijian Liu, Qinxun Bai, Jose Blanchet, Perry Dong, Wei Xu, Zhengqing Zhou, and Zhengyuan Zhou. Distributionally robust Q-learning. In International Conference on Machine Learning, pp. 13623-13643. PMLR, 2022b. Miao Lu, Han Zhong, Tong Zhang, and Jose Blanchet. Distributionally robust reinforcement learning with interactive data collection: Fundamental hardness and near-optimal algorithm. arXiv preprint arXiv:2404.03578, 2024. Xiaoteng Ma, Zhipeng Liang, Jose Blanchet, Mingwen Liu, Li Xia, Jiheng Zhang, Qianchuan Zhao, and Zhengyuan Zhou. Distributionally robust offline reinforcement learning with linear function approximation. arXiv preprint arXiv:2209.06620, 2022. Rémi Munos. Error bounds for approximate value iteration. In Proceedings of the National Conference on Artificial Intelligence, volume 20, pp. 1006. Menlo Park, CA; Cambridge, MA; London; AAAI Press; MIT Press; 1999, 2005. Arnab Nilim and Laurent El Ghaoui. Robustness in Markov decision problems with uncertain transition matrices. In Proc. Advances in Neural Information Processing Systems (NIPS), pp. 839-846, 2004. Kishan Panaganti and Dileep Kalathil. Sample complexity of robust reinforcement learning with a generative model. In International Conference on Artificial Intelligence and Statistics, pp. 9582-9602. PMLR, 2022. Kishan Panaganti, Zaiyan Xu, Dileep Kalathil, and Mohammad Ghavamzadeh. Robust reinforcement learning using offline data. arXiv preprint arXiv:2208.05129, 2022. Lerrel Pinto, James Davidson, Rahul Sukthankar, and Abhinav Gupta. Robust adversarial reinforcement learning. In Proc. International Conference on Machine Learning (ICML), pp. 2817-2826. PMLR, 2017. Paria Rashidinejad, Banghua Zhu, Cong Ma, Jiantao Jiao, and Stuart Russell. Bridging offline reinforcement learning and imitation learning: A tale of pessimism. Advances in Neural Information Processing Systems, 34:11702-11716, 2021. Stephane Ross and J Andrew Bagnell. Agnostic system identification for model-based reinforcement learning. arXiv preprint arXiv:1203.1007, 2012. Bruno Scherrer. Approximate policy iteration schemes: A comparison. In Proc. International Conference on Machine Learning (ICML), pp. 1314-1322, 2014. A EXPERIMENTAL SETUP OF SECTION 8 A.1 GARNET PROBLEMS For simulated MDP environments, we implement Algorithm 3 on Garnet problems G(20, 30, 20), G(30, 50, 30) and G(50, 100, 50). Here, the branch number denotes the number of states that can be achieved after taking an action. The uncertainty radius R s,a is randomly drawn from a uniform distribution ranging from 0.1 to 0.5 for all state-action pairs. The true robust expected values for the Garnet problems, over a certain state distribution, can be obtained via the model-based robust value iteration method. For each problem, we first generate a stochastic behavior policy with partial coverage over state-action pairs. To obtain a near-optimal stochastic behavior policy, we compute the Q-values for the nominal kernel, and adopt a softmax transformation to assign probabilities for all state-action pairs. The randomness (i.e., optimality) of the behavior policy is controlled via temperature parameter t b = 1. State-action pairs with probabilities P s,a ≤ 0.03 (for G(20, 30, 20)), P s,a ≤ 0.02 (for G(30, 50, 30)) and P s,a ≤ 0.01 (for G(50, 100, 50)) are then excluded to achieve partial coverage. Finally, non-zero elements are re-normalized to maintain a valid probability distribution. By deploying the behavior policy on the nominal kernel, 10 datasets are generated at each dataset size from T = 1000 to T = 20000. We compared the double-pessimism method with the single-pessimism method in (Yan et al., 2022). We set γ = 0.95, C b = 1 × 10 -4 and δ = 0.02.

B.1 COMPARISONS IN TABULAR ENVIRONMENTS

In this section, we include additional experiment results under three simulated environments. Specifically, we consider the Frozen-Lake and Taxi environments from OpenAI Gym (Brockman et al., 2016), and the American Option problem (Panaganti et al., 2022;Shi & Chi, 2022;Zhou et al., 2021).

The transition dynamics of these environments can be directly controlled, and we construct l ∞ -norm uncertainty sets centered at their nominal kernels. Similarly, we trained our double-pessimism Q-learning together with the single-pessimism baseline, and plotted the optimality gap between the learned and optimal robust value functions. As the results in Figure 3 show, our double-pessimism Q-learning effectively obtains the optimal robust policy, whereas the single-pessimism Q-learning only achieves sub-optimal performance. The results hence indicate that our additional pessimism effectively enhances robustness against model uncertainty, verifying our theoretical results.

(a) Frozen-Lake (b) Taxi (c) American Option B.2 SCALABLE ALGORITHM WITH FUNCTION APPROXIMATION: DOUBLE-PESSIMISM CQL In this section, we extend the evaluation of our double-pessimism framework to large-scale problems using function approximation techniques. The algorithms presented earlier (Algorithm 1, Algorithm 3), while model-free, are designed for tabular settings and require memory space of O(SA) for the Q-table, making them less efficient for large-scale applications. To improve scalability, replacing the Q-table with low-dimensional function approximations (e.g., neural networks) to reduce memory costs is a widely adopted approach. On the other hand, existing offline RL algorithms like Conservative Q-learning (CQL, (Kumar et al., 2020)) and Implicit Q-learning (IQL, (Kostrikov et al., 2021)), along with others (Ross & Bagnell, 2012; Laroche et al., 2019; Fujimoto et al., 2019; Kumar et al., 2019; Agarwal et al., 2020b; Liu et al., 2020; Jin et al., 2021; Xie et al., 2021a; Yin et al., 2021a; Rashidinejad et al., 2021; Xie & Jiang, 2021; Jiang & Huang, 2020), have focused solely on offline RL without model mismatch, resulting in degraded performance when model mismatch is present.

Aiming to enhance both robustness and scalability, we design and evaluate a double-pessimism CQL algorithm, demonstrating that our framework is not limited to tabular settings but can also be integrated with function approximation or deep RL techniques, significantly improving robustness against model mismatch. Specifically, we employ the CQL method to impose pessimism on the limited dataset, and further incorporate an additional penalty term into the robust Bellman operator estimation to effectively mitigate model mismatch. Based on this construction, we can similarly design a double-pessimism CQL algorithm, from which enhanced robustness is expected. To validate the effectiveness of our double-pessimism principle, we compare our double-pessimism CQL with the vanilla single-pessimism CQL under CartPole from OpenAI Gym. The policy is trained in the nominal environment and evaluated in randomly perturbed environments (perturbation radius τ ) over 800 trials. The results, shown in Figure 5, display the average performance as solid curves, with envelopes representing standard deviations.

As the results indicate, our double-pessimism CQL consistently outperforms the vanilla CQL in perturbed environments, demonstrating enhanced robustness. This experiment confirms the universal applicability of our double-pessimism framework in improving robustness, regardless of the specific algorithm used. It also highlights the scalability of our approach, which can be integrated with advanced deep offline RL algorithms for large-scale problems using function approximation.

B.3 ABLATION EXPERIMENTS

Our double-pessimism principle addresses two key challenges: the first component tackles the limited dataset coverage in offline RL to handle out-of-distribution issues, while the second addresses model mismatch between the data generation and deployment environments.

In this section, we conduct ablation experiments to evaluate the effectiveness of this principle. Specifically, we compare four algorithms in an offline setting: vanilla Q-learning (with zero pessimism), robust Q-learning (with model-mismatch pessimism only), offline non-robust Q-learning (with dataset pessimism only), and our proposed offline robust Q-learning (with double pessimism). The experiments are conducted on two Garnet problems, where we evaluate the robust value functions of the learned policies with respect to an uncertainty set defined by the l ∞ -norm.

The results are shown in Figure 6. The solid curve represents the average value across 10 independent runs, while the shaded area indicates the maximum and minimum values observed.

Our double-pessimism approach outperforms all four algorithms, including those with a single source of pessimism, demonstrating the effectiveness of our framework. Furthermore, the single-pessimism methods achieve better performance than the vanilla algorithm with no pessimism, highlighting the benefits of incorporating pessimism in offline robust RL. However, both are ultimately outperformed by our double-pessimism method, underscoring the importance of addressing both sources of uncertainty through the double-pessimism principle. C FURTHER DISCUSSION OF κ C.1 A UNIVERSAL CONSTRUCTION OF κ

In this section, we discuss the design of the penalty function κ for universal uncertainty set models defined by some distribution divergence/distance functions F (•||•):

Note that this uncertainty set includes perturbed environments within a region centered around the nominal kernel, effectively modeling environmental uncertainty in practical applications. This is because, in practice, perturbed environments should not deviate significantly from the nominal kernel and should therefore fall within a defined region.

We first present the following theorem for a universal construction of the penalty function κ. Theorem 4. Let κ(V ) be the optimal value of the following constrained problem:

Then, κ(V ) satisfies equation 15, i.e.,

Proof. Note that the problem in equation 25 is equivalent to the problem

The proof is then straightforward by noting that P ⊂ Q, hence

Such a result provides a universal construction of the penalty function κ, for the perturbed-based uncertainty set as in equation 24. Note that κ(V ) depends on P , which is unknown in practice, but any unbiased estimation of it is sufficient. To illustrate this and show the generality of our design, we develop a case study for the χ 2 -divergence uncertainty set in the following section.

C.2 CASE STUDY: l α -NORM UNCERTAINTY SET

In this section, we provide a more detailed discussion on the l α -norm uncertainty set. As discussed, we consider the relaxed l α -norm uncertainty set:

Ps,a = {P s,a + q :

where we relax the condition P s,a + q ≥ 0. Then the worst-case transition w.r.t. P can be derived as

where

For popular choices of α, the optimization problem in equation 31 has a closed-form solution, specified in Table 2 (Kumar et al., 2023). Note that for the three choices of α = 1, 2, ∞,

Table 2: Penalty term for l α -norm uncertainty set the resulting penalty terms incur a computational complexity of O(S). When combined with our algorithm, this leads to an overall implementation complexity of O(SA) per step. In contrast, the model-based methods proposed in (Shi & Chi, 2022;Blanchet et al., 2023) have a computational cost of O(S 2 A) per step (Kumar et al., 2023), highlighting the superior efficiency and scalability of our approach.

Our algorithm and theoretical result will then characterize the convergence to the optimal robust policy w.r.t. P. More importantly, when the uncertainty radius R is small, the relaxation will not be effective, i.e., P = P (Zhou et al., 2024).

C.3 CASE STUDY: χ 2 UNCERTAINTY SET

We adapt the construction we obtained to the widely used χ 2 -divergence as a case study. The design of κ for other uncertainty sets can be obtained in a similar way.

Specifically, the uncertainty defined for the (s, a)-pair is

where

is the χ 2 -divergence. We aim to design a model-free function κ that serves as the penalty term to address the uncertainty from the model mismatch.

We first establish the following lemma. Lemma 5. The constrained problem

has the solution -R s,a Var Ps,a (V ).

(34)

Proof. To simplify the notation, we omit the subscript s, a from P s,a and R s,a . We note that if any entry P i = 0, then any feasible q i = 0, otherwise the χ 2 -divergence will be infinite. Thus, we can simply ignore the i-th entry in this case and only consider the remaining ones. Hence, we assume P i > 0, ∀i without loss of generality.

Note that the condition

hence the Lagrangian function L of the constrained problem is

From the KKT conditions (Bertsekas, 1997), the solution q * and the Lagrangian multipliers λ * and µ * must satisfy

We first show that if q * is the optimal solution, then D χ 2 (q * + P ||P ) < R. To show that this statement always holds, our claim is that there exists an optimal solution such that µ * = 0, then we have

and hence,

To prove that this claim is not possible, we provide a counterexample to demonstrate that µ * = 0 and

where p 1 , p 2 ̸ = 0. We have q 2 = -q 1 , then

Hence,

Published as a conference paper at ICLR 2025

The optimal value of the optimization problem is

Obviously, the optimization problem does not have an optimal solution, but instead an infimum.

There always exists a feasible solution q such that

which means that µ * ̸ = 0 always holds.

Thus,

and hence,

where we use the constraint i q * i = 0 and i

Pi = R. Again, from equation 37, we have that

and hence,

Taking the sum over i implies that

and hence,

On the other hand, note that equation 37 further implies that

and hence,

Plugging in equation 49 implies that

Hence, from equation 45, the optimal solution of the constrained problem is then -RVar P (V ), which completes the proof.

With the optimal solution to equation 33, we can then design the penalty function κ for the χ 2 uncertainty set defined as in equation 32. Firstly, we note that equation 33 is a relaxation of the support function over equation 32, therefore the optimal solution to equation 33 is not greater than σ P (V ), and therefore is a pessimistic penalty of the model mismatch. We thus design the penalty function as

We note that in the model-free setting, it is straightforward to obtain an unbiased estimation of κ, which however requires more than 1 sample. Specifically, for n i.i.d. samples (s, a, s ′ i ), i = 1, ..., n, the model-free penalty function is defined as

where

. Such a penalty function satisfies the condition equation 15 of the pessimism principle, and hence we can extend our model-free algorithms to the χ 2 -divergence model. We present the algorithm for the infinite horizon in Algorithm 2. Different from Algorithm 3, for the Algorithm 2 Double-Pessimism Q-Learning for infinite-horizon RMDPs with χ 2 -divergence uncertainty set.

end for π(s) = arg max a∈A Q T (s, a), ∀s Output: π χ 2 -divergence model, we require 2 samples at each step to estimate κ. However, the estimation does not required any information on P s,a and hence Algorithm 3 is still model-free.

Note that generally the penalty function κ is biased, thus the algorithm may not converge to the optimal robust policy. However, the robustness can still be enhanced due to the additional pessimism. We validate the effectiveness of our algorithm in optimizing performance under model mismatch in an offline setting through numerical experiments. Specifically, we implemented our algorithm alongside the baseline single-pessimism Q-learning algorithm (Yan et al., 2022) on Garnet problems with varying parameters, and three simulation environments: Frozen-Lake, Taxi, and American Option. Using datasets of different sizes, we computed the robust value function of the learned policy via dynamic programming (Iyengar, 2005), and plotted the results in Figure 7 and Figure 8. Each curve represents the average over 10 independent runs, with the shaded region indicating the maximum and minimum values. As demonstrated in the results, our double-pessimism Q-learning significantly outperforms the single-pessimism approach, showcasing the robustness of our algorithm to model mismatch and confirming the efficacy of our double-pessimism design. D ANALYSIS OF THE FINITE HORIZON SETTING D.1 NOTATION

Recall the learning rate defined by

for the n-th visit of a given state-action pair at a given time step h. We further adopt two sequences of related quantities for any integers N ≥ 0 and n ≥ 1 from (Shi et al., 2022):

It has been shown in (Shi et al., 2022;Yan et al., 2022) that

We also introduce the following notation:

• N k h (s, a), or simply N k h : The number of episodes that have visited the state-action pair (s, a) at step h before the start of the k-th episode.

• k n h (s, a), or simply k n : The index of the episode in which the state-action pair (s, a) is visited at step h for the n-th time. We adopt the convention that k 0 = 0.

• P k h ∈ {0, 1} 1×S : A row vector corresponding to the empirical transition at step h of the k-th episode, defined as

The deterministic greedy policy at the beginning of the k-th episode.

• π: The final output of the algorithm, corresponding to π K+1 as defined above. For simplicity in our analysis, we treat π as π K , which does not affect the result.

D.2 LEMMAS FOR THEOREM 2

In this section, we present the lemmas that are utilized in the proof of Theorem 2.

The first lemma demonstrates how our choice of the penalty term κ can address the uncertainty arising from model mismatch.

Lemma 6. (Theorem 1 in (Kumar et al., 2023)) Let P s,a be the uncertainty set defined using the l α -norm. For any vector V , the following relationship holds:

where κ is defined as in equation 18.

The following lemma provides properties concerning the learning rates and is adapted from (Jin et al., 2018;Li et al., 2021).

Lemma 7 (Lemma 1 in (Li et al., 2021)). For any integer N > 0, the following properties hold:

The following lemmas concern the concentration properties of the sample generation.

The first lemma below is adapted from Xie et al. (2021b, Lemma A.1).

Lemma 8. (Lemma 8 in (Shi et al., 2022)) Suppose N ∼ Binomial(n, p), where n ≥ 1 and p ∈ [0, 1].

For any δ ∈ (0, 1), we have

and

with probability at least 1 -4δ.

The following lemma is a standard concentration inequlity result.

Theorem 9 (Freedman's inequality (Freedman, 1975)). Consider a filtration

and let E k stand for the expectation conditioned on

for all k ≥ 1 for some quantity R < ∞. We also define

In addition, suppose that W n ≤ σ 2 holds deterministically for some given quantity σ 2 < ∞. Then, for any positive integer m ≥ 1, with probability at least 1 -δ one has

The Freedman's inequality further implies several important results related to our problem. Lemma 10.

be a collection of vectors satisfying the following properties:

h is fully determined by the samples collected up to the end of the (h -1)-th step of the i-th episode;

For any positive integer N ≥ H, consider the following sequence:

With probability at least 1 -δ,

holds simultaneously for all (k, h, s, a, N ) s,a) . From equation 61b in Lemma 7, we have

w , we can apply Lemma 7 from (Li et al., 2021) to obtain, with probability at least 1 -δ,

where the final line uses equation 61b from Lemma 7 again.

be a collection of vectors satisfying the following properties:

) is fully determined by the given state-action pair (s, a) and the samples collected up to the end of the (k -1)-th episode;

For any positive C d ≥ 0, consider the following sequences:

Consider any δ ∈ (0, 1). Then with probability at least 1 -δ,

hold simultaneously for all h ∈ [H].

Proof. The proof similarly follows from (Shi et al., 2022).

We then prove Lemma 1 showing the effectiveness of our double pessimism principle, i.e., that our estimation is a conservative estimation of the robust value function.

Lemma 12. Consider any δ ∈ (0, 1), and suppose that c b > 0 is some sufficiently large constant. Then, with probability at least 1 -δ,

holds simultaneously for all (k, h, s)

Proof. Proof of inequality equation 71. We show it by invoking Lemma 10. Let

where the first equation is from Lemma 6. Hence applying Lemma 10 implies that with probability at least 1 -δ,

holds simultaneously for all (s, a, k, h)

holds simultaneously for all s, a, h, k ∈ S × A × [H] × [K], which follows directly from the property equation 61a in Lemma 7.

Combining the above, equation 74 and equation 76 hence imply that

Proof of inequality equation 72. Note that the second inequality of equation 72 is straightforward as

s) holds for any policy π. As a consequence, it suffices to establish the first inequality of equation 72:

Define

We need to verify

Step 1: base case.

Let us begin with the base case when h + 1 = H + 1 for all episodes k ∈ [K]. Recognizing the fact that V π H+1 = V k H+1 = 0 for any π and any k ∈ [K], we directly arrive at

Step 2: induction. To justify equation 80 under the induction hypothesis equation 79, we decompose the difference term to obtain

where the last line holds since V h (s) has not been updated during episodes 78). We shall prove that the right-hand side of equation 82 is non-negative by discussing the following two cases separately.

Case 1. Consider the case where

holds for all (k, h)

To continue, we turn to controlling a more general term

This relation combined with equation 106 allows us to express the difference between

Here, (a) invokes the robust Bellman equation

, owing to the induction hypothesis in equation 79 as well as the monotonicity of V h+1 in Lemma 12. Consequently, it follows from equation 85 that

(86) for all state-action pair (s, a), where the last inequality holds due to the bound in equation 71 in Lemma 12. Plugging the above result into equation 84 directly establishes that

which follows from the definition of k o (h) in equation 78 and the corresponding fact in equation 83.

We also make note of the fact that

which holds since V h (s) (and hence π h (s)) has not been updated during episodes k o (h), k o (h) + 1, • • • , k -1 (in view of the definition equation 78). Combining the above two results, we can show that

where the final line can be verified using exactly the same argument as in the previous case to show equation 85 and then equation 87. Here, we omit the proof of this step for brevity.

To conclude, substituting the relations equation 87 and equation 90 in the above two cases back into equation 82, we arrive at

≥ 0 as desired in equation 80. This immediately completes the induction argument.

Lemma 13. With probability at least 1 -δ, it holds that

Proof. It is sufficient to show that

Define two auxiliary sequences {Y h,k } K k=1 and {Z h,k } K k=1 which are the empirical estimates of A h,k and B h,k , respectively. For any time step h in episode k, Y h,k and Z h,k are defined as follows

Note that

Here, (a) holds by replacing k n (s k h , a k h ) with l and gathering all terms that involve V ⋆ h+1 -V l h+1 ; in the last line, we have invoked the property

) together with the fact V ⋆ h+1 -V l h+1 ≥ 0 (see Lemma 12), and have further replaced l with k. With the above relation in hand, in order to verify equation 93, we further decompose A h into several terms

where (a) follows from equation 94.

As a result, it remains to control

) separately in the following.

Step 1: controlling K k=1 (A h,k -Y h,k ). We shall first control this term by means of Lemma 11. Specifically, consider

which satisfies

Here, we use the fact that η

N k h n = 1 (see equation 56 and equation 58). Then, applying Lemma 11 with equation 96, we have with probability at least 1 -δ, the following inequality holds true

where the last inequality is from

Step 2: controlling

and let us consider

(101) Similarly, in view of Lemma 11, we can show that with probability at least 1 -δ,

Step 3: putting all this together. Substitution results in equation 98 and equation 102 back into equation 95 completes the proof of equation 93 as follows

This hence completes the proof.

Lemma 14.

D.3 PROOF OF THEOREM 2

We then proceed to the proof. Theorem 15. (Restatement of Theorem 2) Consider any δ ∈ (0, 1). Suppose that the behavior policy µ satisfies Assumption 1. There exists some universal constant c a , such that if we set ι := log SAT δ and set T > SC ⋆ ι, then the policy π returned by Algorithm 1 satisfies

with probability at least 1 -δ.

Proof. For any state-action pair (s, a), according to the update rule specified in Algorithm 1, we have

where the first identity holds because k N k h denotes the most recent episode before k that visits (s, a) at step h, and the learning rate is defined as in equation 55. Note that k > k N k h always holds. Applying the above relation recursively and using the notation defined in equation 56, we obtain

Applying Lemma 12, the optimality gap term equation 104 can be decomposed as follows

where (a) follows from Lemma 12 (i.e., V π K 1 (s) ≥ V K 1 (s) for all s ∈ S), (b) results from the monotonicity property in Lemma 12, and the final equality holds because d π ⋆ 1 (s) = ρ(s). We then bound the right-hand side of equation 107. Since π ⋆ is a deterministic policy, d π ⋆ P,h (s) = d π ⋆ P,h (s, π ⋆ (s)). And from the fact that

for any h ∈ [H], where the last identity holds because

To further bound the term a) in equation 108, we first adapt equation 58 and have that

where the second line follows from the robust Bellman's optimality equation. Combining equation 106 and equation 110 implies that

where (a) is from Lemma 6 and the definition of

), and the last inequality follows from the fact

and equation 71 in Lemma 12. Plug equation 112 in equation 108, we have that K k=1 s∈S

We then bound the last term on the right-hand side of equation 113. By applying Lemma 13, it implies that K k=1 s∈S

Recursively applying equation 114 over the time steps

Finally, to bound the right-hand side of equation 115, we combine Lemma 14 and equation 107, which yields

for some sufficiently large constant c a > 0, where the last inequality is valid as long as T > SC ⋆ ι.

This hence completes the proof of Theorem 2.

For any integer

We then present the following lemma to establish an upper bound on Q ⋆ -Q t , and simultaneously justify that the value function estimate V t is always a pessimistic view of V πt (and hence V ⋆ ). Lemma 17. With probability exceeding 1 -δ, for all s ∈ S and t ∈ [T ], it holds that

where n = n t (s, π ⋆ (s)) and we define

in addition, we also have

Proof. Proof of equation 121. Consider any given pair (s, a) ∈ S × A and denote n = n t (s, a), the total number of times that (s, a) has been visited prior to time t. Set k 0 = -1, and let

for each 1 ≤ i ≤ T . Clearly, each k i is a stopping time. In view of the update rule, we have

which together with the robust Bellman optimality equation gives

the proof of this claim ( 127) is deferred to later. As a consequence, for every s ∈ S and t ∈ [T ], there exists j(t) ∈ [t] such that

≥ min γ σ s,π j(t) (s) (V πt ) -σ s,π j(t) (s) (V t ) , 0 .

Here, (a) and (b) hold since the update rule asserts that there must exist some j(t) ≤ t such that

) and π t (s) = π j(t) (s); (c) utilizes (127); and (d) follows from the monotonicity of V t in t (by construction). By setting

we can deduce that

which together with the assumption 0 < γ < 1 immediately gives

for every s ∈ S, we conclude the proof.

Now we show equation 127. First of all, if n t s, π t (s) = 0, then for all j ∈ [t], Q j s, π t (s) = 0 since it is never updated; therefore, (127) holds true. From now on, we shall only focus on the case when n t s, π t (s) ≥ 1.

Consider any s ∈ S, t ∈ [T ] and j ∈ [t]. For the moment, let us define {k i } T i=1 w.r.t. the state-action pair s, π t (s) in the same way as (123). We can then repeat the argument in (124) to decompose

Lemma 18. (Lemma 3 in (Yan et al., 2022))With probability exceeding 1 -δ, we have

Lemma 19. (Lemma 5 in (Yan et al., 2022)) We can construct an auxiliary set of random variables s i k , a i k : 1 ≤ k ≤ K -1 satisfying

∼ µ b , (130a)

and s i k , a i k is independent of (s t , a t ) : 0 ≤ t ≤ (k -1) τ + i .

Lemma 20. (Lemma 4 in (Yan et al., 2022)) Let Γ = 4 1-γ log ST δ for some 0 < δ < 1. For any vector with non-negative entries V ∈ R d , we have

E.4 PROOF OF THEOREM 3

Following (Yan et al., 2022), we similarly define the following terms first:

θ j := γ 1 + 1 Γ 3 j T t=1 s∈S ρ(P π ⋆ ) j s, π ⋆ (s) min β nt(s,π ⋆ (s)) s, π ⋆ (s) , 1 1 -γ , ξ j := γ 1 + 1 Γ 3 j t mix (δ) t=1 ρ(P π ⋆ ) j , V ⋆ -V t + γ 1 + 1 Γ 3 j+1 ρ(P π ⋆ ) j+1 , V ⋆ -V 0 , ψ j := γ 1 + 1 Γ

3 j T t=t mix (δ) s∈S,a∈A ρ π ⋆ (P π ⋆ ) j (s, a) nt(s,a) i=1 η nt(s,a) i P s,a V ⋆ -V ki(s,a) -1 + 1 Γ ρ π ⋆ (P π ⋆ ) j (s t , a t ) µ b (s t , a t ) nt(st,at) i=1 η nt(st,at) i P st,at V ⋆ -V ki(st,at) , ϕ j := γ j+1 1 + 1 Γ 3j+2 T t=0 1 (st,at)∈I ρ π ⋆ (P π ⋆ ) j (s t , a t ) µ b (s t , a t ) P st,at (V ⋆ -V t ) -1 + 1 Γ s∈S,a∈A

where we recall the definition of I in equation 129.

We then proceed to the proof. Theorem 21. (Restatement of Theorem 3) Consider any δ ∈ (0, 1). Suppose that the behavior policy µ satisfies Assumption 2. The policy π returned by Algorithm 3 satisfies

with probability at least 1 -δ.

Proof. Note that

Here, (a) holds true according to Lemma 17; (b) follows from the monotonicity of V t in t (by construction); and (c) follows simply from the definition of α 0 . We then turn attention to bounding α 0 , towards which we observe that .

Here, the first identity holds since V ⋆ (s) = Q ⋆ s, π ⋆ (s) and 0 ≤ V ⋆ (s) -V t ≤ 1/(1 -γ) for all s ∈ S, the second line relies on the fact that V t (s) ≥ max a Q t (s, a) ≥ Q t (s, π ⋆ (s)), while the last line invokes Lemma 17. With probability exceeding 1 -δ, the first term ζ can be upper bounded by 1{(s t , a t ) ∈ I} ρ π ⋆ (s t , a t ) µ b (s t , a t ) nt(st,at) i=1 η nt(st,at) i P st,at V ⋆ -V ki(st,at) + ψ 0 + (1 + R) t mix (δ) t=1 ⟨ρ, V ⋆ -V t ⟩ + θ 0 (b) ≍ γ 1 + 1 Γ T t=t mix (δ) 1{(s t , a t ) ∈ I} ρ π ⋆ (s t , a t ) µ b (s t , a t )   n T (st,at) j=nt(st,at) η j nt(st,at)   P st,at (V ⋆ -V t ) + ψ 0 + (1 + R) t mix (δ) t=1 ⟨ρ, V ⋆ -V t ⟩ + θ 0 (c) ≤ γ 1 + 1 Γ 2 T t=0 1{(s t , a t ) ∈ I} ρ π ⋆ (s t , a t ) µ b (s t , a t ) P st,at (V ⋆ -V t ) + ψ 0

where we remind the reader of our notation ρ π ⋆ in equation 119. Here, (a) is valid (i.e., ρ(s t , a t )/µ b (s, a) is well defined for t ≥ t mix (δ)) due to Lemma 18; (b) holds by grouping the terms in the previous line; and (c) utilizes Lemma 16 and the property that V ⋆ ≥ V t (cf. Lemma 17). Therefore, we arrive at

where we have used the definition of ξ 0 . Repeat the same argument to reach α j ≤ α j+1 + ξ j + θ j + ψ j + ϕ j for all j ≥ 1. This in turn allows us to conclude that α 0 ≤ lim sup

j→∞ α j =: α + ∞ j=0 ξ j =: ξ + ∞ j=0 θ j =: θ + ∞ j=0 ψ j =: ψ + ∞ j=0 ϕ j =: ϕ .

We will then bound the terms α, ξ, θ, ψ and ϕ separately in the subsequent steps. Our proofs are similar to the ones in (Yan et al., 2022), hence we omit the repeated part.

Bounding α. The bound is similar to (Yan et al., 2022). It is first observed that α = lim sup

Bounding ξ.

By utilizing (131), it holds that

Bounding θ. Following (Yan et al., 2022), we have that Note that for any (s, a) ∈ S × A. Note that this equation exactly matches with Step 2.4 in (Yan et al., 2022), hence the remaining proof similarly follows, and is omitted here. Specifically, we have that

Bounding ϕ. Similar to (Yan et al., 2022), we can employ an analogous argument to show that ϕ can be bounded as

Now, plugging the bounds on α, θ, ψ and ϕ further implies that

(1 -γ) 3 log 2 T δ .