Ranking Bandits · Vaibhav on HTTPS

Corresponds to Lattimore & Szepesvári, Chapter 32.

Motivation: rankings are too many to treat as arms

IntuitionThe problem

A streaming service shows each user an ordered shortlist of $m$ movies out of $\ell$ , with no query. The user clicks on what they like, possibly several items, and the goal is to maximise expected clicks over $n$ rounds. There are $\ell!/(\ell - m)!$ ordered shortlists, so treating each as an independent arm is hopeless. Ranking illustrates the fundamental model-choice dilemma: a rich model of clicks has low misspecification error but is slow to learn, while a coarse model learns fast but may be wrong. The book’s coverage is deliberately narrow; practical large-scale online ranking is still far off.

DefinitionStochastic ranking

Actions are permutations $\mathcal A$ of $[\ell]$ : $A_t(k)$ is the item in position $k$ , and $A_t^{-1}(i)$ is item $i$ ‘s position. Only the first $m$ positions are shown. The learner observes click indicators $C_{ti}\in\{0,1\}$ for every item. The probability of a click at position $k$ under ranking $a$ is $v(a,k)$ , an unknown function $v : \mathcal A\times[\ell]\to[0,1]$ :

$R_n = n\max_{a\in\mathcal A}\sum_{k=1}^\ell v(a,k) - \mathbb E\Big[\sum_{t=1}^n\sum_{i=1}^\ell C_{ti}\Big]$

Click models

NoteAttractiveness times examination

Every standard model says a click needs the item to be attractive (an item property $\alpha(i)\in[0,1]$ ) and its position to be examined (depending on the position, and possibly on the items above it). Which model fits depends on the interface, for example whether clicking navigates away. The information-retrieval literature studies this extensively (Chuklin et al. 2015; Craswell et al. 2008).

Model	$v(a,k)$	Parameters	When appropriate
Document-based	$\alpha(a(k))\,\mathbb I\{k\le m\}$	$\ell$	position irrelevant within the shortlist
Position-based	$\alpha(a(k))\,\chi(k)$ , with $\chi(k) = 0$ for $k > m$	$\ell + m$	fixed examination probability per slot
Cascade	$\alpha(a(k))\,\chi(a,k)$ , $\chi(a,k) = \prod_{k'<k}(1 - \alpha(a(k')))$ for $1 < k\le m$ , $\chi(a,1) = 1$	$\ell$	user scans in order and stops at the first click (clicking leaves the page)

WarningMarginals, not independence

$v(a,k)$ fixes only each click’s marginal probability. The $C_{ti}$ need not be independent. In the cascade model, the standard generative story has at most one click: $C_{t,A_t(k)} = 0$ once an earlier position was clicked, and otherwise the click probability given no earlier click is $\alpha(A_t(k))$ .

The generic model

Definition $\alpha$ -optimal action

An action is $\alpha$ -optimal if it shortlists the $m$ most attractive items, sorted: $\alpha(a(k)) = \max_{k'\ge k}\alpha(a(k'))$ for all $k\in[m]$ .

DefinitionAssumption 32.1

There is an attractiveness function $\alpha$ such that, for any action $a$ , items $i, j$ with $\alpha(i)\ge\alpha(j)$ , and $\sigma$ the transposition of $i$ and $j$ :

No clicks off the list: $v(a,k) = 0$ for $k > m$ .
Sorted is optimal: every $\alpha$ -optimal $a^*$ maximises $\sum_{k\le m}v(a,k)$ .
Swapping changes clicks at least proportionally to attractiveness: $v(a,a^{-1}(i))\ge\frac{\alpha(i)}{\alpha(j)}v(\sigma\circ a,a^{-1}(i))$ . Putting the better item $i$ in a slot instead of $j$ raises that slot’s click probability by at least the factor $\alpha(i)/\alpha(j)$ .
Correct placements are never worse off: if $\alpha(a(k)) = \alpha(a^*(k))$ for some $\alpha$ -optimal $a^*$ , then $v(a,k)\ge v(a^*,k)$ .

IntuitionWhy these assumptions are reasonable

Write $v(a,k) = \alpha(a(k))\chi(a,k)$ , with examination depending only on the items above $k$ .

