Efficient Solution and Learning of Robust Factored MDPs

• URL: http://arxiv.org/abs/2508.00707v1
• Date: Fri, 01 Aug 2025 15:23:15 GMT
• Title: Efficient Solution and Learning of Robust Factored MDPs
• Authors: Yannik Schnitzer, Alessandro Abate, David Parker,
• Abstract summary: Learning r-MDPs from interactions with an unknown environment enables the synthesis of robust policies with provable guarantees on performance.<n>We propose novel methods for solving and learning r-MDPs based on factored state representations.
• Score: 57.2416302384766
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Robust Markov decision processes (r-MDPs) extend MDPs by explicitly modelling epistemic uncertainty about transition dynamics. Learning r-MDPs from interactions with an unknown environment enables the synthesis of robust policies with provable (PAC) guarantees on performance, but this can require a large number of sample interactions. We propose novel methods for solving and learning r-MDPs based on factored state-space representations that leverage the independence between model uncertainty across system components. Although policy synthesis for factored r-MDPs leads to hard, non-convex optimisation problems, we show how to reformulate these into tractable linear programs. Building on these, we also propose methods to learn factored model representations directly. Our experimental results show that exploiting factored structure can yield dimensional gains in sample efficiency, producing more effective robust policies with tighter performance guarantees than state-of-the-art methods.

Related papers

• Efficient Strategy Synthesis for MDPs via Hierarchical Block Decomposition [47.123254940289726]
  Software product lines and robotics utilise Markov decision processes (MDPs) to capture uncertainty and analyse sequential decision-making problems.<n>Despite the usefulness of conventional policy synthesis methods, they fail to scale to large state spaces.<n>Our approach addresses this issue and accelerates policy synthesis in large MDPs by dynamically refining the MDP and iteratively selecting the most fragile MDP regions for refinement.
  arXiv  Detail & Related papers  (2025-06-21T19:03:03Z)
• Robust Counterfactual Inference in Markov Decision Processes [1.5197843979051473]
  Current approaches assume a specific causal model to make counterfactuals identifiable.<n>We propose a novel non-parametric approach that computes tight bounds on counterfactual transition probabilities.
  arXiv  Detail & Related papers  (2025-02-19T13:56:20Z)
• Overcoming the Curse of Dimensionality in Reinforcement Learning Through Approximate Factorization [15.898378661128334]
  Reinforcement Learning (RL) algorithms are known to suffer from the curse of dimensionality. We propose overcoming the curse of dimensionality by approximately factorizing the original Markov decision processes (MDPs) into smaller, independently evolving MDPs. We provide improved sample complexity guarantees for both proposed algorithms.
  arXiv  Detail & Related papers  (2024-11-12T07:08:00Z)
• Sample Complexity Characterization for Linear Contextual MDPs [67.79455646673762]
  Contextual decision processes (CMDPs) describe a class of reinforcement learning problems in which the transition kernels and reward functions can change over time with different MDPs indexed by a context variable. CMDPs serve as an important framework to model many real-world applications with time-varying environments. We study CMDPs under two linear function approximation models: Model I with context-varying representations and common linear weights for all contexts; and Model II with common representations for all contexts and context-varying linear weights.
  arXiv  Detail & Related papers  (2024-02-05T03:25:04Z)
• Robust Active Measuring under Model Uncertainty [11.087930299233278]
  Partial observability and uncertainty are common problems in sequential decision-making. We present an active-measure to solve RAM-MDPs efficiently and show that model uncertainty can, counterintuitively, let agents take fewer measurements.
  arXiv  Detail & Related papers  (2023-12-18T14:21:35Z)
• Ensemble Kalman Filtering Meets Gaussian Process SSM for Non-Mean-Field and Online Inference [47.460898983429374]
  We introduce an ensemble Kalman filter (EnKF) into the non-mean-field (NMF) variational inference framework to approximate the posterior distribution of the latent states. This novel marriage between EnKF and GPSSM not only eliminates the need for extensive parameterization in learning variational distributions, but also enables an interpretable, closed-form approximation of the evidence lower bound (ELBO) We demonstrate that the resulting EnKF-aided online algorithm embodies a principled objective function by ensuring data-fitting accuracy while incorporating model regularizations to mitigate overfitting.
  arXiv  Detail & Related papers  (2023-12-10T15:22:30Z)
• Distributionally Robust Model-based Reinforcement Learning with Large State Spaces [55.14361269378122]
  Three major challenges in reinforcement learning are the complex dynamical systems with large state spaces, the costly data acquisition processes, and the deviation of real-world dynamics from the training environment deployment. We study distributionally robust Markov decision processes with continuous state spaces under the widely used Kullback-Leibler, chi-square, and total variation uncertainty sets. We propose a model-based approach that utilizes Gaussian Processes and the maximum variance reduction algorithm to efficiently learn multi-output nominal transition dynamics.
  arXiv  Detail & Related papers  (2023-09-05T13:42:11Z)
• Latent Variable Representation for Reinforcement Learning [131.03944557979725]
  It remains unclear theoretically and empirically how latent variable models may facilitate learning, planning, and exploration to improve the sample efficiency of model-based reinforcement learning. We provide a representation view of the latent variable models for state-action value functions, which allows both tractable variational learning algorithm and effective implementation of the optimism/pessimism principle. In particular, we propose a computationally efficient planning algorithm with UCB exploration by incorporating kernel embeddings of latent variable models.
  arXiv  Detail & Related papers  (2022-12-17T00:26:31Z)
• Robust Entropy-regularized Markov Decision Processes [23.719568076996662]
  We study a robust version of the ER-MDP model, where the optimal policies are required to be robust. We show that essential properties that hold for the non-robust ER-MDP and robust unregularized MDP models also hold in our settings. We show how our framework and results can be integrated into different algorithmic schemes including value or (modified) policy.
  arXiv  Detail & Related papers  (2021-12-31T09:50:46Z)
• DEALIO: Data-Efficient Adversarial Learning for Imitation from Observation [57.358212277226315]
  In imitation learning from observation IfO, a learning agent seeks to imitate a demonstrating agent using only observations of the demonstrated behavior without access to the control signals generated by the demonstrator. Recent methods based on adversarial imitation learning have led to state-of-the-art performance on IfO problems, but they typically suffer from high sample complexity due to a reliance on data-inefficient, model-free reinforcement learning algorithms. This issue makes them impractical to deploy in real-world settings, where gathering samples can incur high costs in terms of time, energy, and risk. We propose a more data-efficient IfO algorithm
  arXiv  Detail & Related papers  (2021-03-31T23:46:32Z)

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.