Optimal Non-Asymptotic Lower Bound on the Minimax Regret of Learning
  with Expert Advice
  We prove non-asymptotic lower bounds on the expectation of the maximum of $d$
independent Gaussian variables and the expectation of the maximum of $d$
independent symmetric random walks. Both lower bounds recover the optimal
leading constant in the limit. A simple application of the lower bound for
random walks is an (asymptotically optimal) non-asymptotic lower bound on the
minimax regret of online learning with expert advice.
