Optimal Non-Asymptotic Lower Bound on the Minimax Regret of Learning with Expert Advice

Understand

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.