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

arXiv: https://arxiv.org/abs/2509.10162 · HTML: https://mlsanity.com/paper/2509.10162/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 33 references that are in the map.
- First posted on arXiv 12 Sep 2025.

## Builds on (most cited first, 10 of 10)

- [DESPOT: Online POMDP Planning with Regularization](https://mlsanity.com/paper/1609.03250/) (2016)
- [Robust Reinforcement Learning using Offline Data](https://mlsanity.com/paper/2208.05129/) (2022)
- [Sample Complexity of Robust Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2112.01506/) (2021)
- [Online Planning Algorithms for POMDPs](https://mlsanity.com/paper/1401.3436/) (2014)
- [Robust Sample Average Approximation](https://mlsanity.com/paper/1408.4445/) (2014)
- [Optimality Guarantees for Particle Belief Approximation of POMDPs](https://mlsanity.com/paper/2210.05015/) (2022)
- [Robust and Adaptive Planning under Model Uncertainty](https://mlsanity.com/paper/1901.02577/) (2019)
- [Sparse tree search optimality guarantees in POMDPs with continuous observation spaces](https://mlsanity.com/paper/1910.04332/) (2019)
- [Sample Average Approximation for Black-Box VI](https://mlsanity.com/paper/2304.06803/) (2023)
- [Monte Carlo Tree Search in the Presence of Transition Uncertainty](https://mlsanity.com/paper/2312.11348/) (2023)

## Built on by (most cited first, 1 of 1)

- [Scalable Robust MCTS with Anytime Deterministic Optimality Guarantees](https://mlsanity.com/paper/2610.15461/) (2026)

## Abstract (arXiv)

Online planning in Markov Decision Processes (MDPs) enables agents to make sequential decisions by simulating future trajectories from the current state, making it well-suited for large-scale or dynamic environments. Sample-based methods such as Sparse Sampling and Monte Carlo Tree Search (MCTS) are widely adopted for their ability to approximate optimal actions using a generative model. However, in practical settings, the generative model is often learned from limited data, introducing approximation errors that can degrade performance or lead to unsafe behaviors. To address these challenges, Robust MDPs (RMDPs) offer a principled framework for planning under model uncertainty, yet existing approaches are typically computationally intensive and not suited for real-time use. In this work, we introduce Robust Sparse Sampling (RSS), the first online planning algorithm for RMDPs with finite-sample theoretical performance guarantees. Unlike Sparse Sampling, which estimates the nominal value function, RSS computes a robust value function by leveraging the efficiency and theoretical properties of Sample Average Approximation (SAA), enabling tractable robust policy computation in online settings. RSS is applicable to infinite or continuous state spaces, and its sample and computational complexities are independent of the state space size. We provide theoretical performance guarantees and empirically show that RSS outperforms standard Sparse Sampling in environments with uncertain dynamics.