Body: <p>In a Markov Decision Process, is it possible that there exists no &quot;dominated action&quot;?</p>
  <p>I define a dominated action the following way:
  we say that <span class="math-container">$(s,a)$</span> is a dominated action, if <span class="math-container">$\forall \pi, a \notin \text{argmax}\ q^{\pi}(s,.)$</span>, where <span class="math-container">$\pi$</span> are policies.</p>
  <p>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).</p>
  <p>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.</p>
  <p>I am struggling to find a counter-example or a proof.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-01-09T19:56:11.990Z
Comments.Text: 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.
Comments.UserDisplayName: Phil
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-01-09T20:01:15.513Z
Comments.Text: 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?
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-01-09T20:04:10.143Z
Comments.Text: 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!
Comments.UserDisplayName: Phil
Tags: <reinforcement-learning><markov-decision-process><proofs><value-functions><policies>
Title: Does there necessarily exist "dominated actions" in a MDP?
UserDisplayName: Phil
ThreadText: # Does there necessarily exist "dominated actions" in a MDP?
  
  (Asked by: username_0 on 2021-01-09)
  
  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.
  
  **Tags:** reinforcement-learning, markov-decision-process, proofs, value-functions, policies
  > **Comments:**
  > **username_0**: 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.  
  > **username_1**: 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?  
  > **username_0**: 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!  
  
  ---
  
  ## 0 answers
  
  