DCM Bandits: Multiplayer Information Asymmetric Cascading Bandits for Multiple Clicks

arXiv:2608.11873v1 [cs.LG] 12 Aug 2026

DCM Bandits: Multiplayer Information Asymmetric Cascading Bandits for Multiple Clicks Andy Wang∗

Charlton Shih∗

William Chang

Department of Computer Science University of California, Los Angeles Los Angeles, USA dxwang@ucla.edu

Department of Computer Science University of California, Los Angeles Los Angeles, USA charltonshih645@g.ucla.edu

Department of Mathematics University of California, Los Angeles Los Angeles, USA chang314@g.ucla.edu

Abstract—In this work, we extend the Dependent Click Model (DCM) Bandits to a multiplayer information-asymmetric setting, where multiple agents interact with a shared ranked list and may observe multiple clicks per session, introducing new challenges for selection strategies. We study asymmetry in (1) actions and (2) rewards, providing sublinear regret guarantees for three settings where at least one asymmetry is present. Establishing matching information-theoretic lower bounds for these settings is left as an open problem. We further show that for small termination probabilities, the termination ranking need not be known, improving on prior single-agent results. Experiments confirm that our algorithms perform well across asymmetric environments, and highlight the critical role of feedback structure—full versus first-click—in coordinating exploration and minimizing regret. Index Terms—multi-armed bandits, cascading bandits, multiplayer learning, information asymmetry, dependent click model, online learning

I. I NTRODUCTION The cascade model [1] and its dependent-click variant (DCM) [2], [3] are now standard frameworks for ranking under bandit feedback. In DCM, a user examines a ranked list, may click on multiple items, and terminates the session at any point governed by slot-specific satisfaction probabilities. The literature has produced regret-optimal single-agent algorithms [1], [3]–[6] and extensions to combinatorial actions [7], [8], user fatigue [9], exposure bias [10], and adversarial robustness [11]. Modern recommender systems, however, are rarely singleagent: industrial deployments involve multiple modules or stakeholders that jointly determine what is shown, each with partial state and partial feedback [12], [13]. This motivates a decentralized view of cascading bandits in which several players contribute distinct components of the joint ranking and observe different parts of the feedback. The multiplayer bandit literature [14]–[19] addresses coordination under such constraints, but assumes simple per-action rewards; the clickmodel literature, conversely, assumes a single decision-maker. The intersection has, to our knowledge, not been studied. a) Our Contribution.: We introduce multiplayer cascading bandits with multi-click feedback and develop algorithms for three settings of information asymmetry: • Problem A (action asymmetry). mCascadeUCB: a decentralized UCB algorithm in which players jointly ∗ These authors contributed equally.

select the top-K items by upper confidence bound and update shared statistics from observed cascade feedback. • Problem B (reward asymmetry). mCascadeUCB-Intervals-Ranking: an elimination algorithm in which separated confidence intervals implicitly signal suboptimality through action choices. A round-robin variant removes assumptions required in [3] when termination probabilities are small. • Problem C (both). mMDSEE-TopK: a phased explorethen-commit algorithm requiring no communication, extending [16], [17] to multi-slot cascade feedback. We prove sublinear regret for all three algorithms and validate them empirically. To our knowledge this is the first systematic study of decentralized multi-click cascading bandits. Sections II–IV present the model, algorithms with regret analyses, and experiments; Section V discusses related work. II. P ROBLEM S TATEMENTS A. Single-Agent Cascading Bandits We first review the classical single-agent cascading bandit model, which captures user interaction with ranked lists under the cascade hypothesis: users scan items sequentially and click the first attractive item, if any. Let E be a ground set of L items. In each round t = 1, . . . , T , the agent recommends an ordered list At = (e1 , . . . , eK ) of K distinct items from E. Each item e ∈ E has an unknown attraction probability w(e) ∈ [0, 1], representing the probability that a user clicks on the item when examined. Attraction probabilities are assumed independent and stationary. The agent receives reward 1 if any item is clicked and 0 otherwise. The objective is to learn the optimal ranking e⋆ = (e⋆1 , . . . , e⋆K ) maximizing the probability that at least one item is clicked: ! K Y ⋆ e = arg maxA∈ΠK (E) 1 − (1 − w(ek )) , (1) k=1

where ΠK (E) denotes the set of ordered K-subsets of E.

