Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPs

2022/05/23 by Dongruo Zhou, Quanquan Gu, Zhou, Dongruo +1 · 7 citations
Computer Science · Decision Sciences · Engineering · #Advanced Bandit Algorithms Research #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Control (math.OC) #Reinforcement Learning in Robotics #Smart Grid Energy Management

paper · pdf · doi:10.48550/arxiv.2205.11507

openalex publication_date 2022/05/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Recent studies have shown that episodic reinforcement learning (RL) is not more difficult than contextual bandits, even with a long planning horizon and unknown state transitions. However, these results are limited to either tabular Markov decision processes (MDPs) or computationally inefficient algorithms for linear mixture MDPs. In this paper, we propose the first computationally efficient horizon-free algorithm for linear mixture MDPs, which achieves the optimal O(d√(K) +d²) regret up to logarithmic factors. Our algorithm adapts a weighted least square estimator for the unknown transitional dynamic, where the weight is both variance-aware and uncertainty-aware. When applying our weighted least square estimator to heterogeneous linear bandits, we can obtain an O(d√∑_k=1^K σ_k² +d) regret in the first K rounds, where d is the dimension of the context and σ_k² is the variance of the reward in the k-th round. This also improves upon the best-known algorithms in this setting when σ_k²'s are known.

Cited by

• Breaking the Total Variance Barrier: Sharp Sample Complexity for Linear Heteroscedastic Bandits with Fixed Action Set
• Vector-valued self-normalized concentration inequalities beyond sub-Gaussianity
• Variance-Aware Feel-Good Thompson Sampling for Contextual Bandits
• Instance-Dependent Continuous-Time Reinforcement Learning via Maximum Likelihood Estimation
• Second-Order Bounds for [0,1]-Valued Regression via Betting Loss
• Neural Variance-aware Dueling Bandits with Deep Representation and Shallow Exploration
• Adaptive Resolving Methods for Reinforcement Learning with Function Approximations

Related

• Horizon-free Reinforcement Learning in Adversarial Linear Mixture MDPs
• Optimal Horizon-Free Reward-Free Exploration for Linear Mixture MDPs
• Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiency
• Near-optimal Policy Optimization Algorithms for Learning Adversarial Linear Mixture MDPs
• Improved Algorithm for Adversarial Linear Mixture MDPs with Bandit Feedback and Unknown Transition