In a fully observable Markov Decision Process (MDP), a fundamental theorem of reinforcement learning holds true: there is always an optimal policy that is entirely deterministic. If an agent knows its exact state in the environment, it can simply choose the single best action for that state.
However, this guarantee completely collapses in Partially Observable Markov Decision Processes (POMDPs), where agents operate with incomplete information or limited memory. In these settings, optimal behavior frequently demands randomness. Rather than being a symptom of sub-optimal exploration, probabilistic action selection is a mathematical necessity for navigating uncertainty.
The Dilemma of Perceptual Aliasing
To understand why randomness is required, we must first look at how partial observability distorts an agent's view of the world. As Akira Hayashi et al. point out in Viewing Classifier Systems as Model Free Learning in POMDPs, memoryless agents operating in these environments frequently suffer from perceptual aliasing—a phenomenon where physically distinct environmental states yield identical sensor readings or observations.
State A (Hallway 1) ----> Observation: "White Wall" ----> Action?
State B (Hallway 2) ----> Observation: "White Wall" ----> Action?
If an agent is memoryless and its policy is deterministic, it is forced to take the exact same action every time it encounters a specific observation. This rigidity creates a catastrophic vulnerability: deterministic cycles.
Imagine an agent navigating a maze where State A and State B look identical. To escape the maze from State A, the agent needs to go left; to escape from State B, it needs to go right. If a deterministic agent decides to go left when facing this ambiguous observation, it will successfully exit State A. However, if it ever lands in State B, it will also go left—which might loop it right back into State B. Because its policy is fixed, the agent becomes trapped in an infinite, sub-optimal loop.
Stochasticity as a Substitute for Memory
To break these cycles without adding complex internal memory, the agent must randomize its behavior. In Experimental Results on Learning Stochastic Memoryless Policies for Partially Observable Markov Decision Processes, John K. Williams et al. demonstrate that stochasticity serves as a functional substitute for memory. By assigning non-zero probabilities to multiple actions in aliased states (e.g., 50% left, 50% right), the agent ensures that it will eventually select the correct action to transition out of the ambiguous region, effectively breaking the deterministic loop.
This mechanism works because a stochastic policy allows the agent to hedge its bets. As explained by Tommi Jaakkola et al. in Reinforcement Learning Algorithm for Partially Observable Markov Decision Problems, choosing actions probabilistically allows the agent to effectively average its performance across the various hidden states that might correspond to a single observation.
The necessity of this randomness is deeply structural. From a geometric perspective, Johannes Müller et al. map the optimization landscape of these environments in The Geometry of Memoryless Stochastic Policy Optimization in Infinite-Horizon POMDPs, proving that finding optimal memoryless strategies inherently requires navigating continuous probability distributions rather than discrete, deterministic choices.
This requirement is not exclusive to entirely memoryless agents. It applies to any system where the agent's internal memory is too constrained to fully reconstruct the environment. For instance, Christopher Amato et al. show in Solving POMDPs Using Quadratically Constrained Linear Programs that bounded-memory controllers achieve significantly higher performance when action and transition probabilities are treated as continuous, stochastic variables. Similarly, Amit Sinha et al. demonstrate in Agent-state based policies in POMDPs: Beyond belief-state MDPs that randomized actions naturally compensate for the information gaps caused by finite memory limits.
Why Policy Search Outperforms Value-Based Methods
Recognizing that optimal policies are stochastic fundamentally changes how we must train reinforcement learning agents. Traditional value-based methods, such as Q-learning, are designed to find the value of states or state-action pairs and select actions greedily. This paradigm inherently biases the agent toward deterministic behavior and struggles when identical observations have conflicting underlying values.
Direct policy optimization solves this by bypassing value functions entirely. In the foundational paper Policy Gradient Methods for Reinforcement Learning with Function Approximation, Richard S. Sutton et al. establish that direct policy parameterization allows gradient-based methods to smoothly represent, explore, and refine continuous action distributions.
Value-Based (Q-Learning): Observation ----> Max Q(obs, action) ----> Deterministic Choice (Hard)
Policy-Based (Gradients): Observation ----> Softmax(θ) ----> Probabilistic Distribution (Smooth)
This smooth representation is highly robust against the instabilities that plague value-based methods in ambiguous environments. As Leonid Peshkin et al. show in Learning to Cooperate via Policy Search, mapping incomplete observations directly to action distributions allows independent agents in cooperative games to successfully navigate partial views of the world.
Despite these advantages, optimizing stochastic policies remains a steep computational challenge. Kamyar Azizzadenesheli et al. formalize this in Open Problem: Approximate Planning of POMDPs in the class of Memoryless Policies., noting that while deterministic policies are easier to compute, finding the optimal stochastic mapping for a POMDP is an unsolved planning bottleneck. This complexity also disrupts auxiliary training methods; for example, Baicen Xiao et al. point out in Potential-Based Advice for Stochastic Policy Learning that traditional reward shaping frameworks often fail in these domains because they are built on the flawed assumption that the target optimal policy is deterministic.
Hedging Against Epistemic and Intent Uncertainty
While the foundational motivation for stochastic policies comes from spatial or state ambiguity in POMDPs, the exact same mathematical mechanism applies to other forms of uncertainty, such as data limitations or agent interactions.
In offline reinforcement learning, where an agent must learn exclusively from a fixed dataset, it faces severe epistemic uncertainty—it does not know what lies in unobserved regions of the state space. In The Importance of Pessimism in Fixed-Dataset Policy Optimization, Jacob Buckman et al. demonstrate that a pessimistic optimal policy should be stochastic. By distributing probability across multiple plausible actions rather than committing to a single action that might have a hallucinated high value due to statistical noise, the agent safely maximizes the lower bound of its expected returns.
Deterministic Choice: Commit 100% to Action A ----> High risk if Action A's value is over-estimated noise.
Stochastic Choice: Distribute prob. across A & B -> Hedges risk under high epistemic uncertainty.
A parallel problem arises in interactive environments, such as autonomous driving, where an agent faces intent uncertainty regarding other actors. In Risk-Constrained Interactive Safety under Behavior Uncertainty for Autonomous Driving, Julian Bernhard et al. show that generating a stochastic policy—represented as a probability distribution over possible maneuvers—allows a vehicle to maintain safety margins without becoming paralyzed. By outputting a distribution of actions, the system preserves the flexibility required to react to multiple potential choices from surrounding drivers, hedging its bets in the face of an unpredictable future.
Key Foundational Work
Viewing Classifier Systems as Model Free Learning in POMDPs (1998) — contributed 3 concept elements to this direction.
Reinforcement Learning Algorithm for Partially Observable Markov Decision Problems (1994) — contributed 2 concept elements to this direction.
Experimental Results on Learning Stochastic Memoryless Policies for Partially Observable Markov Decision Processes (1998) — contributed 2 concept elements to this direction.