# Shortest-Path Constrained Reinforcement Learning for Sparse Reward Tasks

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 58 references that are in the map.
- First posted on arXiv 13 Jul 2021.

## Builds on (most cited first, 29 of 29)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Curiosity-driven Exploration by Self-supervised Prediction](https://mlsanity.com/paper/1705.05363/) (2017)
- [Exploration by Random Network Distillation](https://mlsanity.com/paper/1810.12894/) (2018)
- [IMPALA: Scalable Distributed Deep-RL with Importance Weighted Actor-Learner Architectures](https://mlsanity.com/paper/1802.01561/) (2018)
- [Unifying Count-Based Exploration and Intrinsic Motivation](https://mlsanity.com/paper/1606.01868/) (2016)
- [Reward Constrained Policy Optimization](https://mlsanity.com/paper/1805.11074/) (2018)
- [FeUdal Networks for Hierarchical Reinforcement Learning](https://mlsanity.com/paper/1703.01161/) (2017)
- [Large-Scale Study of Curiosity-Driven Learning](https://mlsanity.com/paper/1808.04355/) (2018)
- [Multi-Goal Reinforcement Learning: Challenging Robotics Environments and Request for Research](https://mlsanity.com/paper/1802.09464/) (2018)
- [Go-Explore: a New Approach for Hard-Exploration Problems](https://mlsanity.com/paper/1901.10995/) (2019)
- [Semi-parametric Topological Memory for Navigation](https://mlsanity.com/paper/1803.00653/) (2018)
- [Reverse Curriculum Generation for Reinforcement Learning](https://mlsanity.com/paper/1707.05300/) (2017)
- [Learning by Playing - Solving Sparse Reward Tasks from Scratch](https://mlsanity.com/paper/1802.10567/) (2018)
- [DARLA: Improving Zero-Shot Transfer in Reinforcement Learning](https://mlsanity.com/paper/1707.08475/) (2017)
- [Scalable methods for computing state similarity in deterministic Markov Decision Processes](https://mlsanity.com/paper/1911.09291/) (2019)
- [Episodic Curiosity through Reachability](https://mlsanity.com/paper/1810.02274/) (2018)
- [Understanding and Improving Convolutional Neural Networks via Concatenated Rectified Linear Units](https://mlsanity.com/paper/1603.05201/) (2016)
- [Near Optimal Behavior via Approximate State Abstraction](https://mlsanity.com/paper/1701.04113/) (2017)
- [Generating Adjacency-Constrained Subgoals in Hierarchical Reinforcement Learning](https://mlsanity.com/paper/2006.11485/) (2020)
- [Mapping State Space using Landmarks for Universal Goal Reaching](https://mlsanity.com/paper/1908.05451/) (2019)
- [Sparse Graphical Memory for Robust Planning](https://mlsanity.com/paper/2003.06417/) (2020)
- [Contingency-Aware Exploration in Reinforcement Learning](https://mlsanity.com/paper/1811.01483/) (2018)
- [Self-Imitation Learning by Planning](https://mlsanity.com/paper/2103.13834/) (2021)
- [Composable Planning with Attributes](https://mlsanity.com/paper/1803.00512/) (2018)
- [Deep Learning for Reward Design to Improve Monte Carlo Tree Search in ATARI Games](https://mlsanity.com/paper/1604.07095/) (2016)
- [Model Reduction Techniques for Computing Approximately Optimal Solutions for Markov Decision Processes](https://mlsanity.com/paper/1302.1533/) (2013)
- [Attend Before you Act: Leveraging human visual attention for continual learning](https://mlsanity.com/paper/1807.09664/) (2018)

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

- [A Review of Safe Reinforcement Learning: Methods, Theory and Applications](https://mlsanity.com/paper/2205.10330/) (2022)
- [Policy Optimization Prefers The Path of Least Resistance](https://mlsanity.com/paper/2510.21853/) (2025)

## Abstract (arXiv)

We propose the k-Shortest-Path (k-SP) constraint: a novel constraint on the agent's trajectory that improves the sample efficiency in sparse-reward MDPs. We show that any optimal policy necessarily satisfies the k-SP constraint. Notably, the k-SP constraint prevents the policy from exploring state-action pairs along the non-k-SP trajectories (e.g., going back and forth). However, in practice, excluding state-action pairs may hinder the convergence of RL algorithms. To overcome this, we propose a novel cost function that penalizes the policy violating SP constraint, instead of completely excluding it. Our numerical experiment in a tabular RL setting demonstrates that the SP constraint can significantly reduce the trajectory space of policy. As a result, our constraint enables more sample efficient learning by suppressing redundant exploration and exploitation. Our experiments on MiniGrid, DeepMind Lab, Atari, and Fetch show that the proposed method significantly improves proximal policy optimization (PPO) and outperforms existing novelty-seeking exploration methods including count-based exploration even in continuous control tasks, indicating that it improves the sample efficiency by preventing the agent from taking redundant actions.