1. When can we approximate a finite horizon MDP with infinite horizon?
  2. Can we use infinite horizon stochastic shortest path problem on a directed acyclic graph?

Markov decision problem theory and computation is based on using backward induction (dynamic programming) to recursively evaluate expected rewards. When we define a policy $\pi = (d_1, d_2,...,d_{N-1})$, we assume that $N$, the length of horizon or the number of epochs is given.While in the infinite horizon the policies can be defined as, $\nu = (d_1, d_2,...)$ with no limitation on the length of the horizon.

On the other hand, we can only compare two policies whenever their length is equal, in other words, we can compare the immediate rewards in each and every epochs for those policies. In my opinion, the infinite horizon can be used to approximate the finite horizon if it is possible to compare a given policy on both horizons and the infinite horizon policy's reward can give a good upper or lower bound on the expected value of finite horizon policy.

Whit that being mentioned, approximating infinite horizon continuous time stochastic processes by using "Uniformization" technique and convert the problem to a discrete time Markov decision process is a well-known and well-studied procedure. Looking at the technique may give some hints on how the same approach can be used for approximation of the finite horizon process by the infinite horizon one.

Chapter 4 and 5 of the below-referenced book by Martin PUTERMAN, which discuss the finite and infinite horizon processes are highly recommended.

Puterman, Martin L. Markov Decision Processes.: Discrete Stochastic Dynamic Programming. John Wiley & Sons, 2014.


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.