A New Finite-Horizon Dynamic Programming Analysis of Nonanticipative Rate-Distortion Function for Markov Sources

This paper addresses the computation of a non-asymptotic lower bound, given by the nonanticipative rate-distortion function (NRDF), for the discrete-time zero-delay variable-rate lossy compression of discrete Markov sources under per-stage single-letter distortion constraints. We first derive a new information structure for the NRDF and new convexity results that allow reformulating the problem as an unconstrained partially observable finite-horizon stochastic dynamic program (DP) using Lagrange duality theorem subject to a belief state that summarizes past information and evolves in a continuous space. Rather than directly approximating the DP, we derive implicit optimal conditions via the Karush-Kuhn-Tucker (KKT) conditions and propose a novel alternating minimization (AM) scheme to approximate both the control policy and cost-to-go function through backward recursions with provable convergence guarantees. We evaluate the control policies and cost-to-go functions per-stage using an online forward algorithm that executes for any finite horizon. Our methodology yields a near-optimal approximation of the NRDF as the belief state space becomes sufficiently large. Simulation results using time-varying binary Markov sources validate the effectiveness of our approach.