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.