Optimal Regret Analysis of Thompson Sampling in Stochastic Multi-armed Bandit Problem with Multiple Plays

1.1. Multiple-play MAB problem

• Multiple-play bandits model settings such as advertisement placement and cognitive-radio channel selection, where several options can be selected at once.The paper gives advertisements and channels as examples of arms, with clicks and communication permission as rewards, respectively.Source: §1.1 · p. 2
• The open question is whether a computationally efficient multiple-play algorithm can match the optimal regret lower bound; existing logarithmic-bound algorithms do not match its constant factors.Anantharam et al. (1987) derived the lower bound, but their algorithm requires statistics that are difficult to compute.Source: §1.1 · p. 2
• MP-MAB regret depends on which arms are selected together, so an optimal bound on suboptimal-arm draws alone need not guarantee optimal regret.This differs from the single-play setting, where the paper contrasts the draw-count bound with multiple-play regret.Source: §1.1 · p. 2
• MP-TS extends Thompson sampling to multiple-play bandits and achieves an optimal regret bound for binary rewards, matching the lower bound of Anantharam et al. (1987).The paper identifies MP-TS as the first computationally efficient algorithm for MP-MAB with that optimal regret bound.Source: §1.1 · p. 2
• The paper also reports that IMP-TS improves MP-TS empirically without increasing computational complexity.The modification is motivated by analyses of the multiple-play regret structure.Source: §1.1 · p. 2

2. Problem Setup

• Each round, the forecaster selects L of K arms and receives independent, identically distributed Bernoulli rewards from the selected arms.Arm i has reward distribution Bernoulli(µi); Ni(t) counts its draws before round t.Source: §2 · p. 2
• The setup assumes distinct arm means and defines the top L arms as optimal and all remaining arms as suboptimal.The paper states that equal-mean arms are discussed in Appendix A.1.Source: §2 · p. 3
• Algorithm performance is measured by expected regret, the expected loss in cumulative reward relative to the optimal policy.The forecaster seeks to maximize the sum of rewards over the selected arms.Source: §2 · p. 3

3.2. Extension to MP-MAB problem

• For MP-MAB, Anantharam et al. (1987) provide a lower bound on suboptimal-arm draws and the corresponding regret lower bound for strongly consistent algorithms.The draw-count bound is expressed using the divergence between arm i and the Lth-best arm.Source: §3.2 · pp. 3–4
• In multiple-play bandits, regret depends on the combinatorial structure of arm draws, so equal counts of suboptimal draws can yield different regret.Figure 1 illustrates two games with the same number of suboptimal draws but different regret.Source: §3.2 · p. 3, Figure 1 · p. 3

3.3. Necessary condition for an optimal algorithm

• Unlike in single-play bandits, achieving the asymptotic lower bound on suboptimal-arm draws does not necessarily achieve the asymptotic multiple-play regret bound.The section attributes this gap to regret being related to the number of draws by an inequality rather than an equality.Source: §3.3 · p. 4
• An optimal-regret scenario requires arm L to be the optimal arm displaced when a suboptimal arm is selected, which requires at most one suboptimal draw in almost all rounds.Selecting two suboptimal arms pushes out at least one of the top L−1 arms.Source: §3.3 · p. 4
• The section introduces MP-TS as the next proposed approach to suppress simultaneous draws of multiple suboptimal arms.The MP-TS algorithm is listed as Algorithm 1, which selects the top L posterior samples.Source: §3.3 · p. 4, §3.2 · p. 4

4. Multiple-play Thompson Sampling Algorithm

• MP-TS selects the top L arms ranked by posterior samples, extending single-play Thompson sampling’s top-one selection.The algorithm uses a uniform prior on each arm.Source: §4 · p. 4
• The paper’s intuition is that if each suboptimal arm is selected with probability O(1/t), independent selection makes two simultaneous suboptimal draws occur with probability O(1/t^2).The paper states that the resulting total number of simultaneous draws is O(1).Source: §4 · p. 5
• Independent posterior samples across arms give MP-TS a way to suppress simultaneous draws of multiple suboptimal arms.The paper contrasts this randomized independence with deterministic UCB scores, whose suboptimal-arm scores may behave similarly given past rewards.Source: §4 · p. 5

5. Optimal Regret Bound

• Theorem 1 upper-bounds MP-TS regret by a leading expression plus terms Ca and Cb.The supplied theorem passages identify the additional terms but do not show the full leading expression.Source: §5 · p. 5
• Cb grows as O(log log T) = o(log T) when ϵ2 is chosen properly, while Ca is independent of T.For fixed arm means, Ca is O(ϵ1^-2).Source: §5 · p. 5
• MP-TS achieves the asymptotic bound in (7); Anantharam et al. (1987) derived a regret lower bound in a stronger form than (7) for strongly consistent algorithms.Source: §5 · p. 5
• MP-TS is also asymptotically optimal in the high-probability sense.The paper contrasts this with its expected-regret result, which it says is stronger than the high-probability bound by Gopalan et al. (2014).Source: §5 · p. 5

6.1. Additional notation

• The notation uses the L-th largest posterior sample as the minimum among selected arms and the (L − 1)-th largest after excluding two arms.The accompanying events track arm selection, insufficient exploration, and underestimation of optimal arms.Source: §6.1 · p. 5

6.2. Proof of Theorem 1

