Bandits with Ranking Feedback

Q: 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 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.

The fact that our instance-independent bound in Theorem 8 scales with $n^4$ is one of the most interesting open points of this paper. The reason for this unusual order may be found in the fact that the ranking setting prevents us from relying on standard concentration properties. Therefore, no "high-probability" estimates can be performed, and each time in the analysis we perform a "union bound" over the space of arms, this results in an additional $n$ factor in the regret bound. In contrast, when using a high-probability estimate, the same union bound would result in an additional $\log(n)$ term, which is negligible. Furthermore, given the ranking feedback setting, it appears natural that at least two union bounds over the space of arms must be performed in order to compare any possible pair of arms. Therefore, we believe that a super-linear dependence on $n$ in the instance-independent regret bound cannot be avoided, but we still conjecture that such dependence may be moved to lower order terms.

Q: 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|E)$ is a function of $\tau$ only. My understanding that the algorithm is allowed to depend on $T$. Does the proof work for this case?

The point made by the Reviewer is correct, and very subtle. In fact, the current lower bound only applies to any-time policies, independent of the time horizon. Fortunately, modifying the proof to generalize the result to the case where the policy can depend on $T$ is not difficult. We start the proof by contradiction, assuming that both $R_T(\pi_T)\le C(\Delta)T^\alpha \qquad R_T(\pi_T)\le T^\beta$

hold for any $T$, given a sequence of policies $\pi_T$. The "hard instances" are the same, both with two arms and small $\Delta$, and also the event $E_t$ is defined as in the paper. From the assumption, it follows that

$C(\Delta= 1)T^\alpha = C( 1)T^\alpha \ge \mathbb E[Z_2(T)|E_T],$

otherwise the sequence of policies would suffer regret more than $C( 1)T^\alpha$ in case arm one gives always $1$ and the other always $0$. From this equation, it is easy to complete the proof as usual.

In the original proof, the only step requiring the policy to be any-time was the limit $\forall \eta>0,\ \limsup_{t\to \infty}\frac{\sum_{\tau=1}^t \pi(\text{pull 2}|E_\tau)}{t^{\alpha+\eta}}=0,$

which is not necessary and can be easily avoided working by contradiction. We will put this improved proof in the final version of the paper, we remain at the Reviewer disposal in case they need further clarification on how to change this proof.

Q: 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.

We thank the Reviewer for the interesting observation. Nevertheless, we believe the feedback structure the Reviewer is describing is somewhat referred to as "Dueling bandits", or their generalization. Thus, we are open to any suggestion.

Q: 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.

We thank the Reviewer for the question. In the following, we provide a real-world example of a possible application of our setting. In pay-per-click online advertising (the total spent is of the order of several billion USD per year), large platforms optimize advertisers' campaigns. Specifically, these platforms observe the number of clicks of each single campaign, but to allocate the budget most effectively (using a knapsack-style approach), they need to know the revenue of the individual campaigns. Obviously, the platforms cannot observe the revenue, which is private information of the advertiser. On the other hand, advertisers do not want to communicate this private information to the platforms, and, for this reason, the platforms limit themselves to maximizing the number of clicks. However, this kind of optimization leads to very approximate solutions compared to considering the revenue as well. The use of bandits with ranking feedback in this context would circumvent this problem. In particular, advertisers would be asked for feedback on the ranking of advertising campaigns, avoiding the need to ask for revenue information.

Q: 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

We thank the Reviewer for the comment but we believe there is a potential misunderstanding on our results. Indeed, the R-LPE algorithm is specifically tailored for the instance independent case while it achieves a subotptimal instance dependent regret bound. Finally, please notice that R-LPE instance independent regret guarantees are far better than those of the standard Explore and Commit algorithm which are of the order $\mathcal{O}(T^{2/3})$.

Q: R-LPE algorithm needs to know $T$

The reviewer is correct. In our settings, due to the specific nature of the feedback, we cannot employ the well-known "doubling trick" to relax the knowledge of the time horizon $T$. We leave it as an interesting open problem to determine whether the requirements on the knowledge of time horizon $T$ can be relaxed. For what concerns the empirical validation, in the attached PDF we added an experiment measuring the impact of using a misspecified value for $T$.

