Upper and Lower Bounds for Distributionally Robust Off-Dynamics Reinforcement Learning

2024/09/30 by Zhishuai Liu, W. Wang, Liu, Zhishuai +3 · 6 citations
Computer Science · Engineering · #Artificial Intelligence (cs.AI) #Autonomous Vehicle Technology and Safety #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Reinforcement Learning in Robotics #Traffic control and management

paper · pdf · doi:10.48550/arxiv.2409.20521

openalex publication_date 2024/09/30 · openalex created_date 2024/10/28 · openalex updated_date 2026/07/28

Abstract

We study off-dynamics Reinforcement Learning (RL), where the policy training and deployment environments are different. To deal with this environmental perturbation, we focus on learning policies robust to uncertainties in transition dynamics under the framework of distributionally robust Markov decision processes (DRMDPs), where the nominal and perturbed dynamics are linear Markov Decision Processes. We propose a novel algorithm We-DRIVE-U that enjoys an average suboptimality \widetildeO(d H ⋅ min \1/ρ, H\/√(K) ), where K is the number of episodes, H is the horizon length, d is the feature dimension and ρ is the uncertainty level. This result improves the state-of-the-art by O(dH/min\1/ρ,H\). We also construct a novel hard instance and derive the first information-theoretic lower bound in this setting, which indicates our algorithm is near-optimal up to O(√(H)) for any uncertainty level ρ∈(0,1]. Our algorithm also enjoys a 'rare-switching' design, and thus only requires O(dHlog(1+H²K)) policy switches and O(d²Hlog(1+H²K)) calls for oracle to solve dual optimization problems, which significantly improves the computational efficiency of existing algorithms for DRMDPs, whose policy switch and oracle complexities are both O(K).

Cited by

• Online Robust Reinforcement Learning with General Function Approximation
• Distributionally Robust Online Markov Game with Linear Function Approximation
• Multi-Objective Reinforcement Learning with Max-Min Criterion: A Game-Theoretic Approach
• VisuoAlign: Safety Alignment of LVLMs with Multimodal Tree Search
• Rectified Robust Policy Optimization for Model-Uncertain Constrained Reinforcement Learning without Strong Duality
• ORVIT: Near-Optimal Online Distributionally Robust Reinforcement Learning

Related

• Distributionally Robust Off-Dynamics Reinforcement Learning: Provable Efficiency with Linear Function Approximation
• Distributionally Robust Model-Based Offline Reinforcement Learning with Near-Optimal Sample Complexity
• Sample Complexity of Distributionally Robust Off-Dynamics Reinforcement Learning with Online Interaction
• Achieving the Asymptotically Optimal Sample Complexity of Offline Reinforcement Learning: A DRO-Based Approach
• Minimax Optimal and Computationally Efficient Algorithms for Distributionally Robust Offline Reinforcement Learning