2026-10-12

2026/10/12 Onlineopt Scribe

Multi-objective online learning

We have been focusing on Games in learning - where we artificially create an adversary to play a game with that corresponds to us performing better at some task. Most often the task itself isn’t online or even sequential but the online sequential version played with a adversary leads to optimal solution for the original problem.

So far in class we’ve seen algorithms that guarantee a single objective - regret. But what if we have multiple objective that we want to optimize simultaneously?

Recap of the experts problem

Theorem 1: Experts Problem

For $t = 1, \ldots T$; do

• Pick the next $p_t\in \Delta_n$
• The adversary picks a loss vector for each expert $l_t$
• The learner suffers $\langle p_t, l_t \rangle$

Online Learning with Multiple Subsequences

We’re gonna modify the above setting as

Theorem 2: Online Learning with Multiple Subsequences

for $t = 1, \ldots, T$; do

• Observer a context $C_t \in {0, 1}^K$
• Pick the next $p_t\in \Delta_n$
• The adversary picks a loss vector for each expert $l_t$
• The learner suffers $\langle p_t, l_t \rangle$

We associate each $t$ with a context $C_t$. This $C_t$ is a bit-string of length $K$, where $K$ is the number of groups we have. The basic idea is that we have some number of groups and at each timestep we observe where the timestep belongs to some group.

Example:

• $C_6 = (0, 1, 0, 1)$
• Here we have 4 groups and the timestep 6 belongs to group 2 and 4

Groupwise Regret

Now, itstead of our regular regret we have the following $$ \max_{k \in[K]} \left(\sum_{t: C_t(k) = 1} \langle p_t, l_t \rangle

• \min_{i \in [N]} \sum_{t: C_t(k) = 1} l_t(i) \right)\ = \max_{k\in[K]}\max_{i\in[N]}\sum_{t=1}^T C_t(k) \left(\langle p_t, l_t \rangle - l_t(i)\right) $$

This is very much the same formula as regret but instead of counting all the timesteps, we only count the timesteps where a certain group is active.

The overall regret is then the max regret experienced by some group.

Why won’t standard No-Regret work?

It is fairly simple to construct a pathological scenario where standard No-regret will fail to guarantee our new regret.

Consider $N = 2$ and $K = 2$

Assume we run exponential weights for $T$ rounds. We define the loss and the context as follows

• $l_t = (0, 1), C_t = (1, 0), 0 \le t \le T/2$
• $l_t = (1, 0), C_t = (0, 1), T/2 \lt t \le T$

Notice what happens until $T/2$. Expert 1 sufferes no loss and therefore $L_t(1) \lt L_t(2)$. This causes all future instances of $p_t(1) \gt p_t(2)$. Let us evaluate the group-wise regret from time $t=T/2$ until $t=T$

$$ \text{Regret} = \max_{k\in[K]}\max{i\in[N]} \sum_{t = T/2}^T \langle p_t, l_t \rangle - l_t(i)\ \text{Regret} = \sum_{t = T/2}^T p_t(1)\ \text{Regret} = \Omega(T) $$

Hence No-regret algorithms, as is, won’t suffice to give us a guarantee on group-wise regret.

Our goal in this lecture is to prove the following

Upper bound of Group-wise Regret

$$ \max_{k \in [K]}\max_{i \in [N]}\sum_t^T C_t(k) \left( \langle p_t, l_t \rangle - l_t(i) \right) \le O(\sqrt{T\log(NK))} $$

Notice that only $\log(NK)$ differs from our regular regret bound where we had $\log(N)$.

This $K$ factor can cause groups which are scarce to have very large upper bounds. Suppose a group is only active for one timestep. It could still have a very large bound due to a large $K$. So it makes sense to factor in the frequency of a group when establishing this bound.

Hence a stronger version of this can be formulated as $$ \forall k\in[K]\quad\max_{i \in [N]}\sum_t^T C_t(k) \left( \langle p_t, l_t \rangle - l_t(i) \right) \le O(\sqrt{\left(\sum_{t}C_t(k)\right)\log(NK))} $$

Recap: Best Response-No Regret dynamic

$\newcommand{\R}{\mathbb{R}}$

Suppose you have a two-player zero-sum game where the action sets are both probability distributions $p \in \Delta_n, q \in \Delta_m$ and you have a game matrix $G \in \R^{n \times m}$. The utility function of this game is defined as $$f(p, q) = p^TGq$$ and the minimax value of the game is defined as $$v^\star = \min_{p \in \Delta_n}\max_{q \in \Delta_m} p^T G q$$

Then we can find the approximate minimax value and the approximate Nash equilibrium best response using Best Response-No Regret dynamic as follows

Since the max player is running a No-Regret algorithm we have the following regret guarantee

$$ \max_q \sum_t p_t^T G q - \sum_t p_t^T G q_t \le O(\sqrt{T\log N}) $$

But we know that $p_t = \arg\min_p p^TGq_t$ and hence $$ p_t^T G q_t = \min_p p^TGq_t \le \min_p \max_q p^TGq = \text{GameValue} $$

Therefore $$ \max_q \sum_t p_t^T G q - T\times\text{GameValue} \le O(\sqrt{T\log N})\ \max_q \sum_t p_t^T G q \le T\times\text{GameValue} + O(\sqrt{T\log N})\ $$

Modified BR-NR

Instead of fixed $G$, we will now have a time varying and unknown to the learner (max player) $G$.

Learning under this circumstance is quite hopeless. Hence we relax this a bit by saying

$$ \forall q, \exists p\text{ s.t. }\forall G_t:\quad p^TG_tq\le V^\star $$ That is, for every $q$ we can find a $p$ such that the game value is upper bounded by $V^\star$ for any game matrix.

That means that there is some $q-p$ mapping that preserves this condition under all game matrices.

With this relaxation, we have our new algorithm as

min player has no knowledge of $G_t$. We just assume that there exists some $p$ that could be picked such that the upper bound is maintained.

Trivial Example

As this setting may look puzzling, let us see an concrete example and see that this can actually be realized.

$$G_t \in S^n$$ $$G_t(i, j) = l_t(i) - l_t(j)$$

Can we find a $p$ for every $q$ such that $p^TGq \le V^\star$ for any $G_t$?

$$ p_t^TG_tq_t = \sum_{i, j}p_t(i)G(i, j)q_t(j)\ = \sum_{i, j}p_t(i)q_t(j)\left(l_t(i) - l_t(j)\right)\ = \sum_{i, j}p_t(i)q_t(j)l_t(i) - p_t(i)q_t(j)l_t(j) $$