  In the classical lossy source coding problem, one encodes long blocks of
source symbols that enables the distortion to approach the ultimate Shannon
limit. Such a block-coding approach introduces large delays, which is
undesirable in many delay-sensitive applications. We consider the zero-delay
case, where the goal is to encode and decode a finite-alphabet Markov source
without any delay. It has been shown that this problem lends itself to
stochastic control techniques, which lead to existence, structural, and general
structural approximation results. However, these techniques so far have
resulted only in computationally prohibitive algorithmic implementations for
code design. To address this problem, we present a reinforcement learning
design algorithm and rigorously prove its asymptotic optimality. In particular,
we show that a quantized Q-learning algorithm can be used to obtain a
near-optimal coding policy for this problem. The proof builds on recent results
on quantized Q-learning for weakly Feller controlled Markov chains whose
application necessitates the development of supporting technical results on
regularity and stability properties, and relating the optimal solutions for
discounted and average cost infinite horizon criteria problems. These
theoretical results are supported by simulations.