B. Multi-Agent Cascading Bandits We now consider a decentralized multi-agent extension with M players. Each player i ∈ {1, . . . , M } has a local action set E i with |E i | = L. In each round, player i selects K local items from E i . The players’ choices combine to form a joint ranking At = (a1 , . . . , aK ), where each joint item ak = (a1k , . . . , aM k ) contains one action from each player. Thus player i controls the i-th coordinate aik ∈ E i of each joint item. This setting captures two key features: (i) local autonomy, where each player controls only their own marginal choice from E i ; and (ii) global coordination, where the joint ranking emerges from the simultaneous choices of all players. Feedback remains partial as in the cascade model: agents observe the clicked joint item (if any), which reveals that earlier items were unattractive while later items remain unobserved. The reward is shared across players and equals 1 if any item is clicked. To maintain decentralization, agents may agree on a protocol before learning begins but cannot communicate during execution. The joint action space is large: there are LM joint M )! items and (L(L M −K)! possible rankings of size K. We consider three information structures: a) Problem A: Action asymmetry.: Players cannot observe other players’ actions, but all players observe the same click feedback. b) Problem B: Reward asymmetry.: Players observe each other’s actions but receive independent (i.i.d.) click feedback. c) Problem C: Action and reward asymmetry.: Players receive i.i.d. click feedback and cannot observe the actions of other players. C. Multi-Agent Cascading Bandits with Multiple Clicks We extend the model by introducing slot-dependent termination probabilities. In addition to attraction probabilities, each slot j has a termination probability vj with 1 ≤ j ≤ K. When a user clicks an item at position j, the session terminates with probability vj ; otherwise the user continues examining later items. The termination probability is independent of the item and the round. As before, feedback is partial: items before the click are observed to be unattractive, the clicked item is attractive, and later items remain unobserved. Under this model the optimal ranking becomes   K Y e⋆ = arg maxA∈ΠK (E) 1 − (1 − vj w(ej )) . (2)

Algorithm 1 mCascadeUCB-A Require: M players with action sets E i of size L, horizon T , list size K 1: E ← E 1 × · · · × E M 2: Initialize w(e) b ← 0, n(e) ← 0 for all e ∈ E 3: for t = 1 to T do 4: Compute UCBt (e) for all e ∈ E 5: Select top-K items (e1 , . . . , eK ) by UCBt 6: Players extract their components and observe click Ct 7: for j = 1 to min{Ct , K} do 8: Update w b and n for ej 9: end for 10: end for

III. M AIN R ESULTS A. Problem A: Information Asymmetry in Actions We now consider Problem A, where players observe identical rewards but cannot observe one another’s actions. The main challenge is that players must infer which joint item was played in order to correctly update empirical statistics. Otherwise, miscoordination may occur, where different players update different joint items despite observing the same reward. Because all players observe identical clicks, coordination can be achieved through a predetermined exploration phase. Specifically, during the first Kmax = K1 · · · KM rounds players follow a fixed joint schedule that explores all joint items. This ensures that all players obtain identical statistics for every joint item. After this phase, players compute UCB indices for each joint item: ( ∞ if nt−1 (e) = 0, UCBt (e) = (3) w bnt−1 (e) (e) + cnt−1 (e) otherwise. Since all players share identical estimates, they select the same joint item at each round by choosing the K items with the largest UCB values. Ties are broken using a fixed lexicographic order on RM from [16]. Definition 1. We say (x1 , . . . , xM ) < (y1 , . . . , yM ) if there exists n such that xi = yi for all i < n and xn < yn . Coordination then follows by induction: if players select the same actions up to time t − 1, identical UCB statistics imply they select the same joint action at time t. Unlike the classical cascade model, we allow multiple clicks and update all observed prefixes up to min(Ct , K). Because all players maintain identical statistics, no communication is required to maintain coordination. The procedure is given in Algorithm 1.

j=1

The termination probabilities allow multiple clicks within a session, increasing the amount of feedback per round while also introducing additional uncertainty for learning and coordination.

Theorem 2. If each player uses mCascadeUCB-A under Problem A, the expected T -step regret satisfies M

RT ≤

L X e=K+1

12 π2 M log T + L . ∆e,K 3

This matches the regret order of the single-agent cascading UCB algorithm. The exponential dependence on LM is unavoidable for the algorithm as stated: combinatorial cascading bandits over factored action sets [7], [8] obtain polynomial regret only when reward is a known function (e.g. disjunctive) of per-item attractions, whereas we make no parametric assumption tying w(e) to per-player marginals wi (ai )— coordinates may interact arbitrarily, as with complementary product bundles. Combining a known link function with our coordination mechanism to obtain polynomial-in-L regret is a natural extension that we leave to future work. B. Problem B: Information Asymmetry in Rewards We now consider Problem B, where players observe the same actions but receive independent (i.i.d.) click realizations. As a result, players maintain different reward estimates and UCB indices for the same joint item, which may lead to coordination failures. The cascading feedback structure further complicates learning since items receive different numbers of observations across players. To address this, we use confidence intervals with both upper and lower bounds. For each joint item e, players compute UCBt (e) = w bnt−1 (e) + ct−1,nt−1 (e) , LCBt (e) = w bnt−1 (e) − ct−1,nt−1 (e) . Standard concentration inequalities (Lemma 9) imply that the true click probability lies in (LCBt (e), UCBt (e)) with high probability. If UCBt (e) < LCBt (e′ ), the algorithm can safely eliminate e. a) mCascadeUCB-Intervals-Ranking.: The algorithm proceeds in K phases, identifying one item per phase. At phase r, the candidate set is D = E \ R, where R contains items selected in earlier phases. Players cycle through items in D using a shared ordering and repeatedly place the current candidate in the first slot. Because players observe independent clicks, their confidence intervals may differ. Coordination is achieved through implicit signaling: if a player detects that UCBt (e) < LCBt (e′ ), they sabotage e by deviating from the scheduled marginal action. This observable deviation signals that e should be removed from D. As intervals shrink, inferior items are eliminated until a single item remains, which is appended to R. Repeating this process for K phases identifies the full ranking. Example 3. Let K = 2 with two players. A joint item (i, j) denotes player 1 choosing i and player 2 choosing j. Suppose the candidate cycle is (1, 1) → (1, 2) → (2, 1) → (1, 1) → · · · . The corresponding placements are t = 1: ((1, 1), (1, 2)), t = 2: ((1, 2), (2, 1)), t = 3: ((2, 1), (1, 1)), . . . If a player detects UCBt ((1, 2)) < LCBt ((1, 1)), they sabotage round t = 2 by playing ((1, 1), (2, 1)) instead of the

