Q-learning and enhanced policy iteration in discounted dynamic programming

By Dimitri P. Bertsekas, Huizhen Yu. 2010

70 citations recorded by the source corpus.

We consider the classical finite-state discounted Markovian decision problem, and we introduce a new policy iteration-like algorithm for finding the optimal Q-factors. Instead of policy evaluation by solving a linear system of equations, our algorithm involves (possibly inexact) solution of an optimal stopping problem. This problem can be solved with simple Q-learning iterations, in the case where a lookup table representation is used; it can also be solved with the Q-learning algorithm of Tsitsiklis and Van Roy [TsV99], in the case where feature-based Q-factor approximations are used. In exact/lookup table representation form, our algorithm admits asynchronous and stochastic iterative implementations, in the spirit of asynchronous/modified policy iteration, with lower overhead advantages over existing Q-learning schemes. Furthermore, for large-scale problems, where linear basis function approximations and simulation-based temporal difference implementations are used, our algorithm resolves effectively the inherent difficulties of existing schemes due to inadequate exploration.

Subfields: Artificial Intelligence, Computer Networks and Communications, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Management Science and Operations Research

Citations in the corpus

A General Family of Robust Stochastic Operators for Reinforcement Learning (2018, methodology): “The research literature contains a wide variety of studies of operator alternatives to the Bellman operator, including the -greedy method [22], speedy Q-learning [3], policy iteration-like Q-learning [7], and the Boltzmann softmax operator and its variants [2].”
Increasing the Action Gap: New Operators for Reinforcement Learning (2015, background): “While numerous alternatives to the Bellman operator have been put forward (e.g. recently Azar et al. 2011; Bertsekas and Yu 2012), we believe our work to be the ﬁrst to propose such a major departure from the canonical ﬁxed-point condition required from an optimality-preserving operator.”
Approximate policy iteration: a survey and some new methods (2011, methodology): “In this alternative, which stems from the work of Bertsekas and Yu [75], we introduce the bounds directly into the approximation architecture and use a corresponding nonlinear iterative policy evaluation algorithm.”
Tight Performance Bounds for Approximate Modified Policy Iteration with Non-Stationary Policies (2013, methodology): “In this last section, we describe an empirical illustration of our new variation of MPI on the dynamic location problem from Bertsekas and Yu (2012).”