Distributionally Robust Reinforcement Learning with Interactive Data Collection: Fundamental Hardness and Near-Optimal Algorithms

Summary

This work deal with sample complexity of Robust MDPs. The major improvement is that, contrary to previous research that relies on generative models or pre-collected datasets, this paper focuses on RMDPs learning through interactive data collection, addressing two key challenges: distributional robustness and balancing exploration and exploitation. Three main contributions are : 1) Explaining that sample-efficient learning is unachievable without additional assumptions due to the curse of support shift, where training and testing environments may have non-overlapping distributions. 2) Introducing of the vanishing minimal value assumption for Robust Markov Decision Processes (RMDPs) with a total-variation distance robust set, assuming the minimal value of the optimal robust value function is zero, leading to a tractable case. 3) Proposing an algorithm with a provable sample complexity guarantee under this framework.

Strengths

The strengths of this paper are : 1) The paper is clearly written and ideas are well exposed. 2) Authors derive a nice lower bound with counterexample on the sample complexity of RMDPs in an online setting, and tight upper bound using extra assumptions such that vanishing minimal value assumption where TV uncertainty set can be rewritten using Radon-Nikodym derivatives. 3) The proof seems correct for me. 4) Algorithm is quite classic but make sense to derive robust policy while balancing exploration and exploitation.

Weaknesses

5) It would also be interesting to extend results for $s$- rectangular case. 6) There is no lower bound with vanishing minimal assumption to ensure that the upper bound under these assumptions is tight. 7) It would be nice to add the range of $\epsilon$ for the upper bound where sample complexity is valid or give a condition on K rather than saying "lower order term in K" 8) I think it would be interesting to gives more intuition on vanishing minimal assumption.

Questions

9) Do you think that vanishing minimal assumption is restrictive to derive Deep Robust RL algorithm ? 10) Do you think it would be possible to adapt Proposition 4.2 to other norms such as $L_p$ ? 11) To clarify thing, the main difference between generative model setting and online setting in RMDPs is to deal with support shift of kernel ? 12) I understand that KL and $\chi^2$ is a slightly different problem, does vanishing minimal assumption for KL or $\chi^2$ divergences RMDPs make sense as the definition of these divergences already impose bounded support shift of transition kernel ? 13) From a practical point of view, would the idea that sample complexity of RMDPS is smaller than MDPs (both in online and generative model setting) could lead to more sample efficient algorithms ?

Rating

6

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

No limitations.

Summary

This paper studies the learnability of the optimal policy for robust Markov decision process (RMDP) under the interactive data setting. The paper first show a fundamental hardness results which necessitates identifying a subclass of RMDPs which is actually solvable. The authors propose an algorithm whose sample complexity and regret are analyzed.

Strengths

1. The paper is well-organized and well-written. 2. The setting is meaningful and motivated. 3. The analysis is thorough. 4. The comparisons with existing works are very detailed, making the paper easy to follow.

Weaknesses

I am not aware of notable weaknesses.

Questions

1. In my understanding, this is the first **value-based** online/interactive data collection DRRL algorithm. Can authors confirm this is the case? 2. I am aware of Dong et al., 2022, and I am also aware that their proof has fatal flaws. I would like to mention that there is another actor-critic method for DRRL, Zhou et al., 2023 [1]. I believe this can also handle online interaction with the nominal model and learn a robust policy. Can the authors compare it with your work, especially about their robust critic component. 3. Assumption 4.1 is a sufficient condition for any RMDP to be solvable. Can the authors share some insights about the "gap" between this sufficient condition and a could-be necessary condition. Reference [1] ZHOU, R., LIU, T., CHENG, M., KALATHIL, D., KUMAR, P. and TIAN, C. (2023). Natural actor-560 critic for robust reinforcement learning with function approximation. In Thirty-seventh Conference561 on Neural Information Processing Systems.

Rating

7

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

No other limitations I would like to bring up.

Summary

This paper studies robust RL in a finite-horizon RMDP through interactive data collection. They give both a fundamental hardness result in the general case and a sample-efficient algorithm within tractable settings.

Strengths