Algorithm 2 mCascadeUCB-Intervals-Ranking-multiple Require: M players, item set E, horizon T , target size K 1: R ← ∅; initialize means and counts 2: for r = 1 to K − |R| do 3: D ← E \ R; set cycle pointer c ← 0 4: while |D| > 1 do 5: Place items D[c], D[c+1], . . . , D[c+K−1] (mod |D|) in slots 1, . . . , K 6: Compute UCBt , LCBt for e ∈ D 7: if ∃ e ∈ D with UCBt (e) < maxe′ ∈D LCBt (e′ ) then 8: Sabotage scheduled placement by deviating; signal elimination of e 9: end if 10: Observe cascade; for each slot k ≤ min(Ct , K) update estimate of the item placed there 11: Remove dominated items from D; advance c ← c+1 12: end while 13: Append remaining item to R 14: end for 15: Recommend R ordered by empirical means

scheduled ((1, 2), (2, 1)). Other players detect the deviation and remove (1, 2) from the cycle, leaving (1, 1) → (2, 1) → (1, 1) → · · · . This procedure achieves gap-dependent regret O(log T ). Note that obtaining sublinear regret requires recovering not only the top-K set but also their correct ordering. Sabotage signaling is unambiguous because the round-robin schedule is deterministic and common knowledge: every player can compute the scheduled joint action from (t, R, D) alone, so any deviation is a signal rather than noise. The only remaining failure mode—a player eliminating an item whose true attraction is higher than the eliminator’s—is controlled by the confidence radius of Lemma 9 and contributes only an O(LM /T ) additive term to the regret, handled in the proof of Theorem 4. Theorem 4. Let e⋆1 , . . . , e⋆K denote the top-K joint items (in decreasing order of attraction probability), and for each r ∈ {1, . . . , K} let µ⋆r = w(e⋆r ) and ∆e⋆r ,e = µ⋆r − w(e) for any suboptimal e in the r-th elimination phase. The regret of mCascadeUCB-Intervals-Ranking under Problem B satisfies √ K X X (4 + 4 2)2 log T RT ≤ . ∆e2⋆r , e ⋆ r=1 e : w(e)<µr

b) Round-Robin Ranking with Multiple Placements.: The previous algorithm only uses feedback from the first slot. When termination probabilities are small, additional slots can provide useful observations. The algorithm mCascadeUCB-Intervals-Ranking-multiple (Algorithm 2) exploits this by cycling through candidates and placing K items each round.

If the upper confidence bound of an item falls below another item’s lower confidence bound, a player sabotages the scheduled placement, signaling elimination. An item e placed in slot k is observed if the cascade reaches that slot. The observation probability for slot k is pk (e) =

k−1 Yh

i (1 − w(ej )) + w(ej )vj .

j=1

Define the minimum slot-survival probability pmin = min

min

1≤k≤K (e1 ,...,ek−1 )

k−1 Yh

i (1 − w(ej )) + w(ej )vj .

j=1

Lemma 5. If a joint item e is placed in slot j > 1 a total of M times, at least 1 − T1 it receives at   then q with probability T M pmin observations. In particular, the least 1 − 2plog 2 min M bound is non-vacuous whenever log T M ≥ , 2 p2min which is the regime in which the multi-placement strategy yields strictly more information than first-slot-only exploration. Theorem 6. The regret of mCascadeUCB-Intervals-Ranking-multiple satisfies √ 2 !  X B + B 2 + 4A · Re M RT = O L , 2A e q where A = 1 + (K − 1)pmin , B = (K − 1) log2 T , and T Re = 8 log ∆2 + 1. e

