In standard reinforcement learning, we are accustomed to a comforting mathematical guarantee: for any finite Markov Decision Process (MDP), there always exists an optimal policy that is entirely deterministic. If a specific action yields the highest expected long-term reward in a given state, the agent should simply select that action 100% of the time.
However, this foundational assumption completely breaks down the moment we introduce real-world constraints—such as safety budgets, risk limits, or fairness requirements. In a Constrained MDP (CMDP), the mathematically optimal strategy is frequently stochastic. Why does adding a constraint force an agent to become deliberately unpredictable?
The Geometry of Budget Matching
To build intuition, imagine an autonomous vehicle deciding how to navigate a highway. The vehicle can choose between two primary behaviors: a high-speed, high-reward action that carries a higher risk of a safety violation, and a low-speed, low-reward action that is perfectly safe.
Now, suppose we give the vehicle a strict safety budget: it must maintain an average risk threshold that lies exactly halfway between the risks of these two actions. If the vehicle is restricted to a deterministic policy, it faces a dilemma. Choosing the high-speed action violates the safety constraint, while choosing the low-speed action satisfies safety but leaves substantial performance on the table.
As Nicolas Carrara et al. demonstrate in Budgeted Reinforcement Learning in Continuous State Space, the optimal behavior in such scenarios requires a stochastic mixture of actions. By alternating probabilistically between the high-risk and low-risk options, the agent can achieve a precise target risk level that no single deterministic action could satisfy.
Geometrically, deterministic policies only allow the agent to reach discrete vertices in the objective space. Randomization allows the agent to navigate the convex hull of these outcomes, filling the gaps between rigid choices. As Dongho Kim et al. explain in Point-Based Value Iteration for Constrained POMDPs, stochastic action selection allows agents to reach the exact boundary of a cost constraint, maximizing utility by fully utilizing their allowed budget rather than settling for an overly conservative deterministic alternative.
Hedging Against Uncertainty and Non-Linear Utilities
The necessity of randomization extends beyond simple resource budgets; it is also a vital defense mechanism against environmental uncertainty and complex human preferences.
When an agent must balance risk and reward simultaneously, Shie Mannor et al. show in Mean-Variance Optimization in Markov Decision Processes that policy randomization is required to achieve optimal mean-variance trade-offs. Similarly, when operating under model uncertainty, Mohammad Ghavamzadeh et al. demonstrate in Safe Policy Improvement by Minimizing Robust Baseline Regret that searching the space of randomized policies is necessary to hedge against multiple possible transition models. By distributing probability across actions, the agent balances potential gains against the risk of underperforming a baseline across a set of possible environments.
A parallel requirement emerges when optimizing for non-transitive preferences or binary comparisons between distributions (where strategy A beats B, B beats C, but C beats A). In Solving MDPs with Skew Symmetric Bilinear Utility Functions, Hugo Gilbert et al. argue that finding an optimal policy under these conditions is equivalent to finding a Nash Equilibrium in a symmetric zero-sum game. Just as in Rock-Paper-Scissors, any deterministic strategy is easily exploitable; mixed (randomized) strategies are the only way to achieve stability and optimality.
Why Traditional RL Fails under Constraints
Because optimal constrained policies are inherently stochastic, traditional reinforcement learning paradigms face severe structural mismatches. Standard algorithms rely on greedy maximization (such as taking the argmax over action values), which naturally pushes policies toward determinism.
As Ted Moskovitz et al. point out in ReLOAD: Reinforcement Learning with Optimistic Ascent-Descent for Last-Iterate Convergence in Constrained MDPs, simply collapsing constraints into a single scalarized reward function with fixed weights fails. Because standard scalarized objectives typically yield deterministic optimal policies, simple scalarization cannot capture the necessary behavior for complex constraint satisfaction, often causing the policy to oscillate wildly.
This structural mismatch also breaks standard Inverse Reinforcement Learning (IRL). In Learning Safety Constraints from Demonstrations with Unknown Rewards, David Lindner et al. show that traditional IRL frameworks assume the demonstrator follows a deterministic optimal policy. When applied to constrained environments where experts randomize to maintain safety, traditional IRL can misinterpret this stochasticity, inadvertently producing unsafe, deterministic behaviors.
To successfully learn in these environments, algorithms must naturally accommodate probabilistic convergence. For instance, Honghao Wei et al. demonstrate in A Provably-Efficient Model-Free Algorithm for Infinite-Horizon Average-Reward Constrained Markov Decision Processes that on-policy update rules are more effective than traditional max-seeking Q-learning because they allow the agent to naturally represent and converge to stochastic optimal policies.
The Surprising Simplicity of Optimal Randomization
While the mathematical justification for stochastic policies is complex, the actual structure of these optimal policies is surprisingly elegant. An agent does not need to maintain a highly complex, continuous probability distribution over every possible action in every single state.
For a CMDP with a single budget constraint, Haoxian Chen et al. leverage a unique theoretical property in Constrained Reinforcement Learning via Policy Splitting: the optimal policy is actually completely deterministic everywhere except for a single state. In that specific state, the policy splits its actions, mixing between two neighboring deterministic strategies to satisfy the budget exactly.
Expanding on this binary choice mechanism, Xun Shen et al. introduce the concept of a "flipping-based policy" in Flipping-based Policy for Chance-Constrained Markov Decision Processes. The authors prove that optimal solutions for chance-constrained problems can be represented as a stochastic choice between exactly two actions at each state—interpolating between a conservative, safe action and a high-reward, risky action.
This threshold-mixing behavior is mirrored in practical engineering applications. For example, in wireless network scheduling under power constraints, Wenhao Zhan et al. show in Delay Optimal Cross-Layer Scheduling Over Markov Channels with Power Constraint that the optimal control strategy is a randomized mixture of two deterministic threshold policies, allowing the system to hit an exact average power consumption target.
The Predictability Trade-off
Ultimately, the shift from deterministic to randomized policies represents a fundamental trade-off in safe autonomy. While stochasticity provides the mathematical flexibility needed to maximize utility under strict constraints, it introduces predictability challenges.
As Krishnendu Chatterjee notes in Expectation Optimization with Probabilistic Guarantees in POMDPs with Discounted-Sum Objectives, restricting agents to deterministic actions in risk-sensitive scenarios can lead to substantial performance losses. Yet, as Conor F. Hayes et al. point out in A practical guide to multi-objective reinforcement learning and planning, randomized strategies are often unacceptable in high-stakes domains like medicine or law, where stakeholders demand deterministic, explainable decisions.
Understanding why randomization works allows researchers to either embrace probabilistic mixing for maximum efficiency or explicitly quantify the performance cost required to keep an agent's behavior strictly deterministic.
Key Foundational Work
Stationary Deterministic Policies for Constrained MDPs with Multiple Rewards, Costs, and Discount Factors (2005) — contributed 3 concept elements to this direction.