論文の概要: 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年)によって完全に特徴づけられてきたが、固定バジェット設定と呼ばれる「二重」設定における漸近的複雑さについてはほとんど知られていない。
本項では、固定予算設定におけるインスタンス依存漸近複雑性に関する開問題と予想について述べる。
関連論文リスト
- Optimal Best Arm Identification with Fixed Confidence in Restless
Bandits [72.86567379444153]
本研究は,有限個の腕を持つレスレス・マルチアーム・バンディット・セッティングにおけるベスト・アーム識別について検討する。
各アームによって生成された離散時間データは、共通の有限状態空間で値を取る同質マルコフ連鎖を形成する。
その結果,あるマルコフ決定過程の長期的挙動の追跡とその状態-行動的訪問比率が,逆および達成可能性境界を解析するための重要な要素であることが示唆された。
論文 参考訳(メタデータ) (2023-10-20T10:04:05Z) - Complexity Analysis of a Countable-armed Bandit Problem [9.163501953373068]
遊びの地平線上で期待される累積的後悔を最小限に抑えるという古典的問題を考察する。
我々は、$K=2$のとき、$mathcalOleft(log n right)$の率最適有限時間インスタンス依存後悔を実現するアルゴリズムを提案する。
問題に対する後悔の順序と複雑さは、古典的MAB問題と非常に類似していることを示しているが、アルゴリズム設計における性能境界の特性と健全な側面は、後者とはかなり異なる。
論文 参考訳(メタデータ) (2023-01-18T00:53:46Z) - 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) - Instance-Dependent Complexity of Contextual Bandits and Reinforcement
Learning: A Disagreement-Based Perspective [104.67295710363679]
古典的なマルチアームバンディット問題において、インスタンス依存アルゴリズムは、ベストとセカンドベストのアーム間のギャップで「容易」な問題のパフォーマンスを向上させる。
我々は、インスタンス依存の後悔境界を得るのに十分かつ必要である複雑性尺度のファミリーを導入する。
次に、可能な限りギャップに適応する新しいオラクル効率アルゴリズムを導入し、最悪の場合にはミニマックスレートを得る。
論文 参考訳(メタデータ) (2020-10-07T01:33:06Z) - Optimal Best-arm Identification in Linear Bandits [79.3239137440876]
サンプルの複雑さが既知のインスタンス固有の下界と一致する単純なアルゴリズムを考案する。
既存のベストアーム識別戦略とは異なり、我々のアルゴリズムは武器の数に依存しない停止規則を用いる。
論文 参考訳(メタデータ) (2020-06-29T14:25:51Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。