# Does there necessarily exist "dominated actions" in a MDP?

In a Markov Decision Process, is it possible that there exists no "dominated action"?

I define a dominated action the following way: we say that $$(s,a)$$ is a dominated action, if $$\forall \pi, a \notin \text{argmax}\ q^{\pi}(s,.)$$, where $$\pi$$ are policies.

For now, I am only considering the cases where all q-values are distinct and therefore the max is always unique. I also only consider the case of deterministic policies (mappings from state space to action space).

We can consider MDP in which each state has at least 2 actions available to get rid of the corner cases where there is only one possible policy.

I am struggling to find a counter-example or a proof.

• I say that an action is "dominated" if, for all policies, it is not the argmax of the q-value of that policy. An action would be "dominated" if it is never the best action you can perform, regardless of the policy considered.
– Phil
Jan 9 '21 at 19:56
• Ok, now I think I better understand your question. So, an action can be the argmax for some policy but not be the argmax for another policy. In this second case, it would be a dominated action for that second policy, but not for all policies. But you define a dominated action one that is not the argmax but for all policies. Is this interpretation correct?
– nbro
Jan 9 '21 at 20:01
• Yes, i define "domination" to be for all policies. A dominated action would therefore be a very bad choice, which will never occur as an improvement in an algorithm such as Policy Iteration!
– Phil
Jan 9 '21 at 20:04