A Bandit Framework for Strategic Regression
We consider a learner's problem of acquiring data dynamically for training a regression model, where the training data are collected from strategic data sources. A fundamental challenge is to incentivize data holders to exert effort to improve the quality of their reported data, despite that the quality is not directly verifiable by the learner. In this work, we study a dynamic data acquisition process where data holders can contribute multiple times. Using a bandit framework, we leverage the long-term incentive of future job opportunities to incentivize high-quality contributions. We propose a Strategic Regression-Upper Confidence Bound (SR-UCB) framework, a UCB-style index combined with a simple payment rule, where the index of a worker approximates the quality of his past contributions and is used by the learner to determine whether the worker receives future work. For linear regression and a certain family of non-linear regression problems, we show that SR-UCB enables an O log T
This paper studies how to incentivize (self-interested) "arms" to exert effort to improve the quality of their predictions in a MAB setting. The setting assumes that no "ground truth" costs are ever revealed, giving  the problem an additional technical complication of how to measure the quality of the arms' predictions. They show in certain settings that there exist payment schemes and learning algorithms which have approximate BNE with arms exerting enough effort to give the algorithms nontrivial regret guarantees. They also show how to implement the updates of such algorithms in computationally less expensive way, and also in ways which preserve privacy of the arms. 
 The question studied in the paper is interesting, and borrowing the idea from peer prediction to use the other arms' predictions as an unbiased estimator of the quality of one arm's prediction is a nice idea (in particular, because those arms need to be incentivized enough to make reasonably accurate predictions).   However,  the paper focuses too much on presenting "bells and whistles" rather than giving a deeper understanding of the basic (and main) results. Perhaps reorganizing the paper to only briefly mention the computational/privacy aware variants and giving both more intuition and technical content describing the main result (namely, that there exist \alpha-BNE with small regret) would focus the paper and give the reader a cleaner message of what the paper is doing.  This tact would have the added benefit that the reader might be able to better assess the "quantitative" consequences of this work, in that it would leave more room for the authors to ruminate on how much better or worse these bounds are than what one could get in the non-strategic setting, or in various trivial simplifications/special cases of this model. As the paper stands, this reviewer finds it difficult to assess from the main body of the paper alone the technical contribution of the paper (and whether the results follow from a mild reworking of standard proofs or need substantial, new ideas). It is also difficult to assess a theory paper which gives not even a sketch or an outline of a proof in the main body of the paper.  It would also be interesting to have some idea of what reasoning goes into designing the payment rules, or some lower bounds, or some impossibility results showing what sorts of BNE cannot be ruled out by any (reasonable) payment rule; since this is not a "PoA" style result that shows *all* apx-BNE have these regret guarantees, only that some will.  On a smaller scale, the paper has many typos that a spellchecker would catch, and many grammatical errors which make reading the paper cumbersome. This feels like a rough draft that a few days of love would substantially improve in this regard.  It also seems  somewhat strange that the assumptions about various parameters are scattered throughout the body of the paper; they should all be in one place or at least in the theorem statement(s).  Odds-n-ends  - run a spellcheck -"nowadays"? - "degrade the machine learning system's" -> "degrade machine learning systems' " - add "many" before "stable"? - "leveraged" should not be followed by "on" - "indexes" should be "indices" - "computationally light" is a weird phrase. - "the provided incentive much". What? Perhaps "without substantially degrading the incentives guarantee" - "beings" -> "being" - "after receiving the task" should be "after receiving a task" - worth mentioning that different "effort" functions could correspond to different levels of skill in workers - worth mentioning that the per-round payment scheme is "individually rational" - plurality seems to be a regular issue, as well as missing/incorrect articles (the, an, a, etc)