Timezone: »

 
Poster
Minimax Regret for Cascading Bandits
Daniel Vial · Sujay Sanghavi · Sanjay Shakkottai · R. Srikant

Thu Dec 01 09:00 AM -- 11:00 AM (PST) @ Hall J #315
in Poster Session 5 »

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.

Keywords: online learning-to-rank · linear stochastic bandits · cascading bandits
[ Paper]  [ Poster]  [ OpenReview] 

Author Information

Daniel Vial (UT Austin / UIUC)
Sujay Sanghavi (UT-Austin)
Sanjay Shakkottai (University of Texas at Austin)
R. Srikant (University of Illinois at Urbana-Champaign)

More from the Same Authors