Optimality of Walrand-Varaiya Type Policies and Approximation Results for Zero-Delay Coding of Markov Sources

Abstract

Optimal zero-delay coding of a finite state Markov source through quantization is considered. Building on previous literature, the existence and structure of optimal policies are studied using a stochastic control problem formulation. In the literature, the optimality of deterministic Markov coding policies (or Walrand-Varaiya type policies) for infinite horizon problems has been established. This work expands on this result for systems with finite source alphabets, proving the optimality of de- terministic and stationary Markov coding policies for the infinite horizon setup. In addition, the ε-optimality of finite memory quantizers is established and the depen- dence between the memory length and ε is quantified. An algorithm to find the optimal policy for the finite time horizon problem is presented. Numerical results produced using this algorithm are shown.