Research map / Reinforcement learning / MDPs and planning

Near-Optimal Distributionally Robust Reinforcement Learning with General $L_p$ Norms

NeurIPS 2024 · Reinforcement learning › MDPs and planning · approach: Offline RL sample complexity · 1 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Gives sample complexity bounds (upper and lower) for distributionally robust MDPs with general smooth L_p norm uncertainty sets under a generative model, for both sa- and s-rectangular cases, showing robust RL can be no harder than standard RL.

Problem

Sample complexity of distributionally robust MDPs with general smooth L_p-norm uncertainty sets, under sa- and s-rectangularity, with a generative model, and how it compares with standard RL.

Approach

Derives new dual forms for robust Bellman operators under arbitrary smooth norms and bounds the infinite-span seminorm of the value function, yielding near-minimax upper bounds for sa-rectangular RMDPs and improved upper bounds for s-rectangular RMDPs, plus matching lower bounds (L_inf for s-rectangular).

Key results

• For sa-rectangular RMDPs with general smooth L_p norms, the upper bound is about SA/((1-γ)^2 max{1-γ, C_g σ} ε^2), matched by a minimax lower bound (Theorem 2), so robust planning is never harder than standard RL's ~SA/((1-γ)^3 ε^2) when σ ≳ 1-γ.
• For s-rectangular RMDPs, the upper bound improves the prior Clavier et al. (2023) bound of SA/((1-γ)^4 ε^2) by at least a factor 1/(1-γ) when σ̃ ≲ 1-γ, and the paper gives a first s-rectangular lower bound using L_inf norm.
• The s-rectangular data-dependent bound shows that deterministic policies concentrate the uncertainty budget and are easier, while near-uniform policies recover the sa-rectangular rate.

Measured effects reported in the paper

Surprising findings

• Robust MDPs with generalized L_p uncertainty can require fewer samples than standard MDPs when the uncertainty radius is large (σ ≳ 1-γ).
• s-rectangular RMDPs are at least as easy as sa-rectangular RMDPs in sample complexity, despite the more complex optimization.

Limitations

• Results are for tabular settings with a generative model, not function approximation or online learning.
• Theory requires burn-in conditions on accuracy epsilon, and the s-rectangular lower bound is only shown for L_inf norm.
• Does not cover f-divergences such as KL or chi-square; the analysis does not extend directly.

Experimental setup

Metrics: sample complexity order (NSA up to log terms) epsilon-optimality of robust value

Baselines: Shi et al. 2023 Clavier et al. 2023 Yang et al. 2022a Panaganti and Kalathil 2022 standard RL minimax sample complexity

Builds on: Shi et al. 2023 (TV-distance RMDP sample complexity) Clavier et al. 2023 (L_p RMDP) Yang et al. 2022 (robust MDP sample complexity) Iyengar 2005 robust MDP framework Panaganti and Kalathil 2022

Closest papers by meaning

• Distributionally Robust Reinforcement Learning with Interactive Data Collection: Fundamental Hardness and Near-Optimal Algorithms (NeurIPS 2024 · similarity 0.94)
• Sample Complexity of Distributionally Robust Average-Reward Reinforcement Learning (NeurIPS 2025 · similarity 0.93)
• Finite-Sample Analysis of Policy Evaluation for Robust Average Reward Reinforcement Learning (NeurIPS 2025 · similarity 0.91)
• Taming the Curses of Multiagency in Robust Markov Games with Large State Space through Linear Function Approximation (NeurIPS 2026 · similarity 0.90)
• Time-Constrained Robust MDPs (NeurIPS 2024 · similarity 0.90)
• Minimax Optimal and Computationally Efficient Algorithms for Distributionally Robust Offline Reinforcement Learning (NeurIPS 2024 · similarity 0.90)