mlsanityData to 7 Oct 2026

Sample Efficient Reinforcement Learning with Partial Dynamics Knowledge

arXiv 2312.12558 ↗First posted 19 Dec 2023cs.LG math.OC stat.MLcited by 4

Not on the map. Why?

Abstract (arXiv)

The problem of sample complexity of online reinforcement learning is often studied in the literature without taking into account any partial knowledge about the system dynamics that could potentially accelerate the learning process. In this paper, we study the sample complexity of online Q-learning methods when some prior knowledge about the dynamics is available or can be learned efficiently. We focus on systems that evolve according to an additive disturbance model of the form Sh+1 = f(Sh, Ah) + Wh, where f represents the underlying system dynamics, and Wh are unknown disturbances independent of states and actions. In the setting of finite episodic Markov decision processes with S states, A actions, and episode length H, we present an optimistic Q-learning algorithm that achieves tildeO(Poly(H)√T) regret under perfect knowledge of f, where T is the total number of interactions with the system. This is in contrast to the typical tildeO(Poly(H)√SAT) regret for existing Q-learning methods. Further, if only a noisy estimate hatf of f is available, our method can learn an approximately optimal policy in a number of samples that is independent of the cardinalities of state and action spaces. The sub-optimality gap depends on the approximation error hatf-f, as well as the Lipschitz constant of the corresponding optimal value function. Our approach does not require modeling of the transition probabilities and enjoys the same memory complexity as model-free methods.

Key facts. Cited by 4 papers in the map (data through 7 Oct 2026). Builds on 18 of its 28 references that are in the map. First posted on arXiv 19 Dec 2023.

Builds on

18 of 28 references.

References · 18

  1. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  2. 2020Sim-to-Real Transfer in Deep Reinforcement Learning for Robotics: a Surveycited by 388
  3. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 233
  4. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 194
  5. 2017Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learningcited by 175
  6. 2017Using Simulation and Domain Adaptation to Improve Efficiency of Deep Robotic Graspingcited by 138
  7. 2020Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisitedcited by 104
  8. 2020Fast active learning for pure exploration in reinforcement learningcited by 92
  9. 2021Online and Offline Reinforcement Learning by Planning with a Learned Modelcited by 90
  10. 2018Regret Bounds for Robust Adaptive Control of the Linear Quadratic Regulatorcited by 86
  11. 2019Provably Efficient Q-Learning with Low Switching Costcited by 77
  12. 2021Understanding Domain Randomization for Sim-to-real Transfercited by 69
6 more
  1. 2021Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learningcited by 51
  2. 2021Beyond No Regret: Instance-Dependent PAC Reinforcement Learningcited by 41
  3. 2018Q-learning with Nearest Neighborscited by 37
  4. 2020Logarithmic Regret for Learning Linear Quadratic Regulators Efficientlycited by 33
  5. 2022Sample-Efficient Reinforcement Learning with loglog(T) Switching Costcited by 32
  6. 2020Towards Robust Data-Driven Control Synthesis for Nonlinear Systems with Actuation Uncertaintycited by 13

Built on by

Cited by year (2026 to 7 Oct)

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

4 papers.

  1. 2025Analytical Survey of Learning with Low-Resource Data: From Analysis to Investigationcited by 5
  2. 2024Improving Sample Efficiency of Reinforcement Learning with Background Knowledge from Large Language Modelscited by 4
  3. 2026Minimax PAC Bounds for Learning in Exogenous Contextual MDPscited by 1
  4. 2025Perturbing the Derivative: Wild Refitting for Model-Free Evaluation of Machine Learning Models under Bregman Lossescited by 0