Adversarial Attacks on Online Learning to Rank with Click Feedback

Summary

This paper presented a study of reward poisoning attacks on UCB bandit algorithms with binary feedback and applies the designed attack to the online-learning-to-rank (OLTR) problem. The binary reward structure poses unique challenges to reward poisoning attacks, since the attacker needs to ensure the perturbed reward is still binary. The authors proposed an attack algorithm that achieves that. Based on that, the paper studied reward poisoning attacks in OLTR. The attacker is limited to change the click feedback, which is required to be binary before and after attack. Two threat models are considered - in the position-based click feedback scenario, the authors proposed attack strategy targeting the PBM-UCB algorithm; and in the cascade-click model, attack strategy against CascadeUCB is proposed. Both achieve T-O(log T) target item selections with only O(log T) attack cost. The paper also designed a general attack strategy for arbitrary click models that achieve O(log T) sub-optimal item selections. Finally, the paper performed empirical evaluations of the attacks.

Strengths

(1). The paper first studied data poisoning attacks on ranking algorithms, which is timely topic following prior works that study reward poisoning attacks on multi-armed bandit. Although the idea behind the design of the attack algorithm is similar in nature, poisoning ranking algorithms poses unique challenges compared to bandits - the attack needs to ensure the poisoned reward is still binary. (2). The theoretical analysis of this paper is solid. First, an efficient attack targeting the UCB bandit algorithm is proposed, which guarantees that the poisoned reward is still binary. Then two theoretical results are presented to show that UCB-style ranking algorithms are susceptible to poisoning attacks in both position-click and cascade-click scenarios. Finally, the paper also provided a general attack for general click model ranking algorithms. (3). The paper performed extensive empirical evaluations of the proposed attack strategies. The results are convincing.

Weaknesses

(1). The assumption made in section 4.3 is hidden in Theorem 4 - the ranking algorithm needs to guarantee O(log T) sub-optimal item selections. This assumption is critical and should not be hidden inside the theorem. Instead, the authors should consider carefully defining the assumption. (2). The Theorem 4 is not intriguing enough. In particular, it needs to assume that the ranking algorithm guarantees O(log T) sub-optimal item selections. Is O(log T) critical? Can it be O(sqrt(T))? The problem is that O(log T) seems too specific. Instead, it makes more sense to assume the ranking algorithm is no-regret, i.e., it selects suboptimal items in o(T) rounds. In that case, does Theorem 4 still hold?

Questions

(1). Can the author make the assumption in Theorem 4 more prominent? (2). Is O(log T) sub-optimal item selections a critical assumption in Theorem 4? Can the authors extend the result to arbitrary no-regret ranking algorithms that guarantee o(T) suboptimal item selections?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

5: You are absolutely certain about your assessment. You are very familiar with the related work and checked the math/other details carefully.

Soundness

4 excellent

Presentation

4 excellent

Contribution

4 excellent

Limitations

Yes

Summary

The paper introduces adversarial attack on online learning to rank. The attacker aims to fool the online learning to rank algorithm to choose the target item. The paper studied three victim models: stochastic L-armed bandit, OLTR with position-based model and OLTR with cascade model. Authors proposed three attack algorithm respectively for three victim models and a general attack strategy to attack arbitrary OLTR algorithms without knowing the details of the algorithm. Their theoretical analysis and experimental results show that the proposed attack strategies can manipulates the learning agent into choosing the target attack item in linear time but incurring a sublinear cost.

Strengths

The paper studied adversarial attacks on online learning to rank with click feedback, which as far as I know is the first work in this field. The paper provides some theoretical guarantees on their proposed algorithms. The results show that the attack strategies can successfully attack OLTR algorithms with sublinear cost. The paper is well-written and well-organized. The attack strategy on the UCB algorithm clearly shows that the differences between this work and previous work about reward attack on bandits.

Weaknesses

Overall, the paper is well-written and has good technical content, but I have the following concerns: 1. An intuitive attack method is that the attacker first chooses an action (list) $a$ including the target items and sets the reward out of this list to 0. The authors name this as $Trivial_{k-1}$. The authors empirically compared the proposed methods with $Trivial_{k-1}$, which is good. However, $Trivial_{k-1}$ seems to keep the same cost scaling on time as the proposed attack strategies, which weakens the contribution of this work. 2. There is no lower bound about the attack cost and any information. Compared with $Trivial_{k-1}$, The proposed attack algorithms improve the attack cost by a constant ratio. How far is the proposed attack strategies to the optimal?

Questions

See in weakness 2.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

Yes.

Summary

This paper studies adversarial attack to online learning to rank, where a successful attack to an OLTR algorithm is such that a suboptimal item is recommended for linear in T times while with log T cost. This paper approaches this attack problem by studying attack to discrete MAB as warmup and then moves on to attack UCB based OLTR algorithms under position and cascade models. Lastly, it ends up with an attack strategy for general algorithms and click models, both theoretical and simulation results are provided to justify the attacks being successful.

Strengths

1. Adversarial attack to online learning to rank makes up the foundation for studying robust/trustworthy recommendation systems. I agree some research into this topic is a must-do. 2. This paper is well written and easy to read. It appears to have a thoughtful path to break down the OLTR attack problem in a few pieces and tackle it step by step, which is good. However, I doubt, which is also my major concern for this paper, that are some of the steps necessary to derive a successful attack? See details in weakness I list below.

