Online recommender systems seek to recommend a small list of items (such as movies or hotels) to users based on a larger ground set [L] := {1, . . . , L} of items. In this paper, we consider the cascading bandits model (Craswell et al., 2008; Kveton et al., 2015a), which is widely used in information retrieval and online advertising. Upon seeing the chosen list, the user looks at the items sequentially. She clicks on an item if she is attracted by it and skips to the next one otherwise. This process stops when she clicks on one item in the list or if no item is clicked, it is deemed that she is not attracted by any of the items. The items that are in the ground set but not in the chosen list and those in the list that come after the attractive one are unobserved.

Each item , with a certain click probability [0, 1] which is unknown to the learning agent, attracts the user independently of other items. Under this assumption, the optimal solution is the list of items with largest w(i)’s. Based on the chosen lists and obtained feedback in previous steps, the agent tries to learn the click probabilities (explore the combinatorial space) in order to find the optimal list with high probability in as few time steps as possible.

Main Contributions. Given , a learning agent aims to find a list of optimal items of size K with probability at least in minimal time steps. To achieve a greater generality, we provide results for identifying a list of nearoptimal items (Even-Dar et al., 2002; Mannor & Tsitsiklis, 2004; Kalyanakrishnan et al., 2012), where the notion of near-optimality is precisely defined in Section 2. First, we design CASCADEBAI() and derive an upper bound on its time complexity. Second, we establish a lower bound on the time complexity of any best arm identification (BAI) algorithm in cascading bandits, which implies that the performance of CASCADEBAI() is optimal in some regimes. Finally, our extensive numerical results corroborate the efficacy of CASCADEBAI() and the tightness of our upper bound on its time complexity.

Different from combinatorial semi-bandit settings, the amount of feedback in cascading bandits is, in general, random. The analysis of cascading bandits involves the unique challenge in adapting to the variation of the amount of feedback across time. To this end, we define a random variable (r.v.) that describes the feedback from the user at a step and bound its expectation. We define a novel class of r.v.’s, known as left-sided sub-Gaussian (LSG) r.v.’s, and apply a concentration inequality to quantify the variation of the amount of feedback.

Bernstein-type concentration inequalities are applied in many stochastic bandit problems and indicate that subGaussian (SG) distributions possess light tails (Audibert & Bubeck, 2010). Since it turns out that we only need to analyze a one-sided tail in this work, it suffices to consider a one-sided SG condition, which motivates the definition of LSG. We also provide a general estimate of a certain corresponding parameter in Theorem 5.4, which is crucial for the utilization of the inequality. This may be of independent interest. Summary and future work are deferred to Appendix 7.

Literature review. In a stochastic combinatorial bandit (SCB) model, an arm corresponds to a list of items in the ground set, and each item is associated with an r.v. at each time step. The corresponding reward depends on the constituent items’ realizations. We first review the related works on the BAI problem, in which a learning agent aims to identify an optimal arm, i.e., a list of optimal items. (i) Given , a learning agent aims to identify an optimal arm with probability in minimal time steps (Jamieson & Nowak, 2014; Kalyanakrishnan et al., 2012). (ii) Given B > 0, an agent aims to maximize the probability of identifying an optimal arm in B steps (Auer et al., 2002; Audibert & Bubeck, 2010; Carpentier & Locatelli, 2016). These two settings are known as the fixed-confidence and fixed-budget setting respectively. Under the fixed-confidence setting, the early works aim to identify only one optimal item (Audibert & Bubeck, 2010) and the later ones aim to find an optimal arm (Chen et al., 2014; Rejwan & Mansour, 2019). Besides, Mannor & Tsitsiklis (2004); Kaufmann et al. (2016); Agar- wal et al. (2017) provide problem-dependent lower bounds on the time complexity when Kalyanakrishnan et al. (2012) establishes a problem-independent one. All these existing works are under the semi-bandit feedback setting, where an agent observes realizations of all pulled items.

Secondly, we review the relevant works on the regret minimization (RM) problem, in which an agent aims to maximize his overall reward, or equivalently to minimize the so-called cumulative regret. Under the semi-bandit feedback setting, this problem has been extensively studied by Lai & Robbins (1985); Anantharam et al. (1987); Kveton et al. (2014); Li et al. (2010); Qin et al. (2014). Moreover, motivated by numerous applications in clinical analysis and online advertisement, some researchers consider SCB models with partial feedback, where an agent observes realizations of only a portion of pulled items. One prime model that incorporates the partial feedback is cascading bandits (Craswell et al., 2008; Kveton et al., 2015a). Recently, Kveton et al. (2015b); Li et al. (2016); Zong et al. (2016); Wang & Chen (2017); Cheung et al. (2019) studied this model and derived various regret bounds.

When the RM problem is studied with both semi-bandit and partial feedback, the BAI problem has only been studied in the semi-bandit feedback setting thus far. Despite existing works, analysis of the BAI problem in the more challenging case of partial feedback is yet to be done. Our work fills in this gap in the literature by studying the fixed-confidence setting in cascading bandits, and our analysis provides tools for handling the statistical dependence between the amount of feedback and that of time steps in the cascading bandit setting.

For brevity, we denote the set {1, . . . , n} by [n] for any , and the set of all m-permutations of [n], i.e., all ordered m-subsets of [n], by for any . Let there be ground items, contained in [L]. Each item is associated with a weight , signifying the item’s click probability. We define an arm as a list of items in . At each time step t, the agent pulls an arm . Then the user examines the items from to one at a time, until one item is clicked or all items are examined. For each item are i.i.d. across time. The agent observes iff the user clicks on i. The feedback from the user is defined as a vector in represents observing no click, observing a click and no observation respectively. For example, if K = 4 and the user clicks on the third item at time step 2, we have . Clearly, there is a one-to-one mapping from to the integer

where we assume . If (i.e., is not the all-zero vector), the agent observes for , and also observes , but does not observe for . Otherwise, we have (i.e., is the all-zero vector), then the agent observes for . We denote , w = (w(1), . . . , w(L)), and the probability law (resp. the expectation) of the process

