From Optimization to Control: Quasi Policy Iteration

Recent control algorithms for Markov decision processes (MDPs) have been designed using an implicit analogy with well-established optimization algorithms. In this paper, we make this analogy explicit across four problem classes with a unified solution characterization. This novel framework, in turn, allows for a systematic transformation of algorithms from one domain to the other. In particular, we identify equivalent optimization and control algorithms that have already been pointed out in the existing literature, but mostly in a scattered way. With this unifying framework in mind, we then exploit two linear structural constraints specific to MDPs for approximating the Hessian in a second-order-type algorithm from optimization, namely, Anderson mixing. This leads to a novel first-order control algorithm that modifies the standard value iteration (VI) algorithm by incorporating two new directions and adaptive step sizes. While the proposed algorithm, coined as quasi-policy iteration (QPI), has the same computational complexity as VI, it interestingly exhibits an empirical convergence behavior similar to policy iteration with a very low sensitivity to the discount factor. We further extend QPI to the model-free setting (i.e., reinforcement learning), to which we refer as the quasi-policy learning (QPL), and guarantee its convergence by a novel safeguarding technique. QPL also shares similar features with QPI in the sense that despite the first-order per-iteration complexity, its convergent behavior and sensitivity to discount factor are comparable with the second-order algorithms such as Zap Q-learning.

Article

Download

View PDF