Strategic Apple Tasting

Summary

The paper studies an online learning problem with incentives. In particular, in the model studied in the paper there is a principal who has to take decisions on a sequence of $T$ (different) agents. Each agent has a context and they can strategically disclose it (truthfully or untruthfully) to the principal in order to induce them to take favorable decisions. The key feature of the model studied in the paper is that the feedback is one-sided, meaning that the principal only observes a feedback when they take a positive decision on the agent. The paper first proposes an algorithm that achieves $\tilde O(\sqrt{T})$ strategic regret (a stronger notion than Stackelberg regret), when the the contexts are selected stochastically. Then, the paper shows how to deal with adversarially-chosen contexts, by providing an algorithm with $\tilde O(T^{(d+1)/(d+2)})$ strategic regret.

Strengths

ORIGINALITY The paper studies, for the first time to the best of my knowledge, an online learning problem in which both incentives and one-sided feedback are involved. This is a relevant combination present in may application domains. QUALITY The paper does a good job in addressing several aspects of the online learning problem under study. In particular, the paper studies both the case in which contexts are selected stochastically and the one in which they are chosen adversarially. CLARITY The paper is well written and easy to follow. SIGNIFICANCE I believe that the problem studied in the paper is of interest several people spanning different communities, from online learning to algorithmic game theory.

Weaknesses

ORIGINALITY The techniques used in the paper are not groundbreaking, but they are rather adaptations of well-known and widely-used techniques in online learning. QUALITY While the literature revised in the paper is quite extensive as far as work on online learning with incentives are concerned, I think the paper is missing some very related works in the literature at the interface between algorithmic game theory and online learning. In particular, the following lines of research seem strongly related to the paper: - Repeated Stackelberg games: Balcan, Maria-Florina, et al. "Commitment without regrets: Online learning in stackelberg security games." Proceedings of the sixteenth ACM conference on economics and computation. 2015. (see also some subsequent works extending the paper) - Online Bayesian persuasion: Castiglioni, Matteo, et al. "Online bayesian persuasion." Advances in Neural Information Processing Systems 33 (2020): 16188-16198. + Castiglioni, Matteo, et al. "Multi-receiver online bayesian persuasion." International Conference on Machine Learning. PMLR, 2021. (these works extend those on repeated Stackelberg games to the Bayesian persuasion framework) - Online learning in principal-agent problems: Zhu, Banghua, et al. "The Sample Complexity of Online Contract Design." arXiv preprint arXiv:2211.05732 (2022). (a recent preprint that indeed seems very related to the present paper) I would have expected a discussion on these works in the paper. Of course, the papers that I cited above are only some representative of such a line of research, and I am happy to provide more references if the authors need them. CLARITY No weaknesses to report. SIGNIFICANCE No weaknesses to report.

Questions

1) I believe that the model studied in the paper is closely connected with one introduced in a very recent preprint (Bernasconi, Martino, et al. "Optimal Rates and Efficient Algorithms for Online Bayesian Persuasion." arXiv preprint arXiv:2303.01296 (2023).). In that paper, the authors study a model with type reporting that looks very similar to the one in the present paper. Am I right? 2) The regret bound in Theorem 4.1 is very similar to a regret bound in (Zhu, Banghua, et al. "The Sample Complexity of Online Contract Design." arXiv preprint arXiv:2211.05732 (2022).). Can you discuss the differences between the approach in that paper and your approach? 3) Algorithm 3 requires exponential running time in the worst case. Are there any computational hardness results that can be applied to your problem?

Rating

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

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

No limitations.

Summary

The paper studies strategic apple tasting settings. This setting involves decision making that assigns decisions to agents who have incentives to strategically modify their input (context), and the decision maker only receives apple tasting (one-sided) feedback, where it only receives feedback for positively assigned decisions. The authors formulate this setting as an online learning problem with apple-tasting feedback, where a principal makes decisions about a sequence of T agents, with the goal of achieving sublinear strategic regret. Under this problem formulation, the authors proposed a learning algorithm (Algorithm 1) based on greedy, shifted linear policy, and parameter updates based on clean contexts. The author shows that the algorithm achieves O(\sqrt{T}) strategic regret when the sequence when the agent contexts are generated stochastically. Then, the authors extendes to the situation where T is small or unknown and proposed another algorithm (Algorithm 2) under this scenario. Finally, the authors relax the assumption and provide an algorithm (Algorithm 3) under adversarially generated agents. These results apply to the more general setting of bandit feedback, under slight modifications to the algorithms.

