A note on optimization formulations of Markov decision processes (Q2129661)

The paper summarizes the primal, primal-dual and dual problems for discounted standard Markov decision processes, discounted regularized Markov decision processes, undiscounted standard Markov decision processes and undiscounted regularized Markov decision processes. Moreover, the paper shows the equivalence between the dual problem and policy gradient as well as the equivalence between the primal problem and Bellman equation for the above four Markov decision processes. These optimization formulations are helpful for the theoretical study of Markov decision processes algorithms.