Bandits with Ranking Feedback

Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 17:08:53

Abstract: In this paper, we introduce a novel variation of multi-armed bandits called bandits with ranking feedback. Unlike traditional bandits, this variation provides feedback to the learner that allows them to rank the arms based on previous pulls, without quantifying numerically the difference in performance.  This type of feedback is well-suited for scenarios where the arms' values cannot be precisely measured using metrics such as monetary scores, probabilities, or occurrences. Common examples include  human preferences in matchmaking problems. Furthermore, its investigation answers the theoretical question on how numerical rewards are crucial in bandit settings. In particular, we study the problem of designing no-regret algorithms with ranking feedback both in the stochastic and adversarial settings. We show that, with stochastic rewards, differently from what happens with non-ranking feedback, no algorithm can suffer a logarithmic regret in the time horizon $T$ in the instance-dependent case. Furthermore, we provide two algorithms. The first, namely DREE, guarantees a superlogarithmic regret in $T$ in the instance-dependent case thus matching our lower bound, while the second, namely R-LPE, guarantees a regret of $\mathcal{\widetilde O}(\sqrt{T})$ in the instance-independent case. Remarkably, we show that no algorithm can have an optimal regret bound in both instance-dependent and instance-independent cases. Finally, we prove that no algorithm can achieve a sublinear regret when the rewards are adversarial.

Main paper: 
 introduction: 
 Multi-armed bandits are well-known sequential decision-making problems where a learner is given a number of arms whose reward is unknown (Lattimore & Szepesvari, 2017) . At every round, the learner can pull an arm and observe a realization of the reward associated with that arm, which can be generated stochastically (Auer et al., 2002) or adversarially (Auer et al., 1995) . The central question in multi-armed bandits concerns how to address the exploration/exploitation tradeoff to minimize the regret between the reward provided by the learning policy and the optimal clairvoyant algorithm. Interestingly, multi-armed bandits come with several flavors capturing a wide range of different applications, e.g., with delayed feedback (Vernade et al., 2017; 2020 ), combinatorial constraints (Combes et al., 2015)) , and a continuous set of arms (Kleinberg et al., 2019) .In this paper, we introduce a novel variation of multi-armed bandits that, to the best of our knowledge, is unexplored so far. We name the model as bandits with ranking feedback. This feedback provides the learner with a partial observation over the rewards given by the arms. More precisely, the learner can rank the arms based on the previous pulls they experienced, but they cannot quantify numerically the difference in performance. Thus, the learner is not allowed to asses how much an arm is better or worse than another. This type of feedback is well-suited for scenarios where the arms' values cannot be precisely measured using metrics such as monetary scores, probabilities, or occurrences, and naturally applies to various settings, e.g., when dealing with human preferences such as in matchmaking settings among humans and when the scores cannot be revealed for privacy or security reasons. This latter case can be found, e.g., in online advertising platforms offering automatic bidding services as they have no information on the actual revenue of the advertising campaigns since the advertisers prefer not to reveal these values being sensible data for the companies. 1 Remarkably, our model poses the interesting theoretical question whether the lack of numerical scores precludes the design of sublinear regret algorithms or worsens the regret bounds that are achievable when numerical scores are available.Related Works. The field most related to bandits with ranking is preference learning, which aims at learning the preferences of one or more agents from some observations (Fürnkranz & Hüllermeier, 2010) . Let us remark that preference learning has recently gained a lot of attention from the scientific community, as it enables the design of AI artifacts capable of interacting with human-in-the-loop (HTL) environments. Indeed, human feedback may be quite misleading when it is asked to report numerical values, while humans are far more effective at reporting ranking preferences. The preference learning literature mainly focuses on two kinds of preference observations: pairwise preferences and ranking. In the first case, the data observed by the learner involves preferences between two objects, i.e., a partial preference is given to the learner. In the latter, a complete ranking of the available data is given as feedback. Our work belongs to the latter branch. Preference learning has been widely investigated by the online learning community, see, e.g., (Bengs et al., 2018) .Precisely, our work presents several similarities with the dueling bandits settings (Yue et al., 2012; Saha & Gaillard, 2022; Lekang & Lamperski, 2019) , where, in each round, the learner pulls two arms and observes a ranking over them. Nevertheless, although dueling bandits share similarities to our setting, they present substantial differences. Specifically, in our model, the learner observes a ranking depending on the arms they have pulled so far. In dueling bandits, the learner observes an instantaneous comparison between the arms they have just pulled; thus, the outcome of such a comparison does not depend on the arms previously selected, as is the case of bandits with ranking feedback. As a consequence, while in bandits with ranking feedback the goal of the learner is to exploit the arm with the highest mean, in dueling bandits the goal of the learner is to select the arm winning with the highest probability. Furthermore, while we adopt the classical notion of regret used in the bandit literature to assess the theoretical properties of our algorithms, in dueling bandits, the algorithms are often evaluated with a suitable notion of regret, which differs from the classical one.Dueling bandits have their reinforcement learning (RL) counterpart in the preference-based reinforcement learning (PbRL), see, e.g., (Novoseller et al., 2019) and (Wirth et al., 2017) . Interestingly, PbRL techniques differ from the standard RL approaches in that they allow an algorithm to learn from non-numerical rewards; this is particularly useful when the environment encompasses human-like entities (Chen et al., 2022) . Furthermore, PbRL provides a bundle of results, ranging from theory (Xu et al., 2020) to practice (Christiano et al., 2017; Lee et al., 2021) . In PbRL, preferences may concern both states and actions; contrariwise, our framework is stateless since the rewards gained depend only on the action taken during the learning dynamic. Moreover, the differences outlined between dueling bandits and bandits with ranking feedback still hold for preference-based reinforcement learning, as preferences are considered between observations instead of the empirical mean of the accumulated rewards.Original Contributions. We investigate the problem of designing no-regret algorithms for bandits with ranking in both stochastic and adversarial settings. With stochastic rewards, we show that ranking feedback does not preclude sublinear regret. However, it worsens the upper bounds achievable by the algorithms. In particular, in the instance-dependent case, we show that no algorithm can suffer from a logarithmic regret in the time horizon (as instead is possible in the non-ranking case), and we provide an algorithm, namely DREE (Dynamical Ranking Exploration-Exploitation), guaranteeing superlogarithmic regret that matches the lower bound. In the instance-independent case, a crucial question is whether there is an algorithm providing a regret bound better than the well-known Explore-then-Commit algorithm which trivially guarantees a regret of Õ(T 2/3 ) in our case. We design an algorithm, namely R-LPE (Ranking Logarithmic Phased Elimination), which guarantees a regret of Õ( √ T ) in the instance-independent case. More importantly, we show that no algorithm can have an optimal regret bound in both instance-dependent and instance-independent cases. Furthermore, with adversarial rewards, we show that ranking feedback precludes sublinear regret, and therefore numerical rewards are strictly necessary in adversarial online learning settings. Finally, we numerically evaluate our DREE and R-LPE algorithms in a testbed, and we compare their performance with some baseline from the literature in different settings. We show that our algorithms dramatically outperform the baselines in terms of empirical regret. 
