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

Résumé

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

Chercheur postdoctoral en informatique

Mes intérêts de recherche incluent l’intelligence artificielle et l’exploitation de l’architecture moderne des ordinateurs lors de la conception et de l’implémentation d’algorithmes et de structures de données.