6
$\begingroup$

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)

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ 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. $\endgroup$
    – mikkola
    Jul 20, 2021 at 10:38
  • $\begingroup$ @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). $\endgroup$
    – nbro
    Dec 20, 2021 at 14:52

0

Reset to default

You must log in to answer this question.