Coupled Successive Approximations for Markov Programs

Each Markov program corresponds to a pair of linear programs. Constructing successive approximations for the primal and dual variables that are respectively decreasing and increasing allows a mutual stopping criterion based on LP duality. This assumes that ordinary successive approximations have determined an optimal or ϵ-optimal policy but not its value function (exactly). The dual variables approximated are those corresponding to the policy used. In this sense, the dual-variable approximation scheme is piggybacked onto the primal-variable approximation scheme. In another sense, the two schemes are coupled by the reciprocal termination criterion that determines when to stop refining the estimates of both the primal and dual variables.