Definition 3 (Mean-Based Learning Algorithm, [1]}). Let
\(\sigma _{i,t} = \sum _{t^{\prime }=1}^t u_{i,t^{\prime }}\), where \(u_{i,t}\) is utility of action \(i\)  at time \(t\) .
An algorithm for the
experts problem or multi-armed bandits problem is \(\gamma \) -mean-based if it is the case that whenever
\(\sigma _{i,t} < \sigma _{j,t} - \gamma (T) T\), then the probability that the algorithm pulls arm \(i\)  on round \(t\)  is at most \(\gamma \) . We say an algorithm is mean-based if it is \(\gamma \) -mean-based for some \(\gamma (T) = o(1)\) .

