  We study the problem of zero-delay coding for the transmission a Markov
source over a noisy channel with feedback and present a rigorous reinforcement
theoretic solution which is guaranteed to achieve near-optimality. To this end,
we formulate the problem as a Markov decision process (MDP) where the state is
a probability-measure valued predictor/belief and the actions are quantizer
maps. This MDP formulation has been used to show the optimality of certain
classes of encoder policies in prior work. Despite such an analytical approach
in determining optimal policies, their computation is prohibitively complex due
to the uncountable nature of the constructed state space and the lack of
minorization or strong ergodicity results which are commonly assumed for
average cost optimal stochastic control. These challenges invite rigorous
reinforcement learning methods, which entail several open questions addressed
in our paper. We present two complementary approaches for this problem. In the
first approach, we approximate the set of all beliefs by a finite set and use
nearest-neighbor quantization to obtain a finite state MDP, whose optimal
policies become near-optimal for the original MDP as the quantization becomes
arbitrarily fine. In the second approach, a sliding finite window of channel
outputs and quantizers together with a prior belief state serve as the state of
the MDP. We then approximate this state by marginalizing over all possible
beliefs, so that our coding policies only use the finite window term to encode
the source. Under an appropriate notion of predictor stability, we show that
such policies are near-optimal for the zero-delay coding problem as the window
length increases. We give sufficient conditions for predictor stability to
hold. Finally, we propose a reinforcement learning algorithm to compute
near-optimal policies.
