A First-Order Approach to Accelerated Value Iteration

Markov decision processes (MDPs) are used to model stochastic systems in many applications, but computing good policies becomes hard when the effective horizon become very large. In “A First-Order Approach to Accelerated Value Iteration,” Goyal and Grand-Clément present a connection between value iteration (VI) algorithms and gradient descent methods from convex optimization and use acceleration and momentum to design faster algorithms, with convergence guarantees for the computation of the value function of a fixed policy for reversible MDP instances. The authors provide a lower bound on the convergence properties of any first-order algorithm for solving MDPs, where no algorithm can converge faster than VI. Finally, the authors introduce safe accelerated value iteration (S-AVI), which alternates between accelerated updates and value iteration updates. The algorithm S-AVI is worst-case optimal and retains the theoretical convergence properties of VI while exhibiting strong empirical performances and providing significant speedups when compared with classical approaches for a large test bed of MDP instances.