論文の概要: Analysis of Search Heuristics in the Multi-Armed Bandit Setting

• arxiv url: http://arxiv.org/abs/2604.08109v1
• Date: Thu, 09 Apr 2026 11:27:59 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-10 18:34:05.8819
• Title: Analysis of Search Heuristics in the Multi-Armed Bandit Setting
• Title（参考訳）: 多要素帯域設定における探索ヒューリスティックの解析
• Authors: Jasmin Brandt, Barbara Hammer, Timo Kötzing, Jurek Sander,
• Abstract要約: 我々は,従来のマルチアーメッド・バンドの設定を,異なる探索によって行われる探索・探索のトレードオフを理解するために検討する。 進化的アルゴリズムはCondorcetの勝者を特定するのにかなり役立ちません。
• 参考スコア（独自算出の注目度）: 6.730459235906337
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider the classic Multi-Armed Bandit setting to understand the exploration/exploitation tradeoffs made by different search heuristics. Since many search heuristics work by comparing different options (in evolutionary algorithms called "individuals"; in the Bandit literature called "arms"), we work with the "Dueling Bandits" setting. In each iteration, a comparison between different arms can be made; in the binary stochastic setting, each arm has a fixed winning probability against any other arm. A Condorcet winner is any arm that beats every other arm with a probability strictly higher than $1/2$. We show that evolutionary algorithms are rather bad at identifying the Condorcet winner: Even if the Condorcet winner beats every other arm with a probability $1-p$, the (1+1) EA, in its stationary distribution, chooses the Condorcet winner only with constant probability if $p=Ω(1/n)$. By contrast, we show that a simple EDA (based on the Max-Min Ant System with iteration-best update) will choose the Condorcet winner in its maintained distribution with probability $1-Θ(p)$. As a remedy for the (1+1) EA, we show how repeated duels can significantly boost the probability of the Condorcet winner in the stationary distribution.
• Abstract（参考訳）: 従来のマルチアーメッド・バンディット・セッティングは,探索ヒューリスティックスの違いによる探索・探索のトレードオフを理解するのに有用である。 多くの探索ヒューリスティックスは、異なる選択肢(「個人的」と呼ばれる進化的アルゴリズムや「武器」と呼ばれるバンディットの文献)を比較して機能するため、我々は「Dueling Bandits」という設定で作業する。 各イテレーションでは、異なるアームの比較が可能であり、二進確率設定では、各アームは他のどのアームに対しても一定の勝利確率を持つ。 コンドルチェットの勝者は、全ての腕を1/2ドル以上の確率で打ち負かすあらゆる腕である。 仮にコンドルチェットの勝者が1-p$の確率で他の全てのアームを破ったとしても、 (1+1) EAはその定常分布において、$p=Ω(1/n)$の確率でのみコンドルチェットの勝者を選択する。 対照的に、単純なEDA(Max-Min Ant System をベースとしたイテレーションベスト更新)が、Condorcet の勝者を確率1～12(p)$で選択できることが示される。 本研究では, (1+1) EAに対する対策として, 繰り返しデュエルが定常分布におけるコンドルチェット勝者の確率を著しく向上させることを示す。

関連論文リスト

• The Sampling Complexity of Condorcet Winner Identification in Dueling Bandits [6.244816393907942]
  本研究では,コンドルチェットの勝者が存在するという前提の下で,デュエルバンディットのベストアーム識別について検討する。 完全ギャップ行列 $_i,j=q_i,j-tfrac12$ を利用する新しい識別手順を導入する。 我々は、高確率、インスタンス依存のサンプル複雑度を導出し、(対数的要因を除いて)最もよく知られたものを改善することを保証します。
  論文  参考訳（メタデータ） (2026-03-16T12:27:14Z)
• Deceptive Exploration in Multi-armed Bandits [22.14260167840733]
  我々は、各アームがパブリックかつプライベートな報酬分布を持つマルチアームのバンディット設定について検討する。 観察者は、公開報酬に応じて、エージェントがトンプソンサンプリングに従うことを期待するが、偽装エージェントは、気づかれることなく、最高のプライベートアームを素早く特定することを目的としている。
  論文  参考訳（メタデータ） (2025-10-09T20:15:52Z)
