# Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPs

arXiv: https://arxiv.org/abs/2205.11507 · HTML: https://mlsanity.com/paper/2205.11507/

## Key facts

- Cited by 52 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 51 references that are in the map.
- First posted on arXiv 23 May 2022.

## Builds on (most cited first, 30 of 32)

- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [Contextual Decision Processes with Low Bellman Rank are PAC-Learnable](https://mlsanity.com/paper/1610.09512/) (2016)
- [Model-Based Reinforcement Learning with Value-Targeted Regression](https://mlsanity.com/paper/2006.01107/) (2020)
- [Provably Efficient Exploration in Policy Optimization](https://mlsanity.com/paper/1912.05830/) (2019)
- [Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound](https://mlsanity.com/paper/1905.10389/) (2019)
- [Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes](https://mlsanity.com/paper/2012.08507/) (2020)
- [Learning Near Optimal Policies with Low Inherent Bellman Error](https://mlsanity.com/paper/2003.00153/) (2020)
- [Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?](https://mlsanity.com/paper/1910.03016/) (2019)
- [Optimism in Reinforcement Learning with Generalized Linear Function Approximation](https://mlsanity.com/paper/1912.04136/) (2019)
- [Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2005.12900/) (2020)
- [Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mapping](https://mlsanity.com/paper/2006.13165/) (2020)
- [Frequentist Regret Bounds for Randomized Least-Squares Value Iteration](https://mlsanity.com/paper/1911.00567/) (2019)
- [Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensembles](https://mlsanity.com/paper/1910.10597/) (2019)
- [Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizon](https://mlsanity.com/paper/2009.13503/) (2020)
- [Logarithmic Regret for Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2011.11566/) (2020)
- [Information Directed Sampling and Bandits with Heteroscedastic Noise](https://mlsanity.com/paper/1801.09667/) (2018)
- [On Oracle-Efficient PAC RL with Rich Observations](https://mlsanity.com/paper/1803.00606/) (2018)
- [Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functions](https://mlsanity.com/paper/2010.01374/) (2020)
- [Nearly Minimax-Optimal Regret for Linearly Parameterized Bandits](https://mlsanity.com/paper/1904.00242/) (2019)
- [Nearly Optimal Algorithms for Linear Contextual Bandits with Adversarial Corruptions](https://mlsanity.com/paper/2205.06811/) (2022)
- [Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDP](https://mlsanity.com/paper/2101.12745/) (2021)
- [Improved Regret Analysis for Variance-Adaptive Linear Bandits and Horizon-Free Linear Mixture MDPs](https://mlsanity.com/paper/2111.03289/) (2021)
- [Nearly Horizon-Free Offline Reinforcement Learning](https://mlsanity.com/paper/2103.14077/) (2021)
- [Is Long Horizon Reinforcement Learning More Difficult Than Short Horizon Reinforcement Learning?](https://mlsanity.com/paper/2005.00527/) (2020)
- [Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regret](https://mlsanity.com/paper/2104.11186/) (2021)
- [Reward-Free Model-Based Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2110.06394/) (2021)
- [Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity](https://mlsanity.com/paper/2006.03864/) (2020)
- [Horizon-Free Reinforcement Learning in Polynomial Time: the Power of Stationary Policies](https://mlsanity.com/paper/2203.12922/) (2022)
- [Nearly Minimax Optimal Reward-free Reinforcement Learning](https://mlsanity.com/paper/2010.05901/) (2020)

## Built on by (most cited first, 30 of 52)

- [Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processes](https://mlsanity.com/paper/2212.06132/) (2022)
- [Reinforcement Learning from Human Feedback with Active Queries](https://mlsanity.com/paper/2402.09401/) (2024)
- [Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiency](https://mlsanity.com/paper/2302.10371/) (2023)
- [Corruption-Robust Offline Reinforcement Learning with General Function Approximation](https://mlsanity.com/paper/2310.14550/) (2023)
- [A Theoretical Analysis of Optimistic Proximal Policy Optimization in Linear Markov Decision Processes](https://mlsanity.com/paper/2305.08841/) (2023)
- [Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits](https://mlsanity.com/paper/2310.00968/) (2023)
- [A Near-Optimal Algorithm for Safe Reinforcement Learning Under Instantaneous Hard Constraints](https://mlsanity.com/paper/2302.04375/) (2023)
- [Upper and Lower Bounds for Distributionally Robust Off-Dynamics Reinforcement Learning](https://mlsanity.com/paper/2409.20521/) (2024)
- [Improved Regret Analysis in Gaussian Process Bandits: Optimality for Noiseless Reward, RKHS norm, and Non-Stationary Variance](https://mlsanity.com/paper/2502.06363/) (2025)
- [Tackling Heavy-Tailed Rewards in Reinforcement Learning with Function Approximation: Minimax Optimal and Instance-Dependent Regret Bounds](https://mlsanity.com/paper/2306.06836/) (2023)
- [A Nearly Optimal and Low-Switching Algorithm for Reinforcement Learning with General Function Approximation](https://mlsanity.com/paper/2311.15238/) (2023)
- [Model-based RL as a Minimalist Approach to Horizon-Free and Second-Order Bounds](https://mlsanity.com/paper/2408.08994/) (2024)
- [Cooperative Multi-Agent Reinforcement Learning: Asynchronous Communication and Linear Function Approximation](https://mlsanity.com/paper/2305.06446/) (2023)
- [Variance-aware robust reinforcement learning with linear function approximation under heavy-tailed rewards](https://mlsanity.com/paper/2303.05606/) (2023)
- [Optimal Horizon-Free Reward-Free Exploration for Linear Mixture MDPs](https://mlsanity.com/paper/2303.10165/) (2023)
- [On the Model-Misspecification in Reinforcement Learning](https://mlsanity.com/paper/2306.10694/) (2023)
- [Randomized Exploration for Reinforcement Learning with Multinomial Logistic Function Approximation](https://mlsanity.com/paper/2405.20165/) (2024)
- [Replicable Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2509.08660/) (2025)
- [Delay-Adapted Policy Optimization and Improved Regret for Adversarial MDP with Delayed Bandit Feedback](https://mlsanity.com/paper/2305.07911/) (2023)
- [Noise-Adaptive Confidence Sets for Linear Bandits and Application to Bayesian Optimization](https://mlsanity.com/paper/2402.07341/) (2024)
- [Horizon-Free Regret for Linear Markov Decision Processes](https://mlsanity.com/paper/2403.10738/) (2024)
- [Sample-efficient Learning of Infinite-horizon Average-reward MDPs with General Function Approximation](https://mlsanity.com/paper/2404.12648/) (2024)
- [Hybrid Reinforcement Learning Breaks Sample Size Barriers in Linear MDPs](https://mlsanity.com/paper/2408.04526/) (2024)
- [Warm-up Free Policy Optimization: Improved Regret in Linear Markov Decision Processes](https://mlsanity.com/paper/2407.03065/) (2024)
- [Near-Optimal Regret for KL-Regularized Multi-Armed Bandits](https://mlsanity.com/paper/2603.02155/) (2026)
- [Horizon-Free and Variance-Dependent Reinforcement Learning for Latent Markov Decision Processes](https://mlsanity.com/paper/2210.11604/) (2022)
- [Horizon-free Reinforcement Learning in Adversarial Linear Mixture MDPs](https://mlsanity.com/paper/2305.08359/) (2023)
- [Learning Adversarial Low-rank Markov Decision Processes with Unknown Transition and Full-information Feedback](https://mlsanity.com/paper/2311.07876/) (2023)
- [Horizon-Free and Instance-Dependent Regret Bounds for Reinforcement Learning with General Function Approximation](https://mlsanity.com/paper/2312.04464/) (2023)
- [Variance-Dependent Regret Lower Bounds for Contextual Bandits](https://mlsanity.com/paper/2503.12020/) (2025)

## Abstract (arXiv)

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 tilde O(d√K +d2) 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 tilde O(d√sumk=1K σk2 +d) regret in the first K rounds, where d is the dimension of the context and σk2 is the variance of the reward in the k-th round. This also improves upon the best-known algorithms in this setting when σk2's are known.