When pmin ≈ 1 (i.e., termination probabilities are small), the bound approaches the classical cascading-bandit regret O(log T /∆2 ) [1], [3]. C. Problem C: Information Asymmetry in Both We now consider Problem C, which combines the difficulties of Problems A and B: players cannot observe one another’s actions and they receive asymmetric (i.i.d.) click feedback. As a result, mCascadeUCB-Intervals from Problem B cannot coordinate eliminations without action observability, and the approach for Problem A fails because players no longer share identical reward statistics. To handle both asymmetries, we adapt the MDSEE framework [16] to the multi-agent cascade setting. Our goal is to identify the top-K joint items using a phased explore-thencommit strategy. The resulting algorithm, mMDSEE-TopK, alternates between exploration and exploitation phases according to a schedule F (λ) (default F (λ) = λ), where λ is the phase index. In the exploration phase, the algorithm spends L · F (λ) rounds uniformly sampling items via a fixed round-robin schedule: at each round t it recommends a K-list so that each item appears in each slot sufficiently often. The user returns a

Algorithm 3 mMDSEE-TopK Require: Item set E of size L, target size K, horizon T , schedule F (λ) = λ Ensure: Top-K items identification 1: Initialize ŵ0 (e) ← 0, n0 (e) ← 0 for all e ∈ E 2: λ ← 1; t←1 3: while t < T do 4: Exploration: For F (λ) · L rounds, cycle through items with a sliding window of size K 5: for j = 1 to L do 6: Recommend [ ej , e(j+1) mod L , . . . , e(j+K−1) mod L ] 7: Observe click Ct and update estimates 8: t←t+1 9: end for 10: Exploitation: Let Rt be the top-K items by ŵt (e) 11: Texploit ← 2r − t (with 2r > t) 12: for j = 1 to Texploit do 13: Recommend Rt , observe feedback 14: t←t+1 15: end for 16: λ←λ+1 17: end while

click position Ct ∈ {1, . . . , K, ∞}. For each observed position k ≤ Ct , the algorithm updates nt (e) and w bt (e) for the item in slot akt . After exploration, the exploitation phase forms a ranking Rt of the K items with largest empirical means w bt (e) and repeatedly recommends Rt until the next power-of-two boundary 2τ (smallest τ with 2τ > t). The phase index λ is then incremented. We only update estimates using exploration rounds: under asymmetric rewards and unobservable joint actions, feedback during exploitation cannot be reliably attributed to specific joint items. The algorithm is given in Algorithm 3. a) Regret with First-Slot Feedback.: We first analyze the special case where players observe only whether the first slot terminates. Theorem 7 (First-Slot Feedback). Consider Algorithm 3. Suppose that ε < 12 min1≤i≤K mine ∆i+1,i , and let F (λ) = λ. Then the cumulative regret after T rounds satisfies  RT = O LM log log T log T     √ M LM π 1 2 1 + √ e 8cε 1 + erf √ . 2c ε 8c ε Here, ∆i+1,i denotes the gap between the (i + 1)-th and i-th best joint items. Choosing ε = 21 min1≤i≤K ∆i+1,i is sufficient to separate optimal from suboptimal items and to recover the correct ordering within the top-K. The first term reflects exploration across phases; since phase lengths grow exponentially, the effective sample size increases rapidly and error probabilities decay quickly. The second term accounts for mis-commitment: the probability that players

The factor α captures the benefit of multi-slot feedback: observing more slots increases the effective number of observations per round by α = 1 + (K − 1)pmin , tightening concentration and reducing regret. When pmin = 0, no additional slots are observed and we recover Theorem 7 with c = 1. As pmin → 1, we obtain c ≈ K, corresponding to nearly K effective observations per round.

cumulative regret

Theorem 8 (Multi-Slot Feedback). Under the same setting and notation as Theorem 7, let c = 1 + (K − 1)(1 − log T )p , with α = 1 + (K − 1)pmin . If F (λ) = λ, 2p2min F (T ) min then  RT = O log T log log T     √ 1 M LM π 1 2 . + √ √ e 8cαε 1 + erf √ 2c ε α 8cα ε

Synthetic, low termination (v [0.15, 0.25]), L = 3, K = 2, M = 3 4000 3000 2000 1000

0

20000 30000 round t

40000

50000

Synthetic, high termination (v [0.85, 0.95]), L = 3, K = 2, M = 3 mCascadeUCB-A mMDSEE-TopK (full) mMDSEE-TopK (first) Independent per-player UCB

3500 3000 2500 2000 1500 1000 500

We evaluate our algorithms under the DCM cascade simulator: at slot k with item e, the user clicks with probability w(e); if a click occurs, the session terminates with probability vk . The terminating click position Ct (or ∞) is the observed feedback.   t ̸= ∞}  regret QReward is I{C Q and instantaneous is 1 − k (1 − vk wk⋆ ) − 1 − k (1 − vk w(etk )) , where ⋆ w1⋆ , . . . , wK are the top-K attractions paired with the largest vk values (optimal by the rearrangement inequality). a) Baselines.: To verify that joint-arm UCB is not artificially inflating measured regret, we compare against an independent per-player UCB baseline in which each player runs a single-agent UCB over its local item set E i , ignoring joint structure: player i at slot k updates the marginal estimate ŵi (ai ) from the joint feedback. We do not include a separate centralized oracle because under Problem A the decentralized mCascadeUCB-A already maintains identical statistics to a centralized UCB on joint arms; mCascadeUCB-A therefore serves simultaneously as our algorithm and as the centralized benchmark. b) Setup.: Attraction probabilities are drawn w(e) ∼ Uniform[0.1, 0.9] and fixed across seeds. We average over 5 random seeds; shaded regions show ±2 standard deviations. The instance is L = 3, K = 2, M = 3 (27 joint arms) with horizon T = 5 × 104 . We sweep two termination regimes: low (v ∈ [0.15, 0.25]) and high (v ∈ [0.85, 0.95]).

