  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 $S_{h+1} = f(S_h, A_h) + W_h$, where $f$
represents the underlying system dynamics, and $W_h$ 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
$\tilde{\mathcal{O}}(\text{Poly}(H)\sqrt{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 $\tilde{\mathcal{O}}(\text{Poly}(H)\sqrt{SAT})$ regret
for existing Q-learning methods. Further, if only a noisy estimate $\hat{f}$ 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 $\hat{f}-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.
