Standard Reinforcement Learning (RL) operates under a foundational assumption: the agent's goal is to maximize the expected cumulative sum of scalar rewards. Mathematically, this means the objective is a linear function of the state-action occupancy measure (the long-term distribution of states and actions visited by the policy). This linearity is incredibly convenient because it gives rise to the Bellman optimality equation, allowing us to break down a long-term planning problem into recursive, step-by-step updates.
However, many real-world objectives cannot be expressed as a simple sum of step-wise rewards. Consider these scenarios:
- Exploration: An agent trying to maximize the entropy of its state visitation distribution to map out an unknown environment.
- Imitation Learning: An apprentice agent trying to minimize the KL-divergence between its own occupancy measure and an expert's distribution.
- Fairness: A multi-agent system trying to maximize a non-linear welfare function to ensure resources are distributed equitably.
In all these cases, the objective is a nonlinear function of the occupancy measure. When we move to this broader paradigm—known as Reinforcement Learning with General Utilities (RLGU) or Concave Utility RL—the traditional Bellman equation completely breaks down.
The Linearity Trap and the Bellman Breakdown
To understand why traditional methods fail, let's look at the math. In standard RL, the objective $J(\pi)$ for a policy $\pi$ can be written as the inner product of the state-action occupancy measure $\rho_\pi$ and the reward function $r$:
$$J(\pi) = \sum_{s,a} \rho_\pi(s,a) r(s,a)$$
Because this relationship is linear, the value of taking an action in a specific state depends only on the immediate reward and the discounted future value of subsequent states.
In RLGU, as explained by Anas Barakat et al. in Reinforcement Learning with General Utilities: Simpler Variance Reduction and Large State-Action Space, the objective is modified to $J(\pi) = f(\rho_\pi)$, where $f$ is a non-linear function. As Alec Koppel et al. note in Variational Policy Gradient Method for Reinforcement Learning with General Utilities, this causes the standard definition of a value function to lose its recursive structure. The value of an action at state $A$ now depends on the agent's aggregate behavior across the entire environment, including completely unrelated states $B$ and $C$. If you change your policy in state $B$, it alters the global occupancy measure $\rho_\pi$, which changes the gradient of $f$, thereby altering the optimal choice in state $A$.
Without the Bellman equation, value-based methods like Q-learning or value iteration cannot be directly applied. Researchers have therefore developed three primary mechanisms to bypass this limitation and optimize non-linear utilities directly.
Mechanism 1: Linearization via Shadow Rewards
The most intuitive way to handle a non-linear utility function $f(\rho_\pi)$ is to approximate it locally. If we treat the utility function as a curved surface, we can find the tangent plane to that surface at our current policy's occupancy measure. The gradient of the utility function with respect to the occupancy measure, $\nabla f(\rho_\pi)$, acts as a local, linear surrogate.
This insight forms the basis of the "Shadow Reward" framework. As demonstrated by Amrit Bedi et al. in Multi-Agent Reinforcement Learning with General Utilities via Decentralized Shadow Reward Actor-Critic, we can define a time-varying, state-action-dependent proxy reward:
$$r_{\text{shadow}}(s,a) = \left[ \nabla f(\rho_\pi) \right]_{s,a}$$
By treating this shadow reward as a standard scalar reward, the authors show that the complex non-linear problem can be solved using modified versions of standard policy gradient algorithms. In Policy Gradient for Reinforcement Learning with General Utilities, Navdeep Kumar et al. derive a generalized Policy Gradient Theorem, proving that if we can accurately estimate the current occupancy measure $\rho_\pi$ and evaluate the shadow reward, the resulting policy updates will reliably converge toward the global optimum.
Mechanism 2: Bypassing Bellman via Fenchel Duality
When the utility function $f$ is concave (which is true for entropy, fairness metrics, and many risk measures), we can use convex analysis to transform the problem. Fenchel duality allows us to represent a concave function as the infimum of a family of linear functions:
$$f(\rho_\pi) = \min_{y} \left( \langle \rho_\pi, y \rangle - f^*(y) \right)$$
where $f^*$ is the Fenchel conjugate of $f$, and $y$ is a dual variable.
By substituting this into the RL objective, the authors of Variational Policy Gradient Method for Reinforcement Learning with General Utilities reformulate the non-linear RL problem as a stochastic saddle-point (minimax) problem:
$$\max_{\pi} \min_{y} \left( \mathbb{E}_{\rho_\pi}[y(s,a)] - f^*(y) \right)$$
Notice what happened to the expectation: for a fixed dual variable $y$, the term $\mathbb{E}_{\rho_\pi}[y(s,a)]$ is perfectly linear with respect to the occupancy measure. The dual variable $y$ effectively steps into the role of a standard reward function. By alternating between updating the policy $\pi$ (using standard RL steps with $y$ as the reward) and updating the dual variable $y$, the algorithm bypasses the broken Bellman equation entirely, achieving provable global convergence.
Mechanism 3: Geometry of the Occupancy Manifold
A third perspective views the problem through a purely geometric lens. The set of all valid state-action occupancy measures that satisfy an environment's transition dynamics forms a convex polytope embedded in a higher-dimensional space. Every valid policy maps to exactly one point on this "occupancy manifold."
Non-linear Utility Surface f(ρ)
_ .
- - - . _
/ \ <- Peak Utility
| .---. |
/ / \ \
====|=====|=======|=======|==== Occupancy Manifold (Polytope)
| | ρ_π | |
\ \ / /
| '---' |
\_ _ _ _ _ _ _ _/
As explained by Nico Scherf et al. in The Geometry of Nonlinear Reinforcement Learning, optimizing a general utility means finding the point on this manifold that maximizes $f(\rho)$. Instead of updating policy parameters in a highly non-convex parameter space, we can perform optimization directly on the distribution space using Mirror Descent.
In Efficient Model-Based Concave Utility Reinforcement Learning through Greedy Mirror Descent, Bianca Marin Moreno et al. leverage this geometry to develop algorithms that update the policy such that its corresponding occupancy measure moves smoothly across the manifold toward the utility's peak. This geometric approach avoids the non-convex mapping from policy parameters to behavior distributions, providing clean closed-form updates and bypassing expensive projection steps.
Applications and Extensions
By formalizing objectives as non-linear functions of the occupancy measure, the RLGU framework provides a unified mathematical language for several distinct subfields:
Multi-Agent Coordination
In large-scale multi-agent systems, computing global occupancy measures is communication-heavy and impractical. However, Donghao Ying et al. demonstrate in Scalable Multi-Agent Reinforcement Learning with General Utilities that because agent interactions often weaken over physical distance (spatial correlation decay), teams of agents can optimize complex global utilities—like collective exploration or safe operation—by communicating solely within local neighborhoods.
Behavioral Economics and Risk
Traditional risk-averse RL typically optimizes simple variance constraints. In Beyond Expected Returns: A Policy Gradient Algorithm for Cumulative Prospect Theoretic Reinforcement Learning, Olivier Lepel et al. use general utilities to implement Cumulative Prospect Theory (CPT). This allows agents to model human-like decision-making, such as the non-linear overestimation of rare risks and asymmetric evaluation of gains versus losses, scaling efficiently to high-dimensional tasks.
Algorithmic Fairness
When multiple agents share an environment, maximizing the simple sum of rewards can result in policies that exploit certain agents for the benefit of others. To enforce fairness, Peizhong Ju et al. in Achieving Fairness in Multi-Agent MDP Using Reinforcement Learning utilize occupancy-measure-based convex optimization to maximize non-linear welfare functions (such as Nash bargaining solutions), guaranteeing fair outcomes even when the underlying environment dynamics are completely unknown.