論文の概要: Incentive-compatible Bandits: Importance Weighting No More
- arxiv url: http://arxiv.org/abs/2405.06480v1
- Date: Fri, 10 May 2024 13:57:13 GMT
- ステータス: 処理完了
- システム内更新日: 2024-05-13 15:38:11.201760
- Title: Incentive-compatible Bandits: Importance Weighting No More
- Title（参考訳）: インセンティブ互換バンド:重要度がなくなる
- Authors: Julian Zimmert, Teodor V. Marinov,
- Abstract要約: 本稿では,包括的フィードバックによるインセンティブ適合型オンライン学習の課題について検討する。
この研究では、最初のインセンティブに適合するアルゴリズムを提案し、$O(sqrtKT)$ regret bounds を楽しむ。
- 参考スコア（独自算出の注目度）: 14.344759978208957
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the problem of incentive-compatible online learning with bandit feedback. In this class of problems, the experts are self-interested agents who might misrepresent their preferences with the goal of being selected most often. The goal is to devise algorithms which are simultaneously incentive-compatible, that is the experts are incentivised to report their true preferences, and have no regret with respect to the preferences of the best fixed expert in hindsight. \citet{freeman2020no} propose an algorithm in the full information setting with optimal $O(\sqrt{T \log(K)})$ regret and $O(T^{2/3}(K\log(K))^{1/3})$ regret in the bandit setting. In this work we propose the first incentive-compatible algorithms that enjoy $O(\sqrt{KT})$ regret bounds. We further demonstrate how simple loss-biasing allows the algorithm proposed in Freeman et al. 2020 to enjoy $\tilde O(\sqrt{KT})$ regret. As a byproduct of our approach we obtain the first bandit algorithm with nearly optimal regret bounds in the adversarial setting which works entirely on the observed loss sequence without the need for importance-weighted estimators. Finally, we provide an incentive-compatible algorithm that enjoys asymptotically optimal best-of-both-worlds regret guarantees, i.e., logarithmic regret in the stochastic regime as well as worst-case $O(\sqrt{KT})$ regret.
- Abstract（参考訳）: 本稿では,包括的フィードバックによるインセンティブ適合型オンライン学習の課題について検討する。
この種の問題では、専門家は自己関心のあるエージェントであり、最も頻繁に選ばれることを目標に、自分の好みを誤って表現するかもしれない。
目標は、同時にインセンティブに適合するアルゴリズムを考案することであり、これは専門家が真の嗜好を報告することにインセンティブを与え、後見において最高の固定専門家の嗜好に関して後悔することはない。
\citet{freeman 2020no} は、最適$O(\sqrt{T \log(K)})$ regret と $O(T^{2/3}(K\log(K))^{1/3})$ regret の完全な情報設定におけるアルゴリズムを提案する。
この研究では、最初のインセンティブ互換アルゴリズムを提案し、$O(\sqrt{KT})$ regret bounds を楽しむ。
さらに、単純な損失バイアスによって、Freemanらによって提案されたアルゴリズムが$\tilde O(\sqrt{KT})$ regretを楽しむことを実証する。
提案手法の副産物として, 重要重み付き推定器を必要とせず, 観測された損失列に完全に依存する逆数設定において, ほぼ最適な後悔境界を持つ最初のバンディットアルゴリズムを得る。
最後に、確率的状態における対数的後悔と最悪の$O(\sqrt{KT})$後悔という、漸近的に最適な両世界最善の後悔の保証を享受するインセンティブ互換アルゴリズムを提供する。
関連論文リスト
- 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) - Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。
SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
論文 参考訳（メタデータ） (2023-12-13T11:08:25Z) - Private Online Prediction from Experts: Separations and Faster Rates [74.52487417350221]
専門家によるオンライン予測は機械学習の基本的な問題であり、いくつかの研究がプライバシーの制約の下でこの問題を研究している。
本研究では,非適応的敵に対する最良な既存アルゴリズムの残差を克服する新たなアルゴリズムを提案し,解析する。
論文 参考訳（メタデータ） (2022-10-24T18:40:19Z) - Leveraging Initial Hints for Free in Stochastic Linear Bandits [38.58449930961883]
本研究では,学習者の事前知識を付加した帯域フィードバックによる最適化の設定について,最適行動の最初のヒントとして検討する。
我々は、このヒントを用いて、ヒントが正確である場合にその後悔を$tilde O(sqrtT)$に改善する新しいアルゴリズムを提案する。
おそらく驚くべきことに、私たちの研究は、最悪のパフォーマンスを犠牲にすることなく、ヒントを活用することで、証明可能な利益が得られていることを示している。
論文 参考訳（メタデータ） (2022-03-08T18:48:55Z) - Optimal and Efficient Dynamic Regret Algorithms for Non-Stationary
Dueling Bandits [27.279654173896372]
我々は,非定常的あるいは時間的に異なる選好の下で,$K$のDueling Banditsにおける空力的後悔の最小化問題について検討した。
これは、エージェントが各ラウンドで一対のアイテムを選択し、このペアに対する相対的な二項のウィンロスフィードバックのみを観察するオンライン学習設定である。
論文 参考訳（メタデータ） (2021-11-06T16:46:55Z) - Multinomial Logit Contextual Bandits: Provable Optimality and
Practicality [15.533842336139063]
パラメータが不明な多項式ロギット(MNL)選択モデルによってユーザ選択が与えられる順序選択選択問題を検討する。
本稿では,このMNLコンテクストバンディットに対する高信頼境界に基づくアルゴリズムを提案する。
本稿では,アルゴリズムの単純な変種が,幅広い重要なアプリケーションに対して最適な後悔を与えることを示す。
論文 参考訳（メタデータ） (2021-03-25T15:42:25Z) - Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。
楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-17T22:32:19Z) - Corralling Stochastic Bandit Algorithms [54.10645564702416]
相関アルゴリズムの後悔は、最も報酬の高い腕を含む最高のアルゴリズムの後悔よりも悪くはないことを示す。
最高報酬と他の報酬の差は、最高報酬と他の報酬の差に依存することを示す。
論文 参考訳（メタデータ） (2020-06-16T15:33:12Z) - Improved Sleeping Bandits with Stochastic Actions Sets and Adversarial
Rewards [59.559028338399855]
我々は,行動セットと敵意の報酬を伴って睡眠中の盗賊の問題を考察する。
本稿では,EXP3にインスパイアされた新しい計算効率のよいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-04-14T00:41:26Z) - Model Selection in Contextual Stochastic Bandit Problems [51.94632035240787]
基本アルゴリズムを選択できるメタアルゴリズムを開発した。
基本アルゴリズムの1つが$O(sqrtT)$後悔している場合でも、一般的には$Omega(sqrtT)$後悔よりも良いものを得ることはできません。
論文 参考訳（メタデータ） (2020-03-03T18:46:34Z) - Regret Minimization in Stochastic Contextual Dueling Bandits [40.17224226373741]
我々は、コンテキスト設定において、$K$武装デュエルバンディットの問題を考察する。
提案手法は, それぞれ, 後悔の保証を施した2つのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-02-20T06:36:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。