# What is the difference between a stationary and a non-stationary policy?

In reinforcement learning, there are deterministic and non-deterministic (or stochastic) policies, but there are also stationary and non-stationary policies.

What is the difference between a stationary and a non-stationary policy? How do you formalize both? Which problems (or environments) require a stationary policy as opposed to a non-stationary one (and vice-versa)?

## 1 Answer

A stationary policy, $$\pi_t$$, is a policy that does not change over time, that is, $$\pi_t = \pi, \forall t \geq 0$$, where $$\pi$$ can either be a function, $$\pi: S \rightarrow A$$ (a deterministic policy), or a conditional density, $$\pi(A \mid S)$$ (a stochastic policy). A non-stationary policy is a policy that is not stationary. More precisely, $$\pi_i$$ may not be equal to $$\pi_j$$, for $$i \neq j \geq 0$$, where $$i$$ and $$j$$ are thus two different time steps.

There are problems where a stationary optimal policy is guaranteed to exist. For example, in the case of a stochastic (there is a probability density that models the dynamics of the environment, that is, the transition function and the reward function) and discrete-time Markov decision process (MDP) with finite numbers of states and actions, and bounded rewards, where the objective is the long-run average reward, a stationary optimal policy exists. The proof of this fact is in the book Markov Decision Processes: Discrete Stochastic Dynamic Programming (1994), by Martin L. Puterman, which apparently is not freely available on the web.