0

Figures 1 and 2 report cumulative regret.

10000

Fig. 1. Cumulative regret under low termination probability v ∈ [0.15, 0.25]. Coordinated methods cluster tightly; mMDSEE-TopK with full feedback benefits from observations in deeper slots.

IV. E XPERIMENTS

A. Cumulative Regret

mCascadeUCB-A mMDSEE-TopK (full) mMDSEE-TopK (first) Independent per-player UCB

0

cumulative regret

commit to an incorrect joint item due to estimation error. We use F (λ) = λ to obtain sharper asymptotic bounds than [16]. b) Regret with Multiple-Slot Feedback.: We next consider the case where players use feedback from all observed slots up to K. The algorithm is unchanged; only the exploration updates incorporate additional observed joint items, improving estimation without altering coordination.

0

10000

20000 30000 round t

40000

50000

Fig. 2. Cumulative regret under high termination probability v ∈ [0.85, 0.95]. mCascadeUCB-A is best; first-slot mMDSEE-TopK outperforms full-slot here because deeper-slot observations are rare. Independent per-player UCB plateaus at ∼ 6× the regret of coordinated methods.

a) High termination (v ∈ [0.85, 0.95]).: When users frequently terminate after the first click (Fig. 2), most click feedback comes from slot 1. mCascadeUCB-A is the most data-efficient (≈ 580 at T =5 × 104 ). The first-slot variant of mMDSEE-TopK (≈ 810) actually outperforms its fullslot counterpart (≈ 1300): when later-slot observations are rare and noisy, restricting updates to slot 1 reduces variance. Independent per-player UCB plateaus around 3,500, an order of magnitude worse. b) Low termination (v ∈ [0.15, 0.25]).: When cascades typically reach both slots (Fig. 1), full-feedback algorithms exploit every observation. mMDSEE-TopK with full feedback edges out its first-slot counterpart, consistent with the α = 1 + (K − 1)pmin scaling predicted by Theorem 8; the gap is modest at K = 2 but is expected to widen as K grows. Independent per-player UCB again pays a multiplicative penalty for ignoring joint structure. B. Discussion Three insights emerge:

Multi-slot feedback matters when pmin is large. The α = 1 + (K − 1)pmin factor predicted by Theorem 8 matches the observed gap between full- and first-slot variants at low termination. First-slot feedback can win at high termination. When most clicks terminate at slot 1, full-slot updates inject noise rather than information. This is consistent with our analysis: the (K− 1)pmin improvement collapses to zero as pmin → 0. Coordination beats independence even with asymmetric rewards. Independent UCB consistently lags coordinated methods across both termination regimes, showing that the multiplayer asymmetric setting is genuinely harder than M parallel single-agent problems and that joint-arm coordination—even without communication, as in mMDSEE-TopK—provides real value. a) Computational cost.: All algorithms have per-round cost dominated by the top-K selection over LM joint arms, i.e. O(LM log LM ). mMDSEE-TopK requires no inter-player communication; mCascadeUCB-Intervals-Ranking requires action observability but no protocol messages. A single T =5 × 104 run completes in a few seconds on a standard laptop. V. R ELATED W ORK a) Click-model bandits.: The cascade model [1] and its many extensions—combinatorial actions [7], contextual settings [5], Thompson sampling [6], scalability improvements [4], and clustering-based methods [20]—form the algorithmic foundation for learning to rank under bandit feedback. The dependent click model [2], [3] extends single-click cascades to multi-click sessions and is the closest single-agent precursor to our work; recent variants incorporate fatigue [9], exposure bias [10], RL-style ranking [21], and adversarial robustness [11]. All of these assume a single decision-maker. b) Decentralized and multiplayer bandits.: A parallel line of work studies multiple agents learning simultaneously under communication or observation constraints [14], [15], [22]–[26]. Most relevant here are decentralized learning with information asymmetry and no communication [16]–[19] and federated/combinatorial multi-agent formulations [8], which provide the techniques we extend to multi-click feedback. Real-world recommender deployments [12], [13], [27]–[29] and bandit models with structured feedback [30], [31] further motivate the decentralized cascading setting. To our knowledge no prior work has combined multi-click cascade feedback with multi-agent decentralized learning under information asymmetry. VI. C ONCLUSION We study decentralized multi-click cascading bandits with private observations and information asymmetry. Building on the Dependent Click Model and multiplayer bandit theory, we design algorithms that handle action asymmetry, reward asymmetry, and their combination. Our methods extend UCBbased approaches and MDSEE-style exploration to the multiagent cascade setting, achieving sublinear regret under both first-slot and multi-slot feedback.

