PaperlayerView exact revision on arXiv

Source-linked AI summary

Alternative Strategies for Active Learning with Bayesian Bradley Terry Model

Saman Jayasinghe, Sean Walton, Alma Rahat, Andy Gray, Chris Wheadon

arXiv:2610.29416v1cs.LGstat.OT

TL;DR

Recovering rankings from limited pairwise judgements calls for inference that represents uncertainty and selection of informative pairs. The paper proposes a Bayesian Bradley-Terry model with knowledge-gradient pair selection and posterior-based reliability assessment; its theoretical results include posterior variance shrinking at order O(K^-1) in identifiable directions and pairwise contrasts.

  • Problem

    Existing Bayesian comparative-judgement approaches lack a unified framework combining adaptive convergence guarantees, efficient full-ranking pair selection, posterior-based reliability, and robustness analysis.

    Source: §1 · p. 2

  • Method

    The paper develops a hierarchical Bayesian Bradley-Terry model with Polya-Gamma augmentation and three knowledge-gradient acquisition functions for comparative-judgement pair selection.

    Source: §1 · p. 2

  • Results

    Conditional posterior variances of identifiable centered directions and pairwise contrasts are of order O(K^-1).

    Source: §4.2 · p. 19

  • Takeaways & Limitations

    The framework integrates theoretical foundations and practical pair selection for Bayesian Bradley-Terry comparative judgement.

    Source: §1 · p. 2

    For finite K, the marginal posterior is generally non-Gaussian, with asymptotic Gaussianity arising separately as information increases.

    Source: §4.2 · p. 19

Abstract

from arXiv · show

Comparative judgement uses pairwise comparisons to rank items, but recovering accurate rankings from a limited number of judgements depends on both the inference method and the pairs selected. We developed a Bayesian Bradley-Terry model (BBTM) that uses Polya-Gamma data augmentation for efficient Gibbs sampling and quantifies uncertainty in latent abilities and ranks. We propose three active learning strategies based on the knowledge gradient (KG) principle. We define our acquisition functions using Kendall's tau distance, posterior rank entropy, and posterior separation. Approximate one-step updates to posterior moments reduce the computational cost of evaluating candidate pairs. We also introduce Posterior Separation Reliability (PSR), which measures the spread of posterior mean abilities relative to posterior uncertainty. It provides an internal indicator of ranking reliability without requiring a reference ranking. In synthetic experiments covering different item counts, comparison budgets, and noise levels, BBTM generally recovers ranking more accurately than preference-based Bayesian comparative judgement (PBCJ). At low to moderate noise levels, the pairwise entropy pair selection strategy performs best in ranking recovery. However, at the highest noise levels, the KG strategy based on posterior separation produces better point rankings. PSR increases alongside improvements in ranking accuracy as comparisons accumulate. Robustness experiments identify the proportion of informative outcomes needed to meet specified accuracy targets within a fixed comparison budget. In a moderate noise setting, replacing 30\% of outcomes with random choices has little effect on ranking performance. These findings demonstrate the value of Bayesian inference and active learning pair selection for recovering ranks from limited, noisy paired comparisons.

1 Introduction

Recovering reliable rankings from limited, costly pairwise judgments requires both uncertainty-aware inference and informative pair selection. The paper introduces a Bayesian Bradley-Terry framework with active-learning strategies, posterior reliability assessment, and convergence guarantees under adaptive selection.

1 Introduction

  • The paper identifies four gaps in Bayesian comparative judgement: adaptive convergence guarantees, efficient full-ranking pair selection, posterior-based reliability, and robustness analysis.BBTM is presented as a framework integrating theoretical foundations and practical pair selection.Source: §1 · p. 2
  • The hierarchical Bayesian Bradley-Terry model uses Polya-Gamma augmentation for Gibbs sampling and quantifies uncertainty in item strengths with sequential updating.Hierarchical shrinkage through borrowing strength is proposed to improve estimates when comparisons are sparse or limited.Source: §1 · p. 2
  • The paper gives convergence guarantees under adaptive pair selection using posterior consistency and the Bernstein-von Mises theorem, with ε-greedy exploration meeting the conditions.It also proposes a near-optimal mixture of informative human judgments and random outcomes to reduce reliance on costly judgments while producing accurate rankings.Source: §1 · pp. 2–3
  • Three knowledge-gradient acquisition functions target expected rank disruption, rank-entropy reduction, and improvement in reliability for comparative judgement pair selection.The strategies are tailored to ranking objectives in the comparative-judgement framework.Source: §1 · p. 2
  • Gaussian moment matching approximates one-step look-ahead values instead of nested MCMC sampling, enabling scalable knowledge-gradient pair selection.The approximation is used across multiple acquisition functions.Source: §1 · pp. 2–3
  • Posterior Separation Reliability (PSR) is introduced as a posterior-based reliability measure compatible with traditional Scale Separation Reliability.The contribution states that PSR is computed from the posterior distribution.Source: §1 · p. 3

