Instance-optimality in optimal value estimation: Adaptivity via variance-reduced Q-learning
This provides a precise way to distinguish easy from hard problems in Q-learning, addressing instance-specific variability not captured by worst-case bounds.
The paper tackles the problem of estimating optimal Q-value functions in reinforcement learning by identifying an instance-dependent functional that controls estimation difficulty, and shows that a variance-reduced Q-learning algorithm achieves accuracy matching lower bounds up to logarithmic factors.
Various algorithms in reinforcement learning exhibit dramatic variability in their convergence rates and ultimate accuracy as a function of the problem structure. Such instance-specific behavior is not captured by existing global minimax bounds, which are worst-case in nature. We analyze the problem of estimating optimal $Q$-value functions for a discounted Markov decision process with discrete states and actions and identify an instance-dependent functional that controls the difficulty of estimation in the $\ell_\infty$-norm. Using a local minimax framework, we show that this functional arises in lower bounds on the accuracy on any estimation procedure. In the other direction, we establish the sharpness of our lower bounds, up to factors logarithmic in the state and action spaces, by analyzing a variance-reduced version of $Q$-learning. Our theory provides a precise way of distinguishing "easy" problems from "hard" ones in the context of $Q$-learning, as illustrated by an ensemble with a continuum of difficulty.