# Highway Graph to Accelerate Reinforcement Learning

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in RL for games and combinatorial optimization, one of 15 directions in Deep reinforcement learning methods.
- Builds on 22 of its 41 references that are in the map.
- First posted on arXiv 20 May 2024.

## Placed in

- Deep reinforcement learning methods / [RL for games and combinatorial optimization](https://mlsanity.com/deeprl/rl-for-games-and-combinatorial-optimization/)

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

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Asynchronous Methods for Deep Reinforcement Learning](https://mlsanity.com/paper/1602.01783/) (2016)
- [Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model](https://mlsanity.com/paper/1911.08265/) (2019)
- [Prioritized Experience Replay](https://mlsanity.com/paper/1511.05952/) (2015)
- [IMPALA: Scalable Distributed Deep-RL with Importance Weighted Actor-Learner Architectures](https://mlsanity.com/paper/1802.01561/) (2018)
- [Model-Based Reinforcement Learning for Atari](https://mlsanity.com/paper/1903.00374/) (2019)
- [Data-Efficient Hierarchical Reinforcement Learning](https://mlsanity.com/paper/1805.08296/) (2018)
- [Google Research Football: A Novel Reinforcement Learning Environment](https://mlsanity.com/paper/1907.11180/) (2019)
- [Monte Carlo Tree Search: A Review of Recent Modifications and Applications](https://mlsanity.com/paper/2103.04931/) (2021)
- [Value Iteration Networks](https://mlsanity.com/paper/1602.02867/) (2016)
- [Neural Episodic Control](https://mlsanity.com/paper/1703.01988/) (2017)
- [Model-Free Episodic Control](https://mlsanity.com/paper/1606.04460/) (2016)
- [Stochastic Policy Gradient Methods: Improved Sample Complexity for Fisher-non-degenerate Policies](https://mlsanity.com/paper/2302.01734/) (2023)
- [Episodic Memory Deep Q-Networks](https://mlsanity.com/paper/1805.07603/) (2018)
- [Return-Based Contrastive Representation Learning for Reinforcement Learning](https://mlsanity.com/paper/2102.10960/) (2021)
- [Conditional Mutual Information for Disentangled Representations in Reinforcement Learning](https://mlsanity.com/paper/2305.14133/) (2023)
- [Generalizable Episodic Memory for Deep Reinforcement Learning](https://mlsanity.com/paper/2103.06469/) (2021)
- [Temporal Disentanglement of Representations for Improved Generalisation in Reinforcement Learning](https://mlsanity.com/paper/2207.05480/) (2022)
- [Reinforcement Learning with Automated Auxiliary Loss Search](https://mlsanity.com/paper/2210.06041/) (2022)
- [Correcting discount-factor mismatch in on-policy policy gradient methods](https://mlsanity.com/paper/2306.13284/) (2023)
- [Multi-Horizon Representations with Hierarchical Forward Models for Reinforcement Learning](https://mlsanity.com/paper/2206.11396/) (2022)
- [Using Offline Data to Speed Up Reinforcement Learning in Procedurally Generated Environments](https://mlsanity.com/paper/2304.09825/) (2023)

## Abstract (arXiv)

Reinforcement Learning (RL) algorithms often struggle with low training efficiency. A common approach to address this challenge is integrating model-based planning algorithms, such as Monte Carlo Tree Search (MCTS) or Value Iteration (VI), into the environmental model. However, VI requires iterating over a large tensor which updates the value of the preceding state based on the succeeding state through value propagation, resulting in computationally intensive operations. To enhance the RL training efficiency, we propose improving the efficiency of the value learning process. In deterministic environments with discrete state and action spaces, we observe that on the sampled empirical state-transition graph, a non-branching sequence of transitions-termed a highway-can take the agent to another state without deviation through intermediate states. On these non-branching highways, the value-updating process can be streamlined into a single-step operation, eliminating the need for step-by-step updates. Building on this observation, we introduce the highway graph to model state transitions. The highway graph compresses the transition model into a compact representation, where edges can encapsulate multiple state transitions, enabling value propagation across multiple time steps in a single iteration. By integrating the highway graph into RL, the training process is significantly accelerated, particularly in the early stages of training. Experiments across four categories of environments demonstrate that our method learns significantly faster than established and state-of-the-art RL algorithms (often by a factor of 10 to 150) while maintaining equal or superior expected returns. Furthermore, a deep neural network-based agent trained using the highway graph exhibits improved generalization capabilities and reduced storage costs. Code is publicly available at https://github.com/coodest/highwayRL.