# Computational Benefits of Intermediate Rewards for Goal-Reaching Policy Learning

arXiv: https://arxiv.org/abs/2107.03961 · HTML: https://mlsanity.com/paper/2107.03961/

## 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 (most cited first, 28 of 28)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Playing Atari with Deep Reinforcement Learning](https://mlsanity.com/paper/1312.5602/) (2013)
- [Asynchronous Methods for Deep Reinforcement Learning](https://mlsanity.com/paper/1602.01783/) (2016)
- [OpenAI Gym](https://mlsanity.com/paper/1606.01540/) (2016)
- [Hindsight Experience Replay](https://mlsanity.com/paper/1707.01495/) (2017)
- [Dota 2 with Large Scale Deep Reinforcement Learning](https://mlsanity.com/paper/1912.06680/) (2019)
- [FeUdal Networks for Hierarchical Reinforcement Learning](https://mlsanity.com/paper/1703.01161/) (2017)
- [Hierarchical Deep Reinforcement Learning: Integrating Temporal Abstraction and Intrinsic Motivation](https://mlsanity.com/paper/1604.06057/) (2016)
- [StarCraft II: A New Challenge for Reinforcement Learning](https://mlsanity.com/paper/1708.04782/) (2017)
- [Modular Multitask Reinforcement Learning with Policy Sketches](https://mlsanity.com/paper/1611.01796/) (2016)
- [Planning with Goal-Conditioned Policies](https://mlsanity.com/paper/1911.08453/) (2019)
- [Imagination-Augmented Agents for Deep Reinforcement Learning](https://mlsanity.com/paper/1707.06203/) (2017)
- [RIDE: Rewarding Impact-Driven Exploration for Procedurally-Generated Environments](https://mlsanity.com/paper/2002.12292/) (2020)
- [Actionable Models: Unsupervised Offline Reinforcement Learning of Robotic Skills](https://mlsanity.com/paper/2104.07749/) (2021)
- [C-Learning: Learning to Achieve Goals via Recursive Classification](https://mlsanity.com/paper/2011.08909/) (2020)
- [Temporal Difference Models: Model-Free Deep RL for Model-Based Control](https://mlsanity.com/paper/1802.09081/) (2018)
- [Hierarchical Imitation and Reinforcement Learning](https://mlsanity.com/paper/1803.00590/) (2018)
- [Towards Playing Full MOBA Games with Deep Reinforcement Learning](https://mlsanity.com/paper/2011.12692/) (2020)
- [Variational Inverse Control with Events: A General Framework for Data-Driven Reward Definition](https://mlsanity.com/paper/1805.11686/) (2018)
- [Super-Human Performance in Gran Turismo Sport Using Deep Reinforcement Learning](https://mlsanity.com/paper/2008.07971/) (2020)
- [Data-efficient Deep Reinforcement Learning for Dexterous Manipulation](https://mlsanity.com/paper/1704.03073/) (2017)
- [Rewriting History with Inverse RL: Hindsight Inference for Policy Improvement](https://mlsanity.com/paper/2002.11089/) (2020)
- [Hybrid Reward Architecture for Reinforcement Learning](https://mlsanity.com/paper/1706.04208/) (2017)
- [What Can I Do Here? Learning New Skills by Imagining Visual Affordances](https://mlsanity.com/paper/2106.00671/) (2021)
- [Deep Reinforcement Learning](https://mlsanity.com/paper/1810.06339/) (2018)
- [Simplifying Reward Design through Divide-and-Conquer](https://mlsanity.com/paper/1806.02501/) (2018)
- [Distributed Reinforcement Learning of Targeted Grasping with Active Vision for Mobile Manipulators](https://mlsanity.com/paper/2007.08082/) (2020)
- [Hierarchical Reinforcement Learning in StarCraft II with Human Expertise in Subgoals Selection](https://mlsanity.com/paper/2008.03444/) (2020)

## Built on by (most cited first, 17 of 17)

- [Cal-QL: Calibrated Offline RL Pre-Training for Efficient Online Fine-Tuning](https://mlsanity.com/paper/2303.05479/) (2023)
- [General In-Hand Object Rotation with Vision and Touch](https://mlsanity.com/paper/2309.09979/) (2023)
- [Unpacking Reward Shaping: Understanding the Benefits of Reward Engineering on Sample Complexity](https://mlsanity.com/paper/2210.09579/) (2022)
- [Sub-Task Decomposition Enables Learning in Sequence to Sequence Tasks](https://mlsanity.com/paper/2204.02892/) (2022)
- [Decomposing the Enigma: Subgoal-based Demonstration Learning for Formal Theorem Proving](https://mlsanity.com/paper/2305.16366/) (2023)
- [Understanding the Complexity Gains of Single-Task RL with a Curriculum](https://mlsanity.com/paper/2212.12809/) (2022)
- [Learning Representations that Enable Generalization in Assistive Tasks](https://mlsanity.com/paper/2212.03175/) (2022)
- [R1-RE: Cross-Domain Relation Extraction with RLVR](https://mlsanity.com/paper/2507.04642/) (2025)
- [Accelerated Reinforcement Learning for Temporal Logic Control Objectives](https://mlsanity.com/paper/2205.04424/) (2022)
- [Reinforcement Learning in Dynamic Treatment Regimes Needs Critical Reexamination](https://mlsanity.com/paper/2405.18556/) (2024)
- [Sample-Efficient Reinforcement Learning with Temporal Logic Objectives: Leveraging the Task Specification to Guide Exploration](https://mlsanity.com/paper/2410.12136/) (2024)
- [Mission-driven Exploration for Accelerated Deep Reinforcement Learning with Temporal Logic Task Specifications](https://mlsanity.com/paper/2311.17059/) (2023)
- [SEGO: Sequential Subgoal Optimization for Mathematical Problem-Solving](https://mlsanity.com/paper/2310.12960/) (2023)
- [SEAL: SEmantic-Augmented Imitation Learning via Language Model](https://mlsanity.com/paper/2410.02231/) (2024)
- [Tiered Reward: Designing Rewards for Specification and Fast Learning of Desired Behavior](https://mlsanity.com/paper/2212.03733/) (2022)
- [Learning Upper Lower Value Envelopes to Shape Online RL: A Principled Approach](https://mlsanity.com/paper/2510.19528/) (2025)
- [Vision-Guided Outdoor Flight and Obstacle Evasion via Reinforcement Learning](https://mlsanity.com/paper/2605.24449/) (2026)

## 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.