---
kind: concept
slug: no-regret-learning
title: No-regret learning
summary: >-
  A learner's regret is the gap between its cumulative payoff and the best fixed action in hindsight; no-regret learning means that gap shrinks over time. Covers the rescaled-game bound with step size equal to the selection strength for each gene, the recombination-before-selection variant, and what regret does not guarantee (fitness, convergence). Based on one paper so far.
tags: [regret, learning-dynamics, game-theory, evolution]
papers: ["1502.05056"]
related: [multiplicative-weights-update, evolutionary-dynamics, multi-armed-bandit]
status: draft
updated_at: 2026-11-01
---

## Overview

Regret compares a learner with a fixed strategy it could have played every
round. The paper's version is external and cumulative: it takes the average
payoff the learner would have had by always playing one fixed action, and
subtracts the average payoff the learner actually obtained
[arxiv:1502.05056 §5.1]. "No-regret" means this difference tends to zero as
the number of rounds grows; the paper calls the property diminishing regret
[arxiv:1502.05056 §5.1] [arxiv:1502.05056 §6].

The paper applies this to genes in a sexually reproducing population. Each
gene is a learner whose actions are its alleles. The bound it proves depends
only on the gene's own update rule, not on what the other genes do: they may
be independent, correlated or chosen adversarially [arxiv:1502.05056 §5.1].
The guarantee is per gene, and the paper states it is not a guarantee on the
population's average fitness [arxiv:1502.05056 §6].

## Variants

### Rescaled-game bound (step size equal to the selection strength)

The paper's bound is stated for a fitness matrix W whose selection strength is
s, with s in (0, 1/2) and every entry w_ij in [1 − s, 1 + s]
[arxiv:1502.05056 §5.1] [arxiv:1502.05056 cor. 3]. The proof rescales the
game to Δ_ij = (w_ij − 1)/s, so every entry lies in [−1, 1], and runs the
ε-parameterised rule with ε = s on that game [arxiv:1502.05056 §5.1]. The
result, for every number of generations T and every allele i, is that the
realised average fitness of the population is at least the average
hindsight-best allele fitness, minus s² and minus ln(n)/T
[arxiv:1502.05056 cor. 3]. Letting s go to zero and T go to infinity makes the
average regret vanish [arxiv:1502.05056 §5.1].
Card: [On Sex, Evolution, and the Multiplicative Weights Update Algorithm](/papers/1502.05056).

The paper notes that the earlier theory of Chastain et al. (PNAS 2014) gives
a refined form of the same kind of bound, in which ln(n) is replaced by the
entropy of the population distribution [arxiv:1502.05056 §5.1]. This page uses
the paper's ln(n) form.

### Parameter-free rule and the regret run

The marginal match with the population dynamics uses the parameter-free rule,
which is the limit ε → ∞ and the paper's default [arxiv:1502.05056 §2.3]. The
regret bound does not use that run. It switches from the parameter-free rule
on W to the ε-rule on the rescaled game, with ε = s, and this switch is where
the selection strength enters [arxiv:1502.05056 §5.1]. The two are different
runs of the same family, so a regret number from one does not transfer to the
other without the argument the paper gives [arxiv:1502.05056 §2.3] [arxiv:1502.05056 §5.1].
Card: as above.

### Recombination-before-selection regret

For the RS dynamics the paper says the cumulative regret still diminishes, but
it is measured against an expected fitness g^(r) that is not exactly the
population's expected fitness at each generation. The regret therefore
diminishes against that quantity, not against the actual average fitness
[arxiv:1502.05056 §5.1]. The paper describes this as a variation of the SR
corollary and does not restate its constants [arxiv:1502.05056 §5.1].

### Regret from convergence

Regret also diminishes whenever the population converges to a pure Nash
equilibrium, because players have no regret there and the cumulative regret
stops growing [arxiv:1502.05056 §6]. Under weak selection the bound becomes
trivial once the population sits in a pure equilibrium [arxiv:1502.05056 §5.2].
This route needs convergence, which the paper does not prove for general
fitness matrices [arxiv:1502.05056 §5.2] [arxiv:1502.05056 §6].

## When to use which

