Bandits Meet Mechanism Design to Combat Clickbait in Online Recommendation

Thank you for taking the time to read and review our paper. We believe that there might be some misconceptions about the mechanism design and the nature of our strategic bandit problem, which we hope to resolve below.

Adversarial Bandits: We are not entirely sure that we understand your comment about adversarial bandits correctly. We believe that, while challenging, it will be possible to extend our work to the case where arms dynamically adapt their strategies (click-rates) to the learning algorithm. We took a first step in this direction with our experiments, in which we considered the case of “learning” arms (as modeled by gradient ascent) and showed that UCB-S still effectively incentivizes desirable arm behavior. However, theoretically analyzing such dynamics is out of the scope of this paper. Moreover, our algorithm UCB-S is not plain UCB (which is incentive-unaware), but---despite being simple in its design---addresses the main difficulty in the strategic click-bandit which is to incentivize desirable NE under uncertainty while minimizing regret. Moreover, we also want to stress that our work specifically highlights the trade-off between incentivizing all arms to be truthful and recommending only the best arms (see Theorem 5.2 and the discussion below the theorem).

Questions:

Modeling:

1. The assumption that the learner publicly commits to an algorithm is standard in the mechanism design literature and is giving the arms maximal knowledege which makes the problem only more difficult for the learner. There are various ways the arms could reach a NE. Prior knowledge of the algorithm $M$, $T$ and $\Delta_i$ would for example be sufficient (see footnote 4). The arms could also reach an equilibrium by repeatedly interacting with the mechanism over several epochs like we considered in our experiments.

2. We believe that there might be a misconception about the goals of incentive-aware online learning. The goal of $M$ is not to simply minimize regret given a problem instance $s$ and $\mu$. Instead, $M$ must induce desirable equilibria among arms, which thereby allows $M$ to minimize regret. Under a given mechanism $M$ there can be several NE some of which may be more favourable than others. For example, a mechanism $M$ may induce two NE, the first of which is in desirable strategies, e.g., $(s^*(\mu_1), \dots, s^*(\mu_K))$, and the second in undeseriable strategies $(1, \dots, 1)$ (same goes for distributions over such strategy profiles). Under the first, desirable NE the algorithm would be able to achieve low regret, however, under the second, highly undesirable NE the regret would always be large. Hence, the weak regret is small whereas the strong regret is large. Please let us know if this remains unclear.

Algorithm design:

1. Since the distribution of $r_{t,i}$ has mean $\mu_{i}$, we can directly estimate $\mu_i$ from the observations of the post-click rewards: $\hat \mu_i^t = \sum_{l=1}^t \frac{1_{\{i_l=i\}} c_{l,i} r_{l,i}}{m_t(i)}$.

2. UCB-S is an upper confidence bounds-based algorithm just like UCB, but extended by the screening rule. Despite its simplicity, analyzing the dynamics between strategic arms and the learning algorithm (UCB-S) is challenging and the problem of incentivizing arms under (strategy-)uncertainty while minimzing regret has not been studied before. For this reason, we also believe that keeping the mechansim design simple is highly desirable so that the idea and parts of the analysis can more easily be reused and extended.

Thank you for taking the time to read and review our paper. You can find our answers to the two questions you highlighted below.

