Counter Examples for Compact Action Markov Decision Chains With Average Reward Criteria

In this note we present two examples of compact-action finite-state Markov decision chains in which a policy improvement procedure yields wrong or limited results. in the first example, which exhibits a multichain structure, there is no convergence of the average rewards of the successive policies to the maximal value. in the second example, which has a unichain structure, the lack of uniqueness of maximizing policies in each step of the algorithm means that there is no convergence of either bias vectors or maximizing policies. Accordingly, no solution to the average optimality equations can be obtained.