• An Algorithm for Fixed Budget Best Arm Identification with Combinatorial Exploration [3.9901365062418312]
  我々は、K$$armed banditフレームワークにおける最適な腕識別問題を考察する。 エージェントは1つのアームではなく、各タイムスロットでアームのサブセットをプレイすることができる。 我々は、$log K$グループを構築し、最適なアームの存在を検出するための確率比テストを実行するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-02-03T15:10:08Z)
• A General Framework for Clustering and Distribution Matching with Bandit Feedback [81.50716021326194]
  我々は,帯域幅フィードバックを用いたクラスタリングと分散マッチング問題のための一般的なフレームワークを開発する。 誤り確率が$delta$を超えない任意のオンラインアルゴリズムに対して、平均アームプル数に基づいて漸近的でない下界を導出する。 我々の洗練された分析により、アルゴリズムの平均的なアームプル数が、$delta$が消えるにつれて、基本的限界に収束する速度に縛られる新しい現象が明らかになった。
  論文  参考訳（メタデータ） (2024-09-08T12:19:12Z)
• Multi-agent Multi-armed Bandits with Stochastic Sharable Arm Capacities [69.34646544774161]
  我々は、各アームへのリクエストの到着とプレイヤーへのリクエストの割り当てポリシーをキャプチャするマルチプレイヤーマルチアーム・バンディット(MAB)モデルの新しいバリエーションを定式化する。 課題は、プレイヤーが最適な腕引きプロファイルに従って腕を選択するように分散学習アルゴリズムを設計する方法である。 我々は,Mラウンドのみの最適腕引きプロファイルにおいて,プレイヤーがコンセンサスに達することを保証した反復分散アルゴリズムを設計する。
  論文  参考訳（メタデータ） (2024-08-20T13:57:00Z)
• Top Two Algorithms Revisited [14.783452541904365]
  トップ2のアルゴリズムは、トンプソンサンプリングの多腕バンディットモデルにおける最高の腕識別への適応として現れた。 本稿では,トップ2手法の一般解析を行い,リーダーの望ましい特性,挑戦者,および腕の(おそらくは非パラメトリックな)分布を同定する。 提案手法は,トンプソンサンプリングから受け継いだリーダの選択に使用されるサンプリングステップを,他の選択に置き換えることができることを示す。
  論文  参考訳（メタデータ） (2022-06-13T09:03:24Z)
• Best Arm Identification in Restless Markov Multi-Armed Bandits [85.55466536537293]
  マルチアームバンディット環境における最適な腕を特定することの問題点について検討する。 決定エンティティは、上限誤差確率を条件として、ベストアームのインデックスをできるだけ早く見つけることを希望する。 このポリシーは、$R$に依存する上限を達成し、$Rtoinfty$として単調に増加しないことを示す。
  論文  参考訳（メタデータ） (2022-03-29T04:58:04Z)
• Combinatorial Bandits without Total Order for Arms [52.93972547896022]
  セット依存報酬分布を捕捉し、武器の合計順序を仮定しない報酬モデルを提案する。 我々は、新しい後悔分析を開発し、$Oleft(frack2 n log Tepsilonright)$ gap-dependent regret boundと$Oleft(k2sqrtn T log Tright)$ gap-dependent regret boundを示す。
  論文  参考訳（メタデータ） (2021-03-03T23:08:59Z)
• Top-$k$ eXtreme Contextual Bandits with Arm Hierarchy [71.17938026619068]
  我々は、腕の総数が膨大であることができるトップ$ k$極端な文脈的包帯問題を研究します。 まず,Inverse Gap Weighting戦略を用いて,非極端に実現可能な設定のアルゴリズムを提案する。 我々のアルゴリズムは、$O(ksqrt(A-k+1)T log (|mathcalF|T))$である。
  論文  参考訳（メタデータ） (2021-02-15T19:10:52Z)

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

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