Our theoretical analysis captures the role of multiple clicks and slot termination probabilities. Empirical results confirm that leveraging multi-slot feedback significantly improves performance when termination probabilities are small, and that coordinated decentralized learning consistently outperforms independent per-player baselines. a) Open problems.: Two questions remain open. First, we prove no matching information-theoretic lower bound for any of Problems A–C; establishing such bounds (or identifying a regime where our upper bounds are tight) is the natural next step. Second, the worst-case LM dependence reflects the absence of factored structure in our model; identifying mild parametric assumptions (e.g. generalized linear link functions over player features) under which polynomial-in-L regret is attainable would substantially improve scalability. ACKNOWLEDGMENT The authors would like to thank the reviewers for their valuable feedback. R EFERENCES [1] B. Kveton, C. Szepesvari, Z. Wen, and A. Ashkan, “Cascading bandits: Learning to rank in the cascade model,” in Proceedings of the 32nd International Conference on Machine Learning, vol. 37 of Proceedings of Machine Learning Research, pp. 767–776, PMLR, 2015. [2] F. Guo, C. Liu, and Y. M. Wang, “Efficient multiple-click models in web search,” in Proceedings of the Second ACM International Conference on Web Search and Data Mining, pp. 124–131, 2009. [3] S. Katariya, B. Kveton, C. Szepesvári, and Z. Wen, “Dcm bandits: Learning to rank with multiple clicks,” in Proceedings of the 33rd International Conference on Machine Learning (ICML), pp. 1215–1224, PMLR, 2016. [4] S. Zong, H. Ni, K. Sung, N. R. Ke, Z. Wen, and B. Kveton, “Cascading bandits for large-scale recommendation problems,” 2016. [5] S. Li, B. Wang, S. Zhang, and W. Chen, “Contextual combinatorial cascading bandits,” in Proceedings of the 33rd International Conference on Machine Learning (ICML), pp. 1245–1253, PMLR, 2016. [6] Z. Zhong, W. C. Cheung, and V. Y. F. Tan, “Thompson sampling algorithms for cascading bandits,” Journal of Machine Learning Research, vol. 22, no. 218, pp. 1–66, 2021. [7] B. Kveton, Z. Wen, A. Ashkan, and C. Szepesvari, “Combinatorial cascading bandits,” Advances in Neural Information Processing Systems, vol. 28, 2015. [8] F. Fourati, M.-S. Alouini, and V. Aggarwal, “Federated combinatorial multi-agent multi-armed bandits,” 2024. [9] J. Cao, W. Sun, Z.-J. M. Shen, and M. Ettl, “Fatigue-aware bandits for dependent click models,” in Proceedings of the AAAI Conference on Artificial Intelligence, vol. 34, pp. 3341–3348, 2020. [10] M. Mansoury, B. Mobasher, and H. van Hoof, “Mitigating exposure bias in online learning to rank recommendation: A novel reward model for cascading bandits,” in Proceedings of the 33rd ACM International Conference on Information and Knowledge Management, pp. 1638– 1648, 2024. [11] J. Xie, C. Chen, Z. Wang, and S. Li, “Cascading bandits robust to adversarial corruptions,” 2025. [12] K. Zou and A. Sun, “A survey of real-world recommender systems: Challenges, constraints, and industrial perspectives,” 2025. [13] Y. Wang, L. Tao, and X. X. Zhang, “Recommending for a multisided marketplace: A multi-objective hierarchical approach,” Marketing Science, vol. 44, no. 1, pp. 1–29, 2025. [14] E. Boursier and V. Perchet, “A survey on multiplayer bandits,” Journal of Machine Learning Research, vol. 23, no. 1, pp. 1–47, 2022. [15] S. Branzei and Y. Peres, “Multiplayer bandit learning, from competition to cooperation,” in Proceedings of the 34th Conference on Learning Theory, vol. 134 of PMLR, pp. 679–723, 2021. [16] W. Chang, M. Jafarnia-Jahromi, and R. Jain, “Online learning for cooperative multi-player multi-armed bandits,” in 2022 IEEE 61st Conference on Decision and Control (CDC), pp. 7248–7253, IEEE, 2022.

