Kulkarni, Sanjeev R.; Lugosi, Gábor - Department of Economics and Business, Universitat … - 1997
We obtain minimax lower bounds on the regret for the classical two--armed bandit problem. We provide a finite--sample minimax version of the well--known log $n$ asymptotic lower bound of Lai and Robbins. Also, in contrast to the log $n$ asymptotic results on the regret, we show that the minimax...