No way to ask "which comparison should I run next?" — active-learning / information-gain primitives are absent #39

New Issue

2026-09-07T12:21:22Z

logaritmisk commented

2026-09-07 12:21:22 +00:00

Use case

lester-stash uses this crate to rank scenes from pairwise votes, where each observation costs a human click. The dominant question is therefore not "what are the ratings" but "which comparison, run next, teaches me the most per click?"

The crate answers the first question well and offers nothing for the second. A grep across src/, tests/, README.md and docs/ for information gain|entropy|KL diverg|acquisition|active learn returns nothing.

Today lester-stash uses a hand-rolled heuristic:

let quality = trueskill_tt::quality(&[&team_a, &team_b], trueskill_tt::BETA);
let score = quality * sigma_a.powi(2) * sigma_b.powi(2);

That is a guess, not a derivation. quality() is maximised when a match is even, and multiplying by σ² then double-counts uncertainty — the two factors are not independent. It has never been measured against a principled alternative, because there is no principled alternative available.

What is actually missing

The natural quantity is the expected information gain of a candidate matchup: the outcome-weighted divergence between the current beliefs and the beliefs after observing that outcome.

EIG(matchup) = Σ_outcome  P(outcome) · KL( posterior_after(outcome) ‖ prior )

or, for a cheaper and often sufficient proxy, the expected reduction in posterior variance over the participants.

Every ingredient exists except the ones that make it computable:

Ingredient	Status
`posterior_after(outcome)` for a hypothetical result	available — `Game::one_v_one`, `Game::free_for_all`, `Game::ranked` all return posteriors without mutating a `History`
`P(outcome)` for 2 teams	available — `History::predict_outcome`
`P(outcome)` for 3+ teams	missing — `predict_outcome` hard-asserts `teams.len() == 2` (`history.rs:563`, still true in 0.3.0). Tracked in #21
The pieces to reimplement it downstream	missing — see below
Any EIG / variance-reduction utility	missing — this issue

The downstream workaround is blocked too

The obvious response is "compute it yourself, outside the crate". That is not currently possible for the N-team case, because predict_outcome's own maths depends on Gaussian::forget:

// history.rs:573
.fold(crate::N00, |acc, g| acc + g.forget(self.beta.powi(2)))

and forget, exclude and delta are all pub(crate) (gaussian.rs:123, :130, :144). So a downstream crate cannot inflate a posterior by performance noise, and therefore cannot derive outcome probabilities itself for any shape the crate does not already provide.

That combination — no N-team probability, and no public primitive to build one — is what makes this a crate-level gap rather than a downstream inconvenience.

What would help, in rough order of value

Expose the arithmetic. Make Gaussian::forget (and arguably exclude) public. Smallest possible change; unblocks downstream experimentation immediately and commits the crate to nothing.
N-team outcome probabilities — #21. With 1 and 2, a downstream EIG is straightforward to write, if expensive.
A first-class acquisition utility, e.g.
```
pub fn expected_information_gain<T: Time, D: Drift<T>>(
    teams: &[&[Rating<T, D>]],
    options: &GameOptions,
) -> Result<f64, InferenceError>;
```
enumerating the outcomes of the given shape, weighting each by its probability, and returning expected KL or expected variance reduction. This is where the crate could genuinely lead — TrueSkill implementations almost universally stop at quality(), which only answers "is this matchup fair", not "is this matchup informative". Those coincide for two evenly-matched players and diverge sharply everywhere else, including for the "pick the worst of N" shapes we are moving toward.

Options 1 and 2 are enough to unblock lester-stash. Option 3 is the one worth doing properly, and it deserves its own design discussion rather than being bolted on.

Note on cost

EIG is inherently more expensive than quality() — it needs one hypothetical inference per outcome, so a naive selector over all candidate pairs is O(n² · outcomes) inferences. A useful implementation probably wants to be explicit about that cost, and a quality()-style cheap pre-filter to shortlist candidates before scoring them properly is likely the practical pattern. Worth stating in the API docs whichever way it lands, so callers do not discover it in production.

Caveat worth building against

