A General Theory of the Stochastic Linear Bandit and Its Applications
  Recent growing adoption of experimentation in practice has led to a surge of
attention to multiarmed bandits as a technique to reduce the opportunity cost
of online experiments. In this setting, a decision-maker sequentially chooses
among a set of given actions, observes their noisy rewards, and aims to
maximize her cumulative expected reward (or minimize regret) over a horizon of
length $T$. In this paper, we introduce a general analysis framework and a
family of algorithms for the stochastic linear bandit problem that includes
well-known algorithms such as the
optimism-in-the-face-of-uncertainty-linear-bandit (OFUL) and Thompson sampling
(TS) as special cases. Our analysis technique bridges several streams of prior
literature and yields a number of new results. First, our new notion of
optimism in expectation gives rise to a new algorithm, called sieved greedy
(SG) that reduces the overexploration problem in OFUL. SG utilizes the data to
discard actions with relatively low uncertainty and then choosing one among the
remaining actions greedily. In addition to proving that SG is theoretically
rate optimal, our empirical simulations show that SG outperforms existing
benchmarks such as greedy, OFUL, and TS. The second application of our general
framework is (to the best of our knowledge) the first polylogarithmic (in $T$)
regret bounds for OFUL and TS, under similar conditions as the ones by
Goldenshluger and Zeevi (2013). Finally, we obtain sharper regret bounds for
the $k$-armed contextual MABs by a factor of $\sqrt{k}$.