Weaknesses

**Possibly overcomplicates the problem** There’s another work [1]https://arxiv.org/pdf/2305.19218.pdf on arxiv that seems to study the same problem as this paper. This paper retains novelty as these two can be considered as concurrent works according to the arxiv one’s submission date. But interestingly, [1] seems to have conflicted results from this paper: The major tension lies in this paper proposes to alter clicks of unwanted arms with a sophisticated probability (e.g. in Alg.5), while [1] simply set 1 to 0 when an unwanted arm has a click. Moreover, this paper tests in simulation a baseline attack Trivial_1, which is close to the attack proposed by [1] (except for [1] has a cutoff time for attack), and this paper claims Trivial_1 fails to attack according to the plot. And not surprisingly, theorem and simulation results in [1] supports their attack. So this finding casts some doubt on this paper whether it overcomplicates the problem, as the attack proposed in [1] is way simpler with no need to compute a sophisticated probability to attack. Here are some clues in this paper that I think questionable: 1. In Section 3.2, it claims that the challenge in applying previous MAB attack to discret MAB is $\alpha_t$ in (1) can be invalid (>=1) when the altered reward should keep binary, which leads to all the effort in finding a new $\alpha_t$ with care. But simply setting all returns for unwanted arms to be 0 may also get the job done. 2. Simulation section shows that Trivial_1 fails while Trivial_{k-1} succeeds,I don’t think Trivial_{k-1} has essential difference than Trivial_1 as in the special case k=2 they are identical. So maybe there’s something going wrong with the plots or interpretation.

Questions

Major question please refer to weakness 1.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

2 fair

Presentation

3 good

Contribution

2 fair

Limitations

Identified Limitations are listed in Weakness and Question.

Summary

This paper studies attack strategies against UCB-based OLTR algorithms for position-based click model and cascade click model. Compared with prior works in adversarial attacks, OLTR problem leads to the additional challenge that the rewards are discrete and bounded, which requires different attack method design, i.e., to ensure the post-attack reward is valid. The authors further propose attack strategy that works for OLTR algorithms with general click models, at the expense of additional attack cost compared with the strategies designed for specific click models.

Strengths

This paper is well-written and seems to be technically sound. To the best of my knowledge, this is the first work that provides rigorous solutions and analysis for attacking OLTR algorithms. The designed attack strategy for discrete and bounded reward might be of independent interest, e.g., it may be applied to other problem settings with discrete reward.

Weaknesses

I think a more intuitive (and self-contained) explanation, on why the use of conservative estimation can address the challenge caused by bounded reward, would be helpful. The current writing of Section 3.2 requires some knowledge of of [9] to fully understand the intuition and appreciate its novelty.

Questions

Can the authors provide more explanation on why constructing the set $a^{\star}$ by randomly selecting $K-1$ items, in addition to the target item $L$? Since the goal is to make target item $L$ appear in the recommended set $a_{t}$, why do we want to spend cost on making the learner recommend the $K-1$ randomly sampled items as well? Is it possible to simply making sure L replaces the last item in $a_{t}$? The reason the current design (for single target item) seems to be sub-optimal is that, this algorithm can be directly applied to the case where there are more than 1 but less than K+1 target items, without incurring additional cost, i.e., the algorithm will need to spend cost in making the learner pull $K-1$ randomly selected items anyway.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

4 excellent

Contribution

3 good

Limitations

N/A

A gentle reminder to reviewers

Dear reviewers, Thank you again for your valuable comments and suggestions. Since we are approaching the end of the discussion phase, we would appreciate it if you could read our responses and let us know if you have any follow-up questions. Best regards, Paper6757 Authors

Thank you for the response.

I read the rebuttal and my opinion has not changed

Thank you for the response

The response from authors is very helpful. I have also read the comments from other reviewers, as well as responses from authors. Now I have a better understanding of the algorithm design and its guarantees. From authors' response to Reviewer i6fi, the main advantage/contribution of the proposed attack algorithm is that its attack cost has better dependence on problem parameter $\Delta_{a}$, since it can conduct finer-grained attack (compared with setting reward of non-targeted item to 0) using the additional knowledge about the victim algorithm and the click model. However, what I feel is still unsatisfactory and lacks justification is proposed algorithm's dependence on $K$. As I mentioned in my original comments, since the goal of this paper is only to make sure the target arm appears in the recommended list (which is weaker than the goal of the work mentioned by Reviewer i6fi, that needs to put the target arm on top of the list), the current algorithm's design appears to be sub-optimal on this part. In this setting, joint learning and attacking might be needed to avoid spending unnecessary costs on the top $K-1$ arms. The authors response to these two questions seems to be a bit conflicting. For the dependence on $\Delta_{a}$, the authors argued their algorithm is "better" than the work mentioned by Reviewer i6fi, since it can utilize algorithm/model-specific information to conduct finer-grained attack, while for the dependence on "K", the authors argued their algorithm is also "better" than the suggested joint learning and attacking design, because it does not need algorithm/model-specific information. Therefore, I decided to lower my score.