Research map / Reinforcement learning / MDPs and planning

Distributionally Robust Reinforcement Learning with Interactive Data Collection: Fundamental Hardness and Near-Optimal Algorithms

NeurIPS 2024 · Reinforcement learning › MDPs and planning · approach: Function approximation in RL theory · 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.

Shows robust RL with interactive data collection under TV-distance robust sets is hard in general (linear regret due to support shift), and proposes OPROVI-TV, which achieves near-optimal sample complexity under a vanishing minimal value assumption.

Problem

Distributionally robust RL in finite-horizon S×A-rectangular RMDPs with TV robust sets, where the learner can only interact with the training environment (no generative model or offline coverage data), making exploration and robustness jointly necessary.

Approach

Identifies a curse of support shift yielding a linear regret lower bound in general, then introduces a vanishing minimal value assumption that converts the TV robust Bellman operator into one with a shared support, enabling an optimistic robust value iteration with Bernstein-style bonuses (OPROVI-TV).

Key results

• Proves a general lower bound of Ω(ρ·HK) online regret for robust RL with interactive data collection, showing sample-efficient learning is impossible without extra assumptions.
• OPROVI-TV achieves online regret Õ(sqrt(min{H, ρ^-1} H^2 SAK)) under the vanishing minimal value assumption.
• Sample complexity Õ(min{H, ρ^-1} H^2 SA/ε^2), which recovers the minimax-optimal Õ(H^3 SA/ε^2) rate of online RL when ρ=0.

Measured effects reported in the paper

Surprising findings

• Claims an existing NeurIPS-style regret result (Dong et al., 2022) for robust RL with interactive data is invalid due to a flawed lemma use.

Limitations

• Analysis restricted to tabular S×A-rectangular RMDPs; no function approximation.
• Requires vanishing minimal value assumption, which is not automatically satisfied and excludes the general case shown to be hard.
• Only TV robust sets considered; KL and other divergences left for future work.

Experimental setup

Metrics: online regret sample complexity

Baselines: RPVL (Xu et al., 2023) DRVI (Shi et al., 2023) P2MPO (Blanchet et al., 2023) RFQI (Panaganti et al., 2022)

Builds on: UCBVI robust Bellman equation (Iyengar 2005) Shi et al. 2023 value gap characterization Blanchet et al. 2023 d-rectangular robust RL

Closest papers by meaning

• Near-Optimal Distributionally Robust Reinforcement Learning with General $L_p$ Norms (NeurIPS 2024 · similarity 0.94)
• Sample Complexity of Distributionally Robust Average-Reward Reinforcement Learning (NeurIPS 2025 · similarity 0.91)
• Sample-Efficient Robust Multi-Agent Reinforcement Learning in the Face of Environmental Uncertainty (ICML 2024 · similarity 0.91)
• Adversarial Diffusion for Robust Reinforcement Learning (NeurIPS 2025 · similarity 0.91)
• Sample Complexity of Distributionally Robust Off-Dynamics Reinforcement Learning with Online Interaction (ICML 2025 · similarity 0.90)
• Taming the Curses of Multiagency in Robust Markov Games with Large State Space through Linear Function Approximation (NeurIPS 2026 · similarity 0.90)