\begin{thebibliography}{14}
\expandafter\ifx\csname natexlab\endcsname\relax\def\natexlab#1{#1}\fi
\expandafter\ifx\csname url\endcsname\relax
  \def\url#1{{\tt #1}}\fi

\bibitem[Anthony and Bartlett(1999)]{anthony_bartlett99}
M.~Anthony and P.~L. Bartlett.
\newblock {\em Neural Network Learning: Theoretical Foundations}.
\newblock Cambridge University Press, 1999.

\bibitem[Auer et~al.(2002{\natexlab{a}})Auer, Cesa-Bianchi, and
  Fischer]{AuerCesaBianchiFischer02}
P.~Auer, N.~Cesa-Bianchi, and P.~Fischer.
\newblock Finite-time analysis of the multiarmed bandit problem.
\newblock {\em Machine Learning}, 47:\penalty0 235--256, 2002{\natexlab{a}}.

\bibitem[Auer et~al.(1995)Auer, {Cesa-Bianchi}, Freund, and Schapire]{A95}
P.~Auer, N.~{Cesa-Bianchi}, Y.~Freund, and R.~E. Schapire.
\newblock Gambling in a rigged casino: The adversarial multi-armed bandit
  problem.
\newblock In {\em {Proc. 36th Annual Symposium on Foundations of Computer
  Science}}, pages 322--331. IEEE Computer Society Press, 1995.

\bibitem[Auer et~al.(2002{\natexlab{b}})Auer, {Cesa-Bianchi}, Freund, and
  Schapire]{ACFS02}
P.~Auer, N.~{Cesa-Bianchi}, Y.~Freund, and R.~E. Schapire.
\newblock The non-stochastic multi-armed bandit problem.
\newblock {\em SIAM Journal on Computing}, 32:\penalty0 48--77,
  2002{\natexlab{b}}.

\bibitem[Berry and Fristedt(1985)]{BF85}
D.A. Berry and B.~Fristedt.
\newblock {\em Bandit Problems}.
\newblock Chapman and Hall, 1985.

\bibitem[Chernoff(1972)]{Chernoff72}
H.~Chernoff.
\newblock {\em Sequential Analysis and Optimal Design}.
\newblock Society for Industrial \& Applied Mathematics, 1972.

\bibitem[{Even-Dar} et~al.(2002){Even-Dar}, Mannor, and Mansour]{EDMM02}
E.~{Even-Dar}, S.~Mannor, and Y.~Mansour.
\newblock {PAC} bounds for multi-armed bandit and {M}arkov decision processes.
\newblock In J.~Kivinen and R.~H. Sloan, editors, {\em {Fifteenth Annual
  Conference on Computational Learning Theory}}, pages 255--270. Springer,
  2002.

\bibitem[Jennison et~al.(1982)Jennison, Johnstone, and Turnbull]{JJT82}
C.~Jennison, I.~M. Johnstone, and B.~W. Turnbull.
\newblock Asymptotically optimal procedures for sequential adaptive selection
  of the best of several normal means.
\newblock In S.~S. Gupta and J.~Berger, editors, {\em Statistical decision
  theory and related topics {III}}, volume~3, pages 55--86. Academic Press,
  1982.

\bibitem[Kulkarni and Lugosi(2000)]{KulkarniLugosi00}
S.~R. Kulkarni and G.~Lugosi.
\newblock Finite-time lower bounds for the two-armed bandit problem.
\newblock {\em {IEEE} Trans. Aut. Control}, 45\penalty0 (4):\penalty0 711--714,
  2000.

\bibitem[Lai and Robbins(1985)]{LR85}
T.~L. Lai and H.~Robbins.
\newblock Asymptotically efficient adaptive allocation rules.
\newblock {\em Advances in Applied Mathematics}, 6:\penalty0 4--22, 1985.

\bibitem[Mannor and Tsitsiklis(2003)]{MT03}
S.~Mannor and J.N. Tsitsiklis.
\newblock Lower bounds on the sample complexity of exploration in the
  multi-armed bandit problem.
\newblock In B.~Sch$\rm\ddot{o}$lkopf and M.~K. Warmuth, editors, {\em
  {Sixteenth Annual Conference on Computational Learning Theory}}, pages
  418--432. Springer, 2003.

\bibitem[Robbins(1952)]{R52}
H.~Robbins.
\newblock Some aspects of sequential design of experiments.
\newblock {\em Bulletin of the American Mathematical Society}, 55:\penalty0
  527--535, 1952.

\bibitem[Ross(1983)]{Ross}
S.~M. Ross.
\newblock {\em Stochastic Processes}.
\newblock Wiley, 1983.

\bibitem[Siegmund(1985)]{siegmund85}
D.~Siegmund.
\newblock {\em Sequential analysis: Tests and Confidence Intervals}.
\newblock Springer Verlag, 1985.

\end{thebibliography}
