Answers.Body: <p>I think the statement above is incorrect, it should be <span class="math-container">$\forall \; \pi \in \Pi $</span> and not <span class="math-container">$\forall \; s \in S $</span>. Then the proof is trivial and we can show this by contradiction. Assume <span class="math-container">$V_\pi(s) &lt; V_\hat\pi(s),\; \forall s \in S$</span> is always the case, i.e. <span class="math-container">$\nexists \pi \;\forall \;\hat\pi, s.t. V_\pi(s) \geq V_\hat\pi(s)$</span>. This statement is wrong beacause for <span class="math-container">$\pi = \hat\pi$</span> the equality condition holds.
  For the <span class="math-container">$&gt;$</span> case, we can use the definition of <span class="math-container">$\pi^*$</span>, optimal policy.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-01-02T11:15:53.143Z
Answers.LastActivityDate: 2024-01-02T11:23:46.603Z
Answers.LastEditDate: 2024-01-02T11:23:46.603Z
Answers.UserDisplayName: kaiser
Body: <p>I think that it is common knowledge that for any infinite horizon discounted MDP <span class="math-container">$(S, A, P, r, \gamma)$</span>, there always exists a dominating policy <span class="math-container">$\pi$</span>, i.e. a policy <span class="math-container">$\pi$</span> such that for all policies <span class="math-container">$\pi'$</span>: <span class="math-container">$$V_\pi (s) \geq V_{\pi'}(s) \quad \text{for all } s\in S .$$</span></p>
  <p>However, I could not find a proof of this result anywhere. Given that this statement is fundamental for dynamic programming (I think), I am interested in a rigorous proof. (I hope that I am not missing anything trivial here)</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-07-20T10:38:37.887Z
Comments.Text: For what it's worth, a proof of this fact may be found in Chapter 6 of the book "Markov decision processes: Discrete stochastic dynamic programming" by Martin Puterman. To reproduce it here would take a quite a bit of effort due to the context required, I'm afraid.
Comments.UserDisplayName: mikkola
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-12-20T14:52:30.563Z
Comments.Text: @mikkola Maybe you can just sketch the idea of the proof, if you are familiar with it. I guess that would be enough for a formal answer (in addition to pointing to that chapter).
Comments.UserDisplayName: nbro
Tags: <reinforcement-learning><markov-decision-process><proofs><policies>
Title: Proof that there always exists a dominating policy in an MDP
UserDisplayName: MMM
ThreadText: # Proof that there always exists a dominating policy in an MDP
  
  (Asked by: username_0 on 2021-07-16)
  
  I think that it is common knowledge that for any infinite horizon discounted MDP $(S, A, P, r, \gamma)$, there always exists a dominating policy $\pi$, i.e. a policy $\pi$ such that for all policies $\pi'$: $$V\_\pi (s) \geq V\_{\pi'}(s) \quad \text{for all } s\in S .$$
  
  However, I could not find a proof of this result anywhere. Given that this statement is fundamental for dynamic programming (I think), I am interested in a rigorous proof. (I hope that I am not missing anything trivial here)
  
  **Tags:** reinforcement-learning, markov-decision-process, proofs, policies
  > **Comments:**
  > **username_1**: For what it's worth, a proof of this fact may be found in Chapter 6 of the book "Markov decision processes: Discrete stochastic dynamic programming" by Martin Puterman. To reproduce it here would take a quite a bit of effort due to the context required, I'm afraid.  
  > **username_2**: @mikkola Maybe you can just sketch the idea of the proof, if you are familiar with it. I guess that would be enough for a formal answer (in addition to pointing to that chapter).  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_3 on 2024-01-02. Score: 0
  
  I think the statement above is incorrect, it should be $\forall \; \pi \in \Pi $ and not $\forall \; s \in S $. Then the proof is trivial and we can show this by contradiction. Assume $V\_\pi(s) < V\_\hat\pi(s),\; \forall s \in S$ is always the case, i.e. $\nexists \pi \;\forall \;\hat\pi, s.t. V\_\pi(s) \geq V\_\hat\pi(s)$. This statement is wrong beacause for $\pi = \hat\pi$ the equality condition holds.
  For the $>$ case, we can use the definition of $\pi^\*$, optimal policy.
  
  
  ---
  
  