Book contents
Contents
raw Math
RAW Book Machine Learning Bayesian Inference

TrueSkill: Learning from Game Results

Robert Eisele

A win is evidence about skill, not a direct measurement of it. TrueSkill turns that evidence into two quantities: an estimate of ability and an explicit account of uncertainty.

This chapter builds the classic TrueSkill model from the game outcome backward. We will separate lasting skill from match-to-match performance, turn a team result into a truncated Gaussian, derive the resulting rating update, and see why larger ranked matches require approximate inference.

Two skill beliefs and a match result Player A and player B have overlapping distributions of skill. One observed result shifts both beliefs without revealing either exact skill. A result changes belief, not ability lower skillhigher skill before after observing a win uncertainty remains
A rating is a distribution over plausible skills. The plotted update is schematic; the calculator below uses the equations derived here.

One number cannot express what we know

Suppose two players both have estimated skill 25. One is new, so the estimate could plausibly be much too low or much too high. The other has hundreds of consistent results. Giving them the same point score hides an important difference: how much the next result should change our minds.

TrueSkill represents a player's skill with a Gaussian belief

\[s_i\sim\mathcal N(\mu_i,\sigma_i^2).\]

The mean \(\mu_i\) is the current center of belief. The standard deviation \(\sigma_i\) describes uncertainty about the player's lasting skill. It is not the player's variability from one match to another. That second kind of variation enters separately as performance noise.

Same mean, different skill uncertainty Two normal curves have the same mean. The broad curve represents uncertain skill; the narrow curve represents a well-established estimate. same estimated mean μ Broad: large σ, few informative gamesNarrow: small σ, many consistent results
A large \(\sigma\) gives new evidence more leverage. A small \(\sigma\) makes the estimate more resistant to any one result.

From lasting skill to one match

To reason backward from a result, first describe how a result could be generated. A player's match performance fluctuates around their skill:

\[p_i\mid s_i\sim\mathcal N(s_i,\beta^2).\]

Here \(\beta\) measures performance noise. Even if skill were known perfectly, a single performance would still vary. Conversely, \(\sigma_i\) measures uncertainty about skill before seeing the match. The model keeps these sources of spread separate.

TrueSkill's generative path A skill belief combines with performance noise to produce a match performance, which contributes to a team score and then a ranked outcome. Skill beliefμ, σ Performanceskill + noise β Team scoresum of members Observed rankwin, draw, loss Inference runs in the opposite direction: from rank evidence back to skill beliefs.
The generative model separates what exists (skill), what varies during play (performance), and what we actually observe (rank).

A team result becomes one noisy difference

For a team, the classic model sums member performances. Let \(k_i=+1\) for a player on team A and \(k_i=-1\) for a player on team B. The difference between team performances is

\[D=\sum_i k_i p_i.\]

Independent Gaussian variables remain Gaussian when added. Before the result, therefore,

\[D\sim\mathcal N(m,c^2),\qquad m=\sum_i k_i\mu_i,\qquad c^2=\sum_i(\sigma_i^2+\tau^2)+\beta^2(n_A+n_B).\]

The optional \(\tau\) term allows skill to drift between matches; this chapter's single-match calculator sets \(\tau=0\). For a one-on-one match, the variance reduces to \(c^2=\sigma_A^2+\sigma_B^2+2\beta^2\). A positive \(D\) favors team A.

Two performances reduce to one difference The two team scores are subtracted. Their means subtract, while independent uncertainty from both teams and performance noise adds to the variance. Team A scoreTeam B score − One Gaussian difference D = team A − team B mean: subtract · variance: add independent sources
Even a multi-player contest contributes a scalar comparison at this stage. The later challenge is distributing that evidence back to the individual players.

A result cuts the difference distribution

A win does not tell us the exact performance gap. With draw margin \(\epsilon\), it tells us only that \(D>\epsilon\); a loss means \(D<-\epsilon\); a draw means \(-\epsilon\le D\le\epsilon\). These events slice the prior Gaussian into regions.

For a one-on-one match, the predicted probabilities follow from its cumulative distribution function:

\[\begin{aligned}P(A\text{ wins})&=1-\Phi\!\left(\frac{\epsilon-m}{c}\right),\\P(\text{draw})&=\Phi\!\left(\frac{\epsilon-m}{c}\right)-\Phi\!\left(\frac{-\epsilon-m}{c}\right),\\P(B\text{ wins})&=\Phi\!\left(\frac{-\epsilon-m}{c}\right).\end{aligned}\]

The draw margin is a game rule, not a universal constant. If the desired draw probability for two equally skilled players with known skill is \(p_{\rm draw}\), a common calibration is \(\epsilon=\sqrt{2}\,\beta\,\Phi^{-1}((1+p_{\rm draw})/2)\). The calculator uses this convention and displays the resulting margin.

Wins, draws and losses partition a Gaussian A normal performance-difference curve is divided by two draw-margin thresholds into loss, draw and win regions. B winsdrawA wins −ε+εD ∼ N(m, c²)
Each possible outcome is an event about a hidden performance difference. The shaded draw region has finite width only when the game allows draws.

