5
$\begingroup$

Most RL books (Sutton & Barto, Bertsekas, etc.) talk about policy iteration for infinite-horizon MDPs. Does the policy iteration convergence hold for finite-horizon MDP? If yes, how can we derive the algorithm?

$\endgroup$
13
  • 1
    $\begingroup$ Could you point me to specific chapter/sub-topic? $\endgroup$ – user529295 Apr 19 at 15:00
  • 2
    $\begingroup$ @DuttaA The first two chapter don't take contain any references to the question asked. $\endgroup$ – user529295 Apr 23 at 5:42
  • 2
    $\begingroup$ @DuttaA There aren't any proof related to PI for finite MDP. The PI and API (Asynchronous PI) proof given in Neuro-Dynamic Programming by Bertsekas is for SSPs. Also, SSPs aren't the same as finite MDPs unless specific conditions are met. $\endgroup$ – user529295 Apr 23 at 20:25
  • 2
    $\begingroup$ @DuttaA My definition of finite horizon MDP is the same as before. It is you who is confused between what I've asked in my question and what you have assumed. Also, what do you mean by "authors assessment that FHP are easier than SSPs"? They are easier than SSPs $\textit{in what}$? The authors have written no such thing. Also, on page 17, they mention how to convert "FHP to SSP". Not the other way around. And there are no proof relating to that. Please do your research before casting unfounded accusation, and potentially confusing future readers of this question. $\endgroup$ – user529295 Apr 24 at 2:38
  • 2
    $\begingroup$ Hence, I suggested to attach a screenshot. No sane person would ask a 3 page proof on stackexchange. $\endgroup$ – user529295 Apr 24 at 3:19
3
$\begingroup$

In the discussion about Neil Slater's answer (that he, sadly, deleted) it was pointed out that the policy $\pi$ should also depend on the horizon $h$. The decision of action $a$ can be influenced by how many steps are left. So, the "policy" in that case is actually a collection of policies $\pi_h(a|s)$ indexed by $h$ - the distance to horizon.

Alternatively, one can look at it as if our state space $\mathcal{S}$ is now extended with that integer. So we can "lift" our original finite-horizon MDP $(\mathcal{S},\mathcal{A},P,R)$ into a new infinite-horizon MDP by substituting:

$$\mathcal{S} \to \left(\mathcal{S}\times\{0,1,\dots,h\}\right) \cup \{\epsilon\}\\ \mathcal{A} \to \mathcal{A},\; R \to \tilde R,\; P \to \tilde P $$ The new reward and transition functions make sure that the horizon is decreasing, and that we are ending up in a capture state $\epsilon$ that has no future effects: $$ \tilde P(s'_{n-1}|s_n,a) = P(s'|s,a)\quad\quad \tilde P(\epsilon|s_0,a) =\tilde P(\epsilon|\epsilon,a) = 1\\ \tilde R(s_n,a,s'_{n-1}) = R(s,a,s')\quad\quad \tilde R(s_0,a,\epsilon) =\tilde R(\epsilon,a,\epsilon) = 0 $$ This way I've reduced the finite-horizon MDP to an infinite-horizon one. Thus I can reuse the result for the policy iteration convergence of infinite MDPs.

Couple of notes:

  • At first this feels like a huge increase in the state space making the whole problem unnecessary complex. But this complexity is intrinsic to the problem: both the policy and the value function depend on the distance to horizon. So it is necessary to consider the extended number of unknowns in a single self-consistent manner.
  • The infinite-horizon policy iteration convergence relies on a discounting factor $\gamma < 1$. The finite-horizon doesn't need $\gamma$ for convergence. That's where I feel like I've cheated a bit.
  • I came up with this approach myself. It feels quite obvious though. I'd expect this approach to either be mistaken or be already mentioned somewhere in the literature - comments pointing out one or the other are welcome.
