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$ 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

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.