Learning, Regret Minimization, and Equilibria

Motivation: deciding repeatedly under uncertainty

Many situations involve repeatedly making decisions in an uncertain environment: which route to drive to work each day, or repeated play of a game against an opponent whose strategy is unknown.

The basic setting: a space of $N$ actions — the routes, or the rows of a matrix game like $\{\text{rock}, \text{paper}, \text{scissors}\}$ . At each time step the algorithm probabilistically chooses an action, the environment makes its “move” (setting the day’s road congestion), and the algorithm incurs the loss for the action it chose. Then the process repeats.

We want two things: adaptive algorithms that perform well in such settings, and an understanding of the dynamics when many players are all adjusting simultaneously.

IntuitionWhat “regret” means, and why it is the right question

Imagine we design a sophisticated online algorithm, sell it to a client, and it runs for a while incurring some loss. We want to avoid the embarrassment of the client returning to say that in retrospect a much lower loss was available under his simple alternative policy $\pi$ . The regret of our algorithm is the difference between its loss and the loss under $\pi$ .

Different notions of regret differ in what counts as a “simple” alternative. That single choice organizes the whole chapter.

Notion	Alternative policy it competes against
External regret (combining expert advice)	The best single action in retrospect — the alternative plays the same action at every step
Internal regret	Modify the online sequence by replacing every occurrence of one action $i$ by another action $j$
Swap regret	Modify by any map $\{1,\ldots,N\}\to\{1,\ldots,N\}$ — up to a factor $N$ larger than internal regret

ImportantWhy each matters

External regret provides a general methodology for making an online algorithm match an optimal static offline algorithm, by modelling the possible static solutions as actions. In machine learning it yields performance comparable to the best prediction rule from a large hypothesis class.

Swap regret matters because of its tight connection to correlated equilibrium: one way to think of a correlated equilibrium is as a distribution $Q$ over the joint action space such that every player would have zero internal (or swap) regret when playing it.

Model and preliminaries

DefinitionThe online model

An adversarial online model with $N$ actions $X = \{1,\ldots,N\}$ . At each step $t$ the algorithm $H$ selects a distribution $p^t$ over actions; then the adversary selects a loss vector $\ell^t \in [0,1]^N$ .

Full information model: $H$ receives all of $\ell^t$ and suffers $\ell^t_H = \sum_{i=1}^N p_i^t\ell_i^t$ — the expected loss of drawing $i \sim p^t$ .
Partial information (bandit) model: $H$ receives only $(\ell^t_{k^t}, k^t)$ with $k^t \sim p^t$ , and suffers $\ell^t_H = \ell^t_{k^t}$ .

Cumulative losses: $L_i^T = \sum_{t=1}^T \ell_i^t$ and $L_H^T = \sum_{t=1}^T\ell_H^t$ .

DefinitionExternal regret

Given a comparison class $G$ of algorithms, the external regret is $R_G = L_H^T - L_{G,\min}^T$ where $L^T_{G,\min} = \min_{g\in G}L^T_g$ . We take $G = X$ , the single actions, so with $L^T_{\min} = \min_i L^T_i$ ,

$R = L_H^T - L^T_{\min}$

DefinitionModification rules and general regret

A modification rule $F$ takes the history and the currently selected action and outputs a (possibly different) action; $F^t$ denotes it at time $t$ . Given the algorithm’s distributions $p^t$ , it induces

$f^t = F^t(p^t), \qquad f_i^t = \sum_{j\,:\,F^t(j) = i} p_j^t, \qquad L_{H,F} = \sum_t\sum_i f_i^t\ell_i^t$

— at time $t$ , $F$ shifts the probability $H$ assigned to $j$ over to $F^t(j)$ , so the modified distribution depends on $p^t$ . For a finite set $\mathcal F$ of memoryless rules,

$R_{\mathcal F} = \max_{F\in\mathcal F}\big(L_H^T - L^T_{H,F}\big)$

FormulaThe three regrets as classes of modification rules

