Improved Regret Analysis for Variance-Adaptive Linear Bandits and
  Horizon-Free Linear Mixture MDPs
  In online learning problems, exploiting low variance plays an important role
in obtaining tight performance guarantees yet is challenging because variances
are often not known a priori. Recently, considerable progress has been made by
Zhang et al. (2021) where they obtain a variance-adaptive regret bound for
linear bandits without knowledge of the variances and a horizon-free regret
bound for linear mixture Markov decision processes (MDPs). In this paper, we
present novel analyses that improve their regret bounds significantly. For
linear bandits, we achieve $\tilde O(d^{1.5}\sqrt{\sum_{k}^K \sigma_k^2} +
d^2)$ where $d$ is the dimension of the features, $K$ is the time horizon, and
$\sigma_k^2$ is the noise variance at time step $k$, and $\tilde O$ ignores
polylogarithmic dependence, which is a factor of $d^3$ improvement. For linear
mixture MDPs with the assumption of maximum cumulative reward in an episode
being in $[0,1]$, we achieve a horizon-free regret bound of $\tilde O(d
\sqrt{K} + d^2)$ where $d$ is the number of base models and $K$ is the number
of episodes. This is a factor of $d^{3.5}$ improvement in the leading term and
$d^7$ in the lower order term. Our analysis critically relies on a novel
elliptical potential `count' lemma. This lemma allows a novel regret analysis
in conjunction with the peeling trick, which is of independent interest.
