How to Combine Tree-Search Methods in Reinforcement Learning

2018-09-06 · Yonathan Efroni, Gal Dalal, Bruno Scherrer, Shie Mannor

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 $\gamma^h$-contracting procedure, where $\gamma$ is the discount factor and $h$ is the tree depth. To establish our results, we first introduce a notion called \emph{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.

📄 PDF Abstract BibTeX arXiv:1809.01843

Code (0)

등록된 구현이 없습니다.

Tasks

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Solve Traveling Salesman Problem by Monte Carlo Tree Search and Deep Neural Network

2020-05-14 · Zhihao Xing, Shikui Tu, Lei Xu

We present a self-learning approach that combines deep reinforcement learning and Monte Carlo tree search to solve the traveling salesman problem. The proposed approach has two advantages. First, it adopts deep reinforce…

Deep Reinforcement Learning reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)+2

Deep Reinforcement Learning with Model Learning and Monte Carlo Tree Search in Minecraft

2018-03-22 · Stephan Alaniz

Deep reinforcement learning has been successfully applied to several visual-input tasks using model-free methods. In this paper, we propose a model-based approach that combines learning a DNN-based transition model with …

Deep Reinforcement Learning Minecraft Reinforcement Learning Reinforcement Learning (RL)

A* Tree Search for Portfolio Management

2019-01-07 · Xiaojie Gao, Shikui Tu, Lei Xu

We propose a planning-based method to teach an agent to manage portfolio from scratch. Our approach combines deep reinforcement learning techniques with search techniques like AlphaGo. By uniting the advantages in A* sea…

Deep Reinforcement Learning Management reinforcement-learning Reinforcement Learning+1

Interpretable Reinforcement Learning with Ensemble Methods

2018-09-19 · Alexander Brown, Marek Petrik

We propose to use boosted regression trees as a way to compute human-interpretable solutions to reinforcement learning problems. Boosting combines several regression trees to improve their accuracy without significantly …

BIG-bench Machine Learning Interpretable Machine Learning regression reinforcement-learning+2

Hedging of Financial Derivative Contracts via Monte Carlo Tree Search

2021-02-11 · Oleg Szehr

The construction of approximate replication strategies for pricing and hedging of derivative contracts in incomplete markets is a key problem of financial engineering. Recently Reinforcement Learning algorithms for hedgi…

Q-Learning reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)