An online primal-dual method for discounted Markov decision processes
Mengdi Wang, Yichen Chen · 2016
We consider the online solution of discounted Markov decision processes (MDP). We focus on the black-box learning model where transition probabilities and state transition cost are unknown. Instead, a simulator is available to generate random state transitions under given actions. We propose a stochastic primal-dual algorithm for solving the linear formulation of the Bellman equation. The algorithm updates the primal and dual iterates by using sample state transitions and sample costs generated by the simulator. We provide a thresholding procedure that recovers the exact optimal policy from the dual iterates with high probability.