Approximate Modified Policy Iteration

By Bruno Scherrer, Victor Gabillon, Mohammad Ghavamzadeh, Matthieu Geist. 2012

53 citations recorded by the source corpus.

Modified policy iteration (MPI) is a dynamic programming (DP) algorithm that contains the two celebrated policy and value iteration methods. Despite its generality, MPI has not been thoroughly studied, especially its approximation form which is used when the state and/or action spaces are large or infinite. In this paper, we propose three implementations of approximate MPI (AMPI) that are extensions of well-known approximate DP algorithms: fitted-value iteration, fitted-Q iteration, and classification-based policy iteration. We provide error propagation analysis that unifies those for approximate policy and value iteration. For the classification-based implementation, we develop a finite-sample analysis that shows that MPI's main parameter allows to control the balance between the estimation error of the classifier and the overall value function approximation.

Subfields: Artificial Intelligence, Computer Networks and Communications, Electrical and Electronic Engineering

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 Electrical and Electronic Engineering

Citations in the corpus

Approximate Policy Iteration Schemes: A Comparison (2014, background): “Relaxing the goal to controlling the weighted `p-norm for some p ≥ 2 allows to introduce some finer coefficients (Farahmand et al., 2010; Scherrer et al., 2012).”
Challenges of Real-World Reinforcement Learning (2019, background): “The general framework is that of batched reinforcement learning (Scherrer et al., 2012), which we recall in Algorithm 1 for clarity.”
A unified view of entropy-regularized Markov decision processes (2017, methodology): “Our analysis in Section 5.1.2 suggests an entire array of algorithms lying between DPP and TRPO, just as Modiﬁed Policy Iteration lies between Value Iteration and Policy Iteration (Puterman and Shin, 1978; Scherrer et al., 2012).”
Approximate Dynamic Programming for Two-Player Zero-Sum Markov Games (2015, methodology): “From linear recursive relations of the kind of Lemma 1, Scherrer et al. (2012) show how to deduce a bound on the Lp-norm of lk.”
Approximate Value Iteration with Temporally Extended Actions (2015, background): “For example, approximate policy iteration (Lazaric, Ghavamzadeh, & Munos, 2010; Scherrer et al., 2012) may also exploit options to speed up convergence.”
Approximate Dynamic Programming Finally Performs Well in the Game of Tetris (2013, unknown): “Fortunately a class of such ADP algorithms, called classification-based policy iteration (CbPI), have been recently developed and analyzed [12, 7, 13, 9, 17].”
Approximate modified policy iteration and its application to the game of Tetris (2015, background): “This paper is a significant extension of two conference papers by the authors (Scherrer et al., 2012; Gabillon et al., 2013).”
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].”
Analysis of Classification-based Policy Iteration Algorithms (2016, background): “(2010), the idea of classification-based API has been integrated in a variety of different dynamic programming algorithms (see e.g., Gabillon et al. 2011; Scherrer et al. 2012; Farahmand et al. 2013) and it has been shown to be empirically competitive in a series of testbeds and challenging applicat”
Performance bounds for λ policy iteration and application to the game of Tetris (2013, unknown): “In (Scherrer et al., 2012), this has allowed us to provide an Lp norm performance bound for the modified policy iteration family of algorithms (Puterman and Shin, 1978).”