This crate's recurring defect has been a public surface that returns a plausible constant — several instances have been found and fixed. An acquisition function is especially exposed to that failure mode, because a subtly wrong EIG still returns finite, plausible, monotone-looking numbers and simply selects slightly worse matchups forever. Whatever lands here should carry a test that a constant return value would fail: e.g. EIG for an even matchup must exceed EIG for a hopelessly lopsided one, and EIG must fall as both participants' σ falls.

## Use case lester-stash uses this crate to rank scenes from pairwise votes, where **each observation costs a human click**. The dominant question is therefore not "what are the ratings" but **"which comparison, run next, teaches me the most per click?"** The crate answers the first question well and offers nothing for the second. A grep across `src/`, `tests/`, `README.md` and `docs/` for `information gain|entropy|KL diverg|acquisition|active learn` returns nothing. Today lester-stash uses a hand-rolled heuristic: ```rust let quality = trueskill_tt::quality(&[&team_a, &team_b], trueskill_tt::BETA); let score = quality * sigma_a.powi(2) * sigma_b.powi(2); ``` That is a guess, not a derivation. `quality()` is maximised when a match is *even*, and multiplying by σ² then double-counts uncertainty — the two factors are not independent. It has never been measured against a principled alternative, because there is no principled alternative available. ## What is actually missing The natural quantity is the expected information gain of a candidate matchup: the outcome-weighted divergence between the current beliefs and the beliefs after observing that outcome. ``` EIG(matchup) = Σ_outcome P(outcome) · KL( posterior_after(outcome) ‖ prior ) ``` or, for a cheaper and often sufficient proxy, the expected reduction in posterior variance over the participants. Every ingredient exists except the ones that make it computable: | Ingredient | Status | |---|---| | `posterior_after(outcome)` for a hypothetical result | **available** — `Game::one_v_one`, `Game::free_for_all`, `Game::ranked` all return posteriors without mutating a `History` | | `P(outcome)` for 2 teams | **available** — `History::predict_outcome` | | `P(outcome)` for 3+ teams | **missing** — `predict_outcome` hard-asserts `teams.len() == 2` (`history.rs:563`, still true in 0.3.0). Tracked in #21 | | The pieces to reimplement it downstream | **missing** — see below | | Any EIG / variance-reduction utility | **missing** — this issue | ## The downstream workaround is blocked too The obvious response is "compute it yourself, outside the crate". That is not currently possible for the N-team case, because `predict_outcome`'s own maths depends on `Gaussian::forget`: ```rust // history.rs:573 .fold(crate::N00, |acc, g| acc + g.forget(self.beta.powi(2))) ``` and `forget`, `exclude` and `delta` are all `pub(crate)` (`gaussian.rs:123`, `:130`, `:144`). So a downstream crate cannot inflate a posterior by performance noise, and therefore cannot derive outcome probabilities itself for any shape the crate does not already provide. That combination — no N-team probability, and no public primitive to build one — is what makes this a crate-level gap rather than a downstream inconvenience. ## What would help, in rough order of value 1. **Expose the arithmetic.** Make `Gaussian::forget` (and arguably `exclude`) public. Smallest possible change; unblocks downstream experimentation immediately and commits the crate to nothing. 2. **N-team outcome probabilities** — #21. With 1 and 2, a downstream EIG is straightforward to write, if expensive. 3. **A first-class acquisition utility**, e.g. ```rust pub fn expected_information_gain<T: Time, D: Drift<T>>( teams: &[&[Rating<T, D>]], options: &GameOptions, ) -> Result<f64, InferenceError>; ``` enumerating the outcomes of the given shape, weighting each by its probability, and returning expected KL or expected variance reduction. This is where the crate could genuinely lead — TrueSkill implementations almost universally stop at `quality()`, which only answers "is this matchup fair", not "is this matchup informative". Those coincide for two evenly-matched players and diverge sharply everywhere else, including for the "pick the worst of N" shapes we are moving toward. Options 1 and 2 are enough to unblock lester-stash. Option 3 is the one worth doing properly, and it deserves its own design discussion rather than being bolted on. ## Note on cost EIG is inherently more expensive than `quality()` — it needs one hypothetical inference per outcome, so a naive selector over all candidate pairs is O(n² · outcomes) inferences. A useful implementation probably wants to be explicit about that cost, and a `quality()`-style cheap pre-filter to shortlist candidates before scoring them properly is likely the practical pattern. Worth stating in the API docs whichever way it lands, so callers do not discover it in production. ## Caveat worth building against This crate's recurring defect has been *a public surface that returns a plausible constant* — several instances have been found and fixed. An acquisition function is especially exposed to that failure mode, because a subtly wrong EIG still returns finite, plausible, monotone-looking numbers and simply selects slightly worse matchups forever. Whatever lands here should carry a test that a constant return value would fail: e.g. EIG for an even matchup must exceed EIG for a hopelessly lopsided one, and EIG must fall as both participants' σ falls.

