# Improve Value Estimation of Q Function and Reshape Reward with Monte Carlo Tree Search

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

## 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 15 of its 34 references that are in the map.
- First posted on arXiv 15 Oct 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, 15 of 15)

- [Playing Atari with Deep Reinforcement Learning](https://mlsanity.com/paper/1312.5602/) (2013)
- [Deep Reinforcement Learning with Double Q-learning](https://mlsanity.com/paper/1509.06461/) (2015)
- [Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm](https://mlsanity.com/paper/1712.01815/) (2017)
- [StarCraft II: A New Challenge for Reinforcement Learning](https://mlsanity.com/paper/1708.04782/) (2017)
- [Deep Reinforcement Learning from Self-Play in Imperfect-Information Games](https://mlsanity.com/paper/1603.01121/) (2016)
- [Deep Counterfactual Regret Minimization](https://mlsanity.com/paper/1811.00164/) (2018)
- [DouZero: Mastering DouDizhu with Self-Play Deep Reinforcement Learning](https://mlsanity.com/paper/2106.06135/) (2021)
- [Value-Decomposition Multi-Agent Actor-Critics](https://mlsanity.com/paper/2007.12306/) (2020)
- [Monte Carlo Tree Search based Variable Selection for High Dimensional Bayesian Optimization](https://mlsanity.com/paper/2210.01628/) (2022)
- [RLCard: A Toolkit for Reinforcement Learning in Card Games](https://mlsanity.com/paper/1910.04376/) (2019)
- [Combining Q-Learning and Search with Amortized Value Estimates](https://mlsanity.com/paper/1912.02807/) (2019)
- [Asynchronous Actor-Critic for Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2209.10113/) (2022)
- [Efficient Reinforcement Learning for StarCraft by Abstract Forward Models and Transfer Learning](https://mlsanity.com/paper/1903.00715/) (2019)
- [DouZero+: Improving DouDizhu AI by Opponent Modeling and Coach-guided Learning](https://mlsanity.com/paper/2204.02558/) (2022)
- [Monte Carlo Q-learning for General Game Playing](https://mlsanity.com/paper/1802.05944/) (2018)

## Abstract (arXiv)

Reinforcement learning has achieved remarkable success in perfect information games such as Go and Atari, enabling agents to compete at the highest levels against human players. However, research in reinforcement learning for imperfect information games has been relatively limited due to the more complex game structures and randomness. Traditional methods face challenges in training and improving performance in imperfect information games due to issues like inaccurate Q value estimation and reward sparsity. In this paper, we focus on Uno, an imperfect information game, and aim to address these problems by reducing Q value overestimation and reshaping reward function. We propose a novel algorithm that utilizes Monte Carlo Tree Search to average the value estimations in Q function. Even though we choose Double Deep Q Learning as the foundational framework in this paper, our method can be generalized and used in any algorithm which needs Q value estimation, such as the Actor-Critic. Additionally, we employ Monte Carlo Tree Search to reshape the reward structure in the game environment. We compare our algorithm with several traditional methods applied to games such as Double Deep Q Learning, Deep Monte Carlo and Neural Fictitious Self Play, and the experiments demonstrate that our algorithm consistently outperforms these approaches, especially as the number of players in Uno increases, indicating a higher level of difficulty.