Must a dominating policy be strictly better everywhere?

Not under the non-strict definition used here. Ties are allowed; strict dominance is a different convention that must be specified.

Can several policies be dominating?

Yes. Different policies can achieve the same optimal value function.

Does winning on average establish dominance?

No. A weighted average can conceal states where the policy is worse, and states excluded from the starting distribution contribute nothing to that average.

AI Glossary / Reinforcement learning and robotics / Intermediate

Dominating policy

Definition

A dominating policy, in the Markov decision-process sense used here, is a policy whose expected return is at least as high as that of every alternative policy from every state under the same objective and model. It is therefore optimal across starting states, rather than merely best for one chosen starting distribution.

What it means

A policy tells an agent how to act. Its value at a state summarizes the expected future return obtained by following it from that state. To call one policy dominating in this sense is to compare the entire collection of state values against all alternatives.

The word can also describe a pairwise comparison: policy A dominates policy B if A is no worse at every state. That does not establish that A dominates all policies. Terminology may distinguish weak and strict dominance, so the comparison and treatment of ties should always be stated.

How it works

Fix the reward definition, discounting or horizon, transition model and admissible policy class. Evaluate each policy's expected return from the states under consideration. A globally dominating policy has a value at least as large as every competitor's value at every state.

Standard finite-state, finite-action discounted Markov decision problems with bounded rewards admit an optimal deterministic stationary policy. More general problems need their own existence assumptions. A policy that maximizes average return under one initial-state distribution need not justify an unrestricted statewise dominance claim, especially when some states receive zero probability in that evaluation.

Three practical examples

1. A small planning model compares complete policies from every possible initial machine condition. A policy that is never worse across those states dominates another in the pairwise sense.

2. A simulator reports a better overall average for a new policy, but separate starting-state results reveal a decline in one condition. Reviewers reject a claim of statewise dominance.

3. A teaching example finds two different policies with equal optimal values. Both can satisfy the non-strict definition even though their selected actions differ.

Think of it this way

Think of comparing travel plans from several departure points. A plan that is better on average can still be worse from a particular starting point. A dominating plan, under the stated score, is at least as good from every point being compared. This is a statement about the whole comparison, not a prediction that every individual journey will turn out better.

Worked example

Consider a one-step decision problem with three states, each ending immediately after the chosen action. The deterministic reward table is: at state 1, action A gives 5 and B gives 4; at state 2, A gives 2 and B gives 4; at state 3, A gives 3 and B gives 3.

Policy P always chooses A, giving values (5, 2, 3). Policy Q always chooses B, giving (4, 4, 3). Neither dominates the other: P is better at state 1, while Q is better at state 2.

Policy R chooses A at state 1, B at state 2, and either action at state 3. Its values are (5, 4, 3). R dominates both P and Q. Because it chooses a maximum-reward action at every state in this one-step problem, it also dominates every policy in the specified action set, including randomized mixtures.

With equal starting-state weights, P averages 10/3 and Q averages 11/3. Q's higher average still did not make Q dominate P. This example uses known deterministic rewards, so no statistical estimation is involved.

Illustrative case study

Fictional case: Birch Planning compares two simulated warehouse policies. A new policy improves average throughput across the team's usual starting conditions, and a draft report calls it dominating. A reviewer checks less common initial conditions and finds that the old policy performs better in one of them.

The team revises the claim to describe the actual weighted-average comparison and reports the trade-off. It also states the reward and constraints used in the simulator. This invented case illustrates precise reporting; it does not establish dominance, improvement or operational suitability for any real warehouse.

Common misconceptions and mistakes

Dominance concerns expected return, not a guarantee that every random outcome is better. Even a policy with a higher expectation can perform worse on a particular realized trajectory.

Do not confuse dominating one competitor with dominating all admissible policies. Nor does optimality under one reward establish superiority under every business objective. If the reward ignores energy use or service quality, its dominance relation ignores those aspects too. Finally, empirical estimates and incomplete test coverage do not automatically prove exact statewise inequalities, particularly in large or continuous state spaces.

Business use

The concept helps clarify strong claims about decision policies. It asks whether an improvement is uniform across relevant starting conditions or depends on how results are averaged. That distinction matters when a policy serves a mixture of common and unusual operating situations.

In practice, report the comparison scope, uncertainty and objective. Use state groups or scenario families when exhaustive evaluation is impossible, but describe them as tested evidence rather than universal proof. If objectives conflict, present the trade-offs explicitly instead of using dominating as a vague synonym for generally better.

Check your understanding

Policy Q has a higher equal-weight average than P in the worked example. Why does Q fail to dominate P?

Answer: At state 1, Q gives 4 while P gives 5. Dominance requires a no-worse value at every state, so a single counterexample defeats that pairwise claim despite the higher average.

Related terms

Optimal policy
Markov decision process
Policy evaluation
Multi-objective optimization
value function
expected return
statewise comparison
weak dominance
policy class

Learn next

Learn how policy values depend on the starting state and objective. Compare small value tables before discussing dominance. Then distinguish exact model-based proofs from empirical evidence and examine whether the assumptions guaranteeing an optimal policy apply to the problem being studied.

Optimal policy

Sources

Poole and Mackworth, Artificial Intelligence: Foundations of Computational Agents, Decision Processes, statewise policy optimality: https://www.artint.info/3e/html/ArtInt3e.Ch12.S5.html

Sutton and Barto, Reinforcement Learning: An Introduction, optimal policies and value functions: https://www.incompleteideas.net/book/bookdraft2018mar21.pdf

The reward table and Birch Planning case are original hypothetical illustrations. The entry explicitly uses statewise expected-return dominance.

Previous: Dominant strategy equilibrium Next: Donor (imputation)