problem formulation: 
 In this section, we formally state the model of bandits with ranking feedback and discuss the learnerenvironment interaction. Subsequently, we define policies and the regret notion both in the stochastic and in the adversarial settings.Setting and Interaction. Differently from standard bandits-see, e.g., the work by (Lattimore & Szepesvari, 2017) -in which the learner observes the reward associated with the pulled arm, in bandits with ranking feedback the learner can only observe a ranking over the arms based on the previous pulls. Formally, we assume the learner-environment interaction to unfold as follows.2 (i) At every round t ∈ [T ], where T is the time horizon, the learner chooses an arm i t ∈ A :=[n], where A is the set of available arms and n = |A| < +∞.(ii) We study both stochastic and adversarial rewards. In the stochastic setting, the environment draws the reward r t (i t ) associated with arm i t from a probability distribution ν it , i.e., r t (i t ) ∼ ν it , whereas, in the adversarial setting, r t (i t ) is chosen adversarially by an opponent from a bounded set of reward functions. (iii) There is a bandit feedback on the reward of the arm i t ∈ A pulled at round t leading to the estimate of the empirical mean of i t as follows:rt (i) := j∈Wt(i) r j (i) Z i (t) , where W t (i) := {τ ∈ [t] | i τ = i} and Z i (t) := |W t (i)|.3 However, the learner observes the rank over the empirical means {r t (i)} i∈A We denote with S A the set containing all the possible permutations of the elements of set A. Formally, we assume that the ranking R t ∈ S A observed by the learner at round t is such that:rt (R t,i ) ≥ rt (R t,j ) ∀t ∈ [T ] ∀i, j ∈ [n] s.t. i ≥ j,where R t,i ∈ A denotes the i-th element in the ranking R t at round t ∈ [T ].For the sake of clarity, we provide an example to illustrate bandits with ranking feedback and the corresponding learner-environment interaction.Example. We consider an environment with two arms, i.e., A = {1, 2}, in which the learner plays the first action at rounds t = 1 and t = 3 and the second action at round t = 2, so that W 3 (1) = {1, 3} and W 3 (2) = {2}. Let r 1 (1) = 1 and r 3 (1) = 5 be the rewards when playing the first arm at rounds t = 1 and t = 3, respectively, while let r 2 (2) = 5 be the reward when playing the second arm at round t = 2. The empirical means of the two arms and resulting rankings at every round t ∈ [3] are given by:   rt (1) = 1, rt (2) = 0 R t = ⟨1, 2⟩ t = 1 rt (1) = 1, rt (2) = 5 R t = ⟨2, 1⟩ t = 2 rt (1) = 3, rt (2) = 5 R t = ⟨2, 1⟩ t = 3.Policies and Regret. At every round t, the action played by the learner is prescribed by a policy π. In both the stochastic and adversarial settings, we let the policy π be a randomized map from the history of the interactionH t-1 = (R 1 , i 1 , R 2 , i 2 , . . . R t-1 , i t-1) to the set of all the probability distributions with support A. Formally, we let π :H t-1 → ∆ (A), for t ∈ [T ], such that i t ∼ π(H t-1). As it is customary in bandits, the learner's goal is to design a policy π minimizing the cumulative expected regret, whose formal definition is as follows:R T (π) = E T t=1 r t (i * ) -r t (i t ) ,where the expectation is over the randomness of both the policy and environment in the stochastic setting, and we let i * ∈ arg max i∈A µ i with µ i = E [ν i ], whereas the expectation is over the randomness of the policy in the adversarial setting and we let i * ∈ arg max i∈A T t=1 r t (i). For the sake of simplicity, from here on, we omit the dependence on π, referring to R T (π) as R T . The impossibility of observing the reward realizations raises several technical difficulties when designing no-regret algorithms since the approaches adopted for standard (non-ranking) bandits do not generalize to our case. In the following sections, we discuss how the lack of this information degrades the performance of the algorithms when the feedback is ranking. 
