Inproceedings,
Improved Algorithms for Linear Stochastic Bandits (extended, corrected version)
NIPS, page 2312--2320. (December 2011)
Abstract
We improve the theoretical analysis and empirical performance of algorithms for
the stochastic multi-armed bandit problem and the linear stochastic multi-armed
bandit problem. In particular, we show that a simple modification of Auer's UCB
algorithm (Auer, 2002) achieves with high probability constant regret. More importantly,
we modify and, consequently, improve the analysis of the algorithm
for the for linear stochastic bandit problem studied by Auer (2002), Dani et al.
(2008), Rusmevichientong and Tsitsiklis (2010), Li et al. (2010). Our modification
improves the regret bound by a logarithmic factor, though experiments show
a vast improvement. In both cases, the improvement stems from the construction
of smaller confidence sets. For their construction we use a novel tail inequality for
vector-valued martingales.
