Sample Complexity of Distributionally Robust Off-Dynamics Reinforcement Learning with Online Interaction

We thank the reviewer for the positive feedback on our work. We hope our response will fully address all of the reviewer's questions.

1. Discussion on possible relaxation of Assumption 4.5

We appreciate the reviewer's insightful question and agree that Assumption 4.5 might be relaxed to require coverage only of $d^{\pi^\*}$ instead of $d^\pi$ for all $\pi$, similar to the off-policy problem. While this modification is theoretically feasible, it is not straightforward due to the dynamics shift in the deployment environment. It would likely involve revising the way we decompose the regret, leading to non-trivial changes in our current proof structure.

2. Explanation about KL bound in Theorem 4.19

As stated by Remark 4.2 in Blanchet et al. (2023), the $e^H$ dependency for KL bounds is commonly observed in the literature. This is due to the logarithmic function used in the definition of KL divergence.

3. Do you have any comments or comparisons with other existing upper bound results?

Thank you for the question. We would like to point out that no previous work has explored the exact same setting we are studying. The research Lu et al. (2024), which most closely resembles ours in the constrained TV setting, relies on a different assumption that cannot be generalized to other settings considered in our paper. Unlike their approach, we do not concentrate on one specific scenario of uncertainty sets (constrained TV setting) but instead explore the general online learning of robust MDP.

4. Intuition behind the presence of the 1/K term in the bonus functions

The $1/K$ terms in the bonus functions are not intrinsic. In the proof, we constructed $\epsilon$-nets to bound one part of the estimation, which leads to an additional term of $\mathcal{O}(\epsilon)$ or $\mathcal{O}(\sqrt{\epsilon})$, where the value of $\epsilon$ can be arbitrary. We set $\epsilon=\mathcal{O}(1/K)$ or $\epsilon=\mathcal{O}(1/K^2)$, which results in the extra $1/K$ term in the bonus. For a detailed explanation, please refer to Lemmas E.2, E.12, E.16, F.2, F.6, and F.11 respectively for the specific setting.

5. Clarification about notations such as on line 274

As defined in Definition 4.3, $P^o$ represents the nominal transition, $P^w$ represents the worst-case transition, and $P^\pi$ is the corresponding visitation measure. These are distinctly different concepts.

We hope we have addressed all of your questions/concerns. If you have any further questions, we would be more than happy to answer them.

References:

[1] Blanchet, J., Lu, M., Zhang, T., & Zhong, H. (2023). Double pessimism is provably efficient for distributionally robust offline reinforcement learning: Generic algorithm and robust partial coverage. Advances in Neural Information Processing Systems, 36, 66845-66859.

[2] Lu, M., Zhong, H., Zhang, T., & Blanchet, J. (2024). Distributionally robust reinforcement learning with interactive data collection: Fundamental hardness and near-optimal algorithm. arXiv preprint arXiv:2404.03578.

Thank you for your valuable time and effort in providing detailed feedback on our work. We hope our response will fully address all of your questions.

1. Explanation about the bounds in 3.2 and 3.3

Sections 3.2 and 3.3 present update formulas for different types of robust sets (constrained vs. regularized) and different $f$-divergences (TV, KL, and $\chi^2$). Although these updates all follow a similar pattern--applying an optimism-based principle and a robust Bellman operator--their specific forms differ because the dual formulations vary across robust set types and divergence measures. Hence, the resulting $Q$-function estimates and bonus terms change accordingly.

We have outlined the final equations for the updates in Sections 3.2 and 3.3 due to space constraints, but we agree that more in-depth explanation would help clarify how each term arises from the respective dual formulation. We plan to include further details in the final version of the paper to make the derivations and resulting bounds more transparent.

2. Proof sketch of this paper

We summarize the core proof idea as follows.

For the upper bounds, we decompose the regret as $\text{Regret}=\sum\limits_{k=1}^K\big(V_1^{\*,\rho}-V_1^{{\pi^k},\rho}\big)=\sum\limits_{k=1}^K\big(V_1^{\*,\rho}-V_1^{k,\rho}\big)+\sum\limits_{k=1}^K\big(V_1^{k,\rho}-V_1^{{\pi^k},\rho}\big)$.

