2
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Phil
    Jan 9, 2021 at 19:56
  • $\begingroup$ 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? $\endgroup$
    – nbro
    Jan 9, 2021 at 20:01
  • $\begingroup$ 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! $\endgroup$
    – Phil
    Jan 9, 2021 at 20:04

0

Reset to default

You must log in to answer this question.