External: $\mathcal F^{ex}$ has $N$ rules $F_i$ , each always outputting $i$ .
Internal: $\mathcal F^{in}$ has $N(N-1)$ rules $F_{i,j}$ with $F_{i,j}(i) = j$ and $F_{i,j}(i') = i'$ otherwise, giving $\max_{i,j\in X}\ \sum_{t=1}^T p_i^t\big(\ell_i^t - \ell_j^t\big)$
Swap: $\mathcal F^{sw}$ has all $N^N$ functions, giving $\sum_{i=1}^N\ \max_{j\in X}\ \sum_{t=1}^T p_i^t\big(\ell_i^t - \ell_j^t\big)$

Since $\mathcal F^{ex}\subseteq\mathcal F^{sw}$ and $\mathcal F^{in}\subseteq\mathcal F^{sw}$ , swap regret upper-bounds both.

IntuitionInternal versus swap, concretely

Internal regret answers “every time you bought IBM, you should have bought Microsoft instead” — one substitution. Swap regret allows all actions to be remapped simultaneously, and is at most a factor $N$ larger.

External regret minimization

Why the comparison class must be restricted

TheoremNo algorithm can compete with the best sequence

Let $G_{\text{all}}$ be all functions from times $\{1,\ldots,T\}$ to actions. For any online algorithm $H$ there is a loss sequence with $R_{G_{\text{all}}} \ge T(1 - 1/N)$ .

ProofPunish the action the algorithm is least likely to play

At each $t$ , give loss 0 to the action $i^t$ of lowest probability $p^t_{i^t}$ and loss 1 to all others. Since $\min_i p_i^t \le 1/N$ , the algorithm’s loss is at least $T(1-1/N)$ . Meanwhile $g(t) = i^t$ lies in $G_{\text{all}}$ and has total loss 0.

∎

So we compare against $G_a = \{g_i : i\in X\}$ — the best single action.

Warmup: Greedy and Randomized Greedy

(In this subsection losses are $\{0,1\}$ rather than $[0,1]$ , which simplifies notation; everything extends.)

AlgorithmGreedy

Initially $x^1 = 1$ . At time $t$ : let $L^{t-1}_{\min} = \min_i L^{t-1}_i$ and $S^{t-1} = \{i : L^{t-1}_i = L^{t-1}_{\min}\}$ ; play $x^t = \min S^{t-1}$ .

TheoremGreedy

$L^T_{\text{Greedy}} \le N\cdot L^T_{\min} + (N-1)$ .

ProofCount actions eliminated between increments of the minimum

Each time Greedy incurs loss 1 while $L^t_{\min}$ does not increase, at least one action leaves $S^t$ . This can happen at most $N$ times before $L^t_{\min}$ rises by 1, so Greedy loses at most $N$ between successive increments. Formally, by induction $L^t_{\text{Greedy}} \le N - |S^t| + N\cdot L^t_{\min}$ .

∎

WarningThe factor $N$ is not Greedy’s fault — it is determinism’s

For any deterministic algorithm $D$ there is a loss sequence with $L^T_D = T$ and $L^T_{\min} \le \lfloor T/N\rfloor$ .

Proof: give loss 1 to whichever action $D$ selects and 0 to all others, so $L^T_D = T$ . Since only selected actions ever have loss, and some action is selected at most $\lfloor T/N\rfloor$ times, $L^T_{\min}\le\lfloor T/N\rfloor$ .

This implies $L^T_D \ge N\cdot L^T_{\min} + (T\bmod N)$ — almost matching the upper bound for Greedy, so randomization is essential.

AlgorithmRandomized Greedy (RG)

$p_i^1 = 1/N$ . At time $t$ : put $p_i^t = 1/|S^{t-1}|$ for $i \in S^{t-1}$ and 0 otherwise — uniform over all currently best actions, removing the deterministic tie-breaker.

TheoremRandomized Greedy

$L^T_{\text{RG}} \le (\ln N) + (1 + \ln N)L^T_{\min}$ .

ProofA harmonic sum between successive increments

Let $t_j$ be the step at which $L^t_{\min}$ first reaches $j$ ; we bound the loss in $(t_j, t_{j+1}]$ . At any $t$ , $1\le|S^t|\le N$ . If at time $t$ the set $S^t$ shrinks by $k$ from size $n'$ to $n'-k$ , RG’s loss is $k/n'$ — each such action carries weight $1/n'$ — and

$\frac{k}{n'} \le \frac{1}{n'} + \frac{1}{n'-1} + \cdots + \frac{1}{n'-k+1}$

So over the whole interval the loss is at most $1/N + 1/(N-1) + \cdots + 1/1 \le 1 + \ln N$ . Formally, $L^t_{\text{RG}} \le \big(1/N + \cdots + 1/(|S^t|+1)\big) + (1+\ln N)L^t_{\min}$ .

∎

IntuitionWhere RG still loses, and the fix

The losses are greatest when $S^t$ is small, since the online loss is proportional to $1/|S^t|$ . The remedy is to give some weight to actions that are currently near best, letting probability mass decay gracefully with distance from optimality rather than dropping to zero.

Randomized Weighted Majority

AlgorithmRandomized Weighted Majority (RWM)

Give action $i$ with cumulative loss $L_i$ the weight $w_i = (1-\eta)^{L_i}$ and play proportionally: $p_i = w_i/\sum_j w_j$ . Concretely, $w_i^1 = 1$ , $p_i^1 = 1/N$ ; at time $t$ , if $\ell_i^{t-1} = 1$ then $w_i^t = w_i^{t-1}(1-\eta)$ , else $w_i^t = w_i^{t-1}$ ; and $p_i^t = w_i^t/W^t$ with $W^t = \sum_i w_i^t$ .

Think of $\eta$ as a small constant, say $0.01$ . (Losses in $[0,1]$ are handled by the update $w_i^t = w_i^{t-1}(1-\eta)^{\ell_i^{t-1}}$ .)

TheoremRWM

For $\eta \le 1/2$ and binary losses,

$L^T_{\text{RWM}} \le (1+\eta)L^T_{\min} + \frac{\ln N}{\eta}$

Setting $\eta = \min\{\sqrt{(\ln N)/T},\ 1/2\}$ gives $L^T_{\text{RWM}} \le L^T_{\min} + 2\sqrt{T\ln N}$ .

ProofTrack the total weight

The key idea: whenever the algorithm has significant expected loss, the total weight must drop substantially; combine this with the fact that the weight of the best action gives a floor, $W^{T+1}\ge\max_i w_i^{T+1} = (1-\eta)^{L^T_{\min}}$ .

Step 1: the weight drop equals the loss. Let $F^t = \big(\sum_{i:\ell_i^t = 1}w_i^t\big)/W^t$ , which is exactly RWM’s expected loss at time $t$ . Each action with loss 1 has its weight multiplied by $1-\eta$ and the rest are unchanged, so

$W^{t+1} = W^t - \eta F^tW^t = W^t(1-\eta F^t)$

The proportion of weight removed is exactly proportional to the expected loss.

Step 2: sandwich. With $W^1 = N$ ,

$(1-\eta)^{L^T_{\min}} \le W^{T+1} = N\prod_{t=1}^T (1-\eta F^t)$

Step 3: take logarithms and use $\ln(1-z)\le -z$ :

$L^T_{\min}\ln(1-\eta) \le \ln N + \sum_t \ln(1-\eta F^t) \le \ln N - \eta\sum_t F^t = \ln N - \eta L^T_{\text{RWM}}$

Step 4: rearrange and use $-\ln(1-z)\le z+z^2$ for $0\le z\le\tfrac12$ :

$L^T_{\text{RWM}} \le \frac{-L^T_{\min}\ln(1-\eta)}{\eta} + \frac{\ln N}{\eta} \le (1+\eta)L^T_{\min} + \frac{\ln N}{\eta}$

∎

NoteTuning $\eta$ without knowing $T$

The second bound assumes $T$ is known in advance; otherwise a guess and double approach costs only a constant factor. One can in fact get the potentially better $L^T_{\text{RWM}} \le L^T_{\min} + 2\sqrt{L^T_{\min}\ln N}$ by setting $\eta = \min\{\sqrt{(\ln N)/L_{\min}},\ 1/2\}$ .

Polynomial Weights

AlgorithmPolynomial Weights (PW)

$w_i^1 = 1$ , $p_i^1 = 1/N$ . At time $t$ : $w_i^t = w_i^{t-1}(1 - \eta\ell_i^{t-1})$ and $p_i^t = w_i^t/W^t$ .

NoteThe only change, and what it buys

PW differs from RWM only in the update, and extends naturally to losses in $[0,1]$ (even to both losses and gains) while keeping the same proof structure — and it performs especially well in the case of small losses.

It is no longer true that an action of total loss $L$ has weight $(1-\eta)^L$ . What is preserved is the invariant that if PW’s loss at time $t$ is $F^t$ , then exactly an $\eta F^t$ fraction of the total weight is removed: $W^{t+1} = W^t - \eta\sum_i w_i^t\ell_i^t = W^t(1-\eta F^t)$ with $F^t = \big(\sum_i w_i^t\ell_i^t\big)/W^t$ .

TheoremPolynomial Weights

For $\eta \le 1/2$ , any $[0,1]$ -valued loss sequence and any $k$ ,

$L^T_{\text{PW}} \le L^T_k + \eta Q^T_k + \frac{\ln N}{\eta}, \qquad Q^T_k = \sum_{t=1}^T(\ell_k^t)^2$

Setting $\eta = \min\{\sqrt{(\ln N)/T}, 1/2\}$ and noting $Q^T_k \le T$ gives $L^T_{\text{PW}} \le L^T_{\min} + 2\sqrt{T\ln N}$ .

ProofUpper and lower bounds on

\ln W^{T+1}

Upper, exactly as for RWM:

$\ln W^{T+1} = \ln N + \sum_t\ln(1-\eta F^t) \le \ln N - \eta\sum_t F^t = \ln N - \eta L^T_{\text{PW}}$

Lower, from the recursive definition of the weights and $\ln(1-z)\ge -z-z^2$ for $0\le z\le\tfrac12$ :

$\ln W^{T+1}\ \ge\ \ln w_k^{T+1} = \sum_{t=1}^T\ln\big(1-\eta\ell^t_k\big) \ \ge\ -\eta\sum_t\ell^t_k - \eta^2\sum_t(\ell^t_k)^2 = -\eta L^T_k - \eta^2Q^T_k$

Combining, $-\eta L^T_k - \eta^2 Q^T_k \le \ln N - \eta L^T_{\text{PW}}$ .

∎

IntuitionThe quadratic term is a feature

$Q^T_k$ is the sum of squared losses of the comparison action. When the best action’s losses are small, $Q^T_k \ll T$ and the bound is correspondingly sharper — this is a second-order bound, versus the zero-order $2\sqrt{T\ln N}$ .

Lower bounds

TheoremSublinear regret is impossible when $T < \log_2 N$

There is a stochastic loss generation such that any algorithm has $\mathbb{E}[L^T] = T/2$ while $L^T_{\min} = 0$ .

ProofHalve the surviving set each step

At $t=1$ a random half of the actions get loss 0 and the rest 1; at $t=2$ a random half of those get 0 and everything else (including all previous losers) gets 1; and so on. At every step the expected probability mass on zero-loss actions is at most $1/2$ , so the algorithm loses $1/2$ per step. Yet for $T<\log_2 N$ some action still has total loss 0.

∎

Theorem $\Omega(\sqrt T)$ even with $N = 2$

There is a stochastic loss generation with $\mathbb{E}[L^T_{R} - L^T_{\min}] = \Omega(\sqrt T)$ .

ProofRandom walk deviation

Flip a fair coin each step, setting $\ell^t = (0,1)$ or $(1,0)$ with probability $1/2$ each. Any distribution has expected loss exactly $1/2$ , so any algorithm has expected loss $T/2$ . Given $T/2 + y$ losses of the first kind and $T/2-y$ of the second, $T/2 - L^T_{\min} = |y|$ . The probability of a given $y$ is $\binom{T}{T/2+y}/2^T$ , which by Stirling is $O(1/\sqrt T)$ — so with constant probability $|y| = \Omega(\sqrt T)$ .

∎

Regret minimization and game theory

DefinitionGame-theoretic setup

$G = \langle M, (X_i), (s_i)\rangle$ with $m$ players; player $i$ has $N$ actions and loss function $s_i : X_i\times(\times_{j\ne i}X_j)\to[0,1]$ .

Player $i$ plays for $T$ steps using procedure ON, playing mixed action $P^t_i$ while the others play $P^t_{-i}$ . Its loss is $\ell^t_{\text{ON}} = \mathbb{E}_{x\sim P^t}[s_i(x^t)]$ . The loss vector is $\ell^t_j = \mathbb{E}_{x_{-i}\sim P^t_{-i}}[s_i(x_j, x_{-i})]$ — the loss player $i$ would have observed had it played $x_j$ at time $t$ .

Constant-sum games: reaching the value

TheoremExternal regret suffices against the game value

Let $G$ be a constant-sum game with value $(v_1,v_2)$ . If player $i$ plays for $T$ steps with external regret $R$ , its average loss $\tfrac1T L^T_{\text{ON}}$ is at most $v_i + R/T$ .

ProofThe empirical opponent strategy has a good response

Let $q$ be the mixed strategy given by the observed frequencies of player 2’s actions, $q_j = \sum_t P^t_{2,j}/T$ . By the theory of constant-sum games there is an action $x_k$ with $\mathbb{E}_{x_2\sim q}[s_1(x_k,x_2)]\le v_1$ — so had player 1 always played $x_k$ , its loss would be at most $v_1T$ . Hence $L^T_{\min}\le L^T_k \le v_1T$ , and $L^T_{\text{ON}}\le L^T_{\min} + R \le v_1T + R$ .

∎

NoteWhat the rate is

Using a procedure with $R = O(\sqrt{T\log N})$ guarantees average loss at most $v_i + O(\sqrt{(\log N)/T})$ .

ImportantRegret algorithms prove the minimax theorem

Define $v^1_{\min} = \min_{x_1}\max_{z\in\Delta(X_2)}\mathbb{E}_{x_2\sim z}[s_1(x_1,x_2)]$ — the best loss player 1 can guarantee knowing player 2’s mixed action in advance — and $v^1_{\max} = \max_{x_2}\min_{z\in\Delta(X_1)}\mathbb{E}_{x_1\sim z}[s_1(x_1,x_2)]$ , the best it can guarantee going first. The minimax theorem says $v^1_{\min} = v^1_{\max}$ .

ProofMinimax from external regret

Suppose for contradiction $v^1_{\max} = v^1_{\min} + \gamma$ with $\gamma>0$ (clearly $v^1_{\max}\ge v^1_{\min}$ ). Have both players run regret-minimizing algorithms for $T$ steps with regret at most $R$ , where $R/T < \gamma/2$ . Let $L_{\text{ON}}$ be player 1’s loss, so $-L_{\text{ON}}$ is player 2’s.

With $q_i$ the empirical frequency strategies, $L^1_{\min}/T \le v^1_{\min}$ (we pick the best action against the specific mixed action $q_2$ ), and similarly $L^2_{\min}/T\le v^2_{\min}$ . The regret guarantees give $L_{\text{ON}}\le L^1_{\min}+R$ and $-L_{\text{ON}}\le L^2_{\min}+R$ . Chaining,

$Tv^1_{\max} - R = -Tv^2_{\min} - R \le -L^2_{\min} - R \le L_{\text{ON}} \le L^1_{\min}+R \le Tv^1_{\min}+R$

so $v^1_{\max} - v^1_{\min}\le 2R/T < \gamma$ — a contradiction.

∎

NoteA third proof of minimax

The LP treatment gave two: via Nash’s theorem, and via linear programming duality. This is a third, purely algorithmic one — no fixpoint theorem, no duality, just two learners playing each other.

Correlated equilibrium from swap regret

DefinitionSwitch functions and per-player regret

For $x_1, b_1, b_2\in X_i$ let $\text{switch}_i(x_1,b_1,b_2)$ be $b_2$ if $x_1 = b_1$ and $x_1$ otherwise. For a modification function $f$ ,

$\text{regret}_i(x,f) = s_i(x) - s_i(f(x_i), x_{-i})$

DefinitionCorrelated and $\epsilon$ -correlated equilibrium

$P$ over $X$ is a correlated equilibrium if for every player $i$ and any $b_1,b_2\in X_i$ ,

$\mathbb{E}_{x\sim P}\big[\text{regret}_i(x, \text{switch}_i(\cdot,b_1,b_2))\big]\le0$

Equivalently — and this is the form that extends to approximation — for any $F : X_i\to X_i$ , $\mathbb{E}_{x\sim P}[\text{regret}_i(x,F)]\le 0$ . And $P$ is an $\epsilon$ -correlated equilibrium if for every $i$ and every $F_i$ ,

$\mathbb{E}_{x\sim P}[\text{regret}_i(x,F_i)]\le\epsilon$

TheoremSwap regret bounds the distance to correlated equilibrium

If for $T$ steps every player follows a strategy with swap regret at most $R$ , then the empirical distribution $Q$ of the joint actions played is an $(R/T)$ -correlated equilibrium.

ProofThe regret difference is the deviation incentive

$Q$ assigns probability $1/T$ to each $P^t$ . Fix $F : X_i\to X_i$ ; swap regret gives $L^T_{\text{ON}}\le L^T_{\text{ON},F} + R$ . By definition of the regret function,

$L^T_{\text{ON}} - L^T_{\text{ON},F} = \sum_{t}\mathbb{E}_{x^t\sim P^t}[s_i(x^t)] - \sum_t \mathbb{E}_{x^t\sim P^t}\big[s_i(F(x_i^t), x^t_{-i})\big] = T\cdot\mathbb{E}_{x\sim Q}[\text{regret}_i(x,F)]$

so $\mathbb{E}_{x\sim Q}[\text{regret}_i(x,F_i)]\le R/T$ .

∎

ImportantThe headline dynamic result

If the average swap regret vanishes, the empirical play converges to the set of correlated equilibria. Note the contrast with best-response dynamics, which cycle in matching pennies and in general converge to nothing. Learning converges — but to the correlated equilibrium polytope, not to Nash.

Dominated strategies

Definition $\epsilon$ -dominated

$x_j$ is $\epsilon$ -dominated by $x_k$ if $s_i(x_j,x_{-i})\ge\epsilon + s_i(x_k,x_{-i})$ for all $x_{-i}$ ; likewise by a mixed action $y$ with $\mathbb{E}_{x_d\sim y}[s_i(x_d,x_{-i})]$ on the right.

TheoremLow swap regret means rarely playing dominated actions

If player $i$ uses a procedure with swap regret $R$ for $T$ steps, the average weight it puts on the set of $\epsilon$ -dominated actions is at most $R/(\epsilon T)$ .

ProofThe dominating actions witness the regret

If $x_j$ is $\epsilon$ -dominated by $x_k$ then $\text{regret}_i(x,\text{switch}_i(\cdot,x_j,x_k))\ge\epsilon$ for every $x_{-i}$ . Let $D_\epsilon$ be the dominated set and $w = \frac1T\sum_t\sum_{j\in D_\epsilon}P^t_{i,j}$ its time-average weight. Replacing each dominated action by its dominator shows the swap regret is at least $w\epsilon T$ , so $w\epsilon T \le R$ .

∎

NoteExternal regret is not enough in general

Low external regret does not by itself give this guarantee — though RWM and PW happen to.

From external to swap regret: a generic reduction

ImportantThe construction

Instantiate $N$ copies $A_1,\ldots,A_N$ of an external-regret procedure. At each step each $A_i$ outputs a distribution $q_i^t$ , with $q^t_{i,j}$ its weight on action $j$ . We choose our own distribution $p^t$ to satisfy

$p_j^t = \sum_i p_i^t q^t_{i,j}, \qquad\text{i.e.}\qquad p^t = p^tQ^t$

— $p^t$ is a stationary distribution of the Markov process defined by $Q^t$ , which exists and is efficiently computable. When the loss vector $\ell^t$ arrives, we hand $A_i$ the scaled vector $p_i^t\ell^t$ , so $A_i$ believes action $j$ costs $\sum_t p_i^t\ell_j^t$ — exactly what we would incur by putting $i$ ‘s probability mass on $j$ . Procedure $A_i$ becomes responsible for regret of the $i\to j$ variety.

IntuitionTwo equivalent readings of $p^t$

Either draw action $j$ directly with probability $p_j^t$ , or draw procedure $A_i$ with probability $p_i^t$ and let it choose the action — producing exactly $p^tQ^t$ . The fixed-point condition is what makes these agree.

TheoremThe reduction

Given an $R$ external regret procedure, the master procedure $H$ satisfies, for every $F : \{1,\ldots,N\}\to\{1,\ldots,N\}$ ,

$L_H \le L_{H,F} + NR$

i.e. the swap regret of $H$ is at most $NR$ .

ProofThe perceived losses sum to the true loss

$A_i$ experiences loss $(p_i^t\ell^t)\cdot q_i^t = p_i^t(q_i^t\cdot\ell^t)$ , so its external regret guarantee gives, for any $j$ ,

$\sum_{t=1}^T p_i^t\big(q_i^t\cdot\ell^t\big) \le \sum_{t=1}^T p_i^t\ell_j^t + R$

The key step: summing the $N$ procedures’ losses at time $t$ gives $\sum_i p_i^t(q_i^t\cdot\ell^t) = p^tQ^t\ell^t = p^t\ell^t$ by design of $p^t$ — the perceived losses total exactly our actual loss. So summing the displayed inequality over all $i$ , the left side is $L^T_H$ , and choosing $j = F(i)$ on the right gives $L^T_H \le L^T_{H,F} + NR$ .

∎

CorollaryEfficient swap regret

There is an online algorithm with swap regret $O(N\sqrt{T\log N})$ . (This can be improved to $O(\sqrt{NT\log N})$ .)

NoteWhy bother with a reduction

Low-internal-regret algorithms have also been developed from first principles, but this procedure gives the best bounds known for efficient algorithms — and it is a black box, inheriting any future improvement in external regret.

The partial information (bandit) model

The problem. In the bandit model the algorithm observes only the loss of the action it actually performed — you learn the travel time of the route you drove, not of the ones you didn’t. This forces an exploration versus exploitation trade-off: essentially any procedure must somehow explore to estimate losses.

ImportantThe reduction in outline

Partition the $T$ steps into $K$ blocks. Within a block the procedure uses a single distribution, except that it also samples each action once (the exploration steps). The partial-information procedure MAB passes the vector of losses gathered from exploration to a full-information procedure FIB, which returns a new distribution. The work is in relating FIB’s loss on the sequence it observes to MAB’s loss on the real sequence.

DerivationStep 1: a block-based full-information procedure

Blocks $B^\tau = \{(\tau-1)(T/K)+1,\ldots,\tau(T/K)\}$ (assume $K\mid T$ ). Let FIB be an $R_K$ external regret procedure over $K$ steps, updating at the end of each block using the average loss vector $c^\tau = \sum_{t\in B^\tau}\ell^t/|B^\tau|$ . With $C_i^K = \sum_\tau c_i^\tau$ and $C^K_{\min} = \min_i C^K_i$ , since FIB uses a single $p^\tau$ throughout each block,

$L^T_{\text{FIB}} = \sum_\tau\sum_{t\in B^\tau}p^\tau\cdot\ell^t = \frac TK\sum_\tau p^\tau\cdot c^\tau \le \frac TK\big(C^K_{\min}+R_K\big)$

A tempting dead end: with $R_K = O(\sqrt{K\log N})$ the regret is $O((T/\sqrt K)\sqrt{\log N})$ , minimized at $K = T$ — one step per block. But the sampling cost, added next, will force $K \ll T$ .

DerivationStep 2: unbiased estimates instead of true averages

Feed FIB a random vector $\hat c^\tau$ with $\mathbb{E}[\hat c_i^\tau] = c_i^\tau$ . Then for any block and any $p^\tau$ ,

$\frac{1}{|B^\tau|}\sum_{t\in B^\tau}p^\tau\cdot\ell^t = p^\tau\cdot c^\tau = \sum_i p_i^\tau\,\mathbb{E}[\hat c_i^\tau]$

— the true loss of $p^\tau$ in the block equals its expected loss under $\hat c^\tau$ . The $\hat c^\tau$ are random, so the $p^\tau$ are random too (depending on $\hat c^1,\ldots,\hat c^{\tau-1}$ ); still, for any realized sequence $\hat C^K_{\text{FIB}}\le\hat C^K_{\min}+R_K$ , and since $\mathbb{E}[\hat C^K_i] = C^K_i$ and $\mathbb{E}[\min_i \hat C^K_i]\le\min_i\mathbb{E}[\hat C^K_i]$ ,

$\mathbb{E}\big[\hat C^K_{\text{FIB}}\big] \le C^K_{\min}+R_K$

Both FIB and MAB use the same $p^1,\ldots,p^K$ on the same realized sequence, so $\mathbb{E}[C^K_{\text{MAB}}] = \mathbb{E}[\hat C^K_{\text{FIB}}]$ .

DerivationStep 3: the estimates, and the price of getting them

For each action $i$ and block $B^\tau$ , choose a random exploration time $t_i\in B^\tau$ (these need not be independent across actions, so collisions are avoidable). At $t_i$ , MAB plays action $i$ outright, observes $\ell^{t_i}_i$ , and sets $\hat c_i^\tau = \ell^{t_i}_i$ — giving $\mathbb{E}[\hat c^\tau_i] = c^\tau_i$ as required.

The cost: losses are at most 1 and there are $N$ exploration steps in each of $K$ blocks, so exploration costs at most $NK$ overall. Hence

$\mathbb{E}\big[L^T_{\text{MAB}}\big] \le NK + \frac TK\mathbb{E}\big[C^K_{\text{MAB}}\big] \le L^T_{\min} + NK + \frac TK R_K$

TheoremFull information to bandit

Given an $O(\sqrt{K\log N})$ external regret procedure FIB, there is a partial information procedure MAB with

$L^T_{\text{MAB}} \le L^T_{\min} + O\big(T^{2/3}N^{1/3}\sqrt{\log N}\big), \qquad T\ge N$

obtained by setting $K = (T/N)^{2/3}$ , which balances the exploration cost $NK$ against the block-granularity cost $(T/K)R_K$ .

NoteNot the best bounds

This reduction is particularly simple and generic but does not produce the best known bandit bounds; sharper direct algorithms exist.

Convergence to Nash equilibrium in routing games

The setting. Online routing is a natural home for these algorithms: choose among $N$ routes daily and perform nearly as well as the best fixed route in hindsight, even if traffic changes arbitrarily. Even when the number of paths in a graph $G$ is exponential in $|G|$ , there are external-regret algorithms whose running time and regret are polynomial in the graph size — and extensions handle the partial-information case where only the traversed path’s cost is revealed.

DefinitionThe Wardrop model (single commodity)

A directed network $G = (V,E)$ with one unit of flow — a large population of infinitesimal users — travelling from $v_{\text{start}}$ to $v_{\text{end}}$ . Each edge has a nondecreasing latency function $\ell_e$ of the flow $f_e$ on it. The cost of a path is $\sum_{e\in P}\ell_e(f_e)$ and the average travel time is $C(f) = \sum_{e\in E}\ell_e(f_e)f_e$ . A flow is at Nash equilibrium if all flow-carrying paths are minimum-latency given $f$ .

IntuitionWhy the result is natural, and why it is not automatic

A Nash equilibrium is precisely a set of static strategies that are all no-regret with respect to each other, so convergence seems plausible. But there are many simple games where regret-minimizing algorithms do not approach Nash and can perform much worse than any Nash equilibrium. Routing is special.

WarningA nonstandard notion of convergence — and why it must be

The general result says: if each user has regret $o(T)$ — or even if just the average regret over users is $o(T)$ — then a $1-\epsilon$ fraction of days have the property that a $1-\epsilon$ fraction of users experience travel time at most $\epsilon$ above the best path that day, with $\epsilon$ shrinking polynomially in the graph size, the regret bounds, and the maximum latency slope.

Usually an “ $\epsilon$ -approximate equilibrium” requires all participants to have at most $\epsilon$ incentive to deviate. But low-regret algorithms are allowed to occasionally take long paths — and bandit algorithms must occasionally explore paths untried for a while, to avoid regret if they have improved. The multiple levels of hedging are genuinely necessary.

Definition $\epsilon$ -Nash flow and the regret timescale

With $\mathcal P$ the simple paths and $f^t$ the flow on day $t$ , a flow is $\epsilon$ -Nash if $C(f)\le\epsilon + \min_{P\in\mathcal P}\sum_{e\in P}\ell_e(f_e)$ — the average deviation incentive is at most $\epsilon$ . Let $R(T)$ be the average regret over users,

$R(T) = \sum_{t=1}^T\sum_{e\in E}\ell_e(f^t_e)f^t_e - \min_{P\in\mathcal P}\sum_{t=1}^T\sum_{e\in P}\ell_e(f^t_e)$

and let $T_\epsilon$ be the number of steps after which $R(T)\le\epsilon T$ for all $T\ge T_\epsilon$ . RWM and PW achieve $T_\epsilon = O(\tfrac{1}{\epsilon^2}\log N)$ with $\eta = \epsilon/2$ .

TheoremTime-average flow is approximately Nash

Suppose the latency functions are linear. Then for $T\ge T_\epsilon$ , the average flow $\hat f = \tfrac1T(f^1+\cdots+f^T)$ is $\epsilon$ -Nash.

ProofLinearity, then convexity, then the regret bound

Linearity gives $\ell_e(\hat f_e) = \tfrac1T\sum_t\ell_e(f^t_e)$ for every $e$ . Since $\ell_e(f^t_e)f^t_e$ is a convex function of the flow,

$\ell_e(\hat f_e)\hat f_e \le \frac1T\sum_{t=1}^T\ell_e(f^t_e)f^t_e$

Summing over all edges and applying the definition of $T_\epsilon$ , then linearity once more,

$C(\hat f) \le \frac1T\sum_t C(f^t) \le \epsilon + \min_P\frac1T\sum_t\sum_{e\in P}\ell_e(f^t_e) = \epsilon + \min_P\sum_{e\in P}\ell_e(\hat f_e)$

∎

ImportantFrom the time-average to most individual days

This bounds the time-average flow. It can then be used to show most $f^t$ are themselves approximately Nash. The key idea: if an edge’s cost fluctuated wildly, most of its users would experience latency substantially above the edge’s average cost — because more users are on the edge when it is congested than when it is not — which in turn implies substantial regret. These arguments carry over to general nonlinear latencies.

NoteWhy this motivates price of anarchy

routing-games and inefficiency-of-equilibria-introduction analyze the gap between Nash and optimal flows. This section says those results apply to participants using well-motivated self-interested adaptive behavior, not merely to an equilibrium assumed by fiat.

Current research directions

NoteRefined regret bounds

The bounds above are zero-order: they depend on $T$ alone. First-order bounds depend on the best action’s loss, second-order bounds on the sum of squares (like $Q^T_k$ in the PW theorem). An open problem is external regret proportional to the empirical variance of the best action. A second challenge is reducing the prior information the algorithm needs — ideally it should learn and adapt to parameters such as the maximum and minimum loss.

NoteLarge action spaces

We assumed $N$ is small enough to enumerate, with running time proportional to $N$ . But $N$ is often exponential in the natural parameters: all simple $s$ – $t$ paths in an $n$ -node graph, or all binary search trees on $\{1,\ldots,n\}$ . Since the full-information bounds are only logarithmic in $N$ , polynomial regret is information-theoretically available — the challenge is computational efficiency.

Kalai and Vempala give an efficient algorithm whenever (a) the actions form a subset of $\mathbb{R}^n$ , (b) the loss vectors are linear functions over $\mathbb{R}^n$ , and (c) the offline problem $\arg\min_{x\in S}[x\cdot\ell]$ is efficiently solvable — covering both examples above. (Search trees add a rotation cost for changing action between steps, also addressed there.) Zinkevich extends this to convex loss functions given a projection oracle.

NoteDynamics

The classical example is swap regret, where all players minimizing it drives the empirical distribution to the set of correlated equilibria. We also saw convergence to the minimax value in two-player zero-sum games, and to Nash in a Wardrop routing game. Further convergence results in other settings would be of substantial interest: understanding these dynamics is what reveals the strengths and weaknesses of using such procedures.

Quick reference

Object	Statement	Bound
Best sequence in hindsight	Regret $\ge T(1-1/N)$ for any algorithm	Impossible — hence restrict the class
Greedy	$L^T \le N L^T_{\min} + (N-1)$	factor $N$
Any deterministic algorithm	$L^T_D = T$ , $L^T_{\min}\le\lfloor T/N\rfloor$	factor $N$ is forced
Randomized Greedy	$L^T \le \ln N + (1+\ln N)L^T_{\min}$	factor $O(\log N)$
RWM	$L^T \le (1+\eta)L^T_{\min} + \tfrac{\ln N}{\eta}$	$L^T_{\min} + 2\sqrt{T\ln N}$
Polynomial Weights	$L^T \le L^T_k + \eta Q^T_k + \tfrac{\ln N}{\eta}$	second-order; handles $[0,1]$
Lower bound ( $T<\log_2 N$ )	$\mathbb{E}[L^T] = T/2$ , $L^T_{\min}=0$	no sublinear regret
Lower bound ( $N = 2$ )	$\mathbb{E}[L^T - L^T_{\min}] = \Omega(\sqrt T)$	$\sqrt T$ is unavoidable
External → swap	swap regret $\le NR$	$O(N\sqrt{T\log N})$ , improvable to $O(\sqrt{NT\log N})$
Full info → bandit	$L^T_{\text{MAB}}\le L^T_{\min} + NK + \tfrac TK R_K$	$O(T^{2/3}N^{1/3}\sqrt{\log N})$ at $K = (T/N)^{2/3}$
Constant-sum	average loss $\le v_i + R/T$	also proves minimax
Swap regret $R$ for all players	empirical joint distribution is $(R/T)$ -correlated equilibrium	converges to the CE polytope
$\epsilon$ -dominated actions	average weight $\le R/(\epsilon T)$	vanishes for sublinear $R$
Wardrop, linear latencies	$\hat f$ is $\epsilon$ -Nash for $T\ge T_\epsilon$	$T_\epsilon = O(\epsilon^{-2}\log N)$

Facts to keep to hand:

$\mathcal F^{ex},\mathcal F^{in}\subseteq\mathcal F^{sw}$ , so swap regret dominates both; internal-to-swap costs at most a factor $N$ .
Every weight-based proof here has the same skeleton: the fraction of total weight removed per step equals the algorithm’s expected loss, then sandwich $W^{T+1}$ between $N\prod(1-\eta F^t)$ above and the best action’s weight below.
The three equilibrium consequences pair with three regret notions: external → game value and minimax, swap → correlated equilibrium, swap → avoid dominated actions.
Learning converges to correlated, not Nash, equilibria in general — matching the fact that correlated equilibria are LP-easy while Nash is PPAD-complete.
The swap reduction works because $p^t$ is chosen as the stationary distribution of $Q^t$ , which is exactly what makes the subroutines’ perceived losses sum to the true loss.
The bandit reduction balances two costs pulling opposite ways: exploration $NK$ wants $K$ small, block granularity $(T/K)R_K$ wants $K$ large.
Routing is a special case: regret minimization converges to Nash there, but not in general games.

References

[[lit/algorithmic-game-theory|Nisan, Roughgarden, Tardos & Vazirani, Algorithmic Game Theory]] — chapter 4 (Blum & Mansour)
Cesa-Bianchi & Lugosi, Prediction, Learning, and Games — thorough coverage of most topics here

Related