The update comes from the truncated normal

Standardize the difference with \(Z=(D-m)/c\), so \(Z\sim\mathcal N(0,1)\). For an A win, the event is \(Z>a\), where \(a=(\epsilon-m)/c\). Define the inverse Mills ratio and its variance correction:

\[v=\frac{\phi(a)}{1-\Phi(a)},\qquad w=v(v-a).\]

Conditioning a Gaussian on this half-line shifts its mean by \(cv\) and reduces its variance by the fraction \(w\):

\[\mathbb E[D\mid A\text{ wins}]=m+cv,\qquad\operatorname{Var}(D\mid A\text{ wins})=c^2(1-w).\]

A draw is a two-sided truncation. Let \(a=(-\epsilon-m)/c\), \(b=(\epsilon-m)/c\), and \(Z_0=\Phi(b)-\Phi(a)\). Then

\[v=\frac{\phi(a)-\phi(b)}{Z_0},\qquad w=v^2+\frac{b\phi(b)-a\phi(a)}{Z_0}.\]

The same \(v,w\) summarize the truncated difference for any two-team outcome. Each player's skill is correlated with that difference, so the information flows back in proportion to the player's prior variance:

\[\boxed{\mu_i'=\mu_i+k_i\frac{\sigma_i^2}{c}v,\qquad (\sigma_i')^2=\sigma_i^2\left(1-\frac{\sigma_i^2}{c^2}w\right).}\]

For one match, these are the exact first two marginal moments under the Gaussian model. They do not mean the full posterior is still Gaussian: conditioning induces skew and correlations between teammates and opponents. Keeping independent Gaussians with these moments is a compact approximation for future matches.

1 · Modelskill to performance
2 · Compareteam difference
3 · Observewin, draw or loss
4 · Truncatecondition the Gaussian
5 · Updatemeans and uncertainty

A numerical check

Take two equally rated players with \(\mu=25\), \(\sigma=25/3\), performance noise \(\beta=25/6\), and no draw margin. After an A win, the equations give approximately \(\mu_A'=29.205\), \(\mu_B'=20.795\), and \(\sigma_A' = \sigma_B' = 7.194\). The estimates move apart, while both become more certain. The workbench reproduces this case.

Change the assumptions, watch the update

This local workbench computes the predicted result probabilities and exact first two skill moments for one A-versus-B match. Change the priors or select an outcome. No data leaves the browser.

Two-player TrueSkill workbench

The upper panel shows which differences count as the selected result. The lower panels compare each skill belief before and after that observation. Curves are peak-normalized to make their spread legible; the probability figures above use the full densities.
Predicted A win—
Predicted draw—
Predicted B win—
A after · μ / σ—
B after · μ / σ—
Draw margin ε—

Why teams lead to Expectation Propagation

In a single two-team match, the result constrains one Gaussian difference, so the truncated-normal moments give each player's marginal update directly. But the players' skills become correlated: a team win could be explained by one member being stronger than expected, another being weaker than expected, or some combination.

When several teams are ranked, multiple difference constraints share players. The constraints are coupled, and the exact joint posterior is no longer a product of simple Gaussian terms. TrueSkill represents this model as a factor graph and uses Expectation Propagation (EP): each non-Gaussian rank factor is replaced by a Gaussian-shaped message whose moments match the locally conditioned distribution. Messages are revisited until the approximation settles. [Minka2001]

A multi-team comparison couples skill variables Three team performance nodes share rank constraints. Each team depends on multiple skill nodes, so updating one observed ranking couples all the players. SkillsTeam performancesObserved ranks T₁T₂T₃ T₁ > T₂T₂ > T₃ The shared middle team couples both rank constraints; EP passes approximate Gaussian messages.
For more than one comparison, information must travel through the shared skill variables. EP keeps that inference tractable by repeatedly matching local moments.

Expectation Propagation is a general inference method, not the definition of TrueSkill. It is the computational strategy used to approximate posteriors in the richer, coupled ranking model. For a single two-team comparison, the formulas above expose the core Bayesian update directly. The original paper develops the multi-team factor-graph treatment. [Herbrich2006]

What a rating does and does not say

A rating is conditional on the model: its outcome rules, draw margin, performance noise, population assumptions, and history. It is not an objective measurement of a person's worth, nor does a team win identify the contribution of each teammate.

Classic TrueSkill primarily learns from final standings. It does not treat a 1-point win and a 20-point win as different evidence unless the model is extended to use score margins. TrueSkill 2 is such an extension: it can incorporate additional player-level observations, rather than only the team's final rank. [MinkaClevenZaykov2018]

For leaderboards, a system may rank players by a conservative score such as \(\mu-3\sigma\), rather than by \(\mu\) alone. That penalizes uncertain estimates; it is a ranking policy built on the belief, not a different estimate of the posterior mean.

The compact idea: model skill as uncertain, model performance as noisy, turn rank into a constraint on performance, then propagate that evidence back to each skill belief. The model learns not just a score, but how confident it should be in that score.

References