1. Unlike previous work, which relies on a generative model or a pre-collected offline dataset enjoying good coverage of the deployment environment, this paper tackles robust RL via interactive data collection. 2. This paper introduces the vanishing minimal value assumption to RMDPs with a TV-distance robust set, postulating that the minimal value of the optimal robust value function is zero, which eliminates the support shift issue for RMDPs. 3. This paper proposes an algorithm with sharp sample complexity.

Weaknesses

1. This paper is purely theoretical. Although I understand the focus of this paper, but I still want to see some empirical results or even some simulations to get more insight. Moreover, an algorithm is given in this article, thus some numerical studies are required. 2. I am not sure if the Interactive Data Collection design is feasible in practice especially in some real-world problems. 3. Some more detailed discussion about the comparison between the proposed method and the baseline methods are required especially when they are designed for different cases. So maybe some numerical results are helpful.

Questions

Please see the weakness part.

Rating

5

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

No

Summary

The paper addresses the challenges in distributionally robust reinforcement learning (DRRL), particularly focusing on robust Markov decision processes (RMDPs) under the framework of interactive data collection. Unlike previous work that depends on generative models or pre-collected datasets, this study emphasizes interactive data collection where the learner refines policies through interaction with the training environment. The main contributions include identifying fundamental challenges that for total variation (TV) distance, there exists a hard RMDP that all algorithms at least need $O(KH)$ regret. In addition, by introducing a vanishing minimal value assumption to mitigate these challenges, this work proposes a sample-efficient algorithm (OPROVI-TV) with regret $O(\sqrt{\min\{H, 1/\rho\}H^2 SAK } after $K$ trajectories, which matches the results from the state-of-the-art non-robust MDP online learning and also robust MDP with generative model.

Strengths

1. This work focuses on interactive data collection for robust RL, addressing practical challenges and moving beyond reliance on generative models or pre-collected datasets, which is an underdeveloped open direction. 2. The proposed OPROVI-TV algorithm balances exploration and exploitation, providing strong guarantees for online regret and sample complexity for such robust RL problems with online settings.

Weaknesses

1. The main assumption (Assumption 4.1) that this work mainly depends on is interesting, but will such assumptions make the problems (robust MDPs with TV uncertainty set ) not a suitable and meaningful robust RL problems for those tasks? Specifically, no matter Assumption 4.1 or the fail-state assumption from [1] indeed implies that for all policy, $ \min_{s\inS} V_{h}^{\pi}(s) = 0 $ for all $h=1,2,\cdots, H$ if the reviewer does not miss something. The main concern from the reviewer is that (actually the author already discuss about this in Appendix B.4.1): For those tasks under such assumptions, if we consider robust MDPs using TV distance, will those robust MDPs directly equivalent to some non-robust MDPs but with a discounted reward (non-robust MDP with reward function $r<1-\rho/2)$. * So in such cases, will the robust RL problem using TV to construct the uncertainty set be meaningful? I think those robust formulations will reduce back to non-robust MDPs. So maybe some uncertainty set with support control (the adversarial can't make the transition kernel to be out of the support of the nominal transition kernel) will be more suitable to use in such tasks. * In addition, the reviewer believe that under Assumption 4.1, the regret of this problem can be improved to $O(\sqrt{\min\\{H, 1/\rho\\}^3 SAK}?$ Since the maximum value of the robust value function will be $\min\\{ H, 1/\rho\\}$ but not $H$ in the non-robust value function anymore. [1]Panaganti, Kishan, and Dileep Kalathil. "Sample complexity of robust reinforcement learning with a generative model." International Conference on Artificial Intelligence and Statistics. PMLR, 2022.

Questions

1. In the introduction "Given that all the existing52 literature on robust RL theory relies on a generative model or pre-collected data" Not all the existing works are using generative model or offline dataset? Such as [1]. If so, please check [1] Dong, Jing, et al. "Online policy optimization for robust mdp." arXiv preprint arXiv:2209.13841 (2022).

Rating

6

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

Well-answered

Engagement with authors

Dear Reviewer, Please engage with the authors. This is the last day a back and forth discussion is possible. The AC

Engage with authors

Dear Reviewer, Please engage with the authors. This is the last day a back and forth discussion is possible. The AC