2 Background and Literature Review

The review traces how paired comparisons support ranking when absolute scoring is difficult, then surveys Bayesian inference, reliability measures, and knowledge-gradient selection. It positions the paper's framework against limitations in uncertainty assessment and global ranking objectives.

2.1 Paired comparisons and Comparative Judgment

  • Comparative judgement replaces absolute marks with pairwise choices, converting incomplete and noisy comparisons into rankings of work.The review describes paired comparison as a way to measure latent qualities when absolute scoring is difficult.Source: §2.1 · p. 4

2.2 The Bradley Terry Model for Ranking Paired Comparisons

  • The classical Bradley-Terry model links pairwise preference probabilities to latent item strengths, but sparse graphs can destabilize estimates and point estimates omit full uncertainty over strengths or ranks.Its standard form also lacks direct guidance for choosing the next pair in adaptive comparative judgement.Source: §2.2 · p. 4

2.3 Bayesian Bradley Terry Model

  • Bayesian Bradley-Terry inference places priors on latent strengths and uses posterior distributions to quantify uncertainty, regularize sparse comparisons, and support sequential updating.The paper's implementation uses Polya-Gamma augmentation for Gibbs sampling.Source: §2.3 · p. 5

2.4 Bayesian Comparative Judgment in Education

  • Bayesian comparative judgement can provide posterior rank distributions and entropy-based pair selection, but existing approaches emphasize local uncertainty reduction over global ranking accuracy.The review also notes multi-criteria extensions and posterior distributions over item strengths and ranks.Source: §2.4 · pp. 5–6

2.5 Scale Separation Reliability (SSR)

  • Scale Separation Reliability (SSR) is used to assess comparative-judgement reliability, but evidence about its relation to truth is mixed and its interpretation depends on measurement-model parameterization.A review of prior work reports SSR as a proxy for inter-rater agreement, while cautioning against assuming a strict correlation with truth.Source: §2.5 · p. 6

2.6 Knowledge Gradient (KG) Methods

  • Knowledge gradient evaluates expected value across hypothetical outcomes, yet its integration with hierarchical Bayesian Bradley-Terry models for full ranking and reliability remains incomplete.In pairwise comparisons, each observation informs two alternatives; existing Bayesian approaches have partly addressed pair selection but tend to reduce local uncertainty rather than optimize global ranking.Source: §2.6 · pp. 7–8

3 Methodology

The BBTM models pairwise outcomes through latent item abilities and uses Polya-Gamma augmentation for Bayesian inference. Knowledge Gradient pair selection evaluates candidate comparisons by their expected effects on rankings, rank uncertainty, or posterior separation.

3.2.3 Polya Gamma Data Augmentation

  • Polya-Gamma augmentation makes the logistic comparison likelihood conditionally Gaussian, enabling conjugate Gibbs updates for the hierarchical Bayesian model.The model provides posterior inference over item strengths; its hierarchical structure uses shrinkage to improve estimates with sparse or limited comparisons.Source: §3.2.3 · pp. 9–10

3.2.6 Gibbs sampling

  • The four-block Gibbs sampler updates latent Polya-Gamma variables, the direction, and the global scale, and is reported to mix well even with sparse comparison data.The model uses parameter expansion to represent a half-t prior as a scale mixture of conjugate distributions for efficient Gibbs sampling.Source: §3.2.6 · p. 10, §3.2.4 · p. 10

3.2.7 Sigmoid-Normal Approximation

  • Evaluating Knowledge Gradient candidates by separate posterior sampling for each outcome scales quadratically with the number of items, motivating an analytic approximation.The paper gives 10 items as 45 pairs and 90 MCMC runs, versus 20 items as 190 pairs and 380 runs.Source: §3.2.7 · p. 11
  • MacKay’s probit approximation provides a closed-form approximation to the predictive win probability by replacing the intractable logistic-Gaussian convolution.The scaling factor is chosen by matching the sigmoid and probit slopes at the origin.Source: §3.2.7 · p. 11

3.3.1 Mathematical Framework

  • Three Knowledge Gradient utilities target expected Kendall’s tau change, posterior rank entropy reduction, and increased posterior separation.The tau utility favors comparisons expected to disrupt the current rank order; the entropy utility seeks the greatest expected reduction in rank uncertainty.Source: §3.3 · p. 11, §3.3.1 · pp. 12–13

