Provably Efficient Q-learning for Robust Reinforcement Learning
Abstract
Standard reinforcement learning (RL) algorithms based on Markov Decision Processes (MDPs) are vulnerable to sim-to-real gaps. To address this issue, distributionally robust RL algorithms based on robust MDPs (RMDPs) have been proposed, for ensuring that agents can perform reliably to unpredictable conditions in real-world environments. Despite of the rich literature, \revision{an efficient model-free method is still lacking} for robust RL, particularly for Markovian data, which is more relevant in practical applications. In this work, we take a step towards settling this problem by proposing a sample efficient (asynchronous Q-learning) algorithm for robust RL. In particular, consider a γ-discounted infinite-horizon RMDP with state space 𝒮 and action space 𝒜, where the uncertainty set is specified by the total variation (TV) distance with uncertainty level σ. Assuming access to a single trajectory of Markovian samples induced by a behavior policy and the nominal transition kernel, the sample complexity of the proposed Q-learning algorithm --- to achieve an entrywise ε-approximation of the optimal Q-function --- is bounded by 1/(μminε2(1−γ)3max{1−γ,σ}) + tmix/(μmin(1−γ)) up to logarithmic factors. Here, tmix and μmin denote the mixing time and the minimum state-action occupancy probability of the sample trajectory, respectively. This result is nearly minimax optimal, with an additional factor of 1/(1−γ). Moreover, it achieves a significant improvement over existing bounds.
Related
- Provably Efficient Federated Reinforcement Learning with Linear Function Approximation and Logarithmic Communication Cost
- Provably Efficient Risk-Sensitive Offline Reinforcement Learning via Optimized Certainty Equivalents
- Distributionally Robust Average-Reward Reinforcement Learning: Finite-Sample Guarantees under Weak Communication
- Distribution-Agnostic Robust Trajectory Optimization via Chance-Constrained Reinforcement Learning
- Efficient Joint Trajectory Optimization and Resource Allocation for Secure UAV Networks: A Deep Reinforcement Learning Approach
BibTeX
@misc{jiao2026provably,
title = {{Provably Efficient Q-learning for Robust Reinforcement Learning}},
author = {Yuchen Jiao and Gen Li},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.35656},
eprint = {2610.35656},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.35656},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Provably Efficient Q-learning for Robust Reinforcement Learning
AU - Yuchen Jiao
AU - Gen Li
PY - 2026
DA - 2026/10/26
PB - arXiv
DO - 10.48550/arxiv.2610.35656
UR - https://arxiv.org/abs/2610.35656
AB - Standard reinforcement learning (RL) algorithms based on Markov Decision Processes (MDPs) are vulnerable to sim-to-real gaps. To address this issue, distributionally robust RL algorithms based on robust MDPs (RMDPs) have been proposed, for ensuring that agents can perform reliably to unpredictable conditions in real-world environments. Despite of the rich literature, \revision{an efficient model-free method is still lacking} for robust RL, particularly for Markovian data, which is more relevant in practical applications. In this work, we take a step towards settling this problem by proposing a sample efficient (asynchronous Q-learning) algorithm for robust RL. In particular, consider a γ-discounted infinite-horizon RMDP with state space 𝒮 and action space 𝒜, where the uncertainty set is specified by the total variation (TV) distance with uncertainty level σ. Assuming access to a single trajectory of Markovian samples induced by a behavior policy and the nominal transition kernel, the sample complexity of the proposed Q-learning algorithm --- to achieve an entrywise ε-approximation of the optimal Q-function --- is bounded by 1/(μ_minε^2(1−γ)^3max{1−γ,σ}) + t_mix/(μ_min(1−γ)) up to logarithmic factors. Here, t_mix and μ_min denote the mixing time and the minimum state-action occupancy probability of the sample trajectory, respectively. This result is nearly minimax optimal, with an additional factor of 1/(1−γ). Moreover, it achieves a significant improvement over existing bounds.
ER -