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

• URL: http://arxiv.org/abs/2603.08979v1
• Date: Mon, 09 Mar 2026 22:13:38 GMT
• Title: Data-driven robust Markov decision processes on Borel spaces: performance guarantees via an axiomatic approach
• Abstract summary: We consider Markov decision processes (MDPs) with unknown disturbance distribution.<n>We address this problem using the robust Markov decision process (RMDP) approach.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Minimax Optimality of the Probability Flow ODE for Diffusion Models [8.15094483029656]
  This work develops the first end-to-end theoretical framework for deterministic ODE-based samplers.<n>We propose a smooth regularized score estimator that simultaneously controls both the $L2$ score error and the associated mean Jacobian error.<n>We demonstrate that the resulting sampler achieves the minimax rate in total variation distance, modulo logarithmic factors.
  arXiv  Detail & Related papers  (2025-03-12T17:51:29Z)
• Statistical Inference for Temporal Difference Learning with Linear Function Approximation [55.80276145563105]
  We investigate the statistical properties of Temporal Difference learning with Polyak-Ruppert averaging.<n>We make three theoretical contributions that improve upon the current state-of-the-art results.
  arXiv  Detail & Related papers  (2024-10-21T15:34:44Z)
• A Uniform Concentration Inequality for Kernel-Based Two-Sample Statistics [4.757470449749877]
  We show that these metrics can be unified under a general framework of kernel-based two-sample statistics.<n>This paper establishes a novel uniform concentration inequality for the aforementioned kernel-based statistics.<n>As illustrative applications, we demonstrate how these bounds facilitate the component of error bounds for procedures such as distance covariance-based dimension reduction.
  arXiv  Detail & Related papers  (2024-05-22T22:41:56Z)
• Discrete Probabilistic Inference as Control in Multi-path Environments [84.67055173040107]
  We consider the problem of sampling from a discrete and structured distribution as a sequential decision problem. We show that GFlowNets learn a policy that samples objects proportionally to their reward by enforcing a conservation of flows. We also prove that some flow-matching objectives found in the GFlowNet literature are in fact equivalent to well-established MaxEnt RL algorithms with a corrected reward.
  arXiv  Detail & Related papers  (2024-02-15T20:20:35Z)
• Distributed Markov Chain Monte Carlo Sampling based on the Alternating Direction Method of Multipliers [143.6249073384419]
  In this paper, we propose a distributed sampling scheme based on the alternating direction method of multipliers. We provide both theoretical guarantees of our algorithm's convergence and experimental evidence of its superiority to the state-of-the-art. In simulation, we deploy our algorithm on linear and logistic regression tasks and illustrate its fast convergence compared to existing gradient-based methods.
  arXiv  Detail & Related papers  (2024-01-29T02:08:40Z)
• On diffusion-based generative models and their error bounds: The log-concave case with full convergence estimates [5.13323375365494]
  We provide theoretical guarantees for the convergence behaviour of diffusion-based generative models under strongly log-concave data.<n>Our class of functions used for score estimation is made of Lipschitz continuous functions avoiding any Lipschitzness assumption on the score function.<n>This approach yields the best known convergence rate for our sampling algorithm.
  arXiv  Detail & Related papers  (2023-11-22T18:40:45Z)
• Concentration analysis of multivariate elliptic diffusion processes [0.0]
  We prove concentration inequalities and associated PAC bounds for continuous- and discrete-time additive functionals. Our analysis relies on an approach via the Poisson equation allowing us to consider a very broad class of subexponentially ergodic processes.
  arXiv  Detail & Related papers  (2022-06-07T14:15:05Z)
• Adversarially Robust Topological Inference [20.02318707644732]
  In particular, the sublevel sets of the distance function are used in the computation of persistent homology.<n>Despite its stability to perturbations in the Hausdorff distance, persistent homology is highly sensitive to outliers.<n>We propose a textitmedian-of-means variant of the distance function (textsfMoM Dist) and establish its statistical properties.
  arXiv  Detail & Related papers  (2022-06-03T19:45:43Z)
• Reinforcement Learning from Partial Observation: Linear Function Approximation with Provable Sample Efficiency [111.83670279016599]
  We study reinforcement learning for partially observed decision processes (POMDPs) with infinite observation and state spaces. We make the first attempt at partial observability and function approximation for a class of POMDPs with a linear structure.
  arXiv  Detail & Related papers  (2022-04-20T21:15:38Z)
• Robust Estimation for Nonparametric Families via Generative Adversarial Networks [92.64483100338724]
  We provide a framework for designing Generative Adversarial Networks (GANs) to solve high dimensional robust statistics problems. Our work extend these to robust mean estimation, second moment estimation, and robust linear regression. In terms of techniques, our proposed GAN losses can be viewed as a smoothed and generalized Kolmogorov-Smirnov distance.
  arXiv  Detail & Related papers  (2022-02-02T20:11:33Z)
• Parallel Stochastic Mirror Descent for MDPs [72.75921150912556]
  We consider the problem of learning the optimal policy for infinite-horizon Markov decision processes (MDPs) Some variant of Mirror Descent is proposed for convex programming problems with Lipschitz-continuous functionals. We analyze this algorithm in a general case and obtain an estimate of the convergence rate that does not accumulate errors during the operation of the method.
  arXiv  Detail & Related papers  (2021-02-27T19:28:39Z)
• Distributional Robustness and Regularization in Reinforcement Learning [62.23012916708608]
  We introduce a new regularizer for empirical value functions and show that it lower bounds the Wasserstein distributionally robust value function. It suggests using regularization as a practical tool for dealing with $textitexternal uncertainty$ in reinforcement learning.
  arXiv  Detail & Related papers  (2020-03-05T19:56:23Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.