A Stochastic Control Viewpoint on 'Posterior Matching'-style Feedback Communication Schemes

This paper re-visits Shayevitz & Feder's recent 'Posterior Matching Scheme', a deterministic, recursive, capacity-achieving feedback encoding scheme for memoryless channels. We here consider the feedback encoder design problem from a stochastic control perspective. The state of the system is the posterior distribution of the message given current outputs of the channel. The per-trial reward is the average 'reduction in distance' of the posterior to the target unit step function. We show that the converse to the channel coding theorem with feedback upper bounds the optimal reward, and that the posterior matching scheme is an optimal policy. We illustrate that this 'reduction in distance' symbolism leads to the existence of a Lyapunov function on the Markov chain under this optimal policy, which leads to demonstration of achievability for all rates less than capacity.