• The proof decomposes each suboptimal arm's regret and bounds the resulting terms to establish Theorem 1.For deviation bounds on Bernoulli means and Beta posteriors, the analysis borrows techniques from Agrawal & Goyal (2013b) and Honda & Takemura (2014).Source: §6.2 · pp. 5–6
• The proof decomposes regret for a suboptimal arm into four event-based terms, with term (C) covering simultaneous draws of suboptimal arms.The paper identifies term (C) as unique to the multiple-play problem and uses independence of posterior samples in its analysis.Source: §6.2 · p. 6
• Terms (A), (B), and (D) are O(1/δ²), while choosing ϵ2 = O((log log T)/log T) gives E[(C)] = O(log log T).The analysis then evaluates the sufficient number of explorations to complete the regret bound.Source: §6.2 · p. 7

E [(A) + (B) + (C) + (D)] + N suf

• Cb includes an O(log log T) contribution, and setting δ = ϵ1/max_i c_i = Θ(ϵ1) for ϵ1 < 1/2 completes the proof.The stated choice uses c_iδ ≤ 1/2.Source: E [(A) + (B) + (C) + (D)] + N suf · p. 7

7. Experiment

• The simulations compare MP-TS with Exp3.M, CUCB, and MP-KL-UCB on two fixed-arm settings and an online-advertising click-log setting.Scenarios 1 and 2 use 5 and 20 Bernoulli arms; Scenario 3 uses ad click-through rates from a commercial search engine and has more arms and smaller reward gaps. Exp3.M is designed for adversarial rewards.Source: §7 · p. 7
• MP-TS performs significantly better than the other algorithms across all scenarios, and its regret slope quickly approaches the asymptotic lower bound.MP-KL-UCB performs better than CUCB and Exp3.M, but not as well as MP-TS.Source: §7 · pp. 7–8, Figure 2 · p. 8

7.1. Improvement of MP-TS based on the empirical means

• IMP-TS selects L−1 arms using empirical averages and the last arm using Thompson sampling, but the authors provide no regret bound for it.They expect it to achieve the asymptotic bound because T/L exploration opportunities still yield O(log T) opportunities.Source: §7.1 · p. 8
• At T ∼10^3–10^4, IMP-TS’s regret reduction is largest; MP-TS still outperforms IMP-KL-UCB.The before/after comparison uses the settings of Scenario 3, changing only the algorithms.Source: §7.1 · p. 8, Figure 3 · p. 8

8. Discussion

• MP-TS achieves optimal regret for binary rewards when total reward is linear in the selected arms’ individual rewards.The analysis uses independence of posterior samples and is presented as a step toward tight regret analysis that accounts for arm-selection combinatorics.Source: §8 · p. 8
• Position-dependent ad click-through rates change the selection problem from choosing an L-set to choosing an L-sequence.The paper considers a cascade-model MP-TS extension that corrects position-dependent bias as a starting point.Source: §8 · p. 8
• The analysis considers binary rewards; extensions to one-dimensional exponential families and multi-parameter reward distributions remain of interest.Source: §8 · p. 8

Case 1

• The regret bound holds when several strictly suboptimal arms share an expectation, because the analysis treats each suboptimal arm separately.Source: §A.1 · p. 11

Case 2

• The regret bound also holds when strictly optimal arms are tied, since each strictly suboptimal arm remains separated from each strictly optimal arm.Source: §A.1 · p. 11

Case 3

• The analysis does not cover several marginal arms; their simultaneous draws make the regret structure more complex, and extra exploration may slightly increase regret.Source: §A.1 · p. 11

• Theorem 1 applies when the marginal arm is distinct.Source: §A.1 · p. 11

A.2. Cascade model and position-dependent MP-MAB problem

• The cascade model assumes users scan ads from top to bottom, with position discounts representing the probability of observing the next ad.Setting all discounts to 1 recovers the main paper’s model; when discounts are below 1, arm order matters and selection is an L-sequence, not an L-set.Source: §A.2 · p. 11

A.2.1. THOMPSON SAMPLING FOR CASCADE MODEL

• BC-MP-TS adjusts selected arms’ draw counts by their effective draws rather than incrementing by one; with all discounts equal to 1, it is essentially MP-TS.The effective draws account for the probability that an arm at a later position is observed.Source: §A.2.1 · pp. 11–12

A.2.2. OPTIMAL ARM SELECTION AND THE REGRET

• General position- and ad-dependent discounts make optimal sequence selection computationally intractable for large K; ad-independent discounts allow placing the l-th highest sampled arm at position l.For the ad-independent case, the paper conjectures the no-discount regret lower bound but proves no cascade regret bound; the general case is subtler because small changes in arm means can change the optimal selection.Source: §A.2.2 · p. 12

A.2.3. EXPERIMENT OF CASCADE MODEL

• BC-MP-TS’s regret slope quickly approaches the conjectured lower bound, while MP-TS has high regret because it ignores discount factors.The simulation uses 9 Bernoulli arms, L = 3, and a constant discount factor of 0.7.Source: Figure 4 · p. 12, §A.2.3 · p. 12

A.3. Key fact and lemmas

• The supporting appendix states Chernoff and Beta-Binomial facts, Pinsker’s inequality, and probability bounds for empirical averages and Beta posteriors.It also identifies Lemma 9 as combining existing techniques and Lemmas 10–11 as techniques used in earlier Bayesian bandit analyses.Source: §A.3 · pp. 12–14

A.4. Proof of Lemma 3 Evaluation of term (A):

• In the Lemma 3 proof, term (B) is O(log log T) in expectation, and the first term of (22) is O(1).The latter is bounded by 1 + 1/d(µL, µi).Source: §A.4 · pp. 15–16
• Bounds on the second term in (24) and the two subterms of (D) are combined to establish inequality (16).Source: §A.4 · p. 17

A.5. Proof of Lemma 4

• The proof of Lemma 4 is reduced to a statement for arbitrary positive a and b, after which the proof is completed.Source: §A.5 · p. 17