We use the dual formulation to estimate $V$ and add an extra bonus term to maintain an optimistic estimate, ensuring that the first term is less than zero. From the definition of $V^k$, it follows that the second term can be controlled by $\sum\limits_{k=1}^K\sum\limits_{h=1}^H\mathbb{E}\_{\\{P_h^{w,k}\\}_{h=1}^H,\pi^k}\big[2\text{bonus}_h^k\big]$. The cumulative bonus is of an order not larger than $\sqrt{K}$, as derived from the concentration inequalities.

For the lower bounds, we construct a key state that is difficult to explore in the nominal environment but easier to explore in the perturbed environment. Consequently, insufficient knowledge about this key state can lead to significant regret.

We will add the proof sketch in the final version.

3. The text display on the third page

We believe this might be due to the floating environment in LaTeX.

4. Further clarifications on experiment setup and observed performance

In the case of $C_{vr}$, we constructed a well-designed MDP environment where the hyperparameter $\beta$ allows for adjustments to the value of $C_{vr}$ to observe performance changes. However, the $\frac{1}{2}$ order dependency on $C_{vr}$ represents merely a worst-case bound. Furthermore, the regret formulations incorporate additional terms, so we do not anticipate results to be strictly proportional to $\sqrt{C_{vr}}$. Here, we merely demonstrate a general positive correlation to validate our intuition, akin to an ablation study.

Regarding $S$, $A$, and other variables, they are not the primary focus within this topic. The crucial parameters here are $K$ (indicating efficient learning of the problem) and $C_{vr}$ (demonstrating that $C_{vr}$ is a precise metric for the difficulty of the environment). Unlike $C_{vr}$, which is relatively easier to manipulate, altering the values of $S$ and $A$ would lead to a complete structural change in the environment. Given that our environment is specifically designed, it is challenging to introduce $S$ and $A$ as variables into the existing problem.

To answer the reviewer's question, we have conducted a new experiment on the Gambler's Problem (inspired by Panaganti et al., 2022, Section 6). We set the heads-up probability to $p_h=0.6$ for the nominal environment and $p_h=0.4$ for the perturbed environment. We applied the constrained TV setting with $H=30$ and varied the size of $S$ from 15 to 55, reporting the results across 10 training runs as shown in the following table. This demonstrates that performance deteriorates as the sizes of $S$ and $A$ increase.

5. Explanation about performance under minimal perturbation in Figure 1

As is well-known in robust reinforcement learning, algorithms designed to hedge against large uncertainties naturally trade off some performance in near-nominal settings. Therefore, while ORBIT typically outperforms non-robust approaches under significant perturbations, it may appear less effective when perturbations are small or absent because it prioritizes worst-case scenarios over short-term gains.

We hope we have addressed all of your questions/concerns. If you have any further questions, we would be more than happy to answer them.

References:

[1] Panaganti, K., & Kalathil, D. (2022, May). Sample complexity of robust reinforcement learning with a generative model. In International Conference on Artificial Intelligence and Statistics (pp. 9582-9602). PMLR.

We thank the reviewer for the positive feedback on our work. We hope our response will fully address all of the reviewer's questions.

1. The key insights from Figure 2

The primary purpose of Figure 2 is to show that our algorithm converges stably by the end of training in a fixed environment, rather than to compare performance under different ambiguity sets. In the Frozen Lake experiment, our main goal is to highlight the algorithm’s robustness, specifically its ability to handle worst-case scenarios effectively.

2. How should one decide which ambiguity set to use?

As depicted in Figure 3(a), the computational costs vary with different ambiguity settings, where the regularized setting generally proves to be more computationally efficient than the constrained setting. Selecting an appropriate ambiguity set (TV v.s. KL v.s. $\chi^2$) may be specific to the application and the structure of the problem. For hyperparameters like the radius or the regularization parameters, we can select them via hyperparameter tunning based on empirical performance.

3. Can you better motivate the specific choice of ambiguity sets?

Our primary goal is to study the general online robust problem. We focus on these three ambiguity sets because they are widely used and extensively investigated in the reinforcement learning literature (Panaganti & Kalathil, 2022; Yang et al., 2022; Xu et al., 2023; Shi et al., 2024), enabling more direct comparisons with existing studies.

4. Could you also include the popular Wasserstein or MMD ambiguity set?

Thanks for the great suggestion! Our algorithm has the potential to be adapted to these two ambiguity sets since we address the general online robust problem. However, this adaptation might require additional analysis, as these ambiguity sets lack a closed-form dual formulation, posing challenges for direct application of our current algorithm. This will be a great future direction on online robust MDPs.

