Research map / Reinforcement learning / Offline RL
Exact Policy Recovery in Offline RL with Both Heavy-Tailed Rewards and Data Corruption
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.
Studies offline tabular RL with heavy-tailed rewards (bounded (1+γ)-th moment) and ϵ-fraction adversarial corruption, showing trimmed-mean estimation inside generalized PEVI recovers the optimal policy when the corruption-induced bias is below the action gap.
Problem
Offline RL where rewards may have infinite variance and an attacker can corrupt a small fraction of rewards and transitions; standard PEVI leaves an irreducible bias from corruption, so it may return suboptimal policies even with infinite data.
Approach
Derives a sufficient optimality condition for generalized PEVI based on the action gap (rather than policy gap), and plugs in a trimmed-mean estimator, which is minimax optimal for robust mean estimation under heavy tails, so that the bias term below the action gap guarantees exact optimal policy recovery.
Key results
- Trimmed-mean estimator achieves error O(σϵ^{γ/(1+γ)} + σN^{-γ/(1+γ)}) for robust mean estimation under bounded (1+γ)-th moment, shown minimax optimal via a matching lower bound.
- Under corruption, PEVI with trimmed mean returns an exactly optimal policy when 2H(C1,γ σ ϵ^{γ/(1+γ)} + ϵH) < action gap and N is sufficiently large.
- Action-gap optimality condition is never more conservative than the policy-gap condition, and can be much less conservative since policy gap is at most action gap times state occupancy.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the trimmed-mean reward estimator and corruption-adjusted transition confidence bounds | Generalized PEVI · Offline RL with corrupted data and heavy-tailed rewards | suboptimality: SubOpt(ˆπ) = 0 | Helped |
| Use the modified trimmed-mean estimator | Robust mean estimation with heavy-tailed distributions · Heavy-tailed rewards with ϵ-fraction corruption | absolute estimation error: C1,γσϵ^(γ/(1+γ)) + C2,γσ(1/N log 8/δ)^(γ/(1+γ)) | Helped |
| Use trimmed-mean estimation under bounded (1 + γ)-th centered moments | Robust mean estimation · Heavy-tailed distributions with data corruption | absolute estimation error: Ω(σϵ^(γ/(1+γ)) + σN^(−γ/(1+γ))) | Helped |
| Use empirical mean reward and transition estimators | Generalized PEVI · Offline RL with i.i.d. data and subGaussian rewards | suboptimality: SubOpt(ˆπ) = 0 | Helped |
| Require the corruption bias to be below the action gap | Generalized PEVI with trimmed-mean estimation · Offline RL with corrupted data and heavy-tailed rewards | optimal policy recovery: 2H(C1,γσϵ^(γ/(1+γ)) + ϵH) < ∆Amin | Helped |
Surprising findings
- Unlike robust mean estimation, where the true mean can never be learned under corruption, in robust RL the action gap enables exact optimal policy identification despite corruption.
Limitations
- Sample complexity is not optimized; the paper focuses on the optimality condition rather than sample efficiency.
- Analysis is for tabular finite-horizon MDPs with uniform optimal-policy coverage assumption.
- Bias term for gamma<1 is larger and convergence slower, reflecting inherent difficulty.
Experimental setup
Metrics: suboptimality gap estimation error rate
Baselines: truncated empirical mean median-of-means empirical mean estimator
Builds on: PEVI Bubeck et al. 2013 heavy-tailed bandits Lugosi and Mendelson trimmed mean Wang, Cui, and Du 2022 gap-dependent offline RL
Closest papers by meaning
- Towards Robust Offline Reinforcement Learning under Diverse Data Corruption (ICLR 2024 · similarity 0.93)
- Robust Policy Expansion for Offline-to-Online RL under Diverse Data Corruption (NeurIPS 2025 · similarity 0.91)
- Tackling Data Corruption in Offline Reinforcement Learning via Sequence Modeling (ICLR 2025 · similarity 0.90)
- Towards Robust Model-Based Reinforcement Learning Against Adversarial Corruption (ICML 2024 · similarity 0.90)
- Worst-Case Offline Reinforcement Learning with Arbitrary Data Support (NeurIPS 2024 · similarity 0.89)
- A Unified Principle of Pessimism for Offline Reinforcement Learning under Model Mismatch (NeurIPS 2024 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.