On the Use of Non-Stationary Policies for Stationary Infinite-Horizon Markov Decision Processes

By Bruno Scherrer, Boris Lesner. 2012

53 citations recorded by the source corpus.

We consider infinite-horizon stationary γ-discounted Markov Decision Processes, for which it is known that there exists a stationary optimal policy. Using Value and Policy Iteration with some error e at each iteration, it is well-known that one can compute stationary policies that are 2γ/(1 - γ)2 e-optimal. After arguing that this guarantee is tight, we develop variations of Value and Policy Iteration for computing non-stationary policies that can be up to 2γ/1-γ e-optimal, which constitutes a significant improvement in the usual situation when γ is close to 1. Surprisingly, this shows that the problem of "computing near-optimal non-stationary policies" is much simpler than that of "computing near-optimal stationary policies".

How researchers see this paper

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

Citations in the corpus

Approximate Policy Iteration Schemes: A Comparison (2014, methodology): “The ﬁrst bound of NSPI( m ) can be seen as an adaptation of that provided by Scherrer & Lesner (2012) for the more restrictive (cid:96) ∞ -norm setting. discount factor γ , the quality (cid:15) of the approximate greedy operator, and—if applicable—the main parameters α / m of the algorithms.”
Tight Performance Bounds for Approximate Modified Policy Iteration with Non-Stationary Policies (2013, methodology): “Since it is well known that there exists an optimal policy that is stationary, our result—as well as those of Scherrer and Lesner (2012)—suggesting to consider non-stationary policies may appear strange.”
Automated Planning and Acting (2016, background): “However, extending the state representation (with variables representing the context) is often easier than handling general non-stationary stochastic models, for which fewer algorithms and computational results are known (for example, [527]).”
Approximate Dynamic Programming for Two-Player Zero-Sum Markov Games (2015, methodology): “We generalize it for AGPI in the case of σ-weighted Lp-norm, that is defined for a function h and a distribution σ on the state space as ‖h‖p,σ = (∑ s∈S |h(s)|pσ(s) ) 1 p .”