3.3 Novel Pair Selection Methods

  • Knowledge Gradient evaluates both possible outcomes of candidate pairs to estimate their expected effect on the ranking, rather than selecting solely by local pairwise uncertainty.The paper illustrates that a pair with high apparent uncertainty can be less informative about the overall order than another pair.Source: §3.3 · p. 11, §3.3.1 · p. 12

3.4 Fast Knowledge Gradient via One-step Moment updates for BBTM

The paper approximates hypothetical comparison outcomes and posterior updates with analytic moment calculations to make Knowledge Gradient evaluation more efficient. It also describes a robustness experiment and defines Posterior Separation Reliability from posterior means and uncertainty.

3.4 Fast Knowledge Gradient via One-step Moment updates for BBTM

  • One-step analytic moment updates replace nested posterior sampling when evaluating Knowledge Gradient comparisons in Bayesian Bradley-Terry.The paper presents this as its first integration of Knowledge Gradient with Bayesian Bradley-Terry in comparative judgement that avoids nested MCMC sampling.Source: §3.4 · p. 14

The Predictive Distribution and MacKay’s Approximation

3.5 Model Robustness Check

  • The robustness experiment varies the probability α that an outcome reflects true item skills, with the remaining outcomes generated randomly, to assess ranking recovery under noise.The stated objective is to identify the minimum proportion of skill-based outcomes needed to recover an accurate ranking.Source: §3.5 · p. 15

3.6 Posterior Separation Reliability (PSR) for BBTM

  • Posterior Separation Reliability (PSR) measures whether the spread of posterior mean strengths exceeds the average posterior uncertainty across items.Values near 1 indicate strong separation; values near 0 indicate similar separation and uncertainty, while negative values indicate uncertainty exceeds the spread of means.Source: §3.6 · p. 16

4 Convergence of the Bayesian Bradley Terry Model

This section establishes posterior consistency and convergence properties for the Bayesian Bradley–Terry model under the stated comparison-schedule and information assumptions. It also examines contraction and asymptotic normality, and establishes consistency of rankings derived from posterior draws or means.

4 Convergence of the Bayesian Bradley Terry Model

  • Positive long-run frequency for every pair yields posterior consistency; a limiting normalised Fisher information matrix gives a Bernstein-von Mises limit with inverse-information covariance and ranking consistency for strictly separated scores.The convergence argument covers predictable schedules, including random, round-robin, and certain active-learning schemes, without a separate proof for each policy.Source: §4 · p. 17

4.1 Assumptions

  • The assumptions distinguish information sufficient for consistency from a rate-level information limit required for the Bernstein-von Mises theorem; positive frequency for every pair implies the former but not the latter.The theorem is formulated for a fixed finite item set on the centred identifiable subspace, with strictly separated true scores.Source: §4.1 · pp. 17–18

4.2 Foundation Lemmas

  • Polya-Gamma augmentation makes the conditional posterior Gaussian, but the finite-sample marginal posterior remains a generally non-Gaussian scale mixture.The marginal posterior's asymptotic Gaussianity is established separately through the Bernstein-von Mises theorem.Source: §4.2 · pp. 18–19
  • For PG variables drawn from their full conditional distribution, under assumptions 3, 4, 5b, 6, and 7, conditional posterior precision grows linearly on C; conditional variances of identifiable centred directions and pairwise contrasts are O(K−1).Separately, posterior consistency is stated under assumptions 1–4, 5b, 6, and 7, with Π(Aε | yK) = Π(Aε ∩ SM | yK) + Π(Aε \\ SM | yK) → 0.Source: §4.2 · pp. 19, 22, 23
  • Under assumptions 1–7, the adaptive likelihood is locally asymptotically normal, the posterior is locally tight, and the posterior has a Gaussian local limit.The local limit has covariance given by the inverse limiting information matrix.Source: §4.2 · pp. 24–26

4.3 Main theorem

  • Under assumptions 1–4, 5b, 6, and 7, the posterior is consistent and contracts around θ̂K at rate 1/√K; if assumption 5c also holds, the marginal posterior satisfies BvM convergence.Source: §4.3 · p. 26

4.4 Corollary

  • Posterior-draw rankings are consistent under assumptions 1–4, 5b, 6, and 7, and the posterior-mean ranking is frequentist consistent when assumption 5c also holds.The posterior-mean conclusion additionally requires the main theorem to apply.Source: §4.4 · p. 27

5 Experiments and Discussions

Across the synthetic experiments, BBTM outperformed PBCJ at every noise level, while the best pair-selection strategy depended on noise and the ranking metric. Exploration restored the convergence theorem’s pair-coverage condition without harming empirical performance, and PSR rose alongside ranking accuracy as comparisons accumulated.

