On the Use of Non-Stationary Policies for Infinite-Horizon Discounted Markov Decision Processes
This provides a theoretical improvement for researchers in reinforcement learning, showing that computing approximately optimal non-stationary policies is simpler than for stationary policies, though it is incremental as it builds on known Value Iteration methods.
The paper tackles the problem of performance bounds for infinite-horizon discounted Markov Decision Processes, showing that using non-stationary policies generated by Value Iteration reduces state-of-the-art bounds by a factor of (1-γ)/(1-γ^m), significantly improving asymptotic bounds from γ/(1-γ)^2 ε to γ/(1-γ) ε when γ is close to 1.
We consider infinite-horizon $γ$-discounted Markov Decision Processes, for which it is known that there exists a stationary optimal policy. We consider the algorithm Value Iteration and the sequence of policies $π_1,...,π_k$ it implicitely generates until some iteration $k$. We provide performance bounds for non-stationary policies involving the last $m$ generated policies that reduce the state-of-the-art bound for the last stationary policy $π_k$ by a factor $\frac{1-γ}{1-γ^m}$. In particular, the use of non-stationary policies allows to reduce the usual asymptotic performance bounds of Value Iteration with errors bounded by $ε$ at each iteration from $\fracγ{(1-γ)^2}ε$ to $\fracγ{1-γ}ε$, which is significant in the usual situation when $γ$ is close to 1. Given Bellman operators that can only be computed with some error $ε$, a surprising consequence of this result is that the problem of "computing an approximately optimal non-stationary policy" is much simpler than that of "computing an approximately optimal stationary policy", and even slightly simpler than that of "approximately computing the value of some fixed policy", since this last problem only has a guarantee of $\frac{1}{1-γ}ε$.