Multiplicative weights update

Overview

Multiplicative weights (also called polynomial weights in this paper) keeps a probability distribution over a finite set of actions. Each round, every action's weight is multiplied by its expected utility, and the weights are renormalised to sum to one 1502.05056 §2.3. The rule needs only the current distribution and the expected utility of each action.

The paper's use of the rule is in population genetics. Each gene is treated as a player whose actions are its alleles. Its result is that the per-gene (marginal) frequencies of a sexually reproducing population follow this update, for any fitness matrix and recombination rate, provided the utility is chosen correctly 1502.05056 §3 1502.05056 §4. Only the marginals are covered; the full joint population is not guaranteed to follow the rule 1502.05056 §6.

Variants

Parameter-free rule

The rule with no tuning parameter multiplies each weight by the conditional expected utility, where the conditional uses P(j | i) = p_ij / x_i for a gene with allele i and the other gene's allele j 1502.05056 §2.3. The paper describes it as the limit of the ε-parameterised rule as ε grows without bound, and uses it by default 1502.05056 §2.3.

For selection before recombination (SR), the gene's marginal frequencies equal this parameter-free update, for any fitness matrix, recombination rate and population distribution 1502.05056 §3 1502.05056 prop. 1. Card: On Sex, Evolution, and the Multiplicative Weights Update Algorithm.

Mixed-utility rule

The paper defines a utility that mixes an independent value (which uses the other gene's marginal as if the genes were independent) with the conditional value, using a weight α 1502.05056 §2.3. The rule that uses this mixed utility with α set to the recombination rate r matches the marginals of recombination before selection (RS) 1502.05056 §4 1502.05056 prop. 2. Card: On Sex, Evolution, and the Multiplicative Weights Update Algorithm.

Regret-analysis step size

The regret bound does not use the parameter-free rule. It rescales the game by the selection strength s, so the fitness differences become Δ_ij = (w_ij − 1)/s with step size ε = s 1502.05056 §5.1. Its step size is set by the selection strength, not by the limit that defines the parameter-free rule 1502.05056 §2.3 1502.05056 §5.1.

Several loci

With k loci the paper gives an SR update as a sum over all subsets of genes inherited from one parent, and an RS update as a product of marginals. The SR marginal correspondence holds for any k 1502.05056 app. A. Card: as above.

When to use which

Cost for two loci: each step is O(n·m) for an n-by-m joint, as the sketch below shows. This is our count from the sketch, not a figure from the paper.

Implementation sketch

Language-agnostic core of the rule, followed by the two utility choices. The core is the same for every variant. The variants differ only in the utility.

# One multiplicative-weights step over the actions of one player  [§2.3]
# Input:  x (n,) current distribution; g (n,) expected utility per action
# Output: next x (n,), sums to 1

def mw_step(x, g):
    # Multiply each action's weight by its expected utility  [§2.3]
    weighted = x * g                            # (n,)
    # Renormalise so the weights sum to 1  [§2.3]
    return weighted / sum(weighted)

# Conditional expected utility for gene 1, from the joint P  [§2.3]
# Input:  P (n, m) joint distribution; W (n, m) fitness
# Output: g (n,)

def utility_conditional(P, W):
    # Uses P(j | i) = p_ij / x_i, so each player needs the full joint  [§2.3]
    x = sum(P, axis=1)                          # (n,) marginal of gene 1
    return sum(P * W, axis=1) / x               # (n,)

# Independent expected utility for gene 1, from the other gene's marginal  [§2.3]
# Input:  P (n, m); W (n, m)
# Output: g (n,)

def utility_independent(P, W):
    # Uses the other gene's marginal y, as if the genes were independent  [§2.3]
    y = sum(P, axis=0)                          # (m,)
    return W @ y                                # (n,)

Variant choice, using the core above:

• Parameter-free, SR order: mw_step(x, utility_conditional(P, W)) §3, prop. 1.
• Mixed utility for RS order: mw_step(x, r * independent + (1 - r) * conditional), with the two utilities above §4, prop. 2.

For the regret analysis, use the rescaled game with step size ε = s instead of the parameter-free choice §5.1.

Contradictions

• Earlier theory versus this paper. The earlier theory of Chastain et al. (PNAS 2014) linked sexual dynamics to this rule under weak selection and under the assumption that the population stays a product of allele frequencies. This paper says the product assumption is inconsistent with the dynamics and that repeating the one-step result over generations is not justified 1502.05056 §1 1502.05056 §3 1502.05056 app. B. Chastain et al. is not a card here; its position is as this paper reports it.
• Gap size in the appendix. The paper states the joint can be at least 1/8 away from a product distribution "for any norm" 1502.05056 app. B. Reading the approximate population given there, the card author gets a smaller largest-entry gap. This is unverified and the paper's value stands until a check settles it.
• Recombination-rate range. The model restricts r to [0, 0.5] 1502.05056 §2.1, while the marginal-match proposition is stated for r in [0, 1] 1502.05056 §3. The table example uses r = 1 and the paper calls it not biologically valid 1502.05056 tab. 2.

Papers

• On Sex, Evolution, and the Multiplicative Weights Update Algorithm: shows that per-gene marginals of sexual dynamics follow the multiplicative weights rule for any fitness matrix and recombination rate, and that only diminishing regret follows.