The multi-armed bandit is a fundamental sequential decision problem. Since the Fifties it has been studied extensively in various communities, and in the last ten years there has been a surge of interest for this problem in the machine learning community. I will present new results for this problem that go beyond the seminal work of Lai and Robbins. In particular I will give (i) a finite time...