Optimal Sample Complexity for Robust Reinforcement Learning

This direction is merged into another direction: function approximation scalability. Its last version stays readable and citable here.

Version 1 of 125 papers27 conceptsfrozen 2026-10-04

Standard reinforcement learning (RL) operates under a "closed-world" assumption: the environment where an agent trains is identical to the one where it will be deployed. In practice, this assumption is frequently violated. A robot trained in a friction-less simulation may fail on a carpeted floor, and a trading agent may collapse when market volatility shifts. This discrepancy is known as the sim-to-real gap.

To bridge this gap, researchers have turned to Distributionally Robust Reinforcement Learning (DRRL). Instead of optimizing for a single Markov Decision Process (MDP), DRRL agents optimize for the worst-case scenario within a set of possible environments, known as an uncertainty set. While intuition suggests that preparing for the worst should be computationally or statistically expensive, a surge of recent theoretical work demonstrates that robustness can be achieved with the same efficiency as standard RL.

The Robustness Dividend

A common misconception is that robustness requires a "price" in terms of sample complexity. However, Gen Li and colleagues in Tightening the Dependence on Horizon in the Sample Complexity of Q-Learning showed that even vanilla Q-learning is more efficient than previously thought. Building on this, Yue Wang and Shaofeng Zou demonstrated in Online Robust Reinforcement Learning with Model Uncertainty that robust versions of Q-learning and Temporal Difference (TD) control can converge just as fast as their non-robust counterparts.

In some cases, robustness actually provides a "dividend." Pierre Clavier and Adam Wierman found in Near-Optimal Distributionally Robust Reinforcement Learning with General $L_p$ Norms that when environmental uncertainty is high, solving for a robust policy can actually require fewer samples than standard RL. This happens because the robust objective effectively regularizes the learning process, preventing the agent from over-fitting to noise in the training simulator.

Solving the Curse of Support Shift

A major hurdle in online robust learning is the "curse of support shift." If the training environment never exposes the agent to certain states, but those states become critical in a shifted real-world environment, the agent cannot learn how to behave. Miao Lu and Tong Zhang explored this in Distributionally Robust Reinforcement Learning with Interactive Data Collection: Fundamental Hardness and Near-Optimal Algorithms, proving that without specific assumptions, efficient online robust learning is impossible.

To overcome this, researchers developed algorithms like ORVIT and f-ORVIT. Debamita Ghosh and George K. Atia showed in ORVIT: Near-Optimal Online Distributionally Robust Reinforcement Learning that by using optimistic planning within $f$-divergence uncertainty sets, agents can achieve sublinear regret. This means the agent's performance gap relative to the optimal robust policy vanishes as it collects more data, even without a pre-existing dataset or a generative simulator.

Robustness Across the RL Spectrum

The drive toward optimal robust complexity spans various RL architectures:

Why It Works: The Minimax Perspective

The core mechanism behind these results is the integration of robustness parameters directly into the value updates. In standard RL, the Bellman operator applies a transition matrix to a value function. In DRRL, this is replaced by a robust Bellman operator that solves an inner minimization problem (the "adversary" choosing the worst transition) inside the outer maximization (the agent choosing the best action).

As Guanlin Liu and Han Liu demonstrated in Efficient Action Robust Reinforcement Learning with Probabilistic Policy Execution Uncertainty, this minimax framing allows the algorithm to reach the same theoretical lower bounds as standard RL. By treating model uncertainty as a structured part of the optimization rather than a random noise source, these algorithms ensure that the learned policy is "safe" by design, without sacrificing the speed of learning.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_optimal_sample_complexity_for_robust_rei_fea30dd3,
  title = {Optimal Sample Complexity for Robust Reinforcement Learning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/optimal-sample-complexity-for-robust-reinforcement-learning/rdr_fea30dd318b748388a808b11e3e8a205},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_optimal_sample_complexity_for_robust_rei_fea30dd3_v1,
  title = {Optimal Sample Complexity for Robust Reinforcement Learning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/optimal-sample-complexity-for-robust-reinforcement-learning/rdr_fea30dd318b748388a808b11e3e8a205/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}