mlsanityData to 14 Oct 2026

Computational Benefits of Intermediate Rewards for Goal-Reaching Policy Learning

arXiv 2107.03961 ↗First posted 8 Jul 2021cs.AIcited by 17

Not on the map. Why?

Abstract (arXiv)

Many goal-reaching reinforcement learning (RL) tasks have empirically verified that rewarding the agent on subgoals improves convergence speed and practical performance. We attempt to provide a theoretical framework to quantify the computational benefits of rewarding the completion of subgoals, in terms of the number of synchronous value iterations. In particular, we consider subgoals as one-way em intermediate states, which can only be visited once per episode and propose two settings that consider these one-way intermediate states: the one-way single-path (OWSP) and the one-way multi-path (OWMP) settings. In both OWSP and OWMP settings, we demonstrate that adding em intermediate rewards to subgoals is more computationally efficient than only rewarding the agent once it completes the goal of reaching a terminal state. We also reveal a trade-off between computational complexity and the pursuit of the shortest path in the OWMP setting: adding intermediate rewards significantly reduces the computational complexity of reaching the goal but the agent may not find the shortest path, whereas with sparse terminal rewards, the agent finds the shortest path at a significantly higher computational cost. We also corroborate our theoretical results with extensive experiments on the MiniGrid environments using Q-learning and some popular deep RL algorithms.

Key facts. Cited by 17 papers in the map (data through 14 Oct 2026). Builds on 28 of its 80 references that are in the map. First posted on arXiv 8 Jul 2021.

Builds on

28 of 80 references.

References · 28

  1. 2017Proximal Policy Optimization Algorithmscited by 15,215
  2. 2013Playing Atari with Deep Reinforcement Learningcited by 3,274
  3. 2016Asynchronous Methods for Deep Reinforcement Learningcited by 2,258
  4. 2016OpenAI Gymcited by 1,736
  5. 2017Hindsight Experience Replaycited by 1,136
  6. 2019Dota 2 with Large Scale Deep Reinforcement Learningcited by 1,103
  7. 2017FeUdal Networks for Hierarchical Reinforcement Learningcited by 337
  8. 2016Hierarchical Deep Reinforcement Learning: Integrating Temporal Abstraction and Intrinsic Motivationcited by 286
  9. 2017StarCraft II: A New Challenge for Reinforcement Learningcited by 274
  10. 2016Modular Multitask Reinforcement Learning with Policy Sketchescited by 203
  11. 2019Planning with Goal-Conditioned Policiescited by 149
  12. 2017Imagination-Augmented Agents for Deep Reinforcement Learningcited by 140
16 more
  1. 2020RIDE: Rewarding Impact-Driven Exploration for Procedurally-Generated Environmentscited by 135
  2. 2021Actionable Models: Unsupervised Offline Reinforcement Learning of Robotic Skillscited by 125
  3. 2020C-Learning: Learning to Achieve Goals via Recursive Classificationcited by 103
  4. 2018Temporal Difference Models: Model-Free Deep RL for Model-Based Controlcited by 89
  5. 2018Hierarchical Imitation and Reinforcement Learningcited by 88
  6. 2020Towards Playing Full MOBA Games with Deep Reinforcement Learningcited by 78
  7. 2018Variational Inverse Control with Events: A General Framework for Data-Driven Reward Definitioncited by 69
  8. 2020Super-Human Performance in Gran Turismo Sport Using Deep Reinforcement Learningcited by 65
  9. 2017Data-efficient Deep Reinforcement Learning for Dexterous Manipulationcited by 63
  10. 2020Rewriting History with Inverse RL: Hindsight Inference for Policy Improvementcited by 60
  11. 2017Hybrid Reward Architecture for Reinforcement Learningcited by 58
  12. 2021What Can I Do Here? Learning New Skills by Imagining Visual Affordancescited by 23
  13. 2018Deep Reinforcement Learningcited by 14
  14. 2018Simplifying Reward Design through Divide-and-Conquercited by 12
  15. 2020Distributed Reinforcement Learning of Targeted Grasping with Active Vision for Mobile Manipulatorscited by 7
  16. 2020Hierarchical Reinforcement Learning in StarCraft II with Human Expertise in Subgoals Selectioncited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 6; 2023: 5; 2024: 3; 2025: 2; 2026: 1.

17 papers.

Sort:

By area:

  1. 2023Cal-QL: Calibrated Offline RL Pre-Training for Efficient Online Fine-Tuningcited by 237
  2. 2023General In-Hand Object Rotation with Vision and Touchcited by 99
  3. 2022Unpacking Reward Shaping: Understanding the Benefits of Reward Engineering on Sample Complexitycited by 62
  4. 2022Sub-Task Decomposition Enables Learning in Sequence to Sequence Taskscited by 41
  5. 2023Decomposing the Enigma: Subgoal-based Demonstration Learning for Formal Theorem Provingcited by 37
  6. 2022Understanding the Complexity Gains of Single-Task RL with a Curriculumcited by 17
  7. 2022Learning Representations that Enable Generalization in Assistive Taskscited by 13
  8. 2025R1-RE: Cross-Domain Relation Extraction with RLVRcited by 11
  9. 2022Accelerated Reinforcement Learning for Temporal Logic Control Objectivescited by 9
  10. 2024Reinforcement Learning in Dynamic Treatment Regimes Needs Critical Reexaminationcited by 5
  11. 2024Sample-Efficient Reinforcement Learning with Temporal Logic Objectives: Leveraging the Task Specification to Guide Explorationcited by 5
  12. 2023Mission-driven Exploration for Accelerated Deep Reinforcement Learning with Temporal Logic Task Specificationscited by 3
5 more
  1. 2023SEGO: Sequential Subgoal Optimization for Mathematical Problem-Solvingcited by 1
  2. 2024SEAL: SEmantic-Augmented Imitation Learning via Language Modelcited by 1
  3. 2022Tiered Reward: Designing Rewards for Specification and Fast Learning of Desired Behaviorcited by 0
  4. 2025Learning Upper Lower Value Envelopes to Shape Online RL: A Principled Approachcited by 0
  5. 2026Vision-Guided Outdoor Flight and Obstacle Evasion via Reinforcement Learningcited by 0