analysis in the stochastic setting: 
 Initially, we observe that approaches based on optimism-vs.-uncertainty, such as UCB1, might be challenging to apply within our framework. This is because the learner lacks the information to estimate the reward associated with an arm, making it difficult to infer a confidence bound. Therefore, the most popular class of algorithms one can employ in bandits with ranking feedback is that of explore-then-commit (EC) algorithms, where the learner either exploits a single arm or explores the others according to a deterministic or randomized exploration strategy.In the following, we distinguish the instance-dependent case from the instance-independent one. In particular, we provide two algorithms, each guaranteeing a sublinear regret in one of the two cases.It is well-known that standard bandits admit algorithms guaranteeing a regret that is logarithmic in time horizon T in the instance-dependent case. We show in this section that such a result does not hold when the feedback is provided as a ranking. More precisely, our result rules out the possibility of having a logarithmic regret. However, in the next section, we prove that we can get a regret whose dependence on T is arbitrarily close to a logarithm, thus showing that the extra cost one has to pay in the instance-dependent case to deal with ranking feedback is asymptotically negligible in T .Our impossibility result exploits a connection between random walks and arms' cumulative rewards. Formally, we define an (asymmetric) random walk as follows. Definition 1. A random walk is a stochastic process {G t } t∈N such that:G t = 0 t = 1 G t-1 + ϵ t t > 1 ,where {ϵ t } t∈N is an i.i.d. sequence of random variables, and E[ϵ t ] is the drift of the random walk.We model the cumulative reward collected by a specific arm during the learning process as a random walk, where the drift represents the expected reward associated with that arm. Let us notice that, in bandits where the feedback is not given as a ranking, the learner can completely observe the evolution of the random walks, being able to observe the realizations of the reward associated with each pulled arm. Such observations allow the learner to estimate the difference between the performance of each pair of arms. For instance, the learner can observe whether two arms perform similarly or, instead, whether the gap between their performances is significant. Differently, in our case, the learner only observes the rank without quantify numerically the performance.This loss of information raises several technical issues that are crucial, especially when the random walks never switch. Intuitively, in bandits with ranking feedback, we can observe how close the expected rewards of two arms are only by observing subsequent switches of their positions in the ranking. However, there is a strictly positive probability that two random walks never switch (thus leading to no intersection) when they have a different drift E[ϵ t ] and therefore we may not evaluate how two arms are close. This is shown in the following lemma.Lemma 1 (Separation lemma). Let G t , G ′ t be two independent random walks defined as:G t+1 = G t + ϵ t and G ′ t+1 = G ′ t + ϵ ′ t , where G 0 = G ′ 0 = 0 and the drifts satisfy E[ϵ t ] = p > q = E[ϵ ′ t ],. Then:P ∀t, t ′ ∈ N * G t /t ≥ G ′ t ′ /t ′ > 0.The rationale of the above lemma is that, given two random walks with different drifts, there is a line separating them with a strictly positive probability. Therefore, with a non-negligible probability, the empirical mean corresponding to the process with the higher drift upper bounds forever the empirical mean of the process with the lower drift. In bandits with ranking feedback, such a separation lemma shows that the problem of distinguishing two different instances is harder than in the standard, non-ranking feedback case. Before stating our result, as is customary in bandit literature, let us denote with ∆ i := µ * iµ i , where we let i * ∈ arg max i∈A µ i and µ i := E [ν i ]. Now, we can state the following result for the instance-dependent case.Theorem 1 (Instance-dependent lower bound). Let π be any policy for the bandits with ranking feedback, then, for anyC(•) : [0, +∞) → [0, +∞), there is {∆ i } i∈[n] and a time horizon T > 0 such that R T > n i=1 C(∆ i ) log(T ).Proof sketch. It is well-known in the bandit literature that, to achieve logarithmic regret, it is necessary to pull any suboptimal arm at least ∼ log(T ) ∆ 2 i times. The values of ∆ i cannot be estimated without a switch in the ranking. Since even when ∆ i s are very small, the optimal arm may remain in the first position for the whole process, ∆ i cannot be estimated, and it is necessary to pull the suboptimal arms more than O(log(T )) times.We introduce the Dynamical Ranking Exploration-Exploitation algorithm (DREE). The pseudo-code is provided in Algorithm 1. As usual in bandit algorithms, in the first n rounds, a pull for each arm is performed (Lines 2-4). At every subsequent round t > n, the exploitation/exploration tradeoff is addressed by playing the best arm according to the received feedback unless there is at least one arm whose number of pulls at t is smaller than a superlogarithmic function f (t) : (0, ∞) → R + . 4 More precisely, the algorithm plays an arm i at round t if it has been pulled less than f (t) times (Lines 5-6), where ties due to multiple arms pulled less than f (t) times are broken arbitrarily. Instead, if all arms have been pulled at least f (t) times, the arm in the highest position of the last ranking feedback is pulled (Lines 7-9). Each round ends once the learner receives the feedback in terms of ranking over the arms (Line 10). Let us observe that the exploration strategy of Algorithm 1 is deterministic, and the only source of randomness concerns the realization of the arms' rewards.Algorithm 1 Dynamical Ranking Exploration-Exploitation (DREE)1: for t ∈ [T ] do 2: if t ≤ n then 3: play arm i t 4: end if 5:if There is an arm i played less than f (t) times then 6:Play i t = i 7: else 8: Play i t = R t-1,1 9: end if 10:Receive updated ranking R t 11: end for We state the following result, providing the upper regret bound of Algorithm 1 as a function of f . Theorem 2 (Instance-dependent upper bound). Assume that the reward distribution of every arm is 1-subgaussian. Let f : (0, ∞) → R be a superlogarithmic function in t, then there is a term C(f, ∆ i ) for each sub-optimal arm i ∈ [n] which does not depend on T , such that Algorithm 1 satisfies:R T ≤ f (T ) n i=1 ∆ i + log(T ) n i=1 C(f, ∆ i ).To minimize the asymptotic dependence in T of the cumulative regret suffered by the algorithm, we can choose, e.g., f : (0, ∞) → R as f (t) = log(t) 1+δ , where parameter δ > 0 is as small as possible. However, the minimization of δ comes at the cost of increasing the terms C(f, ∆ i ) as they grow exponentially as δ > 0 goes to zero as long as ∆ i < 1. In particular, the terms C(f, ∆ i ) are defined as stated in the following corollary. Corollary 3. Let δ > 0 and f (t) = log(t) 1+δ be the sperlogarithmic function used in Algorithm 1, then we have:C(f, ∆ i ) = 2∆ i e (2/∆ 2 i ) 1/δ + 1 1 -e -∆ 2 i /2We remark that the term C(f, ∆ i ) depends exponentially on ∆ i , suggesting that C(f, ∆ i ) may be large even when adopting values of δ that are not arbitrarily close to zero.Furthermore, let us observe that Algorithm 1 satisfies important properties in the instance-dependent stochastic setting. More precisely, (i) it matches the instance-dependent regret lower-bound, since f (•) can be chosen arbitrarily close to log(t), (ii) it works without requiring the knowledge of the time horizon T , thus being an any-time algorithm.In this section, we provide a negative result, showing that no algorithm can perform well in both the instance-dependent and instance-independent cases, thus suggesting that the two cases need to be studied separately. Initially, we state the following result that relates to the upper regret bounds in the two (instance-dependent/independent) cases.Theorem 4 (Instance Dependent/Independent Trade-off). Let π be any policy for the bandits with ranking feedback problem. If π satisfies the following properties:• (instance-dependent upper regret bound) R T ≤ n i=1 C(∆ i )T α• (instance-independent upper regret bound) R T ≤ nCT β then, 2α + β ≥ 1, where α, β ≥ 0.From Theorem 4, we can easily infer the following impossibility result. Corollary 5. There is no algorithm for bandits with ranking feedback achieving both subpolynomial regret in the instance-dependent case, i.e., ∀α > 0, ∃C(•) : R T ≤ n i=1 C(∆ i )T α , and sublinear regret in the instance-independent case.To ease the interpretation of Corollary 5, we discuss the performance of Algorithm 1 in the instanceindependent case in the following result. Corollary 6. For every choice of δ > 0 in f (t) = log(t) 1+δ , there is no value of η > 0 for which Algorithm 1 achieves an instance-independent regret bound of the form R T ≤ O(T 1-η ).The above result shows that Algorithm 1 suffers from linear regret in T in the instance-independent case except for logarithmic terms.The impossibility result stated by Corollary 5 pushes for the need for an algorithm guaranteeing a sublinear regret in the instance-independent case. Initially, we observe that the standard Explore-then-Commit algorithm (from here on denoted with EC) proposed by Lattimore & Szepesvari (2017) can be applied, achieving a regret bound O(T 2/3 ) in the instance-independent case.Let us briefly summarize the functioning of the EC algorithm. It divides the time horizon into two phases as follows: (i) exploration phase: the arms are pulled uniformly for the first m • n rounds, where m is a parameter of the algorithm one can tune to minimize the regret; (ii) commitment phase: the arm maximizing the estimated reward is pulled.In the case of bandits with ranking feedback, the EC algorithm explores the arms in the first m • n rounds and subsequently pulls the arm in the first position of the ranking feedback received at round t = m • n. As is customary in standard (non-ranking) bandits, the best regret bound can be achieved by setting m = ⌈T 2/3 ⌉, thus obtaining O(T 2/3 ).We show that we can get a regret bound better than that of the EC algorithm. In particular, we provide the Ranking Logarithmic Phased Elimination (R-PLE) algorithm, which breaks the barrier of O(T 2/3 ) guaranteeing a regret O( √ T ) when neglecting logarithmic terms. The pseudocode of R-PLE is reported in Algorithm 2. R-LPE Algorithm. In order to proper analyze the algorithm, we need to introduce the two following definitions. Initially, we introduce the definition of the loggrid set as follows, Definition 2 (Loggrid). Given two real numbers a, b s.t a < b and a constant value T , we defineLG(a, b, T ) := ⌊T λj b+(1-λj )a ⌋ : λ j = j ⌊log(T )⌋, ∀j = 0, . . . , ⌊log(T )⌋ .Next, we give the notion of active set, which the algorithm employs to cancel out sub-optimal arms.Definition 3 (Active set). We define the active set F t (ζ) at the timestep t of the algorithm, the set of armsF t (ζ) :=    a ∈ A : ∀b ∈ A t τ =1:n|τ {R τ (a) > R τ (b)} ≥ ζ    .Where the symbol | stands for "divide", so that the condition τ |n means that we are summing only over the τ which are multiple of n. This condition will be called filtering condition.Algorithm 2 Ranking Logarithmic Phased Elimination (R-LPE)1: Initialize S = [n] 2: Initialize L = LG(1/2, 1, T ) 3: for t ∈ [T ] do 4: Play i t ∈ arg min i∈S Z i (t) 5:Update Z i (t) number of times i t has been pulled 6:Observe ranking R t 7:if min i∈S Z i (t) ∈ L then 8: α = log(min i∈S Zi(t)) log(T ) -1 2 9: S = F t (T 2α ) 10:end if 11: end for Initially, we observe that R-LPE differs from Algorithm 1, as it takes into account the whole history of the process and not only the last ranking R t received. It also requires the knowledge of T .Set S denotes the active set of arms used by the algorithm. Initially, set S comprises all the possible arms available in the problem (Line 1). Furthermore, the set which drives the update of the decision space S, namely L, is initialized as the loggrid built on parameters 1/2, 1, T (Line 2).At every round t ∈ [T ], R-LPE chooses the arm from active set S with the minimum number of pulls, namely i s.t. Z i (t) is minimized (Line 4); ties are broken by index order. Next, the number of times arm i t has been pulled, namely Z i (t), is updated accordingly (Line 5). The peculiarity of the algorithm is that set S changes every time the condition min i Z i (t) ∈ L is satisfied (Line 7). When the aforementioned condition is met, the set of active arms S is filtered to avoid the exploration on sub-optimal arms. Precisely, S is filtered given the time dependent parameter α (Line 8-9).Regret Bound. We state the following theorem providing a regret bound to Algorithm 2 in the instance-independent case. Theorem 7. In the stochastic bandits with ranking feedback setting, Algorithm 2 achieves the following regret bound:R T ≤ O n √ T ,when n arms are available to the learner.At first glance, the result presented in Theorem 7 may seem unsurprising. Indeed, there are several elimination algorithms achieving O( √ T ) regret bounds in different bandit settings (see, for example, (Auer & Ortner, 2010; Lattimore et al., 2020; Li & Scarlett, 2022) ). Nevertheless, our setting poses several additional challenges compared to existing ones. For instance, in our framework, it is not possible to rely on concentration bounds, as the current feedback is heavily correlated with the past ones. For such a reason, our analysis employs non-trivial arguments, drawing from recent results in the theory of Brownian Motions, which allow to properly model the particular feedback we propose. 
