# How to Combine Tree-Search Methods in Reinforcement Learning

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Sep 2018.

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

- [Planning Like Human: A Dual-process Framework for Dialogue Planning](https://mlsanity.com/paper/2406.05374/) (2024)
- [Generalised Policy Improvement with Geometric Policy Composition](https://mlsanity.com/paper/2206.08736/) (2022)
- [Improve Agents without Retraining: Parallel Tree Search with Off-Policy Correction](https://mlsanity.com/paper/2107.01715/) (2021)
- [On The Convergence Of Policy Iteration-Based Reinforcement Learning With Monte Carlo Policy Evaluation](https://mlsanity.com/paper/2301.09709/) (2023)
- [Planning and Learning with Adaptive Lookahead](https://mlsanity.com/paper/2201.12403/) (2022)
- [The Value of Reward Lookahead in Reinforcement Learning](https://mlsanity.com/paper/2403.11637/) (2024)
- [Policy Mirror Descent with Lookahead](https://mlsanity.com/paper/2403.14156/) (2024)
- [The Role of Lookahead and Approximate Policy Evaluation in Reinforcement Learning with Linear Value Function Approximation](https://mlsanity.com/paper/2109.13419/) (2021)
- [Policy Gradient Algorithms with Monte Carlo Tree Learning for Non-Markov Decision Processes](https://mlsanity.com/paper/2206.01011/) (2022)
- [Highway Reinforcement Learning](https://mlsanity.com/paper/2405.18289/) (2024)
- [SoftTreeMax: Policy Gradient with Tree Search](https://mlsanity.com/paper/2209.13966/) (2022)
- [Monotone and Conservative Policy Iteration Beyond the Tabular Case](https://mlsanity.com/paper/2506.07134/) (2025)
- [A New Policy Iteration Algorithm For Reinforcement Learning in Zero-Sum Markov Games](https://mlsanity.com/paper/2303.09716/) (2023)
- [Simulation-Based Optimistic Policy Iteration For Multi-Agent MDPs with Kullback-Leibler Control Cost](https://mlsanity.com/paper/2410.15156/) (2024)
- [Effective Online 3D Bin Packing with Lookahead Parcels Using Monte Carlo Tree Search](https://mlsanity.com/paper/2601.02649/) (2026)
- [Adaptive Mixing of Policies from Searching and Policies from Learning](https://mlsanity.com/paper/2608.15700/) (2026)

## Abstract (arXiv)

Finite-horizon lookahead policies are abundantly used in Reinforcement Learning and demonstrate impressive empirical success. Usually, the lookahead policies are implemented with specific planning methods such as Monte Carlo Tree Search (e.g. in AlphaZero). Referring to the planning problem as tree search, a reasonable practice in these implementations is to back up the value only at the leaves while the information obtained at the root is not leveraged other than for updating the policy. Here, we question the potency of this approach. Namely, the latter procedure is non-contractive in general, and its convergence is not guaranteed. Our proposed enhancement is straightforward and simple: use the return from the optimal tree path to back up the values at the descendants of the root. This leads to a γh-contracting procedure, where γ is the discount factor and h is the tree depth. To establish our results, we first introduce a notion called multiple-step greedy consistency. We then provide convergence rates for two algorithmic instantiations of the above enhancement in the presence of noise injected to both the tree search stage and value estimation stage.