Policy Gradient with Tree Search: Avoiding Local Optimas through Lookahead

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Koren, Uri, Kumar, Navdeep, Gadot, Uri, Ramponi, Giorgia, Levy, Kfir Yehuda, Mannor, Shie
Format:	Preprint
Published:	2025
Subjects:	Machine Learning Artificial Intelligence
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

_version_	1866912418890776576
author	Koren, Uri Kumar, Navdeep Gadot, Uri Ramponi, Giorgia Levy, Kfir Yehuda Mannor, Shie
author_facet	Koren, Uri Kumar, Navdeep Gadot, Uri Ramponi, Giorgia Levy, Kfir Yehuda Mannor, Shie
contents	Classical policy gradient (PG) methods in reinforcement learning frequently converge to suboptimal local optima, a challenge exacerbated in large or complex environments. This work investigates Policy Gradient with Tree Search (PGTS), an approach that integrates an $m$-step lookahead mechanism to enhance policy optimization. We provide theoretical analysis demonstrating that increasing the tree search depth $m$-monotonically reduces the set of undesirable stationary points and, consequently, improves the worst-case performance of any resulting stationary policy. Critically, our analysis accommodates practical scenarios where policy updates are restricted to states visited by the current policy, rather than requiring updates across the entire state space. Empirical evaluations on diverse MDP structures, including Ladder, Tightrope, and Gridworld environments, illustrate PGTS's ability to exhibit "farsightedness," navigate challenging reward landscapes, escape local traps where standard PG fails, and achieve superior solutions.
format	Preprint
id	arxiv_https___arxiv_org_abs_2506_07054
institution	arXiv
publishDate	2025
record_format	arxiv
spellingShingle	Policy Gradient with Tree Search: Avoiding Local Optimas through Lookahead Koren, Uri Kumar, Navdeep Gadot, Uri Ramponi, Giorgia Levy, Kfir Yehuda Mannor, Shie Machine Learning Artificial Intelligence Classical policy gradient (PG) methods in reinforcement learning frequently converge to suboptimal local optima, a challenge exacerbated in large or complex environments. This work investigates Policy Gradient with Tree Search (PGTS), an approach that integrates an $m$-step lookahead mechanism to enhance policy optimization. We provide theoretical analysis demonstrating that increasing the tree search depth $m$-monotonically reduces the set of undesirable stationary points and, consequently, improves the worst-case performance of any resulting stationary policy. Critically, our analysis accommodates practical scenarios where policy updates are restricted to states visited by the current policy, rather than requiring updates across the entire state space. Empirical evaluations on diverse MDP structures, including Ladder, Tightrope, and Gridworld environments, illustrate PGTS's ability to exhibit "farsightedness," navigate challenging reward landscapes, escape local traps where standard PG fails, and achieve superior solutions.
title	Policy Gradient with Tree Search: Avoiding Local Optimas through Lookahead
topic	Machine Learning Artificial Intelligence
url	https://arxiv.org/abs/2506.07054