logaritmisk commented

2026-09-07 12:29:09 +00:00

Audited this against main @ 87fca8d and tested the central premise by building the thing this issue says cannot be built. The source-level facts all hold, but the headline claim — that the downstream workaround is blocked — is wrong, and the priority order should change as a result.

Confirmed

forget, exclude, delta, variance, from_mv are all pub(crate) (src/gaussian.rs:123,130,144).
predict_outcome hard-asserts two teams (src/history.rs:563) and allocates no mass to a draw.
Nothing in the crate does EIG, entropy, or variance reduction.
The critique of the heuristic is correct: quality() peaks on fairness, and multiplying by σ²·σ² double-counts uncertainty rather than composing with it.

The downstream workaround is not blocked

Gaussian::from_ms, mu() and sigma() are all public, so g.forget(β²) is reconstructible as:

Gaussian::from_ms(g.mu(), (g.sigma().powi(2) + beta * beta).sqrt())

I wrote a complete pairwise EIG in examples/ — which links the crate as an external consumer, public API only — and it runs today on 0.3.0. current_skill → Rating::new → Game::one_v_one per outcome → analytic Gaussian KL from public mu()/sigma() covers the whole pipeline:

even + uncertain (sigma 6.0) : 0.370639 nats
even + confident (sigma 0.5) : 0.065779 nats
lopsided (mu +/-12, sigma 6) : 0.012714 nats

predict_outcome internal: 0.8234950724
rebuilt from public API : 0.8234950724
abs diff                : 0.000e0

The reconstructed P(outcome) is bit-identical to History::predict_outcome. So proposal 1 — "expose forget, smallest possible change, unblocks downstream experimentation immediately" — unblocks nothing that is currently blocked. It saves a sqrt round-trip and a rediscovered edge-case guard. Worth doing on ergonomic grounds; not worth doing under the banner of unblocking, because shipping it as the unblock would ship a false premise.

What is actually blocked, and it is narrower

N-team P(outcome). Real. There is no public primitive to build it either — quality() returns draw probability, not the probability of a specific ranking, so it is not a substitute. This is #21 item 1.
Draw mass. Sharper than this issue states: even in the 2-team case, if p_draw > 0 then predict_outcome returns [p, 1-p] with nothing for the draw, so the outcome enumeration does not sum over the real outcome space and every EIG weight built on it is wrong. Also #21 item 1.

So #39 depends on #21 not as "N-team would be nice to have eventually", but as "the outcome distribution is incomplete for any draw-enabled model, at any team count". That is the actual crate-level gap.

The caveat is better founded than stated — use a hard bound, not a monotonicity relation

This issue asks for a test that a plausible constant would fail, and proposes "even > lopsided" and "EIG falls as σ falls". Both are worth having. There is a much stronger one available:

EIG is the mutual information between the observed outcome and the skills. For a binary outcome it therefore cannot exceed H(outcome) ≤ ln 2 ≈ 0.6931 nats, whatever the ratings.

That is an analytic ceiling rather than a relation between fixtures, and it earned its keep on first contact. My initial run had a sign error in the normal tail — it weighted the rare upset with the likely outcome's probability — and produced:

lopsided (mu +/-12, sigma 6) : 4.774960 nats

Finite, plausible, and monotone in the right direction against the confident fixture. Exactly the failure mode this issue warns about. The proposed "even > lopsided" check did catch it, but only through the luck of that particular fixture; the ln 2 bound catches it unconditionally. It belongs in the acceptance criteria, generalised to ln(k) for a k-outcome shape.

One datum in support of the motivating argument

The heuristic and EIG disagree on ranking, not merely on scale — so the heuristic is not a monotone transform of EIG and does select different matchups:

