Answers.Body: <p>This is discussed in [1], where the authors provide the following proposition:</p>
  <blockquote>
  <p>If <span class="math-container">$FH$</span> is the class of finite-horizon MDPs, <span class="math-container">$IFH$</span> the class of
  infinite-horizon MDPs and <span class="math-container">$SSP$</span> are stochastic shortest-path MDPs,
  then</p>
  <p><span class="math-container">$$ FH \subset SSP \\ IFH \subset SSP $$</span></p>
  </blockquote>
  <p>Here, SSP stands for &quot;Stochastic Shortest Path&quot;, FH for &quot;Finite Horizon&quot;, and IFH for &quot;Infinite Horizon&quot; MDPs. The proofs are summarized below:</p>
  <hr />
  <p>Basically, you transform a <span class="math-container">$FH$</span> MDP into <span class="math-container">$SSP$</span> MDP by:</p>
  <ol>
  <li>Add timestep as a state variable to every state and adjust the transition and reward function accordingly.</li>
  <li>Set every state with a timestep at the horizon as a goal state.</li>
  </ol>
  <hr />
  <p>For <span class="math-container">$IFH$</span> MDP, the transformation into <span class="math-container">$SSP$</span> MDP is done this way:</p>
  <ol>
  <li>Add a unique goal state to the MDP that can be reached from every state with any action with probability <span class="math-container">$\gamma$</span> (the discount factor). This transition will give 0 reward/cost.</li>
  <li>Scale all other probabilities in the transition function by
  <span class="math-container">$(1-\gamma)$</span>.</li>
  </ol>
  <hr />
  <p>The chapter concludes that this is why we can focus on developing <span class="math-container">$SSP$</span> algorithms. However, some methods may be made more efficient by leveraging specific properties of the subclasses.</p>
  <p>[1]: Mausam and Kolobov, Planning with Markov Decision Processes: An AI Perspective, chapter 2, Theorem 2.21</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-01-24T13:08:54.657Z
Answers.Text: Welcome to AI Stack Exchange. Images of textbooks are not a very useful format. They could be copyright material, and also the site will not index them, or make them accessible to screen readers etc. Could you please paraphrase the relevant content from the book that helps answer the question, and remove the images
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-01-24T10:00:58.193Z
Answers.LastActivityDate: 2024-03-19T13:19:14.960Z
Answers.LastEditDate: 2024-03-19T13:19:14.960Z
Answers.UserDisplayName: BoZenKhaa
Answers.Body: <p>I know that if you use a discount factor <span class="math-container">$0 &lt; \gamma &lt; 1$</span> you &quot;shrink&quot; the values of expected accumulated costs (or expected accumulated negative reward) so they converge instead of diverging to infinity for histories originated by some policy.</p>
  <p>What I'm not convinced is that this would mean that we can convert the discounted MDP to an SSP because, for example, we would have to define what the goal states are.</p>
  <p><a href="https://ojs.aaai.org/index.php/AAAI/article/view/8016" rel="nofollow noreferrer">This paper</a> for example covers some use of discounted SSPs (goal states are necessarily defined), bot not necessarily discounted MDPs (goal states are not necessarily defined).</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-04-15T01:02:42.987Z
Answers.LastActivityDate: 2022-04-15T01:02:42.987Z
Answers.UserDisplayName: Gabriel Crispino
Body: <p>I have been reading about discounted MDPs and Stochastic Shortest Path (SSP). I recently came to know (from a friend) that every discounted MDP can be converted to an equivalent SSP but not the other way around. Questions:</p>
  <ol>
  <li>Is this claim true? Is the discount factor equal to 1 when the MDP is converted to an SSP?</li>
  <li>More generally, what is the relationship between these two problem categories?</li>
  </ol>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-04-12T13:40:42.850Z
