10
$\begingroup$
  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?
$\endgroup$
3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

I hope to provide intuitively-appealing answers to both questions.

$\textbf{Question 1:}$

Infinite horizon MDP's do not care about the initial state. They attempt to be optimal in the sense that the policy is optimal for all given allowable initial states. Finite MDP's are computed as optimal for a given state. The policy is intended to be optimal only if you start from that initial state. Neighbouring states (such as in a grid or queue) may have the same finite horizon policy as the aforementioned state but that has more to do with state aggregation properties.

Furthermore, finite horizon MDP's typically have time involved in the Cost function as one might seek time-optimal control (diffusing a bomb as soon as possible). Infinite horizon problems have a boundedness condition on the value function for most algorithms to work. Thus, putting time into the value function simply will not work. Time optimal control cannot be performed via the infinite horizon case or is not recommended. So infinite horizon problems are 'chilled' in the sense that they are not in a rush. An example is controlling traffic at an intersection. There is no goal to reach in some shortest time. You just want to minimize the waiting time of vehicles in some long run scenario.

Note, that I mentioned a goal. This will soon tie into your second question. Finite horizon problems can be distinguished in the sense that they have minimal time as a goal. If you do not include time into your cost function then you can compare infinite and finite horizon problems.

Take Windy Grid-world for an example. Grid-world usually has some absorbing reward state to be reached with negative costs for each step taken. A very big negative state can be placed right next to the reward state. Transitions are stochastic in that the agent might be given forward as an action to be performed but only does so with probability $0.6$. Thus one must be open to the risk that the "wind" might blow the agent into the big negative state if it passes too close to it. We have risk.

Now if you have an N-step finite horizon recursion from a given state then the agent will be concerned with getting to the big reward state in $N$ steps or under. This might even mean risking to go directly passed the big negative state. The infinite horizon policy is not concerned by this rush and will take the risk of the big negative state into account. Its policy will most likely attempt to avoid it.

When can we compare them? Well if $N$ is larger than some number $M$ which might be the sum of the length and width of the grid or even the diagonal length of the grid, then it will essentially not be rushed anymore. That is, $N$ can be considered to be large enough to be an infinite horizon. We would never want to compute an infinite horizon problem using a finite horizon algorithm with large $N$ as it stores a policy for each epoch. Infinite horizon algorithms store only the stationary policy. Exceptions include the n-bias optimality in average reward MDP's. Algorithms exist to deal with this. It is not a issue if dealing with discounted case.

$\textbf{Question 2:}$

Stochastic shortest path (SSP) problems require a path to exist from any initial state to some given "goal" state (I promised we would use the goal state term again). This would be formulated as an absorbing state. If this path does not exist then the problem is not well-posed. The optimal control community uses goal-orientated to essentially describe what the reinforcement community would call an episodic problem. SSP does not require a discount factor to ensure that asymptotic costs be bounded. Note that the boundedness assumption means we are referring to SSP as an inifinite horizon problem. As you mention, it needs a directed acyclic graph where the edges are non-zero transition probabilities. This is discussed in the book Dynamic Programming and Optimal Control Vol II by D. Bertsekas. The questions you ask are dealt with, very elegantly, in this book.

SSP is also good for optimal stopping time problems. These are concerned with time. But wait, did I not mention that when we are concerned with time we use finite horizon recursion of size $N$? Yes, but we need to specify $N$ and the initial state. SSP deals with the best way of transitioning to some goal state in the long run, taking risk into account. The policy is optimal for all well-posed initial states.

$\textbf{Conclusion}$ You might see that MDP's are quite specific in what you want to model. One needs to classify them and check assumptions. The book by Bertsekas guides you through all of this as well as the book mentioned above by Puterman (a bit expensive though). The price of these books are well worth the reward of satisfying one's curiosity for MDP's which are a truly amazing class of problems.

$\endgroup$

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.