fixture	heuristic `quality·σa²·σb²`	EIG (nats)
even + uncertain (σ 6.0)	213.061088	0.370639
even + confident (σ 0.5)	0.055902	0.065779
lopsided (μ ±12, σ 6)	4.347874	0.012714

The heuristic ranks the lopsided matchup ~78× above the confident-but-even one; EIG ranks it ~5× below. That is the claim this issue could previously only assert.

Suggested revision to the plan

Land #21 item 1 first — predict_outcome → Result, N teams, draw mass accounted for. Everything here is downstream of it, including the pairwise case whenever p_draw > 0.
Then take the design call on whether an acquisition function belongs in the crate, with the ln k bound and the ranking-disagreement result as its acceptance tests.
Demote "expose forget/exclude" to an ergonomic nicety, decoupled from this issue's rationale.

Audited this against `main` @ `87fca8d` and tested the central premise by building the thing this issue says cannot be built. The source-level facts all hold, but the **headline claim — that the downstream workaround is blocked — is wrong**, and the priority order should change as a result. ## Confirmed - `forget`, `exclude`, `delta`, `variance`, `from_mv` are all `pub(crate)` (`src/gaussian.rs:123,130,144`). - `predict_outcome` hard-asserts two teams (`src/history.rs:563`) and allocates no mass to a draw. - Nothing in the crate does EIG, entropy, or variance reduction. - The critique of the heuristic is correct: `quality()` peaks on *fairness*, and multiplying by `σ²·σ²` double-counts uncertainty rather than composing with it. ## The downstream workaround is not blocked `Gaussian::from_ms`, `mu()` and `sigma()` are all public, so `g.forget(β²)` is reconstructible as: ```rust Gaussian::from_ms(g.mu(), (g.sigma().powi(2) + beta * beta).sqrt()) ``` I wrote a complete pairwise EIG in `examples/` — which links the crate as an external consumer, public API only — and it runs today on 0.3.0. `current_skill` → `Rating::new` → `Game::one_v_one` per outcome → analytic Gaussian KL from public `mu()`/`sigma()` covers the whole pipeline: ``` even + uncertain (sigma 6.0) : 0.370639 nats even + confident (sigma 0.5) : 0.065779 nats lopsided (mu +/-12, sigma 6) : 0.012714 nats predict_outcome internal: 0.8234950724 rebuilt from public API : 0.8234950724 abs diff : 0.000e0 ``` The reconstructed `P(outcome)` is **bit-identical** to `History::predict_outcome`. So proposal 1 — "expose `forget`, smallest possible change, unblocks downstream experimentation immediately" — unblocks nothing that is currently blocked. It saves a `sqrt` round-trip and a rediscovered edge-case guard. Worth doing on ergonomic grounds; not worth doing under the banner of unblocking, because shipping it as the unblock would ship a false premise. ## What is actually blocked, and it is narrower 1. **N-team `P(outcome)`.** Real. There is no public primitive to build it either — `quality()` returns draw probability, not the probability of a specific ranking, so it is not a substitute. This is #21 item 1. 2. **Draw mass.** Sharper than this issue states: even in the **2-team** case, if `p_draw > 0` then `predict_outcome` returns `[p, 1-p]` with nothing for the draw, so the outcome enumeration does not sum over the real outcome space and every EIG weight built on it is wrong. Also #21 item 1. So #39 depends on #21 not as "N-team would be nice to have eventually", but as **"the outcome distribution is incomplete for any draw-enabled model, at any team count"**. That is the actual crate-level gap. ## The caveat is better founded than stated — use a hard bound, not a monotonicity relation This issue asks for a test that a plausible constant would fail, and proposes "even > lopsided" and "EIG falls as σ falls". Both are worth having. There is a much stronger one available: > EIG is the mutual information between the observed outcome and the skills. For a binary outcome it therefore **cannot exceed `H(outcome) ≤ ln 2 ≈ 0.6931` nats**, whatever the ratings. That is an analytic ceiling rather than a relation between fixtures, and it earned its keep on first contact. My initial run had a sign error in the normal tail — it weighted the rare upset with the likely outcome's probability — and produced: ``` lopsided (mu +/-12, sigma 6) : 4.774960 nats ``` Finite, plausible, and monotone in the right direction against the confident fixture. Exactly the failure mode this issue warns about. The proposed "even > lopsided" check did catch it, but only through the luck of that particular fixture; the `ln 2` bound catches it unconditionally. It belongs in the acceptance criteria, generalised to `ln(k)` for a k-outcome shape. ## One datum in support of the motivating argument The heuristic and EIG **disagree on ranking**, not merely on scale — so the heuristic is not a monotone transform of EIG and does select different matchups: | fixture | heuristic `quality·σa²·σb²` | EIG (nats) | |---|---|---| | even + uncertain (σ 6.0) | 213.061088 | 0.370639 | | even + confident (σ 0.5) | 0.055902 | **0.065779** | | lopsided (μ ±12, σ 6) | **4.347874** | 0.012714 | The heuristic ranks the lopsided matchup ~78× above the confident-but-even one; EIG ranks it ~5× below. That is the claim this issue could previously only assert. ## Suggested revision to the plan 1. **Land #21 item 1 first** — `predict_outcome` → `Result`, N teams, draw mass accounted for. Everything here is downstream of it, *including* the pairwise case whenever `p_draw > 0`. 2. **Then** take the design call on whether an acquisition function belongs in the crate, with the `ln k` bound and the ranking-disagreement result as its acceptance tests. 3. Demote "expose `forget`/`exclude`" to an ergonomic nicety, decoupled from this issue's rationale.