Q: Originality: Is the concept of "bandits with ranking feedback" truly novel?

To the best of our knowledge, the "bandits with ranking feedback" model introduced in our paper represents a new bandit setting. Although our setting shares similarities with dueling bandits, the two settings are substantially different, as we discuss in the related works section in our paper.

Q: Experimental Validation.

Following the suggestion of the reviewer, we enriched our experimental evaluation, and the new results we obtained can be found in the attached PDF. In particular, we investigated the following:

• Non Gaussian noise. In the attached PDF, we ran the same experiments of the paper with uniformly distributed noise. We observe that this leads to similar results. However, the variance of the regret curves is slightly increased, but the mean remains nearly the same.

• Measuring the computational effort required by the algorithms. While the running time of DREE is clearly linear in $T$, the running time of R-LPE is less straightforward to compute. However, in the additional experiments, we empirically observed that the running time of the R-LPE algorithm is also linear in $T$.

• Robustness of R-LPE to misspecification of $T$. Even if the algorithm strongly relies on knowledge of the time horizon, we have shown that providing the algorithm with a time horizon larger than the actual one is not particularly harmful. On the other hand, as is usual in bandit algorithms, setting the time horizon $T'$ smaller than the actual time horizon $T$ results in linear growth of the regret after $T'$ rounds.

Q: Algorithm Complexity.

We thank the Reviewer for underlining this important aspect, which we did not mention in the paper due to space constraints. Both our algorithms are very computationally efficient. In the experiment, we have empirically demonstrated this fact, and we will show it theoretically in this rebuttal. Specifically, the DREE algorithm requires either pulling the first-ranked arm (in most rounds) or an arm in a lower position of the ranking according to a deterministic schedule. Therefore, it does not require computing confidence regions, resulting in a running time of just $\mathcal{O}(nT)$. The second algorithm, R-LPE, is more complex compared to DREE, as it requires updating a set of active arms $S$ at certain rounds. Fortunately, this set is only updated during the time steps that belong to the loggrid, and thus it is updated a logarithmic number of times. Therefore, even though there is a summation over $t$ in the definition of the set $S$, the computational complexity of R-LPE is not quadratic in $T$, but rather of order $\mathcal{O}(T+nT\log(T))$. The first term in the latter expression corresponds to the "usual" rounds, where we simply follow a round-robin strategy. The second term corresponds to the product of $\log(T)$ (the number of rounds in the loggrid), $T/n$ (the number of "fair" rounds), and $n^2$ (the number of possible comparisons between pairs of arms).

Q: Adversarial Setting Analysis.

We thank the Reviewer for the question.
On the results explanation. To derive our adversarial lower bound we considered three instances. The instances are similar in terms of rewards for the first two phases but differ significantly in the third one. Thus, we show that, if the learner receives the same ranking when playing in two instances with different best arms in hindsight, it is impossible to achieve low regret in both scenarios.

On possible alternative approaches. We agree with the reviewer that, to handle such cases, different metrics could be taken into consideration. For instance, it would be possible to study algorithms achieving sufficiently "good" competitive ratios, namely, those that are no-regret with respect to a large fraction of the optimum. We leave the aforementioned research directions as interesting future work.

Q: Impact of Dependence on Parameters.

The R-LPE algorithm requires knowledge of the time horizon $T$, while the DREE algorithm is an anytime algorithm. In the attached PDF we added an experiment measuring the empirical impact of using a misspecified value of the time horizon $T$. We would like to emphasize that the R-LPE algorithm has no additional hyper-parameters, since the quantities that characterize it, such as the loggrid and the parameter $\alpha$, can be computed as a function of $T$. Additionally, while the definition of $\alpha$ at Line 8 could be tuned experimentally, doing so may prevent us from achieving the desired regret guarantees of $\mathcal{O}(\sqrt{T})$, which is the primary goal of our paper.

Q: Extension to Other Models

