Minimax Regret for Cascading Bandits

Daniel Vial, Sujay Sanghavi, Sanjay Shakkottai, R. Srikant

Abstract

Cascading bandits is a natural and popular model that frames the task of learning to rank from Bernoulli click feedback in a bandit setting. For the case of unstructured rewards, we prove matching upper and lower bounds for the problem-independent (i.e., gap-free) regret, both of which strictly improve the best known. A key observation is that the hard instances of this problem are those with small mean rewards, i.e., the small click-through rates that are most relevant in practice. Based on this, and the fact that small mean implies small variance for Bernoullis, our key technical result shows that variance-aware confidence sets derived from the Bernstein and Chernoff bounds lead to optimal algorithms (up to log terms), whereas Hoeffding-based algorithms suffer order-wise suboptimal regret. This sharply contrasts with the standard (non-cascading) bandit setting, where the variance-aware algorithms only improve constants. In light of this and as an additional contribution, we propose a variance-aware algorithm for the structured case of linear rewards and show its regret strictly improves the state-of-the-art.

Introduction

In modern information retrieval and recommendation systems, the cascading click model serves as a foundational framework for understanding user behavior. In this model, a user is presented with a list of $K$ items and scans them sequentially from top to bottom. The user clicks on the first attractive item they encounter and then terminates the session. If no items are attractive, the user scans the entire list and leaves without clicking.

Learning to rank in this environment involves a "bandit" problem: the system must decide which items to display to maximize clicks (or minimize regret) while simultaneously learning the attractiveness of each item. Despite the popularity of this model, a significant gap persisted in the theoretical understanding of its regret bounds. This paper resolves that gap, demonstrating that the secret to optimal performance lies in "variance-aware" uncertainty estimation.

The Theoretical Gap

Prior to this work, the "problem-independent" (gap-free) regret bounds for cascading bandits were inconsistent. Existing upper bounds suggested a regret of $\tilde{O}(\sqrt{nLK})$, where $n$ is the number of rounds, $L$ is the total number of items, and $K$ is the list length. Conversely, lower bounds were estimated at $\Omega(\sqrt{nL/K})$.

This discrepancy left a fundamental question unanswered: as the list length $K$ increases, does the problem become harder or easier? This paper proves that the true minimax regret is $\Theta(\sqrt{nL})$, making it independent of $K$. This result reveals that the two effects of increasing $K$—the increased difficulty of finding $K$ good items versus the benefit of receiving more feedback per round—perfectly cancel each other out.

Why Variance Awareness Matters

The core insight of this research is that the "hardest" instances of cascading bandits occur when click-through rates (CTRs) are very low (e.g., $p < 1/K$). Because clicks are modeled as Bernoulli trials, a small mean reward $p$ mathematically necessitates a small variance $p(1-p)$.

Standard algorithms like CascadeUCB1 use Hoeffding-style Upper Confidence Bounds (UCB), which treat all uncertainty identically regardless of the underlying variance. In standard multi-armed bandits, this only results in suboptimal constant factors. However, in the cascading setting, the authors demonstrate that variance-unaware algorithms are fundamentally suboptimal, suffering regret that scales with $\sqrt{K}$.

By utilizing variance-aware confidence sets—derived from Bernstein or Chernoff inequalities—algorithms like CascadeKL-UCB and CascadeUCB-V can achieve the optimal $\Theta(\sqrt{nL})$ regret. These methods create tighter confidence intervals when the mean reward is small, effectively decoupling the learning penalty from the length of the recommendation list.

Extending to the Linear Case: CascadeWOFUL

Moving beyond the tabular case, the paper addresses structured rewards where items are represented by feature vectors. The authors introduce CascadeWOFUL (Weighted Oracle-based Frequentist Upper-confidence bound for Linear bandits).

CascadeWOFUL employs a two-step estimation process:

  1. Coarse Estimation: It uses a standard Hoeffding bound to get an initial estimate of an item's variance.
  2. Refined Regression: It uses that variance estimate as a weight in a Bernstein-style linear regression to produce a highly precise estimate of item attractiveness.

This approach achieves a regret of $\tilde{O}(\sqrt{nd(d+K)})$, a significant improvement over the previous state-of-the-art $\tilde{O}(\sqrt{nd^2K})$, particularly when the feature dimension $d$ is large.

Empirical Validation

The theoretical findings were validated using both synthetic data and the MovieLens-1M dataset. In the MovieLens experiments, ratings were converted to binary feedback (4-5 stars as "attractive"), and SVD was used to generate item features.

Key empirical results include:

  • CascadeWOFUL incurred less than 66% of the regret compared to previous linear cascading algorithms.
  • The performance gains were most pronounced in genres with low click-through rates, confirming the importance of variance awareness in realistic, low-CTR environments.

Conclusion

This work settles the debate regarding the minimax regret of cascading bandits, proving it to be $\Theta(\sqrt{nL})$. By demonstrating that variance awareness is a mathematical necessity for optimality in this setting, the paper provides a clear path forward for designing more efficient recommendation systems. While the focus remains on UCB-based methods, the results suggest that revisiting other frameworks, such as Thompson Sampling, through the lens of variance awareness could yield further breakthroughs.

Summary updated

Abstract

Cascading bandits is a natural and popular model that frames the task of learning to rank from Bernoulli click feedback in a bandit setting. For the case of unstructured rewards, we prove matching upper and lower bounds for the problem-independent (i.e., gap-free) regret, both of which strictly improve the best known. A key observation is that the hard instances of this problem are those with small mean rewards, i.e., the small click-through rates that are most relevant in practice. Based on this, and the fact that small mean implies small variance for Bernoullis, our key technical result shows that variance-aware confidence sets derived from the Bernstein and Chernoff bounds lead to optimal algorithms (up to log terms), whereas Hoeffding-based algorithms suffer order-wise suboptimal regret. This sharply contrasts with the standard (non-cascading) bandit setting, where the variance-aware algorithms only improve constants. In light of this and as an additional contribution, we propose a variance-aware algorithm for the structured case of linear rewards and show its regret strictly improves the state-of-the-art.
BibTeX
@inproceedings{vial2022minimax,
  author = {Daniel Vial and Sujay Sanghavi and Sanjay Shakkottai and R. Srikant},
  title = {{Minimax Regret for Cascading Bandits}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=EgMbj9yWrMI},
}
Figure