Approximate policy iteration: a survey and some new methods

By Dimitri P. Bertsekas. 2011

321 citations recorded by the source corpus.

We consider the classical policy iteration method of dynamic programming (DP), where approximations and simulation are used to deal with the curse of dimensionality. We survey a number of issues: convergence and rate of convergence of approximate policy evaluation methods, singularity and susceptibility to simulation noise of policy evaluation, exploration issues, constrained and enhanced policy iteration, policy oscillation and chattering, and optimistic and distributed policy iteration. Our discussion of policy evaluation is couched in general terms and aims to unify the available methods in the light of recent research developments and to compare the two main policy evaluation approaches: projected equations and temporal differences (TD), and aggregation. In the context of these approaches, we survey two different types of simulation-based algorithms: matrix inversion methods, such as least-squares temporal difference (LSTD), and iterative methods, such as least-squares policy evaluation (LSPE) and TD (λ), and their scaled variants. We discuss a recent method, based on regression and regularization, which rectifies the unreliability of LSTD for nearly singular projected Bellman equations. An iterative version of this method belongs to the LSPE class of methods and provides the connecting link between LSTD and LSPE. Our discussion of policy improvement focuses on the role of policy oscillation and its effect on performance guarantees. We illustrate that policy evaluation when done by the projected equation/TD approach may lead to policy oscillation, but when done by aggregation it does not. This implies better error bounds and more regular performance for aggregation, at the expense of some loss of generality in cost function representation capability. Hard aggregation provides the connecting link between projected equation/TD-based and aggregation-based policy evaluation, and is characterized by favorable error bounds.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Statistical and Nonlinear Physics

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 Computational Theory and Mathematics

In Statistical and Nonlinear Physics

Citations in the corpus

Increasing the Action Gap: New Operators for Reinforcement Learning (2015, background): “Generalizing (5), we deﬁne the consistent Bellman operator T C over Q Z , A : Intuitively (see, e.g., Bertsekas 2011), the D and A mappings induce a new MDP, M (cid”
Policy Error Bounds for Model-Based Reinforcement Learning with Factored Linear Models (2016, background): “Example 3 (State aggregation) State aggregation (Whitt, 1978; Bertsekas, 2011) in MBRL generalizes KBRL.”
Reinforcement Learning under Model Mismatch (2017, methodology): “Convergence for these algorithms even in the non-robust setting are known only for linear architectures, see e.g., [3].”
Adaptive Batch Size for Safe Policy Gradients (2017, unknown): “Inspired by the conservative policy iteration approach [10], recently, new advances have been done in the field of approximate policy iteration algorithms [11, 12], obtaining methods that can learn faster while still giving statistical guarantees of improvement after each policy update [13, 14].”
Q-learning and enhanced policy iteration in discounted dynamic programming (2010, unknown): “, the discussion in Bertsekas [8, 9]).”
Mastering the game of Go without human knowledge (2017, background): “…superhuman performance, winning 100–0 against the previously published, champion-defeating AlphaGo. repeatedly in a policy iteration procedure 22,23 : the neural network’s parameters are updated to make the move probabilities and value ( p , v ) = f θ ( s ) more closely match the improved…”
Bayes-Adaptive Simulation-based Search with Value Function Approximation (2014, background): “The same principle can also be applied to MC control with function approximation with convergence results under appropriate conditions [2].”
Stabilization of Stochastic Iterative Methods for Singular and Nearly Singular Linear Systems (2014, methodology): “Also, the sample sequence can be generated through state transitions of an irreducible Markov chain as, for example, in temporal difference methods for cost evaluation problems in ADP (see Bradtke and Barto [12], Boyan [11], Nedić and Bertsekas [40], Bertsekas [4]) or for general projected equations”
Learning from Limited Demonstrations (2013, methodology): “Our algorithm is couched in the framework of API [7].”
Empirical Dynamic Programming (2013, background): “A survey on approximate policy iteration is provided in [7].”
Iterative Value-Aware Model Learning (2018, background): “…et al., 2009, Farahmand and Precup, 2012, Mnih et al., 2015, Tosatto et al., 2017, Farahmand et al., 2017b] or (Approximate) Policy Iteration (API) algorithms [Lagoudakis and Parr, 2003, Antos et al., 2008, Bertsekas, 2011, Lazaric et al., 2012, Scherrer et al., 2012, Farahmand et al., 2016b].”
Provably Good Batch Reinforcement Learning Without Great Exploration (2020, result): “This is similarly tight as prior analysis assuming concentrability [19, 4].”
Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulator (2018, background): “Optimal control theory (Anderson & Moore, 1990; Evans, 2005; Bertsekas, 2011; 2017) shows that the optimal control input can be written as a linear function in the state, Planning with a known model.”
On the Use of Non-Stationary Policies for Stationary Infinite-Horizon Markov Decision Processes (2012, background): “Interestingly, this very constant 2γ (1−γ)2 appears in many works analyzing AVI algorithms [25, 11, 27, 12, 13, 23, 7, 6, 20, 21, 22, 9], API algorithms [15, 19, 16, 1, 8, 18, 5, 17, 10, 3, 9, 2] and in one of their generalization [26], suggesting that it cannot be improved.”
Safe Policy Iteration (2013, background): “When either Qπk or the corresponding greedy policy πk+1 cannot be computed exactly, approximate policy iteration (API) algorithms (refer to (Bertsekas, 2011) for a recent survey on API) need to be considered.”