No-Regret Online Prediction with Strategic Experts
- URL: http://arxiv.org/abs/2305.15331v1
- Date: Wed, 24 May 2023 16:43:21 GMT
- Title: No-Regret Online Prediction with Strategic Experts
- Authors: Omid Sadeghi and Maryam Fazel
- Abstract summary: We study a generalization of the online binary prediction with expert advice framework where at each round, the learner is allowed to pick $mgeq 1$ experts from a pool of $K$ experts.
We focus on the setting in which experts act strategically and aim to maximize their influence on the algorithm's predictions by potentially misreporting their beliefs.
Our goal is to design algorithms that satisfy the following two requirements: 1) $textitIncentive-compatible$: Incentivize the experts to report their beliefs truthfully, and 2) $textitNo-regret$: Achieve
- Score: 16.54912614895861
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study a generalization of the online binary prediction with expert advice
framework where at each round, the learner is allowed to pick $m\geq 1$ experts
from a pool of $K$ experts and the overall utility is a modular or submodular
function of the chosen experts. We focus on the setting in which experts act
strategically and aim to maximize their influence on the algorithm's
predictions by potentially misreporting their beliefs about the events. Among
others, this setting finds applications in forecasting competitions where the
learner seeks not only to make predictions by aggregating different forecasters
but also to rank them according to their relative performance. Our goal is to
design algorithms that satisfy the following two requirements: 1)
$\textit{Incentive-compatible}$: Incentivize the experts to report their
beliefs truthfully, and 2) $\textit{No-regret}$: Achieve sublinear regret with
respect to the true beliefs of the best fixed set of $m$ experts in hindsight.
Prior works have studied this framework when $m=1$ and provided
incentive-compatible no-regret algorithms for the problem. We first show that a
simple reduction of our problem to the $m=1$ setting is neither efficient nor
effective. Then, we provide algorithms that utilize the specific structure of
the utility functions to achieve the two desired goals.
Related papers
- Fair Secretaries with Unfair Predictions [12.756552522270198]
We show that an algorithm can have zero probability of accepting the best candidate, which we deem unfair, despite promising to accept a candidate whose expected value is at least $maxOmega (1), 1 - O(epsilon)$ times the optimal value, where $epsilon$ is the prediction error.
Our algorithm and analysis are based on a new "pegging" idea that diverges from existing works and simplifies/unifies some of their results.
arXiv Detail & Related papers (2024-11-15T00:23:59Z) - On the price of exact truthfulness in incentive-compatible online learning with bandit feedback: A regret lower bound for WSU-UX [8.861995276194435]
In one view of the classical game of prediction with expert advice with binary outcomes, each expert maintains an adversarially chosen belief.
We consider a recently introduced, strategic variant of this problem with selfish (reputation-seeking) experts.
We show, via explicit construction of loss sequences, that the algorithm suffers a worst-case $Omega(T2/3)$ lower bound.
arXiv Detail & Related papers (2024-04-08T02:41:32Z) - Trading-Off Payments and Accuracy in Online Classification with Paid
Stochastic Experts [14.891975420982513]
We investigate online classification with paid experts.
In each round, the learner must decide how much to pay each expert and then make a prediction.
We introduce an online learning algorithm whose total cost after $T$ rounds exceeds that of a predictor.
arXiv Detail & Related papers (2023-07-03T08:20:13Z) - Active Ranking of Experts Based on their Performances in Many Tasks [72.96112117037465]
We consider the problem of ranking n experts based on their performances on d tasks.
We make a monotonicity assumption stating that for each pair of experts, one outperforms the other on all tasks.
arXiv Detail & Related papers (2023-06-05T06:55:39Z) - Streaming Algorithms for Learning with Experts: Deterministic Versus
Robust [62.98860182111096]
In the online learning with experts problem, an algorithm must make a prediction about an outcome on each of $T$ days (or times)
The goal is to make a prediction with the minimum cost, specifically compared to the best expert in the set.
We show a space lower bound of $widetildeOmegaleft(fracnMRTright)$ for any deterministic algorithm that achieves regret $R$ when the best expert makes $M$ mistakes.
arXiv Detail & Related papers (2023-03-03T04:39:53Z) - Memory Bounds for the Experts Problem [53.67419690563877]
Online learning with expert advice is a fundamental problem of sequential prediction.
The goal is to process predictions, and make a prediction with the minimum cost.
An algorithm is judged by how well it does compared to the best expert in the set.
arXiv Detail & Related papers (2022-04-21T01:22:18Z) - Non-Clairvoyant Scheduling with Predictions Revisited [77.86290991564829]
In non-clairvoyant scheduling, the task is to find an online strategy for scheduling jobs with a priori unknown processing requirements.
We revisit this well-studied problem in a recently popular learning-augmented setting that integrates (untrusted) predictions in algorithm design.
We show that these predictions have desired properties, admit a natural error measure as well as algorithms with strong performance guarantees.
arXiv Detail & Related papers (2022-02-21T13:18:11Z) - Malicious Experts versus the multiplicative weights algorithm in online
prediction [85.62472761361107]
We consider a prediction problem with two experts and a forecaster.
We assume that one of the experts is honest and makes correct prediction with probability $mu$ at each round.
The other one is malicious, who knows true outcomes at each round and makes predictions in order to maximize the loss of the forecaster.
arXiv Detail & Related papers (2020-03-18T20:12:08Z) - No-Regret and Incentive-Compatible Online Learning [29.267666165169324]
We study online learning settings in which experts act strategically to maximize their influence on the learning algorithm's predictions.
We want the learning algorithm to be no-regret with respect to the best fixed expert in hindsight.
We provide algorithms that achieve no regret and incentive compatibility for experts for both the full and partial information settings.
arXiv Detail & Related papers (2020-02-20T16:21:34Z) - Toward Optimal Adversarial Policies in the Multiplicative Learning
System with a Malicious Expert [87.12201611818698]
We consider a learning system that combines experts' advice to predict a sequence of true outcomes.
It is assumed that one of the experts is malicious and aims to impose the maximum loss on the system.
We show that a simple greedy policy of always reporting false prediction is optimal with an approximation ratio of $1+O(sqrtfracln NN)$.
For the online setting where the malicious expert can adaptively make its decisions, we show that the optimal online policy can be efficiently computed by solving a dynamic program in $O(N3)$.
arXiv Detail & Related papers (2020-01-02T18:04:46Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.