Sample Complexity of Variance-reduced Distributionally Robust Q-learning

2023/05/28 by Shengbo Wang, Nian Si, Wang, Shengbo +5 · 6 citations
Computer Science · #Reinforcement Learning in Robotics

paper · pdf · doi:10.48550/arxiv.2305.18420

Abstract

Dynamic decision-making under distributional shifts is of fundamental interest in theory and applications of reinforcement learning: The distribution of the environment in which the data is collected can differ from that of the environment in which the model is deployed. This paper presents two novel model-free algorithms, namely the distributionally robust Q-learning and its variance-reduced counterpart, that can effectively learn a robust policy despite distributional shifts. These algorithms are designed to efficiently approximate the q-function of an infinite-horizon γ-discounted robust Markov decision process with Kullback-Leibler ambiguity set to an entry-wise ε-degree of precision. Further, the variance-reduced distributionally robust Q-learning combines the synchronous Q-learning with variance-reduction techniques to enhance its performance. Consequently, we establish that it attains a minimax sample complexity upper bound of O(|S||A|(1-γ)^-4ε^-2), where S and A denote the state and action spaces. This is the first complexity result that is independent of the ambiguity size δ, thereby providing new complexity theoretic insights. Additionally, a series of numerical experiments confirm the theoretical findings and the efficiency of the algorithms in handling distributional shifts.

Cited by

• Online Robust Reinforcement Learning with General Function Approximation
• Distributionally Robust Self Paced Curriculum Reinforcement Learning
• Primal-Only Actor Critic Algorithm for Robust Constrained Average Cost MDPs
• OEUVRE: OnlinE Unbiased Variance-Reduced loss Estimation
• Robust Reinforcement Learning in Finance: Modeling Market Impact with Elliptic Uncertainty Sets
• ORVIT: Near-Optimal Online Distributionally Robust Reinforcement Learning

Related

• A Finite Sample Complexity Bound for Distributionally Robust Q-learning
• Robust Q-learning Algorithm for Markov Decision Processes under Wasserstein Uncertainty
• Variance-Reduced Cascade Q-learning: Algorithms and Sample Complexity
• Q-Learning with Shift-Aware Upper Confidence Bound in Non-Stationary Reinforcement Learning
• Q-learning with Uniformly Bounded Variance: Large Discounting is Not a Barrier to Fast Learning