Exploration of Unranked Items in Safe Online Learning to Re-Rank

Hiroaki Shiino, Kaito Ariu, Kenshi Abe, Riku Togashi

Abstract

Bandit algorithms for online learning to rank (OLTR) problems often aim to maximize long-term revenue by utilizing user feedback. From a practical point of view, however, such algorithms have a high risk of hurting user experience due to their aggressive exploration. Thus, there has been a rising demand for safe exploration in recent years. One approach to safe exploration is to gradually enhance the quality of an original ranking that is already guaranteed acceptable quality. In this paper, we propose a safe OLTR algorithm that efficiently exchanges one of the items in the current ranking with an item outside the ranking (i.e., an unranked item) to perform exploration. We select an unranked item optimistically to explore based on Kullback-Leibler upper confidence bounds (KL-UCB) and safely re-rank the items including the selected one. Through experiments, we demonstrate that the proposed algorithm improves long-term regret from baselines without any safety violation.

Introduction

In Online Learning to Rank (OLTR), systems learn to order items by observing user clicks in real-time. Standard algorithms are often "aggressive" in their exploration, showing users experimental rankings to gather data. While this helps the system learn quickly, it frequently results in a poor user experience and potential disengagement.

Existing "safe" algorithms, such as BubbleRank, attempt to mitigate this by ensuring experimental rankings do not deviate significantly from a trusted "original" ranking. However, BubbleRank is primarily designed to re-order items already present in the top list. When exploring "unranked items"—new content or items currently ranked low—it relies on naive random swapping. This approach is statistically inefficient and slow to identify high-quality items that deserve higher placement.

Methodology

The authors propose KL-UCB-BR, which extends the BubbleRank framework with a more sophisticated exploration strategy. The algorithm maintains three distinct rankings:

  1. Leader Ranking ($ \sigma^{LDR} $): The current best estimate of the optimal ranking.
  2. Temporary Ranking ($ \sigma' $): A list used to safely test swaps and incorporate one "optimistically" chosen unranked item.
  3. Display Ranking ($ \sigma $): The actual list shown to the user, generated by randomly swapping adjacent items in the temporary list to gather more data.

Optimistic Exploration with KL-UCB

Instead of picking a random unranked item to test, KL-UCB-BR utilizes the Kullback-Leibler Upper Confidence Bound (KL-UCB). It calculates an optimistic attractiveness score for every unranked item and selects the one with the highest potential to outperform the item currently at the bottom of the leader list. This ensures the system prioritizes the most promising new content for exploration.

Experimental Evaluation

The researchers evaluated KL-UCB-BR using the Yandex click dataset, simulating user behavior with the PyClick library under two common models: the Position-Based Model (PBM) and the Cascade Model (CM). For each query, the top 5 items formed the "original" ranking, while the remaining 5 were treated as "unranked" items to be discovered.

Key Results

KL-UCB-BR was compared against BubbleRank and safety-agnostic methods like TopRank and UniRank.

Performance comparison of KL-UCB-BR against baselines in terms of cumulative regret and safety violations.

As shown in the experimental results, KL-UCB-BR achieved significantly lower cumulative regret than BubbleRank across both PBM and CM scenarios. While safety-agnostic methods like TopRank achieved lower regret in the long run, they incurred massive safety violations during the early stages of learning. In contrast, KL-UCB-BR and BubbleRank maintained zero safety violations throughout the experiments, demonstrating a superior balance between exploration efficiency and user experience safety.

Conclusion

KL-UCB-BR provides a model-agnostic, safe approach to exploring unranked items in OLTR. By replacing random swapping with optimistic exploration under uncertainty, it significantly outperforms existing safe baselines. Future research directions include extending the algorithm to handle item features via contextual bandit approaches and exploring multiple unranked items simultaneously to scale to larger item pools.

Summary updated

Abstract

Bandit algorithms for online learning to rank (OLTR) problems often aim to maximize long-term revenue by utilizing user feedback. From a practical point of view, however, such algorithms have a high risk of hurting user experience due to their aggressive exploration. Thus, there has been a rising demand for safe exploration in recent years. One approach to safe exploration is to gradually enhance the quality of an original ranking that is already guaranteed acceptable quality. In this paper, we propose a safe OLTR algorithm that efficiently exchanges one of the items in the current ranking with an item outside the ranking (i.e., an unranked item) to perform exploration. We select an unranked item optimistically to explore based on Kullback-Leibler upper confidence bounds (KL-UCB) and safely re-rank the items including the selected one. Through experiments, we demonstrate that the proposed algorithm improves long-term regret from baselines without any safety violation.
BibTeX
@inproceedings{shiino2023exploration,
  author = {Hiroaki Shiino and Kaito Ariu and Kenshi Abe and Riku Togashi},
  title = {{Exploration of Unranked Items in Safe Online Learning to Re-Rank}},
  booktitle = {International ACM SIGIR Conference on Research and Development in Information Retrieval},
  year = {2023},
  url = {https://openreview.net/forum?id=dyF4mNzmwA},
}
Figure