Policy Gradient for Reinforcement Learning with General Utilities

Navdeep Kumar, Kaixin Wang, Kfir Levy, Shie Mannor

Abstract

In Reinforcement Learning (RL), the goal of agents is to discover an optimal policy that maximizes the expected cumulative rewards. This objective may also be viewed as finding a policy that optimizes a linear function of its state-action occupancy measure, hereafter referred as Linear RL. However, many supervised and unsupervised RL problems are not covered in the Linear RL framework, such as apprenticeship learning, pure exploration and variational intrinsic control, where the objectives are non-linear functions of the occupancy measures. RL with non-linear utilities looks unwieldy, as methods like Bellman equation, value iteration, policy gradient, dynamic programming that had tremendous success in Linear RL, fail to trivially generalize. In this paper, we derive the policy gradient theorem for RL with general utilities. The policy gradient theorem proves to be a cornerstone in Linear RL due to its elegance and ease of implementability. Our policy gradient theorem for RL with general utilities shares the same elegance and ease of implementability. Based on the policy gradient theorem derived, we also present a simple sample-based algorithm. We believe our results will be of interest to the community and offer inspiration to future works in this generalized setting.

Introduction

Standard Reinforcement Learning (RL) typically operates under the assumption that the agent's goal is to maximize the expected sum of rewards. Mathematically, this objective is a linear function of the "occupancy measure"—the distribution representing the frequency with which an agent visits specific state-action pairs. While this "Linear RL" framework has been highly successful, it fails to capture a wide array of sophisticated objectives where the utility is a non-linear function of the occupancy measure.

Examples of such "General RL" problems include:

  • Apprenticeship Learning: Minimizing the distance between an agent's occupancy measure and that of an expert.
  • Pure Exploration: Maximizing the entropy of visited states to ensure comprehensive environment coverage.
  • Constrained MDPs: Optimizing performance while strictly adhering to specific visitation constraints.

Historically, these problems required complex mathematical workarounds, such as Fenchel duality or stochastic saddle-point formulations, which are often difficult to implement and lack the intuitive appeal of standard policy gradient methods. This paper bridges that gap by deriving a Policy Gradient Theorem for General Utilities.

The Policy Gradient Theorem for General Utilities

The central contribution of this work is the derivation of a gradient for a general utility function $f(\mu^\pi)$ with respect to policy parameters $\theta$. The authors prove that this gradient can be expressed in a form remarkably similar to the classic Policy Gradient Theorem introduced by Sutton et al. (1999).

The Pseudo-Reward Insight

The key to this derivation is the introduction of a "pseudo-reward," denoted as $R_\pi$. By applying the chain rule, the authors show that the gradient of a non-linear utility can be treated as a local linear reward. Specifically, $R_\pi$ is defined as the derivative of the utility function with respect to the occupancy measure ($R_\pi = \nabla_{\mu} f$).

At any given iteration, the agent effectively performs standard RL using this shifting reward signal. This allows the framework to recover the original Policy Gradient Theorem exactly when a standard linear reward function is applied, confirming that this theory is a true generalization of existing RL foundations.

Algorithmic Framework

To translate this theory into practice, the authors propose a sample-based algorithm designed to handle the dependencies between the policy, the occupancy measure, and the resulting pseudo-rewards.

  1. Occupancy Measure Estimation: Since the pseudo-reward depends on the current occupancy measure, the algorithm must estimate $\mu^\pi$ on the fly. The authors propose a bootstrapping method, akin to Temporal Difference (TD) learning, to update this estimate from samples.
  2. Parallel Updates: The proposed algorithm (Algorithm 1) updates three components in parallel: the occupancy measure, the Q-values (derived from the pseudo-reward), and the policy parameters.
  3. Function Approximation: The theory extends to function approximators like neural networks. The authors demonstrate that if the approximation is "compatible" with the policy, the resulting gradient remains exact, ensuring the method's applicability to high-dimensional state spaces.

Key Theoretical Results

  • Theorem 1 (Policy Gradient for Convex RL): Provides the exact formula: $\nabla_\theta f = \sum_{s,a} \mu^\pi(s) Q^\pi_{R_\pi}(s, a) \nabla_\theta \pi(a|s)$. This confirms that the standard policy gradient architecture is robust enough to accommodate general utilities without fundamental structural changes.
  • Linear Convergence: The authors provide a solid theoretical foundation for their iterative occupancy estimation, proving in Lemma 1 that the method converges linearly to the true measure.

Discussion and Future Work

This work offers an elegant theoretical bridge, yet it opens several avenues for further research. Because the algorithm involves three nested updates (occupancy, Q-values, and policy), balancing the learning rates for these multi-timescale stochastic processes remains a practical challenge.

Furthermore, while the derivation assumes the utility function $f$ is differentiable—which covers common metrics like KL-divergence and $L_2$ distance—future extensions may be needed for non-smooth constraints. Finally, as a purely theoretical contribution, the next logical step is empirical validation to compare this approach against existing Variational Policy Gradient methods in complex, high-dimensional environments.

Summary updated

Abstract

In Reinforcement Learning (RL), the goal of agents is to discover an optimal policy that maximizes the expected cumulative rewards. This objective may also be viewed as finding a policy that optimizes a linear function of its state-action occupancy measure, hereafter referred as Linear RL. However, many supervised and unsupervised RL problems are not covered in the Linear RL framework, such as apprenticeship learning, pure exploration and variational intrinsic control, where the objectives are non-linear functions of the occupancy measures. RL with non-linear utilities looks unwieldy, as methods like Bellman equation, value iteration, policy gradient, dynamic programming that had tremendous success in Linear RL, fail to trivially generalize. In this paper, we derive the policy gradient theorem for RL with general utilities. The policy gradient theorem proves to be a cornerstone in Linear RL due to its elegance and ease of implementability. Our policy gradient theorem for RL with general utilities shares the same elegance and ease of implementability. Based on the policy gradient theorem derived, we also present a simple sample-based algorithm. We believe our results will be of interest to the community and offer inspiration to future works in this generalized setting.
BibTeX
@misc{kumar2022policy,
  author = {Navdeep Kumar and Kaixin Wang and Kfir Levy and Shie Mannor},
  title = {{Policy Gradient for Reinforcement Learning with General Utilities}},
  year = {2022},
  eprint = {2210.00991},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2210.00991},
}

Loading related content...

Figure