Answers.Body: <p>In the discussion about Neil Slater's answer (that he, sadly, deleted) it was pointed out that the policy <span class="math-container">$\pi$</span> should also depend on the horizon <span class="math-container">$h$</span>. The decision of action <span class="math-container">$a$</span> can be influenced by how many steps are left. So, the &quot;policy&quot; in that case is actually a collection of policies <span class="math-container">$\pi_h(a|s)$</span> indexed by <span class="math-container">$h$</span> - the distance to horizon.</p>
  <p>Alternatively, one can look at it as if our state space <span class="math-container">$\mathcal{S}$</span> is now extended with that integer. So we can &quot;lift&quot; our original finite-horizon MDP <span class="math-container">$(\mathcal{S},\mathcal{A},P,R)$</span> into a new infinite-horizon MDP by substituting:</p>
  <p><span class="math-container">$$\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  
  $$</span>
  The new reward and transition functions make sure that the horizon is decreasing, and that we are ending up in a capture state <span class="math-container">$\epsilon$</span> that has no future effects:
  <span class="math-container">$$ \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 
  $$</span>
  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.</p>
  <p>Couple of notes:</p>
  <ul>
  <li>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.</li>
  <li>The infinite-horizon policy iteration convergence relies on a discounting factor <span class="math-container">$\gamma &lt; 1$</span>. The finite-horizon doesn't need <span class="math-container">$\gamma$</span> for convergence. That's where I feel like I've cheated a bit.</li>
  <li>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.</li>
  </ul>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-04-16T18:38:57.563Z
Answers.Text: Intuitively, I understand that the policy should depend on horizon $h$. However, why do we have to "extend" our state space? Also, why did @neilslater delete his answer? I didn't quite see his answer.
Answers.UserDisplayName: user529295
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-04-16T18:44:31.513Z
Answers.Text: @user529295 The idea is that, instead of having multiple policies, you have multiple versions of each state. And your transition probabilities always decrease the numerical index associated to each state.
Answers.UserDisplayName: Kostya
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-04-16T18:45:25.367Z
Answers.Text: Regarding your reservation with respect to discount factor $\gamma$, my view is that finite horizon MDP is similar to stochastic shortest path with fixed horizon rather than random. In that way, we don't have to rely on discounted MDP formulation (or discount factor, in general). However, I ain't sure if my view is correct.
Answers.UserDisplayName: user529295
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-04-16T19:35:17.763Z
Answers.Text: @user529295 I think you are exactly right - the new "lifted" MDP can be seen as a SSP with the target state $\epsilon$
Answers.UserDisplayName: Kostya
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-04-16T20:48:20.017Z
Answers.Text: @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
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-04-19T13:26:56.390Z
Answers.Text: @DuttaA I'm not totally sure, but if "proper" means - "reaches the goal state with P=1". Then any policy over "lifted" MDP is "proper", because the transition function is structured that way.
Answers.UserDisplayName: Kostya
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-04-19T13:47:20.960Z
Answers.Text: @DuttaA The dynamics (transition function) is such that you always reach the goal state - no matter what your policy is.
Answers.UserDisplayName: Kostya
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-04-19T14:03:58.757Z
Answers.Text: @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.
Answers.UserDisplayName: Kostya
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-04-23T05:47:59.320Z
Answers.Text: @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.
Answers.UserDisplayName: user529295
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-04-23T08:16:49.720Z
Answers.Text: @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.
Answers.UserDisplayName: Kostya
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-04-23T08:37:25.270Z
Answers.Text: @DuttaA There is not a single mention of SSPs in Sutton and Barto. They define MDP in the 3rd chapter and use MDPs throughout the book.
Answers.UserDisplayName: Kostya
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-04-23T09:03:21.720Z
Answers.Text: 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.
Answers.UserDisplayName: Kostya
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-04-16T17:02:48.200Z
Answers.LastActivityDate: 2021-04-16T22:53:47.940Z
Answers.LastEditDate: 2021-04-16T22:53:47.940Z
Answers.UserDisplayName: Kostya
Body: <p>Most RL books (Sutton &amp; 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?</p>
  
Tags: <reinforcement-learning><markov-decision-process><convergence><policy-iteration>
Title: Does the policy iteration convergence hold for finite-horizon MDP?
UserDisplayName: user529295
ThreadText: # Does the policy iteration convergence hold for finite-horizon MDP?
  
  (Asked by: username_0 on 2021-04-14)
  
  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?
  
  **Tags:** reinforcement-learning, markov-decision-process, convergence, policy-iteration
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2021-04-16. Score: 3
  
  In the discussion about username_2 username_2'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.
  
  > **Comments:**
  > **username_0**: Intuitively, I understand that the policy should depend on horizon $h$. However, why do we have to "extend" our state space? Also, why did @username_2 delete his answer? I didn't quite see his answer.  
  > **username_1**: @username_0 The idea is that, instead of having multiple policies, you have multiple versions of each state. And your transition probabilities always decrease the numerical index associated to each state.  
  > **username_0**: Regarding your reservation with respect to discount factor $\gamma$, my view is that finite horizon MDP is similar to stochastic shortest path with fixed horizon rather than random. In that way, we don't have to rely on discounted MDP formulation (or discount factor, in general). However, I ain't sure if my view is correct.  
  > **username_1**: @username_0 I think you are exactly right - the new "lifted" MDP can be seen as a SSP with the target state $\epsilon$  
  > **username_2**: @username_0 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  
  > **username_1**: @DuttaA I'm not totally sure, but if "proper" means - "reaches the goal state with P=1". Then any policy over "lifted" MDP is "proper", because the transition function is structured that way.  
  > **username_1**: @DuttaA The dynamics (transition function) is such that you always reach the goal state - no matter what your policy is.  
  > **username_1**: @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.  
  > **username_0**: @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.  
  > **username_1**: @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.  
  > **username_1**: @DuttaA There is not a single mention of SSPs in Sutton and Barto. They define MDP in the 3rd chapter and use MDPs throughout the book.  
  > **username_1**: 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.  
  
  ---
  
  