Topology-Driven Solver Selection for Stochastic Shortest Path MDPs via Explainable Machine Learning

Abstract

Selecting optimal solvers for complex AI tasks grows increasingly difficult as algorithmic options expand. We address this challenge for Stochastic Shortest Path Markov Decision Processes (SSP-MDPs) — a core model for robotics navigation, autonomous system planning, and stochastic scheduling — by introducing a topology-driven solver selection framework. First, we identify and empirically validate topological features — including strongly connected components, goal-state ratio, goal eccentricity (i.e., maximal distance to a goal), and average actions per state — that critically influence solver performance across synthetic and real-world SSP-MDPs. Using these insights, we propose the first classifier able to predict the fastest MDP solver for a given instance, achieving over 64% accuracy on diverse benchmarks. Counterfactual explainability analysis further clarifies how these features govern solver efficiency. By directly linking topological structures to algorithmic performance, our work streamlines solver selection while enhancing computational efficiency, offering a principled approach to MDP optimization.

Jaël Champagne Gareau

Postdoctoral Researcher in Computer Science

My research interests include AI and exploitation of modern computer architecture when designing and implementing algorithms and data structures.