5.1 Experimental Setup

  • The experiments varied item abilities, item counts, comparison budgets, and outcome noise, then compared BBTM and PBCJ across six pair-selection methods.Each model-method combination was run 50 times on matched generated problems, with ranking accuracy measured by normalised Kendall’s tau distance.Source: §5.1 · p. 28

5.2 Model convergence check

  • At σ = 5.0, BBTM converged faster than PBCJ under KG-SSR, KG-Tau, entropy, and random selection, while the models were comparable under KG-Entropy and no-repeat selection.At σ = 1.25 BBTM was faster across all selectors; at σ = 10.0 it was faster under KG-SSR, entropy, and random selection.Source: §5.2 · p. 28, Figure 1 · p. 29

5.3 Identifying the winning method

  • Across all noise levels, BBTM had fewer losses than PBCJ, with both models performing worst at high item counts and low budgets.The comparison used normalised Kendall’s tau distance across matched seeds; Figure 2 shows the σ = 5.0 pattern.Source: §5.3 · p. 29, Figure 2 · p. 30
  • Entropy selection led at σ ≤ 5.0, but KG-SSR overtook it on all reported metrics at σ = 10.0.At σ = 5.0, entropy outperformed the other BBTM selectors; KG-SSR followed, while KG-Entropy was worst.Source: §5.3 · pp. 29–30

5.4 Empirical validation of the Convergence Theorem

  • With purely greedy selection, entropy and KG-SSR covered 49% and 66% of pairs; at ε = 0.20, coverage rose to 72% and 81%, while KG-Entropy and KG-Tau covered 99% without exploration.Purely greedy selection violated the theorem’s pair-coverage assumption for entropy and KG-SSR; ε-greedy selection met that condition and did not harm empirical ranking performance.Source: §5.4 · p. 31, Figure 3 · p. 31, Figure 4 · p. 31

5.5 Rank Distribution Recovery

  • At σ = 5.0, entropy led in both rank accuracy and rank-distribution recovery, but at σ = 10.0 KG-SSR had better τ while entropy had better JSD.The best selector therefore depended on whether point rankings or full posterior rank distributions were assessed.Source: §5.5 · p. 32, Figure 5 · p. 32

5.6 Posterior Separation Reliability (PSR): Empirical Behaviour and Validity

  • As comparisons accumulated, PSR increased while normalised τ decreased, aligning the posterior-based reliability measure with improved ranking accuracy.PSR is computed from the posterior and tracks latent-strength separation relative to posterior uncertainty.Source: §5.6 · pp. 33–34, Figure 7 · p. 33

5.7 Robustness of the model

  • At σ = 5.0, median τ was 0.044 with either 70% or 100% skill-based outcomes, so 30% random outcomes retained near-optimal ranking accuracy.At σ = 10.0, the τ ≤ 0.05 target was unattainable; the tolerance for random outcomes varied with noise and selector.Source: §5.7 · p. 34, Figure 8 · p. 34, Table 1 · p. 35

A Additional Convergence plots

Appendix A shows model convergence plots for σ = 1.25 and σ = 10.0.

A Additional Convergence plots

B Additional Heatmap Results

Appendix B presents additional performance-comparison heatmaps at σ = 0.0001, 1.25, 2.5, 5.0, and 10.0.

B Additional Heatmap Results

C Additional JSD Heatmap Results

Appendix C presents additional performance-comparison heatmaps across five noise levels.

C Additional JSD Heatmap Results

D Additional PSR Plots

Appendix D shows PSR plots for entropy and KG-SSR pair selection under the same N = 10, K = 10, σ = 5.0 configuration.

D Additional PSR Plots

  • Figure 21 shows PSR behaviour for entropy selection at N = 10, K = 10, and σ = 5.0.Source: Figure 21 · p. 44
  • Figure 22 shows PSR behaviour for KG-SSR selection at N = 10, K = 10, and σ = 5.0.Source: Figure 22 · p. 44

E Model robustness plots for σ = 1.25, 5.0, 10.0 for entropy and KG-SSR pair selections

The appendix presents BBTM robustness plots for entropy and KG-SSR pair selection at N = 10 and K = 10 across three noise levels.

E Model robustness plots for σ = 1.25, 5.0, 10.0 for entropy and KG-SSR pair selections

F Additional plots for empirical validation of the convergence theorem for σ = 0.0001, 1.25, 2.50, 10.0

The appendix presents pair-coverage and convergence plots for four noise levels as additional empirical validation of the convergence theorem.

F Additional plots for empirical validation of the convergence theorem for σ = 0.0001, 1.25, 2.50, 10.0

Loading 2610.29416v1…