論文の概要: UCB Exploration for Fixed-Budget Bayesian Best Arm Identification

• arxiv url: http://arxiv.org/abs/2408.04869v3
• Date: Wed, 23 Oct 2024 05:44:21 GMT
• ステータス: 処理完了
• システム内更新日: 2024-11-08 12:11:36.693945
• Title: UCB Exploration for Fixed-Budget Bayesian Best Arm Identification
• Title（参考訳）: 固定予算ベイズ型ベストアーム識別のためのUCB探索
• Authors: Rong J. B. Zhu, Yanqi Qiu,
• Abstract要約: 固定予算設定におけるベストアーム識別(BAI)について検討した。 ベイズ条件下での固定予算BAI問題に対して理論的かつ実験的に効率的であるUPB探索アルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study best-arm identification (BAI) in the fixed-budget setting. Adaptive allocations based on upper confidence bounds (UCBs), such as UCBE, are known to work well in BAI. However, it is well-known that its optimal regret is theoretically dependent on instances, which we show to be an artifact in many fixed-budget BAI problems. In this paper we propose an UCB exploration algorithm that is both theoretically and empirically efficient for the fixed budget BAI problem under a Bayesian setting. The key idea is to learn prior information, which can enhance the performance of UCB-based BAI algorithm as it has done in the cumulative regret minimization problem. We establish bounds on the failure probability and the simple regret for the Bayesian BAI problem, providing upper bounds of order $\tilde{O}(\sqrt{K/n})$, up to logarithmic factors, where $n$ represents the budget and $K$ denotes the number of arms. Furthermore, we demonstrate through empirical results that our approach consistently outperforms state-of-the-art baselines.
• Abstract（参考訳）: 固定予算設定におけるベストアーム識別(BAI)について検討した。 UCBEのような上位信頼境界(UCB)に基づく適応的アロケーションは、BAIでうまく機能することが知られている。 しかし、その最適後悔が理論的にインスタンスに依存していることはよく知られており、これは多くの固定予算のBAI問題においてアーティファクトであることが示されている。 本稿では, ベイズ条件下での固定予算BAI問題に対して, 理論的かつ実験的に効率的なUPB探索アルゴリズムを提案する。 鍵となる考え方は事前情報を学習することであり、これは累積的後悔の最小化問題において行ったような UCB ベースの BAI アルゴリズムの性能を向上させることができる。 我々は、失敗確率とベイズ的BAI問題に対する単純な後悔の限界を確立し、次数 $\tilde{O}(\sqrt{K/n})$ の上限を対数因子まで与え、$n$ は予算を表し、$K$ は武器の数を表す。 さらに,本手法が最先端のベースラインを一貫して上回ることを示す実証実験を行った。

関連論文リスト

• 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)
• Prior-Dependent Allocations for Bayesian Fixed-Budget Best-Arm Identification in Structured Bandits [5.362453227879925]
  本研究では, ベイジアン固定予算ベストアーム識別(BAI)の問題について検討する。 本稿では,事前情報と環境構造に基づく固定割当を用いたアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-02-08T18:13:26Z)
• Bayesian Fixed-Budget Best-Arm Identification [24.31655036648236]
  固定予算ベストアーム識別(英語: Fixed-budget best-arm identification、BAI)は、エージェントが一定の予算内で最適な腕を特定する確率を最大化する盗賊問題である。 ベイズ除去アルゴリズムを提案し、最適な腕を誤識別する確率の上限を導出する。
  論文  参考訳（メタデータ） (2022-11-15T23:29:51Z)
• Batch-Size Independent Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms or Independent Arms [53.89752069984382]
  半帯域 (CMAB) について検討し, 半帯域 (CMAB) におけるバッチサイズ (K$) の依存性の低減に着目した。 まず,確率的に引き起こされるアーム(CMAB-T)を用いたCMABの設定に対して,分散を考慮した信頼区間を持つBCUCB-Tアルゴリズムを提案する。 次に,独立アームを用いた非トリガ型CMABの設定に対して,TPVM条件の非トリガ型を利用したSESCBアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-08-31T13:09:39Z)
• Best Arm Identification under Additive Transfer Bandits [49.69203462561861]
  提案手法は, 未知であるにもかかわらず, ソースとターゲットMABインスタンスの間には, 付加的な関係があることが知られている。 本稿では,LUCBスタイルのアルゴリズムを理論的に解析し,高い確率で$epsilon$-optimal target armを同定する。
  論文  参考訳（メタデータ） (2021-12-08T02:20:18Z)
• 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)
• Towards Minimax Optimal Best Arm Identification in Linear Bandits [95.22854522340938]
  固定予算設定における線形包帯における最適な腕識別の問題について検討する。 G-最適設計の特性を活用し、アーム割り当て規則に組み込むことにより、パラメータフリーなアルゴリズムを設計する。 OD-LinBAIの故障確率に関する理論的解析を行った。
  論文  参考訳（メタデータ） (2021-05-27T09:19:10Z)
• Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decomposition [59.34067736545355]
  有限水平型マルコフ決定過程(MDP)における強化学習問題を,S$状態,A$動作,エピソード長$H$を用いて検討した。 モデルフリーアルゴリズム UCB-Advantage を提案し、$T = KH$ および $K$ が再生すべきエピソード数である場合に $tildeO(sqrtH2SAT)$ regret を達成することを証明した。
  論文  参考訳（メタデータ） (2020-04-21T14:00:06Z)
• The Unreasonable Effectiveness of Greedy Algorithms in Multi-Armed Bandit with Many Arms [10.662105162882526]
  本研究は,Emphmany-armed regimeにおける$k$-armed bandit問題について考察する。 以上の結果から,多腕の環境下での強欲なアルゴリズムには,新たなエフェフリー探索法が有用であることが示唆された。
  論文  参考訳（メタデータ） (2020-02-24T08:59:34Z)

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

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