Direct Policy Gradients: Direct Optimization of Policies in Discrete Action Spaces

Guy Lorberbom, Chris J. Maddison, Nicolas Heess, Tamir Hazan, Daniel Tarlow

Introduction

In reinforcement learning (RL) with discrete action spaces, agents must learn a policy that maximizes expected returns. Because evaluating every possible sequence of actions is computationally intractable, algorithms typically rely on approximations like REINFORCE, which estimate the gradient by sampling trajectories from the agent's current policy.

However, passive sampling is highly inefficient in sparse-reward environments. If an agent only receives a reward for a very specific sequence of actions, sampling from an untrained (mostly uniform) policy will almost always yield zero reward and, consequently, a zero gradient.

This paper introduces Direct Policy Gradients (DirPG), a novel RL algorithm that replaces standard policy gradient sampling with heuristic-guided optimization. By asking whether we can use optimization and search heuristics (like A search) to actively find good trajectories, the authors combine the Gumbel-max trick with A sampling. This allows DirPG to actively search for high-reward trajectories to compute gradients, offering an exponentially higher chance of finding informative learning signals in sparse-reward environments.

Methods

The authors build on a framework called Direct Optimization, which approximates gradients of discrete variables by optimizing a randomized objective function.

  1. Trajectory-Level Reparameterization: They use the Gumbel-max trick to reparameterize the sampling process. Sampling a trajectory from the policy is mathematically equivalent to finding the trajectory $a_{opt}$ that maximizes a Gumbel-perturbed log-probability score.
  2. The Direct Objective: They define a new target trajectory, $a_{dir}$, which maximizes the same Gumbel-perturbed score plus the environment reward scaled by a parameter $\epsilon$. Essentially, $a_{dir}$ is pulled toward higher rewards.
  3. The Gradient Update: The policy gradient is approximated by the difference between the log-probabilities of $a_{dir}$ (the better trajectory) and $a_{opt}$ (the standard sample).
  4. A* Sampling: Finding $a_{dir}$ naively requires exhaustive search. To make this efficient, the authors adapt A* sampling. By using domain knowledge in the form of upper bounds on the "return-to-go" (heuristics), the algorithm prunes the search tree and finds $a_{dir}$ using a minimal number of environment interactions.
Algorithm 1: Direct Policy Gradient
Note: Because the algorithm needs to explore multiple trajectories under the exact same environmental noise conditions to isolate the effect of the agent's actions, DirPG requires access to a simulator during training.

Key Insights

  • Active Search Beats Passive Sampling: In sparse reward regimes, DirPG has an exponentially higher probability of sampling an informative (non-zero) gradient compared to REINFORCE because it actively searches for the reward rather than waiting to stumble upon it.
  • $\epsilon$ Controls Risk Sensitivity: In previous direct optimization literature, $\epsilon$ was viewed merely as a numerical finite-difference approximation. The authors prove it actually controls the agent's risk profile. A positive $\epsilon$ makes the agent risk-seeking, while a negative $\epsilon$ makes it risk-averse.
  • Built-in Variance Reduction: The $a_{opt}$ term in the DirPG gradient update naturally acts as a control variate, meaning the algorithm inherently reduces gradient variance without needing a separately trained baseline network (like a critic).
  • Approximate Search is Sufficient: You don't need to run A to perfect completion. The authors show that finding an approximate* $a_{dir}$ that is just somewhat better than $a_{opt}$ still provides a valid and effective signal for the policy to improve.

Experimental Results

The authors evaluate DirPG across three distinct environments to test its versatility and theoretical properties:

1. Combinatorial Bandits Tested on a graph-based spanning tree problem, DirPG was compared against Upper Confidence Bound (UCB) algorithms. DirPG proved highly competitive with, and often outperformed, comparable UCB bandit algorithms, automatically scaling the number of search interactions it needed as learning progressed.

Performance comparison on Combinatorial Bandits

2. Risk Control (DeepSea) DeepSea is a 5x5 grid environment specifically designed to test an agent's risk sensitivity, forcing a choice between a safe path with zero variance and a risky path with high variance. Empirical results perfectly matched the theory: when trained with $\epsilon < 0$, the agent converged entirely on the "safe" policy. When $\epsilon > 0$, the agent split its mass to seek the "risky" policy.

3. MiniGrid-MultiRoom-N6-v0 In this partially observable grid-world where the agent must navigate rooms and open doors, DirPG was tested against REINFORCE and Cross-Entropy baselines. Using a weighted A* heuristic ($\alpha = 0.3$) to guide the search for $a_{dir}$ yielded the best performance, successfully trading off search depth and breadth. DirPG achieved higher average returns in fewer episodes compared to the baselines.

Limitations and Future Work

While powerful, DirPG currently has two main limitations. First, it requires a simulator at training time to reset the environment and explore different branches under the exact same random seed. Second, it operates under an episodic constraint, requiring complete trajectories to compute the updates.

The authors are actively exploring how to remove the episodic limitation. They also suggest applying DirPG to real-world domains where heuristic search and upper bounds are traditionally very strong, such as complex navigation, combinatorial optimization, and program synthesis.

Summary updated

Abstract

Direct optimization (McAllester et al., 2010; Song et al., 2016) is an appealing framework that replaces integration with optimization of a random objective for approximating gradients in models with discrete random variables (Lorberbom et al., 2018). A* sampling (Maddison et al., 2014) is a framework for optimizing such random objectives over large spaces. We show how to combine these techniques to yield a reinforcement learning algorithm that approximates a policy gradient by finding trajectories that optimize a random objective. We call the resulting algorithms \emph{direct policy gradient} (DirPG) algorithms. A main benefit of DirPG algorithms is that they allow the insertion of domain knowledge in the form of upper bounds on return-to-go at training time, like is used in heuristic search, while still directly computing a policy gradient. We further analyze their properties, showing there are cases where DirPG has an exponentially larger probability of sampling informative gradients compared to REINFORCE. We also show that there is a built-in variance reduction technique and that a parameter that was previously viewed as a numerical approximation can be interpreted as controlling risk sensitivity. Empirically, we evaluate the effect of key degrees of freedom and show that the algorithm performs well in illustrative domains compared to baselines.
BibTeX
@inproceedings{lorberbom2020direct,
  author = {Guy Lorberbom and Chris J. Maddison and Nicolas Heess and Tamir Hazan and Daniel Tarlow},
  title = {{Direct Policy Gradients: Direct Optimization of Policies in Discrete Action Spaces}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=rcbqcMc8ec},
}
Figure