Stabilizing Q-learning with Linear Architectures for Provably Efficient Learning
The $Q$-learning algorithm is a simple and widely-used stochastic
approximation scheme for reinforcement learning, but the basic protocol can
exhibit instability in conjunction with function approximation. Such
instability can be observed even with linear function approximation. In
practice, tools such as target networks and experience replay appear to be
essential, but the individual contribution of each of these mechanisms is not
well understood theoretically. This work proposes an exploration variant of the
basic $Q$-learning protocol with linear function approximation. Our modular
analysis illustrates the role played by each algorithmic tool that we adopt: a
second order update rule, a set of target networks, and a mechanism akin to
experience replay. Together, they enable state of the art regret bounds on
linear MDPs while preserving the most prominent feature of the algorithm,
namely a space complexity independent of the number of step elapsed. We show
that the performance of the algorithm degrades very gracefully under a novel
and more permissive notion of approximation error. The algorithm also exhibits
a form of instance-dependence, in that its performance depends on the
"effective" feature dimension.