No-regret learning

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 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 1502.05056 §5.1 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 1502.05056 §5.1. The guarantee is per gene, and the paper states it is not a guarantee on the population's average fitness 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] 1502.05056 §5.1 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 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 1502.05056 cor. 3. Letting s go to zero and T go to infinity makes the average regret vanish 1502.05056 §5.1. Card: On Sex, Evolution, and the Multiplicative Weights Update Algorithm.

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 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 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 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 1502.05056 §2.3 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 1502.05056 §5.1. The paper describes this as a variation of the SR corollary and does not restate its constants 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 1502.05056 §6. Under weak selection the bound becomes trivial once the population sits in a pure equilibrium 1502.05056 §5.2. This route needs convergence, which the paper does not prove for general fitness matrices 1502.05056 §5.2 1502.05056 §6.

When to use which

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.

# 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

# 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)

# 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 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 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 1502.05056 §2.3 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 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 1502.05056 §5.1. The two forms are not compared numerically in the paper.

Papers

• On Sex, Evolution, and the Multiplicative Weights Update Algorithm: 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.