# ExPoSe: Combining State-Based Exploration with Gradient-Based Online Search

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 41 references that are in the map.
- First posted on arXiv 3 Feb 2022.

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

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Playing Atari with Deep Reinforcement Learning](https://mlsanity.com/paper/1312.5602/) (2013)
- [Trust Region Policy Optimization](https://mlsanity.com/paper/1502.05477/) (2015)
- [Asynchronous Methods for Deep Reinforcement Learning](https://mlsanity.com/paper/1602.01783/) (2016)
- [OpenAI Gym](https://mlsanity.com/paper/1606.01540/) (2016)
- [Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model](https://mlsanity.com/paper/1911.08265/) (2019)
- [Rainbow: Combining Improvements in Deep Reinforcement Learning](https://mlsanity.com/paper/1710.02298/) (2017)
- [Neural Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1611.09940/) (2016)
- [Deep Exploration via Bootstrapped DQN](https://mlsanity.com/paper/1602.04621/) (2016)
- [Agent57: Outperforming the Atari Human Benchmark](https://mlsanity.com/paper/2003.13350/) (2020)
- [Noisy Networks for Exploration](https://mlsanity.com/paper/1706.10295/) (2017)
- [Thinking Fast and Slow with Deep Learning and Tree Search](https://mlsanity.com/paper/1705.08439/) (2017)
- [Value Iteration Networks](https://mlsanity.com/paper/1602.02867/) (2016)
- [Imagination-Augmented Agents for Deep Reinforcement Learning](https://mlsanity.com/paper/1707.06203/) (2017)
- [The Predictron: End-To-End Learning and Planning](https://mlsanity.com/paper/1612.08810/) (2016)
- [An investigation of model-free planning](https://mlsanity.com/paper/1901.03559/) (2019)
- [ChainerRL: A Deep Reinforcement Learning Library](https://mlsanity.com/paper/1912.03905/) (2019)
- [Learning to Search with MCTSnets](https://mlsanity.com/paper/1802.04697/) (2018)
- [Gated Path Planning Networks](https://mlsanity.com/paper/1806.06408/) (2018)
- [Learning model-based planning from scratch](https://mlsanity.com/paper/1707.06170/) (2017)
- [Improving exploration in policy gradient search: Application to symbolic optimization](https://mlsanity.com/paper/2107.09158/) (2021)
- [Policy Gradient Search: Online Planning and Expert Iteration without Search Trees](https://mlsanity.com/paper/1904.03646/) (2019)
- [State-Aware Variational Thompson Sampling for Deep Q-Networks](https://mlsanity.com/paper/2102.03719/) (2021)

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

- [Levin Tree Search with Context Models](https://mlsanity.com/paper/2305.16945/) (2023)
- [Differentiable Tree Search Network](https://mlsanity.com/paper/2401.11660/) (2024)

## Abstract (arXiv)

Online tree-based search algorithms iteratively simulate trajectories and update action-values for a set of states stored in a tree structure. It works reasonably well in practice but fails to effectively utilise the information gathered from similar states. Depending upon the smoothness of the action-value function, one approach to overcoming this issue is through online learning, where information is interpolated among similar states; Policy Gradient Search provides a practical algorithm to achieve this. However, Policy Gradient Search lacks an explicit exploration mechanism, which is a key feature of tree-based online search algorithms. In this paper, we propose an efficient and effective online search algorithm called Exploratory Policy Gradient Search (ExPoSe), which leverages information sharing among states by updating the search policy parameters directly, while incorporating a well-defined exploration mechanism during the online search process. We evaluate ExPoSe on a range of decision-making problems, including Atari games, Sokoban, and Hamiltonian cycle search in sparse graphs. The results demonstrate that ExPoSe consistently outperforms other popular online search algorithms across all domains. The ExPoSe source code is available at textiturlhttps://github.com/dixantmittal/ExPoSe.