Stochastic Optimality in Constrained Markov Decision Processes

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 282 papers123 conceptsfrozen 2026-10-04

In standard reinforcement learning, we are taught that there always exists an optimal deterministic policy. If you know the state of the world perfectly, there is one "best" action to take. However, as soon as you introduce constraints—such as a safety budget, a battery limit, or a risk threshold—this fundamental rule of thumb breaks. In Constrained Markov Decision Processes (CMDPs), the optimal way to behave is often to flip a coin.

The Geometry of Constraints

To understand why randomness becomes necessary, consider the trade-off between reward and safety. In an unconstrained environment, an agent simply seeks the highest point on the reward landscape. In a constrained environment, that peak might be "off-limits" because it violates a safety boundary.

As Xun Shen, Akifumi Wachi, and colleagues explain in Flipping-based Policy for Chance-Constrained Markov Decision Processes, a deterministic policy is often either too conservative (staying far away from the danger but losing reward) or too aggressive (getting high reward but violating the constraint). A stochastic policy allows the agent to interpolate between these two behaviors. By choosing a high-reward action with probability $p$ and a safe action with probability $1-p$, the agent can land exactly on the constraint boundary, maximizing utility while strictly adhering to the budget.

This isn't just a theoretical curiosity. Krishnendu Chatterjee and Petr Novotný demonstrate in Reinforcement Learning of Risk-Constrained Policies in Markov Decision Processes that using linear programming to calculate these exact action probabilities allows agents to find optimal "mixed strategies" that deterministic approaches simply cannot represent.

Why Greedy Algorithms Fail

The necessity of stochasticity creates a massive headache for standard RL algorithms like Q-learning. Traditional Q-learning is "max-seeking"—it looks for the single best action and updates toward it. But in a CMDP, the "best" behavior isn't a single action; it's a distribution.

Honghao Wei and Lei Ying point out in A Provably-Efficient Model-Free Algorithm for Infinite-Horizon Average-Reward Constrained Markov Decision Processes that max-seeking rules often fail to converge in these settings. Instead, they advocate for on-policy update rules that can naturally represent and converge to randomized optimal strategies.

Furthermore, Jaeyoung Lee and Krzysztof Czarnecki show in Recursive Constraints to Prevent Instability in Constrained Reinforcement Learning that the constrained Bellman operator actually lacks a fixed point when restricted to deterministic policies. This causes "policy oscillation," where the agent's strategy constantly jumps back and forth between being "too safe" and "too risky," never settling on a stable solution.

Mechanisms of Randomization

Researchers have identified several ways this stochasticity manifests in optimal behavior:

  1. Action Flipping: For an MDP with a single constraint, Shen et al. proved that the optimal policy only needs to randomize between at most two actions in any given state. This "binary stochasticity" is enough to satisfy the risk budget.
  2. Initial Coin Flips: In more complex scenarios involving temporal logic (LTL) constraints, Leon Witzman and Luke Ong found in Reinforcement Learning with ω-Regular Objectives and Constraints that the agent might only need to be stochastic once. At the very start of an episode, the agent "flips a coin" to choose between two different deterministic stationary strategies and then follows that choice to the end.
  3. Mixing Arms: Even in simpler "bandit" settings, Meltem Tatlı and Ali Tajer show in Preference-centric Bandits: Optimality of Mixtures and Regret-efficient Algorithms that if your goal is to optimize for a specific risk profile (like tail behavior), the optimal strategy is to play a mixture of different arms rather than just the one with the highest mean.

The Trade-off with Interpretability

While stochasticity is mathematically superior, it poses a challenge for real-world deployment. In safety-critical systems like autonomous driving or medical robotics, we often want predictable, deterministic behavior.

As Dmitri A. Dolgov discusses in Stationary Deterministic Policies for Constrained MDPs, enforcing determinism in these environments creates a "performance gap." You are essentially leaving reward on the table to ensure the robot doesn't act unpredictably. This tension defines the current frontier of the field: how to design algorithms like ReLOAD, proposed by Ted Moskovitz and colleagues in Reinforcement Learning with Optimistic Ascent-Descent, that can handle the inherent stochasticity of the problem while still converging to stable, usable control laws.

Papers in this version

Showing 60 of 82 papers.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 65 papers
  2. Version 1 · 2026-10-04 · 82 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_randomized_policy_optimization_1f403fe0,
  title = {randomized policy optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/randomized-policy-optimization/rdr_1f403fe05366476280db13755e5dd1ec},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_stochastic_optimality_in_constrained_mar_1f403fe0_v1,
  title = {Stochastic Optimality in Constrained Markov Decision Processes},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/stochastic-optimality-in-constrained-markov-decision-processes/rdr_1f403fe05366476280db13755e5dd1ec/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}