analysis in the adversarial setting: 
 We focus on bandits with ranking feedback in adversarial settings. In particular, we show that no algorithm provides sublinear regret without statistical assumptions on the rewards. Theorem 8. In adversarial bandits with ranking feedback, no algorithm achieves o(T ) regret with respect to the best arm in hindsight with a probability of 1ϵ for any ϵ > 0.Proof sketch. The proof introduces three instances in an adversarial setting in a way that no algorithm can achieve sublinear regret in all the three. The main reason behind such a negative result is that ranking feedback obfuscates the value of the rewards so as not to allow the algorithm to distinguish two or more instances where the rewards are non-stationary. The three instances employed in the proof are divided into three phases such that the instances are similar in terms of rewards for the first two phases, while they are extremely different in the third phase. In summary, if the learner receives the same ranking when playing in two instances with different best arms in hindsight, it is not possible to achieve a small regret in both of them. 
numerical evaluation: 
 This section presents a numerical evaluation of the algorithms proposed in the paper for the stochastic settings, namely, DREE and R-LPE. The goal of such a study is to show two crucial results: firstly, the comparison of our algorithms with a well-known bandit baseline, and secondly, the need to develop distinct algorithms tailored for instance-dependent and instance-independent scenarios. To establish a benchmark for comparison, we consider the EC (Explore-Then-Commit) algorithm, which is one of the most popular algorithms among the explore-then-commit class providing sublinear regret guarantees. In the following, we evaluate the DREE algorithm with different choices of the δ parameter in the function f (t) = log(t) 1+δ ; precisely, we choose δ ∈ {1.0, 1.5, 2.0}. Furthermore, we consider four stochastic instances whose specific parameters are discussed below. In all these instances, we assume the rewards to be drawn from Gaussian random variables with unit variance, i.e., σ 2 = 1, and we let the time horizon be equal to T = 2 • 10 5 . Finally, for each algorithm, we evaluate the cumulative regret averaged over 50 runs.We structure the presentation of the experimental results into two groups. In the first, the instances have a small ∆ min , while in the second, the instances have a large ∆ min .Small Values of ∆ min We focus on two instances with ∆ min < 0.05. In the first of these two instances, we consider n = 4 arms, and a minimum gap of ∆ min = 0.03. In the second instance, we consider n = 6 arms, with ∆ min = 0.03. The expected values of the rewards of each arm are reported in Appendix D, while the experimental results in terms of average cumulative regret are reported in Figures 1a-1b . We observe that in the first instance (see Figure 1a ) all the DREE algorithms exhibits a linear regret bound, confirming the strong sensitivity of this family of algorithms on the parameter ∆ min in terms of regret bound. In contrast, the R-LPE algorithm exhibits better performances in terms of regret bound, as its theoretical guarantee are independent on the values of ∆ min . Furthermore, Figure 1b shows that the DREE algorithms (with δ ∈ 1.0, 1.5) achieve a better regret bound when the number of arms is increased. Indeed, these regret bounds are comparable to the ones achieved by the R-LPE algorithm. The previous result is reasonable as the presence of ∆ i -s in the regret bound lowers the dependence on the number of arms. It is worth noticing that all our algorithms outperform the baseline EC.Large Values of ∆ min We focus on two instances with ∆ min ≥ 0.25. In the first instance, we consider n = 4 arms with a minimum gap of ∆ min = 0.5 among their expected rewards. In the second instance, we instead consider a larger number of arms, specifically n = 8, with a minimum gap equal to ∆ min = 0.25. The expected values of the rewards are reported in Appendix D, while the experimental results in terms of average cumulative regret are provided in Figures 2a-2b . As it clear from both Figures 2a-2b when ∆ min is sufficiently large, the DREE algorithms (with δ ∈ {1.0, 1.5}) achieves better performances with respect both the EC and R-PLE algorithms in terms of cumulative regret. Furthermore, there is empirical evidence that a small δ guarantees better performance, which is reasonable according to theory. Indeed, when δ is small, the function f (t), which drives the exploration, is closer to a logarithm. Also, as shown in Corollary 3, when ∆ min is large enough, the parameter δ affects the dimension of C(f, ∆ i ) more weakly, which results in a better regret bound.Notice that a platform can observe the number of clicks received by an advertising campaign, but it cannot observe the revenue associated with that campaign.Given n ∈ N>0 we denote with [n] := {1, . . . , n}.Note that the latter definition is well-posed as long as |Wt(i)| > 0. For each i ∈ A and t ∈ [T ] such that |Wt(i)| = 0, we let rt(i) = 0.A function f (t) is superlogarithmic when lim t→∞ f (t) log(t) = +∞. 
 
 Appendix:  


