Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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).
strengths_and_weaknesses: Strenghts:
- The sequential, non-stationary scenario is original, highly significant and of practical importance
- 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.)
- The paper is clearly written, the presentation is of high quality
- The results on simulated data show that the method works well on data from the assumed model
- The results on sports data seem interesting and in agreement with domain knowledge

Weaknesses:
- The BTL model seems to be less relevant and less studied than other ranking models (e.g., the Mallows model, mentioned by the authors)
- 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.
- 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.)

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)
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: 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.
strengths_and_weaknesses: Strengths:
  1. The paper considers a new problem setup for the pairwise comparison ranking problem under the piece-wise constant time-varying BTL model.
  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.

Weaknesses:
  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?
  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. 
  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? 
  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.

questions: Could the author/s answer some of my concerns in the above section? Thanks.
limitations: N/A
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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. 

The 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). 

Experiments 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). 
strengths_and_weaknesses: Strengths
1) The major contribution of this work, i.e., estimating multiple change points from pairwise comparison time series, seems novel.
2) The proposed algorithms have solid theoretical guarantees on the consistency, although the signal to noise ratio assumption might be difficult to check.
3) Experiments on simulated data shows the clear advantage of the proposed approach.
4) The motivation is clearly presented. The related works of BLT model are well introduced. 

Weaknesses
1) 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?
2) 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.
questions: See the weakness section above
limitations: The author did address the potential negative societal impact of this work.
review_title: null

Meta-review: metareview: In *Detecting Abrupt Changes in Sequential Pairwise Comparison Data* the authors consider the problem of detecting multiple change points in sequential pairwise comparison data.  The reviewers in general consider the model both well-motivated and novel.  For these reasons I recommend that this paper be accepted.

confidence: Certain
Decision: Accept