[17] W. Chang and Y. Lu, “Optimal cooperative multiplayer learning bandits with noisy rewards and no communication,” arXiv preprint arXiv:2311.06210, 2023. [18] W. Chang and Y. Lu, “Multiplayer information asymmetric contextual bandits,” 2025. [19] W. Chang and A. Karthik, “Multiplayer information asymmetric bandits in metric spaces,” 2025. [20] S. Li and S. Zhang, “Online clustering of contextual cascading bandits,” in Proceedings of the 32nd AAAI Conference on Artificial Intelligence, 2018. [21] Y. Du, R. Srikant, and W. Chen, “Cascading reinforcement learning,” in Proceedings of the 12th International Conference on Learning Representations (ICLR), 2024. [22] B. Awerbuch and R. D. Kleinberg, “Competitive collaborative learning,” in Proceedings of the 18th Annual Conference on Learning Theory (COLT), vol. 3559 of Lecture Notes in Computer Science, pp. 233–248, Springer, 2005. [23] P. Landgren, V. Srivastava, and N. E. Leonard, “Distributed cooperative decision-making in multiarmed bandits: Frequentist and bayesian algorithms,” in Proceedings of the 55th IEEE Conference on Decision and Control (CDC), pp. 167–172, IEEE, 2016. [24] N. Cesa-Bianchi, C. Gentile, Y. Mansour, and A. Minora, “Delay and cooperation in nonstochastic bandits,” in Proceedings of the 29th Annual Conference on Learning Theory, vol. 49 of Proceedings of Machine Learning Research, pp. 605–622, PMLR, 2016. [25] P. Alatur, K. Y. Levy, and A. Krause, “Multi-player bandits: The adversarial case,” Journal of Machine Learning Research, vol. 21, pp. 1– 23, 2020. [26] G. Lugosi and A. Mehrabian, “Multiplayer bandits without observing collision information,” Mathematics of Operations Research, 2021. [27] B. Loepp, “Multi-list interfaces for recommender systems: survey and future directions,” Frontiers in big Data, vol. 6, p. 1239705, 2023. [28] A. Fletcher, P. L. Ormosi, and R. Savani, “Recommender systems and supplier competition on platforms,” Journal of Competition Law & Economics, vol. 19, no. 3, pp. 397–426, 2023. [29] R. Demsyn-Jones, “Measurement and applications of position bias in a marketplace search engine,” 2022. [30] N. Alon, N. Cesa-Bianchi, C. Gentile, S. Mannor, Y. Mansour, and O. Shamir, “Nonstochastic multi-armed bandits with graph-structured feedback,” Theoretical Computer Science, 2014. [31] J. Mo and H. Xie, “A multi-player mab approach for distributed selection problems,” in Advances in Knowledge Discovery and Data Mining (PAKDD), Springer, 2023.

Therefore, with probability at least 1 − T1 , s #{observations of e in slot k} >

1−

log T 2p2min M

! M pmin .

Proof. A necessary condition for item e to still be in the candidate set is that UCB(e) > LCB(e⋆ ). This implies s s 4 log T 4 log T > µ̂e⋆ − µ̂e + , (4) ne (t) ne⋆ (t) s s 4 log T 4 log T ∗ =⇒ µe + 2 >µ −2 (good event), ne (t) ne (t) (5) s s 4 log T 4 log T > ∆e⋆ ,e − 2 =⇒ 2 . (6) ne (t) ne⋆ (t) Since items in the candidate set are pulled in a round-robin fashion, we have |ne (t) − ne⋆ (t)| ≤ 1. This implies that when ne (t) ≥ 2, we also have ne⋆ (t) ≥ ne (t)/2. Plugging this in: s s 4 log T 4 log T > ∆e⋆ ,e − 2 , (7) 2 ne (t) ne (t)/2 s √  log T  4 + 4 2 > ∆e⋆ ,e , (8) ne (t) √ (4 + 4 2)2 log T =⇒ ne (t) < . (9) ∆2e⋆ ,e Now suppose the optimal joint items are e⋆1 , . . . , e⋆K , where ⋆ er is the item selected in the r-th elimination phase. The total

number of pulls across all suboptimal items is bounded as A PPENDIX √ K X X (4 + 4 2)2 log T Lemma 9. Assume that Xi − µ are independent, στ< . subgaussian random variables. Then for any ε ≥ 0, ∆e2⋆r , e r=1 e : w(e)<µ⋆     r nε2 nε2 P(µ̂ ≥ µ+ε) ≤ exp − 2 , P(µ̂ ≤ µ−ε) ≤ exp − 2 ,Under the good event, the regret from t = τ to T is zero, 2σ 2σ since only top items are pulled from that point onward. Pn 1 where µ̂ = n t=1 Xt . Proof. By the reasoning similar to Theorem 4, item e needs Proof. Suppose item e was placed in slot k for the i-th time, only N 8 log T + 1 observations before it is eliminated elim = ∆2 K and let pki be the probability that this item was observed. Let (the additional +1 accounts for the sabotage round). Since the Xi be the Bernoulli random variable for the clicks for the i-th first slot always gets observed, the total observations satisfy placement. Then Xi −pki is a sequence of mean-0 independent 1 K X 2 -subgaussian random variables, so by Lemma 9 we have P k Ytotal = M + #{obs in slot r} P 
2 i Xi i pi r=2 Pr < − ϵ ≤ exp −2M ϵ . q   M M log T > M + (K −1) 1 − M pmin . 2 P k 2pmin M α p Setting ϵ = Mi i for some small α > 0, we conclude that We require Yq P k P total ≥ Nelim . Let A := 1 + (K − 1)pmin ,
log T 2 2 i pi i Xi Pr < (1 − α) ≤ exp −2α pmin M . B := (K − 1) log2 T , and R := 8 ∆ + 1. Then AM − 2 K M M √ √ B M − R ≥ 0. Setting x := M ≥ 0 yields the quadratic Setting the right-hand side to be upper bounded by 1/T : Ax2 − Bx − R ≥ 0, solved by s √
1 log T B + B 2 + 4AR exp −2α2 p2min M = =⇒ α = . 2 x ≥ . T 2pmin M 2A

