論文の概要: On the price of exact truthfulness in incentive-compatible online learning with bandit feedback: A regret lower bound for WSU-UX
- arxiv url: http://arxiv.org/abs/2404.05155v1
- Date: Mon, 8 Apr 2024 02:41:32 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-09 15:43:25.312231
- Title: On the price of exact truthfulness in incentive-compatible online learning with bandit feedback: A regret lower bound for WSU-UX
- Title（参考訳）: 包括的フィードバックによるインセンティブに適合したオンライン学習における真偽の価格について:WSU-UXに対する後悔の念
- Authors: Ali Mortazavi, Junhao Lin, Nishant A. Mehta,
- Abstract要約: 古典的な予測ゲームと専門的なアドバイスと二進的な結果の1つの見方では、それぞれの専門家は反対に選択された信念を維持している。
本稿では、この問題の戦略的なバリエーションとして、自己中心的な専門家(レコメンデーション・シーキング)が紹介されている。
損失列の明示的な構成により、アルゴリズムは最悪の場合$Omega(T2/3)$lowboundに苦しむことを示した。
- 参考スコア（独自算出の注目度）: 8.861995276194435
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In one view of the classical game of prediction with expert advice with binary outcomes, in each round, each expert maintains an adversarially chosen belief and honestly reports this belief. We consider a recently introduced, strategic variant of this problem with selfish (reputation-seeking) experts, where each expert strategically reports in order to maximize their expected future reputation based on their belief. In this work, our goal is to design an algorithm for the selfish experts problem that is incentive-compatible (IC, or \emph{truthful}), meaning each expert's best strategy is to report truthfully, while also ensuring the algorithm enjoys sublinear regret with respect to the expert with the best belief. Freeman et al. (2020) recently studied this problem in the full information and bandit settings and obtained truthful, no-regret algorithms by leveraging prior work on wagering mechanisms. While their results under full information match the minimax rate for the classical ("honest experts") problem, the best-known regret for their bandit algorithm WSU-UX is $O(T^{2/3})$, which does not match the minimax rate for the classical ("honest bandits") setting. It was unclear whether the higher regret was an artifact of their analysis or a limitation of WSU-UX. We show, via explicit construction of loss sequences, that the algorithm suffers a worst-case $\Omega(T^{2/3})$ lower bound. Left open is the possibility that a different IC algorithm obtains $O(\sqrt{T})$ regret. Yet, WSU-UX was a natural choice for such an algorithm owing to the limited design room for IC algorithms in this setting.
- Abstract（参考訳）: 古典的な予測ゲームと専門的な助言と二進的な結果の1つの観点では、各専門家は反対に選択された信念を維持し、この信念を正直に報告する。
本稿では,この問題の新たな戦略的バリエーションとして,各専門家が,自らの信念に基づいた将来的な評価を最大化するために,戦略的に報告する自己資本的(レコメンデーション・シーキング)の専門家が検討する。
本研究の目的は、インセンティブに相応しい利己的な専門家問題(IC、または「emph{truthful}」)のためのアルゴリズムを設計することであり、すなわち、各専門家の最善の戦略は、真に報告することであり、同時に、アルゴリズムが、最高の信念を持つ専門家に対して、サブリニアな後悔を楽しむことを確実にすることである。
Freeman et al (2020) は、最近この問題を情報と盗賊の設定で研究し、賃金制度に関する先行研究を生かして真面目で非相対的なアルゴリズムを得た。
完全な情報に基づく結果が古典的(最高の専門家)問題のミニマックスレートと一致する一方で、バンドイットアルゴリズムWSU-UXの最もよく知られた後悔は$O(T^{2/3})$であり、古典的(最高のバンドイット)設定のミニマックスレートとは一致しない。
高い後悔が彼らの分析の成果であったのか、あるいはWSU-UXの限界だったのかは不明だった。
損失列の明示的な構成を通して、アルゴリズムは最悪の場合$\Omega(T^{2/3})$low boundに苦しむことを示した。
左開は、異なるICアルゴリズムが$O(\sqrt{T})$ regretを得る可能性である。
しかし、この設定では、ICアルゴリズムの限られた設計スペースのため、WSU-UXはそのようなアルゴリズムにとって自然な選択であった。
関連論文リスト
- Incentive-compatible Bandits: Importance Weighting No More [14.344759978208957]
本稿では,包括的フィードバックによるインセンティブ適合型オンライン学習の課題について検討する。
この研究では、最初のインセンティブに適合するアルゴリズムを提案し、$O(sqrtKT)$ regret bounds を楽しむ。
論文 参考訳（メタデータ） (2024-05-10T13:57:13Z) - Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedback [58.66941279460248]
人からのフィードバックから学ぶことは、大言語モデル(LLM)のような生成モデルを調整する上で重要な役割を果たす
本稿では,本問題の領域内モデルについて考察する。-文脈的デュエルバンディットと敵対的フィードバックを併用し,真の嗜好ラベルを敵によって反転させることができる。
本稿では,不確実性重み付き最大推定に基づく頑健なコンテキストデュエルバンドイット(アルゴ)を提案する。
論文 参考訳（メタデータ） (2024-04-16T17:59:55Z) - Feel-Good Thompson Sampling for Contextual Dueling Bandits [49.450050682705026]
FGTS.CDBという名前のトンプソンサンプリングアルゴリズムを提案する。
われわれのアルゴリズムの核心は、デュエルバンディットに適した新しいFeel-Good探索用語である。
我々のアルゴリズムは最小限の誤差、すなわち $tildemathcalO(dsqrt T)$, $d$ はモデル次元、$T$ は時間水平線である。
論文 参考訳（メタデータ） (2024-04-09T04:45:18Z) - 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) - Streaming Algorithms for Learning with Experts: Deterministic Versus
Robust [62.98860182111096]
エキスパート問題を伴うオンライン学習では、アルゴリズムは、T$day(または時間)ごとに結果を予測する必要がある。
目標は最小限のコストで予測を行うことだ。
最良専門家が$M$の誤りを犯したとき、後悔する$R$を達成するような決定論的アルゴリズムに対して、$widetildeOmegaleft(fracnMRTright)$の空間下界を示す。
論文 参考訳（メタデータ） (2023-03-03T04:39:53Z) - Private Online Prediction from Experts: Separations and Faster Rates [74.52487417350221]
専門家によるオンライン予測は機械学習の基本的な問題であり、いくつかの研究がプライバシーの制約の下でこの問題を研究している。
本研究では,非適応的敵に対する最良な既存アルゴリズムの残差を克服する新たなアルゴリズムを提案し,解析する。
論文 参考訳（メタデータ） (2022-10-24T18:40:19Z) - Efficient and Optimal Algorithms for Contextual Dueling Bandits under
Realizability [59.81339109121384]
我々は,学習者が文脈情報を用いて2つの決定を下す連続的な決定設定であるK$コンテキストデュエルバンディット問題について検討するが,一方の判断が他方よりも優れていることを示唆する強調基準に基づくフィードバックのみを観察する。
提案手法は, 最善応答後悔という新たな概念に対して, 最善応答後悔に対する最適後悔率を実現するアルゴリズムである。
論文 参考訳（メタデータ） (2021-11-24T07:14:57Z) - Adapting to Misspecification in Contextual Bandits [82.55565343668246]
我々は、$varepsilon$-misspecified contextual banditsに対して、新しいオラクル効率アルゴリズム群を導入する。
我々は、未知の不特定値に対して最適な$O(dsqrtT + varepsilonsqrtdT)$ regret boundを達成する最初のアルゴリズムを得る。
論文 参考訳（メタデータ） (2021-07-12T21:30:41Z) - Optimal anytime regret with two experts [11.959180302329358]
我々は、いつでも後悔を最小限に抑えるために、最初のミニマックス最適アルゴリズムを設計する。
このアルゴリズムは、計算のアイデアを用いて解決した後悔問題の連続的な類似を考慮し、設計する。
論文 参考訳（メタデータ） (2020-02-20T20:04:32Z) - Regret Minimization in Stochastic Contextual Dueling Bandits [40.17224226373741]
我々は、コンテキスト設定において、$K$武装デュエルバンディットの問題を考察する。
提案手法は, それぞれ, 後悔の保証を施した2つのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-02-20T06:36:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。