mlsanityData to 7 Oct 2026

Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensembles

arXiv 1910.10597 ↗First posted 23 Oct 2019cs.LG cs.AI stat.MLcited by 100

Not on the map. Why?

Abstract (arXiv)

Reinforcement learning (RL) methods have been shown to be capable of learning intelligent behavior in rich domains. However, this has largely been done in simulated domains without adequate focus on the process of building the simulator. In this paper, we consider a setting where we have access to an ensemble of pre-trained and possibly inaccurate simulators (models). We approximate the real environment using a state-dependent linear combination of the ensemble, where the coefficients are determined by the given state features and some unknown parameters. Our proposed algorithm provably learns a near-optimal policy with a sample complexity polynomial in the number of unknown parameters, and incurs no dependence on the size of the state (or action) space. As an extension, we also consider the more challenging problem of model selection, where the state features are unknown and can be chosen from a large candidate set. We provide exponential lower bounds that illustrate the fundamental hardness of this problem, and develop a provably efficient algorithm under additional natural assumptions.

Key facts. Cited by 100 papers in the map (data through 7 Oct 2026). First posted on arXiv 23 Oct 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 25; 2022: 26; 2023: 25; 2024: 12; 2025: 5; 2026: 7.

100 papers.

Sort:

By area:

  1. 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 176
  2. 2021Pessimistic Model-based Offline Reinforcement Learning under Partial Coveragecited by 160
  3. 2021Model-free Representation Learning and Exploration in Low-rank MDPscited by 82
  4. 2022Denoised MDPs: Learning World Models Better Than the World Itselfcited by 66
  5. 2022Near-optimal Offline Reinforcement Learning with Linear Representation: Leveraging Variance Information with Pessimismcited by 63
  6. 2022Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processescited by 57
  7. 2022Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPscited by 52
  8. 2022Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processescited by 49
  9. 2021Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDPcited by 45
  10. 2021An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gapcited by 40
  11. 2023Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiencycited by 39
  12. 2022Provable Benefits of Representational Transfer in Reinforcement Learningcited by 38
38 more
  1. 2022Offline Reinforcement Learning Under Value and Density-Ratio Realizability: The Power of Gapscited by 34
  2. 2021Proper Value Equivalencecited by 33
  3. 2021Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvaturecited by 32
  4. 2022On the Complexity of Adversarial Decision Makingcited by 32
  5. 2022Model-based RL with Optimistic Posterior Sampling: Structural Conditions and Sample Complexitycited by 31
  6. 2022Distributionally Robust Offline Reinforcement Learning with Linear Function Approximationcited by 31
  7. 2022A General Framework for Sample-Efficient Function Approximation in Reinforcement Learningcited by 31
  8. 2022Nearly Minimax Optimal Reinforcement Learning with Linear Function Approximationcited by 30
  9. 2021Reward-Free Model-Based Reinforcement Learning with Linear Function Approximationcited by 29
  10. 2023Tight Guarantees for Interactive Decision Making with the Decision-Estimation Coefficientcited by 29
  11. 2021Near-optimal Policy Optimization Algorithms for Learning Adversarial Linear Mixture MDPscited by 28
  12. 2021Provable RL with Exogenous Distractors via Multistep Inverse Dynamicscited by 28
  13. 2023A Theoretical Analysis of Optimistic Proximal Policy Optimization in Linear Markov Decision Processescited by 28
  14. 2022On the Statistical Efficiency of Reward-Free Exploration in Non-Linear RLcited by 27
  15. 2021Almost Optimal Algorithms for Two-player Zero-Sum Linear Mixture Markov Gamescited by 25
  16. 2024Distributionally Robust Off-Dynamics Reinforcement Learning: Provable Efficiency with Linear Function Approximationcited by 25
  17. 2021Learning Stochastic Shortest Path with Linear Function Approximationcited by 23
  18. 2023Maximize to Explore: One Objective Function Fusing Estimation, Planning, and Explorationcited by 20
  19. 2021Nearly Minimax Optimal Regret for Learning Infinite-horizon Average-reward MDPs with Linear Function Approximationcited by 18
  20. 2021Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs with a Generative Modelcited by 18
  21. 2021On Query-efficient Planning in MDPs under Linear Realizability of the Optimal State-value Functioncited by 17
  22. 2023On the Convergence and Sample Complexity Analysis of Deep Q-Networks with ε-Greedy Explorationcited by 17
  23. 2025Robust LLM Alignment via Distributionally Robust Direct Preference Optimizationcited by 17
  24. 2021Optimistic Policy Optimization is Provably Efficient in Non-stationary MDPscited by 16
  25. 2022Understanding the Complexity Gains of Single-Task RL with a Curriculumcited by 16
  26. 2023Improved Regret for Efficient Online Reinforcement Learning with Linear Function Approximationcited by 16
  27. 2024Upper and Lower Bounds for Distributionally Robust Off-Dynamics Reinforcement Learningcited by 15
  28. 2021Uniform-PAC Bounds for Reinforcement Learning with Linear Function Approximationcited by 14
  29. 2021PC-MLP: Model-based Reinforcement Learning with Policy Cover Guided Explorationcited by 14
  30. 2023Rate-Optimal Policy Optimization for Linear Markov Decision Processescited by 14
  31. 2023A Nearly Optimal and Low-Switching Algorithm for Reinforcement Learning with General Function Approximationcited by 14
  32. 2021Agnostic Reinforcement Learning with Low-Rank MDPs and Rich Observationscited by 13
  33. 2021Near-Optimal Reward-Free Exploration for Linear Mixture MDPs with Plug-in Solvercited by 13
  34. 2021Locally Differentially Private Reinforcement Learning for Linear Mixture Markov Decision Processescited by 13
  35. 2022Oracle Inequalities for Model Selection in Offline Reinforcement Learningcited by 13
  36. 2022Model-Based Reinforcement Learning with Multinomial Logistic Function Approximationcited by 13
  37. 2023On the Statistical Efficiency of Mean-Field Reinforcement Learning with General Function Approximationcited by 13
  38. 2023Tackling Heavy-Tailed Rewards in Reinforcement Learning with Function Approximation: Minimax Optimal and Instance-Dependent Regret Boundscited by 13

50 most cited of 100 All 100 (JSON)