| Situation | Use | Why |
|---|---|---|
| Each gene's update must have a regret bound that holds whatever the other genes do | Rescaled-game bound with ε = s | The bound depends only on the gene's own algorithm [arxiv:1502.05056 §5.1] [arxiv:1502.05056 cor. 3] |
| Fitness entries lie outside [1 − s, 1 + s], or s is not in (0, 1/2) | No bound from this paper | The proof rescales by s and needs Δ in [−1, 1] [arxiv:1502.05056 §5.1] |
| Recombination happens before selection | Regret against g^(r) | The paper's regret for RS is measured against that quantity, not against realised fitness [arxiv:1502.05056 §5.1] |
| You want a fitness or quality guarantee for the population | None from this paper | The paper says regret is the only property established, and the outcome can be a poor local optimum [arxiv:1502.05056 §6] |
| You can observe that the population has reached a pure equilibrium | Regret is already diminishing | Players have no regret at a Nash equilibrium [arxiv:1502.05056 §6] |
| You need convergence for a general fitness matrix | Not established here | The paper cites results for potential games with small ε and gives no threshold for s; for general matrices the paper reports cycling [arxiv:1502.05056 §5.2] [arxiv:1502.05056 §6] |

## Implementation sketch

The sketch restates the paper's definitions in our own notation. It is a
check on recorded runs, not the authors' code, and the paper releases no code.

```pseudocode
# Rescaled game used by the regret proof  [arxiv:1502.05056 §5.1]
# Input:  W (n, m) fitness with entries in [1 - s, 1 + s]; s in (0, 1/2)
# Output: Delta (n, m) with entries in [-1, 1]

def rescaled_game(W, s):
    # Delta_ij = (w_ij - 1) / s  [arxiv:1502.05056 §5.1]
    return (W - 1) / s
```

```pseudocode
# One epsilon-PW update for one gene  [arxiv:1502.05056 §2.3]
# Input:  x (n,) strategy; m (n,) expected profit per allele in the rescaled game
# Output: next strategy (n,)

def eps_pw_step(x, m, eps):
    # x_i proportional to x_i * (1 + eps * m_i)  [arxiv:1502.05056 §2.3]
    weighted = x * (1 + eps * m)
    return weighted / sum(weighted)
```

```pseudocode
# Check the regret bound on a recorded run, for one gene  [arxiv:1502.05056 cor. 3]
# Input:  w_bar (T,) realised average fitness per generation  [arxiv:1502.05056 §5.1]
#         g_cond (T, n) conditional utility of each allele per generation  [arxiv:1502.05056 §5.1]
#         s: selection strength; n: number of alleles
# Output: slack (n,); the bound holds for allele i when slack[i] >= 0

def regret_slack(w_bar, g_cond, s, n):
    T = len(w_bar)
    # Realised average fitness over the run, AF_SR^T  [arxiv:1502.05056 §5.1]
    af_sr = mean(w_bar)
    # Hindsight average for each fixed allele, AF_i^T  [arxiv:1502.05056 §5.1]
    af_i = mean(g_cond, axis=0)                 # (n,)
    # Right-hand side of the bound  [arxiv:1502.05056 cor. 3]
    rhs = af_i - s**2 - ln(n) / T
    return af_sr - rhs
```

The check uses the conditional utility g̲ for the hindsight term and the
realised average fitness for the SR term, as the paper defines them
[arxiv:1502.05056 §5.1]. For RS runs, replace the hindsight term with the
g^(r) utility, following the variant above.

## Contradictions

- **Regret versus fitness.** The paper quotes Chastain et al. as reading the
  result as each gene optimising its cumulative expected fitness over time.
  The paper argues that this reading can suggest a guarantee on the population's
  average fitness that the result does not give, and that only diminishing
  regret is established [arxiv:1502.05056 §6]. The two positions are both
  cited here; this page does not decide between them.
- **Parameter-free run versus regret run.** The paper's marginal equivalence is
  for the parameter-free rule, while the regret proof uses ε = s on the rescaled
  game [arxiv:1502.05056 §2.3] [arxiv:1502.05056 §5.1]. The paper says the
  inequality it uses is stated for ε-PW and that a slight modification makes it
  apply to the parameter-free rule, citing Kale's analysis in a footnote
  [arxiv:1502.05056 §5.1]. The paper does not spell out that modification. This
  page has not verified it.
- **ln(n) versus entropy.** The paper's bound uses ln(n), while the earlier
  result uses the entropy of the population distribution in the same role
  [arxiv:1502.05056 §5.1]. The two forms are not compared numerically in the
  paper.

## Papers

- [On Sex, Evolution, and the Multiplicative Weights Update Algorithm](/papers/1502.05056): proves a per-gene diminishing-regret bound for sexual dynamics with fitness in [1 − s, 1 + s], and argues that regret, not fitness or convergence, is the guarantee that follows.