Lower bounds on regret
There are many different models in which regret minimization makes sense. One particular model is Gaussian density estimation. Takimoto and Warmuth, in their paper The minimax strategy for Gaussian density estimation, give a tight analysis which includes both an upper bound achieved by a particular algorithm and an almost matching lower bound proved using the adversary method. There are probably many more such analyses out there.