Learning in Markov Decision Processes with Exogenous Dynamics

• URL: http://arxiv.org/abs/2603.02862v2
• Date: Wed, 04 Mar 2026 14:42:12 GMT
• Title: Learning in Markov Decision Processes with Exogenous Dynamics
• Authors: Davide Maran, Davide Salaorni, Marcello Restelli,
• Abstract summary: We study a structured class of MDPs characterized by state components whose transitions are independent of the agent's actions.<n>We show that exploiting this structure yields significantly improved learning guarantees.<n>We empirically validate our approach across classical toy settings and real-world-inspired environments.
• Score: 39.6376520918509
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Reinforcement learning algorithms are typically designed for generic Markov Decision Processes (MDPs), where any state-action pair can lead to an arbitrary transition distribution. In many practical systems, however, only a subset of the state variables is directly influenced by the agent's actions, while the remaining components evolve according to exogenous dynamics and account for most of the stochasticity. In this work, we study a structured class of MDPs characterized by exogenous state components whose transitions are independent of the agent's actions. We show that exploiting this structure yields significantly improved learning guarantees, with only the size of the exogenous state space appearing in the leading terms of the regret bounds. We further establish a matching lower bound, showing that this dependence is information-theoretically optimal. Finally, we empirically validate our approach across classical toy settings and real-world-inspired environments, demonstrating substantial gains in sample efficiency compared to standard reinforcement learning methods.

Related papers

• Sample Complexity of Distributionally Robust Off-Dynamics Reinforcement Learning with Online Interaction [11.339580074756187]
  Off-dynamics reinforcement learning (RL) can be formulated as learning in a robust Markov decision process (RMDP)<n>We study a more realistic and challenging setting where the agent is limited to online interaction with the training environment.
  arXiv  Detail & Related papers  (2025-11-07T16:24:22Z)
• Unified modality separation: A vision-language framework for unsupervised domain adaptation [60.8391821117794]
  Unsupervised domain adaptation (UDA) enables models trained on a labeled source domain to handle new unlabeled domains.<n>We propose a unified modality separation framework that accommodates both modality-specific and modality-invariant components.<n>Our methods achieve up to 9% performance gain with 9 times of computational efficiencies.
  arXiv  Detail & Related papers  (2025-08-07T02:51:10Z)
• Structured Agent Distillation for Large Language Model [56.38279355868093]
  We propose Structured Agent Distillation, a framework that compresses large LLM-based agents into smaller student models.<n>Our method segments trajectories into [REASON] and [ACT] spans, applying segment-specific losses to align each component with the teacher's behavior.<n>Experiments on ALFWorld, HotPotQA-ReAct, and WebShop show that our approach consistently outperforms token-level and imitation learning baselines.
  arXiv  Detail & Related papers  (2025-05-20T02:01:55Z)
• FlickerFusion: Intra-trajectory Domain Generalizing Multi-Agent RL [19.236153474365747]
  Existing MARL approaches often rely on the restrictive assumption that the number of entities remains constant between training and inference.<n>In this paper, we tackle the challenge of intra-trajectory dynamic entity composition under zero-shot out-of-domain (OOD) generalization.<n>We propose FlickerFusion, a novel OOD generalization method that acts as a universally applicable augmentation technique for MARL backbone methods.
  arXiv  Detail & Related papers  (2024-10-21T10:57:45Z)
• STAT: Towards Generalizable Temporal Action Localization [56.634561073746056]
  Weakly-supervised temporal action localization (WTAL) aims to recognize and localize action instances with only video-level labels. Existing methods suffer from severe performance degradation when transferring to different distributions. We propose GTAL, which focuses on improving the generalizability of action localization methods.
  arXiv  Detail & Related papers  (2024-04-20T07:56:21Z)
• Hierarchical Decision Making Based on Structural Information Principles [19.82391136775341]
  We propose a novel Structural Information principles-based framework, namely SIDM, for hierarchical Decision Making.<n>We present an abstraction mechanism that processes historical state-action trajectories to construct abstract representations of states and actions.<n>We develop a skill-based learning method for single-agent scenarios and a role-based collaboration method for multi-agent scenarios, both of which can flexibly integrate various underlying algorithms for enhanced performance.
  arXiv  Detail & Related papers  (2024-04-15T13:02:00Z)
• 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)

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.