mlsanityData to 7 Oct 2026

Optimal Horizon-Free Reward-Free Exploration for Linear Mixture MDPs

arXiv 2303.10165 ↗First posted 17 Mar 2023cs.LG math.OC stat.MLcited by 7

Not on the map. Why?

Abstract (arXiv)

We study reward-free reinforcement learning (RL) with linear function approximation, where the agent works in two phases: (1) in the exploration phase, the agent interacts with the environment but cannot access the reward; and (2) in the planning phase, the agent is given a reward function and is expected to find a near-optimal policy based on samples collected in the exploration phase. The sample complexities of existing reward-free algorithms have a polynomial dependence on the planning horizon, which makes them intractable for long planning horizon RL problems. In this paper, we propose a new reward-free algorithm for learning linear mixture Markov decision processes (MDPs), where the transition probability can be parameterized as a linear combination of known feature mappings. At the core of our algorithm is uncertainty-weighted value-targeted regression with exploration-driven pseudo-reward and a high-order moment estimator for the aleatoric and epistemic uncertainties. When the total reward is bounded by 1, we show that our algorithm only needs to explore tilde O( d2varepsilon-2) episodes to find an varepsilon-optimal policy, where d is the dimension of the feature mapping. The sample complexity of our algorithm only has a polylogarithmic dependence on the planning horizon and therefore is "horizon-free". In addition, we provide an Omega(d2varepsilon-2) sample complexity lower bound, which matches the sample complexity of our algorithm up to logarithmic factors, suggesting that our algorithm is optimal.

Key facts. Cited by 7 papers in the map (data through 7 Oct 2026). Builds on 41 of its 46 references that are in the map. First posted on arXiv 17 Mar 2023.

Builds on

41 of 46 references.

References · 41

  1. 2017What Uncertainties Do We Need in Bayesian Deep Learning for Computer Vision?cited by 2,335
  2. 2017Constrained Policy Optimizationcited by 928
  3. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  4. 2018Reward Constrained Policy Optimizationcited by 397
  5. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
  6. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 233
  7. 2019Provably Efficient Exploration in Policy Optimizationcited by 203
  8. 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 199
  9. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 199
  10. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 180
  11. 2020Reward-Free Exploration for Reinforcement Learningcited by 177
  12. 2019Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?cited by 140
29 more
  1. 2019Optimism in Reinforcement Learning with Generalized Linear Function Approximationcited by 111
  2. 2020Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mappingcited by 102
  3. 2019Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensemblescited by 100
  4. 2019Frequentist Regret Bounds for Randomized Least-Squares Value Iterationcited by 100
  5. 2020Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizoncited by 99
  6. 2020Fast active learning for pure exploration in reinforcement learningcited by 92
  7. 2020On Reward-Free Reinforcement Learning with Linear Function Approximationcited by 89
  8. 2020Logarithmic Regret for Reinforcement Learning with Linear Function Approximationcited by 79
  9. 2020Adaptive Reward-Free Explorationcited by 77
  10. 2018On Oracle-Efficient PAC RL with Rich Observationscited by 71
  11. 2020Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functionscited by 71
  12. 2019Reinforcement Learning with Convex Constraintscited by 57
  13. 2022Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processescited by 57
  14. 2020Provably Efficient Reward-Agnostic Navigation with Linear Value Iterationcited by 56
  15. 2022Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPscited by 52
  16. 2022Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processescited by 49
  17. 2021Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDPcited by 45
  18. 2022VOQL: Towards Optimal Regret in Model-free RL with Nonlinear Function Approximationcited by 44
  19. 2021Nearly Horizon-Free Offline Reinforcement Learningcited by 36
  20. 2020Is Long Horizon Reinforcement Learning More Difficult Than Short Horizon Reinforcement Learning?cited by 34
  21. 2021Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regretcited by 34
  22. 2021Reward-Free Model-Based Reinforcement Learning with Linear Function Approximationcited by 29
  23. 2020Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexitycited by 28
  24. 2022Horizon-Free Reinforcement Learning in Polynomial Time: the Power of Stationary Policiescited by 27
  25. 2020Nearly Minimax Optimal Reward-free Reinforcement Learningcited by 26
  26. 2022Sample Efficient Deep Reinforcement Learning via Uncertainty Estimationcited by 26
  27. 2022Towards Deployment-Efficient Reinforcement Learning: Lower Bound and Optimalitycited by 24
  28. 2021Settling the Horizon-Dependence of Sample Complexity in Reinforcement Learningcited by 17
  29. 2021Near-Optimal Reward-Free Exploration for Linear Mixture MDPs with Plug-in Solvercited by 13

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 1; 2024: 3; 2025: 2; 2026: 1.

7 papers.

  1. 2024Traversing Pareto Optimal Policies: Provably Efficient Multi-Objective Reinforcement Learningcited by 13
  2. 2024Model-based RL as a Minimalist Approach to Horizon-Free and Second-Order Boundscited by 11
  3. 2023On the Model-Misspecification in Reinforcement Learningcited by 7
  4. 2025Replicable Reinforcement Learning with Linear Function Approximationcited by 6
  5. 2024Uncertainty-Aware Reward-Free Exploration with General Function Approximationcited by 5
  6. 2025Rate optimal learning of equilibria from datacited by 2
  7. 2026Provably Efficient Federated Reinforcement Learning with Linear Function Approximation and Logarithmic Communication Costcited by 0