Solving Markov Decision Processes with Reachability Characterization from Mean First Passage Times
This work addresses the computational efficiency of MDPs for applications like robotics, though it appears incremental as it modifies existing methods.
The paper tackles the problem of efficiently solving Markov decision processes (MDPs) by introducing a reachability landscape based on Mean First Passage Time (MFPT) to characterize state importance, resulting in new algorithms (MFPT-VI and MFPT-PI) that outperform state-of-the-art solutions in runtime and iteration count in robotic decision-making scenarios.
A new mechanism for efficiently solving the Markov decision processes (MDPs) is proposed in this paper. We introduce the notion of reachability landscape where we use the Mean First Passage Time (MFPT) as a means to characterize the reachability of every state in the state space. We show that such reachability characterization very well assesses the importance of states and thus provides a natural basis for effectively prioritizing states and approximating policies. Built on such a novel observation, we design two new algorithms -- Mean First Passage Time based Value Iteration (MFPT-VI) and Mean First Passage Time based Policy Iteration (MFPT-PI) -- that have been modified from the state-of-the-art solution methods. To validate our design, we have performed numerical evaluations in robotic decision-making scenarios, by comparing the proposed new methods with corresponding classic baseline mechanisms. The evaluation results showed that MFPT-VI and MFPT-PI have outperformed the state-of-the-art solutions in terms of both practical runtime and number of iterations. Aside from the advantage of fast convergence, this new solution method is intuitively easy to understand and practically simple to implement.