論文の概要: Deceptive Exploration in Multi-armed Bandits

• arxiv url: http://arxiv.org/abs/2510.08794v1
• Date: Thu, 09 Oct 2025 20:15:52 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-14 00:38:47.70307
• Title: Deceptive Exploration in Multi-armed Bandits
• Title（参考訳）: マルチアームバンドにおける知覚探索
• Authors: I. Arda Vurankaya, Mustafa O. Karabag, Wesley A. Suttle, Jesse Milzman, David Fridovich-Keil, Ufuk Topcu,
• Abstract要約: 我々は、各アームがパブリックかつプライベートな報酬分布を持つマルチアームのバンディット設定について検討する。 観察者は、公開報酬に応じて、エージェントがトンプソンサンプリングに従うことを期待するが、偽装エージェントは、気づかれることなく、最高のプライベートアームを素早く特定することを目的としている。
• 参考スコア（独自算出の注目度）: 22.14260167840733
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider a multi-armed bandit setting in which each arm has a public and a private reward distribution. An observer expects an agent to follow Thompson Sampling according to the public rewards, however, the deceptive agent aims to quickly identify the best private arm without being noticed. The observer can observe the public rewards and the pulled arms, but not the private rewards. The agent, on the other hand, observes both the public and private rewards. We formalize detectability as a stepwise Kullback-Leibler (KL) divergence constraint between the actual pull probabilities used by the agent and the anticipated pull probabilities by the observer. We model successful pulling of public suboptimal arms as a % Bernoulli process where the success probability decreases with each successful pull, and show these pulls can happen at most at a $\Theta(\sqrt{T}) $ rate under the KL constraint. We then formulate a maximin problem based on public and private means, whose solution characterizes the optimal error exponent for best private arm identification. We finally propose an algorithm inspired by top-two algorithms. This algorithm naturally adapts its exploration according to the hardness of pulling arms based on the public suboptimality gaps. We provide numerical examples illustrating the $\Theta(\sqrt{T}) $ rate and the behavior of the proposed algorithm.
• Abstract（参考訳）: 我々は、各アームがパブリックかつプライベートな報酬分布を持つマルチアームのバンディット設定について検討する。 観察者は、公開報酬に応じて、エージェントがトンプソンサンプリングに従うことを期待するが、偽装エージェントは、気づかれることなく、最高のプライベートアームを素早く特定することを目的としている。 オブザーバーは公衆の報酬と引き抜かれた武器を観察できるが、個人の報酬は観察できない。 一方、エージェントは、公的および私的な報酬の両方を観察します。 我々は、エージェントが使用する実際のプル確率と観測者の期待するプル確率との間の段階的にクルバック・リーブラー(KL)の分散制約として検出可能性を定式化する。 我々は、成功確率が各成功プルで減少するベルヌーイ過程として公共の最適腕の引き抜きの成功をモデル化し、これらの引抜きがKL制約の下で少なくとも$\Theta(\sqrt{T})$レートで起こり得ることを示す。 次に, 最適誤差指数を特徴付ける解法として, パブリックおよびプライベートな手段に基づく最大誤差問題を定式化する。 最終的にトップ2アルゴリズムにインスパイアされたアルゴリズムを提案する。 このアルゴリズムは、公共の最適度差に基づいて腕を引っ張ることの難しさに応じて自然に探索に適応する。 本稿では,$\Theta(\sqrt{T})$レートと提案アルゴリズムの挙動を示す数値例を示す。

関連論文リスト

• Heterogeneous Multi-Agent Bandits with Parsimonious Hints [12.709437751500353]
  異種多腕包帯問題 (HMA2B) について検討し, エージェントは腕を引っ張るだけでなく, 低コストの観測(隠れ)をクエリできる。 このフレームワークでは、M$エージェントはそれぞれ$K$のアームにユニークな報酬分布を持ち、$T$のラウンドでは、他のエージェントが腕を引っ張らない場合にのみ引き出すアームの報酬を観察することができる。 目標は、腕を引っ張ることなく必要最小限のヒントをクエリし、時間に依存しない後悔を達成することで、全ユーティリティを最大化することである。
  論文  参考訳（メタデータ） (2025-02-22T07:46:41Z)
