Near-Optimal Sample Complexity of Robust Reinforcement Learning with KL Uncertainty Set

In this paper, we study distributionally robust reinforcement learning with Kullback--Leibler (KL) divergence defined uncertainty set. The goal is to find a policy that maximizes the robust value function, defined as the worst-case value over all transition kernels in the uncertainty set. Assuming access to a generative model, we aim to understand the sample complexity of finding an $\epsilon$-optimal robust policy. The best-known sample complexity results in the literature show a non-trivial gap of $\mathcal{O}\{\max\{p_\wedge^{-1}(1-\gamma)^{-1},(1-\gamma)^{-2}\}\}$ between the upper and lower bounds, where $p_\wedge$ denotes minimal non-zero support of the nominal transition kernel, and $\gamma$ is the discount factor. More importantly, existing results on the lower bound only cover a limited range of the uncertainty level. In this paper, we develop tighter and complete upper and lower bounds for robust RL with KL-defined uncertainty set. Our upper bound is the tightest among all existing studies, and it improves upon the best known bound by at least the order of $\mathcal{O}(\min\{p_\wedge^{-1},(1-\gamma)^{-1}\})$. Furthermore, our lower bound holds for any uncertainty level. Our upper and lower bounds (nearly) match under various cases, providing near minimax optimality results for this problem.