Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper considers the problem of multi-task peer prediction where the goal is to elicit truthful information from agents using a scoring mechanism that scores agents based on their joint reports. It connects this problem of multi-task peer prediction to online no-regret learning by considering agents that learn to manipulate their reports in order to maximize their scores. The paper considers a special case of two agents and binary signal/reports and formulates the problem as a two-player repeated game. The paper shows that given any scoring mechanism there exist no-regret algorithms for agents which do not converge to truthful reporting. The paper then considers the CA mechanism which is a well-known mechanism for peer prediction and shows that a large class of learning algorithms converge to truthful reporting. This large class includes several no-regret algorithms such as Hedge, FPL etc. The paper also shows empirically that many popular online learning algorithms converge to truthful reporting.  
strengths_and_weaknesses: Strengths: I think that this paper provides a significant contribution to the burgeoning literature on mechanism design for learning agents. The problem of peer prediction is an important problem in information elicitation and is well-motivated due to various applications in crowdsourcing. The paper initiates a study of the dynamics of learning under this important problem and provides several non-trivial results.

Weakness: The paper considers a very simple setting with two agents and binary reports. Nevertheless, I think that this simple setting lays a solid foundation to build upon in the future.
questions: 1. Do the results presented in this paper extend to the case of multiple agents? It is not clear how to define a learning scenario for multiple agents and define the CA mechanism under such a learning scenario. 

2. It would be very interesting to see if the results in this paper can be extended to the case of non-binary signal/reports?

3. It would also be interesting to understand necessary conditions that result in truthful convergence of learning algorithms under the CA mechanism.
limitations: I do not foresee any negative societal impact of this paper.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper considers the sequential peer prediction setting when the participants are learning agents. In particular, the authors ask the following question — if a peer prediction mechanism is used to reward the learning agents, then under what conditions they converge to truthful reporting. The first result shows that some no regret learning mechanisms might fail to converge to truthful reporting. This is because the agents can construct a no-regret sequence of reports irrespective of their private signals.

The main contribution lies in showing that convergence to truthful strategies is possible if imposes certain assumptions on the no-regret learning algorithms. Fortunately, this class includes standard no-regret learning algorithms like Hedge, FPL etc. In particular, the main result shows that if the designer uses correlated agreement mechanism, and the joint distribution over the signals satisfy positive correlation, then convergence to truthful strategy is possible.  
strengths_and_weaknesses: 
Strengths:
- I think it is an interesting problem to address the convergence of learning algorithms under peer prediction based payment mechanisms. Prior work has empirically studied convergence properties of learning algorithms, and to the best of my knowledge, this paper proves convergence to truthful strategy for the first time.
- I found the analysis of the convergence proof quite interesting and non-trivial. The authors also clearly explained different steps involved in the proof.

Weaknesses:
- The setting only considers binary signal setting and that certainly makes the analysis easier.
- My other criticism is regarding the setting. If the designer knows that the agents will use a learning algorithm then the designer doesn’t have to use CA mechanism every round. Since all the tasks are identically distributed the designer can eventually learn the prior distribution and might not even need peer prediction mechanism. Is this observation accurate or am I missing something here?
- Finally, the proof assumes full information feedback setting. This is because an agent (say Alice) can observe Bob’s signal and can compute exact payment under a different strategy. However, in practice e.g. in rating platforms, people just receive their score for a report. So the learning algorithms must run with bandit feedback. I think this is the main limitation of the current paper.

Some other comments:
- Section 2 introduces the concept of rank k mechanism. Is this definition used anywhere? I understand that CA is a rank-2 mechanism, I am not sure if k > 2 is used anywhere. If not, it might be a good idea to avoid this definition.

questions: Some questions for the authors.
- Does the current proof work with bandit feedback e.g. what happens if one agent doesn't observe the other agent's reported signal and only receives the scores?
- In simulation, all the mechanisms eventually converge to truthful reporting. Is it possible to empirically show that there exists some mechanism which does not converge? I understand the existence of such a mechanism was shown using the probabilistic method, so it might not be possible to empirically show the existence of such a mechanism.
limitations: This paper doesn't have any negative societal impact.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper aims to theoretically analyze the dynamics of sequential peer prediction mechanisms, especially when participants are learning agents. To achieve this goal the authors firstly analyze the limitation of the notion no regret, that is, even no regret algorithms may also not converge. Then, the authors put their focus on a specific type of algorithms, where the policy is updated only based on the agents' cumulative rewards. In the experiments, the authors have conducted many simulation studies to demonstrate the effectiveness of their model.
strengths_and_weaknesses: 
To be honest, the topic of this paper is too far from my research domains. I can only make evaluations based on my general knowledge. In general, I think the paper is very well written, the organization is comfortable and compact. The studied problem seems to be important. Extending traditional static information elicitation mechanisms to sequential settings is important and should be more practical in real-world problems. The theory seems to be sound, which can well support their claims. 
My concerns are as follows: (1) it could be better if there are some real-world experiments. (2) If the sequence is too long, whether the error produced from the former steps influence much on the following steps.

