../

2026-10-19 Onlineopt Scribe

$\newcommand{\qq}{\quad\quad}$

Multi Objective Online Learning

We saw this through the lens of a context vector. Each time-step is tagged with a context vector which associates it with some groups.

We saw the definitions of group regret and how regular exponential weights fails to guarantee that.

We saw a small modification to the update rule

$$ q_{t+1}(i, k) = q_t(i, k)\exp(\eta C_t(k)(\langle p_t, l_t \rangle - l_t(i))) $$

ensures

$$ \text{Regret} \le O(\sqrt{T\log(NK)}) $$

We also saw how we can strengthen this to be upper bound by

$$ O(\sqrt{\left(\sum_{t}C_t(k)\right)\log(NK))} $$

A remarks is that this also applies to $C_t(k) \in [0, 1]$ instead of just $\{0, 1\}$.

Next we’ll see variations of this where the context isn’t as simple.

Swap Regret

Algorithm 1: Swap Regret Setting

For $t = 1, \ldots, T$

  1. Learner sends $p_t\in\Delta_N$
  2. Adversary decides $l$
  3. Learner samples $i_t \sim p_t$
  4. Adversary reveals $l$ to the learner

We define Internal Regret as

$$ \begin{align*} \text{Internal Regret}(i) &= \sum_{t:i_t = i} l_t(i) - \min_{j \in[N]} \sum_{t:i_t = 1} l_t(j) \\ &= \max_{j\in[N]} \sum_t^T C_t(i) (l_t(i) - l_t(j))\qq C_t(i)=\mathbb{1}[i_t = i] \end{align*} $$

We are using the actual loss instead of $\langle p_t, l_t \rangle$ as we have a concrete sample $i_t$ at every time-step.

Then, we define swap regret as

$$ \begin{align*} \text{Swap Regret}&=\sum_{i}^N \text{Internal Regret}(i) &= \sum_t^T l_t(i_t) - \min_{\phi : [N]\rightarrow[N]} \sum_t^T l_t(\phi(i_t)) \end{align*} $$ DONE