論文の概要: No-regret incentive-compatible online learning under exact truthfulness with non-myopic experts
- arxiv url: http://arxiv.org/abs/2502.11483v1
- Date: Mon, 17 Feb 2025 06:36:45 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-02-18 14:14:08.712356
- Title: No-regret incentive-compatible online learning under exact truthfulness with non-myopic experts
- Title（参考訳）: 正真正当性に基づくノンレグレットインセンティブ対応オンライン学習
- Authors: Junpei Komiyama, Nishant A. Mehta, Ali Mortazavi,
- Abstract要約: 我々は、T$以上のラウンド、N$の戦略的専門家がそれぞれ予測をメカニズムに報告するオンライン予測設定を調査します。
いずれのラウンドでも、各専門家は結果に対する信念を持っているが、専門家は、その結果が選択される回数を最大化するために、レポートを選択することを望んでいる。
我々は、この設定において、初めて、完全に真実でないメカニズムを開発します。
- 参考スコア（独自算出の注目度）: 12.760453906939444
- License:
- Abstract: We study an online forecasting setting in which, over $T$ rounds, $N$ strategic experts each report a forecast to a mechanism, the mechanism selects one forecast, and then the outcome is revealed. In any given round, each expert has a belief about the outcome, but the expert wishes to select its report so as to maximize the total number of times it is selected. The goal of the mechanism is to obtain low belief regret: the difference between its cumulative loss (based on its selected forecasts) and the cumulative loss of the best expert in hindsight (as measured by the experts' beliefs). We consider exactly truthful mechanisms for non-myopic experts, meaning that truthfully reporting its belief strictly maximizes the expert's subjective probability of being selected in any future round. Even in the full-information setting, it is an open problem to obtain the first no-regret exactly truthful mechanism in this setting. We develop the first no-regret mechanism for this setting via an online extension of the Independent-Event Lotteries Forecasting Competition Mechanism (I-ELF). By viewing this online I-ELF as a novel instance of Follow the Perturbed Leader (FPL) with noise based on random walks with loss-dependent perturbations, we obtain $\tilde{O}(\sqrt{T N})$ regret. Our results are fueled by new tail bounds for Poisson binomial random variables that we develop. We extend our results to the bandit setting, where we give an exactly truthful mechanism obtaining $\tilde{O}(T^{2/3} N^{1/3})$ regret; this is the first no-regret result even among approximately truthful mechanisms.
- Abstract（参考訳）: 我々は、T$以上のラウンド、N$の戦略的専門家がそれぞれ予測をメカニズムに報告し、メカニズムが1つの予測を選択し、その結果が明らかになるオンライン予測設定について研究する。
いずれのラウンドでも、各専門家は結果に対する信念を持っているが、専門家は、その結果が選択される回数を最大化するために、レポートを選択することを望んでいる。
このメカニズムの目標は、その累積的損失(選択された予測に基づく)と、(専門家の信念によって測られるように)後見における最高の専門家の累積的損失(累積的損失)の差という、低い信念の後悔を得ることである。
したがって、真にその信念を報告することは、将来のラウンドにおいて専門家が選択される主観的確率を厳密に最大化することを意味する。
完全な情報設定であっても、この設定において最初の非回帰的真理的なメカニズムを得るのはオープンな問題である。
Independent-Event Lotteries Forecasting Competition Mechanism (I-ELF) のオンライン拡張を通じて、この設定のための最初のノンレグレットメカニズムを開発する。
このオンラインI-ELFは、損失依存摂動を伴うランダムウォークに基づくノイズを伴ってFPL(Follow the Perturbed Leader)の新たな例と見なすことで、$\tilde{O}(\sqrt{T N})$ regretを得る。
我々の結果は、ポアソン二項確率変数の新しい尾境界によって加速される。
我々はその結果をバンディット設定にまで拡張し、ここでは$\tilde{O}(T^{2/3} N^{1/3})$ regret を得る真正なメカニズムを与える。
関連論文リスト
- Fair Secretaries with Unfair Predictions [12.756552522270198]
予測値が少なくとも$maxOmega (1), 1 - O(epsilon)$倍の候補を受け入れることを約束しているにもかかわらず、アルゴリズムが最良の候補を受け入れる確率がゼロであることを示し、ここでは$epsilon$が予測誤差である。
私たちのアルゴリズムと分析は、既存の作業から分岐し、結果のいくつかを単純化/統一する、新たな"ペギング(pegging)"アイデアに基づいている。
論文 参考訳（メタデータ） (2024-11-15T00:23:59Z) - No-Regret Online Prediction with Strategic Experts [16.54912614895861]
オンラインバイナリ予測の一般化をエキスパートアドバイスフレームワークを用いて研究し、各ラウンドで、学習者は、Kドルの専門家のプールからmgeq 1ドルの専門家を選ぶことができる。
我々は、専門家が戦略的に行動し、彼らの信念を誤報することでアルゴリズムの予測への影響を最大化することを目的とした設定に焦点を当てる。
目標は,次の2つの要件を満たすアルゴリズムを設計することです。 1) $textitIncentive-compatible$: 専門家に信念を真実に報告させるインセンティブ,2) $textitNo-regret$: Achieve。
論文 参考訳（メタデータ） (2023-05-24T16:43:21Z) - Benefits of Permutation-Equivariance in Auction Mechanisms [90.42990121652956]
競売人の収益を最大化しつつ、競売人の過去の後悔を最小限にする競売メカニズムは、経済学において重要であるが複雑な問題である。
ニューラルネットワークによる最適なオークションメカニズムの学習を通じて、注目すべき進歩が達成されている。
論文 参考訳（メタデータ） (2022-10-11T16:13:25Z) - Random Rank: The One and Only Strategyproof and Proportionally Fair
Randomized Facility Location Mechanism [103.36492220921109]
我々は、強い比例性は動機が良く基本的な公理であるが、その性質を満たす決定論的戦略防御機構は存在しないことを示した。
次に、予測において強い比例性を満たすランダムランクと呼ばれるランダム化メカニズムを同定する。
我々の主な特徴はランダムランクを、普遍的真理性、普遍的匿名性、期待における強い比喩性を達成するユニークなメカニズムとして特徴づけている。
論文 参考訳（メタデータ） (2022-05-30T00:51:57Z) - No-Regret Learning with Unbounded Losses: The Case of Logarithmic
Pooling [12.933990572597583]
対数プール法(対数プール)として知られる基本的および実用的アグリゲーション法に焦点をあてる。
オンラインの対戦環境において,最適なパラメータ集合を学習する問題を考察する。
本稿では,O(sqrtT log T)$experied regretに達する方法で,専門家の重みを学習するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-02-22T22:27:25Z) - Are You Smarter Than a Random Expert? The Robust Aggregation of
Substitutable Signals [14.03122229316614]
本稿では,幅広い情報構造から専門家の知識を逆選択する文脈において,予測集約の研究を開始する。
投射的代替条件の下では、専門家の予測の平均値を取得することは、ランダムな専門家を信頼する戦略によって大幅に改善される。
本研究では, 専門家の予測を平均化し, 一定の要因によって前者から遠ざかることで平均を極端に推し進めることにより, 集積器の性能保証は, 事前の知識がなくても実現可能であることを示す。
論文 参考訳（メタデータ） (2021-11-04T20:50:30Z) - Efficient Competitions and Online Learning with Strategic Forecasters [10.772308279491202]
Witkowskiet al。
この問題を特定し、勝者を選ぶための真正なメカニズムであるELFを提案した。
ELFは、確率の高い準最適予測器を選択するために、$Theta(nlog n)$イベントやテストデータポイントを必要とする。
標準オンライン学習アルゴリズムは、$O(log(n) / epsilon2)$イベントのみを使用して$epsilon$-optimal予測子を選択します。
論文 参考訳（メタデータ） (2021-02-16T18:48:37Z) - Right Decisions from Wrong Predictions: A Mechanism Design Alternative
to Individual Calibration [107.15813002403905]
意思決定者は、しばしば不完全な確率予測に頼る必要がある。
本稿では,予測ユーティリティが実際に取得したユーティリティと一致することを保証する補償機構を提案する。
本研究では、乗客が飛行遅延確率に基づいて、個々の旅行計画をどのように確実に最適化できるかを示すアプリケーションを示す。
論文 参考訳（メタデータ） (2020-11-15T08:22:39Z) - VCG Mechanism Design with Unknown Agent Values under Stochastic Bandit
Feedback [104.06766271716774]
本研究では,エージェントが自己の価値を知らない場合に,マルチラウンドの福祉最大化機構設計問題について検討する。
まず、福祉に対する後悔の3つの概念、各エージェントの個々のユーティリティ、メカニズムの3つの概念を定義します。
当社のフレームワークは価格体系を柔軟に制御し、エージェントと販売者の後悔のトレードオフを可能にする。
論文 参考訳（メタデータ） (2020-04-19T18:00:58Z) - Malicious Experts versus the multiplicative weights algorithm in online
prediction [85.62472761361107]
2人の専門家と1人の予測者による予測問題を考える。
専門家の一人が正直で、各ラウンドで確率$mu$で正しい予測をしていると仮定する。
もう一つは悪意のあるもので、各ラウンドで真の結果を知り、予測者の損失を最大化するために予測を行う。
論文 参考訳（メタデータ） (2020-03-18T20:12:08Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。