5. Can you also handle those non-rectangular ambiguity sets?

Non-rectangular ambiguity sets differ fundamentally from those discussed in this paper, and our algorithm is not equipped to handle these due to their inherent complexity. To our knowledge, nearly all studies in the robust MDP literature use rectangular ambiguity sets. Moreover, Wiesemann et al. (2013) showed that solving DRMDPs with general uncertainty sets can be NP-hard. We therefore identify this as an open problem for future research.

We hope we have addressed all of your questions/concerns. If you have any further questions, we would be more than happy to answer them.

References:

[1] Panaganti, K., & Kalathil, D. (2022, May). Sample complexity of robust reinforcement learning with a generative model. In International Conference on Artificial Intelligence and Statistics (pp. 9582-9602). PMLR.

[2] Yang, W., Zhang, L., & Zhang, Z. (2022). Toward theoretical understandings of robust markov decision processes: Sample complexity and asymptotics. The Annals of Statistics, 50(6), 3223-3248.

[3] Xu, Z., Panaganti, K., & Kalathil, D. (2023, April). Improved sample complexity bounds for distributionally robust reinforcement learning. In International Conference on Artificial Intelligence and Statistics (pp. 9728-9754). PMLR.

[4] Shi, L., Li, G., Wei, Y., Chen, Y., Geist, M., & Chi, Y. (2023). The curious price of distributional robustness in reinforcement learning with a generative model. Advances in Neural Information Processing Systems, 36, 79903-79917.

[5] Wiesemann, W., Kuhn, D., & Rustem, B. (2013). Robust Markov decision processes. Mathematics of Operations Research, 38(1), 153-183.

Thank you for your valuable time and effort in providing detailed feedback on our work. We hope our response will fully address all of your questions.

1. The definitions of $P_h^\pi$ and $d_h^\pi$ in Assumption 4.5

The definitions are provided in Definition 4.3, where $P_h^\pi$ represents the visitation measure under the worst-case scenario, and $d_h^\pi$ represents the visitation measure in the nominal environment, both are defined to be induced by the policy $\pi$.

2. Comparison of ORBIT with algorithms in Liu and Xu (2024a) and Lu et al. (2024)

All three works investigate the online robust MDP setting using value-iteration-based methods. In particular, Liu and Xu (2024a) focuses on the linear function approximation regime, whereas Lu et al. (2024) and our work consider the tabular setting. However, Liu and Xu (2024a) and Lu et al. (2024) address only the constrained TV-divergence scenario. In contrast, our study addresses a broader range of online robust problems, including robust sets defined by three different $f$-divergences, as well as constrained RMDP and regularized RMDP, the latter of which was not considered in their work. Consequently, our algorithm provides distinct update formulations and bonus terms across six settings.

3. Discussion on the average training time for $\chi^2$ cases in Figure 3(a)

Lemmas E.15 and F.10 reveal that deriving the dual formulation for the $\chi^2$ update requires solving a multi-dimensional optimization problem, which leads to longer training times. In contrast, the constrained KL setting (Lemma E.11) relies only on one-dimensional optimization. Furthermore, for constrained TV (as illustrated in Algorithm 2), regularized TV (Lemma F.1), and KL settings (Lemma F.5), the optimization problems have closed-form solutions. This is why the average training time for $\chi^2$ cases is significantly longer.

4. Is it correct that the fail-state conditions 4.1 and 4.2 are special cases of bounded visitation measure ratio?

No, our assumptions do not imply theirs, nor do theirs imply ours. The fail-states condition was specifically designed for the constrained TV robust sets, as explained in Proposition 4.4. In contrast, our assumption addresses the general online robust problem and is applicable to various other $f$-divergence robust sets.

We hope we have addressed all of your questions/concerns. If you have any further questions, we would be more than happy to answer them.

References:

[1] Liu, Z., & Xu, P. (2024, April). Distributionally robust off-dynamics reinforcement learning: Provable efficiency with linear function approximation. In International Conference on Artificial Intelligence and Statistics (pp. 2719-2727). PMLR.

[2] Lu, M., Zhong, H., Zhang, T., & Blanchet, J. (2024). Distributionally robust reinforcement learning with interactive data collection: Fundamental hardness and near-optimal algorithm. arXiv preprint arXiv:2404.03578.