# Policy Gradient Algorithms with Monte Carlo Tree Learning for Non-Markov Decision Processes

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 33 of its 87 references that are in the map.
- First posted on arXiv 2 Jun 2022.

## Builds on (most cited first, 30 of 33)

- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor](https://mlsanity.com/paper/1801.01290/) (2018)
- [Trust Region Policy Optimization](https://mlsanity.com/paper/1502.05477/) (2015)
- [Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model](https://mlsanity.com/paper/1911.08265/) (2019)
- [Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm](https://mlsanity.com/paper/1712.01815/) (2017)
- [Reinforcement Learning with Deep Energy-Based Policies](https://mlsanity.com/paper/1702.08165/) (2017)
- [Unifying Count-Based Exploration and Intrinsic Motivation](https://mlsanity.com/paper/1606.01868/) (2016)
- [Self-critical Sequence Training for Image Captioning](https://mlsanity.com/paper/1612.00563/) (2016)
- [Deep Recurrent Q-Learning for Partially Observable MDPs](https://mlsanity.com/paper/1507.06527/) (2015)
- [SeqGAN: Sequence Generative Adversarial Nets with Policy Gradient](https://mlsanity.com/paper/1609.05473/) (2016)
- [A Deep Reinforced Model for Abstractive Summarization](https://mlsanity.com/paper/1705.04304/) (2017)
- [Graph Convolutional Policy Network for Goal-Directed Molecular Graph Generation](https://mlsanity.com/paper/1806.02473/) (2018)
- [#Exploration: A Study of Count-Based Exploration for Deep Reinforcement Learning](https://mlsanity.com/paper/1611.04717/) (2016)
- [Large-Scale Study of Curiosity-Driven Learning](https://mlsanity.com/paper/1808.04355/) (2018)
- [Thinking Fast and Slow with Deep Learning and Tree Search](https://mlsanity.com/paper/1705.08439/) (2017)
- [Top-K Off-Policy Correction for a REINFORCE Recommender System](https://mlsanity.com/paper/1812.02353/) (2018)
- [Monte Carlo Tree Search: A Review of Recent Modifications and Applications](https://mlsanity.com/paper/2103.04931/) (2021)
- [On Learning Intrinsic Rewards for Policy Gradient Methods](https://mlsanity.com/paper/1804.06459/) (2018)
- [Sample Efficient Reinforcement Learning with REINFORCE](https://mlsanity.com/paper/2010.11364/) (2020)
- [On the Weaknesses of Reinforcement Learning for Neural Machine Translation](https://mlsanity.com/paper/1907.01752/) (2019)
- [Monte-Carlo Tree Search as Regularized Policy Optimization](https://mlsanity.com/paper/2007.12509/) (2020)
- [Ordering-Based Causal Discovery with Reinforcement Learning](https://mlsanity.com/paper/2105.06631/) (2021)
- [Revisiting the Weaknesses of Reinforcement Learning for Neural Machine Translation](https://mlsanity.com/paper/2106.08942/) (2021)
- [Expected Policy Gradients for Reinforcement Learning](https://mlsanity.com/paper/1801.03326/) (2018)
- [How to Combine Tree-Search Methods in Reinforcement Learning](https://mlsanity.com/paper/1809.01843/) (2018)
- [Deep Learning for Reward Design to Improve Monte Carlo Tree Search in ATARI Games](https://mlsanity.com/paper/1604.07095/) (2016)
- [Policy Gradient Search: Online Planning and Expert Iteration without Search Trees](https://mlsanity.com/paper/1904.03646/) (2019)
- [POLY-HOOT: Monte-Carlo Planning in Continuous Space MDPs with Non-Asymptotic Analysis](https://mlsanity.com/paper/2006.04672/) (2020)
- [Convex Regularization in Monte-Carlo Tree Search](https://mlsanity.com/paper/2007.00391/) (2020)

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

- [Adaptive Mixing of Policies from Searching and Policies from Learning](https://mlsanity.com/paper/2608.15700/) (2026)
- [OPTS-TTPO: Enhancing Finite-Sample Policy-Gradient Learning with Tree Search](https://mlsanity.com/paper/2609.40035/) (2026)

## Abstract (arXiv)

Policy gradient (PG) is a reinforcement learning (RL) approach that optimizes a parameterized policy model for an expected return using gradient ascent. While PG can work well even in non-Markovian environments, it may encounter plateaus or peakiness issues. As another successful RL approach, algorithms based on Monte Carlo Tree Search (MCTS), which include AlphaZero, have obtained groundbreaking results, especially in the game-playing domain. They are also effective when applied to non-Markov decision processes. However, the standard MCTS is a method for decision-time planning, which differs from the online RL setting. In this work, we first introduce Monte Carlo Tree Learning (MCTL), an adaptation of MCTS for online RL setups. We then explore a combined policy approach of PG and MCTL to leverage their strengths. We derive conditions for asymptotic convergence with the results of a two-timescale stochastic approximation and propose an algorithm that satisfies these conditions and converges to a reasonable solution. Our numerical experiments validate the effectiveness of the proposed methods.