Regularization and Variance-Weighted Regression Achieves Minimax
  Optimality in Linear MDPs: Theory and Practice
Toshinori Kitamura Tadashi Kozuno Yunhao Tang Nino Vieillard Michal Valko Wenhao Yang Jincheng Mei Pierre Ménard Mohammad Gheshlaghi Azar Rémi Munos Olivier Pietquin Matthieu Geist Csaba Szepesvári Wataru Kumagai Yutaka Matsuo
Mirror descent value iteration (MDVI), an abstraction of Kullback-Leibler
(KL) and entropy-regularized reinforcement learning (RL), has served as the
basis for recent high-performing practical RL algorithms. However, despite the
use of function approximation in practice, the theoretical understanding of
MDVI has been limited to tabular Markov decision processes (MDPs). We study
MDVI with linear function approximation through its sample complexity required
to identify an $\varepsilon$-optimal policy with probability $1-\delta$ under
the settings of an infinite-horizon linear MDP, generative model, and G-optimal
design. We demonstrate that least-squares regression weighted by the variance
of an estimated optimal value function of the next state is crucial to
achieving minimax optimality. Based on this observation, we present
Variance-Weighted Least-Squares MDVI (VWLS-MDVI), the first theoretical
algorithm that achieves nearly minimax optimal sample complexity for
infinite-horizon linear MDPs. Furthermore, we propose a practical VWLS
algorithm for value-based deep RL, Deep Variance Weighting (DVW). Our
experiments demonstrate that DVW improves the performance of popular
value-based deep RL algorithms on a set of MinAtar benchmarks.