---
kind: concept
slug: multiplicative-weights-update
title: Multiplicative weights update
summary: >-
  The multiplicative weights rule: each action's weight is multiplied by its expected utility and the weights are renormalised. Covers the parameter-free and mixed-utility variants, when each applies, and what regret guarantees follow. Based on one paper so far, which links the rule to sexual population dynamics.
tags: [learning-dynamics, regret, game-theory]
papers: ["1502.05056"]
related: [evolutionary-dynamics]
status: draft
updated_at: 2026-11-01
---

## 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 [arxiv: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 [arxiv:1502.05056 §3] [arxiv:1502.05056 §4]. Only the marginals are
covered; the full joint population is not guaranteed to follow the rule
[arxiv: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 [arxiv:1502.05056 §2.3]. The paper
describes it as the limit of the ε-parameterised rule as ε grows without
bound, and uses it by default [arxiv: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 [arxiv:1502.05056 §3] [arxiv:1502.05056 prop. 1].
Card: [On Sex, Evolution, and the Multiplicative Weights Update Algorithm](/papers/1502.05056).

### 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 α [arxiv: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) [arxiv:1502.05056 §4] [arxiv:1502.05056 prop. 2].
Card: [On Sex, Evolution, and the Multiplicative Weights Update Algorithm](/papers/1502.05056).

### 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 [arxiv:1502.05056 §5.1]. Its step size is set by the
selection strength, not by the limit that defines the parameter-free rule
[arxiv:1502.05056 §2.3] [arxiv: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 [arxiv:1502.05056 app. A]. Card: as above.

## When to use which

| Situation | Use | Why |
|---|---|---|
| Two genes, selection before recombination, and you want the per-gene update | Parameter-free rule, SR order | The paper proves the marginal match for any fitness matrix, r and population [arxiv:1502.05056 §3] |
| Two genes, recombination before selection | Mixed-utility rule with α = r | The paper proves the marginal match with this utility [arxiv:1502.05056 §4] |
| Only per-gene marginals are available | Not covered by the conditional utility | The conditional utility needs the full joint P, and the paper says the marginals do not determine the joint [arxiv:1502.05056 §2.3] [arxiv:1502.05056 §6] |
| You need a per-gene regret bound with fitness in [1 − s, 1 + s] | Regret-analysis step size, s in (0, 1/2) | The bound AF_SR^T ≥ AF_i^T − s² − ln(n)/T is proved for general P [arxiv:1502.05056 §5.1] [arxiv:1502.05056 cor. 3] |
| You need a fitness or quality guarantee for the outcome | Not supported by this paper | The paper says regret is the only guarantee, and runs can end at poor local optima [arxiv:1502.05056 §6] |
| Weak selection and a convergence claim | Use the cited results, with care | Convergence under weak selection is cited to known potential-game results, with no threshold for s [arxiv:1502.05056 §5.2]. For general matrices the dynamics can cycle [arxiv:1502.05056 §6] |
| Three or more loci | SR sum over subsets, or RS product | Cost grows with the product of allele counts and with 2^k subsets [arxiv:1502.05056 app. A] |

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.

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

```pseudocode
# 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,)
```

```pseudocode
# 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 [arxiv:1502.05056 §1] [arxiv:1502.05056 §3] [arxiv: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" [arxiv: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]
  [arxiv:1502.05056 §2.1], while the marginal-match proposition is stated for
  r in [0, 1] [arxiv:1502.05056 §3]. The table example uses r = 1 and the paper
  calls it not biologically valid [arxiv:1502.05056 tab. 2].

## Papers

- [On Sex, Evolution, and the Multiplicative Weights Update Algorithm](/papers/1502.05056): 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.