logaritmisk referenced this issue from a commit

2026-09-07 12:59:46 +00:00

feat!: N-team outcome prediction with draw mass, replacing the 2-team panic

logaritmisk commented

2026-09-07 13:04:08 +00:00

The blocker is fixed. #21 is closed as of 507894d on main, and with it both of the things this issue actually depended on.

What changed

History::predict_outcome now returns Result<Prediction, InferenceError>, supports N teams, and accounts for p_draw. Two cheaper entry points sit beside it:

method	answers	cost
`predict_win_probabilities(teams)`	`P(team i finishes strictly first)`	quadratic in team count, ~µs
`predict_ranking(teams, ranks)`	one specific finishing order	`O(teams × grid)`, ~1 ms
`predict_outcome(teams)`	the full distribution over finishing orders	factorial; capped at `MAX_PREDICTED_TEAMS` (6) with a `TooManyTeams` error

Prediction hands back rank vectors in exactly the shape Outcome::ranking takes, so an outcome from a prediction feeds straight into Game::ranked — which is the loop an EIG needs.

Unknown keys are now an error rather than being silently dropped, so a candidate matchup involving someone the history has never seen fails loudly instead of scoring well.

Two corrections to this issue's premises

1. Proposal 1 was unnecessary and has not been done. Making Gaussian::forget public was listed here as the smallest change that "unblocks downstream experimentation immediately". As set out above, it unblocked nothing: from_ms, mu() and sigma() are public, so forget was always reconstructible, and a working pairwise EIG ran against the unmodified 0.3.0 public API. forget/exclude remain pub(crate). If they are ever exposed it should be on ergonomic grounds, not as a fix for a problem that did not exist.

2. The N-team maths is not what this issue assumed, and is much better. The framing here — and my own first framing — treated N-team outcome probabilities as intractable. They are not:

Who finishes first separates into a one-dimensional integral, because performances are independent Gaussians. No multivariate orthant probability is involved. Adaptive Gauss–Kronrod evaluates it to ~1e-15, matching the exact two-team closed form.
A full finishing order is not a general orthant integral either, because the factor graph only ever constrains rank-adjacent teams. That chain collapses into a sequential recursion over cumulative integrals, O(teams × grid) per order, converging as O(h²) to ~1e-7.

Both are exact and deterministic — no sampler, no new dependency, and no per-call variation. That matters here specifically: a Monte Carlo P(outcome) would have put sampling noise directly into every EIG weight, and an acquisition function that returns a slightly different ranking each call is very hard to debug.

One trap worth recording, because it is the exact failure mode this issue warns about. Fixed-node Gauss–Hermite is the obvious tool for the first integral and is wrong: when one team's σ is small the CDF product becomes a step narrower than the node spacing and the nodes step straight over it. Measured 4.4e-4 off the closed form on a mildly skewed matchup and 1.7e-2 on a small-σ one — finite, plausible, monotone in the right direction, and silently wrong. Adaptive refinement is what makes that case safe; win_probabilities_survive_a_rival_with_a_tiny_sigma pins it down.

