Why is the optimal policy non-stationary in the case finite-horizon problems, whereas it is stationary in the case of infinite-horizon problems?

Question

I have difficulty understanding the meaning of stationary policy in the RL (MDP) setting.

Specifically, let's assume stationary dynamics $$P(s_{t+1}=j|s_t=i,a) = P (s_{k+1}=j|s_k=i,a) \ \forall t,k,i,j,a$$ In other words, given a fixed policy, the probability of transitioning from state $i$ to state $j$ under some action $a$ does not change over time.

We know that a stationary policy will always choose the same action in the same state, independent of time, while a non-stationary policy can choose different action in the same state, depending on time.

I do not understand why in the case of finite-horizon problems the optimal policy is non-stationary while in the case of infinite horizon problems the optimal policy is stationary.

If this is truly the case, why most RL algorithms use stationary policies in episodic settings (i.e. finite-horizon)?

Furthermore, in reality, a lot of environments are non-stationary and it makes more sense to use a non-stationary policy instead of a stationary one. Again, why most RL algorithms use stationary policies in these cases, too?

Answer 1

Yes, you are correct that infinite horizon MDPs admit a stationary policy (which means time-invariant policy).

There are two questions:

1. Why do finite horizon MDPs have a nonstationary policy while infinite horizon MDP has a stationary policy.
2. Why do we use episodic tasks than finite horizon MDPs in practice.

Your first question is easy to answer. Consider a 1 length horizon and a 10 length horizon. If you have only 1 step left, it makes sense to immediately take the action that gives you the highest expected reward. However, if you have more steps, it might be possible to take any action that gives you a lesser reward at the moment but would take you to a better state from where you could get better rewards. For example, if you have an exam tomorrow, you will be busy studying for your exam, and you will keep all other stuff away. If you follow cricket, consider the twenty-twenty matches. The batsman would hit the ball differently for the same kind of ball in the first and the last over. However, in the case of an infinite horizon MDP, how many ever steps you have already taken, you have an infinite number of steps remaining. That means you are exactly in the same situation as the previous time you visited the same state. If you are aware of infinite series sums, consider x = 1+ 1/2 + 1/4 + 1/8 + ...=1 + 1/2(1 + 1/2 + 1/4 + 1/8 +...) = 1 + x/2. The same stuff has happened here, because of which you replace the infinite series in the bracket with s. If you considered a test match to be a decent approximation for an infinite horizon case within the first 20 overs, you would notice that the style of play is consistent over these 20 overs (unlike the case in a 20-20 match).

Coming to your second question, episodic tasks are goal-oriented. If you reach a particular state, you can end. No limit is directly imposed on the number of steps the agent can take(in fact you may not even know the time that is required beforehand), but just that he needs to finish the job. Such situations are best modelled as episodic tasks. Another reason from a computational perspective is that policy planning on infinite horizon MDPs is easier than that of finite horizon MDPs.

Answer 2

I will try to give you an intuitive answer that abstracts away from your particular model. For starters, let's note that if you have any situation where the value of a particular action/policy depends on what happens later, then obviously the optimal action/policy is going to depend on your assessment of what is likely to happen later. If you are dealing with a model with stationary transitions then the only thing that is different at each time period is the number of time periods remaining.

Now, in the stationary finite-horizon case with times $t=0,1,2,...,T$, at each time period there is a different number of remaining time periods. Consequently, the "what happens later" is different in each time period, so unsurprisingly, the optima changes at each time period. Contrarily, in the stationary infinite-horizon case with times $t=0,1,2,...$, at each time period there is still an infinite number of future time periods. Since "what happens later" is the same at each time period, there is a single optima.

This type of dynamic arises in all sorts of problems, but one case where it arises is in game theory. For example, consider a cooperative game where the players can cooperate for some mutual benefit, but they can also betray each other for some immediate higher unilateral benefit. In the infinite-horizon game there is no incentive to betray because the long-term consequences will be negative. But in the finite-horizon game, once you get near the end of the game (e.g., the last round) there is no "later" consequence to betrayal, so it becomes more desirable. (Indeed, for this reason, many game theorists believe that cooperative and moral norms of behaviour arise out of an expecation of long-term repeated interaction.)

Answer 3

We know that a stationary policy will always choose the same action in the same state, independent of time, while a non-stationary policy can choose different action in the same state, depending on time.

This is not entirely correct. A stationary policy can still be nondeterministic (e.g. have a 50% chance of selecting action 1, and a 50% chance of selecting action 2, regardless of the current time).

I do not understand why in the case of finite-horizon problems the optimal policy is non-stationary while in the case of infinite horizon problems the optimal policy is stationary.

The example you already gave in comments yourself explains why non-stationary policies may be required in a finite-horizon setting. I don't think the same case can be made for the infinite-horizon setting though, since the discount factor $\gamma$ is not state-dependent, and there is no time limit that suddenly changes whether or not a highly-rewarding state is still reachable.

If this is truly the case, why most RL algorithms use stationary policies in episodic settings (i.e. finite-horizon)? Furthermore, in reality, a lot of environments are non-stationary and it makes more sense to use a non-stationary policy instead of a stationary one. Again, why most RL algorithms use stationary policies in these cases, too?

It's difficult to tell why choices were made across the board without any specific cases; there may have been different reasons in different cases. In many cases, I expect it is done because it is already difficult enough in practice to learn a single stationary policy for complex problems; learning many different policies for different remaining time horizons would take even more time.

Note that, in cases where the remaining time-to-go is observable to an agent, and also considered to be really important, you could include that time-to-go in your state representation. Then, a "stationary" policy that doesn't change over time (but implicitly still takes it into account by observing the remaining time in the state) can still be optimal.