mlsanityData to 14 Oct 2026

Replicable Reinforcement Learning with Linear Function Approximation

arXiv 2509.08660 ↗First posted 10 Sep 2025cs.LGcited by 7

On the map: Deep reinforcement learning methods → RL theory and sample complexity

Abstract (arXiv)

Replication of experimental results has been a challenge faced by many scientific disciplines, including the field of machine learning. Recent work on the theory of machine learning has formalized replicability as the demand that an algorithm produce identical outcomes when executed twice on different samples from the same distribution. Provably replicable algorithms are especially interesting for reinforcement learning (RL), where algorithms are known to be unstable in practice. While replicable algorithms exist for tabular RL settings, extending these guarantees to more practical function approximation settings has remained an open problem. In this work, we make progress by developing replicable methods for linear function approximation in RL. We first introduce two efficient algorithms for replicable random design regression and uncentered covariance estimation, each of independent interest. We then leverage these tools to provide the first provably efficient replicable RL algorithms for linear Markov decision processes in both the generative model and episodic settings. Finally, we evaluate our algorithms experimentally and show how they can inspire more consistent neural policies.

Key facts. Cited by 7 papers in the map (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 51 of its 81 references that are in the map. First posted on arXiv 10 Sep 2025.

Builds on

51 of 81 references.

References · 51

  1. 2017Curiosity-driven Exploration by Self-supervised Predictioncited by 1,194
  2. 2017Deep Reinforcement Learning that Matterscited by 754
  3. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
  4. 2017Robust Adversarial Reinforcement Learningcited by 451
  5. 2020Improving Reproducibility in Machine Learning Research (A Report from the NeurIPS 2019 Reproducibility Program)cited by 322
  6. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 292
  7. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 234
  8. 2020FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPscited by 233
  9. 2019Provably Efficient Exploration in Policy Optimizationcited by 205
  10. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 200
  11. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 181
  12. 2018Deep Reinforcement Learning and the Deadly Triadcited by 174
38 more
  1. 2016A vector-contraction inequality for Rademacher complexitiescited by 142
  2. 2019Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?cited by 140
  3. 2019Optimism in Reinforcement Learning with Generalized Linear Function Approximationcited by 111
  4. 2020Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mappingcited by 102
  5. 2019Frequentist Regret Bounds for Randomized Least-Squares Value Iterationcited by 101
  6. 2019Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensemblescited by 100
  7. 2017Reproducibility of Benchmarked Deep Reinforcement Learning Tasks for Continuous Controlcited by 93
  8. 2021d3rlpy: An Offline Deep Reinforcement Learning Librarycited by 84
  9. 2021Model-free Representation Learning and Exploration in Low-rank MDPscited by 82
  10. 2020Logarithmic Regret for Reinforcement Learning with Linear Function Approximationcited by 79
  11. 2024Simplifying Deep Temporal Difference Learningcited by 78
  12. 2018On Oracle-Efficient PAC RL with Rich Observationscited by 71
  13. 2022Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processescited by 57
  14. 2022Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPscited by 52
  15. 2022Making Linear MDPs Practical via Contrastive Representation Learningcited by 52
  16. 2019Measuring the Reliability of Reinforcement Learning Algorithmscited by 51
  17. 2022Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processescited by 49
  18. 2022Reproducibility in Learningcited by 44
  19. 2023Stability is Stable: Connections between Replicability, Privacy, and Adaptive Generalizationcited by 42
  20. 2018Uniform Convergence of Gradients for Non-Convex Learning and Optimizationcited by 38
  21. 2021Is High Variance Unavoidable in RL? A Case Study in Continuous Controlcited by 28
  22. 2022The Phenomenon of Policy Churncited by 28
  23. 2022Replicable Banditscited by 22
  24. 2022Reproducibility in Optimization: Theoretical Framework and Limitscited by 21
  25. 2023Replicable Reinforcement Learningcited by 21
  26. 2023Replicability in Reinforcement Learningcited by 21
  27. 2024MAD-TD: Model-Augmented Data stabilizes High Update Ratio RLcited by 16
  28. 2021Near-Optimal Reward-Free Exploration for Linear Mixture MDPs with Plug-in Solvercited by 14
  29. 2024Replicable Learning of Large-Margin Halfspacescited by 12
  30. 2019Let's Play Again: Variability of Deep Reinforcement Learning Agents in Atari Environmentscited by 11
  31. 2024Replicability in High Dimensional Statisticscited by 8
  32. 2023Optimal Horizon-Free Reward-Free Exploration for Linear Mixture MDPscited by 7
  33. 2024On the Computational Landscape of Replicable Learningcited by 7
  34. 2024Can we hop in general? A discussion of benchmark selection and design using the Hopper environmentcited by 7
  35. 2024Replicable Online Learningcited by 7
  36. 2024Replicable Uniformity Testingcited by 4
  37. 2025The Role of Randomness in Stabilitycited by 4
  38. 2025From Generative to Episodic: Sample-Efficient Replicable Reinforcement Learningcited by 4

50 most cited of 51 All 51 (JSON)

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 7.

7 papers.

  1. 2026Model Agreement via Anchoringcited by 1
  2. 2026Behavior-Consistent Deep Reinforcement Learningcited by 1
  3. 2026Is Pure Exploitation Sufficient in Exogenous MDPs with Linear Function Approximation?cited by 0
  4. 2026Computationally Efficient Replicable Learning of Parities and Applicationscited by 0
  5. 2026Replicable Compositioncited by 0
  6. 2026Replicable Conformal Predictioncited by 0
  7. 2026When Do Models Admit They Are Wrong? Failure Disclosure Is Unstable Under Reinforcement Learningcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2025List Replicable Reinforcement Learning
  2. 2022On Practical Reinforcement Learning: Provable Robustness, Scalability, and Statistical Efficiency
  3. 2024Hybrid Reinforcement Learning Breaks Sample Size Barriers in Linear MDPs
  4. 2025Near-Optimal Sample Complexity in Reward-Free Kernel-Based Reinforcement Learning
  5. 2025Statistical and Algorithmic Foundations of Reinforcement Learning
  6. 2023Making RL with Preference-based Feedback Efficient via Randomization
  7. 2026Frozen Policy Iteration: Computationally Efficient RL under Linear Qπ Realizability for Deterministic Dynamics
  8. 2026Reinforcement Learning with Function Approximation for Non-Markov Processes