I'm currently taking an Intro to AI course, and we've learned about MDP's and specifically about policy iteration. When we talked about the convergence of the policy iteration, it was mentioned that if the error of the solution in the i'th iteration constitute $$ ||U_i - U|| < \epsilon $$ than the adequate policy holds $$ ||U^{\pi_i} - U|| < \frac{2\epsilon\gamma}{1-\gamma} $$ where $$ U^{\pi_i} $$ is the expectation of the utility of the chosen policy in the i'th iteration. I wanted to read a formal proof, but couldn't find anything online, perhaps someone here can refer me to it?

Thank you very much in advance.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.