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

We thank the reviewer for the helpful and insightful feedback. In the following, we provide point-to-point responses to the weaknesses and questions.

Question 1. Empirical performance in tabular environments We first refer the reviewer to Section A of the appendix, where we compare our algorithms with two baselines. Additional results for large environments are provided in the rebuttal PDF, Fig. 2. Our method outperforms the non-robust method and demonstrates performance similar to the LCB approach [35], consistent with our theoretical results. Furthermore, as shown in Fig. 1 of the rebuttal PDF, in the tabular setting, our algorithms have a lower execution time and computational complexity than the LCB baseline. Hence we claim that our algorithms perform better than the baselines under tabular environments.

It is also important to note that there is no practical implementation of the baseline [5] due to the NP-hardness of their models. Consequently, we did not include a comparison with [5] (please also see our response to Reviewer 2 Weakness 2).

Weakness & Q2. Extend to practical settings. We want to emphasize that our major contribution is to develop a methodological framework for offline RL with model mismatch, which incorporates both uncertainties from the limited dataset and model mismatch as a single distributional uncertainty set and tackles them through a unified DRO framework. To better illustrate our novelty and technique contributions, we present our results in the tabular setting, where we show the sample complexity of our algorithms improves upon or matches the SOTA.

However, our method can be easily extended to large-scale problems with function approximation. For example, in d-rectangular robust linear MDPs [26,5], the nominal transition kernel is the inner product of some d-dimensional feature functions $\phi$ and a d-dim vector $\theta$: $\mathsf{P}^a_{s,s'}=\phi(s,a)^\top \theta_{s'}$. The uncertainty set for the model mismatch is set as $\mathcal{P}=\\{(\phi(s,a)^\top \tau_{s'}): D(\theta_i,\tau_i)\leq R, i\leq d\\}$. Our method can be adapted to solve offline robust linear MDP problems. Specifically, after estimating the parameter $\hat{\theta}$ from the offline dataset as in [5], we can design a similar enlarged uncertainty set $\tilde{\mathcal{P}}=\\{(\phi(s,a)^\top \tau_{s'})_{s,a,s'}: D(\hat{\theta}_i,\tau_i)\leq R+\kappa_i \\}$, where $\kappa_i$ is some enlarged term that accounts for the uncertainty of the dataset. Hence our method will result in a standard robust linear MDP formulation, which can be solved as in [26].

Our method can be further extended to robust MDPs with latent structure or function approximation. Specifically, the nominal transition kernel can be represented or approximated by some parameter function $\mathsf{P}\approx f_\theta$, and the robust MDP for the model mismatch will be set as $\mathcal{P}=\\{ f_{\theta'}: D(\theta,\theta')\leq R\\}$. Similarly, after estimating the parameter $\hat{\theta}$ from the dataset and designing a dataset dependent term $\kappa$, solving the enlarged robust MDP $\mathcal{P}=\\{ f_{\theta'}: D(\hat{\theta},\theta')\leq R+\kappa\\}$ will result in a policy tackling both two sources of uncertainty. Also, it is worth mentioning that such a robust MDP can be solved empirically using adversarial training approaches, as in [a,b].

Another extension to make our method more practical is to design model-free algorithms for our DRO formulation. Unlike the model-based approach presented in our paper, model-free algorithms do not require the model estimation or solving the Bellman equation but can directly learn the optimal policy in an online bootstrapping fashion, making them more suitable for large-scale problems. Existing robust Q-learning algorithms, e.g., [c,d], can be directly adapted by setting the uncertainty set radius to $R+\kappa$ and solving our formulation, which further makes our method more practical.

To verify that our method can also be extended to practical settings, we further implement a model-free robust Q-learning as described in [c] to solve the American Option environment ([c], [64]) in the offline setting. For each dataset, we ran the robust Q-learning algorithm with the uncertainty set constructed as described in our paper and plotted the robust value function of the learned policy. The results, presented in Fig. 3 of the rebuttal PDF, demonstrate that our method can be combined with model-free algorithms to effectively solve offline problems under model mismatch, particularly for large-scale problems. We will add more discussion in our paper.

[a] Rigter, Marc, et al. "Rambo-rl: Robust adversarial model-based offline reinforcement learning." Advances in neural information processing systems 35 (2022): 16082-16097.

[b] Pinto, Lerrel, et al. "Robust adversarial reinforcement learning." International conference on machine learning. PMLR, 2017.

[c] Liang, Zhipeng, et al. "Single-trajectory distributionally robust reinforcement learning." arXiv preprint arXiv:2301.11721 (2023).

[d] Liu, Zijian, et al. "Distributionally Robust $Q$-Learning." International Conference on Machine Learning. PMLR, 2022.

We thank the reviewer for the helpful and insightful feedback. In the following, we provide point-to-point responses to the weaknesses and questions.

Weakness 1. Experiment results on more complex and diverse benchmarks. We further provide two more experiments on large-scale environments in the rebuttal PDF. We implement our algorithm with the two baselines under the KL divergence uncertainty set.

In this rebuttal, we further add the results under the Garnet problem G(64,16) [a] in Fig 2(a), where there are 64 states and 16 actions. The transition kernels and reward functions are generated following some Gaussian distribution $\mathcal{N}(\mu_{s,a},\sigma_{s,a})$. The comparison under the N-Chain problem is presented in Fig 2(b). And the results under the Cartpole problem are in Fig 2(c). We also implement a model-free algorithm under the American Option problem in Fig 3, where no model estimation is required, indicating the potential of our method in solving large-scale problems.

As the results show, our method performs similarly to the LCB algorithm, aligning with our theoretical results. Moreover, our approach also shows a great improvement compared to the non-robust method, which verifies the robustness of our method.

We will include more experiments under different environments and uncertainty sets in the final version.

Weakness 2. Computational cost. Our algorithms are 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 [41] to the robust setting, both involving non-rectangular uncertainty sets that are NP-hard to solve [49]. This creates uncertainty regarding the solvability of their models. Specifically, due to the unsolvability of the non-robust model in [41], an adversarial training-based algorithm is designed in [b] with only an experimental convergence guarantee, highlighting the implementation challenges of [5]. In contrast, our algorithm can be implemented with polynomial complexity. Specifically, the total computational complexity of our algorithm under the TV, CS, and KL models is shown in [13] to be $\mathcal{O}(S^2A\log S)$,$\mathcal{O}(S^2A\log S)$, and $\tilde{\mathcal{O}}(S^2A)$.

Compared to [35], our algorithms also offer better computational complexity. Specifically, the penalty term in [35] requires a complicated computation involving a minimum operator, resulting in an additional max-min structure in their algorithm update. The comparison/max-min operator in the LCB algorithm is executed $SA$ times per step, significantly increasing computational complexity. In contrast, our algorithms have a simple structure and do not require additional operators, making them more computationally efficient.

To illustrate our computational efficiency, we include numerical experiments in the rebuttal PDF. We implemented the LCB algorithm from [35] and our DRO algorithm under the KL model, monitoring the execution time of both methods while learning the same policy from the same dataset. We plotted the execution time for each dataset versus the size of the dataset in three environments: Gambler's game, Frozen Lake, and N-chain. As shown in Fig. 1, our algorithm consistently requires less execution time across all three environments, demonstrating lower computational complexity.

Therefore, our methods exhibit superior computational complexity compared to both baselines.

[a] Archibald, T. W., et al. "On the generation of markov decision processes." Journal of the Operational Research Society 46.3 (1995): 354-361. [b] Rigter, Marc, et al. "Rambo-rl: Robust adversarial model-based offline reinforcement learning." Advances in neural information processing systems 35 (2022): 16082-16097.

We thank the reviewer for the helpful and insightful feedback. In the following, we provide point-to-point responses to the weaknesses and questions.

Weakness 1. Advantages compared to [5] and [35]. In summary, our method has three major advantages compared to both baselines. Firstly, our work is applicable under three different uncertainty set models, whereas [35] is limited to the KL model and [5] addresses only the KL and TV models (please see Weakness 2 for further discussion). Secondly, our algorithms achieve better sample complexity results compared to [5], and match the SOTA complexity under the KL model in [35] (please see discussion in Weakness 1-1). Finally, our algorithms demonstrate superior computational complexity compared to both baselines, and are the most efficient (please also see Weakness 3).

These improvements further strengthens our paper, highlighting our novelty and contributions.

Weakness 1-1. Comparison of sample complexity with [5] and [35]. We refer to Table 1 on page 8 for a comparison of the sample complexity results between ours and the two baselines. A more detailed comparison is provided below.

Compared with [5], our methods and results achieve better sample complexity in both KL and TV models. In the TV model, our sample complexity outperforms [5] in terms of dependence on $S$ and $(1-\gamma)$; For the KL model, our complexity is linearly dependent on $S$, while [5] has a quadratic dependence. Furthermore, as noted in [5], their result's exponential term can be replaced by utilizing both $P_{\min}$ and $\mu_{\min}$, while our (asymptotic) complexity result depends solely on $P_{\min}$.

Our results match exactly those of [35] in the KL model, indicating that we are achieving SOTA. Additionally, we provide results for two other models, which cannot be obtained directly using the algorithm in [35] (also see Weakness 2).

Weakness 2. Extension of baselines to other models. Although extending the method in [5] may seem straightforward at first glance, the concrete extension requires additional effort. More importantly, the extended sample complexity result under the CS uncertainty set is also expected to be proportional to $S^2$, similar to the results under the other two models, whereas our method exhibits a linear dependence on $S$. This difference arises because the method in [5] is distribution-based, designing the first-level uncertainty set to cover the true nominal kernel, which results in worse complexity than ours (a more detailed discussion can be found in [46]).

In [35], the LCB-based algorithm is only designed for the KL model and requires additional efforts to extend to other models. Specifically, a careful study of the optimal solution to the corresponding DRO problem is needed to design the penalty term, ensuring a pessimistic estimation of the robust value functions. In contrast, our method can be directly applied from a uniform framework under all three uncertainty sets.

Weakness 3. Computational complexity comparison. Our algorithms enjoy better computational complexity than both baselines.

The two-layer optimization problem in [5] is an extension of the model studied in [41] to the robust setting, both involving non-rectangular uncertainty sets that are NP-hard to solve [49]. This creates uncertainty regarding the solvability of their models. Specifically, due to the unsolvability of the non-robust model in [41], an adversarial training-based algorithm is designed in [a] with only an experimental convergence guarantee, highlighting the implementation challenges of [5]. In contrast, our algorithm can be implemented with polynomial complexity. Specifically, the total computational complexity of our algorithm in the TV, CS and KL models is shown in [13] to be $\mathcal{O}(S^2A\log S)$,$\mathcal{O}(S^2A\log S)$, and $\tilde{\mathcal{O}}(S^2A)$.

Compared to [35], our algorithms also offer better computational complexity. Specifically, the penalty term in [35] requires a complicated computation involving a minimum operator, resulting in an additional max-min structure in their algorithm update. The comparison/max-min operator in the LCB algorithm is executed $SA$ times per step, significantly increasing computational complexity. In contrast, our algorithms have a simple structure and do not require additional operators, making them more computationally efficient.

To illustrate our computational efficiency, we include numerical experiments in the rebuttal PDF. We implemented the LCB algorithm from [35] and our DRO algorithm under the KL model, monitoring the execution time of both methods while learning the same policy from the same dataset. We plotted the execution time for each dataset versus the size of the dataset in three environments: Gambler's game, Frozen Lake, and N-chain. As shown in Fig. 1, our algorithm consistently requires less execution time across all three environments, demonstrating lower computational complexity.

Therefore, our methods exhibit superior computational complexity compared to both baselines.

[a] Rigter, Marc, et al. "Rambo-rl: Robust adversarial model-based offline reinforcement learning." Advances in neural information processing systems 35 (2022): 16082-16097.

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!