Towards Theoretical Understandings of Robust Markov Decision Processes: Sample Complexity and Asymptotics

Abstract

In this paper, we study the non-asymptotic and asymptotic performances of the optimal robust policy and value function of robust Markov Decision Processes(MDPs), where the optimal robust policy and value function are solved only from a generative model. While prior work focusing on non-asymptotic performances of robust MDPs is restricted in the setting of the KL uncertainty set and $(s,a)$-rectangular assumption, we improve their results and also consider other uncertainty sets, including $L_1$ and ${\chi }^2$ balls. Our results show that when we assume $(s,a)$-rectangular on uncertainty sets, the sample complexity is about $\tilde{O}\left(\frac{|\mathcal{S}{|}^2|\mathcal{A}|}{{\epsilon }^2{\rho }^2(1-\gamma {)}^4}\right)$. In addition, we extend our results from $(s,a)$-rectangular assumption to $s$-rectangular assumption. In this scenario, the sample complexity varies with the choice of uncertainty sets and is generally larger than the case under $(s,a)$-rectangular assumption. Moreover, we also show that the optimal robust value function is asymptotic normal with a typical rate $\sqrt{n}$ under $(s,a)$ and $s$-rectangular assumptions from both theoretical and empirical perspectives.

References in corpus (17)

• Continuous control with deep reinforcement learning
• Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor
• Minimax Statistical Learning with Wasserstein Distances
• Towards Optimal Off-Policy Evaluation for Reinforcement Learning with Marginalized Importance Sampling
• Information-Theoretic Considerations in Batch Reinforcement Learning
• What are the Statistical Limits of Offline RL with Linear Function Approximation?
• Batch Value-function Approximation with Only Realizability
• Is Pessimism Provably Efficient for Offline RL?
• Near-Optimal Provable Uniform Convergence in Offline Policy Evaluation for Reinforcement Learning
• CoinDICE: Off-Policy Confidence Interval Estimation
• Distributionally Robust Reinforcement Learning
• Distributional Robustness and Regularization in Reinforcement Learning
• Risk Bounds and Rademacher Complexity in Batch Reinforcement Learning
• Partial Policy Iteration for L1-Robust Markov Decision Processes
• Approximate Dynamic Programming By Minimizing Distributionally Robust Bounds
• Optimizing Percentile Criterion Using Robust MDPs
• On the Optimality of Batch Policy Optimization Algorithms