Provably Near-Optimal Distributionally Robust Reinforcement Learning in Online Settings

Debamita Ghosh, George K. Atia, Yue Wang · 2025

Read Provably Near-Optimal Distributionally Robust Reinforcement Learning in Online Settings by Debamita Ghosh, George K. Atia, Yue Wang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-03768.txt.

Introduction

Debamita Ghosh and co-authors study how to train a learning agent that still works when the real world differs from the test world. In their 2025 study, named ORVIT, the agent learns by acting in one unknown setting, with no ready-made data set and no way to rerun the world at will. The aim is a policy that holds up across a cloud of nearby settings, not just the one it trained in.

Their method is built to run fast and to keep total regret low as learning goes on, a claim the team backs with proofs. The cloud of settings is set by standard ways to measure how far apart two chance patterns sit. Past work leaned on data or world copies that real users often lack. A sound method for the leaner case widens where robust learning can be used.

Catalog record

CREATORDebamita Ghosh, George K. Atia, Yue Wang
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE147 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-03768

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Provably Near-Optimal Distributionally Robust Reinforcement Learning in Online Settings Debamita Ghosh, George K. Atia, Yue Wang Abstract Reinforcement learning (RL) faces significant challenges in real-world deployments due to the sim-to-real gap, where policies trained in simulators often underperform in practice due to mismatches between training and deployment conditions. Distributionally robust RL addresses this issue by optimizing worst-case performance over an uncertainty set of environments and providing an optimized lower bound on deployment performance. However, existing studies typically assume access to either a generative model or offline datasets with broad coverage of the deployment environment—assumptions that limit their practicality in unknown environments without prior knowledge. In this work, we study the more realistic and challenging setting of online distributionally robust RL, where the agent interacts only with a single unknown training environment while aiming to optimize its worst-case performance. We focus on general f f -divergence-based uncertainty sets, including χ 2 \chi^{2} and KL divergence balls, and propose a computationally efficient algorithm with sublinear regret guarantees under minimal assumptions. Furthermore, we establish a minimax lower bound on regret of online learning, demonstrating the near-optimality of our approach. Extensive experiments across diverse environments further confirm the robustness and efficiency of our algorithm, validating our theoretical findings. 1 Introduction Reinforcement learning (RL) is a powerful framework for solving complex decision-making problems and has achieved major success in simulation-based domains like video games silver2016mastering ; zha2021douzero ; berner2019dota ; vinyals2017starcraft and generative AI NeurIPS2022_TrainingLLM_Ouyang ; cao2023reinforcement ; black2023training ; uehara2024understanding ; zhang2024large ; du2023guiding ; cao2024survey . However, applying RL to real-world domains such as autonomous driving IEEE2021_DRLSurvey_Kiran and healthcare ACM2018_SupervisedRLRNN_Wang remains challenging. The major challenge is due to the infeasibility of direct real-world training under these environments, where RL agents are instead generally trained in simulation and then deployed in the real world. However, real-world deployments are often susceptible to environment uncertainties from, e.g., unpredictable noise, unmodeled perturbations, and even adversarial attacks, which cannot be fully captured by the training environments padakandla2020reinforcement ; rajeswaran2017epopt ; james2017transferring , resulting in the sim-to-real gap and severe performance degradation in practical deployments Sage2013_RLSurvey_Kober ; Arxiv2016_CAD2RL_Sadeghi ; IEEE2018_SimToRealTransfer_Peng ; IEEE2020_SimToRealTransferDRLRobotics_Zhao . Distributionally robust RL INFORM2005_RobusDP_Iyengar ; PMLR2017_RobustAdvRL_Pinto ; Arxiv2022_SimToRealTransferContinuousPartialObs_Hu offers a promising way to bridge the sim-to-real gap by training policies that remain reliable under environment shifts. It handles uncertainty by defining a set of plausible environments centered around the training model and then optimizing for the worst-case scenario using a pessimistic objective. This strategy ensures a guaranteed lower bound on performance when the true environment lies within the uncertainty set, while also enhancing generalization and robustness to unforeseen conditions goodfellow2014explaining ; vinitsky2020robust ; abdullah2019wasserstein ; hou2020robust ; rajeswaran2017epopt ; atkeson2003nonparametric ; morimoto2005robust ; huang2017adversarial ; kos2017delving ; lin2017tactics ; pattanaik2018robust ; mandlekar2017adversarially . Despite its extensive studies, most existing methods on distributionally robust RL cannot be directly adapted to real-world applications due to their restrictive assumptions on data collection. Most studies either rely on a generative model of the training environment PMLR2022_SampleComplexityRORL_Panaganti ; PMLR2023_ImprovedSampleComplexityDRRL_Xu ; NeuRIPS2023_CuriousPriceDRRLGenerativeMdel_Shi that can freely generate data, or assume offline datasets that comprehensively cover the unknown optimal policy NeuRIPS2023_DoublePessimismDROfflineRL_Blanchet ; JMLR2024_DROfflineRLNearOptimalSampelComplexity_Shi ; Arxiv2024_OfflineRobustRLFDivg_Tang ; NeuRIPS2024_UnifiedPessimismOfflineRL_Yue ; NeurIPS2024_MinimaxOptimalOfflineRL_Liu ; NeurIPS2022_RobustRLOffline_Panaganti ; Arxiv2024_SampleComplexityOfflineLinearDRMDP_Wang , which generally cannot be guaranteed in practice, as the practical environments are unknown and data is often sparse, and the agent needs to explore the environments by itself. This motivates the studies of distributionally robust RL with online interactions Arxiv2024_UpperLowerDRRL_Liu ; Arxiv2024_DRORLwithInteractiveData_Lu ; PMLR2024_LinearFunctionDRMDP_Liu ; ICML2025_OnlineDRMDPSampleComplexity_He , where the agent strategically explores the unknown training environment and optimizes for the worst-case performance. Due to the mismatch between the environment that generates training data (nominal), and the one used to evaluate robustness (worst-case), online distributionally robust RL is an off-target problem Arxiv2020_OffDynRL_Eysenbach ; NeurIPS2024_MinimaxOptimalOfflineRL_Liu ; holla2021off , leading to a major challenge known as the information deficit : the states covered by the worst-case or deployment environment may not be visited during training, yet the agent must still act reliably in these unfamiliar states ICML2025_OnlineDRMDPSampleComplexity_He . This lack of exposure can significantly increase the difficulties of online learning. Existing studies of online distributionally robust RL generally addresses the challenges through additional structural assumptions, e.g., existence of fail-states Arxiv2024_UpperLowerDRRL_Liu ; PMLR2024_LinearFunctionDRMDP_Liu ; Arxiv2024_DRORLwithInteractiveData_Lu . These assumptions greatly simplify the problem by making worst-case shifts predictable, effectively eliminating the information deficit and allowing efficient learning. A more recent work ICML2025_OnlineDRMDPSampleComplexity_He bypasses these structural assumptions, but relies on some coverage-type assumption. However, in realistic settings where deployment dynamics are unknown, these assumptions are impractical or hard to justify, greatly limiting the practical use of these studies. A critical question hence naturally arises: Can we develop an online distributionally robust RL algorithm with no structural assumptions and near-optimal sample-complexity? 1.1 Contributions In this paper, we answer this question by designing algorithms for online distributionally robust RL with near-optimal sample complexity, without relying on structural assumptions such as fail-states. Our major contributions are summarized as follows. • We propose an optimistic model-based meta-algorithm for online distributionally robust RL, named RVI- f , with implementations under two important uncertainty set structures: RVI- \chi^{2} and RVI- KL . These algorithms use plug-in estimates of the nominal kernel and introduce data-driven penalty terms tailored to the respective uncertainty sets. Notably, our algorithm enjoys better simplicity and more efficient implementation, compared to the ones in ICML2025_OnlineDRMDPSampleComplexity_He , which requires an additional optimization oracle. • We prove that RVI- \chi^{2} and RVI- KL are data-efficient: they achieve an \varepsilon -optimal robust policy with \tilde{\mathcal{O}}\big(H^{5}(1+\sigma)SA/\varepsilon^{2}\big) and \tilde{\mathcal{O}}\big(H^{5}\exp(2H^{2})SA/(P^{\star}_{\min}\varepsilon^{2})\big) samples, respectively. Here, P^{\star}_{\min} denotes the minimum positive entry of the nominal transition probability induced by the optimal robust policy. Our results do not require any additional assumptions, and enjoy a better complexity compared to previous work ICML2025_OnlineDRMDPSampleComplexity_He (Refer to Table 1 for details and Section 3 for relevant notation). • We further develop hard instances to derive the minimax lower bound for online distributionally robust RL, highlighting the fundamental difficulty of the problem. Our results show that for any online algorithm, there exists a hard instance requiring a sample complexity of at least \Omega\big(H^{5}(1+\sigma)SA/\varepsilon^{2}\big) and \Omega\big(H^{5}SA/(P^{\star}_{\min}\varepsilon^{2})\big) to find an \varepsilon -optimal policy under RMDP- \chi^{2} and RMDP- KL . This demonstrates the near-optimality of our algorithms, which is minimax-optimal up to logarithmic factors under \chi^{2} set, and matches the lower bound up to the dependency on H under the KL set. • We validate our methods through extensive experiments on the Gambler’s problem and Frozen Lake, demonstrating strong performance under significant distribution shifts and supporting our theoretical findings. 2 Related Work We provide a detailed discussion on other related works in this section. 2.1 Distributionally Robust Reinforcement Learning. The framework of distributionally robust MDPs are developed in INFORM2005_RobusDP_Iyengar ; INFORMS2005_RobustMDPUncertaintyTransitionMatrix_Nilim ; NeurIPS2006_RobustnessMDP_Xu ; INFORM2013_RMDP_Wiesemann ; INFORMS2016_RMDPkRectangualr_Mannor , where the uncertainty set is known and dynamic programming based planning methods are studied. These methods are later extended to learning settings where only samples from the nominal environments are available. Based on data collection pattern, existing works mainly consider two settings: the generative model setting where agents can freely generate samples under the nominal kernel AnnalsStat2022_TheoreticalUnderstandingRMDP_Yang ; PMLR2022_SampleComplexityRORL_Panaganti ; NeuRIPS2023_CuriousPriceDRRLGenerativeMdel_Shi ; INFORMS2023_DRBatchContxBandits_Si ; PMLR2023_SampleComplexityDRQLearning_Wang ; PMLR2023_ImprovedSampleComplexityDRRL_Xu ; JMLR2024_SampleComplexityVarianceReducedDRQLearning_Wang ; Arxiv2023_TowardsMinimaxOptimalityRobustRL_Clavier ; NeurIPS2021_OnlineRobustRLModelUncertainty_Wang ; wang2022policy ; wang2023model

Read the complete text