As mentioned before, my background does not fit this paper, thus if other reviewers have negative opinions, I can change my score.
questions: See the Strengths And Weaknesses 
limitations: Yes, the authors have discussed the limitations of their model.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper studies a sequential reporting problem where two agents are incentivized via payments to report back a private signal each of them receives. While this problem has been studied under strong assumptions in the Bayesian setting, the authors are the first to study this problem when the two agents are learners and can update their actions to reflect what they have learned about the rewards based on this history so far. The author’s show that no-regret learning on its own is too weak a notion for any algorithm to incentivize truth-telling in the limit. But, the main punchline of the paper is that for a large class of natural learning algorithms based on reward updating (included in this class are several no-regret algorithms such as multiplicative weights and follow-the-leader), truthful peer prediction is indeed possible using a classic scheme (CA) that (to my understanding) incentivizes agreement between the two agents. This phenomenon is also demonstrated via an experiment.
strengths_and_weaknesses: Given that the CA scheme plays such an important role in the main results of the paper, I would have liked to see more discussion on (1) why it is important (2) what it means. It seems to reward one agent when the other agent changes her prediction to agree with that agent. But as far as I could tell there was no further discussion on this.

Also, more discussion on the class of reward-based learning algorithms would have been helpful, as this is the main condition posed by the authors as a fix to the unrealistic behavior that is possible under only a no-regret assumption. Why, intuitively, does this fix those issues? Can’t agents still collude in this model? To me it seems like the idea of reward updating a neat one, but its presentation is opaque: what do the axioms (assumptions 3.2-3.4) mean in plain language? Why use these specific axioms? 

The analysis of the stochastic process induced by CA and the learning agents is an interesting technical contribution, though I did not read the proofs in detail. 

I think the overall contribution is quite interesting and nicely fills in a gap in the peer-prediction literature (agents that learn is an important wrinkle being studied in various settings), but I think the main weakness of this paper is its presentation. I found concepts to be introduced in an ad-hoc manner without much discussion on how things connected (specific examples in the “Questions” section). 

questions: Line 97-98: State that X_t and Y_t denote random variables, and x_t and y_t are their realizations.

Section 2 would benefit from some more intuition and motivation. For example the “correlated agreement mechanism” is new to me, and a sentence or two on why it is important/intuitive in this setting would have been helpful.

Lines 116-118: the remark about multi-task information elicitation is confusing to someone who doesn’t already know what this is.

Lines 120-130: I found it difficult to understand the reasoning behind this setup. Why are the four actions defined as they are? If a strategy is a distribution over these four action that depends on the history of signals, isn’t it equivalent to let the set of actions be {0,1}, and then a strategy would be a mapping into the set of distributions on {0,1} that depends on the history/knowledge so far? I’m not able to see the need to have four distinguished options as they are defined currently, so if this is an important assumption the reason for it should be greatly clarified.

Line 152: “permutation equilibrium” (which I don’t think is a standard solution concept) has not been defined. 

Lines 157-159: My understanding is that the goal is to design algorithms to incentivize truthful reporting. I roughly understand that if both agents converge to opt_2 (fully mis-reporting), then the algorithm can be “flipped” to revert back to truthful reporting. But I think this needs more elaboration. How exactly can this be done with a single bit of “whether the prior of 0 is larger than 1”? There hasn’t been any discussion of priors/beliefs at this point. Also, would this allow for Defn 2.3 to wlog only include opt_1? If so that might be a more intuitive way to write the condition.

In assumption 3.3 should it be “nondecreasing” rather than “nonincreasing”? An intuitive explanation in words of what f and the assumptions mean would be helpful, though the instantiation for Multplicative weights is helpful.

Line 222: say that FPL is follow the perturbed leader.

General stylistic comments: many grammatical errors throughout. Avoid forward references (e.g. line 163).

limitations: N/A
review_title: null

Meta-review: metareview: The reviews are mostly positive and consider that the paper solves an interesting problem with non-trivial techniques. For further improvement, the reviewers mentioned some concerns about the problem setup being restricted, and gave some suggestions for improving presentation.
confidence: Less certain
Decision: Accept