  In this paper, we address the stochastic contextual linear bandit problem,
where a decision maker is provided a context (a random set of actions drawn
from a distribution). The expected reward of each action is specified by the
inner product of the action and an unknown parameter. The goal is to design an
algorithm that learns to play as close as possible to the unknown optimal
policy after a number of action plays. This problem is considered more
challenging than the linear bandit problem, which can be viewed as a contextual
bandit problem with a \emph{fixed} context. Surprisingly, in this paper, we
show that the stochastic contextual problem can be solved as if it is a linear
bandit problem. In particular, we establish a novel reduction framework that
converts every stochastic contextual linear bandit instance to a linear bandit
instance, when the context distribution is known. When the context distribution
is unknown, we establish an algorithm that reduces the stochastic contextual
instance to a sequence of linear bandit instances with small misspecifications
and achieves nearly the same worst-case regret bound as the algorithm that
solves the misspecified linear bandit instances.
  As a consequence, our results imply a $O(d\sqrt{T\log T})$ high-probability
regret bound for contextual linear bandits, making progress in resolving an
open problem in (Li et al., 2019), (Li et al., 2021).
  Our reduction framework opens up a new way to approach stochastic contextual
linear bandit problems, and enables improved regret bounds in a number of
instances including the batch setting, contextual bandits with
misspecifications, contextual bandits with sparse unknown parameters, and
contextual bandits with adversarial corruption.
