Online Robust Planning under Model Uncertainty: A Sample-Based Approach

Abstract: Online planning in Markov Decision Processes (MDPs) empowers agents to make sequential decisions by simulating future trajectories, making it highly effective for large-scale and dynamic environments. While sample-based methods like Sparse Sampling and Monte Carlo Tree Search (MCTS) are widely adopted, they rely heavily on the assumption of a perfect generative model. In practice, these models are estimated from limited data, and the resulting approximation errors can cause standard planners to execute suboptimal or critically unsafe behaviors. Robust MDPs (RMDPs) provide a principled framework to mitigate this model uncertainty; however, existing RMDP solvers are computationally intensive and primarily restricted to offline use. In this work, we introduce Robust Sparse Sampling (RSS), the first online planning algorithm for RMDPs that offers finite-sample theoretical performance guarantees. By leveraging the computational efficiency of Sample Average Approximation (SAA), RSS bridges the gap between robust offline theory and scalable online planning. Our algorithm computes a robust value function on the fly, enabling tractable, worst-case policy optimization in real-time. Crucially, RSS accommodates continuous and infinite state spaces, as its sample and computational complexities are strictly independent of the state space size. We provide rigorous theoretical performance bounds and empirically demonstrate that RSS significantly outperforms standard Sparse Sampling in environments with uncertain dynamics, ensuring safer and more resilient autonomous behavior.