# Lower bounds on regret

In "regret" styled analysis over $T$ steps of an iterative algorithm $\{x_i \in F \}_{i=1}^T$ (where $F$ is some feasible set) being given the sequence of loss functions $\{ f_i\}_{i=1}^T$ one defines the regret $R_T = \sum_{i=1}^Tf_t(x_i) - \min_{x \in F} \sum_{i=1}^T f_t(x)$ Most typical analyses assume that the $f$s are convex.

Is this notion of "regret" lower bounded? Or under what conditions is it lower bounded?

I guess "minimizing the regret" does not make sense because one can always have an "Oracle" access to the sequence of points $x^*_i$ such that $x^*_i = \min_{x \in F} f_i(x)$. Then for this sequence for $x^*$ points the regret is only at most $0$.

• There are lower bounds on regret that show that the classical algorithms cannot be improved. The lower bounds give an adversary which can force any algorithm to have a certain amount of regret. – Yuval Filmus Feb 17 '18 at 14:24
• Thanks! Can you kindly link to the reference? And this lower bound is $0$? – gradstudent Feb 17 '18 at 18:59
• The lower bound is certainly not 0. There are better lower bounds. – Yuval Filmus Feb 17 '18 at 23:06

• Thanks! So in general I know of papers which in the context of such algorithms try to prove that the average regret i.e $\frac{R_T}{T}$is asymptotically $0$. What could be the motivation of trying to prove this particular limit? (...given that what the lower bound is seems to depend on the model and the distribution and other things as you say..) – gradstudent Feb 18 '18 at 5:28
• But what about my "oracle" based argument that $R_T$ can always be made at most $0$? If that is correct then why is average regret asymptotically going to $0$ (no matter how fats) even a good thing? Shouldnt one be targetting to get regret as negative? (because that is clearly possible for the oracle) – gradstudent Feb 18 '18 at 8:47