  Recently, several studies (Zhou et al., 2021a; Zhang et al., 2021b; Kim et
al., 2021; Zhou and Gu, 2022) have provided variance-dependent regret bounds
for linear contextual bandits, which interpolates the regret for the worst-case
regime and the deterministic reward regime. However, these algorithms are
either computationally intractable or unable to handle unknown variance of the
noise. In this paper, we present a novel solution to this open problem by
proposing the first computationally efficient algorithm for linear bandits with
heteroscedastic noise. Our algorithm is adaptive to the unknown variance of
noise and achieves an $\tilde{O}(d \sqrt{\sum_{k = 1}^K \sigma_k^2} + d)$
regret, where $\sigma_k^2$ is the variance of the noise at the round $k$, $d$
is the dimension of the contexts and $K$ is the total number of rounds. Our
results are based on an adaptive variance-aware confidence set enabled by a new
Freedman-type concentration inequality for self-normalized martingales and a
multi-layer structure to stratify the context vectors into different layers
with different uniform upper bounds on the uncertainty.
  Furthermore, our approach can be extended to linear mixture Markov decision
processes (MDPs) in reinforcement learning. We propose a variance-adaptive
algorithm for linear mixture MDPs, which achieves a problem-dependent
horizon-free regret bound that can gracefully reduce to a nearly constant
regret for deterministic MDPs. Unlike existing nearly minimax optimal
algorithms for linear mixture MDPs, our algorithm does not require explicit
variance estimation of the transitional probabilities or the use of high-order
moment estimators to attain horizon-free regret. We believe the techniques
developed in this paper can have independent value for general online decision
making problems.
