mlsanityData to 14 Oct 2026

What Fundamental Structure in Reward Functions Enables Efficient Sparse-Reward Learning?

arXiv 2509.03790 ↗First posted 4 Sep 2025cs.LG cs.AIcited by 2

On the map: Offline RL and imitation learning from data → Inverse reinforcement learning

also in 1 more
Abstract (arXiv)

Sparse-reward reinforcement learning (RL) remains fundamentally hard: without structure, any agent needs Omega(|S||A|/p) samples to recover rewards. We introduce Policy-Aware Matrix Completion (PAMC) as a first concrete step toward a structural reward learning framework. Our key idea is to exploit approximate low-rank + sparse structure in the reward matrix, under policy-biased (MNAR) sampling. We prove recovery guarantees with inverse-propensity weighting, and establish a visitation-weighted error-to-regret bound linking completion error to control performance. Importantly, when assumptions weaken, PAMC degrades gracefully: confidence intervals widen and the algorithm abstains, ensuring safe fallback to exploration. Empirically, PAMC improves sample efficiency across Atari-26 (10M steps), DM Control, MetaWorld MT50, D4RL offline RL, and preference-based RL benchmarks, outperforming DrQ-v2, DreamerV3, Agent57, T-REX/D-REX, and PrefPPO under compute-normalized comparisons. Our results highlight PAMC as a practical and principled tool when structural rewards exist, and as a concrete first instantiation of a broader structural reward learning perspective.

Key facts. Cited by 2 papers in the map (data through 14 Oct 2026). Placed in Inverse reinforcement learning, one of 13 directions in Offline RL and imitation learning from data. Builds on 25 of its 35 references that are in the map. First posted on arXiv 4 Sep 2025.

Builds on

25 of 35 references.

References · 25

  1. 2017Proximal Policy Optimization Algorithmscited by 15,215
  2. 2017On Calibration of Modern Neural Networkscited by 4,960
  3. 2017Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networkscited by 4,897
  4. 2015Dropout as a Bayesian Approximation: Representing Model Uncertainty in Deep Learningcited by 4,448
  5. 2016Simple and Scalable Predictive Uncertainty Estimation using Deep Ensemblescited by 3,926
  6. 2017Deep reinforcement learning from human preferencescited by 3,912
  7. 2020Conservative Q-Learning for Offline Reinforcement Learningcited by 1,809
  8. 2016Concrete Problems in AI Safetycited by 1,642
  9. 2019Can You Trust Your Model's Uncertainty? Evaluating Predictive Uncertainty Under Dataset Shiftcited by 1,287
  10. 2019Meta-World: A Benchmark and Evaluation for Multi-Task and Meta Reinforcement Learningcited by 1,204
  11. 2017Curiosity-driven Exploration by Self-supervised Predictioncited by 1,194
  12. 2018Exploration by Random Network Distillationcited by 993
13 more
  1. 2017Selective Classification for Deep Neural Networkscited by 852
  2. 2020CURL: Contrastive Unsupervised Representations for Reinforcement Learningcited by 760
  3. 2016Deep Exploration via Bootstrapped DQNcited by 527
  4. 2017Minimax Regret Bounds for Reinforcement Learningcited by 503
  5. 2018Is Q-learning Provably Efficient?cited by 487
  6. 2016Geometric deep learning on graphs and manifolds using mixture model CNNscited by 468
  7. 2018Scalable agent alignment via reward modeling: a research directioncited by 447
  8. 2020Data-Efficient Reinforcement Learning with Self-Predictive Representationscited by 318
  9. 2016#Exploration: A Study of Count-Based Exploration for Deep Reinforcement Learningcited by 309
  10. 2017Noisy Networks for Explorationcited by 266
  11. 2020Never Give Up: Learning Directed Exploration Strategiescited by 212
  12. 2017Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learningcited by 176
  13. 2017Parameter Space Noise for Explorationcited by 161

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 1; 2026: 1.

2 papers.

  1. 2025Adaptive Constraint Propagation: Scaling Structured Inference for Large Language Models via Meta-Reinforcement Learningcited by 0
  2. 2026Certificate-Guided Pruning for Stochastic Lipschitz Optimizationcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2024Reward-Relevance-Filtered Linear Offline Reinforcement Learning
  2. 2025DISCOVER: Automated Curricula for Sparse-Reward Reinforcement Learning
  3. 2024Dense Dynamics-Aware Reward Synthesis: Integrating Prior Experience with Demonstrations
  4. 2025Shaping Sparse Rewards in Reinforcement Learning: A Semi-supervised Approach
  5. 2026ARMS: Automatic Reward Shaping for Sparse-Reward Multi-Agent Reinforcement Learning
  6. 2024Sample Efficient Reinforcement Learning by Automatically Learning to Compose Subtasks
  7. 2024ETGL-DDPG: A Deep Deterministic Policy Gradient Algorithm for Sparse Reward Continuous Control
  8. 2026Reward-free Pretraining for Reinforcement Learning via Occupancy Coverage Maximization