Policy Gradient with Tree Search: Avoiding Local Optimas through Lookahead

Uri Koren, Navdeep Kumar*, Uri Gadot, Giorgia Ramponi, Kfir Levy, Shie Mannor · 2025

Read Policy Gradient with Tree Search: Avoiding Local Optimas through Lookahead by Uri Koren, Navdeep Kumar*, Uri Gadot, Giorgia Ramponi, Kfir Levy, Shie Mannor (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-07054.txt.

Introduction

Uri Koren and colleagues add lookahead search to a standard reinforcement learning method that often gets stuck in mediocre strategies. Policy gradient methods climb toward better behavior by small steps, so they settle at the nearest good-enough peak, especially in complex worlds. Writing in twenty twenty-five, the team equips the learner with a tree search that peeks several steps ahead before updating. Their theory shows that deeper lookahead steadily shrinks the set of bad resting points, improving the worst case for any strategy the method can settle on.

Crucially, the analysis allows updates only at states the current strategy actually visits, which matches real practice. Tests on ladder, tightrope, and grid worlds show the combined method escaping traps where plain policy gradient fails and finding clearly better solutions. Farsightedness, the authors argue, is the missing ingredient.

Catalog record

CREATORUri Koren, Navdeep Kumar*, Uri Gadot, Giorgia Ramponi, Kfir Levy, Shie Mannor
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE35 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-07054

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Policy Gradient with Tree Search: Avoiding Local Optimas through Lookahead Uri Koren, Navdeep Kumar*, Uri Gadot, Giorgia Ramponi, Kfir Levy, Shie Mannor Abstract 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 m -step lookahead mechanism to enhance policy optimization. We provide theoretical analysis demonstrating that increasing the tree search depth m 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. 1 Introduction Reinforcement Learning (RL) has become a cornerstone in artificial intelligence, enabling agents to solve sequential decision-making problems in a wide range of domains, from robotics to healthcare to autonomous driving Sutton1998 . Among the plethora of RL algorithms, policy gradient (PG) methods stand out for their ability to directly optimize policies and scale to high-dimensional action spaces sutton1999policy ; schulman2015trust . Their success in landmark applications such as AlphaGo, robotics, and game-playing agents underscores their versatility and potential AlphaZero ; mnih2015humanlevel . Despite these successes, PG methods are not without challenges. A fundamental limitation arises from the non-concave nature of the objective in policy space valuePolytope , making PG methods susceptible to convergence at suboptimal local minima PGTS ; PG_local_conv_single_time_scale ; actor-critic . As global convergence PG requires the strict assumption of finite mis-match coefficient or initial state-distribution have strictly positive probability at all states. PG_ConvRate ; SoftMaxPG_conv ; PG_Conv_JLiu_Elementaryanalysispolicygradient_linearConv . This issue is exacerbated in real-world applications where large and continuous state spaces, combined with safety constraints, restrict exploratory behavior. For example, in autonomous driving, policies cannot feasibly explore all potential states, nor is it desirable to employ aggressive exploratory strategies that might compromise safety. These practical constraints render the standard assumptions for global convergence of PG methods—such as uniform exploration or a bounded mismatch coefficient—highly intractable SoftMaxPG_conv ; PG_conv_average_reward . Popular variants of policy gradient (PG) algorithms, such as TRPO and PPO trpo , employ trust region updates to improve stability. While these methods enhance convergence robustness, they remain susceptible to local optima. Exploratory techniques like \epsilon -greedy PG and entropy-regularized methods can potentially improve solution quality by promoting exploration. However, these undirected exploration methods often require exponential time to sufficiently explore high-diameter Markov Decision Processes (MDPs) PureExploration . Another line of work incorporates Monte Carlo Tree Search (MCTS) to unroll the running policy across multiple steps, improving the estimation of Q-values and leading to better performance AlphaZero . While MCTS reduces the variance of updates and facilitates faster, more stable convergence, it cannot escape the inherent limitation of converging to suboptimal stationary policies characteristic of standard PG methods. Lookahead extensions of policy iteration and policy mirror descent Efroni2018BeyondTO ; protopapas2024policymirrordescentlookahead have demonstrated faster convergence to global optima compared to non-lookahead variants. However, these methods require policy updates at all states during each iteration—a condition that is computationally infeasible for large-scale MDPs. In real-world scenarios, the state space may be prohibitively large or only partially known, making full-state updates impractical both in terms of exploration and memory requirements. The Policy Gradient with Tree Search (PGTS) method, as proposed in PGTS , demonstrates convergence to a globally optimal policy without requiring any conditions on the mismatch coefficient. While the original formulation relies on infinite tree search depth—a strong theoretical result—it is computationally impractical for real-world applications. Our work explores the practical utility of PGTS with finite tree depths across diverse MDP structures, including random MDPs, Ladder MDPs, Tightrope MDPs, and Gridworld MDPs. We observe that while PGTS behaves similarly to standard PG in well-connected random MDPs, it significantly outperforms PG in large-diameter MDPs such as Ladder and Gridworld. Notably, PGTS not only identifies higher-quality solutions but also accelerates the discovery of high-reward regions, leading to faster convergence. A key advantage of PGTS is highlighted in Tightrope MDPs, where its far-sighted strategy enables exploration of regions with temporary declines in returns, subsequently recovering and converging to optimal policies faster than standard PG. This contrasts with the monotonic improvement seen in PG, which may be shortsighted in such settings. While PGTS may not guarantee global optimality under local updates, we theoretically demonstrate that the number of stationary points decreases with increased tree depth. This property implies a reduction in local optima, enhancing solution quality as the tree depth grows. To our knowledge, this is the first bottom-up approach that systematically addresses the limitations of local optima in PG methods, contrasting with top-down approaches that impose restrictive global convergence assumptions SoftMaxPG_conv ; PG_conv_average_reward ; PG_ConvRate ; Natural_Actor_Critic_Conv_Bhatnagar . We believe that the development of sample-based PGTS methods compatible with deep neural networks has the potential to significantly enhance the performance of reinforcement learning in practice. However, understanding the convergence rate of PGTS remains a challenging task. We hypothesize that these rates may depend on structural properties of the MDP, such as its hardness, diameter, or connectivity—a direction we leave open for future exploration. 2 Preliminaries A Markov Decision Process (MDP) is defined as a tuple (\mathcal{S},\mathcal{A},P,R,\gamma,\mu) , where the components are as follows: \mathcal{S} and \mathcal{A} represent the state and action spaces; P\in(\Delta_{\mathcal{S}})^{\mathcal{S}\times\mathcal{A}} is the transition kernel; R\in\mathbb{R}^{\mathcal{S}\times\mathcal{A}} is the reward function; \gamma\in[0,1) is the discount factor; \mu\in\Delta_{\mathcal{S}} is the initial state distribution; and \Delta_{\mathcal{X}} denotes the probability simplex over the set \mathcal{X} puterman2014markov ; Sutton1998 . The set of policies \Pi includes all policies \pi\in\Pi , where \pi(a|s) is the probability of taking action a in state s . We use the shorthand notations P^{\pi}(s^{\prime}|s)=\sum_{a}\pi(a|s)P(s^{\prime}|s,a) and R^{\pi}(s)=\sum_{a}\pi(a|s)R(s,a) to represent the state transition probabilities and the expected reward under policy \pi , respectively. The objective in an MDP is to find a policy \pi\in\Pi that maximizes the return J^{\pi}:=\mu^{T}(I-\gamma P^{\pi})^{-1}R^{\pi}=E\Bigm[\sum_{k=0}^{\infty}\gamma^{k}R(s_{k},a_{k})\mid s_{0}\sim\mu,\pi,P\Bigm]. For shorthand J^{*}=\max_{\pi}J^{\pi} denotes the global optimal return and \pi^{*} is global optimal policy that achieves this optimal return. The first-order (one-step) gradient of the return is given by: \displaystyle\frac{\partial J^{\pi}}{\partial\pi(a|s)}=d^{\pi}(s)Q^{\pi}(s,a) (1) where d^{\pi}=\mu^{T}(I-\gamma P^{\pi})^{-1}=E[\sum_{k=0}^{\infty}\gamma^{k}\mathbf{1}(s_{k})\mid s_{0}\sim\mu,\pi,P] is the occupancy measure where \mathbf{1}(s)\in\mathbb{R}^{\St} is one-hot indicator vector for coordinate s , further, Q^{\pi}=R+\gamma Pv^{\pi} is the action-value (Q-value) function, and v^{\pi}=(I-\gamma P^{\pi})^{-1}R^{\pi} is the state-value function Sutton1998 . The update rule for policy gradient is then: \displaystyle\pi_{k+1}=\text{proj}_{\Pi}\left(\pi_{k}+\eta_{k}\frac{\partial J^{\pi_{k}}}{\partial\pi}\right), (2) where \eta_{k} is learning rate and proj_{\Pi} is projection operator on the policy space \Pi . This rule has been demonstrated to converge to a globally optimal solution under the condition of a bounded mismatch coefficient, \max_{\pi}\lVert\frac{d^{\pi^{*}}}{d^{\pi}}\rVert, which is guaranteed if \tilde{\mu}:=\min_{s}\mu(s)>0 agarwal2021theory ; xiao2022convergence ; PG_Conv_JLiu_Elementaryanalysispolicygradient_linearConv . Notably, \tilde{\mu}>0 also ensures \min_{s}d^{\pi}(s)>0 allowing for policy updates across all states at each iteration, effectively making the policy gradient (PG) method resemble a soft policy iteration However, satisfying the \tilde{\mu}>0 condition is challenging in practice, especially in large Markov Decision Processes (MDPs), especially with continuous state spaces. Moreover, even if we employ

Read the complete text