Summary
- The paper studies the problem of online prediction with expert advice. In their setting, a learner at each round selects $m$ experts, and the loss is determined by a submodular or modular function of the beliefs reported by the selected experts. Each expert, being strategic, may intentionally misrepresent their beliefs to maximize their chances of being selected in the next round. The goal of the learner is to design no-regret algorithms that incentive experts to report their beliefs truthfully (also called IC).
- To tackle this problem, the authors first present an inefficient reduction to the case when $m=1$. Subsequently, they propose two efficient algorithms that are for the specific types of loss functions considered.
- In the case of the modular loss function, the authors investigate Follow-The-Perturbed-Leader (FTPL) and propose a general condition for the perturbation distribution that ensures approximate IC.
- For the submodular loss function,they propose a simpler algorithm named the online distorted greedy algorithm. This algorithm not only guarantees exact IC but also attains the optimal approximation ratio.
Strengths
- The paper studies an important and generic problem of online prediction with strategic experts that may find its applications in many scenarios.
- The proposed algorithms in this paper are not only easy to implement and also enjoy good theoretical guarantees of being (approximate) IC and no regret.
Weaknesses
1. Several claims may have some issues, see eg Questions 3, 5, 6.
2. The presentation could be improved. For instance, Section 1.2 titled "Contributions" seems to contain some elements of background and motivations which might be more appropriately placed in the introduction of the paper. Moreover, it would be beneficial to include more discussions following important definitions (like Def 1) and theorems to provide more intuitions.
3. In the experimental section, the authors plot the regret curve that is not normalized. This makes it hard to interpret, as unnormalized regret curves don't explicitly demonstrate the rate at which the algorithms learn. Additionally, to reflect the difference between reported and true beliefs, a uniformly random value within the range guaranteed by Theorem 3 is added, but this theorem doesn't ensure a uniform distribution for this difference. Finally, incorporating a comparison of the proposed algorithms with and aggregated predictions of FiveThirtyEight could potentially enrich the analysis.
Questions
1. Regarding Def 1:
- Is this a new concept being proposed, or has it previously been studied in previous works?
- The experts are long-standing in this setting, but the focus of the paper is on myopic IC. Although the authors mentioned that the analysis of FTPL could be extended to the more general setting of maximizing a conic combination of probabilities of being chosen at all subsequent rounds, is it also true for the online distorted greedy algorithm? What's the main modification/challenge of extending to non-myopic experts?
- Would achieving IC become impossible if the definition is for all $r_t$, rather than the expectation over Bern( $b_{i,t}$ )?
2. In the "forecasting competitions" example described in Section 3.1, it seems that the loss function is not captured by the modular function studied in this paper, given it is normalized by $|S_t|$ rather than $m$.
3. About Thm 1, could you clarify why the reduction preserves IC? In particular:
- How is the belief of each meta-expert defined in this context? Is the new loss function $\ell_S$ still proper? How to define IC when the belief of each expert is multi-dimensional?
- Even though WSU is IC for the $m=1$ problem, it only guarantees every single expert reports truthfully when fixing other's reports. In particular, it doesn't rule out the possibility that a group of experts form a coalition and misreport together to increase the sum of their probabilities of being selected, which is exactly what would happen when a single expert misreports in the $m$-expert problem -- it results in the simultaneous misreporting of $\binom{K}{m-1}$ meta-experts.
4. Thm 3 guarantees approximate IC in the sense of $|p^\star\_{i,t}-b\_{i,t}|$ being small. However, a more common notion of approximate IC is through the difference of utility, which, applies to this setting, is the difference in $\pi_{i,t+1}$ when $p^\star_{i,t}$ and $b_{i,t}$ are reported respectively. Could the authors include a discussion about this alternative notion?
5. Combining Thm 3 and Thm 5, it seems that as $B$ approaches 0, the FTPL algorithm becomes more IC and also yields a smaller regret. However, this contradicts the intuition that if the learner's decisions are entirely noise-driven (i.e., $B=0$), the regret should be high. Could the authors comment on this?
6. On lines 297-298, you mention that the $(1-\frac{c_f}{e})$ approximation factor is optimal. Is this claim supported by a lower bound? If so, could you point to the relevant references?
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.