(3) If $i$ ‘s slot is above $j$ ‘s, the swap leaves everything above $i$ ‘s slot unchanged, so the ratio is exactly $\alpha(i)/\alpha(j)$ . If $i$ ‘s slot is below, the swap puts the better item $i$ higher up, which can only lower examination of the later slot. This relies on users searching harder after unattractive items, the most easily criticised assumption.
(4) Items above a correctly placed item can’t be more attractive than those in the optimal list, so that position is examined at least as often.

Assumption 32.1 is partly chosen so the proof works, but it contains all three models (Exercise 32.1). There are many parameters, but the learner never needs to learn $\chi$ , only the order of $\alpha$ .

ProofThe cascade model satisfies (3) and (4) (Exercise 32.1, sketch)

(3): let $k = a^{-1}(i)$ . If $j$ sits below $k$ , the items above $k$ are unchanged, so $\chi(\sigma\circ a,k) = \chi(a,k)$ and equality holds. If $j$ sits above (at $k' < k$ ), then in $\sigma\circ a$ the better item $i$ is at $k'$ , so $\chi(\sigma\circ a,k) = \chi(a,k)\frac{1 - \alpha(i)}{1 - \alpha(j)}\le\chi(a,k)$ , and $v(a,k) = \alpha(i)\chi(a,k)\ge\frac{\alpha(i)}{\alpha(j)}\alpha(j)\chi(\sigma\circ a,k)$ .

(4): the $\alpha$ -optimal list puts the top $k-1$ items above $k$ , so any other list has items above $k$ that are no more attractive. Hence $\prod_{k'<k}(1 - \alpha(a(k')))\ge\prod_{k'<k}(1 - \alpha(a^*(k')))$ .

The position-based model satisfies (3) with equality, and the document-based model is the special case $\chi(k) = \mathbb I\{k\le m\}$ . (Sketch worked here.)

∎

The TopRank policy

AlgorithmTopRank (Lattimore et al. 2018)

Step 0: input $\delta$ , $\ell$ , $m$ . Set the relation $G_1 = \emptyset$ . A pair $(i,j)\in G_t$ means “proved with high probability that $\alpha(i) < \alpha(j)$ ”.

Step 1: Layer by topological sort. With $\min_{G_t}(A) = \{i\in A : (i,j)\notin G_t\ \forall j\in A\}$ (items not proven worse than any remaining item),

$\mathcal P_{td} = \min_{G_t}\Big([\ell]\setminus\bigcup_{c<d}\mathcal P_{tc}\Big),\qquad d = 1, \ldots, M_t$

If $G_t$ is acyclic, this is a partition of $[\ell]$ (Exercise 32.5). A cycle is a failure event; then play any fixed action.

Step 2: Shuffle within layers. Layer $d$ gets the consecutive positions $\mathcal I_{td}$ , which follow the earlier layers’ positions. $A_t$ is uniform over the rankings with $\sigma(\mathcal I_{td}) = \mathcal P_{td}$ for all $d$ : shuffle layer 1 into the top slots, then layer 2, and so on. $D_{ti}$ denotes item $i$ ‘s layer.

Step 3: Compare items only within a layer. With $U_{tij} = \mathbb I\{D_{ti} = D_{tj}\}(C_{ti} - C_{tj})$ , $S_{tij} = \sum_{s\le t}U_{sij}$ and $N_{tij} = \sum_{s\le t}\lvert U_{sij}\rvert$ ,

$G_{t+1} = G_t\cup\Big\{(j,i) : S_{tij}\ge\sqrt{2N_{tij}\log\frac{c\sqrt{N_{tij}}}\delta}\Big\}$

with $c\approx3.43$ from the ternary-martingale bound (Exercise 20.10).

ExampleOne round, worked

With $\ell = 5$ , $m = 4$ and $G_t = \{(3,1),(5,2),(5,3)\}$ (item 3 proven worse than 1; item 5 worse than 2 and 3):

$\mathcal P_{t1} = \{1,2,4\}$ (none proven worse than a rival), placed in positions $\{1,2,3\}$ in random order;
$\mathcal P_{t2} = \{3\}$ in position 4;
$\mathcal P_{t3} = \{5\}$ , not shown.

Only layers whose positions reach $m$ need computing.

IntuitionWhy shuffle and why compare only within layers

