A state-space perspective on modelling and inference for online skill rating

Samuel Duffield, Sam Power, Lorenzo RimellaJournal of the Royal Statistical Society Series C (Applied Statistics) 2023

TL;DR

This paper proposes a unified state-space modeling framework for skill rating in competitive sports, treating player skills as dynamic and match outcomes as observations. This approach offers a flexible and interpretable alternative to traditional methods like Elo, enabling more robust inference and better handling of complex scenarios.

What Problem Does This Paper Address?

Estimating player skill is a fundamental task in competitive sports, crucial for ranking, matchmaking, and strategic decision-making. Traditional methods like Elo, Glicko, and TrueSkill, while popular, often rely on implicit statistical models or approximations that can limit their flexibility and interpretability. The authors identify a need for a more principled, model-based approach that can explicitly represent time-varying skills, handle complex match outcomes (like draws), and provide uncertainty quantification. They aim to bridge the gap between simple, heuristic methods and more complex, computationally intensive models by offering a unified state-space framework.

Methods

The core contribution is a state-space model (SSM) perspective on skill rating. This means player skills are treated as latent, time-varying states, and match results are observed quantities. The authors advocate for a modular approach where model definition and inference are decoupled, allowing practitioners to easily experiment with different components.

Key techniques and concepts introduced or emphasized include:

  • State-Space Modeling: Representing player skills as time-varying latent variables.
  • Decoupling Approximation: Assuming player skills evolve independently, which significantly simplifies computations, especially for a large number of players.
  • Match Sparsity: Exploiting the fact that only players involved in a match affect its outcome, reducing computational complexity.
  • Inference Objectives: Clearly defining the three main tasks: filtering (estimating current skill), smoothing (estimating past skill), and parameter estimation (learning model parameters).
  • Algorithmic Approaches: Discussing and comparing various inference methods, including:
  • Extended Kalman Filter (EKF): A standard approach for approximating non-Gaussian SSMs, but can introduce bias.
  • Sequential Monte Carlo (SMC): A more flexible, non-parametric approach that can handle complex distributions but incurs Monte Carlo variance.
  • Factorial Hidden Markov Models (fHMM): A discrete state-space model that offers computational advantages.
  • Model Refinements: Extending the framework to handle more complex match outcomes like draws and points-based scoring (e.g., bivariate Poisson for football goals).

The paper emphasizes the importance of a unified framework that allows for easy experimentation with different model structures and inference algorithms.

Datasets

The authors use real-world data from three sports for their experiments:

  • Women's Tennis Association (WTA) results: Primarily used for parameter estimation and model comparison, noting that draws do not occur in tennis.
  • English Premier League (EPL) football data: Includes match results and goals scored, allowing for the study of models with draws and margin of victory.
  • Professional (classical format) chess matches: Used to evaluate models in a sport with a high draw percentage.

They also provide links to the data sources and a Python package (abile) for reproducing their simulations.

Key Insights and Ideas

  • Unified Framework: The state-space perspective provides a powerful, unifying lens for understanding and comparing various skill rating methods, from simple Elo to complex dynamic models.
  • Dynamic Skills are Crucial: The paper argues that assuming static skills is often unrealistic, and dynamic models better capture the evolving nature of player abilities.
  • Trade-offs in Inference: Different inference methods (EKF, SMC) offer distinct trade-offs between computational cost, bias, and variance, making the choice dependent on the specific application.
  • Interpretability Matters: Model-based approaches, unlike black-box methods, offer greater interpretability, allowing for deeper insights into player performance and the factors influencing it.
  • Scalability is Key: The authors address the challenge of scaling skill rating to large numbers of players and matches through approximations like decoupling and match sparsity.

Key Results

  • Model-Based Approaches Outperform: Across tennis, football, and chess, the proposed model-based state-space approaches (especially those with uncertainty quantification) significantly outperform simpler methods like Elo and Glicko, particularly in sports with draws.
  • SMC and fHMM Identify Global Optima: In parameter estimation experiments on tennis data, SMC and fHMM successfully identified the global optimum, while the Gaussian approximation used by TrueSkill2 led to bias and evasion of the optimum.
  • Smoothing Provides Smoother Trajectories: Smoothing distributions offer less uncertainty and more realistic, less reactive skill trajectories compared to filtering distributions, which are more sensitive to recent results.
  • Model Refinements Yield Better Predictions: Extending the model to account for factors like goal margins in football (using a bivariate Poisson likelihood) improved predictive performance.

Limitations and Future Work

  • Computational Cost: While approximations are used, complex models with many players or states can still be computationally demanding. The paper notes that SMC's computational cost scales with the number of particles, and fHMM's with the number of states.
  • Parameter Estimation Challenges: For complex models, parameter estimation can be challenging, and the paper uses an iterative EM approach with approximations. The authors suggest exploring online parameter estimation and Bayesian approaches for more robust estimation.
  • Model Complexity: The paper acknowledges that while the state-space framework is flexible, building more complex models that account for additional factors (e.g., external influences, specific player parameters) is a natural direction for future work.
  • Alternative Inference Methods: The authors mention other approximate inference methods like Expectation Propagation and Assumed Density Filtering as potential alternatives, particularly for models with skewed likelihoods.
  • Multiplayer Extensions: While the framework is generalizable, the paper primarily focuses on pairwise comparisons, with multiplayer extensions noted as a direction for future research.

Summary updated

Abstract

Abstract We summarize popular methods used for skill rating in competitive sports, along with their inferential paradigms and introduce new approaches based on sequential Monte Carlo and discrete hidden Markov models. We advocate for a state-space model perspective, wherein players’ skills are represented as time-varying, and match results serve as observed quantities. We explore the steps to construct the model and the three stages of inference: filtering, smoothing, and parameter estimation. We examine the challenges of scaling up to numerous players and matches, highlighting the main approximations and reductions which facilitate statistical and computational efficiency. We additionally compare approaches in a realistic experimental pipeline that can be easily reproduced and extended with our open-source Python package, abile.
BibTeX
@article{duffield2023state,
  author = {Samuel Duffield and Sam Power and Lorenzo Rimella},
  title = {{A state-space perspective on modelling and inference for online skill rating}},
  journal = {Journal of the Royal Statistical Society Series C (Applied Statistics)},
  year = {2023},
}
Figure