# In a finite unichain average-reward MDP, how does optimal bias vector depend on stage reward

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!!!

• Where does $\kappa$ appear in the subsequent formula? – jbowman Sep 14 '18 at 3:46
• 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)|$$ – Yingying Li Sep 21 '18 at 21:24