論文の概要: Open Problem: Optimal Best Arm Identification with Fixed Budget
- arxiv url: http://arxiv.org/abs/2303.00950v1
- Date: Thu, 2 Mar 2023 04:07:08 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-03 16:10:42.406030
- Title: Open Problem: Optimal Best Arm Identification with Fixed Budget
- Title(参考訳): オープンな問題: 固定予算による最適な腕識別
- Authors: Chao Qin
- Abstract要約: 腕の識別や純粋な探査の問題はCOLTコミュニティで注目されている。
本項では、固定予算設定におけるインスタンス依存複雑性に関する開問題と予想について論じる。
- 参考スコア(独自算出の注目度): 1.4213973379473654
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Best arm identification or pure exploration problems have received much
attention in the COLT community since Bubeck et al. (2009) and Audibert et al.
(2010). For any bandit instance with a unique best arm, its asymptotic
complexity in the so-called fixed-confidence setting has been completely
characterized in Garivier and Kaufmann (2016) and Chernoff (1959), while little
is known about the asymptotic complexity in its "dual" setting called
fixed-budget setting. This note discusses the open problems and conjectures
about the instance-dependent asymptotic complexity in the fixed-budget setting.
- Abstract(参考訳): 腕の識別や純粋な探索の問題は、Bubeck et al. (2009) や Audibert et al. (2010) 以降、COLTコミュニティで注目されている。
独特な最高の腕を持つバンドイットの例では、いわゆる固定信頼設定における漸近的複雑性は、ガリヴィエとカウフマン(2016年)とチャーノフ(1959年)によって完全に特徴づけられてきたが、固定バジェット設定と呼ばれる「二重」設定における漸近的複雑さについてはほとんど知られていない。
本項では、固定予算設定におけるインスタンス依存漸近複雑性に関する開問題と予想について述べる。
関連論文リスト
- Bridging Rested and Restless Bandits with Graph-Triggering: Rising and Rotting [67.1631453378926]
Graph-Triggered Banditsは、安静と安静のバンディットを一般化するフレームワークである。
本研究は,2種類の単調包帯に焦点をあてる: 立ち上がり, 腕の期待される報酬が増加する, 引き金の数が増える, 回転する, 反対の行動が起こる。
論文 参考訳(メタデータ) (2024-09-09T18:23:07Z) - A General Framework for Clustering and Distribution Matching with Bandit Feedback [81.50716021326194]
我々は,帯域幅フィードバックを用いたクラスタリングと分散マッチング問題のための一般的なフレームワークを開発する。
誤り確率が$delta$を超えない任意のオンラインアルゴリズムに対して、平均アームプル数に基づいて漸近的でない下界を導出する。
論文 参考訳(メタデータ) (2024-09-08T12:19:12Z) - Optimal Multi-Fidelity Best-Arm Identification [65.23078799972188]
バンディットのベストアーム識別において、アルゴリズムは、できるだけ早く特定の精度で、最高平均報酬の腕を見つけることを任務とする。
マルチフィデリティのベストアーム識別について検討し、低コストで低いフィデリティ(正確な平均推定値を持たない)で腕をサンプリングすることを選択できる。
この問題に対処するためのいくつかの方法が提案されているが、その最適性は、特に最適な腕を特定するのに必要な総コストのゆるやかな下限のため、未解決のままである。
論文 参考訳(メタデータ) (2024-06-05T08:02:40Z) - Pure Exploration for Constrained Best Mixed Arm Identification with a Fixed Budget [6.22018632187078]
固定予算の制約付きベスト・ミックスアーム識別(CBMAI)問題を導入する。
目標は、与えられた学習予算$N$で、期待されるコストの制約によって期待される報酬を最大化する最高の混合アームを見つけることである。
我々は、(最良の混合アームの支持の)誤識別に関する理論上の上限を提供し、予算$N$で指数関数的に崩壊することを示す。
論文 参考訳(メタデータ) (2024-05-23T22:35:11Z) - Bayesian Fixed-Budget Best-Arm Identification [24.31655036648236]
固定予算ベストアーム識別(英語: Fixed-budget best-arm identification、BAI)は、エージェントが一定の予算内で最適な腕を特定する確率を最大化する盗賊問題である。
ベイズ除去アルゴリズムを提案し、最適な腕を誤識別する確率の上限を導出する。
論文 参考訳(メタデータ) (2022-11-15T23:29:51Z) - Best Arm Identification in Restless Markov Multi-Armed Bandits [85.55466536537293]
マルチアームバンディット環境における最適な腕を特定することの問題点について検討する。
決定エンティティは、上限誤差確率を条件として、ベストアームのインデックスをできるだけ早く見つけることを希望する。
このポリシーは、$R$に依存する上限を達成し、$Rtoinfty$として単調に増加しないことを示す。
論文 参考訳(メタデータ) (2022-03-29T04:58:04Z) - Finding Optimal Arms in Non-stochastic Combinatorial Bandits with
Semi-bandit Feedback and Finite Budget [6.759124697337311]
有限サンプリング予算制約の下では,半帯域フィードバックによる帯域幅問題を考える。
アクションは、一組のアームを選択し、選択されたセット内の各アームに対するフィードバックが受信される。
本稿では,アーム除去戦略の全スペクトルをカバーするのに適した汎用アルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-02-09T14:36:05Z) - Dare not to Ask: Problem-Dependent Guarantees for Budgeted Bandits [66.02233330016435]
後悔と質問されたフィードバックの両方について、問題に依存した保証を提供します。
本稿では,問題依存的後悔と累積的フィードバック境界を導出するBuFALUというアルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-10-12T03:24:57Z) - Generalized non-stationary bandits [78.05847530997926]
スイッチングバンドイット問題を一般化する非定常バンドイット問題について検討する。
本稿では, 4つの問題 (a)-(d) を効率よく, 統一的に解く単一アルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-02-01T09:34:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。