論文の概要: Rate-optimal Design for Anytime Best Arm Identification

• arxiv url: http://arxiv.org/abs/2510.23199v1
• Date: Mon, 27 Oct 2025 10:36:56 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-28 19:54:32.603595
• Title: Rate-optimal Design for Anytime Best Arm Identification
• Title（参考訳）: 随時ベストアーム識別のためのレート最適設計法
• Authors: Junpei Komiyama, Kyoungseok Jang, Junya Honda,
• Abstract要約: 目的は、限られたサンプリング予算の下で、一組のKドルアームから、最も高い平均報酬で腕を識別することである。 この問題はA/Bテストのような多くの実践シナリオをモデル化する。 この問題に対するアルゴリズムのクラスを考えるが、これは定数係数まで確実に最小限のアルゴリズムである。
• 参考スコア（独自算出の注目度）: 19.803714682639903
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider the best arm identification problem, where the goal is to identify the arm with the highest mean reward from a set of $K$ arms under a limited sampling budget. This problem models many practical scenarios such as A/B testing. We consider a class of algorithms for this problem, which is provably minimax optimal up to a constant factor. This idea is a generalization of existing works in fixed-budget best arm identification, which are limited to a particular choice of risk measures. Based on the framework, we propose Almost Tracking, a closed-form algorithm that has a provable guarantee on the popular risk measure $H_1$. Unlike existing algorithms, Almost Tracking does not require the total budget in advance nor does it need to discard a significant part of samples, which gives a practical advantage. Through experiments on synthetic and real-world datasets, we show that our algorithm outperforms existing anytime algorithms as well as fixed-budget algorithms.
• Abstract（参考訳）: 目的は、限られたサンプリング予算の下で、一組のKドルアームから、最も高い平均報酬で腕を識別することである。 この問題はA/Bテストのような多くの実践シナリオをモデル化する。 この問題に対するアルゴリズムのクラスを考えるが、これは定数係数まで確実に最小限のアルゴリズムである。 この考え方は固定予算のベストアーム識別における既存の作業の一般化であり、これは特定のリスク尺度の選択に限られる。 このフレームワークに基づいて、一般的なリスク尺度である$H_1$に対して証明可能な保証を持つクローズドフォームアルゴリズムであるSome Trackingを提案する。 既存のアルゴリズムとは異なり、ほぼ追跡は前もって全予算を必要とせず、サンプルのかなりの部分を捨てる必要もなく、実用的な利点をもたらす。 合成および実世界のデータセットの実験を通して、我々のアルゴリズムは、固定予算アルゴリズムだけでなく、既存のアルゴリズムよりも優れていることを示す。

関連論文リスト

• Balancing Performance and Costs in Best Arm Identification [5.558508644689221]
  本研究は、推奨アームの性能と、このアームを学習することで得られるコストとを明示的にバランスさせるリスク関数を最小化する新しいフォーマリズムを提案する。 この枠組みでは、サンプリングフェーズの各観察にコストがかかり、アームを推奨すると、最適下腕を特定するためにパフォーマンスペナルティが生じる。 性能ペナルティの2つの選択のリスク、誤識別の確率、単純な後悔のリスクについて理論的に下位境界を導出し、DBCAREと呼ばれるアルゴリズムを提案し、これらの下位境界をほぼ全ての問題インスタンス上のポリログ因子に一致させる。
  論文  参考訳（メタデータ） (2025-05-26T23:33:43Z)
• Optimal Multi-Fidelity Best-Arm Identification [65.23078799972188]
  バンディットのベストアーム識別において、アルゴリズムは、できるだけ早く特定の精度で、最高平均報酬の腕を見つけることを任務とする。 マルチフィデリティのベストアーム識別について検討し、低コストで低いフィデリティ(正確な平均推定値を持たない)で腕をサンプリングすることを選択できる。 この問題に対処するためのいくつかの方法が提案されているが、その最適性は、特に最適な腕を特定するのに必要な総コストのゆるやかな下限のため、未解決のままである。
  論文  参考訳（メタデータ） (2024-06-05T08:02:40Z)
• Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
  我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。 特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
  論文  参考訳（メタデータ） (2023-12-19T13:17:43Z)
• Mean-based Best Arm Identification in Stochastic Bandits under Reward Contamination [80.53485617514707]
  本稿では,ギャップベースアルゴリズムと逐次除去に基づく2つのアルゴリズムを提案する。 具体的には、ギャップベースのアルゴリズムでは、サンプルの複雑さは定数要素まで最適であり、連続的な除去では対数因子まで最適である。
  論文  参考訳（メタデータ） (2021-11-14T21:49:58Z)
• Fixed-Budget Best-Arm Identification in Structured Bandits [33.27743152847947]
  固定予算設定におけるベストアーム識別(BAI)は、学習エージェントが一定の回数の観測後に最適な(ベスト)腕を特定する確率を最大化する盗賊問題である。 結合一般化モデルから平均報酬推定値に基づいて最適アームを除去し,構造を組み込んだ一般トラクタブルアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-06-09T01:32:43Z)
• Optimal Best-arm Identification in Linear Bandits [79.3239137440876]
  サンプルの複雑さが既知のインスタンス固有の下界と一致する単純なアルゴリズムを考案する。 既存のベストアーム識別戦略とは異なり、我々のアルゴリズムは武器の数に依存しない停止規則を用いる。
  論文  参考訳（メタデータ） (2020-06-29T14:25:51Z)

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

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