Introduction
In standard Reinforcement Learning (RL), the objective is straightforward: maximize a cumulative reward. Mathematically, this means the objective is a linear function of the occupancy measure—the distribution of time the agent spends across various state-action pairs. However, many modern RL challenges, such as apprenticeship learning, pure exploration, and skill discovery, do not fit this linear mold.
This paper introduces a novel Policy Gradient Theorem designed specifically for RL with general, non-linear utility functions. By demonstrating that the gradient of complex, non-linear objectives can be expressed in a form nearly identical to the standard policy gradient, the authors provide a simple, model-free algorithm capable of tackling high-dimensional RL problems without relying on complex mathematical dualities.
The Challenge of Non-Linear RL
In standard "Linear RL," the reward is a fixed number provided by the environment. But in non-linear RL, the "reward" depends on the agent's overall behavior. For example:
- Apprenticeship Learning: The agent attempts to match an expert's state-action distribution.
- Pure Exploration: The agent seeks to maximize the entropy of visited states.
- Skill Discovery: The agent learns diverse behaviors without a specific, static reward signal.
In these scenarios, the objective is a non-linear function of the occupancy measure. Standard tools like Bellman equations and classic Policy Gradients fail. Previous attempts to solve this, specifically for "Convex RL," relied on Fenchel duality—a mathematically complex approach that is notoriously difficult to implement in large-scale, model-free settings.
The Core Innovation: A Generalized Policy Gradient
The authors bridge this gap by deriving a Policy Gradient Theorem for non-linear RL.
Theorem 1: Virtual Rewards
The researchers prove that the gradient of a general utility function, $f(\mu^\pi)$, can be calculated with the same elegance as the standard policy gradient. The breakthrough lies in defining a "virtual" reward, $R_\theta$.
This virtual reward is simply the derivative of the utility function with respect to the occupancy measure. Essentially, the theorem shows that:
- A complex, non-linear goal can be treated as a standard RL problem.
- The "reward" for this standard problem is dynamic—it represents how much a small change in the agent's state-visitation frequency improves the overall non-linear objective.
Strikingly, this non-linear policy gradient looks almost exactly like the traditional one, utilizing the same $Q$-values and the same log-derivative of the policy ($\nabla_\theta \log \pi$). Furthermore, unlike previous work that required the objective to be convex, this derivation holds for general differentiable functions, including non-convex ones.
Model-Free Implementation
To translate this theory into practice, the authors propose a model-free algorithm (Algorithm 1) that operates on two distinct time-scales:
- Scale 1 (Occupancy Estimation): Iteratively estimates the current occupancy measure ($\mu$) based on the agent's trajectory. The authors provide a lemma proving that this iterative estimate ($\mu_n$) converges to the true measure ($\mu^\pi$) at a linear rate ($\gamma^n$).
- Scale 2 (Policy Update): Updates the policy parameters ($\theta$) using the derived gradient and the virtual reward calculated from the current estimate of $\mu$.
This bootstrapping of the occupancy measure is crucial for model-free RL, where the environment's transition dynamics are unknown.
Key Results and Theoretical Guarantees
As an ICLR "Tiny Paper," this work focuses purely on theoretical derivation and algorithm design rather than empirical benchmarks. Its primary contributions include:
- First Direct Derivation: Successfully providing the first direct derivation of a policy gradient for non-linear RL.
- Global Convergence for Convex RL: Proving that for the specific case of convex RL, this gradient method is guaranteed to converge to a global optimum under mild conditions.
- Stable Internal Estimates: Guaranteeing the linear convergence of the occupancy measure estimate, ensuring the algorithm remains stable during training.
Limitations and Future Work
While the theoretical foundation is robust, the paper acknowledges several limitations:
- Lack of Empirical Evidence: The paper does not include experimental results on datasets like MuJoCo or Atari. Future work must benchmark this algorithm against existing methods, such as Variational Policy Gradient, in complex environments.
- Non-Convex Optima: While the gradient can be calculated for non-convex functions, the algorithm is only guaranteed to find a local optimum in those cases. Finding global optima for general non-linear utilities remains an open challenge.
- Hyperparameter Sensitivity: The two-time-scale algorithm relies on two different learning rates ($\eta_t$ for occupancy and $\epsilon_t$ for policy). Balancing these rates is practically challenging and requires careful tuning.
Summary updated