論文の概要: The Price of Incentivizing Exploration: A Characterization via Thompson Sampling and Sample Complexity

• arxiv url: http://arxiv.org/abs/2002.00558v6
• Date: Sun, 12 Jun 2022 19:54:20 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-04 09:33:16.536376
• Title: The Price of Incentivizing Exploration: A Characterization via Thompson Sampling and Sample Complexity
• Title（参考訳）: インセンティブ化探索の価格:トンプソンサンプリングとサンプル複雑度による評価
• Authors: Mark Sellke, Aleksandrs Slivkins
• Abstract要約: インセンティブ付き探索(Incentivized Exploring)は、武器の選択を自給自足エージェントによって制御するマルチアーム・バンディットのバージョンである。 我々は、インセンティブの価格に焦点を合わせ、インセンティブの適合性のために、広く解釈された、パフォーマンスの喪失が引き起こされる。
• 参考スコア（独自算出の注目度）: 83.81297078039836
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider incentivized exploration: a version of multi-armed bandits where the choice of arms is controlled by self-interested agents, and the algorithm can only issue recommendations. The algorithm controls the flow of information, and the information asymmetry can incentivize the agents to explore. Prior work achieves optimal regret rates up to multiplicative factors that become arbitrarily large depending on the Bayesian priors, and scale exponentially in the number of arms. A more basic problem of sampling each arm once runs into similar factors. We focus on the price of incentives: the loss in performance, broadly construed, incurred for the sake of incentive-compatibility. We prove that Thompson Sampling, a standard bandit algorithm, is incentive-compatible if initialized with sufficiently many data points. The performance loss due to incentives is therefore limited to the initial rounds when these data points are collected. The problem is largely reduced to that of sample complexity: how many rounds are needed? We address this question, providing matching upper and lower bounds and instantiating them in various corollaries. Typically, the optimal sample complexity is polynomial in the number of arms and exponential in the "strength of beliefs".
• Abstract（参考訳）: 我々はインセンティブ付き探索 (incentivized exploration): 腕の選択が利己的なエージェントによって制御されるマルチアームのバンディットのバージョンであり、アルゴリズムは推奨事項のみを発行できる。 アルゴリズムは情報の流れを制御し、情報非対称性は探索するエージェントにインセンティブを与える。 先行研究は、ベイズ先行法により任意に大きくなる乗法的要因までの最適な後悔率を達成し、武器数で指数関数的にスケールする。 それぞれの腕をサンプリングするより基本的な問題は、同じ要因にぶつかる。 我々は、インセンティブの価格に焦点を合わせ、インセンティブに適合するため、広く解釈された、パフォーマンスの損失である。 標準バンディットアルゴリズムであるトンプソンサンプリングが十分多くのデータポイントで初期化されるとインセンティブ互換であることが証明される。 したがって、インセンティブによるパフォーマンス損失は、これらのデータポイントの収集時に初期ラウンドに制限される。 問題は、主にサンプルの複雑さに還元される: ラウンドがいくつ必要か? この問題に対処し、上と下の境界を一致させ、様々な行でインスタンス化する。 典型的には、最適なサンプル複雑性は、腕の数の多項式と「信念の強さ」の指数関数である。

関連論文リスト

• The Batch Complexity of Bandit Pure Exploration [10.036727981085223]
  マルチアームバンディットにおける純粋な探索問題では、アルゴリズムは武器を反復的にサンプリングし、できるだけ早く停止し、武器分布に関する質問に対する正しい答えを返すべきである。 私たちは、バッチ化メソッドに興味を持ち、サンプルの振る舞いを数回だけ、観察のバッチ間で変更します。 純粋な探索タスクに対して,任意のサンプル効率アルゴリズムが使用するバッチ数に対して,インスタンス依存の低いバウンダリを与える。
  論文  参考訳（メタデータ） (2025-02-03T15:03:45Z)
• Optimal Multi-Objective Best Arm Identification with Fixed Confidence [62.36929749450298]
  我々は、各アームが選択時にM$Dのベクトル報酬を得られる多腕バンディット設定を考える。 最終的なゴールは、最も短い(予想される)時間において、エラーの確率の上限に従属する全ての目的の最良のアームを特定することである。 本稿では,各ステップでアームをサンプリングするために,エミュロゲート比例という新しいアイデアを用いたアルゴリズムを提案し,各ステップにおける最大最小最適化問題を解く必要をなくした。
  論文  参考訳（メタデータ） (2025-01-23T12:28:09Z)
• Best Arm Identification in Batched Multi-armed Bandit Problems [3.908867017036043]
  近年のマルチアームバンディット問題は、多くの実生活シナリオにおいて、腕をバッチでサンプリングする必要がある。 最適な腕の識別に異なる理論的設定の目的を組み込むことができる一般的な線形プログラミングフレームワークを導入する。 数値実験により,UCB型サンプリング法やトンプソン型サンプリング法と比較して,アルゴリズムの性能も良好であることを示した。
  論文  参考訳（メタデータ） (2023-12-21T14:16:38Z)
• Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
  我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。 特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
  論文  参考訳（メタデータ） (2023-12-19T13:17:43Z)
• Thompson Exploration with Best Challenger Rule in Best Arm Identification [66.33448474838342]
  本稿では,バンドイットフレームワークにおける固定信頼度最良腕識別問題について検討する。 我々は、トンプソンサンプリングと、ベストチャレンジャールールとして知られる計算効率の良いアプローチを組み合わせた新しいポリシーを提案する。
  論文  参考訳（メタデータ） (2023-10-01T01:37:02Z)
• Incentivizing Combinatorial Bandit Exploration [87.08827496301839]
  自己関心のあるユーザに対してレコメンデーションシステムでアクションを推奨するバンディットアルゴリズムを考える。 ユーザーは他のアクションを自由に選択でき、アルゴリズムの推奨に従うためにインセンティブを得る必要がある。 ユーザは悪用を好むが、アルゴリズムは、前のユーザから収集した情報を活用することで、探索にインセンティブを与えることができる。
  論文  参考訳（メタデータ） (2022-06-01T13:46:25Z)
• Optimal Clustering with Bandit Feedback [57.672609011609886]
  本稿では,バンディットフィードバックを用いたオンラインクラスタリングの問題点について考察する。 これは、NPハード重み付きクラスタリング問題をサブルーチンとして解決する必要性を回避するための、シーケンシャルなテストのための新しい停止規則を含む。 合成および実世界のデータセットの広範なシミュレーションを通して、BOCの性能は下界と一致し、非適応的ベースラインアルゴリズムよりも大幅に優れることを示す。
  論文  参考訳（メタデータ） (2022-02-09T06:05:05Z)
• Adaptive Algorithms for Multi-armed Bandit with Composite and Anonymous Feedback [32.62857394584907]
  複合および匿名フィードバックによるマルチアームバンディット(MAB)問題を研究する。 本稿では,逆の場合と非逆の場合の適応アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-12-13T12:25:41Z)
• Quantile Multi-Armed Bandits: Optimal Best-Arm Identification and a Differentially Private Scheme [16.1694012177079]
  我々は,多腕バンディットにおける最高の武器識別問題,潜在的に私的な報酬について検討する。 ゴールは、固定された所定のレベルで、最も高い定量値を持つ腕を特定することである。 このアルゴリズムは$delta$-PACであり,サンプルの複雑さを特徴付ける。
  論文  参考訳（メタデータ） (2020-06-11T20:23:43Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。