On the acceptance test this issue asked for

The suggested checks (even > lopsided, EIG falls as σ falls) are worth having but are fixture-dependent. Two stronger ones are now available:

Σ P(outcome) = 1. The outcome space is exhaustive and disjoint by construction, so any drift from one is integration error and nothing else. No golden values needed. Gauss–Hermite failed it at 4.4e-4; the shipped method holds it to ~1e-9. Prediction::total() exposes it deliberately for this purpose.
EIG ≤ ln k. Expected information gain is the mutual information between the observed outcome and the skills, so it cannot exceed the entropy of the outcome variable — ln 2 ≈ 0.6931 nats for a two-way result, ln k for k outcomes. This is an analytic ceiling, not a relation between fixtures. It caught a sign error in my own prototype that produced 4.77 nats while passing the "even > lopsided" check.

The ln k bound is the one that generalises, and it is what an acquisition function should be tested against.

**The blocker is fixed.** #21 is closed as of `507894d` on `main`, and with it both of the things this issue actually depended on. ## What changed `History::predict_outcome` now returns `Result<Prediction, InferenceError>`, supports N teams, and accounts for `p_draw`. Two cheaper entry points sit beside it: | method | answers | cost | |---|---|---| | `predict_win_probabilities(teams)` | `P(team i finishes strictly first)` | quadratic in team count, ~µs | | `predict_ranking(teams, ranks)` | one specific finishing order | `O(teams × grid)`, ~1 ms | | `predict_outcome(teams)` | the full distribution over finishing orders | factorial; capped at `MAX_PREDICTED_TEAMS` (6) with a `TooManyTeams` error | `Prediction` hands back rank vectors in exactly the shape `Outcome::ranking` takes, so an outcome from a prediction feeds straight into `Game::ranked` — which is the loop an EIG needs. Unknown keys are now an error rather than being silently dropped, so a candidate matchup involving someone the history has never seen fails loudly instead of scoring well. ## Two corrections to this issue's premises **1. Proposal 1 was unnecessary and has not been done.** Making `Gaussian::forget` public was listed here as the smallest change that "unblocks downstream experimentation immediately". As set out [above](#issuecomment-27620), it unblocked nothing: `from_ms`, `mu()` and `sigma()` are public, so `forget` was always reconstructible, and a working pairwise EIG ran against the unmodified 0.3.0 public API. `forget`/`exclude` remain `pub(crate)`. If they are ever exposed it should be on ergonomic grounds, not as a fix for a problem that did not exist. **2. The N-team maths is not what this issue assumed, and is much better.** The framing here — and my own first framing — treated N-team outcome probabilities as intractable. They are not: - **Who finishes first** separates into a *one-dimensional* integral, because performances are independent Gaussians. No multivariate orthant probability is involved. Adaptive Gauss–Kronrod evaluates it to ~1e-15, matching the exact two-team closed form. - **A full finishing order** is not a general orthant integral either, because the factor graph only ever constrains rank-*adjacent* teams. That chain collapses into a sequential recursion over cumulative integrals, `O(teams × grid)` per order, converging as `O(h²)` to ~1e-7. Both are **exact and deterministic** — no sampler, no new dependency, and no per-call variation. That matters here specifically: a Monte Carlo `P(outcome)` would have put sampling noise directly into every EIG weight, and an acquisition function that returns a slightly different ranking each call is very hard to debug. One trap worth recording, because it is the exact failure mode this issue warns about. Fixed-node Gauss–Hermite is the obvious tool for the first integral and is wrong: when one team's σ is small the CDF product becomes a step narrower than the node spacing and the nodes step straight over it. Measured **4.4e-4** off the closed form on a mildly skewed matchup and **1.7e-2** on a small-σ one — finite, plausible, monotone in the right direction, and silently wrong. Adaptive refinement is what makes that case safe; `win_probabilities_survive_a_rival_with_a_tiny_sigma` pins it down. ## On the acceptance test this issue asked for The suggested checks (even > lopsided, EIG falls as σ falls) are worth having but are fixture-dependent. Two stronger ones are now available: - **`Σ P(outcome) = 1`.** The outcome space is exhaustive and disjoint by construction, so any drift from one is integration error and nothing else. No golden values needed. Gauss–Hermite failed it at 4.4e-4; the shipped method holds it to ~1e-9. `Prediction::total()` exposes it deliberately for this purpose. - **`EIG ≤ ln k`.** Expected information gain is the mutual information between the observed outcome and the skills, so it cannot exceed the entropy of the outcome variable — `ln 2 ≈ 0.6931` nats for a two-way result, `ln k` for k outcomes. This is an analytic ceiling, not a relation between fixtures. It caught a sign error in my own prototype that produced **4.77 nats** while passing the "even > lopsided" check. The `ln k` bound is the one that generalises, and it is what an acquisition function should be tested against. ## Next Starting on proposal 3, the first-class acquisition utility. Proposal 1 is closed as unnecessary; proposal 2 is done.