Shuffling makes items in a layer exchangeable in position. A click difference between two layer-mates then reflects attractiveness only: position effects cancel in expectation. This is why $\chi$ never needs to be learned.
The certification rule is a sequential test on a $\{-1,0,1\}$ -valued martingale, counting only informative rounds (exactly one of the two clicked). It is anytime-valid, so $G_t$ stays consistent with the true order.
Layers refine over time: certified pairs split layers, so items settle into their correct positions. $G_t$ need not be transitive; it is just a set of certified comparisons.

Regret analysis

TheoremTheorem 32.2 — Regret of TopRank

Under Assumption 32.1, labelling items so that $\alpha(1) > \cdots > \alpha(\ell)$ (for presentation only; the algorithm doesn’t use the order), with $\Delta_{ij} = \alpha(i) - \alpha(j)$ :

$R_n\le\delta nm\ell^2 + \sum_{j=1}^\ell\sum_{i=1}^{\min\{m,j-1\}}\Big(1 + \frac{6(\alpha(i) + \alpha(j))\log(c\sqrt n/\delta)}{\Delta_{ij}}\Big)$

and $R_n\le\delta nm\ell^2 + m\ell + \sqrt{4m^3\ell n\log(c\sqrt n/\delta)}$ . With $\delta = 1/n$ :

$R_n = O\Big(\sum_{j=1}^\ell\sum_{i\le\min\{m,j-1\}}\frac{\alpha(i)\log n}{\Delta_{ij}}\Big),\qquad R_n = O\big(\sqrt{m^3\ell n\log n}\big)$

IntuitionProof plan

(a) Misplacing items costs regret only while the algorithm is gaining information that will certify the right order. (b) Once $G_t$ is rich enough, the play is optimal. Only pairs involving a top- $m$ item $i$ matter: that is the double sum’s range.

LemmaLemma 32.3 — Within a layer, better items get clicked more

If $\alpha(i)\ge\alpha(j)$ share layer $d$ in round $s$ , then on $\{U_{sij}\ne0\}$ :

$\mathbb E_{s-1}[U_{sij}\mid U_{sij}\ne0]\ge\frac{\Delta_{ij}}{\alpha(i) + \alpha(j)},\qquad\mathbb E_{s-1}[U_{sji}\mid U_{sji}\ne0]\le0$

ProofExchangeability from shuffling, plus Assumption 32.1(3)

Step 1: adding and subtracting $\mathbb P(C_i = C_j = 1)$ ,

$\mathbb E[U\mid U\ne0] = \frac{\mathbb P(C_i = 1) - \mathbb P(C_j = 1)}{\mathbb P(C_i\ne C_j)}\ge\frac{\mathbb E\,v(A,A^{-1}(i)) - \mathbb E\,v(A,A^{-1}(j))}{\mathbb E\,v(A,A^{-1}(i)) + \mathbb E\,v(A,A^{-1}(j))} \tag{32.2}$

using $\mathbb P(C_i\ne C_j)\le\mathbb P(C_i = 1) + \mathbb P(C_j = 1)$ (the numerator is nonnegative by Step 2).

Step 2: Swap symmetry. TopRank makes $a$ and $\sigma\circ a$ equally likely ( $\sigma$ swaps $i, j$ ), and $a^{-1}(i) = (\sigma\circ a)^{-1}(j)$ . By Assumption 32.1(3),

$\mathbb E\,v(A,A^{-1}(i))\ge\frac{\alpha(i)}{\alpha(j)}\sum_a\mathbb P(A = \sigma\circ a)\,v(\sigma\circ a,(\sigma\circ a)^{-1}(j)) = \frac{\alpha(i)}{\alpha(j)}\mathbb E\,v(A,A^{-1}(j))$

Step 3: the ratio $\frac{x - y}{x + y} = 1 - \frac2{1 + x/y}$ increases in $x/y\ge\alpha(i)/\alpha(j)$ , so it is at least $\frac{\alpha(i) - \alpha(j)}{\alpha(i) + \alpha(j)}$ . Part 2 follows from $U_{sji} = -U_{sij}$ .

∎

LemmaLemmas 32.4–32.6 — Certifications are correct, so layers are well-ordered

