math.OCMar 9, 2026

Data-driven robust Markov decision processes on Borel spaces: performance guarantees via an axiomatic approach

Authors: Sivaramakrishnan Ramani

Organizations: Department of Computational Applied Mathematics and Operations Research, Rice University, Houston, USA.

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

We consider Markov decision processes (MDPs) with unknown disturbance distribution and address this problem using the robust Markov decision process (RMDP) approach. We construct the empirical distribution of the unknown disturbance distribution and characterize our ambiguity set of distributions as the sublevel set of a nonnegative distance function from the empirical distribution. By connecting the weak convergence of distributions to convergence with respect to the distance function, we prove that the robust optimal value function and the out-of-sample value function converge to the true optimal value function with increasing sample-sizes. We establish that, for finite sample-sizes, the robust optimal value function serves as a high probability upper bound on the out-of-sample value function. We also obtain probabilistic convergence rates, sample complexity bounds, and out-of-distribution performance bounds. The finite sample performance guarantees rely on the distance function satisfying a certain concentration type inequality. Several well-studied distances in the literature meet the requirements imposed on the distance function. We also analyze the data-driven properties of empirical MDPs and demonstrate that, unlike our data-driven RMDPs, empirical MDPs fail to satisfy some of the finite sample performance guarantees.

Figures & tables

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

NotationDescriptionReference
J~N,ϵ\tilde{J}^{N,\epsilon}Robust optimal value function( 4 )
π^N\hat{\pi}^{N}Robust optimal policyp. 3
Φ~N,ϵ\tilde{\Phi}^{N,\epsilon}Robust Bellman operator( 6 )
J∗J^{*}Optimal value function( 2 )
J(π^N,⋅)J(\hat{\pi}^{N},\cdot)Out-of-sample value functionp. 3
Φ,Φπ\Phi,\Phi_{\pi}Bellman and evaluation operator( 8 ), ( 9 )
Appendix
Table 1: MDP and data-driven RMDP notations.
More in this topic

Robust Markov Decision Processes

Robust Markov decision processes optimize decisions under uncertain dynamics, seeking reliable performance against adverse transition models.

See all 26 papers

Explore similar work

CardsList

  1. Robust Average-Reward Markov Decision Processes: Minimax-Optimal Learning via Plug-in Reductions

    Aug 6, 2026Yuepeng Yang, Yuxin Chen, Yuejie ChiRobust Markov Decision ProcessesAverage-Reward RL

    *Department of Statistics and Data Science, Yale University. · †Department of Statistics and Data Science, the Wharton School, University of Pennsylvania.

  2. Efficient Q-Learning and Actor-Critic Methods for Robust Average-Reward Reinforcement Learning

    Jun 8, 2025Yang Xu, Swetha Ganesh, Vaneet AggarwalRobust Markov Decision ProcessesReinforcement Learning

    Purdue University, West Lafayette, Indiana, USA 47907

  3. Distributionally Robust Reinforcement Learning with Interactive Data Collection: Fundamental Hardness and Near-Optimal Algorithms

    Apr 4, 2024Miao Lu, Han Zhong, Tong Zhang +1Distributionally Robust RLRobust RL

    †Department of Management Science and Engineering, Stanford University. · ‡Center for Data Science, Peking University. · §Department of Computer Science, University of Illinois Urbana-Champaign.