logaritmisk referenced this issue from a commit

2026-09-07 13:10:26 +00:00

feat: add expected information gain for active matchup selection

logaritmisk commented

2026-09-07 13:10:51 +00:00

Done, as of 3c2f9ac on main. Closing.

What landed

expected_information_gain(teams, options) — the standalone signature proposed here — plus History::expected_information_gain(teams), which uses each competitor's current skill as the prior along with the history's own beta, drift and p_draw, so the outcomes it weighs are the ones that would actually be fitted if the matchup were played and recorded.

Also documented in the README under Which match to play next, with the cost characteristics stated on the public API rather than left to be discovered in production.

The three proposals

#	proposal	outcome
1	expose `Gaussian::forget` / `exclude`	not done — unnecessary
2	N-team outcome probabilities	done in #21
3	first-class acquisition utility	done here

Proposal 1 is deliberately not done. It was listed as the change that "unblocks downstream experimentation immediately", and it unblocked nothing: from_ms, mu() and sigma() are public, so forget was always reconstructible in one line, and a working pairwise EIG ran against unmodified 0.3.0 using only the public API. Shipping it under that banner would have shipped a false premise. If those are ever exposed it should be on ergonomic grounds, as its own issue.

Measured behaviour

even sigma=25 : 0.382434 nats     lopsided (mu +/-12, sigma 6) : 0.012714 nats
even sigma=6  : 0.370639 nats     hopeless (mu +/-40, sigma 1) : 0.000000 nats
even sigma=0.5: 0.065779 nats     ceiling  ln 2                : 0.693147

even sigma=6 : 0.370639 is bit-identical to the throwaway prototype run earlier in this issue, which used a different erfc, a hand-written KL, and only the public API of the unmodified crate. Two independent implementations agreeing to six decimal places is the strongest evidence available that the value is correct.

On the caveat this issue raised

The concern was exactly right, and it is the reason for the test design. An acquisition function is unusually exposed to returning finite, plausible, monotone numbers while being wrong, because a subtly wrong EIG does not crash — it selects slightly worse matchups forever.

The two checks suggested here (even > lopsided, gain falls as σ falls) are both implemented, but both are fixture-dependent. The load-bearing test is the analytic one:

EIG ≤ ln k. Information gain is the mutual information between the observed outcome and the skills, so it cannot exceed the entropy of the thing being observed — ln 2 for a two-way result, ln 3 once draws are possible, ln k for k outcomes.

This is a ceiling rather than a relation between fixtures, and it earned its place: the prototype above returned 4.77 nats from a sign error in the normal tail while passing the "even > lopsided" check by luck of the fixture. never_exceeds_the_entropy_of_the_outcome catches that class unconditionally. At 0.38 against a 0.69 ceiling the bound is meaningful rather than vacuous.

disagrees_with_the_quality_times_variance_heuristic pins down that this is not a monotone transform of quality * sigma_a^2 * sigma_b^2 — the two rank a lopsided matchup and a confident even one in opposite orders — so a later simplification cannot quietly revert to the heuristic.

One deliberate omission

The expected-variance-reduction proxy is mentioned here as "a cheaper and often sufficient" alternative. It is not cheaper: it needs the same hypothetical posteriors, so it shares the entire dominant cost and saves only the closing arithmetic. Rather than ship a second metric implying a tradeoff that does not exist, the API documents that the dominant cost is one inference pass per outcome, and points at the practical pattern this issue anticipated — shortlist with quality() or predict_win_probabilities, then score only the shortlist.

