In standard reinforcement learning (RL), we typically parameterize a policy $\pi(a|s)$ directly—such as through a neural network or a tabular softmax distribution—and optimize its parameters to maximize the expected sum of rewards. While intuitive, this formulation hides a fundamental mathematical challenge: the objective function is highly non-convex with respect to the policy parameters.
This non-convexity arises because a policy determines actions, which change the state distribution, which in turn changes where the policy is evaluated. This compounding feedback loop means that standard policy gradient methods can suffer from local optima, optimization instability, and a complete breakdown when dealing with non-linear utilities (such as maximizing entropy or enforcing group fairness) or adversarial environments where rewards change unpredictably.
To bypass this trap, a powerful paradigm reformulates the problem entirely. Instead of asking "what action should I take in this state?", we ask "how often will I visit this state-action pair?" This shift moves the optimization from the non-convex space of policy parameters to the convex space of occupancy measures.
Shifting Perspectives: What is an Occupancy Measure?
An occupancy measure $q(s, a)$ represents the expected discounted frequency (or total probability in episodic settings) that an agent visits state $s$ and executes action $a$ under a given policy.
Crucially, there is a direct mapping between valid occupancy measures and policies. If you know the occupancy measure $q(s,a)$, you can recover the exact policy that generated it simply by normalizing the distribution over actions:
$$\pi(a|s) = \frac{q(s,a)}{\sum_{a'} q(s,a')}$$
However, you cannot just pick any arbitrary distribution over states and actions and call it an occupancy measure. The distribution must respect the physical laws of the environment—meaning the "inflow" of probability into any given state must equal the "outflow." This requirement is captured by the Bellman flow constraints:
$$\sum_{a'} q(s', a') = \mu_0(s') + \gamma \sum_{s, a} q(s, a) P(s' | s, a)$$
where $\mu_0(s')$ is the initial state distribution, $\gamma$ is the discount factor, and $P(s'|s,a)$ represents the transition dynamics. Because $q(s,a)$ appears linearly in these constraints, the set of all valid occupancy measures forms a convex polytope.
The Magic of Convexification
Why is operating within this polytope so advantageous? When we express the standard reinforcement learning objective in terms of the occupancy measure $q(s,a)$, the expected long-term reward becomes a purely linear function of our decision variables:
$$\max_{q} \sum_{s,a} q(s,a) R(s,a)$$
As Montufar et al. demonstrate in Geometry and convergence of natural policy gradient methods, mapping the RL objective to the state-action frequency polytope transforms a complex sequential decision problem into a linear optimization problem over a convex set.
By focusing on the dual linear programming formulation of Markov Decision Processes (MDPs), the optimization problem shifts from value functions to stationary distributions. Malek et al. leverage this in Linear Programming for Large-Scale Markov Decision Problems to show how stochastic convex optimization can handle massive state spaces where traditional dynamic programming fails. This perspective allows researchers to deploy the full arsenal of convex analysis, bypassing traditional value-iteration loops entirely to provide strong performance guarantees (Revisiting the Linear-Programming Framework for Offline RL with General Function Approximation).
Even in more complex settings, such as partially observable environments, this representational shift provides clarity. Dressler et al. extend this perspective to memoryless policies in POMDPs in Algebraic optimization of sequential decision problems, characterizing the feasible set through linear constraints and determinantal varieties to isolate global optima.
Taming Non-Linear Utilities and Global Constraints
The true power of occupancy measures shines when moving beyond simple linear reward summation. Many modern RL problems involve objectives that are non-linear functions of the state-action distribution. Examples include:
- Exploration: Maximizing the entropy of the state-visitation distribution to explore reward-free environments (Provably Efficient Maximum Entropy Exploration; Active Model Estimation in Markov Decision Processes.).
- Security: Minimizing information leakage to an adversarial observer (Least Inferable Policies for Markov Decision Processes).
- Fairness: Ensuring demographic parity or balanced resource allocation across multiple agents (A Reinforcement Learning Based Approach for Joint Multi-Agent Decision Making; Achieving Fairness in Multi-Agent MDP Using Reinforcement Learning).
In the policy space, these objectives break the Bellman optimality principle because the reward at a given step depends globally on the history of the policy's deployment. In the occupancy measure space, however, these objectives remain clean, solvable concave or convex optimization problems.
For instance, Koppel et al. exploit this hidden convexity in Variational Policy Gradient Method for Reinforcement Learning with General Utilities to establish global convergence guarantees for general utilities using Fenchel duality.
Direct Policy Space (Non-Convex) Occupancy Measure Space (Convex Polytope)
┌────────────────────────────────┐ ┌────────────────────────────────────────┐
│ π(a|s) parameters │ │ q(s,a) frequencies │
│ │ │ │
│ Objective: Highly non-convex │ =====> │ Objective: Linear / Concave │
│ Constraints: Implicit, complex│ │ Constraints: Linear Bellman Flow │
│ (Local optima traps) │ │ (Global convergence guaranteed) │
└────────────────────────────────┘ └────────────────────────────────────────┘
Similarly, global safety or resource constraints can be expressed as simple linear bounds on $q(s,a)$. This enables exact solutions via linear programming (A Sample-Efficient Algorithm for Episodic Finite-Horizon MDP with Constraints) or semi-infinite programming when constraints exist on a continuous spectrum (Semi-infinitely Constrained Markov Decision Processes).
Sun demonstrates in Reinforcement Learning with Stepwise Fairness Constraints that mapping trajectories to occupancy measures allows complex sequential policies to be optimized through quadratically constrained linear programming, ensuring group fairness at every single time step. Even in imitation learning, Boularias et al. show in Bootstrapping Apprenticeship Learning that treating expert demonstrations as constraints on occupancy measures guarantees that recovered strategies strictly satisfy the underlying transition physics.
Thriving in Adversarial and Non-Stationary Worlds
In many real-world scenarios, the environment is non-stationary or adversarial: rewards or losses change arbitrarily between episodes. Direct policy optimization struggles here because a small change in policy parameters can catastrophically alter the distribution of visited states, leading to high regret.
By optimizing over occupancy measures via Online Mirror Descent (OMD) or Follow-the-Regularized-Leader (FTRL), agents can smoothly update their target state-action frequencies. Zimin et al. pioneered this with O-REPS (Online learning in episodic Markovian decision processes by relative entropy policy search), proving that regularizing occupancy measure updates with relative entropy yields near-optimal regret bounds in adversarial environments.
When the environment's transition dynamics are unknown, agents can combine occupancy measure optimization with optimistic transition estimates (Online Stochastic Shortest Path with Bandit Feedback and Unknown Transition Function) or log-barrier regularization (Efficient Rate Optimal Regret for Adversarial Contextual MDPs Using Online Function Approximation) to safely explore while minimizing regret.
Zhao et al. expand this in Dynamic Regret of Online Markov Decision Processes, utilizing mirror descent on clipped occupancy measures to compete effectively against a sequence of changing optimal policies without knowing environmental volatility in advance.
Li further refines these bounds for adversarial linear mixture MDPs under bandit feedback in Improved Algorithm for Adversarial Linear Mixture MDPs with Bandit Feedback and Unknown Transition, performing robust strategy updates by leveraging visitation data across the entire occupancy space.
Ultimately, by transforming sequential decision-making into a structured convex optimization task, occupancy measure optimization provides a mathematically rigorous foundation for reinforcement learning. It ensures that whether an agent is navigating adversarial losses, balancing multi-agent fairness, or satisfying strict safety boundaries, it can find a globally optimal strategy through predictable, stable updates.