Decision: The reviewers overall favor the paper's contributions, among which are the introduction of a bandit model with a new form of rank-ordered feedback, and a comprehensive study of attainable performance in this model. I must add, however, that there were also concerns raised almost unanimously about the practical relevance of this setting in modeling applications. The author(s) responded to this by providing a setting involving pay per click online advertising optimization where an agent must optimize for ad displays without knowing (potentially sensitive and private) revenue information per ad. This appears to have been satisfactorily accepted as a motivating example by the reviewers. Noting that the study of this new model can hold potential and inform decision making algorithms for future purposes, I recommend acceptance of the paper.

Reviews: review: paper_summary: paper_summary: This paper considers a new multi-armed bandit problem where the feedbacks are ranking of the arms. In this problem, the environment gives the feedback on the ranking of the arms based on the previous pulls. The authors first consider the stochastic setting and give the lower bound of the regret for the instance-dependent case. Then, they propose a design of explore-then-commit, called DREE, which is proved to achieve a sublunar regret for instance-dependent case. After discussing the regret tradeoff between instance-dependent and  instance-independent cases, the authors design a phase elimination algorithm (R-LPE) that has a sublunar regret. Then they move beyond the stochastic setting and prove that sub-linear regret cannot be achieved for the adversarial setting.
strength_weakness: strength_weakness: I am concerned about the following aspects.
First, in the problem setting, the ranking feedback is assumed to be perfect in terms of the ranking of the averaged history rewards. However, human probably not give the perfect ranking since history reward is not easily observed. Thus, it would be better if the authors can discuss the designs with imperfect ranking feedback.
Second, the analysis in the adversarial setting does not give any insight. It is obvious that the regret is linear for adversarial bandits with ranking feedback. However, can the authors discuss whether their algorithms are robust enough for adversarial setting? (e.g. provide an analysis of the competitive ratio.)
questions: questions: Can the authors give more concrete examples to motivate the setting of bandits with ranking feedbacks?
Can the authors provide a high-level explanation on why there exists a tradeoff between instance-dependent and instance-independent cases?
limitations: limitations: The authors do not include a discussion of the limitations. However, a discussion on the limitations of the setting will be helpful.
paper_summary: paper_summary: The paper introduces a variant of the multi-armed bandit problem called "bandits with ranking feedback," where the feedback ranks the arms based on historical data without showing precise numerical differences. This approach is particularly useful in scenarios where exact measurement of values is impractical, such as with human preferences or confidential data. The main contributions of the study include developing no-regret algorithms that operate under both stochastic and adversarial conditions for this model. The findings indicate that achieving logarithmic regret is impossible with ranking feedback in the stochastic setting, and no algorithm can achieve sublinear regret in the adversarial setting. The paper proposes two algorithms: DREE, which achieves superlogarithmic regret in stochastic instances, and R-LPE, which manages a regret of O(\sqrt{T})in stochastic instance-independent scenarios. These innovations significantly enhance the understanding and implementation of bandit algorithms in complex feedback environments.
strength_weakness: strength_weakness: 1) Originality: Is the concept of "bandits with ranking feedback" truly novel?
2) Experimental Validation: The paper would benefit from more experimental validation. While the theoretical aspects are well-developed, further empirical testing in diverse conditions could strengthen the validation of the algorithms. Tests with non-Gaussian noise and in real-world settings would be particularly insightful.
3) Algorithm Complexity: The discussion on the computational complexity and practical scalability of the introduced algorithms is limited. More detailed analysis in this area could provide better insights into their applicability in real-world scenarios.
4) Adversarial Setting Analysis: It is mentioned that no algorithm can achieve sublinear regret in adversarial settings, but more detailed explanations or suggestions for alternative approaches to handle such conditions would be beneficial.
5) Impact of Dependence on Parameters: The algorithms appear to heavily rely on the correct setting of specific parameters, such as the time horizon T. Discussing the sensitivity of the algorithms to these parameters and providing strategies for effective parameter tuning would aid their practical application.
6) Extension to Other Models: Could the principles of ranking feedback be applied to other types of bandit problems, such as contextual bandits or those with structured action spaces? This extension could broaden the applicability of the research findings.
questions: questions: 1) Originality: Is the concept of "bandits with ranking feedback" truly novel?
2) Experimental Validation: The paper would benefit from more experimental validation. While the theoretical aspects are well-developed, further empirical testing in diverse conditions could strengthen the validation of the algorithms. Tests with non-Gaussian noise and in real-world settings would be particularly insightful.
3) Algorithm Complexity: The discussion on the computational complexity and practical scalability of the introduced algorithms is limited. More detailed analysis in this area could provide better insights into their applicability in real-world scenarios.
4) Adversarial Setting Analysis: It is mentioned that no algorithm can achieve sublinear regret in adversarial settings, but more detailed explanations or suggestions for alternative approaches to handle such conditions would be beneficial.
5) Impact of Dependence on Parameters: The algorithms appear to heavily rely on the correct setting of specific parameters, such as the time horizon T. Discussing the sensitivity of the algorithms to these parameters and providing strategies for effective parameter tuning would aid their practical application.
6) Extension to Other Models: Could the principles of ranking feedback be applied to other types of bandit problems, such as contextual bandits or those with structured action spaces? This extension could broaden the applicability of the research findings.
limitations: limitations: Experimental Scope: The authors could extend the experimental validation to include real-world datasets or scenarios to better demonstrate the practicality of the algorithms under different environmental conditions.
paper_summary: paper_summary: The paper studies the setting where, every time an arm is pulled, a principal gets to observe a reward, but the player only gets to observe the order that emerges from the accumulated rewards so far. The authors study both the adversarial and stochastic, and both the instance-dependent and instance-independent regrets. They provide tight results for all cases, with the only exception being the stochastic instance-independent case, where they provide tight bounds only for the Gaussian model.
strength_weakness: strength_weakness: - I miss some more realistic motivation for the model and some concrete applications. As I said, from a theoretical point of view, the model is very interesting, but when I tried myself, I could not come up with a clear application.

