# Does this $\max$ mean that we need to maximize the regret in this regret formula?

I found that the regret in Online Machine Learning is stated as:

$$\operatorname{Regret}_{T}(h)=\sum_{t=1}^{T} l\left(p_{t}, y_{t}\right)-\sum_{t=1}^{T} l\left(h(x), y_{t}\right),$$

where $$p_t$$ is the answer of my algorithm to the question $$x$$ and $$y_t$$ is the right answer, while $$h()$$ is one of the hypotheses in the hypothesis space. Intuitively, as denoted in the paper, our objective is to minimize this Regret in order to optimize our algorithm, but in the following formula

$$\operatorname{Regret}_{T}(\mathcal{H})=\max _{h^{\star} \in \mathcal{H}} \operatorname{Regret}_{T}\left(h^{\star}\right)$$

they maximize this value. Am I interpreting the $$max$$ wrongly?

Yes, you're interpreting the $$\max$$ there wrongly. In your second formula

$$\operatorname{Regret}_{T}(\mathcal{H})=\max _{h^{\star} \in \mathcal{H}} \operatorname{Regret}_{T}\left(h^{\star}\right) \label{1}\tag{1}$$

The sign $$=$$ means "is defined as", so maybe the following notation is less confusing

$$\operatorname{Regret}_{T}(\mathcal{H}) \triangleq \max _{h^{\star} \in \mathcal{H}} \operatorname{Regret}_{T}\left(h^{\star}\right)$$

In fact, in section 2.1 of the same paper, there's a similar but more detailed formula that should clarify the meaning of $$\max$$ $$\operatorname{Regret}_{T}(\mathcal{H})=\max _{h \in \mathcal{H}}\left(\sum_{t=1}^{T}\left|p_{t}-y_{t}\right|-\sum_{t=1}^{T}\left|h\left(\mathbf{x}_{t}\right)-y_{t}\right|\right)$$

Note that $$\operatorname{Regret}_{T}(\mathcal{H})$$ is defined for $$\mathcal{H}$$, while your first formula is defined for $$x$$. So, \ref{1} is the regret for the whole hypotheses class $$\mathcal{H}$$, which is thus the maximum regret that you can have across all possible hypotheses $$h \in \mathcal{H}$$. This should make sense.

• I corrected the argument of my first formula, it was h not x. Anyway thank you, I thought was "is defined as" but I was not sure Jul 29 '20 at 7:36
• @FraMan But note that you had taken a screenshot of the formula and it was $x$ because I used a program to convert the screenshot to the latex formula.
– nbro
Jul 29 '20 at 12:34
• I wrote the Latex formula wrong and then I uploaded a screenshot of that formula because I'm stupid :) Jul 29 '20 at 13:18
• @FraMan Haah, don't worry, man :)
– nbro
Jul 29 '20 at 13:41