Let $F_t$ be the event that some pair’s sum $S_{sij}$ deviates from its conditional drift $\sum_u\mathbb E_{u-1}[U_{uij}\mid U_{uij}\ne0]\lvert U_{uij}\rvert$ by at least the boundary $\sqrt{2N_{sij}\log(c\sqrt{N_{sij}}/\delta)}$ , for some $s < t$ .

32.4: $\mathbb P(F_n)\le\delta\ell^2$ (union bound over pairs and the ternary-martingale bound).
32.5: on $F_t^c$ , no wrong pair is ever certified: $(i,j)\notin G_t$ when $i < j$ . The drift of $S_{sji}$ is at most 0 by Lemma 32.3, so it never crosses the boundary.
32.6: on $F_t^c$ , layer $d$ ‘s best item satisfies $I_{td}^* = \min\mathcal P_{td}\le1 + \sum_{c<d}\lvert\mathcal P_{tc}\rvert$ . Each layer contains an item at least as good as the item that belongs in its first slot. If the overall best remaining item sits in a later layer, a chain of correct certifications links it back to a strictly better item in layer $d$ .

LemmaLemma 32.7 — Each pair’s click gap stays logarithmic

On $F_n^c$ , for $i < j$ : $S_{nij}\le1 + \frac{6(\alpha(i) + \alpha(j))}{\Delta_{ij}}\log\frac{c\sqrt n}\delta$ .

ProofThe drift pushes

S

up, certification caps it

Once $S_{tij}$ crosses the boundary, $i$ and $j$ are split into different layers and stop accumulating, so $S_{nij}\le1 + \sqrt{2N\log(c\sqrt N/\delta)}$ . On $F_n^c$ and by Lemma 32.3, $S_{nij}\ge\frac{\Delta_{ij}N}{\alpha(i) + \alpha(j)} - \sqrt{2N\log(\cdot)}$ . Combining: $\frac{\Delta_{ij}N}{\alpha(i) + \alpha(j)}\le(1 + 2\sqrt2)\sqrt{N\log\frac{c\sqrt n}\delta}$ , so $N\le\frac{(1 + 2\sqrt2)^2(\alpha(i) + \alpha(j))^2}{\Delta_{ij}^2}\log(\cdot)$ . Substituting back, $S\le1 + \sqrt2(1 + 2\sqrt2)\frac{\alpha(i) + \alpha(j)}{\Delta_{ij}}\log(\cdot)$ , and $\sqrt2(1 + 2\sqrt2)\approx5.4\le6$ .

∎

ProofProof of Theorem 32.2: optimal clicks are captured layer by layer

Step 1: Each layer’s best item collects the optimal clicks for its slots. Fix layer $d$ and $I^* = I_{td}^*$ , placed uniformly in $\mathcal I_{td}$ . By Lemma 32.6, $I^*$ belongs at or above any of these slots. Assumptions 32.1(3–4) give $v(A_t,k)\ge v(\sigma\circ A_t,k)\ge v(a^*,k)$ for $I^*$ in slot $k$ . Hence $\mathbb E_{t-1}[C_{tI^*}]\ge\frac1{\lvert\mathcal I_{td}\rvert}\sum_{k\in\mathcal I_{td}}v(a^*,k)$ and $\sum_{k\le m}v(a^*,k)\le\sum_d\lvert\mathcal I_{td}\rvert\,\mathbb E_{t-1}[C_{tI_{td}^*}]$ .

Step 2: Per-round regret becomes within-layer click differences.

$\sum_kv(a^*,k) - \mathbb E_{t-1}\sum_jC_{tj}\le\sum_d\sum_{j\in\mathcal P_{td}}\mathbb E_{t-1}[U_{tI_{td}^*j}]\le\sum_{j=1}^\ell\sum_{i=1}^{\min\{m,j-1\}}\mathbb E_{t-1}[U_{tij}] \tag{32.4}$

since $\mathbb E[U_{tij}]\ge0$ for $i < j$ (Lemma 32.3), and layers whose best item is beyond $m$ aren’t shown.

Step 3: Sum over time. At most $nm$ clicks occur in total, so $R_n\le nm\mathbb P(F_n) + \sum_j\sum_{i\le\min\{m,j-1\}}\mathbb E[\mathbb I\{F_n^c\}S_{nij}]$ (32.5). Apply Lemmas 32.4 and 32.7. The worst-case bound comes from stopping the proof of Lemma 32.7 early (Exercise 32.6).