Extending our results to settings where the action space is no longer discrete is highly non-trivial, as it would first require rethinking the concept of ranking feedback. However, if we consider linear (or possibly contextual) bandits with finitely many arms, it would be interesting to see if such a linear structure allows for a better dependence on the number of arms (possibly sublinear as in [1]) in the instance indepenednt regret bound. Nonetheless, it should be noted that, from a technical perspective, combining linear settings with ranking ones would require merging the argument based on optimal design for the least squares estimator [2] or self-normalized processes [3] with our bound, which is instead based on Levy's arcsin law.

[1] Tor Lattimore, Csaba Szepesvari, Gellert Weisz. Learning with Good Feature Representations in Bandits and in RL with a Generative Model.

[2] Kiefer and J. Wolfowitz. The equivalence of two extremum problems.

[3] Yasin Abbasi-yadkori, Dávid Pál, Csaba Szepesvári, Improved Algorithms for Linear Stochastic Bandits

Q: "First, in the problem setting, the ranking feedback is assumed to be perfect in terms of the ranking of the averaged history rewards. (...)"

We completely agree with the Reviewer that the introduction of imperfection/uncertainty/tolerance is of paramount importance as it would allow to capture better the actual human behavior, and this refinement is exactly the next step of our agenda. On the other side, no imperfection can be introduced before a complete study of the perfect model, and, as we show in our paper, the study of the exact model is not straightforward. Furthermore, we observe that introducing a perturbation in the ranking observed by the learner may hinder the possibility of designing a no-regret algorithm. Thus, exploring scenarios where the learner receives corrupted ranking feedback and still manages to design a no-regret algorithm is both a fascinating and challenging research direction. Nonetheless, it requires a different approach from the one presented in our work and is something we plan to investigate in the future.

Q: Second, the analysis in the adversarial setting does not give any insight. (...)

We believe that the impossibility result for the adversarial setting represents a first yet fundamental step toward a full understanding of the problem when the rewards are adversarially chosen. We are disappointed that the Reviewer found our result trivial, as it is uncommon in the online learning literature to achieve a positive result in the stochastic setting that cannot be extended to the adversarial setting. This feature is peculiar to the bandits with ranking feedback model, as even related settings, such as dueling bandits, do not exhibit this kind of impossibility result. Finally, we agree with the Reviewer that studying the competitive ratio of algorithms developed for adversarial settings is an interesting research direction, and we plan to pursue it in the future.

Q: 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?

We thank the Reviewer for the question. In the following, we provide a real-world example of a possible application of our setting. In pay-per-click online advertising (the total spent is of the order of several billion USD per year), large platforms optimize advertisers' campaigns. Specifically, these platforms observe the number of clicks of each single campaign, but to allocate the budget most effectively (using a knapsack-style approach), they need to know the revenue of the individual campaigns. Obviously, the platforms cannot observe the revenue, which is private information of the advertiser. On the other hand, advertisers do not want to communicate this private information to the platforms, and, for this reason, the platforms limit themselves to maximizing the number of clicks. However, this kind of optimization leads to very approximate solutions compared to considering the revenue as well. The use of bandits with ranking feedback in this context would circumvent this problem. In particular, advertisers would be asked for feedback on the ranking of advertising campaigns, avoiding the need to ask for revenue information.

Q: Can the authors provide a high-level explanation on why there exists a tradeoff between instance-dependent and instance-independent cases?

Usually, in multi-armed bandits, an instance-independent regret bound can be derived from an instance-dependent one. Indeed, if the instance-dependent regret bound depends on the suboptimality gaps as $R_T \propto {\log(T)}/{\Delta}$, it is possible to take the worst possible value of $\Delta$ and achieve the desired instance-independent regret bound. Unfortunately, in our case, the instance-dependent regret bound cannot be written in this form as a consequence of the feedback characterizing our setting. Indeed, we can only observe switches in the ranking, which do not reflect the actual differences in the expected rewards of the arms. Thus, the only way to “explore” in our setting is by pulling arms that could be highly sub-optimal. For this reason, achieving an asymptotic regret bound that is close to logarithmic requires exploiting the arm being ranked first several times, thus suffering a particularly unpleasant dependence on the suboptimality gaps $\Delta_i$ (see, for example, Corollary 3). Finally, we remark that the formalization of this reasoning is presented in Theorem 4 (Instance Dependent/Independent Trade-off).