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.

本文提出一个本地极小极大方法，分析了计算强化学习下的最优 $Q$ 值函数的实例特定行为，并提供一个针对 $Q$ 学习中困难问题和易解问题的有力解释。