Strengths

- I like that the paper is very well written and easy to follow - The studied one-sided feedback settings with strategic agents are interesting and often occurs in real-world situations. - The problem is clearly formulated. For all proposed algorithms, the authors provided performance guarantees which are clearly explained and supported by proofs.

Weaknesses

It is slightly hard for me to make a connection between assumption of the agent's strategic modification to their context (with effort budget \delta mentioned in definition 2.1), and the motivated examples such as hiring and lending.

Questions

- As in the above section, can the authors shed some light on the strategic modification effort budget? - Line 212: The authors mentioned "This is the type of strategizing we want to incentivize." I didn't understand why the decision maker would like to incentivize this behavior? - Algorithm 1 line 4, "... and data S_t", do you mean "data D_t"? - Can the authors move algorithm 4 (which is part of algorithm 2) into the main text?

Rating

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

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

3 good

Presentation

3 good

Contribution

3 good

Limitations

I see that the authors listed a few related future directions in the conclusion. No negative societal impact observed.

Summary

The paper considers contextual bandit problem in which the users can strategically modify their context for its own sake. It provides sublinear regret algorithms by exploiting the budgeted strategic structure of the agents, against stochastically chosen agents. It further obtains sublinear regret algorithms against adversarially chosen agents by considering a variant of EXP3.

Strengths

The paper studies interesting problem setting and makes reasonable contribution.

Weaknesses

Although the analysis seems technically thorough, intuition behind the solution is pretty straightforward: incentivize truthful action for certain amount of times, estimate $\theta$, strictly separate strategically modified context by conservatively setting decision boundary based on the effort budget. Also, the algorithm seems to heavily depend on the information on the agents' budget. Detailed comments are in Questions.

Questions

- What happens if the principal can also optimize over the choice of decision policy, i.e., not just using thresholded rule? - In L254, even though a small fraction of agents may strategically modify their contexts, it seems fairly intuitive that the estimates would be inconsistent, so wonder why the authors think this to be a surprising fact - is it meant to be "far" from being consistent, not just inconsistent? - L82 consists a lot of citations. It looks bad to me, at least parsing them/giving more contexts to each reference/removing part of them would be helpful. It's a bit distracting in its current form and gave me no information. - It seems that the algorithm essentially needs to know the budget $\delta$ in advance. What happens if the algorithm has misspecified budget? Is the algorithm fairly robust? - In L170, bandit feedback setting is said to be more challenging - why is it more challenging than the one-sided feedback? Also, the authors argue that all their algorithms can be made to be applicable to the bandit setting - yes it's good to know that, but I wonder if there's more general results, e.g., any reduction from one setting to the other, or if the authors have thought about any black-box reduction from one algorithm to another. - I also wonder why the standard adversarial contextual bandit algorithm does not work, instead of Algorithm 1, possibly with some slight modifications. - I'd like to ask on how the authors think about the case if the agents observe some noisy context about themselves. Minor comments - I found the presentation of Stackelberg regret and Proposition 2.4 a bit redundant, as it does not appear in the main paper but there. - In Algorithm 1, what is data $S_t$ - it seems it's not updated at all? - L290, typo: withing - L298, duplicated threshold

Rating

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

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

Detailed comments are in Questions.

Summary

They consider the problem of online learning with apple tasting feedback where the sequence of arriving agents may strategically modify their features (contexts). They show how to achieve sublinear strategic regret compared to the best policy in the hindsight if agents were reporting truthfully. Their main result is $\tilde{O}(\sqrt{T})$ strategic regret when the sequence of agents arriving is stochastic. Their regret bound depends exponentially on d the context dimension. They show how to mitigiate this dependency and achieve a regret bound that depends polynomially on d but with a worse dependence on T. The main idea to to use a modified version of explore-then-commit algorithm that was introduced in the prior work. Finally, they extend their results to a sequence of agents chosen by an oblivious adversary that achieves sublinear regret however it requires an exponentially large amount of computation at each round.

Strengths