∎

ImportantWhat makes TopRank work

Randomising within layers turns an unknown, position-dependent click model into pairwise duels whose drift depends only on attractiveness. The regret is a sum over pairs involving a top- $m$ item of “duel length × gap”, the ranking analogue of $\sum\log n/\Delta$ . The $\alpha(i) + \alpha(j)$ factor makes regret small when items are rarely clicked, KL-UCB-style.

Notes

RemarkRobust to time-varying click models (Note 1)

The analysis never used that $v$ is fixed. If $v_1, \ldots, v_n$ all satisfy Assumption 32.1 with the same $\alpha$ , the same bounds hold for the regret $\sum_t\sum_kv_t(a^*,k) - \mathbb E\sum_{t,i}C_{ti}$ , with no change to the algorithm. This is a structured form of non-stationarity.

AlgorithmCascade bandits with independence (Note 2)

The usual cascade formalisation: $Z_{ti}\sim\mathrm{Bernoulli}(\alpha(i))$ independent; $M_t = \min\{k\le m : Z_{tA_t(k)} = 1\}$ ; $C_{ti} = 1$ iff $M_t\le m$ and $A_t(M_t) = i$ . Each round reveals that all items above the click were unattractive and the clicked one attractive, so $\alpha$ can be estimated directly with no randomisation. Sort items by upper confidence bounds and show the top $m$ : CascadeUCB (Hoeffding) or CascadeKL-UCB (Chernoff; KL-UCB). KL helps a lot in practice because most attractiveness values are barely above zero (Kveton et al. 2015; asymptotically optimal variants by Combes et al. 2015).

RemarkScaling with $\ell$ (Note 3)

The linear dependence on $\ell$ hurts with huge catalogues. Assume $\alpha(i) = \langle\theta,\phi_i\rangle$ with known features, the linear-bandit idea (cascade: Zong et al. 2016; generic: Li et al. 2019).

DefinitionAdversarial ranked bandits (Notes 4–5; Radlinski et al. 2008)

The adversary picks sets $S_t\subseteq[\ell]$ of items the user would like. The reward is 1 iff some shortlisted item is in $S_t$ : $X_t(a) = \mathbb I\{S_t\cap\{a(1), \ldots, a(m)\}\ne\emptyset\}$ . The feedback is the first clicked position. This is the cascade model with $S_t = \{i : Z_{ti} = 1\}$ .

The offline problem, best ranking in hindsight, is NP-hard (maximum coverage).
If $\ell, m$ are small, exhaustive search works. Otherwise the greedy approach is essentially the best possible: there are efficient algorithms with $\mathbb E\sum_tX_t(A_t)\ge(1 - \frac1e)\max_a\sum_tX_t(a) - O(m\sqrt{n\ell\log\ell})$ . This is approximate regret against a $(1 - 1/e)$ -scaled benchmark.

TheoremAdversarial document- and position-based ranking as semi-bandits (Exercises 32.3–32.4)

Document-based ( $X_t(a) = \lvert S_t\cap\{a(1), \ldots, a(m)\}\rvert$ , clicks on shown items observed): a combinatorial semi-bandit over $m$ -sets with $d = \ell$ . Theorem 30.2 gives $R_n\le\sqrt{2m\ell n(1 + \log\ell)}$ .
Position-based ( $X_t(a) = \sum_k\mathbb I\{a(k)\in S_{tk}\}$ ): coordinates are (item, position) pairs, $d = m\ell$ , and actions are assignments with $\lVert a\rVert_1 = m$ . Theorem 30.2 gives $\sqrt{2nm\cdot m\ell(1 + \log\ell)} = m\sqrt{2\ell n(1 + \log\ell)}$ .

(Reductions sketched here.) No computational issues arise for the document-based case: $m$ -sets are efficient.

ExampleThe diversity critique (Exercise 32.2)

Radlinski et al. argue against ranking by individual relevance (the probability ranking principle, Maron–Kuhns 1960; validity conditions in Robertson 1977). Relevance probabilities are dependent: if one “jaguar car” page is irrelevant, the others probably are too. Relevance varies across users. And users want one good result. So the right objective is “at least one attractive item” (coverage), which favours diverse lists.

