論文の概要: 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): 腕の選択が利己的なエージェントによって制御されるマルチアームのバンディットのバージョンであり、アルゴリズムは推奨事項のみを発行できる。 アルゴリズムは情報の流れを制御し、情報非対称性は探索するエージェントにインセンティブを与える。 先行研究は、ベイズ先行法により任意に大きくなる乗法的要因までの最適な後悔率を達成し、武器数で指数関数的にスケールする。 それぞれの腕をサンプリングするより基本的な問題は、同じ要因にぶつかる。 我々は、インセンティブの価格に焦点を合わせ、インセンティブに適合するため、広く解釈された、パフォーマンスの損失である。 標準バンディットアルゴリズムであるトンプソンサンプリングが十分多くのデータポイントで初期化されるとインセンティブ互換であることが証明される。 したがって、インセンティブによるパフォーマンス損失は、これらのデータポイントの収集時に初期ラウンドに制限される。 問題は、主にサンプルの複雑さに還元される: ラウンドがいくつ必要か? この問題に対処し、上と下の境界を一致させ、様々な行でインスタンス化する。 典型的には、最適なサンプル複雑性は、腕の数の多項式と「信念の強さ」の指数関数である。

関連論文リスト

• 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 Exploration with Linear Contexts and Combinatorial Actions [9.15749739027059]
  インセンティブ付きバンディット探索では、腕の選択は推奨され、ベイズ的なインセンティブと互換性が求められる。 最近の研究は、十分な初期サンプルを収集した後、人気のあるトンプソンサンプリングアルゴリズムがインセンティブ互換になる、という一定の独立性の仮定の下で示されている。 線形包帯に対してこの結果の類似性を与え、そこでは前者の独立性を自然凸条件に置き換える。
  論文  参考訳（メタデータ） (2023-06-03T03:30:42Z)
• 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)
• Resource Allocation in Multi-armed Bandit Exploration: Overcoming Sublinear Scaling with Adaptive Parallelism [107.48538091418412]
  腕の引っ張りに様々な量の資源を割り当てることができる分割可能な資源にアクセス可能な場合,マルチアームの帯状地における探索について検討する。 特に、分散コンピューティングリソースの割り当てに重点を置いており、プル毎により多くのリソースを割り当てることで、結果をより早く得ることができます。
  論文  参考訳（メタデータ） (2020-10-31T18:19:29Z)
• Quantile Multi-Armed Bandits: Optimal Best-Arm Identification and a Differentially Private Scheme [16.1694012177079]
  我々は,多腕バンディットにおける最高の武器識別問題,潜在的に私的な報酬について検討する。 ゴールは、固定された所定のレベルで、最も高い定量値を持つ腕を特定することである。 このアルゴリズムは$delta$-PACであり,サンプルの複雑さを特徴付ける。
  論文  参考訳（メタデータ） (2020-06-11T20:23:43Z)

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

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