Remark 1 (Tightness of the simple regret bound) In standard MAB problems without contexts, there is a well known lower bound on expected simple regret that is of the order of \(\sigma \sqrt{k/T}\) . This matches the upper bound in Corollary REF , up to logarithmic factors, even in problems with contexts. The lower bound follows by the same argument used to prove Theorem 3.5 in [1]}. That argument considers a difficult instance where \(k-1\)  arms offer mean reward of 1/2, and a randomly chosen optimal arm has mean \(1/2 + c\cdot \sigma \cdot \sqrt{k/T}\) . When \(c\)  is a small constant, it is impossible for an algorithm to detect which arm is best.
