2
$\begingroup$

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)?

$\endgroup$
2
$\begingroup$

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 deterministic 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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ I am a little doubtful of the notation used for deterministic policy. A stochastic policy also can also be written like that I guess (a mapping from $S$ to $A$). By deterministic I guess you mean probability 1 or greedy policy? So I think the notation $f(S) = A$ is more suited. $\endgroup$ – DuttaA May 14 at 12:48
  • $\begingroup$ @DuttaA By deterministic policy I mean it picks the same action in a given state with probability $1$, i.e. it's a function. For example, $f(x) = x^2$ always gives you the same number for the same input. You write $f(S) = A$, but, in this answer, $S$ is the space of states and $A$ is the space of actions, so that would not be appropriate (because the input is not a space). Also, $f(S)$ typically refers to the output of the function $f$. The notation $f: S \rightarrow A$ represents a mapping. It's the typical way of definiting a certain function from a certain domain to a certain codomain. $\endgroup$ – nbro May 14 at 12:59
  • $\begingroup$ In another answer I had written, I was trying to formalize stochastic policies as mappings, but that notation is not that common. It's more common to write them as conditional probability distributions. In practice, however, they are a family (or set) of probability distributions, because, for each state, you will have a different probability distribution. But people often ignore this and say that a stochastic policy is a "conditional probability distribution", but that's not correct. It's an "abuse of terminology". $\endgroup$ – nbro May 14 at 12:59
  • $\begingroup$ That was for the sake of comments, what I meant was $f(s) = a \forall s \epsilon S, a \epsilon A$. But yes I guess I just stated a redundant thing. $\endgroup$ – DuttaA May 14 at 13:06
  • $\begingroup$ Why is the term 'conditional probability distribution' incorrect? It is conditioned on a particular state. Are you saying since multiple states exist the term is incorrect? $\endgroup$ – DuttaA May 14 at 13:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.