Without loss of generality, we assume . We say item i is optimal if . We assume w(K) > w(K +1) to ensure there are exactly K optimal items. Next, we say item i is -optimal () if and set set of all -optimal items, is the set of all optimal arms (up to permutation), and is the set of all -optimal arms.

To identify an -optimal arm, an agent uses an algorithm that decides which arms to pull, when to stop pulling, and which arm to choose eventually. A deterministic and non-anticipatory online algorithm consists in a triple

• the sampling rule determines, based on the observation history, the arm to pull at time step t; in other words, is -measurable, with • the stopping rule determines the termination of the algo-

rithm, which leads to a stopping time with respect to satisfying

• the recommendation rule chooses an arm -measurable.

We define the time complexity of . Under the fixed-confidence setting, a risk parameter (failure probability) (0, 1) is fixed. We say an algorithm -PAC (probably approximately correct) if goal is to obtain an -PAC algorithm such that is small and is small with high probability. We also define the optimal expected time complexity over all -PAC algorithms as

This measures the hardness of the problem. We abbreviate when there is no ambiguity.

Our algorithm CASCADEBAI() is presented in Algorithm 1. Intuitively, to identify an -optimal arm, an agent needs to learn the true weights w(i) of a number of items in [L] by exploring the combinatorial arm space.

At each step t, we classify an item as surviving, accepted or rejected. Initially, all items are surviving and belong to the survival set . Over time, an item may be eliminated from , in which case we say that it is identified. Once an item is identified, it can be moved to either the accept set if it is deemed to be -optimal, or the reject set otherwise. (i) At step 1, all items are in . (ii) At each step t, the agent selects surviving items with the least number of previous observations, ’s, pulls them in ascending order of the , and gets cascading feedback from the user in the form of the ’s. Similarly to a Racing algorithm (Even-Dar et al., 2002; Maron & Moore, 1994; Heidrich-Meisner & Igel, 2009; Jun et al., 2016), this design of increases the ’s of all surviving items almost uniformly and avoids the wastage of time steps. (iii) Next, we maintain upper and lower confidence bounds (UCB, LCB) across time to facilitate the identification of items as in Lines 13–17. The confidence radius is defined as follows:

We set when . (iv) Lastly, the algorithm stops once

We develop an upper bound on the time complexity of CASCADEBAI() and a lower bound on the expected time complexity of any -PAC algorithm. We also discuss the gap between the bounds. We use to denote finite and positive universal constants whose values may vary from line to line. The proofs are sketched in Section 5 and more details are provided in Appendix D.

4.1. Upper bound

The gaps between the click probabilities determine the hardness to identify the items. The gaps are defined as

Here is a slight variation of that takes into account the -optimality of items. Moreover, to correctly identify item i with probability at least , our algorithm needs to observe it at least

times. Similarly to existing works (Even-Dar et al., 2002; Mannor & Tsitsiklis, 2004), we derive the upper bound with ’s. A larger leads to a smaller that it requires fewer observations to identify item i correctly. The permutation defines the ordering of : as the number of surviving items in as the number of observations of them. Note that is an r.v. We lower bound

µ(k, w):=

and upper bound with . We abbreviate as as as as when there is no ambiguity. In anticipation of Theorem 4.1, we define three more notations:

K

Theorem 4.1. Assume . With probability at least , Algorithm 1 outputs an -optimal arm after at most steps, where

When , for all and . We note that it is a waste to pull identified items. This occurs only when (see Lemma 5.9) and this scenario is more complicated to analyze. The scenario is relatively easier to analyze and the result is deferred to Proposition C.1 (see Appendix C).

Interpretation of the bound. The first term in the bound is unique to the cascading model, which results from the gap between and . We can bound in terms of the maximum and minimum weights,

Proposition 4.2. Assume

Next, recall that we say that an item is identified by time t if it is put into or for some . In the worstcase scenario, the agent identifies items in descending order of ’s. With probability at least , it costs at most steps to identify items is for identifying the remaining ones. More precisely, after item is identified, the number of steps required for identifying item is we sum these steps up to obtain (4.1). Since the results in many existing works (Even-Dar et al., 2002; Jun et al., 2016) mainly involve ’s, we show the dependence of more concretely in (4.2).

Technique. The crucial analytical challenge to derive our bound, especially to establish , is to quantify the impact of partial feedback that results from the cascading model. Firstly, we bound by exploiting some properties of the cascading feedback. Next, to bound the gap between and for some , we propose a novel class of r.v.’s, known as LSG r.v.’s, provide an estimate of a certain LSG parameter, and utilize a Berstein-type concentration inequality to bound the tail probability of a certain LSG r.v.. Details are in Section 5.1.

To facilitate the remaining discussion in Section 4.1, we specialize our analysis and results henceforth to the case of and the agent aims to find remaining results in Section 4.1 can be directly generalized to the scenario of by replacing

