Policy Gradient with Tree Search (PGTS) in Reinforcement Learning Evades Local Maxima

Navdeep Kumar, Priyank Agrawal, Kfir Yehuda Levy, Shie MannorICLR 2024 · OpenReview

In the world of Reinforcement Learning (RL), Policy Gradient (PG) methods are the workhorses of the industry. They are behind many of the most famous breakthroughs in AI, from mastering complex video games to controlling nuclear fusion plasma. However, PG methods have a notorious "Achilles' heel": they are incredibly prone to getting stuck in local maxima.

A recent paper, "Policy Gradient with Tree Search (PGTS) in Reinforcement Learning Evades Local Maxima," provides a theoretical bridge between two worlds—planning and optimization—to solve this exact problem.

The Problem: The Myopia of Standard Policy Gradients

Standard Policy Gradient methods often fail because they only look one step ahead, causing them to get trapped in sub-optimal solutions. Imagine navigating a dark maze by feeling the walls one inch at a time; if you find a comfortable corner, you might stay there forever, never realizing there’s a treasure room just two turns away.

Mathematically, the "return function" in RL is highly non-concave. Because PG methods follow the first-order gradient of this function, they act as "greedy" one-step improvers. If the immediate gradient doesn't point toward a reward, the agent stops learning. While Dynamic Programming can solve this, it suffers from the "curse of dimensionality," becoming computationally impossible as the environment grows. The authors set out to prove that adding "lookahead" (Tree Search) to PG can bridge the gap between greedy optimization and global planning.

Methods: Policy Gradient with Tree Search (PGTS)

The authors introduce Policy Gradient with Tree Search (PGTS). The core innovation is the $m$-step lookahead gradient.

Instead of calculating the gradient based on the immediate next state, PGTS uses a tree search of depth $m$. The gradient is redefined using the $m$-th power of the optimal Bellman operator ($T^m$).

Essentially, the update rule becomes: $$\nabla^m_\pi(s, a) = d^\pi(s)(T^m Q^\pi)(s, a)$$

Where:

  • $d^\pi(s)$ is the state occupancy measure (how often we visit a state).
  • $T^m Q^\pi$ represents the value found after looking $m$ steps into the future and picking the best possible actions.

This allows the gradient to "see" rewards that are many steps away, even if the current path yields nothing but zeros.

The Ladder MDP: A Conceptual Testbed

As a study focused on fundamental theory, the authors do not use massive benchmarks like Atari or MuJoCo. Instead, they use a conceptual "toy" environment called the Ladder MDP.

The Ladder MDP environment

In the Ladder MDP, an agent starts at $s_0$ and can go "left" or "right." A reward of 1 exists only at the very end of the chain ($s_4$). If the agent's initial policy is to always go "left," a standard 1-step gradient will see a reward of 0 in both directions and never change its behavior. It is stuck in a local maximum. The authors use this environment to demonstrate how PGTS overcomes the "blindness" of standard PG.

Key Insights and Results

By integrating Tree Search (TS) into the gradient calculation, the authors prove that increasing the search depth systematically eliminates local maxima, eventually guaranteeing convergence to a global optimum.

  • The Horizon Matters: The paper establishes a direct mathematical link between search depth and the optimization landscape. As the tree search length ($m$) increases, the number of local maxima in the return function decreases.
  • Global Convergence (Theorem 1): The authors prove that in the limiting case ($m = \infty$ and an infinite learning rate), PGTS will converge to the global optimal solution in at most $S$ steps (where $S$ is the number of states).
  • Compact Representation: The complex $m$-step lookahead can be written compactly using the optimal Bellman operator, making it easier to analyze theoretically.
  • Ladder MDP Success: While standard PG fails on the Ladder MDP (the gradient remains zero), PGTS with a sufficient $m$ successfully identifies the path to the reward and updates the policy toward the global optimum.

Limitations and Future Work

While the theoretical results are promising, there are practical hurdles to address in future research:

  • Computational Complexity: Performing a deep tree search at every gradient step is computationally expensive. The "infinite $m$" case is a theoretical ideal, not a practical algorithm.
  • Finite Search Depth: The paper proves the limit case ($m = \infty$), but the exact behavior and "quality" of convergence for finite, practical values of $m$ (like $m=3$ or $m=5$) remains an open question.
  • Learning Rate: The current proof assumes an infinite learning rate for the $S$-step convergence; extending this rigorously to finite learning rates is a suggested next step.

Paper Citation: Kumar, N., Agrawal, P., Levy, K., & Mannor, S. (2024). Policy Gradient with Tree Search (PGTS) in Reinforcement Learning Evades Local Maxima. Published as a Tiny Paper at ICLR 2024.

Summary updated

Abstract

The policy gradient (PG) methods are being extensively used in practice. However, their theoretical convergence guarantees require strict regularity conditions. Such conditions are unnatural and generally not satisfied in practice, causing such techniques to get stuck in a sub-optimal local maximum (rewards). Tree search (TS) methods, have been recently shown to enjoy strong empirical performance in related planning tasks. In this work, we attempt at first theoretical analysis of Tree search-based policy gradient and its convergence properties. Specifically, we show that for a large tree length, the number of local maxima decreases, and therefore in the limiting case, PG converges to a global optimal solution.
BibTeX
@inproceedings{kumar2024policy,
  author = {Navdeep Kumar and Priyank Agrawal and Kfir Yehuda Levy and Shie Mannor},
  title = {{Policy Gradient with Tree Search (PGTS) in Reinforcement Learning Evades Local Maxima}},
  booktitle = {International Conference on Learning Representations},
  year = {2024},
  url = {https://openreview.net/forum?id=61g5xxWOI6},
}
Figure