Detecting Abrupt Changes in Sequential Pairwise Comparison Data
Authors: Wanshan Li
Alessandro Rinaldo
Daren Wang
Venue: NeurIPS 2022 Accept (2022)
Keywords: ranking
change point detection
Bradley-Terry model
high-dimensional statistics

Abstract: The Bradley-Terry-Luce (BTL) model is a classic and very popular statistical approach for eliciting a global ranking among a collection of items using pairwise comparison data. In applications in which the comparison outcomes are observed as a time series, it is often the case that data are non-stationary, in the sense that the true underlying ranking changes over time. In this paper we are concerned with localizing the change points in a high-dimensional BTL model with piece-wise constant parameters. We propose novel and practicable algorithms based on dynamic programming that can consistently estimate the unknown locations of the change points. We provide consistency rates for our methodology that depend explicitly on the model parameters, the temporal spacing between two consecutive change points and the magnitude of the change. We corroborate our findings with extensive numerical experiments and a real-life example.

Detecting Abrupt Changes in Sequential Pairwise Comparison Data
Wanshan Li Department of Statistics & Data Science Carnegie Mellon University wanshanl Candrew. cmu. edu
Daren Wang Department of ACMS
University of Notre Dame
dwang24@nd. edu
Alessandro Rinaldo
Department of Statisties Data Science Carnegie Mellon University arinaldo0cmu.ced edu
Abstract
The Tradley-Terry-Lun (BTL) model is classic and very popular statistical approach for eliciting a global ranking among a collection items using pairwise comparison data. In applications in which the comparison outcomes observed as a time series, is often the case that data are non-stationary, in the sense that the underlying ranking changes over time. In this paper with localizing the change points in a high-dimensional BTL model with piece- wise constant parameters. We propose novel and practicable algorithms based dynamic programming that can consistently estimate the unknown locations of the change points. We provide consistency rates for our methodology that depend explicitly on the model parameters, the temporal spacing between two consecutive change points and the magnitude of the change. We corroborate our findings with extensive numerical experiments and real-life example.
concerned
Introduction
Pairwise comparison data among the most common types of data collected for the purpose of eliciting a global ranking among a collection of items or teams. The Bradley-Terr--Luc model classical and popular parametric approach model pairwise comparison data and to obtain an estimate of the underlying ranking. The Bradley-Terry- Luce model and its variants have been proven be powerful approaches many applications, including sports analytics (Fahrmeir and Tutz 1994 Masarotto and Varin 2012. Cattelan et al. 2013)
(Bradley and Terry 1952 Luce 1959)
bibliometrics (Stigler, 1994] Varin et al. 2016). search analytics (Radlinski and Joachims
2007
Agresti 2013). and much more.
To introduce the BTL model, suppose that are interested in ranking n distinct items, each with (fixed but unobserved) positive preference score w;, E [n]. quantifying its propensity to beat other items in pairwise comparison. The BTL model assumes that the outcomes of the comparisons between different pairs are independent Bernoulli random variables such that, for a given pair of items, say and j in [n] {I,..., ".....n,,, n1,, the probability that is preferred (or beats) j is
w
Pg P (i beats j)
Vi,j E [m]].
(1.1)
w + W
A common reparametrization is to set w = exp(O?) for each i, where 0" = ..,,..., 0%) E IR".
To ensure identifiability it further assumed that Σ Elelo 0 0.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

1 INTRODUCTION
2
The properties and performance of the BTL model have been thoroughly studied under the assumption that the outcomes of all the pairwise comparisons are simultaneously available and follow the same BTL model. In many applications however, it is very common to observe pairwise comparison data sequentially (i.e. one at a time), with time stamps over multiple time periods. In these cases, is unrealistic to assume that observations with different time stamps come from the same distribution. For instance, in sports analytics, the performance of teams often changes across match rounds, and Fahrmeir and Tutz (1994) utilized state-space generalization of the BTL model to analyze sport tournaments data. Ranking analysis with temporal variants has also become increasingly important because of the growing needs for models and methods to handle time-dependent data. A series of results in this direction can be found in Glickman 1993), Glickman and Stern ( (1998), Cattelln et al. (2013). Lopez et al. 2018). Maystre et al. (2019), Bong et al. (2020). Karlé and Tyagi (2021) and references therein. Much of the aforementioned literature on time-varying BTL model postulates that temporal changes in the model parameters smooth functions of time and thus occur gradually on a relatively large time scale. However, there are instances in which it may be desirable to instead model abrupt changes in the underlying parameters and estimate the times at which such change has occurred. These change point settings, which, to the best of our knowledge, have not been considered in the literature, and are the focus of this paper.
Contributions
We make the following methodological and theoretical contributions.
Novel change point methodology. We develop a computationally efficient methodology to consistently estimate the change points for time-varying BTL model with piece-wise constant parameters. Our baseline procedure Algorithm | consists of a penalized maximum likelihood estimator of the BTL model under an to penalty, and can be efficiently implemented via dynamic programming. We further propose a slightly more computationally expensive two-step procedure in Algorithm 2 that takes as input the estimator returned by our baseline procedure and delivers more precise estimator with provably better error rates. We demonstrate through simulations and a real life example the performance and practicality of the procedure we develop.
Theoretical guarantees. We obtain finite sample error rates for our procedures that depend explicitly all the parameters at play: the dynamic range of the BTL model and the number of items to be compared, the number of change points, the smallest distance between two consecutive change points and the minimal magnitude of the difference between the model parameters two consecutive change points. Importantly, our theory allows for general connected comparison graph and it explicitly captures the effect the topology of the comparison graph. Our results hold provided that a critical signal-tos signal-to-noise ratio condition involving all the relevant parameters is satisfied. We conjecture that this condition is optimal in an information theoretic sense. Both the signal-to-no noise ratio condition and the localization rates we obtain exhibit a quadratic dependence on the number of items be compared. which matches the sample complexity bound for two sample testing for the BTL model recently derived by Rastogi et al. (2220).
We emphasize that the change point setting we consider have not been previously studied and both our methodology and the corresponding theoretical guarantees appear to be the first contribution of its kind in this line of work.
Related work
Change point detection a classical problem in statistics that dates back 1940s (Wlld 1945| Page 1954). Contributions in the 1980s established asymptotic theory for change point detection methods (Vostrikova 1981 James al. 1987 Yao and Au 1989). Most of the classical literature studied the univariate mean model. Recently with more advanced theoretical tools developed in modern statistics, more delicate analysis of change point detection came out in high-dimensional mean models (Jirak)
2015; Aston and Kirch 2018 8, Wang and Samworth 2018), covariance models (Aue et al.] 2009 Avanesov and Buzun 2018, Wang et al. (021b). high-dimensional regression models (Rinaldo et al.
2021;:Wang et al.) 202 network models (Wang et al. (221aa), and temporally lated times
series (Cho and Fryzlewicz 2015, Preuss et al. 2015) Chen et al. 202T: Wang and Zhao 2022).
Although change point detection has already been extensively studied in many different settings, little known about the case of pairwise comparison data. Höhle (2010) numerically study the CUSUM

