# Sample Efficient Reinforcement Learning with Partial Dynamics Knowledge

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

## Key facts

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

## Builds on (most cited first, 18 of 18)

- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Sim-to-Real Transfer in Deep Reinforcement Learning for Robotics: a Survey](https://mlsanity.com/paper/2009.13303/) (2020)
- [Model-Based Reinforcement Learning with Value-Targeted Regression](https://mlsanity.com/paper/2006.01107/) (2020)
- [Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds](https://mlsanity.com/paper/1901.00210/) (2019)
- [Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning](https://mlsanity.com/paper/1703.07710/) (2017)
- [Using Simulation and Domain Adaptation to Improve Efficiency of Deep Robotic Grasping](https://mlsanity.com/paper/1709.07857/) (2017)
- [Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisited](https://mlsanity.com/paper/2010.03531/) (2020)
- [Fast active learning for pure exploration in reinforcement learning](https://mlsanity.com/paper/2007.13442/) (2020)
- [Online and Offline Reinforcement Learning by Planning with a Learned Model](https://mlsanity.com/paper/2104.06294/) (2021)
- [Regret Bounds for Robust Adaptive Control of the Linear Quadratic Regulator](https://mlsanity.com/paper/1805.09388/) (2018)
- [Understanding Domain Randomization for Sim-to-real Transfer](https://mlsanity.com/paper/2110.03239/) (2021)
- [Provably Efficient Q-Learning with Low Switching Cost](https://mlsanity.com/paper/1905.12849/) (2019)
- [Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning](https://mlsanity.com/paper/2110.04645/) (2021)
- [Beyond No Regret: Instance-Dependent PAC Reinforcement Learning](https://mlsanity.com/paper/2108.02717/) (2021)
- [Q-learning with Nearest Neighbors](https://mlsanity.com/paper/1802.03900/) (2018)
- [Logarithmic Regret for Learning Linear Quadratic Regulators Efficiently](https://mlsanity.com/paper/2002.08095/) (2020)
- [Sample-Efficient Reinforcement Learning with loglog(T) Switching Cost](https://mlsanity.com/paper/2202.06385/) (2022)
- [Towards Robust Data-Driven Control Synthesis for Nonlinear Systems with Actuation Uncertainty](https://mlsanity.com/paper/2011.10730/) (2020)

## Built on by (most cited first, 4 of 4)

- [Analytical Survey of Learning with Low-Resource Data: From Analysis to Investigation](https://mlsanity.com/paper/2510.08962/) (2025)
- [Improving Sample Efficiency of Reinforcement Learning with Background Knowledge from Large Language Models](https://mlsanity.com/paper/2407.03964/) (2024)
- [Minimax PAC Bounds for Learning in Exogenous Contextual MDPs](https://mlsanity.com/paper/2606.25170/) (2026)
- [Perturbing the Derivative: Wild Refitting for Model-Free Evaluation of Machine Learning Models under Bregman Losses](https://mlsanity.com/paper/2509.02476/) (2025)

## 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.