1. CTR as a chosen quantity: We agree that the case of arms freely choosing click-rates might not portray real-world scenarios. However, please note that when arms are limited in their control of the click-rates, we can expect to suffer less regret (as we remove some of their power to strategize). Still, an additional analysis would be required to make this statement precise. As you already hinted at, an interesting way to relax the mentioned assumption would be to assume that arms can repeatedly put effort towards changing their CTR, but there is no guarantee that this effort will have an effect every round (thereby limiting the arms' power/control). This would of course require additional modeling assumptions and the mechanism design and analysis would have to be carefully adapted to these changes. However, we believe that such a problem may still be theoretically tractable (depending on the specific modeling assumptions). In any case, this would also be an interesting problem to study empirically.

2. Arms changing their mean reward: Thank you for the interesting question which points at some exciting extensions to our work. Your question is also closely related to your other comment about modeling agent utilities. To give the arms more agency, we could, for instance, allow the arms to change their mean rewards each round at a cost. A simple, natural choice could be that the utility of arm $i$ in round $t$ is given by $v_{t,i} = \lambda_1 1_{\{i_t=i\}} c_{t,i} - \lambda_2 |\mu_{t,i}- \mu_{t-1,i}|$, i.e., arm $i$ has utility $\lambda_1$ for a click minus the cost $\lambda_2$ times distance for changing its mean reward. We naturally expect the analysis of arm behavior to become more complex (arms now take an action every round). Moreover, in this case a detailed characterization of arm behavior could be very intriguing since we would expect an additional dependence on the parameters of the arm utilities (here, $\lambda_1$ and $\lambda_2$). We believe that there are many similar and interesting extensions in this direction, which can build on our work.

Thank you for taking the time to read and review our paper. We respond to your comments and questions below.

1. Arms ability to control click-rates: Allowing the arms to arbitrarily select their click-rate results in a worst-case scenario from the perspective of the learner. If the arms had limited power, we would generally incur less regret. However, some adaptations to the mechanism and an additional analysis is required to make this statement precise. The case where each arm can only change their click-rate within a range (smaller than $[0,1]$) is an interesting direction for future work.

2. Screening rule and false positives: Please note that “false positives”, i.e., the event that an arm is eliminated at any round even though it has been truthful, occur with probability less than $1/T^2$ (this probability can be arbitrarily reduced by adapting the confidence intervals). Please also refer to the paragraph at the bottom of page 6, where we discuss that any elimination of UCB-S is always justified w.h.p. in the sense that truthful arms are never eliminated w.h.p. We comment on fixed-length cold-start algorithms further below.

3. Comparison to other work: Thank you for the suggestion. To the best of our knowledge, our paper is the first to study the situation where the agent strategies (and other parameters) are initially unobserved and must be learned from interaction while simultaneously incentivizing agents under uncertainty. It is therefore difficult to directly compare to other work along aspects like regret, and we found that the comparison of the regret to standard online learning problems such as MABs is the most insightful as this highlights the cost and challenges of mechanism design in online learning (see e.g. the discussion below Corollary 5.4).

4. (1). Yes, in Prop. 4.1 (i) all other arms are indifferent about their strategies because they are never selected by the $\mu$-Oracle. Hence, $v_i(s_i, s_{-i}) = 0 \cdot s_i = 0$ for any strategy $s_i$. However, when an arm is selected at least one time (which is the case in Figure 3 since standard UCB explores all arms), then the arm’s utility $v_i$ is maximized by $s_i = 1$.

   (2). The observation that UCB-S initially suffer larger regret than UCB can be explained by the elimination rule causing UCB-S to select arms uniformly at random when arms are untruthful. While generating larger regret in the short term (i.e., early epochs), this threat of elimination incentivizes the arms to adapt their strategies in the next epoch and eventually leads to smaller regret for UCB-S. In contrast, UCB simply attempts to minimize regret in the given problem instance without incentivizing any change in the arm behavior. We added additional explanations about this the experiments section. The y-axis is computed directly from the interactions of UCB-S and UCB with the respective arm strategies in response to these algorithms.

   (3). This is an open question, which turned out to be difficult to answer in generality. Instead, we deal with mixed NE by approximately characterized all strategies in the support of any NE (mixed or pure) in Theorem 5.2.

Questions:

1. Thank you for the interesting question. Such fixed-length cold-start algorithms behave similarly to explore-then-commit algorithms and will therefore suffer worse regret (typically order $T^{2/3}$) than adaptive exploration approaches such as UCB. Moreover, the probability of mistakenly eliminating truthful agents will be the same (i.e., there is no notable advantage in terms of false positives), since we must again rely on confidence bounds (please also see our response to your second question about the probability of an unjustified elimination).

2. One way to model such a setting would be to consider the case where the platform selects a set of arms each round and only one of the arms is clicked depending on their strategies. For instance, a natural click-model could be the MNL-model. In this case, the arms’ strategies no longer correspond exactly to their click-rate, but instead determine an arm’s click-rate relative to other arms (see also future work discussed in Appendix I).

3. While we chose to study a setting particularly inspired by online recommendation, we can think of our work and findings more abstractly as a setting in which the agents’ strategies (among other parameters) are initially unknown and must be learned from interaction while simultaneously incentivzing agents. The concept of confidence widths governing our mechanism design (as is the case in the screening rule of UCB-S) could prove useful for more scenarios, especially, for those where agent strategies are not directly observable, but must be learned from noisy observations. For example, another application scenario, which we however haven't closely looked into yet, could be repeated auctions with noisy bidding.

Thank you for taking the time to read and review our paper.

1. Arms ability to control click-rates: We agree that we study a simplified model in which we assume that each arm can freely choose their click-rate. However, this leads to a worst-case scenario from the perspective of the learner and when the arms are limited in their control over the click-rates we generally expect to incur less regret. Regarding clickbait and how clickbait influences click-rates, note that that the click-rate which the vendors can influence can be thought of as the click-rate of a new user without prior exposure to the specific item, hence, the click-rate wouldn't be necessarily harmed over time. Nevertheless, the extension to click-rates which change over time (whether caused by the arms or other sources) is an interesting direction for future work. The case where the arms can only change their click-rate within a limited range is also interesting.

2. NE and other arm behavior: We completely agree. For this reason we wanted to support the developed theory with our experiments which assume a natural model of gradually adapting arm behavior as modeled by gradient descent. We were happy to observe that our incentive design is also effective under such models of arm behavior and that our theoretical results are direclty corroborated by the experiments (e.g., in the experiments we also observe that the optimality gap of each arm governs their behavior/strategy). While challenging, theoretically analyzing such "learning" agents' behavior is definitely an interesting direction for future work but out of the scope of this paper.