論文の概要: Tree-Guided Identify-Then-Exploit: A Unified Framework of Best Arm Identification and Regret Minimization for Dueling Bandits

• arxiv url: http://arxiv.org/abs/2606.01799v1
• Date: Mon, 01 Jun 2026 07:17:49 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-02 21:34:31.485165
• Title: Tree-Guided Identify-Then-Exploit: A Unified Framework of Best Arm Identification and Regret Minimization for Dueling Bandits
• Title（参考訳）: ツリーガイドによる識別-Then-Exploit:Dueling Banditsのためのベストアーム識別とレグレット最小化の統一フレームワーク
• Authors: Pu Wang, Yao-Xiang Ding,
• Abstract要約: 我々はコンドルチェット・ウィンナーの仮定で$N$の武器を持つデュエルバンドについて研究する。 広く採用されている3つの目的は、ベストアーム識別(BAI)、弱い後悔、強い後悔である。 我々は,これらすべての目的に対処する最初の統合フレームワークであるTG-ITE(Tree-Guided Identify-Then-Exploit)を提案する。
• 参考スコア（独自算出の注目度）: 15.350660480734424
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study $N$-armed stochastic dueling bandits under the Condorcet-winner assumption, where three widely adopted objectives are considered: best-arm identification (BAI), weak regret, and strong regret. We propose Tree-Guided Identify-Then-Exploit (TG-ITE), the first unified framework to tackle all these objectives to our knowledge. Without requiring stronger assumptions, we propose a shared tree-guided identification approach to find a high-confidence incumbent within $O(N)$ comparisons. We further propose varied exploitation strategies to utilize this warm-start stage to optimize the specific objectives at hand. This methodology enables our approach to (1) achieve $O(N)$ sample complexity in BAI without commonly adopted stronger assumptions; (2) build the first winner-stays-style algorithm to achieve $O(N)$ weak regret; (3) enjoy the same $O(N \log T)$ guarantee as specialized strong-regret approaches; (4) realize the joint optimization of BAI and weak regret with $O(N)$ guarantees for both, eliminating the sub-optimal gap of $O(\log N)$ in the existing approach. Our results provide evidence that the trade-off between BAI and regret minimization is relatively benign in dueling bandits.
• Abstract（参考訳）: コンドルチェット・ウィンナーの仮定では, ベストアーム識別(BAI), 弱い後悔, 強い後悔の3つの目的が広く採用されている。 我々は,これらすべての目的に対処する最初の統合フレームワークであるTG-ITE(Tree-Guided Identify-Then-Exploit)を提案する。 より強い仮定を必要とせず、我々は、$O(N)$比較の中で高信頼な既存元を見つけるための共有木誘導識別手法を提案する。 我々はまた、このウォームスタートステージを利用して、目前にある特定の目的を最適化するための様々な搾取戦略を提案する。 本手法は,(1)より強い仮定を伴わないBAIにおいて,(1)$O(N)$サンプル複雑性を実現すること,(2)$O(N)$弱い後悔を達成するために,最初の勝者-ステイズスタイルのアルゴリズムを構築すること,(3)特別な強欲的アプローチとして,同じ$O(N \log T)$保証を享受すること,(4)既存のアプローチにおける$O(N)$のサブ最適ギャップを排除して,BAIの共同最適化と弱い後悔を実現すること,の2つの方法を実現する。 以上の結果から,BAIと後悔の最小化とのトレードオフが,盗賊のデュエルにおいて比較的良質であることを示す。

関連論文リスト

• Breaking the $\log(1/Δ_2)$ Barrier: Better Batched Best Arm Identification with Adaptive Grids [28.547030766096956]
  ほぼ最適なサンプル複雑性を実現するアルゴリズムを導入し、インスタンスに敏感なバッチ複雑性を特徴とする。 我々は、この枠組みを線形包帯におけるバッチ化されたベストアーム識別の問題に拡張し、同様の改善を実現する。
  論文  参考訳（メタデータ） (2025-01-29T01:40:36Z)
• Best Arm Identification with Minimal Regret [55.831935724659175]
  最高の腕識別問題 優雅にアマルガメートは、最小化とBAIを後悔している。 エージェントの目標は、所定の信頼度で最高の腕を特定することである。 二重KL-UCBアルゴリズムは、信頼度がゼロになる傾向があるため、最適性を達成する。
  論文  参考訳（メタデータ） (2024-09-27T16:46:02Z)
• Optimal Multi-Fidelity Best-Arm Identification [65.23078799972188]
  バンディットのベストアーム識別において、アルゴリズムは、できるだけ早く特定の精度で、最高平均報酬の腕を見つけることを任務とする。 マルチフィデリティのベストアーム識別について検討し、低コストで低いフィデリティ(正確な平均推定値を持たない)で腕をサンプリングすることを選択できる。 この問題に対処するためのいくつかの方法が提案されているが、その最適性は、特に最適な腕を特定するのに必要な総コストのゆるやかな下限のため、未解決のままである。
  論文  参考訳（メタデータ） (2024-06-05T08:02:40Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
  論文  参考訳（メタデータ） (2023-12-13T11:08:25Z)
• Versatile Dueling Bandits: Best-of-both-World Analyses for Online Learning from Preferences [28.79598714109439]
  両環境および敵環境における$K$武器のデュエルバンディットの問題について検討する。 まず,マルチアームのバンディットに対して,任意の(一般的な)デュエル・バンドレットから新たなリダクションを提案する。 提案アルゴリズムは,コンドルチェット・ウィンナーベンチマークに対して最適な$O(sum_i = 1K fraclog TDelta_i)$ regret boundを達成した最初のアルゴリズムでもある。
  論文  参考訳（メタデータ） (2022-02-14T13:37:23Z)
• Achieving the Pareto Frontier of Regret Minimization and Best Arm Identification in Multi-Armed Bandits [91.8283876874947]
  本稿では,BoBW-lil'UCB$(gamma)$アルゴリズムの設計と解析を行う。 i) RMとBAIの両方の目的に対して最適なアルゴリズムを同時に実行できないことを示す。 また、BoBW-lil'UCB$(gamma)$は、時間複雑性と後悔の点で競合よりも優れていることを示す。
  論文  参考訳（メタデータ） (2021-10-16T17:52:32Z)

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

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