Consider a finite unichain MDP with stage reward $r$, state space $S=\{1, \dots, n\}$, action space A, and transition probability $p$. The Bellman equation is $$ h(i) + g= \max_{a \in A} ( r(i,a ) + \sum_{j\in S} p_{ij}(a) h(j)$$ Under the finite unichain assumption, and requiring $h(n)=0$, there exists a unique solution $(g_r, h_r)$.

Now, under the same transition probability, there is another reward function $v$. We can solve the Bellman equation plus $h(n)=0$ under stage reward $v$, and find a unique solution $(g_v, h_v)$.

My question is, does the following claim hold?

Claim: there exists a constant $\kappa$ that does not depend on $r$ or $v$, but may depend on transition probabilities and $n$, such that $$ \max_{i\in S} | h_r(i)-h_v(i)| \leq \kappa \max_{i\in S, a\in A} | r(i,a)- v(i,a)|$$.

I can prove the claim when the MDP is recurrent, or when there is a special state that is always recurrent under all policies. But I fail to prove it for general unichain MDP.

In fact, I highly doubt if this claim is correct in general unichain models, but am having a hard time constructing a counterexample.

It would be great if someone has some ideas on the proof, or the construction of a counterexample.

Thank you very much!!!

  • $\begingroup$ Where does $\kappa$ appear in the subsequent formula? $\endgroup$ – jbowman Sep 14 '18 at 3:46
  • $\begingroup$ Sorry it is a typo. It should be $$ \max_i | h_r(i)-h_v(i)|<= \kappa \max_{i,a} | r(i,a)-v(i,a)|$$ $\endgroup$ – Yingying Li Sep 21 '18 at 21:24

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.