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?
  • 2
    $\begingroup$ Could you provide a reference for where you found this claim? $\endgroup$ – mikkola Apr 12 at 13:40
  • 1
    $\begingroup$ Yes, the claim sounds really strange - can you provide some references? $\endgroup$ – Kostya Apr 12 at 13:50
  • 1
    $\begingroup$ 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. $\endgroup$ – user529295 Apr 13 at 3:28
  • $\begingroup$ @user529295 this "friend" of yours - does he by any chance supervises your PhD? $\endgroup$ – Kostya Apr 16 at 23:29
  • $\begingroup$ This seems to be true for a MDP with finite states, as any policy will have a bounded return irrespective of the policy. But I don't think this holds for infinite chains. So I am guessing it might be possible to construct a policiy for IHP and another policy in FHP which will have the same expected return. $\endgroup$ – user9947 Apr 19 at 13:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.