What is the difference between a non-stationary policy and a state that stores time?

Question

This question is related to What does "stationary" mean in the context of reinforcement learning?, but I have a more specific question to clarify the difference between a non-stationary policy and a state that includes time.

My understanding is that, in general, a non-stationary policy is a policy that doesn't change. My first (probably incorrect) interpretation of that was that it meant that the state shouldn't contain time. For example, in the case of game, we could encode time as the current turn, which increases every time the agent takes an action. However, I think even if we include the turn in the state, the policy is still non-stationary so long as sending the same state (including turn) to the policy produces the same action (in case of a deterministic policy) or the same probability distribution (stochastic policy).

I believe the notion of stationarity assumes an additional implicit background state that counts the number of times we have evaluated the policy, so a more precise way to think about a policy (I'll use a deterministic policy for simplicity) would be:

$$ \pi : \mathbb{N} \times S \rightarrow \mathbb{N} \times A $$ $$ \pi : (i, s_t) \rightarrow (i + 1, s_{t+1}) $$

instead of $\pi : S \rightarrow A$.

So, here is the question: Is it true that a stationary policy must satisfy this condition?

$$ \forall i, j \in \mathbb{N}, s \in S, \pi (i, s) = \pi(j, s) $$

In other words, the policy must output the same result no matter when we evaluate it (either the ith or jth time). Even if the state $S$ contains a counter of the turn, the policy would still be non-stationary because for the same state (including turn), no matter how many times you evaluate it, it will return the same thing. Correct?

As a final note, I want to contrast the difference between a state that includes time, with the background state I called $i$ in my definition of $\pi$. For example, when we run an episode of 3 steps, the state $S$ will contain 0, 1, 2, and the background counter of number of the policy $i$ will also be set to 2. Once we reset the environment to evaluate the policy again, the turn, which we store in the state, will go back to 0, but the background number of evaluations won't reset and it will be 3. My understanding is that in this reset is when we could see the non-stationarity of the policy in action. If we get a different result here it's a non-stationary policy, and if we get the same result it's a stationary policy, and such property is independent of whether or not we include the turn in the state. Correct?

Answer 1

So, here's is the question: Is it true that a non-stationary policy must satisfy this condition?

$$ \forall i, j \in \mathbb{N}, s \in S, \pi (i, s) = \pi(j, s) $$

With your custom notation (which certainly isn't common, but seems reasonable)... I assume you meant to say that a stationary policy must satisfy that condition, rather than that a non-stationary policy must satisfy that condition. In that case, yeah, that seems correct to me. A stationary policy would satisfy that condition, and a non-stationary one wouldn't.

---

Wrapping back to the more usual notation, where $\pi(S, A)$ denotes a probability of selecting $A$ in $S$ (which also still covers the case of a deterministic policy, which would simply assign a probability of $1$ to a single action, and $0$ to all others)... I think it's still interesting to consider the case where we decide to "bake" a time-step counter into the state representation.

With this notation, for two different time steps $t$ and $t'$, such that $t \neq t'$, I'd say that a policy $\pi$ is stationary if and only if:

$$\pi(S_t, A_t) = \pi(S_{t'}, A_{t'}) \text{ if } S_t = S_{t'} \wedge A_t = A_{t'}.$$

Note that if we decide to include $t$ in the state-representation, the case that $S_t = S_{t'}$ with $t \neq t'$ will actually never hold within the same episode, states at different time steps will always automatically be different from each other if the time step is one of the "features" encoded in the state. So, within a single episode a policy with a "time-aware" state representation will always automatically be stationary because there cannot be any repeating states. Of course, if you start looking across multiple different episodes, this can change; this is what you're doing when you write:

Once we reset the environment to evaluate the policy again, the turn, which we store in the state, will go back to 0, but the background number of evaluations won't reset and it will be 3.

If you chose to also embed that "episode counter" into the state representation, you would also no longer have any state repetitions at all anymore across different episodes (I don't think doing this would ever be a good idea though).

Answer 2

I think you're overthinking it. I've never seen a formalisation of the concept of "stationary policy" (apart from yours). However, in general, "stationary" means that something does not change (over time). In the context of reinforcement learning, you can interpret it in such a way that it is consistent with the context where you find this expression, unless you decide to formalise this expression (like you've tried in this question).

I think it might be useful to differentiate between the learning phase and the "inference" (or "behaviour") phase, even though these two might interleave in the RL context, that is, you might be using a policy (to behave in the real-world) even though you're still attempting to find the best policy (and I am not just referring to on-policy algorithms, but, in general, you might be using a policy to behave in the real-world which is sub-optimal while your learning algorithm, like Q-learning, is attempting to find the best policy).

During the learning phase, the policy will keep changing over time (anyway), because you still haven't found the optimal policy. So, you could call the policy derived from the $Q$ values, during the $Q$-learning algorithm, a non-stationary policy, because it keeps changing (because the $Q$ values also keep changing). However, it is often the case that these are considered different policies associated with different approximations of the $Q$ function.

You could also call a policy that changes in response to changes of the (dynamics of the) environment a non-stationary policy. In this case, you would call such an environment a non-stationary environment (because e.g. its transition model might keep changing over time).

The problem that you describe when you compare the state $i$ with states that encode time only arises because of your definition of state $i$. You can also reset $i$ when you reset the environment.