Comparison to the semi-bandit problem. A related algorithm in the setting of semi-bandit feedback and is the BATCHRACING Algorithm, which was proposed by Jun et al. (2016). This algorithm has three paramters k, r and b which respectively represent the number of optimal items, the maximum number of pulls of one item at one step and the size of a pulled arm. When r = 1 and b = k, we denote it as BATRAC(k). The fact that our algorithm observes between 1 and K items per step motivates a comparison among CASCADEBAI(

Corollary 4.3. (i) If all w(i)’s are at most 1/K, with probability at least , Algorithm 1 outputs after at most

steps; (ii) if all w(i)’s are at least 1/2, with probability at least , Algorithm 1 outputs after at most

steps.

The results of Corollary 4.3 are intuitive: (i) if all w(i)’s are close to 0 (i.e., at most 1/K), the bound on the time complexity of CASCADEBAI() is of the same order as that of BATRAC(K); (ii) if all w(i)’s are close to 1 (i.e., at least 1/2), the bound corresponds with that of BATRAC(1) (Jun et al., 2016). We further upper bound the expected time complexity of our algorithm (denoted by ) in these cases.

Proposition 4.4. (i) If all w(i)’s are at most 1/K,

(ii) if all w(i)’s are at least 1/2,

According to the definition of and hence also satisfies the above bounds. Corollary 4.3 and Proposition 4.4 indicate that the high probability upper bound on and the upper bound on are of the same order in the sense that (i) if all w(i)’s are at most 1/K, both upper bounds are if all w(i)’s are at least

Specialization to the case of two click probabilities. We consider a simplified scenario with the following assumption; this allows us to present the upper bound on the time complexity with greater clarity.

Assumption 4.5. With , the K optimal and suboptimal items have click probabilities and respectively.

Proposition 4.6. Under Assumption 4.5, (i) if 1/K, with probability at least , Algorithm 1 outputs after at most

steps; (ii) if , with probability at least

Algorithm 1 outputs after at most

steps.

In the second case, if , the first term dominates the bound. For instance, satisfies this condition.

Proposition 4.7. Under Assumption 4.5, (i) if

(ii) if

Proposition 4.7 also upper bounds together with Proposition 4.6 implies that the high probability bound on and the bound on are of the same order in these cases.

4.2. Lower bound

We set , in which scenario the agent aims to find an optimal arm . We also upper bound the expected number of observations of items per step by

We write ˜, where KL(

Theorem 4.8. We have

Comparison to the semi-bandit problem. First, if is close to 1 (i.e., , i.e., at one step, the agent observes at most 2 items in expectation. We can recover the lower bound in Kaufmann et al. (2016) by replacing with 1, which is of the same order as our bound in this case. Next, if is close to the agent observes items in expectation. Then the bound is the same as that incurred by pulling K items per step and getting semi-bandit feedback, which is

Specialization to the case of two click probabilities.

Corollary 4.9. Under Assumption 4.5, we have

4.3. Comparison of the upper and lower bounds

To see whether the upper and lower bounds on match, we set and consider the following simplified cases.

Corollary 4.10. Set

(ii) if

The upper bounds above are achieved by Algorithm 1.

In the first case, the gap between the upper and lower bounds is manifested in the terms . In the second case, the gap is manifested in

5.1. Analysis of partial feedback for cascading bandits

At a high level, the time complexity T can be established by analyzing and . The first term is de- termined by ’s, the number of observations that guarantees the correct identification of items with high probability. These ’s are invariant to the scenario whether the agent receives semi-bandit or partial feedback from the user. The second term in the semi-bandit feedback setting while it is an r.v. in the partial feedback setting. Since ’s have already been studied by a number of works on the semi-bandit feedback (Even-Dar et al., 2002; Jun et al., 2016), the crucial challenge of analyzing cascading bandits is to estimate probabilitistically.

According to Algorithm 1, , the agent pulls K surviving (i.e., not identified) items. Otherwise, the agent pulls all surviving items first and then complements with some identified items. In the cascading bandit setting, the agent observes only one item when the first item is clicked, and the corresponding probability is ; the agent observes two items when is not clicked but is clicked, and the probability is ; and so on. Therefore,

Since depends only on (the pulled arm at step t) and is learnt online, it is difficult to estimate for each step separately. Therefore, the second best thing one can do is to bound as a function of and w. We now present some properties of

Theorem 5.1. Consider a set of items with weights u = such that , and let be the expected number of observations when items are placed with order I. Let , and I be any order, then

(i) boundedness:

(ii) monotonicity: let be another vector of weights, then

Theorem 5.1 implies that when w is fixed, attains its minimum when the agent pulls items 1, 2, . . . , k in this order and attains its maximum when the agent pulls in this order. Moreover, if for all is even smaller; if for all is even larger. This observation inspires Lemma 5.2.

Lemma 5.2. For any k, t,

Next, since , instead of , affects the dynamics, we examine the gap between and . Clearly, a tight concentration inequality is essential to estimate this gap well. Since is a bounded r.v., there are some applicable Bernstein-type inequalities. For instance, we can apply Azuma’s inequality to analyze SG r.v.’s. However, (i) it is challenging to find an SG parameter of that is good enough for our purpose (a more detailed explanation is provided after Lemma 5.6), and (ii) we only require a one-sided concentration inequality. Hence, we resort to defining a new class of r.v.’s — known as LSG r.v.’s — and provide an estimate of the relevant LSG parameter.

Definition 5.3 (LSG). An r.v.

Theorem 5.4. Let X be an almost surely bounded nonnegative r.v.. If

Furthermore, we bound (Lemma 5.5) and adapt a variation of Azuma’s inequality as in Theorem B.1 (Shamir, 2011) to evaluate the dependence between the number of observations and the number of time steps.

Lemma 5.5. For any

Lemma 5.6. For any

then . Further when holds, for any T > 0, implies that

Lemma 5.6 implies that with high probability, we can lower bound the amount of observations on the surviving items over the whole horizon. Subsequently, with probability at least , the agent would have received sufficiently many observations on the surviving items to return an -optimal arm after at most time steps (see Theorem 4.1). The lemma also indicates that a smaller LSG/SG parameter of leads to a smaller upper bound on the number of time steps. Since we can show is -LSG but cannot show it is -SG (a detailed discussion is deferred to Appendix D.9), it is beneficial to consider the class of LSG distributions for our problem. The class of LSG r.v.’s and the general estimate of the LSG parameter, which is crucial for the utilization of the concentration inequality, may be of independent interest.

5.2. Proof sketch of Theorem 4.1

Concentration. As the algorithm proceeds, the agent moves items from to or according to the con-fidence bounds of all surviving items in . This motivates us to define a “nice event”

To show that holds with high probability, we utilize Theorem B.2 (Jamieson et al., 2014; Jun et al., 2016) and the SG property of (the r.v. that reflects whether item i is clicked at time step t).

Lemma 5.7. For any

Sufficient observations. Next, we assume holds and find the number of observations that guarantees the correct identification of an item. To facilitate the analysis of the expected time complexity (Proposition 4.4, 4.7), we assume holds for a fixed in Lemma 5.8, which generalizes Jun et al. (2016, Lemma 2). Lemma 5.8. Fix any Set , then for any time step t,

Lemmas 5.7 and 5.8 imply that with sufficiently many observations, the agent can correctly identify items with probability at least

Time complexity. Subsequently, we observe that our algorithm stops before identifying all items.

Lemma 5.9. Assume holds. Algorithm 1 stops after identifying at most

Lemma 5.9 indicates that it suffices to count the number of time steps needed to identify at most

We consider the worst case in which the agent identifies items in descending order of the ’s. We divide the whole horizon into several phrases according to , the number of surviving items. During each phrase, we upper bound the required number of observations with Lemma 5.8; then Lemma 5.6 helps to upper bound the required number of time steps with high probability. Lastly, we bound the total error probability by and utilize the Lagrange multipliers to solve the following problem:

Altogether, we upper bound the time complexity.

5.3. Proof sketch of Theorem 4.8

In particular, is optimal under instance 0, while suboptimal under instance . Bearing the risk of overloading the notations, under instance , we denote as an optimal arm, as the arm chosen by algorithm at step t and as the corresponding stochastic outcome (see its definition in Section 2).

Figure 5.1: Optimal set in instance (shaded in green)

KL divergence. We first apply chain rule to decompose

Lemma 5.10 (Cheung et al. (2018, Lemma 6.4)). For any

Next, we lower bound with the KL divergence by

applying a result from Kaufmann et al. (2016).

Lemma 5.11. For any

Define the event . We estab- lish that, for any -PAC algorithm, and . Lastly, by revisiting the definition of in Section 4.1, we see that also upper bounds the expected number of observations of items at one step for any -PAC algorithm (Lemma 5.2). This allows us to lower bound

We evaluate the performance of CASCADEBAIsome related algorithms. For each choice of algorithm and instance, we run 20 independent trials. The standard deviations of the time complexities of our algorithm are negligible compared to the averages, and therefore are omitted from the plots. More details are provided in Appendix E.

6.1. Order of pulled items

Figure 6.1: Average time complexity incurred by different sorting order of : ascending order of (Algorithm 1), ascending/descending order of in the cascading bandits.

As shown in Lines 5–9 of Algorithm 1, CASCADEBAI() sorts items in based on ascending order of ’s. This order is crucial for proving our theoretical results. To learn the impact of ordering on the time complexity, we evaluate the empirical performance of sorting in descending or ascending order of ’s, ’s or ’s. We compare these methods under various problem settings and set the maximum time step as . Figure 6.1 shows that CASCADEBAI() empirically performs as well as the best among the other heuristics, but CASCADEBAI(is the only one with a theoretical guarantee.

6.2. Comparison to semi-feedback setting

We compare CASCADEBAI(), BATRAC(K) and BATRAC(1) (Jun et al., 2016) empirically. In Figure 6.2, if are sufficiently small as the parameters shown in subfigure (a), CASCADEBAI() performs similarly to BATRAC(K); if are large as in subfigure (b), it behaves similarly to BATRAC(1). This corroborates the implications of Corollary 4.3.

Figure 6.2: Average time complexity of CASCADEBAI, BATRAC(1), BATRAC(K) with

6.3. Further empirical evidence

Our analysis of the cascading feedback involves in the upper bound of the time complexity; these parameters depend strongly on to assess the tightness of our analyses, we consider several simplified cases by choosing as functions of K and examine whether the dependence of the resultant time complexity (Proposition 4.6) on K is materialized through numerical experiments.

Table 6.1: Upper bounds on the time complexity of Al- gorithm 1 with , (Proposition 4.6), and their fitting results.

We fit a model to the averaged time complexity under each setting as stated in Table 6.1. In each case, the -statistic is almost 1, implying that the variability of the time complexity is almost fully explained by the proposed polynomial model (Glantz et al., 1990). Therefore, the empirical results show that the dependence of the upper bound on K (Proposition 4.6) is rather tight, which implies that using the new concept of LSG r.v.’s, our quantifications of the cascading feedback are also rather tight.

Figure 6.3: Fit the averaged time complexity with functions of K for two cases. Fix . Blue dots are the averaged time complexity, red line is the fitted curve, and cyan dashed lines show the 95% confidence interval.

This work presents the first theoretical analysis of best arm identification problem with partial feedback. We also show that the upper bound for the CASCADEBAI() algorithm closely matches the lower bound in some cases. Empirical experiments further support the theoretical analysis. Moreover, the relation between the second moment and the LSG property of a bounded random variable may be of independent mathematical interest.

The assumption of (ensuring tightness of the sample complexity in Corollary 4.10) is relevant in practical applications since CTRs are low in real applications. For most applications (e.g. online advertising), K is small (10), so our assumption is reasonable. We are cautiously optimistic that, the framework could be enhanced for better bounds in the remaining less practically relevant regime, which is an avenue for future work.

The following are some more avenues for further investigations. First, we note that estimating the number of observations per time step is key to establishing a high probability bound on the total number of time steps. In this work, we bound the expectation of this term with and w (Lemma 5.2). This bound is tight in some cases (cf. Corollary 4.10). These include the difficult case where all click probabilities w(i)’s are close to one another and hence the gaps are small. Nevertheless, a tighter bound for each individual time step may improve the results; this, however, will require a more elaborate and delicate analysis of the stochastic outcomes and their impacts at each time step. This is especially so since the order of selected items also affects the number of observations in the cascading bandit setting. Secondly, this work focuses on the fixed-confidence setting of the BAI problem. We see that the consideration of the fixed-budget setting for cascading bandits is still not available. It is envisioned that the analysis of the statistical dependence between the number of observations and time steps would be non-trivial. Thirdly, we envision that the analysis may be generalized to the contextual setting (Soare et al., 2014; Tao et al., 2018).

We thank the reviewers for their insightful comments. This work is partially funded by a National University of Singapore Start-Up Grant (R-266-000-136-133) and a Singapore National Research Foundation (NRF) Fellowship (R-263-000-D02-281).

Agarwal, A., Agarwal, S., Assadi, S., and Khanna, S. Learning with limited rounds of adaptivity: Coin tossing, multi-armed bandits, and ranking from pairwise comparisons. In Kale, S. and Shamir, O. (eds.), Proceedings of the 2017 Conference on Learning Theory, volume 65 of Proceedings of Machine Learning Research, pp. 39–75, Amsterdam, Netherlands, 07–10 Jul 2017. PMLR. URL http://proceedings.mlr.press/ v65/agarwal17c.html.

Anantharam, V., Varaiya, P., and Walrand, J. Asymptot- ically efficient allocation rules for the multiarmed bandit problem with multiple plays–Part I: I.I.D. rewards. IEEE Transactions on Automatic Control, 32(11):968– 976, November 1987.

Audibert, J.-Y. and Bubeck, S. Best arm identification in multi-armed bandits. In COLT-23th Conference on learning theory-2010, pp. 13–p, 2010.

Auer, P., Cesa-Bianchi, N., and Fischer, P. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2-3):235–256, 2002.

Carpentier, A. and Locatelli, A. Tight (lower) bounds for the fixed budget best arm identification bandit problem. In Conference on Learning Theory, pp. 590–604, 2016.

Chen, S., Lin, T., King, I., Lyu, M. R., and Chen, W. Combinatorial pure exploration of multi-armed bandits. In Ghahramani, Z., Welling, M., Cortes, C., Lawrence, N. D., and Weinberger, K. Q. (eds.), Advances in Neural Information Processing Systems 27, pp. 379–387. Curran Associates, Inc., 2014. URL http://papers.nips.cc/paper/5433- combinatorial-pure-exploration-of- multi-armed-bandits.pdf.

Cheung, W. C., Tan, V. Y. F., and Zhong, Z. Thompson sam- pling for cascading bandits. CoRR, abs/1810.01187, 2018. URL http://arxiv.org/abs/1810.01187.

Cheung, W. C., Tan, V., and Zhong, Z. A Thompson sam- pling algorithm for cascading bandits. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 438–447, 2019.

Cover, T. M. and Thomas, J. A. Elements of information theory. John Wiley & Sons, 2012.

Craswell, N., Zoeter, O., Taylor, M., and Ramsey, B. An experimental comparison of click position-bias models. In Proceedings of the 1st ACM International Conference on Web Search and Data Mining, pp. 87–94, 2008.

Even-Dar, E., Mannor, S., and Mansour, Y. Pac bounds for multi-armed bandit and markov decision processes. In International Conference on Computational Learning Theory, pp. 255–270. Springer, 2002.

Glantz, S. A., Slinker, B. K., and Neilands, T. B. Primer of applied regression and analysis of variance, volume 309. McGraw-Hill New York, 1990.

Heidrich-Meisner, V. and Igel, C. Hoeffding and bernstein races for selecting policies in evolutionary direct policy search. In Proceedings of the 26th Annual International Conference on Machine Learning, pp. 401–408. ACM, 2009.

Jamieson, K. and Nowak, R. Best-arm identification algo- rithms for multi-armed bandits in the fixed confidence setting. In 2014 48th Annual Conference on Information Sciences and Systems (CISS), pp. 1–6. IEEE, 2014.

Jamieson, K., Malloy, M., Nowak, R., and Bubeck, S. lilucb: An optimal exploration algorithm for multi-armed bandits. In Conference on Learning Theory, pp. 423–439, 2014.

Jun, K.-S., Jamieson, K. G., Nowak, R. D., and Zhu, X. Top arm identification in multi-armed bandits with batch arm pulls. In AISTATS, pp. 139–148, 2016.

Kalyanakrishnan, S., Tewari, A., Auer, P., and Stone, P. Pac subset selection in stochastic multi-armed bandits. In ICML, volume 12, pp. 655–662, 2012.

Kaufmann, E., Capp´e, O., and Garivier, A. On the complexity of best-arm identification in multi-armed bandit models. The Journal of Machine Learning Research, 17 (1):1–42, 2016.

Kveton, B., Wen, Z., Ashkan, A., Eydgahi, H., and Eriksson, B. Matroid bandits: Fast combinatorial optimization with learning. In Proceedings of the Thirtieth Conference on Uncertainty in Artificial Intelligence, UAI’14, pp. 420– 429, 2014.

Kveton, B., Szepesvari, C., Wen, Z., and Ashkan, A. Cas- cading bandits: Learning to rank in the cascade model.

In International Conference on Machine Learning, pp. 767–776, 2015a.

Kveton, B., Wen, Z., Ashkan, A., and Szepesv´ari, C. Combinatorial cascading bandits. In Proceedings of the 28th International Conference on Neural Information Processing Systems - Volume 1, NIPS’15, pp. 1450–1458, 2015b.

Lai, T. L. and Robbins, H. Asymptotically efficient adaptive allocation rules. Advances in applied mathematics, 6(1): 4–22, 1985.

Li, L., Chu, W., Langford, J., and Schapire, R. E. A contextual-bandit approach to personalized news article recommendation. In Proceedings of the 19th International Conference on World Wide Web, pp. 661–670, 2010.

Li, S., Wang, B., Zhang, S., and Chen, W. Contextual combinatorial cascading bandits. In Proceedings of The 33rd International Conference on Machine Learning, volume 48, pp. 1245–1253, 2016.

Mannor, S. and Tsitsiklis, J. N. The sample complexity of exploration in the multi-armed bandit problem. Journal of Machine Learning Research, 5(Jun):623–648, 2004.

Maron, O. and Moore, A. W. Hoeffding races: Accelerat- ing model selection search for classification and function approximation. In Advances in neural information processing systems, pp. 59–66, 1994.

Qin, L., Chen, S., and Zhu, X. Contextual combinatorial bandit and its application on diversified online recommendation. In SDM, pp. 461–469. SIAM, 2014.

Rejwan, I. and Mansour, Y. Combinatorial bandits with full-bandit feedback: Sample complexity and regret minimization. arXiv preprint arXiv:1905.12624, 2019.

Shamir, O. A variant of azuma’s inequality for martingales with subgaussian tails. arXiv preprint arXiv:1110.2392, 2011.

Soare, M., Lazaric, A., and Munos, R. Best-arm identifica- tion in linear bandits. In Advances in Neural Information Processing Systems, pp. 828–836, 2014.

Tao, C., Blanco, S., and Zhou, Y. Best arm identifi-cation in linear bandits with linear dimension dependency. In Dy, J. and Krause, A. (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 4877–4886, Stockholmsmssan, Stockholm Sweden, 10–15 Jul 2018. PMLR. URL http:// proceedings.mlr.press/v80/tao18a.html.

Wang, Q. and Chen, W. Improving regret bounds for com- binatorial semi-bandits with probabilistically triggered arms and its applications. In Advances in Neural Information Processing Systems, pp. 1161–1171, 2017.

Zong, S., Ni, H., Sung, K., Ke, N. R., Wen, Z., and Kveton, B. Cascading bandits for large-scale recommendation problems. In Proceedings of the Thirty-Second Conference on Uncertainty in Artificial Intelligence, UAI’16, pp. 835–844, 2016.

Here are some basic facts from the literature that we will use:

Theorem B.1 (Azumas Inequality for Martingales with Subgaussian Tails, implied by Shamir (2011)). Let be a martingale difference sequence, and suppose that for any almost surely. Then for all

Theorem B.2 (Non-asymptotic law of the iterated logarithm (Jamieson et al., 2014; Jun et al., 2016)). Let be i.i.d. zero-mean sub-Gaussian random variables with scale

In general, a larger indicates a smaller time complexity. Here are two explanations. (i) When grows, , the number of -optimal items also grows. Then it should be easier to identify an -optimal arm. (ii) If is sufficiently large such that , then there are at least K items left in the survival set before the algorithm stops. Otherwise, when , the agent pulls surviving items at some steps and this results in a wastage in the number of time steps.

Proposition C.1. Assume . With probability at least , Algorithm 1 outputs an -optimal arm after at most steps where

In this Section, we provide proofs of Proposition 4.2, Corollary 4.3, Propositions 4.4, 4.6, 4.7, Corollary 4.9, Theorem 5.1, 5.4, Lemmas 5.2 – 5.11, and complete the proof of Theorems 4.1, 4.8, Proposition C.1 in this order.

D.1. Proof of Proposition 4.2

Proposition 4.2. Assume

Proof. According to Lemma 5.2 and Theorem 5.4,

We upper bound in two cases:

(i):

(ii):

D.2. Proof of Corollary 4.3

steps; (ii) if all w(i)’s are at least 1/2, with probability at least , Algorithm 1 outputs after at most

steps.

Proof. According to Lemma 5.2 and Theorem 5.4,

We first upper bound in two cases:

(i):

(ii):

Next, we separate the upper bound in Theorem 4.1 into two parts and bound them separately:

Case 1: All click probabilities w(i) are at most

Case 2: All click probabilities w(i) are at least

Recall that when

for all . Altogether, we complete the proof.

D.3. Proof of Proposition 4.4

Proposition 4.4. (i) If all w(i)’s are at most 1/K,

(ii) if all w(i)’s are at least 1/2,

Proof. (i) Consider all click probabilities ’s are at most 1/K. For any , revisit the proof and result of Theorem 4.1. First, Lemma 5.7 implies that . Assume holds from now on. Secondly, Lemma 5.8 indicates that Algorithm 1 can correctly identify item observations. Thirdly, similar to the discussion in Section 5.2, we set . Additionally applying the analysis in Proposition 4.2 and Corollary 4.3, with probability at least , we can bound the time complexity by

In short, set

then

Meanwhile, Tonelli’s Theorem implies that

Since

(ii) Consider all click probabilities w(i)’s are at least 1/2. The analysis is similar to that in Case (i). With the analysis in Theorem 4.1 and results in Proposition 4.2 and Corollary 4.3, for any , with probability at least , the time complexity is at most

D.4. Proof of Proposition 4.6

Proposition 4.6. Under Assumption 4.5, (i) if , with probability at least , Algorithm 1 outputs at most

steps; (ii) if , with probability at least , Algorithm 1 outputs after at most

steps.

Proof. We first remind ourselves how the algorithm proceeds. In this instance, yields . For any item . And according to Lemma 5.8, item i will be correctly classified with high probability after observations where

This implies that each item requires the same number of observations to be correctly identified. According to the design of algorithm, for any remaining items . Therefore, the worst case is as follows:

• the agent observes one item for times and the others for times after steps, and identifies one item per step for the subsequent

Therefore, we now turn to upper bounding the number of steps required to eliminate an item for the first time. According to Lemma 5.6, we set . Then the total number of observations during steps should be larger than with probability at least . The number of observations can be upper bounded as follows:

Then with Lemma 5.7 and its ensuing discussion in Section 5.2, with probability at least , the time complexity is upper bounded by

Next, we consider how the values of affect the bound. According to Lemma 5.2 and Theorem 5.4,

We discuss two cases separately:

Case 1: . The upper bound becomes:

Case 2: . The bound becomes

D.5. Proof of Proposition 4.7

Proposition 4.7. Under Assumption 4.5, (i) if

(ii) if

Proof. For any , we revisit the proof of Proposition 4.6. Firstly, Lemma 5.7 implies that . Assume holds from now on. Secondly, Lemma 5.8 implies that the agent can identify any item correctly after

observations. Then with analysis similar to Appendix D.4, we can upper bound the time complexity of Algorithm 1 with probability

Case 1: : with probability at least , the time complexity is upper bounded by

Then for any . Meanwhile, Tonelli’s Theorem implies that

Since

Case 2: : with a similar analysis, for any

D.6. Proof of Corollary 4.9

Corollary 4.9. Under Assumption 4.5, we have

Proof. First, by setting , the result in Theorem 4.8 becomes

Next, according to Pinsker’s and reverse Pinsker’s inequality for any two distributions P and Q defined in the same finite space X we have

where . In our case, set and

Further since as stated by Lemma 5.2, the lower bound becomes

D.7. Proof of Theorem 5.1

Theorem 5.1. Consider a set of items with weights such that , and let be the expected number of observations when items are placed with order

order, then

Proof. (i) Consider any ordered set , it is sufficient to show the following:

If there exists such that , we can change their positions to get and have

The proof of is as follows:

µ

µ

(ii) To show the monotonicity, it is sufficient to show the following:

(#): Set two sets of click probabilities u, v such that for some and for . Then we have

Here is the proof of (#). If m = k, then obviously we have , we exchange positions of the m-th and (m + 1)-th item to get a new ordered set

Hence

If m + 1 < k, note that the only difference between now lies in the click probability of the (m + 1)-th item. In detail,

We exchange positions of the (m + 1)-th and (m + 2)-th item in to get a new ordered set . Similarly we have

We can continue this operation for times and get . Iteratively, we have . Besides, the only difference between now lies in the click probability of the k-th item:

Since µ

D.8. Proof of Lemma 5.2

Lemma 5.2. For any k, t,

Proof. Lower bound. According to Lemma 5.1, the expectation of observations attains its minimum when we pull an ordered set {1, 2, . . . , k}, and attains its maximum when we pull an ordered set . In other words, depending on the instance, the expectation of observations can be lower bounded as follows:

Moreover, since the lower bound is larger than the expectation of observations when pull item 1 for K times (note that this is not allowed in Algorithm 1), we can utilize only to lower bound the expectation:

then

Let , then . Since is a nondecreasing function of x and ,

If , there exists

This leads to

Otherwise,

decreases as increases. Then,

Upper bound. Similarly we can see that the expectation of observations attains its maximum when we pull an ordered set , and therefore upper bounded by

Furthermore, the upper bound is smaller than the expectation of observations when or we pull item L for K times (again note that this is not allowed in Algorithm 1):

D.9. Proof of Theorem 5.4

Theorem 5.4. Let X be an almost surely bounded nonnegative r.v.. If

Proof. Set and a.s., then and . It is equivalent to show that for any ,

Set

it is further equivalent to show . Then since a.s., for any , by Bounded Convergence Theorem,

Therefore,

Let be the probability measure of

Since . Hence is monotonically decreasing on R. Further, for any , since

Given , it is more challenging to show X is v-SG than to show X is v-LSG. By revisiting the proof above, we see that given X is v-LSG, to show X is v-SG suffices to show . Since it is hard to directly tell whether the inequality above holds for any , it is natural to look at how

Fix any , again, applying the Bounded Convergence Theorem, we have

Since is differentiable on R, it requires at least . Furthermore, since , one may consider showing that

In the proof above, we define a function g to show that on . However, since on , this cannot help to show

The discussion above indicates that showing X is v-SG is more challenging than showing X is v-LSG.

D.10. Proof of Lemma 5.5

Lemma 5.5. For any

Proof. Recall is the minimum click probability. We abbreviate as X. Firstly, since . Next, note that increases when the click probabilities decrease or k increases. Set Y as a random variable drawn from a geometric distribution with parameter

D.11. Proof of Lemma 5.6

Lemma 5.6. For any

then . Further when holds, for any implies that

Proof. We abbreviate (the number of observations of surviving items at step t when pulling k surviving items), and set denote the decisions and observations up to step t. Besides, let be the set to pull at step t, then is determined by depends on

i s a martingale difference sequence adapted to . Besides, according to Theorem 5.4, for any t, any . Then for any

Let the probability bound in the right hand side be

Note that

Next, for any T > 0, consider

Set

then . Note that

D.12. Proof of Lemma 5.7

Proof of Remark D.1. Any non-negative random variable bounded in [a, b] a.s. is sub-Gaussian with parameter Meanwhile, yields that

Proof. For all . Recall that

then according to Theorem B.2,

D.13. Proof of Lemma 5.8

Preliminary. Since we use the UCB of the empirical top-item to accept -optimal items, hopefully it should be close to the true click probability of item ; likewise, the LCB of the empirical top-item should be close to the true click probability of item . This is stated in Lemma D.2.

Lemma D.2 (Jun et al. (2016, Lemma 3)). Denote by the index of the item with empirical mean is i-th largest: i.e., Assume that the empirical means of the arms are controlled by

After that, Lemma 5.8 shows that the agent will correctly classify the items after a sufficient number of observations, and also show what is the sufficient number of observations for each item.

Proof. Recall

And We use as abbreviations for respectively.

It suffices to show for the case where are empty since otherwise the problem is equivalent to removing rejected or accepted arms from consideration and starting a new problem with and while maintaining the observations so far. Note that when

First of all, implies that

Then since . Combining this with Lemma D.2, we have

We first prove that for any

For clarity, we write , which is the item with (K + 1)-th largest empirical mean at the t-th step. We assume the contrary: . We can apply (D.1) and (D.2) to obtain

Next,

Part (a) of the second line above follows from: (i) if ; (ii) else, Then invert to the third line using

Therefore, implies that is accepted.

Subsequently, we prove that for any

Again for brevity, we write , the item with K-th largest empirical mean at the t-th step. We assume the contrary: . Again applying (D.1) and (D.2), we have

Next,

Similar to the first case, with

D.14. Proof of Lemma 5.9

Lemma 5.9. Assume holds. Algorithm 1 stops after identifying at most

Proof. Assume Case (i): . In the worst case, the algorithm does not terminate before identifying the -th one. In this case,

after identifying the -th one with sufficient observations, either the accept set or the reject set is full, i.e., or , the the agent can just place the remaining item in the unfilled set.

Hence, the algorithm terminates after sufficiently observing and identifying at most

Case (ii): . The algorithm classify all items correctly according to Lemma 5.8. since the number of -optimal items

is , the number of suboptimal items is Besides, according to the design of the algorithm. Therefore,

In other words, the algorithm terminates after sufficiently observing and identifying at most K, 1} items.

D.15. Proof of Lemma 5.11

Lemma 5.11. For any

To manifest the difference between instance and other instances, with

• under instance 0;

• , . . . , w, . . . , wunder instance ℓ.

We combine Lemma 5.10 and a result from Kaufmann et al. (2016) to relate the time complexity and KL divergence together. Lemma D.3 ((Kaufmann et al., 2016, Lemma 19)). Let T be any almost surely finite stopping time with respect to every event , instance

Notations. Before presenting the proof, we remind the reader of the definition of the KL divergence (Cover & Thomas, 2012). For two discrete random variables X and Y with common support A,

denotes the KL divergence between probability mass functions of X and Y . Next, we also use to also signify this KL divergence. Lastly, when a and b are two real numbers between 0 and , i.e., KL(a, b) denotes the KL divergence between Bern(a) and Bern(b).

Proof. For any certain , we can observe that the KL divergence should grow with the KL divergence of observed items. Further, for each observed item i, there is a KL divergence of

Then according to Lemma 5.10,

D.16. Proof of Theorem 4.1

Preliminary. Recall that , and counts the number of observations of item i up to the t-th step. The worst case is that the algorithm eliminates in order, and the algorithm eliminates at most 1 item at one time step. Besides, the design of Algorithm 1 implies that

In the following discussion,we assume (discussion on is in Appendix C). Note that Lemma 5.7 implies that . Besides, we write for simplicity.

Bound the number of observations per phrase. Observe that there are less than K surviving items remaining in the survival set at some steps before the algorithm terminates, we separate the steps into several phrases:

(i) During the first phrase, the agent eliminates items within steps. According to Lemma 5.8 and Line (D.3),

Then the total number of observations of surviving items in within this phrase can be bounded as follows:

(ii) During the k-th phrase for any , the agent eliminates the -th item within steps. Again apply Lemma 5.8 and Line (D.3):

Then the total number of observations of surviving items in within this phrase can also be bounded:

Bound the number of time steps per phrase. Recall that the k-th () phrase consist of time steps. Let be the total number of observations within the steps. Lemma 5.6 indicates that

Then according to Lemma 5.6, for any , with probability at least

Bound the time complexity. Altogether, we would have as the time complexity. Besides, we bound the total error incurred by partial observation by . In other words,

Depending on the value of , there are two cases:

For brevity, we only go through the remaining analysis for the first case, the analysis for the second one is similar.

Since the second term in the bound on T merely depends on the problem, we turn to analyze the first term. Since the first term holds for any values of ’s such that , we minimize the first term with the method of Lagrange

Let

then for all

attains its maximum when

Now we bound individually.

Bounding : note that

Bounding when is increasing on (0, e), is decreasing on and attains its global maximum at x = e. Hence,

Bounding : We first rewrite this term according to the definition of

Next, since as shown in Lemma 5.2, when

and

Further,

Summation of

The time complexity is upper bounded by

where

D.17. Proof of Theorem 4.8

Recall that is a vector in , where represents observing no click, observing a click and no observation respectively. For example, when and , items 2, 1, 5, 4 are listed in the displayed order; items 2, 1 are not clicked, item 5 is clicked, and the response to item 4 is not observed. By the definition of the cascading model, the outcome is in general a (possibly emtpy) string of 0s, followed by a 1 (if the realized reward is 1), and then followed by a possibly empty string of s. Clearly, are random variables with distribution depending on (hence these random variables distribute differently for different , albeit a possibly complicated dependence on

With the analysis in Section 5.3, according to Lemma 5.11 and the definition of the instance , one obtains for or respectively,

Let denote the number of observations of items at time step t. By revisiting the definition of in Section 4.1, we see that actually counts the observation of all pulled items at time step and summing over the items yields a bound on the expected number of total observations . Meanwhile, an upper bound of as stated in Lemma 5.2 and tower property indicates that

Note that , we complete the proof of Theorem 4.8.

D.18. Proof of Proposition C.1

Proposition C.1. Assume . With probability at least , Algorithm 1 outputs an -optimal arm after at most steps where

Proof. Consider . According to Lemma 5.9, there are at least in the survival set before the algorithm terminates, so the algorithm pulls K items from the surviving set at each time step. And for simplicity, we again write

Recall Lemma 5.6, we set . Then the total number of observations during steps should be larger than with probability at least . And since the number of observations can

be upper bounded, we consider

Lastly, with Lemma 5.6, 5.7 and 5.8, we obtain that with probability at least , Algorithm 1 stops after at most

steps.

E.1. Order of pulled items

Figure E.1: Average time complexity incurred by different sorting order of : ascending order of (Algorithm 1), ascending/descending order of in the cascading bandits.

After a large amount of observations, it is likely that the empirical mean approaches the true weight w(i), and w(i) lies between the confidence bounds with high probability. Therefore, one may consider to sort descending or ascending order of ’s (the difference to Algorithm 1 reveals in Line 5–9). Diving into the numerical results, we found an algorithm always manages to find an -optimal arm provided that it is not terminated by the limit of steps. Hence, we focus on the comparison of averaged stopping time.

In Figure E.1, we can see that sorting in the ascending order of or , especially the latter one, incurs an apparently larger averaged stopping time than other methods in most cases. Next, the descending order of does not work well in some cases. Thirdly, the ascending order of performs almost the same as our algorithm in most cases but there are several cases where it performs much worse and does not terminate even after iterations. Lastly, the descending order of works almost as well as Algorithm 1 empirically but is in lack of theoretical guarantee on time complexity. Meanwhile, the standard deviation of the stopping time of our algorithm is negligible comparing to the average value. For instance, in the left-most case of Figure 6.1, the standard deviation is about 22318.54 when the average is about 754140.65.

E.2. Further empirical evidence

Table E.1: Fitted results of upper bounds on the stopping time T of Algorithm 1 with (Proposition 4.6).

As shown in Table E.1, p-value is the probability that we reject the assumption of our fitting model versus a constant model (Glantz et al., 1990). Hence, the small p-values indicates that our fitting models are reasonable. Next, all ’s are positive, implying all averaged stopping time grows with K, which corroborates our theoretical results.

Figure E.2: Fit the averaged stopping time with functions of K for each case in order. Fix . Blue dots are the averaged stopping time, red line is the fitted curve, and cyan dashed lines show the 95% confidence interval.