論文の概要: Asymptotically Optimal Linear Best Feasible Arm Identification with Fixed Budget

• arxiv url: http://arxiv.org/abs/2506.02386v1
• Date: Tue, 03 Jun 2025 02:56:26 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-04 21:47:35.203937
• Title: Asymptotically Optimal Linear Best Feasible Arm Identification with Fixed Budget
• Title（参考訳）: 固定予算を用いた漸近的最適リニアベストフェーブルアーム同定
• Authors: Jie Bian, Vincent Y. F. Tan,
• Abstract要約: 本稿では,誤差確率の指数的減衰を保証し,最適な腕識別のための新しいアルゴリズムを提案する。 我々は,複雑性のレベルが異なる様々な問題インスタンスに対する包括的経験的評価を通じて,アルゴリズムの有効性を検証する。
• 参考スコア（独自算出の注目度）: 55.938644481736446
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The challenge of identifying the best feasible arm within a fixed budget has attracted considerable interest in recent years. However, a notable gap remains in the literature: the exact exponential rate at which the error probability approaches zero has yet to be established, even in the relatively simple setting of $K$-armed bandits with Gaussian noise. In this paper, we address this gap by examining the problem within the context of linear bandits. We introduce a novel algorithm for best feasible arm identification that guarantees an exponential decay in the error probability. Remarkably, the decay rate -- characterized by the exponent -- matches the theoretical lower bound derived using information-theoretic principles. Our approach leverages a posterior sampling framework embedded within a game-based sampling rule involving a min-learner and a max-learner. This strategy shares its foundations with Thompson sampling, but is specifically tailored to optimize the identification process under fixed-budget constraints. Furthermore, we validate the effectiveness of our algorithm through comprehensive empirical evaluations across various problem instances with different levels of complexity. The results corroborate our theoretical findings and demonstrate that our method outperforms several benchmark algorithms in terms of both accuracy and efficiency.
• Abstract（参考訳）: 固定予算内で最高の実現可能な腕を特定するという課題は、近年、かなりの関心を集めている。 誤差確率が 0 に近づく正確な指数速度はまだ確立されていないが、ガウス雑音を伴う$K$武装のバンディットは比較的単純な設定である。 本稿では,線形バンディットの文脈における問題を調べることによって,このギャップに対処する。 本稿では,誤差確率の指数的減衰を保証し,最適な腕識別のための新しいアルゴリズムを提案する。 顕著なことに、指数によって特徴づけられる減衰速度は、情報理論の原理を用いて導かれる理論的な下界と一致する。 本手法では,min-learnerとmax-learnerを含むゲームベースサンプリングルール内に埋め込まれた後続サンプリングフレームワークを活用する。 この戦略は基礎をトンプソンサンプリングと共有しているが、固定予算制約の下での識別プロセスを最適化するために特別に調整されている。 さらに,複雑性のレベルが異なる様々な問題インスタンスを対象とした包括的経験的評価により,アルゴリズムの有効性を検証した。 その結果,提案手法は精度と効率の両面で,いくつかのベンチマークアルゴリズムより優れていることが示された。

関連論文リスト

• 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)

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

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