Counterpoints: whether the critique bites depends on the objective. For total clicks under document- or position-based models, sorting by attractiveness is optimal (Assumption 32.1(2)). For satisfaction-style objectives with correlated preferences (the cascade/coverage view), diversity matters. Assumption 32.1(3)‘s “search harder after bad items” is exactly where the two views diverge.

RemarkRelated models

Position-based model algorithms with logarithmic regret and lower bounds: Lagrée et al. (2016). Dependent click model, where the reward is unobserved satisfaction: Katariya et al. (2016). Rank-1 bandits (one item in one of $m$ positions): Katariya et al. (2017). TopRank generalises Zoghi et al. (2017), who factored $v = \alpha\chi$ and constrained $\chi$ , with weaker assumptions and stronger bounds. Practical issues such as cold start: Glowacka (2019).

Quick reference

Object	Statement	Note
Action	permutation $a$ ; top $m$ shown	$\ell!/(\ell-m)!$ rankings
Regret	$n\max_a\sum_kv(a,k) - \mathbb E\sum_{t,i}C_{ti}$	clicks
Document-based	$\alpha(a(k))\mathbb I\{k\le m\}$	$\ell$ parameters
Position-based	$\alpha(a(k))\chi(k)$	$\ell + m$ parameters
Cascade	$\alpha(a(k))\prod_{k'<k}(1 - \alpha(a(k')))$	first click only
Generic	Assumption 32.1(1)–(4)	contains all three
TopRank	topological layers of certified pairs, shuffled	learns the order of $\alpha$ only
Certification	$S_{tij}\ge\sqrt{2N_{tij}\log(c\sqrt{N_{tij}}/\delta)}$	ternary martingale, $c\approx3.43$
Duel drift	$\mathbb E[U_{ij}\mid U_{ij}\ne0]\ge\Delta_{ij}/(\alpha(i) + \alpha(j))$	from shuffling + Assumption 32.1(3)
Duel length	$S_{nij}\le1 + 6\frac{\alpha(i) + \alpha(j)}{\Delta_{ij}}\log\frac{c\sqrt n}\delta$
Regret	$O(\sum_j\sum_{i\le\min(m,j-1)}\alpha(i)\log n/\Delta_{ij})$ ; $O(\sqrt{m^3\ell n\log n})$	$\delta = 1/n$
Cascade (independent)	CascadeUCB / CascadeKL-UCB	no randomisation needed
Ranked bandits	$(1 - \frac1e)$ -approximate regret $O(m\sqrt{n\ell\log\ell})$	offline NP-hard
Semi-bandit reductions	document: $\sqrt{2m\ell n(1 + \log\ell)}$ ; position: $m\sqrt{2\ell n(1 + \log\ell)}$	Theorem 30.2

Facts to keep to hand

Rankings need a click model. Treating rankings as arms is hopeless. Click models factor clicks into item attractiveness and position examination, and the generic assumptions only require that better items earn proportionally more clicks and that sorted lists are optimal.
TopRank learns an order, not a model. Shuffling within layers cancels position effects, so pairwise click differences between layer-mates have drift $\Delta_{ij}/(\alpha(i) + \alpha(j))$ . Anytime-certified comparisons build up a correct topological layering, and the examination model is never estimated.
Regret is a sum of pairwise duels. Each pair involving a top- $m$ item costs about $\frac{\alpha(i)}{\Delta_{ij}}\log n$ , worst case $\sqrt{m^3\ell n\log n}$ , and the guarantee survives click models that change over time with the same attractiveness.
The objective matters. Total clicks favour sorting by attractiveness. “At least one good result” favours diversity, makes the offline problem NP-hard, and leads to $(1 - 1/e)$ -approximate regret.

References

Lattimore & Szepesvári, Bandit Algorithms — Chapter 32
Lattimore, Kveton, Li & Szepesvári, “TopRank: A practical algorithm for online stochastic ranking” (2018)
Chuklin, Markov & de Rijke, Click Models for Web Search (2015)
Radlinski, Kleinberg & Joachims, “Learning diverse rankings with multi-armed bandits” (2008)