Sample Complexity of Distributionally Robust Off-Dynamics Reinforcement Learning with Online Interaction

• URL: http://arxiv.org/abs/2511.05396v1
• Date: Fri, 07 Nov 2025 16:24:22 GMT
• Title: Sample Complexity of Distributionally Robust Off-Dynamics Reinforcement Learning with Online Interaction
• Authors: Yiting He, Zhishuai Liu, Weixin Wang, Pan Xu,
• Abstract summary: 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.
• Score: 11.339580074756187
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Off-dynamics reinforcement learning (RL), where training and deployment transition dynamics are different, can be formulated as learning in a robust Markov decision process (RMDP) where uncertainties in transition dynamics are imposed. Existing literature mostly assumes access to generative models allowing arbitrary state-action queries or pre-collected datasets with a good state coverage of the deployment environment, bypassing the challenge of exploration. In this work, we study a more realistic and challenging setting where the agent is limited to online interaction with the training environment. To capture the intrinsic difficulty of exploration in online RMDPs, we introduce the supremal visitation ratio, a novel quantity that measures the mismatch between the training dynamics and the deployment dynamics. We show that if this ratio is unbounded, online learning becomes exponentially hard. We propose the first computationally efficient algorithm that achieves sublinear regret in online RMDPs with $f$-divergence based transition uncertainties. We also establish matching regret lower bounds, demonstrating that our algorithm achieves optimal dependence on both the supremal visitation ratio and the number of interaction episodes. Finally, we validate our theoretical results through comprehensive numerical experiments.

Related papers

• Learning Optimal and Sample-Efficient Decision Policies with Guarantees [3.096615629099617]
  This thesis addresses the problem of learning from offline datasets in the presence of hidden confounders.<n>We derive a sample-efficient algorithm for solving conditional moment restrictions problems with convergence and optimality guarantees.<n>We also develop an algorithm that can learn effective imitator policies with convergence rate guarantees.
  arXiv  Detail & Related papers  (2026-02-20T04:24:49Z)
• Sample-Efficient Neurosymbolic Deep Reinforcement Learning [49.60927398960061]
  We propose a neuro-symbolic Deep RL approach that integrates background symbolic knowledge to improve sample efficiency.<n>Online reasoning is performed to guide the training process through two mechanisms.<n>We show improved performance over a state-of-the-art reward machine baseline.
  arXiv  Detail & Related papers  (2026-01-06T09:28:53Z)
• Balance Equation-based Distributionally Robust Offline Imitation Learning [8.607736795429638]
  Imitation Learning (IL) has proven highly effective for robotic and control tasks where manually designing reward functions or explicit controllers is infeasible.<n>Standard IL methods implicitly assume that the environment dynamics remain fixed between training and deployment.<n>We address this challenge through Balance Equation-based Distributionally Robust Offline Learning.<n>We formulate the problem as a distributionally robust optimization over an uncertainty set of transition models, seeking a policy that minimizes the imitation loss under the worst-case transition distribution.
  arXiv  Detail & Related papers  (2025-11-11T07:48:09Z)
• See, Think, Act: Online Shopper Behavior Simulation with VLM Agents [58.92444959954643]
  This paper investigates the integration of visual information, specifically webpage screenshots, into behavior simulation via VLMs.<n>We employ SFT for joint action prediction and rationale generation, conditioning on the full interaction context.<n>To further enhance reasoning capabilities, we integrate RL with a hierarchical reward structure, scaled by a difficulty-aware factor.
  arXiv  Detail & Related papers  (2025-10-22T05:07:14Z)
• Counterfactual experience augmented off-policy reinforcement learning [9.77739016575541]
  CEA builds efficient inference model and enhances representativeness of learning data.<n>Uses variational autoencoders to model the dynamic patterns of state transitions.<n>Builds a complete counterfactual experience to alleviate the out-of-distribution problem of the learning data.
  arXiv  Detail & Related papers  (2025-03-18T02:32:50Z)
• In-Context Linear Regression Demystified: Training Dynamics and Mechanistic Interpretability of Multi-Head Softmax Attention [52.159541540613915]
  We study how multi-head softmax attention models are trained to perform in-context learning on linear data.<n>Our results reveal that in-context learning ability emerges from the trained transformer as an aggregated effect of its architecture and the underlying data distribution.
  arXiv  Detail & Related papers  (2025-03-17T02:00:49Z)
• Scalable Offline Reinforcement Learning for Mean Field Games [6.8267158622784745]
  Off-MMD is a novel mean-field RL algorithm that approximates equilibrium policies in mean-field games using purely offline data. Our algorithm scales to complex environments and demonstrates strong performance on benchmark tasks like crowd exploration or navigation.
  arXiv  Detail & Related papers  (2024-10-23T14:16:34Z)
• Dynamic Environment Responsive Online Meta-Learning with Fairness Awareness [30.44174123736964]
  We introduce an innovative adaptive fairness-aware online meta-learning algorithm, referred to as FairSAOML. Our experimental evaluation on various real-world datasets in dynamic environments demonstrates that our proposed FairSAOML algorithm consistently outperforms alternative approaches.
  arXiv  Detail & Related papers  (2024-02-19T17:44:35Z)
• 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)
• Conditional Kernel Imitation Learning for Continuous State Environments [9.750698192309978]
  We introduce a novel conditional kernel density estimation-based imitation learning framework. We show consistently superior empirical performance over many state-of-the-art IL algorithms.
  arXiv  Detail & Related papers  (2023-08-24T05:26:42Z)
• Smoothed Online Learning for Prediction in Piecewise Affine Systems [43.64498536409903]
  This paper builds on the recently developed smoothed online learning framework. It provides the first algorithms for prediction and simulation in piecewise affine systems.
  arXiv  Detail & Related papers  (2023-01-26T15:54:14Z)
• 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 Inverse Reinforcement Learning under Transition Dynamics Mismatch [60.23815709215807]
  We study the inverse reinforcement learning (IRL) problem under a transition dynamics mismatch between the expert and the learner. We propose a robust MCE IRL algorithm, which is a principled approach to help with this mismatch.
  arXiv  Detail & Related papers  (2020-07-02T14:57:13Z)

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.