Squaring gives M ≥



2 √ B+ B 2 +4AR . 2A

PK The instantaneous regret satisfies Rt ≤P k=1 [w(e∗k ) − w(etk )], so the total regret is RT ≤ e suboptimal ∆K · E[#placements of e], yielding the stated bound. Proof. Split the total regret into exploration and commitment phases: RT = RT,E + RT,C . Exploration term. Let νt (e) be the number of times item e has been placed first up to time t. Since exploration occurs at t = 20 , 21 , . . . , 2⌊log2 T ⌋ , we have νt (e) ≤ F (⌊log2 T ⌋)⌈log2 T ⌉. Each pull incurs at most L regret, so RT,E ≤ LM F (⌊log2 T ⌋)⌈log2 T ⌉. Commitment term. Let ε < 12 min1≤i≤K mine ∆i+1,i . Define the good event for playerT i at time t: Git (e) = {|w bni t (e) (e) − w(e)| < ε}. If Gt = i Git (e) holds, all players choose the optimal ranking, so Rt = 0. Hence RT,C =

T X

[E[Rt | Gt ]P (Gt ) + E[Rt | Gct ]P (Gct )]

t=1

≤

T X

P (Gct ).

t=1

By De Morgan and a union bound, RT,C ≤ PT P M t=1 e∈E P (|w bnt (e) (e) − w(e)| ≥ ε). Hoeffding’s inequality gives P (|w bnt (e) (e) − w(e)| ≥ ε) ≤ 2 exp(−2nt (e)ε2 ). Since F (λ) = λ, the total number of explorations up to phase λ = log2 t is nt (e) = 1 + 2 + · · · + F (λ) = Ω((log2 t)2 /2). Therefore F0 (t) := nt (e)/ ln t ≥ c ln t for 2 a constant c > 0. The exponent becomes t−2F0 (t)ε ≤ 2 t−2cε ln t = exp(−2cε2 (ln t)2 ). the comparison integral I(c, ε) = R ∞Define −2cε2 (ln x)2 e dx. Substituting u = ln x and completing the 1 square: Z ∞ 1 2 2 2 8cε e−2cε v dv I(c, ε) = e −

1 2

4cε    √ 1 π 1 = √ e 8cε2 1 + erf √ . 2 2c ε 8c ε the summand is positive and decreasing, PSince ∞ 2 exp(−2cε (ln t)2 ) ≤ 1 + I(c, ε), hence t=1   √ M LM π 1 exp RT,C ≲ √ 8cε2  2c ε   1 × 1 + erf √ . 8c ε This completes the proof.

Proof. We follow the proof of Theorem 7 with minor modifications. Under multiple-slot feedback, each time e is placed we obtain additional observations from deeper slots. The effective observation mass is s ! log T ñt (e) = nt (e) + (K − 1) 1 − nt (e) pmin . 2p2min nt (e)

Concentration bound. Hoeffding’s inequality applied to the empirical estimate gives Pr(|w bñt (e) (e) − w(e)| ≥ ε) ≤ 2 exp(−2ñt (e)ε2 ). Lower bound on effective observations. Since nt (e) ≥ F0 (t) log2 t, dropping lower-order terms, we simplify the dominant scaling as ñt (e) = Θ(F0 (t) log t·[1+(K −1)pmin ]). Regret bound. The commitment regret becomes RT,C ≤ 2M |E|

T X

 exp − 2F0 (t) log(t)

t=1

 × (1 + (K −1)pmin )ε2 . Using α = 1 + (K − 1)pmin , this rewrites to RT,C ≤ P∞ 2 2M LM t=1 t−2αF0 (t)ε . Multi-slot feedback increases the effective observation count by α, yielding   √ 1 M LM π RT,C ≲ √ √ exp 8cαε2 2c ε α    1 × 1 + erf √ . 8cα ε

Related documents

• Designing for the Next Click: Bandits for Real-Time Page Layout#798473
• Designing for the Next Click: Bandits for Real-Time Page Layout#797060
• Degree-Parameterized Analysis of Sampling-Based Online Matching#1083917
• Diversified Multinomial Logit Contextual Bandits#363253
• Offline Policy Evaluation as a decision support tool for designing Adaptive Experiments#1104472