- For the general stochastic and instance-independent case, the only guarantee that is provided is that of the EC algorithm which can be easily applied in this setting

- R-LPE algorithm needs to know T
questions: questions: No questions
limitations: limitations: No limitations
paper_summary: paper_summary: The paper studies the multi-armed bandit problem when the learner only observes the ranking of the average cumulative reward of all the arms. This is a strictly worse information environment than the standard setting. The paper proposes algorithms that still attains the instance independent and dependent regret rates that match the stochastic multi-armed bandit. It also shows that no algorithms can do better in both the instance-dependent and -independent settings simultaneously.
strength_weakness: strength_weakness: - It is probably out of the scope of this paper. But the current dependence on $n$, the number of arms, is quite far from optimal ($n^4$) in the instance dependent case. I wonder if the authors have thought about better designs to obtain linear or sublinear dependence. Some discussion would be helpful.
questions: questions: - In the proof of Theorem 4, the policy doesn't seem to depend on $T$. For example, in line 534, the probability of $\pi(pull 2|E_\tau)$ is a function of $\tau$ only. My understanding that the algorithm is allowed to depend on $T$. Does the proof work for this case?
- I think the title misleads the readers. Ranking feedback sounds like receiving the order of the rewards in the current round. It is up to the authors, but a more informative title would help the paper.
limitations: limitations: NA

Comments: title: No further questions
comment: I have read the response. Thank you authors for answering my questions.
Thanks for the detailed response. I don't have further questions.
I would like to thank the authors for their answer and the clarifications. I do not have any further questions at this point. While I still do not find the motivating example very convincing, I will keep the score as it is.