If a variance-reduction figure is wanted as an alternative output rather than as a cheaper path, that is worth its own issue.

Done, as of `3c2f9ac` on `main`. Closing. ## What landed `expected_information_gain(teams, options)` — the standalone signature proposed here — plus `History::expected_information_gain(teams)`, which uses each competitor's current skill as the prior along with the history's own `beta`, `drift` and `p_draw`, so the outcomes it weighs are the ones that would actually be fitted if the matchup were played and recorded. Also documented in the README under *Which match to play next*, with the cost characteristics stated on the public API rather than left to be discovered in production. ## The three proposals | # | proposal | outcome | |---|---|---| | 1 | expose `Gaussian::forget` / `exclude` | **not done — unnecessary** | | 2 | N-team outcome probabilities | done in #21 | | 3 | first-class acquisition utility | done here | Proposal 1 is deliberately not done. It was listed as the change that "unblocks downstream experimentation immediately", and it unblocked nothing: `from_ms`, `mu()` and `sigma()` are public, so `forget` was always reconstructible in one line, and a working pairwise EIG ran against unmodified 0.3.0 using only the public API. Shipping it under that banner would have shipped a false premise. If those are ever exposed it should be on ergonomic grounds, as its own issue. ## Measured behaviour ``` even sigma=25 : 0.382434 nats lopsided (mu +/-12, sigma 6) : 0.012714 nats even sigma=6 : 0.370639 nats hopeless (mu +/-40, sigma 1) : 0.000000 nats even sigma=0.5: 0.065779 nats ceiling ln 2 : 0.693147 ``` `even sigma=6 : 0.370639` is bit-identical to the throwaway prototype run [earlier in this issue](#issuecomment-27620), which used a different `erfc`, a hand-written KL, and only the public API of the unmodified crate. Two independent implementations agreeing to six decimal places is the strongest evidence available that the value is correct. ## On the caveat this issue raised The concern was exactly right, and it is the reason for the test design. An acquisition function is unusually exposed to returning finite, plausible, monotone numbers while being wrong, because a subtly wrong EIG does not crash — it selects slightly worse matchups forever. The two checks suggested here (even > lopsided, gain falls as σ falls) are both implemented, but both are fixture-dependent. The load-bearing test is the analytic one: > **`EIG ≤ ln k`.** Information gain is the mutual information between the observed outcome and the skills, so it cannot exceed the entropy of the thing being observed — `ln 2` for a two-way result, `ln 3` once draws are possible, `ln k` for k outcomes. This is a ceiling rather than a relation between fixtures, and it earned its place: the prototype above returned **4.77 nats** from a sign error in the normal tail while passing the "even > lopsided" check by luck of the fixture. `never_exceeds_the_entropy_of_the_outcome` catches that class unconditionally. At 0.38 against a 0.69 ceiling the bound is meaningful rather than vacuous. `disagrees_with_the_quality_times_variance_heuristic` pins down that this is not a monotone transform of `quality * sigma_a^2 * sigma_b^2` — the two rank a lopsided matchup and a confident even one in opposite orders — so a later simplification cannot quietly revert to the heuristic. ## One deliberate omission The expected-variance-reduction proxy is mentioned here as "a cheaper and often sufficient" alternative. It is **not cheaper**: it needs the same hypothetical posteriors, so it shares the entire dominant cost and saves only the closing arithmetic. Rather than ship a second metric implying a tradeoff that does not exist, the API documents that the dominant cost is one inference pass per outcome, and points at the practical pattern this issue anticipated — shortlist with `quality()` or `predict_win_probabilities`, then score only the shortlist. If a variance-reduction figure is wanted as an alternative *output* rather than as a cheaper path, that is worth its own issue.

logaritmisk closed this issue

2026-09-07 13:10:54 +00:00

logaritmisk added the enhancement label 2026-09-07 13:53:42 +00:00

logaritmisk referenced this issue

2026-09-07 21:27:06 +00:00

`expected_information_gain` is discrete-outcome only, so scored consumers cannot ask "which matchup next?" #49

Sign in to join this conversation.

1 Participants

Notifications

Due Date

No due date set.

Dependencies

No dependencies set.

Reference: logaritmisk/trueskill-tt#39