論文の概要: No-Regret Online Prediction with Strategic Experts
- arxiv url: http://arxiv.org/abs/2305.15331v1
- Date: Wed, 24 May 2023 16:43:21 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-25 14:09:49.272577
- Title: No-Regret Online Prediction with Strategic Experts
- Title（参考訳）: 戦略的専門家によるノンレグレットオンライン予測
- Authors: Omid Sadeghi and Maryam Fazel
- Abstract要約: オンラインバイナリ予測の一般化をエキスパートアドバイスフレームワークを用いて研究し、各ラウンドで、学習者は、Kドルの専門家のプールからmgeq 1ドルの専門家を選ぶことができる。
我々は、専門家が戦略的に行動し、彼らの信念を誤報することでアルゴリズムの予測への影響を最大化することを目的とした設定に焦点を当てる。
目標は,次の2つの要件を満たすアルゴリズムを設計することです。 1) $textitIncentive-compatible$: 専門家に信念を真実に報告させるインセンティブ,2) $textitNo-regret$: Achieve。
- 参考スコア（独自算出の注目度）: 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.
- Abstract（参考訳）: オンラインバイナリ予測の一般化をエキスパートアドバイスフレームワークを用いて研究し、各ラウンドで、学習者は、Kドルの専門家のプールから$m\geq 1$のエキスパートを選ぶことができ、全体的なユーティリティは、選択した専門家のモジュラーまたはサブモジュラー関数である。
我々は,専門家が戦略的に行動する場面に着目し,アルゴリズムの予測への影響を最大化することを目的とした。
この設定は、学習者が異なる予測者を集約して予測を行うだけでなく、相対的なパフォーマンスに応じてそれらをランク付けしようとする予測競技に応用される。
私たちの目標は、以下の2つの要件を満たすアルゴリズムを設計することです。
1) $\textit{Incentive-compatible}$: 専門家に彼らの信念を真実に報告するよう促し、
2) $\textit{no-regret}$: 従属する中での$m$専門家の最高の固定セットの真の信念に関して、サブリニアな後悔を達成する。
以前の研究では、$m=1$でこのフレームワークを研究しており、この問題に対してインセンティブ互換のno-regretアルゴリズムを提供した。
まず、簡単な$m=1$設定の削減は効率的でも効果的でもないことを示す。
次に,実用関数の具体的構造を利用して2つの目的を達成するアルゴリズムを提案する。
関連論文リスト
- Fair Secretaries with Unfair Predictions [12.756552522270198]
予測値が少なくとも$maxOmega (1), 1 - O(epsilon)$倍の候補を受け入れることを約束しているにもかかわらず、アルゴリズムが最良の候補を受け入れる確率がゼロであることを示し、ここでは$epsilon$が予測誤差である。
私たちのアルゴリズムと分析は、既存の作業から分岐し、結果のいくつかを単純化/統一する、新たな"ペギング(pegging)"アイデアに基づいている。
論文 参考訳（メタデータ） (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]
古典的な予測ゲームと専門的なアドバイスと二進的な結果の1つの見方では、それぞれの専門家は反対に選択された信念を維持している。
本稿では、この問題の戦略的なバリエーションとして、自己中心的な専門家(レコメンデーション・シーキング)が紹介されている。
損失列の明示的な構成により、アルゴリズムは最悪の場合$Omega(T2/3)$lowboundに苦しむことを示した。
論文 参考訳（メタデータ） (2024-04-08T02:41:32Z) - Trading-Off Payments and Accuracy in Online Classification with Paid
Stochastic Experts [14.891975420982513]
有償専門家によるオンライン分類について検討する。
各ラウンドでは、学習者は専門家にいくら払うかを決め、予測しなければなりません。
本稿では,T$ラウンド後の総費用が予測値を上回るオンライン学習アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-07-03T08:20:13Z) - Active Ranking of Experts Based on their Performances in Many Tasks [72.96112117037465]
我々は、dタスクのパフォーマンスに基づいて、n名のエキスパートをランク付けする問題を考察する。
我々は,各専門家のペアに対して,各タスクにおいて他方よりも優れているという,単調な仮定を定めている。
論文 参考訳（メタデータ） (2023-06-05T06:55:39Z) - Streaming Algorithms for Learning with Experts: Deterministic Versus
Robust [62.98860182111096]
エキスパート問題を伴うオンライン学習では、アルゴリズムは、T$day(または時間)ごとに結果を予測する必要がある。
目標は最小限のコストで予測を行うことだ。
最良専門家が$M$の誤りを犯したとき、後悔する$R$を達成するような決定論的アルゴリズムに対して、$widetildeOmegaleft(fracnMRTright)$の空間下界を示す。
論文 参考訳（メタデータ） (2023-03-03T04:39:53Z) - Memory Bounds for the Experts Problem [53.67419690563877]
専門家のアドバイスによるオンライン学習は、逐次予測の根本的な問題である。
目標は、予測を処理し、最小コストで予測を行うことです。
アルゴリズムは、そのセットでもっとも優れた専門家と比較してどれだけうまく機能するかによって判断される。
論文 参考訳（メタデータ） (2022-04-21T01:22:18Z) - Non-Clairvoyant Scheduling with Predictions Revisited [77.86290991564829]
非論理的スケジューリングでは、優先度不明な処理条件でジョブをスケジューリングするためのオンライン戦略を見つけることが課題である。
我々はこのよく研究された問題を、アルゴリズム設計に(信頼できない)予測を統合する、最近人気の高い学習強化された設定で再検討する。
これらの予測には所望の特性があり, 高い性能保証を有するアルゴリズムと同様に, 自然な誤差測定が可能であることを示す。
論文 参考訳（メタデータ） (2022-02-21T13:18:11Z) - Malicious Experts versus the multiplicative weights algorithm in online
prediction [85.62472761361107]
2人の専門家と1人の予測者による予測問題を考える。
専門家の一人が正直で、各ラウンドで確率$mu$で正しい予測をしていると仮定する。
もう一つは悪意のあるもので、各ラウンドで真の結果を知り、予測者の損失を最大化するために予測を行う。
論文 参考訳（メタデータ） (2020-03-18T20:12:08Z) - No-Regret and Incentive-Compatible Online Learning [29.267666165169324]
本研究では,学習アルゴリズムの予測に対する影響を最大化するために,専門家が戦略的に行動するオンライン学習環境について検討する。
私たちは、学習アルゴリズムを、後見の最高の固定専門家に対して、不適切なものにしたいと考えています。
完全な情報設定と部分的な情報設定の両方について、専門家にとって後悔とインセンティブの相性のないアルゴリズムを提供する。
論文 参考訳（メタデータ） (2020-02-20T16:21:34Z) - Toward Optimal Adversarial Policies in the Multiplicative Learning
System with a Malicious Expert [87.12201611818698]
専門家のアドバイスを組み合わせて真の結果を予測する学習システムについて考察する。
専門家の一人が悪意があり、システムに最大損失を課すことを目指していると推測されている。
誤予測を常に報告する単純な欲求ポリシーは、近似比が1+O(sqrtfracln NN)$で最適であることを示す。
悪意のある専門家がその判断を適応的に行うことができるオンライン環境では、最適のオンラインポリシーを$O(N3)$で動的プログラムを解くことで効率的に計算できることが示される。
論文 参考訳（メタデータ） (2020-01-02T18:04:46Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。