Timezone: »
Oral
On the Use of NonStationary Policies for Stationary InfiniteHorizon Markov Decision Processes
Bruno Scherrer · Boris Lesner
We consider infinitehorizon stationary $\gamma$discounted Markov Decision Processes, for which it is known that there exists a stationary optimal policy. Using Value and Policy Iteration with some error $\epsilon$ at each iteration, it is wellknown that one can compute stationary policies that are $\frac{2\gamma{(1\gamma)^2}\epsilon$optimal. After arguing that this guarantee is tight, we develop variations of Value and Policy Iteration for computing nonstationary policies that can be up to $\frac{2\gamma}{1\gamma}\epsilon$optimal, which constitutes a significant improvement in the usual situation when $\gamma$ is close to $1$. Surprisingly, this shows that the problem of ``computing nearoptimal nonstationary policies'' is much simpler than that of ``computing nearoptimal stationary policies''.
Author Information
Bruno Scherrer (INRIA)
Boris Lesner (INRIA)
More from the Same Authors

2013 Poster: Approximate Dynamic Programming Finally Performs Well in the Game of Tetris »
Victor Gabillon · Mohammad Ghavamzadeh · Bruno Scherrer 
2013 Poster: Improved and Generalized Upper Bounds on the Complexity of Policy Iteration »
Bruno Scherrer 
2012 Poster: On the Use of NonStationary Policies for Stationary InfiniteHorizon Markov Decision Processes »
Bruno Scherrer · Boris Lesner 
2008 Poster: Biasing Approximate Dynamic Programming with a Lower Discount Factor »
Marek Petrik · Bruno Scherrer