Comments.Text: Could you provide a reference for where you found this claim?
Comments.UserDisplayName: mikkola
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-04-12T13:50:01.630Z
Comments.Text: Yes, the claim sounds really strange - can you provide some references?
Comments.UserDisplayName: Kostya
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-04-13T03:28:16.307Z
Comments.Text: My friend told me about it. The proposed reason was as follows: Since discounted MDPs don't have a terminal state, they use discount factor as a proxy to reach the terminal state. I can't wrap my head around it.
Comments.UserDisplayName: user529295
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-04-16T23:29:33.323Z
Comments.Text: @user529295 this "friend" of yours - does he by any chance supervises your PhD?
Comments.UserDisplayName: Kostya
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-04-19T15:02:31.943Z
Comments.Text: @Kostya I ain't no PhD student. I happen to learn RL and have a friend who does too.
Comments.UserDisplayName: user529295
Tags: <reinforcement-learning><markov-decision-process><discount-factor>
Title: Relation between discounted MDP and stochastic shortest path problems in RL
UserDisplayName: user529295
ThreadText: # Relation between discounted MDP and stochastic shortest path problems in RL
  
  (Asked by: username_0 on 2021-04-12)
  
  I have been reading about discounted MDPs and Stochastic Shortest Path (SSP). I recently came to know (from a friend) that every discounted MDP can be converted to an equivalent SSP but not the other way around. Questions:
  
  1. Is this claim true? Is the discount factor equal to 1 when the MDP is converted to an SSP?
  2. More generally, what is the relationship between these two problem categories?
  
  **Tags:** reinforcement-learning, markov-decision-process, discount-factor
  
  > **Comments:**
  > **username_1**: Could you provide a reference for where you found this claim?  
  > **username_2**: Yes, the claim sounds really strange - can you provide some references?  
  > **username_0**: My friend told me about it. The proposed reason was as follows: Since discounted MDPs don't have a terminal state, they use discount factor as a proxy to reach the terminal state. I can't wrap my head around it.  
  > **username_2**: @username_0 this "friend" of yours - does he by any chance supervises your PhD?  
  > **username_0**: @username_2 I ain't no PhD student. I happen to learn RL and have a friend who does too.  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_3 on 2024-01-24. Score: 1
  
  This is discussed in [1], where the authors provide the following proposition:
  
  > If $FH$ is the class of finite-horizon MDPs, $IFH$ the class of
  > infinite-horizon MDPs and $SSP$ are stochastic shortest-path MDPs,
  > then
  >
  > $$ FH \subset SSP \\ IFH \subset SSP $$
  
  Here, SSP stands for "Stochastic Shortest Path", FH for "Finite Horizon", and IFH for "Infinite Horizon" MDPs. The proofs are summarized below:
  
  ---
  
  Basically, you transform a $FH$ MDP into $SSP$ MDP by:
  
  1. Add timestep as a state variable to every state and adjust the transition and reward function accordingly.
  2. Set every state with a timestep at the horizon as a goal state.
  
  ---
  
  For $IFH$ MDP, the transformation into $SSP$ MDP is done this way:
  
  1. Add a unique goal state to the MDP that can be reached from every state with any action with probability $\gamma$ (the discount factor). This transition will give 0 reward/cost.
  2. Scale all other probabilities in the transition function by
     $(1-\gamma)$.
  
  ---
  
  The chapter concludes that this is why we can focus on developing $SSP$ algorithms. However, some methods may be made more efficient by leveraging specific properties of the subclasses.
  
  [1]: Mausam and Kolobov, Planning with Markov Decision Processes: An AI Perspective, chapter 2, Theorem 2.21
  
  > **Comments:**
  > **username_4**: Welcome to AI Stack Exchange. Images of textbooks are not a very useful format. They could be copyright material, and also the site will not index them, or make them accessible to screen readers etc. Could you please paraphrase the relevant content from the book that helps answer the question, and remove the images  
  
  ---
  
  ### Answer by username_5 on 2022-04-15. Score: 0
  
  I know that if you use a discount factor $0 < \gamma < 1$ you "shrink" the values of expected accumulated costs (or expected accumulated negative reward) so they converge instead of diverging to infinity for histories originated by some policy.
  
  What I'm not convinced is that this would mean that we can convert the discounted MDP to an SSP because, for example, we would have to define what the goal states are.
  
  [This paper](https://ojs.aaai.org/index.php/AAAI/article/view/8016) for example covers some use of discounted SSPs (goal states are necessarily defined), bot not necessarily discounted MDPs (goal states are not necessarily defined).
  
  
  ---
  
  