2026-10-26 Onlineopt scribe
$\newcommand{\qq}{\quad\quad}$
Recap: Swap Regret
We know that internal regret of action $i$ is
$$ \text{Internal Regret}(i) = \max_{j \in[N]} \sum_t^T C_t(i) (l_t(i_t) - l_t(j))\qq C_t(i) = \mathbb{1}[i_t = i] $$Then Swap-Regret is defined as
$$ \text{Swap Regret} = \sum_t^T l_t(i_t) - \min_{\phi: [N]\rightarrow[N]} \sum_t^T l_t (\phi(i_t)) $$We saw this being used for calibration
Recall the No-regret-robust-response dynamics
| Min player | Max player |
|---|---|
| Send $q_t\gets \text{NR}$ | |
| Pick a $p_t$ such that $p_t^T G_t q_t \le 0$ | |
NR.update($G^Tp_t$) |
Can we use this to obtain swap regret? We saw it being used for group-wise regret but what about swap?
Consider the No-Swap-Regret Learning setting with $G_t (i, (j, k)) = \mathbb{1}(l_t(i)-l_t(j))$
Then by No-Regret-Robust-Response dynamics guarantee we have
$$ \max_{j, k} \sum_{t=1}^T \mathbb{1}[i_t =k] (l_t(k) - l_t(j)) \le o(T) + o(T) $$This basically comes from the standard guarantee $\max_q\sum_t p_t^T G_t q \le 0$ and is very easy to prove.
The hard part was ensuring that $\forall q\quad \exists p\quad \forall G_t\quad p^T G_t q \le 0$
This resulted in finding a solution for $p(k) \sum_j q(j, k) = \sum_j p(j)q(k, j)$
To do so we constructed a new matrix $Q(j, k) = q(j, k) + \mathbb{1}[j = k](1 - \sum^N_i q(i, k))$
Let us deconstruct this mysterious thing
$$ Q(j, k) = \begin{cases} q(j, k)\qq\text{Non-diagonal elements}\\ q(j, k) + (1 - \text{Sum of }k^{th}\text{ column}) \end{cases} $$We are adding the residual to the diagonal elements such that each column sums up to 1. We are doing this because $\sum_{j, k} q(j, k) = 1$ i.e summing all the elements is 1 not individual rows or columns.
This new $Q$ matrix is a transition matrix similar to Markov chain transition matrices.