# Provably Efficient Q-learning for Robust Reinforcement Learning

Preprint · Yuchen Jiao, Gen Li

- Archive id: arxiv:2610.35656
- Published: 2026-10-26
- arXiv: https://arxiv.org/abs/2610.35656
- Citations: 0
- Source URL: https://arxiv.org/abs/2610.35656
- PDF: https://arxiv.org/pdf/2610.35656
- Provenance: arxiv

## 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 $\\mathcal{S}$ and action space $\\mathcal{A}$, 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 $\\varepsilon$-approximation of the optimal Q-function --- is bounded by $$ \\frac{1}{μ\_{\\mathsf{min}}\\varepsilon^2(1-γ)^3\\max\\{1-γ,σ\\}} + \\frac{t\_{\\mathsf{mix}}}{μ\_{\\mathsf{min}}(1-γ)} $$ up to logarithmic factors. Here, $t\_{\\mathsf{mix}}$ and $μ\_{\\mathsf{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 $\\frac{1}{1-γ}$. Moreover, it achieves a significant improvement over existing bounds.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

Topics: [Robot Learning & Embodied AI](https://space-kitty.com/topics/robotics-embodied)

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.