---

2 MODEL AND ASSUMPTIONS
3
method for online change point detection in logit models and BTL models without giving theoretical guarantees. We aim fill the gap in the literature and propose a theoretically trackable approach that can optimally localize abrupt changes in the pairwise comparison data.
2 Model and assumptions
Below we introduce the time- varying BTL model with piece-wise constant coefficients that we are going to study and the sampling scheme for collecting pairwise comparison data over time.
Suppose there is connected comparison graph g [(m), E) with edge set E S Erul == ((,j)= S n). We assume throughout that data are collected as a time series indexed by
1 isi < Te = .,,.., T) that, each time point t, single pairwise comparison among a collection of items is observed. The distinct pair (iz, jt) E [n]] of items to be compared at time is randomly chosen from the edge set E of G, independently over time. That is,
P(i: i, =]
v(i.) E
(2.1)
E
For each I, let y1 {0, }} denote the outcome of the comparison between in and jr. where ye = 1 indicates that it beats Je in the comparison. We assume that yr follows the BTL model (I.I). i.c.
(0) ())
(o) = 1[(4,,)))] e e
(2.2)
where (1) (0]((), () is, possibly time-varying, parameter that belongs to the set θ = (0 E 1 = 0, 100| - B),
(2.3)
for some B > In the recent literature on the BTL model, the parameter B is referred as the dynamic range (see, e.g., Chen et al., 2019) which readily implies a bound on the smallest possible probability that an item beaten by any other item. Indeed, it follows from (2.2) and 2.3) that
min tE[T]A.EEM
(t) 2 e 2B /(1 + e 2B == Ptb >
(2.4)
Remark 1. The quantity Pus have appeared in several equivalent forms in the BTL literature, e.g..
Mi (Simons and Yao. 1999 Negahban et al. 2017) and 2BB (Li et al. 2022). The maxi,je[n] we
minimal winning probability Ptb provides a way of quantifying the difficulty estimating the model parameters, with a small pu implying that some items are systematically better than others, a fact that is known to lead to non-existence of the MLE (see, e.g. |Ford 1957) and to hinder parameter estimability. In the BTL literature the dynamic range B and, as result, the quantity Pts are often treated as known constants and thus omitted (Shah et al. 2016 Chen et al. 20200), a strong assumption that results in an implicit regularization but potentially hides an important feature of the model. As argued in Bong and Rinaldo (2022), in high-dimensional settings this may not be realistic. We will allow for the possibility of varying B and pis. and keep track of the effect of these parameters our consistency rates.
a different but equivalent form that is reminiscent of logistic regression and will facilitate our analysis. One express the fact that, time t, the items and je are randomly selected from 9 [ni, J, E' to be compared using a random n-dimensional vector x(t) that is drawn from the sets of all vectors in { {-1,00 0, 1)"h with exactly two-non-zen entries of opposite sign, namely I;, (t) and Tj. (t) = -1 for (4,,e) E F. Then equation (2.2) can be written as
convenient to rewrite
P (o- [vt ([)( = & (x())T0(()).
(2.5)
where (xx) = I+e-a the sigmoid function. For any time interval I C [T] we then assume that the data take the form of an i.i.d. sequence ((x(t), 3:) hez where each x(f) is an i..dd draw from
{-1,0, O, 1)" with aforementioned properties and, conditionally x(t), yt is Bernoulli random variable with success probability (..2). The negative log- likelihood of the data is then given by
L(O,I) E())), where (0)) 1(0: Mr, x(1)) -1x((1) 0 log[1 + exx((((1) 0)]. (2.6)

---

3 MAIN RESULTS
4
For a time interval I, we can define random comparison graph Gz Ez) with vertex set V := [n] and edge set Ex := {(i,j) and j are compared in J). It well-known that the topology of Gvz, Fz) plays an important role in the estimation of BTL parameters (Shah et al. 2016 6)..
Under assumption (. the comparison graph over I follows the random graph model G( [1 which has [Z] edges randomly picked from the edge set E with replacement. Therefore, the process {(x(t), ye) HEz is stationary as long as (t) is unchanged over
In the change point BTL model we assume that, for some unknown integer K 2 1, there exist K + KK+1 such that 1 = < ?n < .... < TjK < 1 = T and (z) * (* - 1) whenever
points {mn k=0
I {7H ]E[K]] Define the minimal spacing A between consecutive change points and the minimal jump size K as
A min (MH 7)k-1), kE|K+11
min ke[K+1]
(m)) 0" (71-1))l2-
(2.7)
As mentioned in the introduction, the goal of change point localization is to produce estimator of the change points {fk kej &] such that, with high-pro hogh-probbiility as T + oo, we recover the correct number of change points and the localization error is a vanishing fraction of the minimal distance between change points, i.e. that
k= K, and max li kE(K"
7 I/A o(1)
(2.8)
In change point literature, estimators satisfying the above conditions called consistent. In the next section we will present two change point estimators and prove their consistency.
Main results
To estimate the change points, solve the following regularized maximum likelihood problem all possible partitions P of the time course (T]:
P arg min
Σ L(((), ZEP
+
(I) = arg min L(O,I), o
(3.1)
where I(O, I) is the negative log-likelihood function for the BTL model defined in (2.6) and > 0 an user-specified tuning parameter. Here partition P is defined
of integer intervals:
p = (1), P2). [PK,, T),, < p1 P2 <K <.
(3.2)
With K- Kp |P| 1, the estimated change points (ftx ke are then induced by n pk- E [K]. The optimization problem (3.1) has an fu-penalty, and can be solved by a dynamic programming algorithm described in Algorithm | with O(T²C(T) complexity (Friedrich al. 2008 Rinaldo et al., 2021) where C(T) is the complexity of solving ming L(0, [1,
In this section, we will demonstrate that the estimator returned by Algorithm 1 is consistent. Towards that goal, we require the following signal-to-noise ratio condition involving the parameters A, K, B, n, the sample size T, and the topological property of the underlying comparison graph [[m)), E).
Assumption 3.1 (Signal-to-noise ratio). Let {(((t), y1) he(ry be i.i.d. observations generated from model [2.1 and (2.5) with parameters {0 (t)} C θg defined in (2.3). We assume that for a diverging sequence B, hrea+
EE log(I'n).
A 2 > Brpw 4 K
(3.3)
xz((o)
where we recall that pio ==
I+c-2n, dmax is the maximal degree of nodes in G and A2(G is the second smallest eigenvalue of the Laplacian of G
2B
The formulation of -o-oise ratio conditions involving all the parameters of the model has become staple of modern change point analysis literature. To provide some intuition, the term x is a proxy for the strength of the signal of change points in the sense that the localization and
For simple undirected graph & with (binary) adjacency matrix A, the Laplacian Lg : D -- A where D = diag(di," dn)) where d, is the degree of node

---

3 MAIN RESULTS
5
detection problems are expected to become easier, as the magnitude of the jumps and the spacing between change points increase. On the other hand, the right hand side of Equation (3.3) collects terms that impact negatively the difficulty of the problem: the smaller the minimal win probability Pib and the algehraic connectivity Az(Tg)) the larger the number of items n to compare and the number of change points K, the more difficult it is to estimate the change points.
Remark 2 (One the topology of g). When the comparison graph G is complete graph, we have |F]] n(n n) dmaa
1, (T n. so the assumption becomes
x2 2 BTPs Kn² log(T'n).
(3.4)
In this case, the comparison graph (vi],, Foz) is random graph G(n,, m)) that have m edges sampled uniformly randomly with replacement. G(n, m)) is similar to an Rénös--Réní graph that is commonly used in the ranking literature (Chen et al.) 2019 2020). In this regard, our result, which directly reflects the impact of the general topology of the sampling graph, is fairly general and in line with recent advances in statistical ranking.
Also note that in general, X2 S An < <2dmax so the assumption (33) ensures that the sample complexity m 2 Co log in Lemma B.15 satisfied in the worst case x² x n2
>2(Tag)
Remark (On the sharpness of the signal-to-noise ratio condition). We will now argue that the requirement (3.1) imposed by the signal-to-noise ratio (SNR for brevity) is reasonably sharp by relating it to the sample complexity of a two-sample testing problem. To that effect, consider the simplified setting in which there is only one change point at time A = T/2 and G is complete graph. In this case, it can be shown that the SNR condition (3.1) becomes (see Proposition B35)
A R² 2 BTPi 2n² log(Tn),
(3.5)
i.e. the dependence on the dynamic range B is through Pib iinstead of Pib" It stands to reason that estimating the unknown change point A should be at least as hard as testing the null hypothesis that there exists a change point at time A. Indeed, this testing problem should be easier because A has been revealed and because, in general, testing is easier than estimation. This can in turn be cast as two-sample testing problem of the form
Ho P(O (() v.s. H1
_ |P(( (( 2,,
(3.6)
where e >> 0 is to be specified, (1)) and (:2) are the BTL model parameters for the first and the last
observations respectively and, for E {1,2), 2). P(O())) is the n x n matrix of winning probabilities corresponding to the BTL model parameter (60) as specified by (.22). To see how one arrives at (3.6).
we have that, by Proposition B.4.
(P((O()) - (( >> 2
nPï
2 [10(1] 203)
(3.7)
16
Thus, change point setting with [[0(1) 2 x² translates into the testing problem (3.6)
with c² = x/ppe/ (16n). By Theorem 7 of Rastogi et al. (2020), there exists an algorithm that will return consistent test for (3.6) based on two independent samples of size N if N 2 cn2 log(n) y
When we apply this result to the simplified change point settings described above (by replacing N and e² with A and x² /² (16n) respectively) we conclude that the sample complexity bound of Theorem 7 of Rastogi et al. (2020) corresponds, up to constants, to the above SNR condition (3.5) save for the terms log(T") and By. Thus, we conclude that the assumed SNR condition for change point localization is essentially equivalent to the sample complexity needed to tackle the simpler two-sample testing problem, indication that our assumption is sharp.
Finally, we take notice that, when there are multiple change points, in our analysis appears necessary to strengthen the signal-to-noiss ratio condition (3.5) (3.1 by requiring a dependence on Pio'
We are now ready to present our first consistency result.
Theorem 3.2. Let (fjz) kE[R] be the estimates of change points from Algorithm 7 with the tuning pa- rameter 7 = Cypi6 -2 (K + +1) ndmas log(Tn) where C.,, is a universal constant. Under Assumption 3.1 (L()
we have
P p K = K,
max 7M Thl S CpPp
= |E 1E log(Tn) 10-2212200 2(Tn)) 2122(Tn) (3.8) x² (3)))
kE[K]
where Cp i a universal constant that depends on Cr.

---

3 MAIN RESULTS
6
Theorem 3.2
gives a high- probbabbbyyl upper bound for the localization error of the output { ke([R]
of Algorithm
By Assumption
3.1
it follows that as T - oc, with high probability,
E Fdduaxx 6² (3.g)))))))
77 KEIK]
max
mhl
CpPRo"
K
log log(Tn) CPPPCPE o(A):
(3.9)
BT
where we use the singal-to-noise ratio assumption A inequality and the fact that By diverges in the final step. This implies that the estimators {7 [ejK) are consistent. Moreover, when K
BTP K [Elnddas log(Tn) in the last Ag(Ta)
there is no change point, is guaranteed that, with high probability, Algorithm [ will return empty set. We summarize this property Proposition B.6 and include it in Appendix B.2 due the limit of space.
Algorithm 1: Dynamic Programming. DP (((x(t), M1) (E()))))))
INPUT: Data {(((t), Me Hery, tuning parameter 7, Set S = 0, p -1.. b (7, ,00 RR".. Denote b, be the i-th entry of b.
for r in (2. (2..... [ do
for in {l.....r- 1 do
b b + L(((I),I) where I= (l....,r]:
if < by then L b, + b; pr
1-
To compute the change point estimates from p E EN" T.
while k >> 1 do
L - P ; S S h h.
OUTPUT: The estimated change points S b
Algorithm 2: Local Refinement.
INPUT: Data ((((t), 31) Me) the be(R) (7o. 7R+1) + (1,7).
for k = 1,.... K do
(8k, ex) + (2 /3 7 3+ + 2133+
" Σ t=
n& x- arg min
min einea
((
min
(
nE(e2+h...ee---
e
E t=
(3.10)
OUTPUT: (fh (ishke
Inspired by previous works (Wang et al., 2021a; Rinaldo al. 2021). we can further improve the localization error by applying local refinement procedure as described in Algorithm 2 to {m [eE[)) This methodology takes as input any preliminary estimator of the change points that estimates the number of change points correctly with localization error that is a (not necessarily vanishing) fraction of the minimal spacing A, and returns a new estimator with provably smaller localization error. natural preliminary estimator the one returned in Algorithm [ The next result derives the improved localization rates delivered by the local refinement step. The two improvements are the elimination of the term K in the rate and better dependence on Ptb-
Theorem 3.3. Let (he f kel be the output of Algorithm 2 with input (ne bhokkejk) returned by Algo-
rithm 7 Under Assumption 3.1 for all sufficiently large T we have
P P K,
Eddnax log(Tn) 2 21-2(Tn) x2))(Lo)
max hh nal S CRPTT KE[K]
(3.11)
where CR 0 is universal constant that depends C..

---

4 EXPERIMENTS
7
Remark 4. By "sufficiently large T in the theorem statement, we mean that T should be large enough to make = lis 7%k S A (see Proposition B.3 in Appendix B for details). Such T
exists because of Equation 3.9 and the fact that Br is diverging in T.
We conjecture that the rate 3..1 resulting from the local refinement procedure is, aside possibly
from a logarithmic factor, minimax optimal.
4 Experiments
In this section, we study the numerical performance of our newly proposed method based on a combination of dynamic programming with local refinement, which we will refer to as DPLR; see Smorithms[andde We note that the detection of multiple change points in pairwise comparison data has not been studied before, as Höhle (2010) only focus on single change point detection for pairwise comparison data, so we are not aware of any existing competing methods in the literature. Thus, we develop a potential competitor based on the combination of Wild Binary Segmentation (WBS) (Fryzlewicz 2014), a popular method for univariate change point detection, and the likelihood ratio approach studied in Höhle (2010). We will call this potential competitor WBS-GLR (GLR stands for generalized likelihood ratio). Due to the limit of space, we include the detail of WBS-GLE in Appendix A.T] and results of additional experiments in Appendix A.2] where additional settings considered. Furthermore, we discuss and compare the performance of two other potential competitors in Appendix A..4
All of our simulation results show that our proposed method DPLR outperforms WBS-GLR in the sense that DPLR gives more accurate change point estimates with similar running time. Each experiment is run on a virtual machine of Google Colab with Intel(R) Xeon(R) CPU of cores 2.30 GHz and 12GB RAM. All of our reproducible code is openly accessible
Simulation Settings. Suppose we have K change points {Te [ejK] in the sequential pairwise comparison data, with 7o = 1. We can use (*()))) to represent the value of true parameters after the change point 7lk- To begin, we define 0 (1%) as follows. For 1 <
n, we set 0ī (7%) (1m) + (i - 1)6 with some constant 6. In each experiment, we set ó first and then set 01 (no) to make (m)) = 0. For a given n, we set ō = n-1
1 16 (p) = n=1 log(;",)) where & is the inverse
function of z6 and guarantees that the maximum winning probability 0.9. We consider three types of changes:
0.9. Recall that P. (0; 0z) is the winning probability, so the value of d
Type I (reverse): 0, (mx) = 07+1-1(00.
Type II (block-reverse): 0, (mx) 014+1- for i S [+]: 03 (1)) 0111++111(000 for i> (7).
Type III (block exchange): 8 (mx) ( for < [g]: 87 (m²) = 16 (7u) for i [6]]
We consider four simulation settings. For each setting, we set the comparison graph [[n)), E)) to be the complete graph and T (K 1)4 with true change points located 77, = is for i [K]. To describe the true parameter at each change point, we use an ordered tuple. For instance, (I, II, III, I) means that K 4 and the true parameters 7J,, 7/2 Ta, 7/4 are determined based on 0" (mj) and the change type I, II, III, and I, respectively.
For the constrained MLE in Equation penalized logistic regression, as it is well-known that the constrained and the penalized estimators for generalized linear models are equivalent. For both DPLR and WBS-GLR, we use À = 0.1. For M, the number of random intervals in WBS-GLR, we set it to be 50 as a balance of time and accuracy.
we the function in sklearn for fitting the é2-
For both methods, we use cross-vale validatiin to choose the tuning parameter 7, Given the sequential pairwise comparison data in each trial, we use samples with odd time indices as training data and even time indices as test data. For each tuning parameter, the method is applied to the training data to get estimates of change points. Then a BTL model is fitted to the test data for each interval determined by the estimated change points. The tuning parameter and the corresponding change point estimators with the minimal test error (negative loglikelihood) are selected. We run 100 trials for each setting.
Cooe repository: httpp://github..... httpe///iiuubbcccoooouteeeeee///

---

APPLICATION: THE NATIONAL BASKETBALL ASSOCIATION GAMES
8
H 77)
Time
K
<< K
K = K
K >
K
Setting (i) n 10, K 3, 500, Change (I, II, III)
DPLR
(9.1)
49.7s (0.7)
0
100
0
WBS-GLR
15.2 (7.9) 31.9s (3.9)
0
100
Setting (ii) 20, K 3, A 800, Change (I, II, III)
DPLR
(99)
118.5s (2.2)
0
100
0
WBS-GLR
240.5 (220.3)
144.2s (12.5)
0
40
60
Setting (iii) 12
100, K = 2, A
= 1000, Change II)
DPLR
13.4 (14.4)
167.4s (3.3)
0
100
WBS-GLR
111.9 (195.6)
215.9s (17.0)
0
79
21
Setting (iv) 7t = 100, K = 3, A 2000,
Change (1, II, III)
DPLR
12.4 (12.1)
402.4s (7.4)
0
100
0
WBS-GLR
412.3 (495.5) 400.0s (40.9)
0
57
43
Table I: Comparison of DPLR and WBS-GLR under four different simulation settings. 100 trials are conducted in each setting. For the localization enror and running time (in seconds). the average over 100 trials shown with standard error in the bracket. The three columns on the right record the number of trials in which R- < K, K K, and K > K respectively.
Results. To measure the localization enrors, use the Hausdorff distance H (e In (e(K) between the estimated change points (f) 1%.eetk ke(k] and the true change points {πKbe(K]- The Hausdorff distance HS1 S2) between two sets of scalars is defined as
H(S1 S2) max sup inf yl. sup inf | yl}. yeS, #ES;
(4.1)
=ES, vES2
The results are summarized in Table where we use H 7) to denote the localization error for brevity. As see, our proposed method DPLR gives more accurate localization with similar running time compared to the potential competitor WBS-GLR.
Application: the National Basketball Association games
We study the game records of the National Basketball Association (NBA) Usually regular NBA season begins October and ends April of the next year, so in what follows, season is named by the two years it spans over. The original data contains all game records of NBA from season 1946-1947 to season 2015-2016. We focus on subset of 24 teams founded before 1990 and seasons from season 1980- 1981 to season 2015-2016. All code of analysis is available online with the data
We start with exploratory data analysis and the results show strong evidence for multiple change points 5 Therefore, we apply our method DPLR to the dataset to locate those change points. We the samples with odd time indices training data and even time indices test data, and use cross-validation to choose the tuning parameter 7-
To interpret the estimated change points, we fit the BTL model each subset splitted change point estimates separately. The result is summarized in Table 2 Several teams show significant jumps in the preference scores and rankings around change points. Apart from this quantitative assessment, the result is also firmly supported by memorable facts NBA history, and we will name few here. In 1980s, Celtics in the "Larry Bird" era with its main and only competitor "Showtime" Lakers. Then starting from 1991, Michael Jordan and Bulls created one the most famous dynasties in NBA history. 1998 is the year Michael Jordan retired, after which Lakers and Spurs were dominating during 1998-2009 with their famous cores "Shaq and Kobe" and "Twin Towers".. The two teams together won champions during these seasons. $2010-S2012 is the well-known "Big 3" era of Heat. Meanwhile, Spurs kept its strong competitiveness under the lead of Timothy Duncan. From 2013, with the arise of super stars Stephen Curry and Klay Thompson, Warriors started take the lead.
httpa://gist wtt.ggtttttttt........gg http:///wwta......//oo//o/////ta
Code repository: http:///gtthhb.ccc//ootttteeeees
'Due to the limit of space, include these results in Appendix A.3

---

CONCLUSIONS
9
S1980-S1985
S1986-S1991m
S199Im-S1997
S1998-S20033
Celtics
1.1484
Lakers
1.1033
Bulls
0.9666
Spurs
0,8910
76ers
0.9851
Pistons
0.7696
Jazz
0.8618
Lakers
0,8744
Bucks
0.7828
Celtics
0.7304
Knicks
0,5908
Kings
0.6833
Lakers
0.7779
Trail Blazers
0.6848
Suns
0,5628
Mavericks
0,5087
Nuggets
0.0789
Bulls
0.6647
Rockets
0,5032
Trail Blazers
0.4899
Trail Blazers
0,0636
Jazz
0,5179
Spurs
0,4742
Jazz
0,3944
Suns
0.0636
Bucks
0.3474
Trail Blazers
0,4176
Timberwolves
0.3913
Spurs
0.0611
Suns
0.3472
Cavaliers
0.3751
Pacers
0.3165
Nets
0.0215
Rockets
0.3156
Magic
0.3009
Hornets
0.1002
Pistons
-0.0252
76ers
0,2195
Lakers
0.2730
76crs
0.0993
Knicks
-0.1333
Cavaliers
0.1885
Pacers
0.2688
Suns
0.0721
Rockets
-0.1950
Mavericks
0.1798
Horeets
0.2465
Pistons
0.0249
Jazz
-0.2926
Knicks
0.0583
Heat
0.1445
Bucks
-0,0146
Kings
-0.3104
Warriors
0.0441
Pistons
-0.2028
Rockets
-0,0525
Mavericks
-0.3104
Spurs
0.0035
Nets
-0.2122
Knicks
-0.1420
Bulls
-0,3115
Nuggets
-0,0232
Warriors
+030755
Heat
-0.1455
Warriors
-0.4330
Pacers
-0.0237
Celtics
+0.3288
Nets
-0.2276
Pacers
-0.5500
Kings
-0.7006
Kings
-0,8008
Magic
-0,2650
Clippers
-0.6443
Nets
-0.7666
Clippers
-0.5419
Celtics
-0,2885
Cavaliers
00.7771
Clippers
-0.7788
Bucks
+0,8664
Nuggets
-0.4894
Heat
NA Magic
-0,8969
Nuggets
-0.6272
Clippers
-0.6250
Hornets
NA
Timberwolves
-0,9554
Timberwolves
-0.6570
Cavaliers
-0.7796
Magic
NA
Heat
-0,9874
76ers
-0,869
Warriors
-0.3362
Timberwolves
NA
Hornets -1.0418
Mavericks
-1.1542
Bulls
-1.1801
S2004-S2006
S2007-S2009
S2010-S2012
S2013-S2015
Spurs
1.0532
Lakers
1.0097
Heat
0.9909
Warriors
1.3617
Suns
0.9559
Celtics
0.8699
Spurs
0.8653
Spurs
1.2728
Mavericks
0.9338
Magic
0.7741
Bulls
0.8292
Clippers
0,9909
Pistons
0.8120
Cavaliers
0.7466
Nuggets
0.5857
Rockets
0.6158
Heat
0,2713
Spurs
0.6270
Lakers
0,4922
Trail Blazers
0.5501
Rockets
0.1803
Mavericks
0.5686
Mavericks
0.4121
Mavericks
0.4197
Cavaliers
0.1510
Jazz
0.5169
Clippers
0.3413
Cavaliers
0.3872
Nuggets
0.1322
Nuggets
0.4751
Celtics
0.2901
Heat
0.3215
Kings
0.0542
Suns
0,4146
Knicks
0.1990
Pacers
0.3202
Lakers
0.0166
Hornets
0,3593
Pacers
0.1233
Bulls
0.2104
Nets
-0.0149
Rockets
0.3428
Rockets
0.1227
Hornets
0.0145
Timberwolves
-0.0566
Trail Blazers
0.2750
Jazz
0.0167
Pistons
-0.1710
Clippers
-0.0646
Bulls
-0.1660
Trail Blazers
+0.0599
Suns
-0,1787
Bulls
-0.0680
Pistons
-0.1811
Magic
+0.0899
Jazz
-0.1936
Pacers
-0.0824
Heat
-0,2939
Warriors
0.1402
Celtics
-0,2037
Jazz
-0.1039
76ers
-0.3418
76ers
-0.9330
Nets
-0,3093
Magic
-0.2482
Warriors
-0.3729
Bucks
-0.2362
Nuggets
-0.3140
Warriors
-0.2803
Pacers
-0.3936
Suns
-0.3228
Kings
-0,4066
76ers
-0.3030
Bucks
-0,5456
Nets
-0.4589
Bucks
-0.4516
Celtics
-0.5144
Kings
-0.7977
Horeets
-0.4670
Timberwolves
-0.6266
Hornets
-0.5641
Knicks
-0,8568
Timberwolves
-0.6034
Magic
-0.6398
Bucks -0,6555
Nets
-0,8935
Kings
-0.6929
Knicks
-0,6591
Knicks
-0.7101
Clippers
-1.0853
Pistons
-0.7807
Lakers
-0.9431
Trail Blazers
-0.8947
Timberwolves
-1.0901
Cavaliers
-1.2285
76ers
-1.3676
Table Fitted 0 (rounded the fourth decimal) for 24 selected teams seasons 1980-2016 of the
National Basketball Association. Teams are ranked by the MLE 0 on subsets splitted the estimated change points given by our DPLR method. S1980 means season 1980-1981 and S1991m means the middle of season 1991-1992. Heat(1 1988), Hornets(1985) Magic(1989) and Timberwolves(195) (1999) were founded after S1985, so the corresponding entries are marked as NA.
6 Conclusions
We have formulated and investigate novel change point analysis problem for pairwise comparison data based on high-dimensional BTL model. We have developed a novel methodology that yields consistent estimators of the change points, and establish theoretical guarantees with nonasymptotic

---

CONCLUSIONS
localization error. To the best of our knowledge, this is the first work in the literature that addresses in both a methodological and theoretically sound way multiple change points ranking data.
Although we filled a big gap in the literature, there remain many open and interesting problems for future work. First, we only consider pairwise comparison data modeled by the BTL model. Of course, there are other popular ranking models for general ranking data, c.g., the Plackett-Luce mucel(Luce) 1959 Plackett I975), Stochastically Transitive models(Shat
al. 2017), and the Mallows model Tang 2019). It would be interesting to see that for those models how difterent the method and theory would be from our settings. We present some exploratory results on this in Appendix A.44 Second, we have focused on retrospective setting of change point detection and passive setting of ranking, On the other hand. online change point detection (Vovk) (021) and active ranking (Heckel al. 2019]]
Ren et al., (02T)) are widely used in practice. Thus, it would be interesting to consider the online or active framework in change point detection for ranking data. Third, the recent change point detection literature, incorporating temporal dependence is of growing interest (Chen et al. [021]] Wang and Zhao 2022). so investigating how temporal dependence in the pairwise comparison data can affect our results seems like a worthwhile direction.
At last, discuss potential societal impacts of work. The BTL model does have applications with potentially undesirable societal impacts, e.g., sports-betting (McHale and Morton (01T), which could amplify the negative impacts gambling. We recommend using our method for research purposes rather than gambling driven purposes.
Acknowledgments
We would like thank the anonymous reviewers for their feedback which greatly helped improve our exposition. Wanshan Li and Alessandro Rinaldo acknowledge partial support from NSF grant DMS-EPSRC 2015489.

---

REFERENCES
11
References
Agresti, A. (2013). Categorical data analysis. Wiley Series in Probability and Statistics. Wiley- Interscience [John Wiley & Sons], Hoboken, NJ, third edition.
Aston, J. A. and Kirch, C. (2018). High dimensional efficiency with applications to change point tests. Electronic Journal of Statistics, 12(1):1901- -994.
Aue, A.,
Hörmann, S., Horváth, L.., and Reimherr, M. (2009). Break detection in the covariance structure of multivariate time series models. The Annals of Statistics, 37(6B):4046 4087.
Avanesov, V. and Buzun, N. (2018), Change-point detection in high-dimensione covariance structure. Electronic Journal of Statistics, 12(2):3254 3294.
Bong, H., Li, W., Shrotriya, S., and Rinaldo, A. (2020). Nonparametric estimation in the dynamic Bradley- Terry model. In Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pages 3317-3326. PMLR.
Bong, H. and Rinaldo, A. (2022). Generalized results for the existence and consistency of the MLE in the Bradley-Terry-Luu model. appear in International Conference on Machine Learning.
Bradley, R. A. and Terry, M. H. (1952). Rank analysis of incomplete block designs. I. The method of paired comparisons. Biometrika, 39:324-345.
Cattelan, M., Varin, C., and Firth, D. (2013). Dynamic Bradley- Terry modelling of sports tournaments. Journal of the Royal Statistical Society. Series C (Applied Statisties), 62(1):335-150
Chen, L., Wang, W., and Wu, W. B. (2021), Inference of breakpoints in high-dimensional time series. Journal of the American Statistical Association, 0(0):113..
Chen, P., Gao, C., and Zhang, A. Y. (2020). Partial recovery for top-K ranking: optimality of MLE and sub-optimality of spectral method. to appear in The Annals of Statistics.
Chen, Y., Fan, J., Ma, C., and Wang, K. (2019). Spectral method and regularized MLE are both optimal for top- ranking. The Annals of Statistics, 47(4):2204 2235.
Cho, H. and Fryzlewicz, (2015). Multiple-change-pee -pintt detection for high dimensional time series via sparsified binary segmentation. Journal of the Royal Statistical Society. Series B (Statistical Methodooogyy,, 7722):75-5077
Fahrmeir, L. and Tutz, G. (1994). Dynamic stochastic models for time-dependent ordered paired comparison systems. Journal of the American Statistical Association, 1444 1449.
Ford, L. R. (1957). Solution of ranking problem from binary comparisons. The American Mathematical Monthly, 23-
Friedrich, F., Kempe, A., Liebscher, V., and Winkler, G. (2008). Complexity penalized M-estimation:
fast computation. Journal of Computational and Graphical Statiticss, 17(1):001-224.
Fryzlewicz, P. (2014). Wild binary segmentation for multiple change-point detection. The Annals of Statistics, 42 42(6):2243 -2281.
Glickman, M. E. (1993). Paired comparison models with time varying parameters. Doctoral thesis, Harvard University.
Glickman, M. E. and Stern, H. S. (1998). A state-space model for national football league scores. Journal of the American Statistical Association, 93(441):25-35.
Heckel, R., Shah, N. B., Ramchandran, K., and Wainwright, J. (2019). Active ranking from pairwise comparisons and when parametric assumptions do not help. The Annals of Statistics, 47(6):309933126
Höhle, M. (2010). Online change-point detection in categorical time series. In Statistical Modelling and Regression Structures: Festschrift Honour of Ludwig Fahrmeir, pages 377-397. Physica- Verlag HD, Heidelberg.

---

REFERENCES
12
James, B., James, K. L., and Siegmund, D. (1987). Tests for change-pone point. Biometrika, 74(1):71-83,
Jirak, M. (2015). Uniform change point tests in high dimension. The Annals of Statistics, 43(6):2451- 2483.
Karlé, E. and Tyagi, H. (2021). Dynamic ranking with the BTL model: A nearest neighbor based rank centrality method. arXiv:2109.1377 13743.
Li, W., Shrotriya, S., and Rinaldo, A. (2022). -buudss of the MLE in the BTL model under general comparison graphs. to appear Uncertainty in Artificial Intelligence.
Lopez, M. J., Matthews, G. J., and Baumer, B. S. (2018), How often does the best team win? A unified approach to understanding randomness North American sport. The Annals of Applied Statistics, 12(4):2483-255 2516.
Luce, R. D. (1959). Individual Choice Behavior: Theoretical Analysis. New York, Wiley.
Masarotto, G. and Varin, C. (2012). The ranking lasso and its application to sport tournaments. The Annals of Applied Statistics, 6(4):1949-1970
Maystre, L., Kristof, V., and Grossglauser, M. (2019). Pairwise comparisons with flexible time- dynamics. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 1236-1246.
McHale, and Morton, (2011). bradley-terry type model for forecasting tennis match results. International Journal of Forecasting, 27(2):619-630.
Negahban, S., Oh, S., and Shah, D. (2017). Rank centrality: Ranking from pairwise comparisons. Operations Research, (561):266-287.
Page, E. S. (1954). Continuous Inspection Schemes. Biometrika, 41(1-2):100-115.
Plackett, R. (1975). The analysis permutations. Journal of the Royal Statistical Society. Series C (Applied Statistics), 2432):1932002.
Pollard, D. (1990). Empirical Processes: Theory and Applications. Inst Mathematical Statistic.
Preuss, P., Puchstein, R., and Dette, H. (2015). Detection of multiple structural breaks in multivariate time series. Journal of the American Statistical Association, 110(510):554-66
Radlinski, F. and Joachims, T. (2007). Active exploration for learning rankings from clickthrough data. In Proceedings of the 13th ACM SIGKDD International Conference Knowledge Discovery and Data Mining, KDD '07, pages 570-579, New York, NY, USA. ACM.
Rastogi, C., Balakrishnan, S., Shah, N., and Singh, A. (2020). Two-sample testing pairwise comparison data and the role of modeling assumptions. In 2020 IEEE International Symposium on Information Theory (ISIT), pages 1271-1276.
Ren, W., Liu, J., and Shroff, N. (2021). Sample complexity bounds for active ranking from multi- wise comparisons. In Advances in Neural Information Processing Systems, volume 34, pages 4290-4300.
Rinaldo, A., Wang, D., Wen, Q. Willett, R., and Yu, Y. (2021). Localizing changes in high- dimensional regression models. In Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pages 2099-2097. PMLR.
Scott, A. and Knott, M. (1974). A cluster analysis method for grouping means in the analysis of variance. Biometrics, 30:507.
Shah, N. B., Balakrishnan, S., Bradley, J., Parekh, A., Ramchandran, K., and Wainwright, M. J. (2016). Estimation from pairwise comparisons: Sharp minimax bounds with topology dependence. Journal of Machine Learning Research, 17(58):1-47.

---

REFERENCES
13
Shah, N. B.. Balakrishnan, S., Guntuboyina, A., and Wainwright, M. J. (2017). Stochastically transi- tive models for pairwise comparisons: Statistical and computational issues. IEEE Transactions on Information Theory, 63(2):934-955 959.
Shah, N. B. and Wainwright, M. J. (2018). Simple, robust and optimal ranking from pairwise comparisons. Journal of Machine Learning Research,
Simons, G. and Yao, Y.-C. (1999). Asymptotics when the number of parameters tends to infinity in the bradley-terry model for paired comparisons. Annals Statistics, 27(3):0441-1000.
Stigler, M. (1994). Citation patterns in the journals of statistics and probability. Statistical Science, 9:94-108.
Tang. W. (2019). Mallows ranking models: maximum likelihood estimate and regeneration. In Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 6125-6134 PMLR.
Tao, T. (2012). Topics in Random Matrix Theory. American Mathematical Society.
Tropp, J. A. (2015). An introduction matrix concentration inequalities. Foundations and Trends@ in Machine Learning, 8(1-2):1-230
Varin, C., Cattelan, M., and Firth, D. (2016). Statistical modelling of citation exchange between statistics journals. Journal of the Royal Statistical Society. Series (Statistics in Society), 179(1):1- 63.
Venkatraman, F. S. (1992). Consistency results in multiple change-point problems. Doctoral thesis, Stanford University.
Vostrikova, (1981). Detection of the disorder multidimensional random-processes. Doklady Akademii Nauk SSSR, 259:270 - 274.
Vovk, V. (2021). Testing randomness online. Statistical Science, 36(4):595 661.
Wainwright, M. J. (2019). High-Dimensional Statistics: A Non-Asymptotic Viewpoint. Cambridge: Cambridge University Press.
Wald, A. (1945). Sequential Tests of Statistical Hypotheses. The Annals of Mathematical Statistics, 16(2):117 17 186.
Wang, D., Yu, Y., and Rinaldo, A. (2020). Univariate mean change point detection: Penalization, CUSUM and optimality. Electronic Journal of Statistics, 14(1):1917- 19611.
Wang, D., Yu, Y., and Rinaldo, A. (2021a). Optimal change point detection and localization in sparse dynamic networks. The Annals of Statistics, 49(1):203 232.
Wang, D., Yu, Y., and Rinaldo, A. (2021b). Optimal covariance change point localization in high dimensions. Bernoulli, 27(1):554 -755
Wang, D. and Zhao, Z. (2022). Optimal change-poie saange-pointtto testing for high-dimensional linear models with temporal dependence. arXiv:2205.0388
Wang, D., Zhao, Z., Lin, K. Z., and Willetr, R. (2021c). Statistically and computationally efficient
change point localization in regression settings. Journal of Machine Learning Research, 22(248):1- 46.
Wang, T. and Samworth, J. (2018). High dimensional change point estimation via sparse projection. Journal of the Royal Statistical Society: Series (Statistical Methodology), 80(1):57-83.
Yao, Y.-C. and Au, S. T. (1989). Least-squares estimation of step function. Sankhyā: The Indian Journal of Statistics, Series (7961-2002), 37333383--81

---

REFERENCES
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Section 6
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See the end of Section
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes) See Section 2
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendix B
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes] See Sections and for details including a link to our anonymized reproducible code repository i.c.
https: anonymous. wao.ymous..ooon...... wwwpe..cpeeenceeeeeeee..e. wcience/r/CPD 4664
(b) Did you specify all the training details (c.g.. data splits, hyperparameters, how they were chosen)? [Yes] See Section 4
(c) Did you report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [Yes] We report standard errors of 100 trials, see Section [ (d) Did you include the total amount compute and the type of resources used (e.g.. type of GPUs, internal cluster, cloud provider)? [Yes] See the second paragraph of Section
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] We cited all relevant works of the algorithms we used at places they first occur in our paper. We also cite the collector of the data we used Section
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsoureing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]


Reviews:
[{"review_id": "iGoydVVoZBt", "reviewer": "Reviewer_4GCo", "summary": "The paper proposes a dynamic programming based algorithm to localize the change points in a high-dimensional Bradley-Terry-Luce (BTL) model with piece-wise constant parameters. The proposed algorithm is also proven to have consistent estimation of the unknown locations of the change points.", "questions": "Could the author/s answer some of my concerns in the above section? Thanks.", "limitations": "N/A", "rating": 4, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n  1. The paper considers a new problem setup for the pairwise comparison ranking problem under the piece-wise constant time-varying BTL model.\n  2. The paper proposes a dynamic programming based algorithm to locate the change points under the piece-wise constant time-varying BTL model with proven consistent estimation in the change locations.\n\nWeaknesses:\n  1. The paper is a bit hard to read/understand. Some terms/equations are not defined adequately. For example, What is the diverging sequence B_T and \\Delta_{\\kappa} in Eq.(3.3)? How to derive the equality in Eq.(3.8)? What is F(I) in Algorithm 1for loop?\n  2. The assumption of the distinct pair of items to be compared with at each time step being randomly chosen from the whole items and independently over time is very restrictive. For example, I don't think the pairs from the practical example used in the paper's Experiment section is randomly chosen and independently over time. \n  3. I am concerned with some of the statements regarding the Remark 2 on the sharpness of the signal-to-noise ratio condition and the statement for the Theorem 3.3. The author/s explained a lot in why it makes sense to be in the form of Eq.(3.3) for most parameters except the minimal winning probability p_{lb}. But p_{lb} is one of the most important parameters in this case and the explanation seems a bit weak to me. For the Theorem 3.3, the author/s conjecture that it's minimax optimal. But for a theoretical paper, it's not rigorous since for the problem setup in this paper, it assumes that the comparison data comes from some distributions. Then in what sense of minimax it is optimal? Is there any condition for that optimality? \n  4. I am also concerned with the computation complexity of the proposed algorithm, which is O(T^2C(T)), where C(T) is the complexity of solving min_{\\theta} L(\\theta, [1,T]). Since this algorithm targets the problem setup of the sequential pairwise comparison, the time horizon T is usually very large which makes the computation very slow.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "fccB0SknTYh", "reviewer": "Reviewer_4hC2", "summary": "The paper considers the problem of detecting changes in the parameters of the Bradley-Terry-Luce (BTL) model using sequential data on pairwise comparisons among items. The model assumes that the parameters are piece-wise constant, and the goal is to detect the change-points given an entire time-series where at each time step a comparison between pairs of items chosen at random is performed. The paper proposes two novel algorithms (a basic one and a more refined one) that build on standard dynamic programming approaches. The paper proves theoretical guarantees for the proposed algorithms, deriving finite sample error rates that depend explicitly on the several parameters of the model. The refined algorithm is tested and compared with a “potential” competitor (since no other algorithm is available for the same problem) on simulated data. The refined algorithm is also tested on real sports data (i.e., NBA games).", "questions": "Have you run the “potential” competitor on the NBA data? If yes, what are the difference in the results with the ones obtained with your method?", "limitations": "Yes (at the end of Section 6)", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strenghts:\n- The sequential, non-stationary scenario is original, highly significant and of practical importance\n- The main contributions are the problem definition, its formulation, and the analysis of the proposed algorithms. (The algorithms seem to fall into a fairly standard approach for similar problems.)\n- The paper is clearly written, the presentation is of high quality\n- The results on simulated data show that the method works well on data from the assumed model\n- The results on sports data seem interesting and in agreement with domain knowledge\n\nWeaknesses:\n- The BTL model seems to be less relevant and less studied than other ranking models (e.g., the Mallows model, mentioned by the authors)\n- There is no comparison with the “potential competitor” on real data. Since the simulated data comes from the model assumed by the proposed algorithms, it is not surprising that the proposed method works better than the potential competitor. It is therefore important to compare the methods on real data.\n- Algorithm 1 is poorly formatted and takes a lot of space (e.g., the if-then statement can be inline, there is no need for the “end for”, “end if”, etc.)\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "HrmdiU6FTfp", "reviewer": "Reviewer_8mZi", "summary": "This paper aims to address the novel problem of estimating multiple change points from pairwise comparison time series, which is modeled using the existing time-varying BTL model. \n\nThe comparison pair is assumed to be randomly chosen from n items (Eq. 2.1). The probability of one item beats another item is modeled as a Bernoulli distribution (Eq. 2.2). The parameter estimation can be achieved by minimizing the negative log-likelihood with regularization (Eq. 2.6, Eq. 3.1). Two algorithms (Algorithm 1 dynamic programming and Algorithm 2 local refinement) are proposed. The major contribution of this work is to prove that both algorithms are consistent under assumption 3.1 (Theorem 3.2, Theorem 3.3). \n\nExperiments on simulated data shows the proposed approach can estimate the correct number of change points and the location of those points much more accurately compared to the baseline (Table 1). ", "questions": "See the weakness section above", "limitations": "The author did address the potential negative societal impact of this work.", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n1) The major contribution of this work, i.e., estimating multiple change points from pairwise comparison time series, seems novel.\n2) The proposed algorithms have solid theoretical guarantees on the consistency, although the signal to noise ratio assumption might be difficult to check.\n3) Experiments on simulated data shows the clear advantage of the proposed approach.\n4) The motivation is clearly presented. The related works of BLT model are well introduced. \n\nWeaknesses\n1) In the simulated experiments, would it be better if the ground truth parameter \\theta^* are generated by random sampling instead of fully determined by the constant \\delta?\n2) Besides the three types of changes listed in the simulated setting, it would also be useful to see how the algorithm performs under random perturbation on \\theta^* and check how the proposed approach performs when the perturbation strength increases.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept