PaperlayerView exact revision on arXiv

Source-linked AI summary

TopRank: A practical algorithm for online stochastic ranking

Tor Lattimore, Branislav Kveton, Shuai Li, Csaba Szepesvari

arXiv:1806.02248v2stat.MLcs.LG

TL;DR

Stochastic online ranking methods often rely on specific click models, whose simplicity can risk approximation error. This paper proposes a generalized click model and TopRank, which maintains a partial order using click evidence. The authors report stronger regret guarantees and improved empirical performance despite the model's increased generality.

  • Problem

    Stochastic online ranking methods use specific click models, but simple models risk approximation error and experiments indicate no single existing model captures an entire user population.

    Source: §1 · p. 1

  • Method

    The paper generalizes the click model without requiring attractiveness–examination factorization and introduces TopRank, which refines a partial order from click evidence.

    Source: §1 · p. 2, §3 · p. 2, §4 · p. 4

  • Results

    TopRank has stronger regret guarantees and improved empirical performance than prior work despite weaker assumptions and increased model generality.

    Source: §1 · p. 2, §7 · p. 8

  • Takeaways & Limitations

    The generalized model subsumes document-based, position-based, cascade, and factored models, while TopRank's proof is described as simpler and more insightful.

    Source: §3 · p. 2, §7 · p. 8

    Matching upper and lower bounds are not yet available, and the hardest case among the broad class of allowed click functions remains unknown.

    Source: §7 · p. 9

Abstract

from arXiv · show

Online learning to rank is a sequential decision-making problem where in each round the learning agent chooses a list of items and receives feedback in the form of clicks from the user. Many sample-efficient algorithms have been proposed for this problem that assume a specific click model connecting rankings and user behavior. We propose a generalized click model that encompasses many existing models, including the position-based and cascade models. Our generalization motivates a novel online learning algorithm based on topological sort, which we call TopRank. TopRank is (a) more natural than existing algorithms, (b) has stronger regret guarantees than existing algorithms with comparable generality, (c) has a more insightful proof that leaves the door open to many generalizations, (d) outperforms existing algorithms empirically.

1 Introduction

Online learning to rank uses user clicks to adapt rankings, but stochastic methods often rely on restrictive click models whose simplicity can bring approximation error. TopRank generalizes prior work with a broader click model and a partial-order algorithm, reporting stronger regret guarantees and better empirical performance than Zoghi et al..

1 Introduction

  • Online learning to rank adapts rankings using user feedback to maximize satisfaction, building on observations that clicks can improve existing ranking policies.Ranking has applications including web search and recommender systems.Source: §1 · p. 1
  • Stochastic ranking methods use click models to address the combinatorial action set, with cascade and position-based models among the established examples [22] [10].The cascade model assumes users scan top-to-bottom and click the first attractive item; the position-based model makes click probability depend on position and attractiveness, not surrounding items.Source: §1 · p. 1
  • Cascade and position-based models are easy to learn because they have few parameters, but their simplicity risks approximation error.Experiments have found that no single existing click model captures an entire user population.Source: §1 · p. 1
  • TopRank generalizes Zoghi et al. with a click model and algorithm that empirically outperform their method and strengthen its regret results despite weaker assumptions.The authors also describe the algorithm as simpler and its proof as more insightful.Source: §1 · p. 2
  • TopRank casts finding the most attractive list as sorting with noisy feedback and does not require click probability to factor into examination and attractiveness.Its partial order is refined as observations accumulate.Source: §1 · p. 2

2 Online learning to rank

The online ranking problem selects rankings over repeated rounds and uses observed clicks to evaluate performance against an omniscient optimal ranking.

2 Online learning to rank

  • The item collection has L items and K available slots, with L > K; an action is a permutation assigning items to positions.Only the first K items are visible to the user; the ordering of items after those slots is included for notation.Source: §2 · p. 2
  • Over n rounds, the learner chooses a ranking from past observations and receives binary click indicators for the items.The click probability for a position depends on the chosen ranking.Source: §2 · p. 2
  • Performance is measured by expected cumulative regret relative to the strategy that knows the optimal ranking in advance.The model does not require click indicators to be independent or limit users to one click.Source: §2 · p. 2

3 Modeling assumptions

The model places assumptions directly on click probabilities rather than requiring the usual attractiveness–examination factorization, while still encompassing several classical click models.

3 Modeling assumptions

  • The click model assumes zero click probability for positions beyond K, which are not visible to the user.The model's relaxed assumptions subsume the document-based, position-based, cascade, and factored models studied by Zoghi et al..Source: §3 · p. 2
  • Unlike prior formulations, click probability need not factor into item attractiveness and position-examination probability.The model instead assumes an unknown attractiveness function satisfying stated assumptions.Source: §3 · p. 2
  • The assumptions require an optimal action to place items in decreasing attractiveness order, though tied attractiveness can make the optimal action non-unique.All optimal actions have the same sequence of attractiveness values in the first K positions.Source: §3 · p. 3
  • When a more attractive item is exchanged with a less attractive one, the click probability for the more attractive item's slot can only decrease under the stated comparison.The assumption also specifies a lower bound on the probability difference in terms of attractiveness.Source: §3 · p. 3
  • For rankings with the same item attractiveness at position k as an optimal ranking, the click probability at k must be at least as high.Figure 1 illustrates that the direction of the probability comparison can differ between the second and fourth positions.Source: §3 · p. 3, Figure 1 · p. 3

4 Algorithm

TopRank maintains a topological ordering of items from click evidence, grouping unresolved items into blocks and randomizing within each block to construct rankings.

4 Algorithm

  • TopRank repeatedly peels off minimum items in its current relation to form blocks, then randomizes within blocks and tracks pairwise clicks.A relation (j, i) is added when item i receives sufficiently more clicks than j while they are in the same block; it represents evidence that α(j) < α(i).Source: §4 · p. 4
  • If the relation contains cycles, the algorithm is not well defined, although the analysis shows cycles occur with low probability and permits arbitrary behavior when one occurs.The algorithm need not compute blocks placed entirely beyond the K visible slots.Source: §4 · p. 4
  • In the five-item example, the first three slots randomly contain items 1, 2, and 4, slot four contains item 3, and item 5 is not shown.The illustrated relation encodes evidence that item 3 is less attractive than item 1, and item 5 less attractive than items 2 and 3.Source: §4 · p. 4, Figure 2 · p. 4
  • TopRank is not an elimination algorithm: an item not currently shown may later be randomized into a slot as the relation changes.The example allows items 4 and 5 to be randomized for the fourth position after additional relations are added.Source: §4 · p. 4

5 Regret analysis

The analysis establishes regret upper bounds for TopRank and explains their proof through pairwise click evidence and the evolving relation among items.

5 Regret analysis

  • Under Assumptions 1–4 and strictly ordered attractiveness values, Theorem 1 gives TopRank gap-dependent and problem-independent n-step regret upper bounds.The problem-independent bound follows by stopping early in the proof of Lemma 5.Source: §5 · pp. 4, 5, 7
  • Under comparably general assumptions, BatchRank’s problem-dependent regret is a factor K^2 worse than TopRank’s.The analysis also describes its gap dependence in terms of the minimal suboptimality gap.Source: §5 · pp. 4–5
  • The proof’s core mechanism is that regret from misplacing items yields information that enriches Gt, after which the algorithm plays optimally.On the complement of the failure event, the proof bounds regret using the evolving relation and the pairwise statistics.Source: §5 · pp. 5–6
  • For items in the same block, conditional pairwise click evidence has nonnegative drift toward the more attractive item and nonpositive drift in the reverse direction.The positive drift is bounded below in terms of the attractiveness gap and the two items’ attractiveness values.Source: §5 · p. 5
  • The paper also establishes a minimax lower bound for ranking using only problems in the document-based model.The theorem’s stated setting has L = NK, with n ≥ K, n ≥ N, and N ≥ 8.Source: §5 · p. 7

6 Experiments

Experiments compare TopRank with CascadeKL-UCB and BatchRank on Yandex-derived ranking problems. TopRank improves on BatchRank across both click models, while its comparison with CascadeKL-UCB depends on the model.

6 Experiments

  • The experiments use 60 frequent queries from a 167-million-query Yandex dataset, reranking 10 documents to maximize expected clicks in the first five positions.Each query's cascade and position-based models are learned with PyClick; comparisons are against BatchRank and CascadeKL-UCB.Source: §6 · pp. 7–8
  • In average regret, CascadeKL-UCB is about three times lower than TopRank, which is about three times lower than BatchRank in the cascade model; in the position-based model, TopRank is about 30% lower than BatchRank.After 4 million steps in the position-based model, CascadeKL-UCB's regret is higher than TopRank's.Source: Figure 4 · p. 8, §6 · p. 8
  • On specific queries, CascadeKL-UCB outperforms TopRank in the cascade model, while TopRank consistently outperforms BatchRank there and typically outperforms it in the position-based model.In the position-based model, TopRank can outperform CascadeKL-UCB in as few as one million steps on some queries.Source: §6 · p. 8, Figure 3 · p. 8

7 Conclusions

The paper introduces a click model encompassing previous models and reports stronger regret guarantees and improved empirical performance for its algorithm. It also leaves open the hardest-case analysis for its broad model class and further work on exploiting item structure.

7 Conclusions

  • The new click model subsumes previous models, while the algorithm is reported to have stronger regret guarantees, a more insightful proof, and improved empirical performance despite increased generality.The paper also reports a lower bound for combinatorial linear semi-bandits with m-sets that improves on Uchiya et al.'s bound.Source: §7 · p. 8
  • Matching upper and lower bounds remain unavailable, and the authors do not yet know the hardest case among functions satisfying Assumptions 1–4.They identify exploiting item structure when the number of items is large as a future direction.Source: §7 · pp. 8–9
  • The authors suggest investigating item structure under more relaxed assumptions, building on linear-structure work for the cascade model [22].Source: §7 · p. 9

A Proof of weaker assumptions

The appendix shows that the assumptions of Zoghi et al. imply Assumptions 1–4, by constructing compatible click probabilities and attractiveness values. It also identifies one prior condition that is unnecessary and notes that the relaxed assumptions include position-based and cascade models.

A Proof of weaker assumptions

  • For any β and χ satisfying Zoghi et al.'s six conditions, the proof constructs α(i) = β(i)χ(a, 1) and v(a, k) = β(a(k))χ(a, k) to satisfy Assumptions 1–4.Condition 4 makes α independent of the choice of action a.Source: A Proof of weaker assumptions · p. 11
  • Assumption 1 follows from condition 1, and Assumption 2 follows from condition 6, while the proof of Assumption 3 uses separate cases including condition 5.Source: A Proof of weaker assumptions · p. 11
  • Assumption 4 follows from condition 2, and the proof does not use condition 3.The authors note that functions can satisfy Assumptions 1–4 without satisfying all six prior conditions.Source: A Proof of weaker assumptions · p. 11
  • The relaxed assumptions are weaker than those of Zoghi et al. and retain the position-based and cascade models.Source: A Proof of weaker assumptions · p. 11

B Proof of Lemma 6

The proof bounds a martingale-based process using exponential supermartingales and a mixture argument. A stopping-time inequality completes the upper-tail bound, after which symmetry and a union bound yield the result.

B Proof of Lemma 6

  • For λ > 0, the conditional exponential bound makes M_t(λ) a supermartingale under the defined filtration.The proof uses X_s ∈ {−1, 0, 1}.Source: B Proof of Lemma 6 · p. 11
  • Integrating M_t(λ) over a uniform distribution on [0, 2] and applying Markov's inequality bounds the probability that M_τ reaches 1/δ for a bounded measurable stopping time.Source: B Proof of Lemma 6 · p. 11
  • A stopping-time argument completes the upper-tail bound; symmetry and a union bound then yield the result.The proof cites and also points to for the stopping-time argument.Source: B Proof of Lemma 6 · p. 11

C Proof of problem independent bound in Theorem 1

The proof bounds an initial term using earlier lemmas, then combines the resulting bounds through substitution and Cauchy–Schwarz.

C Proof of problem independent bound in Theorem 1

D Proof of minimax lower bound in Theorem 2

The lower-bound proof constructs a family of document-based ranking problems and uses stopped observations and relative-entropy comparisons to show that some problem in the family yields a lower bound.

D Proof of minimax lower bound in Theorem 2

  • The lower-bound argument defines ranking problems indexed by m ∈ [N]^K; for fixed m, the optimal action has attractiveness 1/2 + ∆ for k ≤ K and 1/2 for k > K.Source: D Proof of minimax lower bound in… · p. 13
  • Regret is expressed through the counts of suboptimal items shown, then bounded using stopping times that limit each block’s observations.The stopping time τk caps Tk(τk) at n + K because at most K actions can be shown per round.Source: D Proof of minimax lower bound in… · p. 13
  • Averaging over the N^K instances yields at least one instance satisfying the resulting regret bound.The proof applies randomization over all m ∈ [N]^K and concludes by selecting an instance from the average.Source: D Proof of minimax lower bound in… · pp. 13–14
  • The comparison between problem instances bounds information using Pinsker’s inequality and relative entropy up to the stopping time.The proof uses the chain rule for relative entropy and the stated Bernoulli divergence bound.Source: D Proof of minimax lower bound in… · pp. 13–14
Loading 1806.02248v2…