Doubly robust Thompson sampling for linear payoffs
  A challenging aspect of the bandit problem is that a stochastic reward is
observed only for the chosen arm and the rewards of other arms remain missing.
The dependence of the arm choice on the past context and reward pairs compounds
the complexity of regret analysis. We propose a novel multi-armed contextual
bandit algorithm called Doubly Robust (DR) Thompson Sampling employing the
doubly-robust estimator used in missing data literature to Thompson Sampling
with contexts (\texttt{LinTS}). Different from previous works relying on
missing data techniques (\citet{dimakopoulou2019balanced},
\citet{kim2019doubly}), the proposed algorithm is designed to allow a novel
additive regret decomposition leading to an improved regret bound with the
order of $\tilde{O}(\phi^{-2}\sqrt{T})$, where $\phi^2$ is the minimum
eigenvalue of the covariance matrix of contexts. This is the first regret bound
of \texttt{LinTS} using $\phi^2$ without the dimension of the context, $d$.
Applying the relationship between $\phi^2$ and $d$, the regret bound of the
proposed algorithm is $\tilde{O}(d\sqrt{T})$ in many practical scenarios,
improving the bound of \texttt{LinTS} by a factor of $\sqrt{d}$. A benefit of
the proposed method is that it utilizes all the context data, chosen or not
chosen, thus allowing to circumvent the technical definition of unsaturated
arms used in theoretical analysis of \texttt{LinTS}. Empirical studies show the
advantage of the proposed algorithm over \texttt{LinTS}.
