When is a stochastic policy strictly better than any deterministic policy?

## What the two policy types are A policy `pi(a|s)` assigns probabilities to actions in each state. It is **deterministic** when one action gets probability 1 — often written `pi(s) = a` — and **stochastic** otherwise. Note that a stochastic policy is not the same thing as a stochastic environment: transitions can be random while the policy is a fixed rule, and vice versa. ## The theorem that makes this question interesting For a finite Markov decision process with known, stationary dynamics and full observation of the state, there exists an optimal policy that is deterministic. The reason is visible in the optimality equation: `V*(s) = max over a of E[r + g*V*(s')|s,a]`. A maximum over a finite set is attained by some single action, so committing to that action loses nothing. Randomising over several actions can tie the optimum — mixing only among maximisers is also optimal — but it can never strictly beat it. So the honest answer to "is stochastic better?" starts with **no, not in the textbook setting**, and the interview value lies in naming precisely which assumption has to fail. ## Case 1: an adversary can best-respond Suppose you bid repeatedly in a sealed-bid auction against one rival who can observe your past bids. Model this as a single-agent MDP and you get a deterministic optimal bid — but the rival is not part of the environment's fixed dynamics; they adapt. Once your bid is predictable, the rival can position their own bid to win cheaply whenever it suits them and concede only when the item is not worth it, so your realised surplus collapses. A randomised bid schedule leaves the rival uncertain about the threshold they are bidding against, and their best response degrades. This is a game, not an MDP: the "environment" contains an optimiser working against you, and in general equilibria of such games require mixed strategies. Any competitive pricing, bidding, or security setting where the counterparty studies your behaviour has this shape. ## Case 2: state aliasing under partial observation The MDP theorem assumes the agent conditions on the true state. If the agent only sees an observation, two distinct underlying states can look identical. A deterministic policy is a function of what it can see, so it must emit the same action in both — and if the right action differs between them, it is guaranteed wrong in one, potentially forever (walking into the same wall, taking the same doomed action every visit). A policy that randomises over the two candidate actions is wrong only some of the time and, in aliased navigation-style problems, can achieve a strictly higher expected return than the best deterministic map from observation to action. The deep fix is a better state representation — adding memory or history so the states stop aliasing — but randomising is the direct mitigation when you cannot. ## Case 3: restricted or smooth policy classes If the policy is constrained — to a parametric family, to a smooth function for optimisation reasons, or by a constraint like "no more than 30% of traffic to one variant" — the deterministic optimum may not be inside the feasible set. Then the best available policy is stochastic simply because determinism is unavailable. Constrained MDPs, where you maximise return subject to a cost budget, are a clean example: the optimal solution there is often a randomisation between two deterministic policies, because that is the only way to hit the budget exactly. ## What this is not It is not an argument that randomness helps learning. During learning an agent must try actions its current estimates do not favour, and that is a separate topic with its own machinery. Nor is a stochastic policy a "noisy" version of a deterministic one — the mixing probabilities are part of the policy and are chosen, not injected as noise after the fact. And a stochastic policy still has a perfectly ordinary value function: `V_pi(s) = sum over a of pi(a|s) * Q_pi(s,a)`, the average over the actions it might take. ## How to answer in an interview Lead with the theorem — deterministic suffices for finite, fully observed MDPs — then name the escapes: adversarial or multi-agent settings, partial observability with aliasing, and restricted or constrained policy classes. Candidates who say "stochastic is always better because it explores" have skipped the theorem, and candidates who say "deterministic is always better because it is decisive" have missed the escapes.