Online Learning to Rank with Features

Shuai Li, Tor Lattimore, Csaba Szepesvári

This ICML 2019 paper by Shuai Li, Tor Lattimore, and Csaba Szepesvári tackles one of the most persistent challenges in recommendation systems: how to learn to rank items effectively when you have millions of items but only a few slots to show them.

TL;DR

The authors introduce RecurRank, an algorithm for online learning to rank that scales with the dimension of item features rather than the total number of items. By combining a flexible, factored click model with linear experimental design, they achieve a state-of-the-art regret bound that is significantly more robust than previous approaches.

The Challenge of Online Ranking

In online ranking scenarios like search results or movie recommendations, a learner must choose an ordered list of $K$ items from a large pool $L$ to show a user. The ultimate goal is to maximize clicks.

There are two massive hurdles in this domain:

  1. The Combinatorial Explosion: The number of possible rankings is astronomical, making brute-force exploration impossible.
  2. The "Large $L$" Problem: Most existing algorithms try to learn the "attractiveness" of every single item individually. If you have millions of items, you’ll never collect enough data to rank them all accurately.

Previous solutions often relied on very rigid "click models" (like the Cascade Model) which assume users scan results in a very specific, linear way. If real-world user behavior doesn't perfectly match that model, these algorithms fail. This paper seeks a middle ground: a model flexible enough to handle various user behaviors, but structured enough to handle massive item sets using features.

Methodology: A Factored, Feature-Based Approach

The authors propose a factored model where the probability of a click on an item depends on two distinct components:

  • Examination ($\chi$): The probability the user actually looks at that position.
  • Attractiveness ($\alpha$): The inherent appeal of the item.

The "secret sauce" is assuming that attractiveness is a linear function of features: $\alpha(a) = \langle a, \theta_* \rangle$. This allows the algorithm to generalize. For example, learning about one "action movie" helps it predict the attractiveness of other action movies it hasn't seen yet, drastically reducing the exploration space.

The RecurRank Algorithm

RecurRank operates by recursively partitioning the $K$ available positions into intervals.

Recursive partitioning of ranking positions in the RecurRank algorithm.
  • Exploration via G-Optimal Design: Within each interval, it uses "G-optimal design"—a technique from experimental design—to pick items for the first position of that interval. This ensures the algorithm learns the most about the unknown parameter $\theta$ with the fewest possible samples.
  • Exploitation: The remaining positions in the interval are filled with items the algorithm currently thinks are the best.
  • Recursive Splitting: Once the algorithm is confident enough about the relative attractiveness of items, it splits the interval into smaller sub-intervals and repeats the process with higher precision.

Key Results and Performance

The authors evaluated RecurRank using both synthetic environments (simulating users following the Cascade Model and the Position-Based Model) and a real-world dataset (MovieLens 20m, using SVD to extract 5-dimensional features for 1,000 movies).

Cumulative regret across Cascade Model (CM), Position-Based Model (PBM), and MovieLens datasets. RecurRank (red) consistently outperforms or matches baselines.
  • Theoretical Bound: They prove a cumulative regret bound of $R_T = O(K \sqrt{dT} \log(LT))$. This confirms that the dependence on the number of items $L$ is only logarithmic, meaning the complexity scales with the feature dimension $d$ instead. This is the difference between an algorithm that works on a toy dataset and one that works on Netflix.
  • Robustness on PBM: In simulations where the popular CascadeLinUCB algorithm failed due to model mismatch (the Position-Based Model), RecurRank continued to perform excellently because of its more flexible assumptions.
  • MovieLens Success: On the MovieLens dataset, RecurRank learned significantly faster than TopRank and achieved much lower regret than CascadeLinUCB, which suffered from "incorrect bias" in its model.

Limitations and Future Work

While RecurRank represents a significant step forward, the authors note a few areas for future improvement:

  • Data Waste: Currently, RecurRank only uses click data from the first position of each interval to estimate attractiveness. This keeps the math clean and avoids bias, but it's inefficient. Using data from all positions is a primary area for future work.
  • Static Item Sets: The paper assumes the set of items $L$ is fixed, whereas real-world systems constantly add or remove items.
  • Linearity Assumption: While linear models are powerful, some attractiveness functions might be non-linear. Extending this to Generalized Linear Models (GLMs) could provide even more flexibility.
  • Computational Complexity: Finding the G-optimal design is a convex optimization problem. While solvable, it adds computational overhead compared to simpler heuristic-based rankers.

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