$\endgroup$
19
  • 1
    $\begingroup$ @user529295 I deleted my answer because I was concerned that it may be wrong and misleading. In it I give an algorithm that works for one interpretation of "optimal" for an MDP with horizon held at $t + h$ for all value functions. However, I am concerned it is the wrong interpretation of "optimal", and I did not want to confuse things $\endgroup$ – Neil Slater Apr 16 at 20:48
  • 3
    $\begingroup$ @DuttaA That's not an assumption - that's how I've constructed the "lifted" MDP. Every state has an index $s_i$ that gets decremented at every transition. When the index reaches 0 - we transition to the goal state. $\endgroup$ – Kostya Apr 19 at 14:03
  • 1
    $\begingroup$ @DuttaA You're incorrect about your previous comment "If the policy is not proper FHP becomes IHP". You only need proper policies for SSP problems, which are one version of Infinite horizon problems. You can do away with proper policies if your cost is bounded, thereby, leading to discounted MDPs. Similarly, for finite horizon problems, you only need non-stationary policies, and not proper policies. $\endgroup$ – user529295 Apr 23 at 5:47
  • 1
    $\begingroup$ @DuttaA SSP was never mentioned neither in the question or in the answer. Both question and answer repeatedly state that they deal with MDP. Just saying. $\endgroup$ – Kostya Apr 23 at 8:16
  • 2
    $\begingroup$ Yes, MDPs and SSPs are distinct. In this Q/A we've been talking about MDPs. The Sutton and Barto book is about MDPs. You can reformulate some MDPs as SSPs if you want. This Q/A doesn't discuss this. Sutton and Barto don't either. $\endgroup$ – Kostya Apr 23 at 9:03
-1
$\begingroup$

The proof is similar in idea to the earlier answer. The notations used here are more inclined towards the book Neuro-Dynamic Programming by Bertsekas.

The proof is first we convert a FHP to a SSP (the details of SSP or Stochastic Shortest Path Problem formulation can be found in the aforementioned book) and then refer to the aforementioned book for a complete proof.

Say we have a collection of states $\mathcal S = \{s_1,s_2,...s_n\}$. We consider deterministic policies since Stochastic policies will never be better off then a determinstic policy (convex combination of deterministic policies).

The problem of Finite horizon MDP is defined as:

$$\max_{\mu_0,...\mu_{T-1}} \mathbb E [r_0 + r_1..+V_T(s_T)]$$

where $\mu:\mathcal S \rightarrow \mathcal A$

This can be constructed into an equivalent SSP problem by assigning a time index along with the states i.e we now define states as $s_{i,t}, \forall i \in [n], \forall t \in [T]$. Thus our state space has increased drastically.

Then the equivalent SSP problem becomes:

$$\max_{\mu_0,...\mu_{T}} \mathbb E [r_0 + r_1..r_T|S_0 = s_i]$$ (i.e we start at a particular type of start state, I did not index it with time since it is understood from $S_0$ a r.v of the state reached at time indexed by $t$ i.e $S_t$), where we define $r_T = V_T(s_T)$ and the single stage rewards as $g(s_{i,t}, \mu_{s_{i,t}}, s_{j,t+1}) = r_t$ (where $s_{it},s_{i,t+1}$ are random variables.

There is nothing after timestep $T$ as we define that we have reached a cost free state after time $T$ i.e we can say that $P^{\pi}(S_{T+1} = NV|S_{T} = s_{i,T}) = 1, \forall i, \forall \pi$ and $P^{\pi}(S_{t+1} = NV|S_{t} = NV) = 1, \forall \pi$ and $g(NV,a,NV) = 1, \forall a \in \mathcal A$ where we are taking the actions accordig to a policy $\pi$ hence $P^{\pi}$

NOTE : $\mu_t:\mathcal S_t \rightarrow \mathcal A$ where $S_t = [s_{i,t'}|s_{i,t'} \in S, t'=t]$ i.e basically it only works on states indexed by $t$

Thus we have a SSP problem at hand where by the definition of the problem the agent reaches a cost free step after certain time steps $T$.

Now the proof is pretty straightforward and one can refer to convergence of Asynchronous PI (which is used in practical RL) from Neuro-Dynamic Programming by Bertsekas. The proof is easier in this case due to the fact that all policies are proper, which is a fundamental assumption in the proof for convergence of API for SSP.

Alternatively, if we talk about pure PI (i.e exact Policy Evaluation, and after that one Policy Improvement Step) the proof is a lot easier (again due to all policies being proper). So for an initial policy $\pi_0 = \{\mu_0,...\mu_{T} \}$, we first perform PE (evaluation), which will converge to $V^{\pi_0}$ (the proof of which can again be found in NDP, and probably can also be proved using LLN). After this we do PI (improvement). Since the number of states are finite, the number of policies (deterministic) will be finite and thus we will get a sequence of improving policies until no further improvement is possible and thus our $\pi^*, V^*$ is obtained.

(NOTE: The sufficient sampling of each state is ensured by the transition probabilities, this was not needed in an SSP problem as there was no time index and we could ensure it by exploring starts i.e by choosing every state as a start state infinitely often).

The algorithm for PI can be found in NDP (if model is known) all you need to ensure is exploring starts. While if model is not knwon one can use traditional approaches like MC, TD which will again converge due to Stochastic Approximation Theorem the proof of which can again be found in NDP.

$\endgroup$

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.