I think the paper is written nicely and the results are nice. The algorithms seem to be a natural extension of the non-strategic setting. The model is interesting and the presentation is great.

Weaknesses

I think the paper is written nicely and the results are nice. The algorithms seem to be a natural extension of the non-strategic setting. Since they are using the linear thresholds model, they need to shift the decision boundary to account for strategic behavior and a similar set of ideas have been studied in the previous work.

Questions

It might be helpful to add a paragraph on how your bounds differ from the non-strategic case. Prop 2.4. last line, it might be helpful for the reader to argue why the first term is at most 0. Line 218, you can ensure the data is clean since it is strictly above the threshold? Thm 3.3. it might be helpful to also remind the reader what c_0 is. Another open question is to get regret bounds when the agents are picked by an adaptive adversary. Are there any connections between the trembling hand model that you are describing and the \eps-best response model considered by [Haghtalab, Lykouris, Nietert, Wei' EC22]? Another piece of work related to your bandit feedback could be the work by [Ahmadi, Blum, Yang' EC23] where in one of their models they propose a modification of EXP3 algorithm in the strategic setting.

Rating

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

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

4 excellent

Presentation

4 excellent

Contribution

3 good

Limitations

yes

Summary

This paper studies an online learning problem with one-sided (apple-tasting) feedback. At each round $t\in[T]$, an agent with a $d$-dimensional context vector $x_t$ arrives. The principal chooses a policy $\pi_t$ to map the context to binary decisions. Given $\pi_t$, the agent best responds strategically by modifying their context to $x'_t$ where $||x'_t-x_t||\leq \delta$. Then, the principal receives a one-sided, linear feedback in $x_t$. The goal is to design a policy with sub-linear strategic regret that compares the principal's reward with that of the optimal policy had agents reported their contexts truthfully. The authors propose algorithms for stochastic and adversarial settings.

Strengths

- Online learning with strategic agents has many real-world applications and the results of this work could be applied to automatic decision-making processes such as lending and hiring. Therefore, the problem is very well-motivated. - The paper is very well-written, in particular, the proof sketches provided in the paper give a very clear high-level picture of the techniques and ideas used to analyze the performance of the algorithms. - The authors have done an excellent job comparing and contrasting their paper with prior works, it is clear how this paper contributes to this literature.

Weaknesses

- While the proposed algorithms are a great first step towards solving this problem, they are sub-optimal from different aspects. First, Algorithm 1 does not make any use of unclean data and it simply discards them. While the authors have shown that using unclean data for estimation is not useful, they could be used with some confidence level to rule out some of the underperforming policies. Moreover, Algorithm 3 for the adversarial setting is practically not useful because of its exponential computational complexity. - Based on the motivating examples that are provided in the introduction, I don't see why agents strategically modifying their context vector is necessarily a bad thing. For instance, paying bills on time and maintaining low credit utilization to increase credit scores (which is used for lending) should be incentivized (rather than discouraged).

Questions

- What is the reasoning behind a bounded $\ell_2$ norm perturbation of size $\delta$ (instead of a different norm or a packing-type constraint) as the effort budget? Could you explain this in the context of a motivating application? - Why is $r_0$ missing in the linear thresholding policy of Algorithm 3? - Instead of considering each $d$-dimensional vector in $[0,1]^d$ (or a discretized grid of such vectors) as experts in Algorithm 3, is it possible to assume a structure on the policies and solve the resulting online structured learning problem (as it's done in the following papers)? Koolen, Wouter M., Manfred K. Warmuth, and Jyrki Kivinen. "Hedging Structured Concepts." COLT. 2010. Cohen, Alon, and Tamir Hazan. "Following the perturbed leader for online structured learning." International Conference on Machine Learning. PMLR, 2015. - Algorithm 4 is mentioned multiple times in the paper, but it's not provided in the main text. It'd be great to either have the algorithm or a short description of it in the paper. - Is it possible to relax the assumption that the variance $\sigma^2$ is known? How would such a relaxation affect the results? -------------------------------- I've read the authors' rebuttal, thanks for addressing my questions and concerns.

Rating

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

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

2 fair

Limitations

The limitations are clearly discussed in the conclusion. This is a theoretical work and a discussion of potential negative societal impacts is not necessary.