• An Algorithm for Fixed Budget Best Arm Identification with Combinatorial Exploration [3.9901365062418312]
  我々は、K$$armed banditフレームワークにおける最適な腕識別問題を考察する。 エージェントは1つのアームではなく、各タイムスロットでアームのサブセットをプレイすることができる。 我々は、$log K$グループを構築し、最適なアームの存在を検出するための確率比テストを実行するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-02-03T15:10:08Z)
• Optimal Multi-Objective Best Arm Identification with Fixed Confidence [62.36929749450298]
  我々は、各アームが選択時にM$Dのベクトル報酬を得られる多腕バンディット設定を考える。 最終的なゴールは、最も短い(予想される)時間において、エラーの確率の上限に従属する全ての目的の最良のアームを特定することである。 本稿では,各ステップでアームをサンプリングするために,エミュロゲート比例という新しいアイデアを用いたアルゴリズムを提案し,各ステップにおける最大最小最適化問題を解く必要をなくした。
  論文  参考訳（メタデータ） (2025-01-23T12:28:09Z)
• Multi-agent Multi-armed Bandits with Stochastic Sharable Arm Capacities [69.34646544774161]
  我々は、各アームへのリクエストの到着とプレイヤーへのリクエストの割り当てポリシーをキャプチャするマルチプレイヤーマルチアーム・バンディット(MAB)モデルの新しいバリエーションを定式化する。 課題は、プレイヤーが最適な腕引きプロファイルに従って腕を選択するように分散学習アルゴリズムを設計する方法である。 我々は,Mラウンドのみの最適腕引きプロファイルにおいて,プレイヤーがコンセンサスに達することを保証した反復分散アルゴリズムを設計する。
  論文  参考訳（メタデータ） (2024-08-20T13:57:00Z)
• Best Arm Identification in Bandits with Limited Precision Sampling [14.011731120150124]
  学習者が腕選択の精度に限界がある多腕バンディット問題の変種における最適な腕識別について検討する。 非特異な最適アロケーションを処理するために,修正されたトラッキングベースアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-05-10T12:07:48Z)
• Best arm identification in rare events [0.43012765978447565]
  このフレームワークのキーとなる応用は、オンライン広告において、広告のクリックレートが1パーセントのごく一部であり、売上への最終的な転換率は高い利益であるが、再びクリックレートのごく一部になるかもしれない。 近年,BAI問題に対するアルゴリズムが開発され,正確なアーム選択に関する統計的保証を提供しながら,サンプルの複雑さを最小化している。 両腕の報酬過程は複合ポアソン法によりよく近似され、より高速なアルゴリズムに到達し、サンプルの複雑さはわずかに増大する。
  論文  参考訳（メタデータ） (2023-03-14T04:51:24Z)
• Bandit Social Learning: Exploration under Myopic Behavior [54.767961587919075]
  オンラインプラットフォーム上でのレビューによって動機付けられた社会学習のダイナミクスについて検討する。 エージェントはまとめて単純なマルチアームのバンディットプロトコルに従うが、各エージェントは探索を伴わずにミオプティカルに振る舞う。 このような振る舞いに対して,スターク学習の失敗を導出し,好意的な結果を提供する。
  論文  参考訳（メタデータ） (2023-02-15T01:57:57Z)
• Best Arm Identification in Restless Markov Multi-Armed Bandits [85.55466536537293]
  マルチアームバンディット環境における最適な腕を特定することの問題点について検討する。 決定エンティティは、上限誤差確率を条件として、ベストアームのインデックスをできるだけ早く見つけることを希望する。 このポリシーは、$R$に依存する上限を達成し、$Rtoinfty$として単調に増加しないことを示す。
  論文  参考訳（メタデータ） (2022-03-29T04:58:04Z)

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

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