Decentralized Learning in Finite Markov Chains: Revisited

The convergence proof in the paper ldquoDecentralized learning in finite Markov chains,rdquo published in the IEEE Transactions on Automatic Control, vol. AC-31, no. 6, pp. 519-526, 1986, is incomplete. This note first provides a sufficient condition for the existence of a unique optimal policy for infinite-horizon average-cost Markov decision processes (MDPs), making the convergence result established by Wheeler and Narendra preserved with the condition. We then present a novel simulation-based decentralized algorithm, called ldquosampled joint-strategy fictitious play for MDPrdquo for average MDPs based on the recent study by Garcia of a decentralized approach to discrete optimization via fictitious play applied to games with identical payoffs. We establish a stronger almost-sure convergence result than Wheeler and Narendra´s, showing that the sequence of probability distributions over the policy space for a given MDP generated by the algorithm converges to a unique optimal policy with probability one.