Tight Performance Bounds for Approximate Modified Policy Iteration with Non-Stationary Policies

By Boris Lesner, Bruno Scherrer. 2013

3 citations recorded by the source corpus.

We consider approximate dynamic programming for the infinite-horizon stationary $\gamma$-discounted optimal control problem formalized by Markov Decision Processes. While in the exact case it is known that there always exists an optimal policy that is stationary, we show that when using value function approximation, looking for a non-stationary policy may lead to a better performance guarantee. We define a non-stationary variant of MPI that unifies a broad family of approximate DP algorithms of the literature. For this algorithm we provide an error propagation analysis in the form of a performance bound of the resulting policies that can improve the usual performance bound by a factor $O\left(1-\gamma\right)$, which is significant when the discount factor $\gamma$ is close to 1. Doing so, our approach unifies recent results for Value and Policy Iteration. Furthermore, we show, by constructing a specific deterministic MDP, that our performance guarantee is tight.

Subfields: Artificial Intelligence, Electrical and Electronic Engineering, 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 Electrical and Electronic Engineering

In Management Science and Operations Research

Citations in the corpus

Approximate modified policy iteration and its application to the game of Tetris (2015, methodology): “Interesting future work includes 1) the adaptation and precise analysis of our three algorithms to the computation of non-stationary policies—we recently showed that considering a variation of AMPI for computing non-stationary policies allows improving the 1 (1−γ)2 constant (Lesner and Scherrer, 201”