Online Learning to Rank with Features

Shuai Li, Tor Lattimore, Csaba Szepesvári

Abstract

We introduce a new model for online ranking in which the click probability factors into an examination and attractiveness function and the attractiveness function is a linear function of a feature vector and an unknown parameter. Only relatively mild assumptions are made on the examination function. A novel algorithm for this setup is analysed, showing that the dependence on the number of items is replaced by a dependence on the dimension, allowing the new algorithm to handle a large number of items. When reduced to the orthogonal case, the regret of the algorithm improves on the state-of-the-art.

Introduction

In Online Learning to Rank (OL2R), a system must present an ordered list of $K$ items to a user and learn from their interactions to optimize future rankings. This task faces two primary challenges:

  1. Combinatorial Explosion: The number of possible rankings grows exponentially with the number of positions $K$.
  2. Large Item Sets: Real-world libraries (e.g., Netflix, Google) contain millions of items ($L$). Traditional models that learn attractiveness for each item independently fail to scale.

While previous works utilized click models to simplify these issues, they often relied on rigid assumptions, such as the Cascade Model, which are sensitive to deviations in user behavior. This paper proposes a flexible model that leverages item features to handle large-scale libraries while remaining robust across various user behaviors.

Methodology: The RecurRank Algorithm

The proposed approach uses a factored click model where click probability depends on examination (whether a user views a position) and attractiveness (whether they like the item). Attractiveness is modeled as a linear function of an item's features.

To optimize this, the authors introduce RecurRank, which employs:

  • Recursive Partitioning: The algorithm treats $K$ ranking positions as intervals, starting with a single large interval and recursively splitting them as it learns.
  • G-Optimal Design: A technique from experimental design used to select items for the "top" position of an interval, minimizing uncertainty in attractiveness estimates.
  • Exploration vs. Exploitation: Within intervals, the algorithm balances learning item values and placing high-rated items in prominent spots.
Recursive partitioning of ranking instances in RecurRank.

A key innovation in RecurRank is using data only from the first position of each interval to estimate attractiveness. While seemingly data-inefficient, this prevents complex dependencies at lower positions from biasing the learning process.

Theoretical Analysis

By shifting from item-based to feature-based learning, the regret—a measure of performance loss—no longer depends heavily on the total number of items $L$, but rather on the dimension of the feature space $d$.

Comparison of regret bounds for various online learning to rank models.

The authors prove a cumulative regret bound of $R_T = O(K \sqrt{dT \log(LT)})$. As shown in the table above, when features are not used (the orthogonal case), this bound represents a $\sqrt{K}$ improvement over previous state-of-the-art results, such as those by Lattimore et al. (2018).

Empirical Evaluation

RecurRank was evaluated using synthetic simulations (Cascade Model and Position-Based Model) and the MovieLens 20m dataset.

  • Synthetic Results: RecurRank significantly outperformed TopRank, which lacks feature-based learning. It also demonstrated superior robustness compared to CascadeLinUCB; while CascadeLinUCB performs well when the model matches the Cascade Model perfectly, its performance degrades significantly under different user behaviors (e.g., PBM).
  • Real-World Data: On MovieLens, RecurRank learned faster than competitors and avoided the bias saturation that caused other models to plateau.

Conclusion and Future Work

RecurRank provides a scalable and robust framework for online ranking. However, several avenues for future research remain:

  • Data Efficiency: Exploring ways to utilize clicks from all $K$ positions without introducing bias.
  • Dynamic Item Sets: Adapting the model for environments where items are frequently added or removed.
  • Non-Linearity: Extending the attractiveness function to Generalized Linear Models to better suit practical applications like logistic regression.

Summary updated

Abstract

We introduce a new model for online ranking in which the click probability factors into an examination and attractiveness function and the attractiveness function is a linear function of a feature vector and an unknown parameter. Only relatively mild assumptions are made on the examination function. A novel algorithm for this setup is analysed, showing that the dependence on the number of items is replaced by a dependence on the dimension, allowing the new algorithm to handle a large number of items. When reduced to the orthogonal case, the regret of the algorithm improves on the state-of-the-art.
BibTeX
@inproceedings{li2019online,
  author = {Shuai Li and Tor Lattimore and Csaba Szepesvári},
  title = {{Online Learning to Rank with Features}},
  booktitle = {International Conference on Machine Learning},
  year = {2019},
  url = {https://openreview.net/forum?id=S1WuziZ_-r},
}
Figure