論文の概要: Fast and Regret Optimal Best Arm Identification: Fundamental Limits and Low-Complexity Algorithms
- arxiv url: http://arxiv.org/abs/2309.00591v3
- Date: Wed, 29 May 2024 19:49:02 GMT
- ステータス: 処理完了
- システム内更新日: 2024-05-31 23:52:32.296328
- Title: Fast and Regret Optimal Best Arm Identification: Fundamental Limits and Low-Complexity Algorithms
- Title（参考訳）: 高速かつレグレトな最適アーム同定法:基本極限と低複雑さアルゴリズム
- Authors: Qining Zhang, Lei Ying,
- Abstract要約: 2つの目的を持つマルチアーメッド・バンドイット(MAB)問題: (i) 最適なアームに対する迅速な識別とコミットメント、および (ii) 連続したラウンドで連続して$T$の報酬。
本稿では,これら2つの目的を達成することを目的としたemphRegret Best Arm Identification (ROBAI)を紹介する。
- 参考スコア（独自算出の注目度）: 15.038210624870656
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper considers a stochastic Multi-Armed Bandit (MAB) problem with dual objectives: (i) quick identification and commitment to the optimal arm, and (ii) reward maximization throughout a sequence of $T$ consecutive rounds. Though each objective has been individually well-studied, i.e., best arm identification for (i) and regret minimization for (ii), the simultaneous realization of both objectives remains an open problem, despite its practical importance. This paper introduces \emph{Regret Optimal Best Arm Identification} (ROBAI) which aims to achieve these dual objectives. To solve ROBAI with both pre-determined stopping time and adaptive stopping time requirements, we present an algorithm called EOCP and its variants respectively, which not only achieve asymptotic optimal regret in both Gaussian and general bandits, but also commit to the optimal arm in $\mathcal{O}(\log T)$ rounds with pre-determined stopping time and $\mathcal{O}(\log^2 T)$ rounds with adaptive stopping time. We further characterize lower bounds on the commitment time (equivalent to the sample complexity) of ROBAI, showing that EOCP and its variants are sample optimal with pre-determined stopping time, and almost sample optimal with adaptive stopping time. Numerical results confirm our theoretical analysis and reveal an interesting "over-exploration" phenomenon carried by classic UCB algorithms, such that EOCP has smaller regret even though it stops exploration much earlier than UCB, i.e., $\mathcal{O}(\log T)$ versus $\mathcal{O}(T)$, which suggests over-exploration is unnecessary and potentially harmful to system performance.
- Abstract（参考訳）: 本稿では,2つの目的を持つ確率的マルチアーマッド帯域(MAB)問題について考察する。
一 最適な腕の素早い識別及びコミットメント
(ii)$T$連続ラウンドの一連の報酬最大化。
それぞれの目的は、個別によく研究されているが、つまり、最高の腕の識別である。
(i)と後悔の最小化
(ii) 実用的重要性にもかかわらず, 両目的の同時実現は未解決の問題である。
本稿では,これら2つの目的を達成することを目的とした,emph{Regret Optimal Best Arm Identification} (ROBAI)を紹介する。
事前に決定された停止時間と適応的な停止時間の両方でROBAIを解くため、EOCPとその変種と呼ばれるアルゴリズムをそれぞれ提示する。これはガウスと一般の包帯において漸近的最適後悔を達成できるだけでなく、事前決定された停止時間を持つ$\mathcal{O}(\log T)$ラウンドと適応的な停止時間を持つ$\mathcal{O}(\log^2 T)$ラウンドにおいて最適なアームにコミットする。
さらに、ROBAIのコミットメント時間(サンプル複雑性と同等)の低い境界を特徴付け、EOCPとその変種が予め決定された停止時間に最適なサンプルであり、適応的な停止時間にほぼ最適であることを示す。
数値的な結果は、我々の理論解析を裏付け、古典的 UCB アルゴリズムによってもたらされる興味深い「過剰探索」現象を明らかにし、EOCP は UCB よりもはるかに早く探索を中止しているにもかかわらず、より少ない後悔、すなわち $\mathcal{O}(\log T)$ 対 $\mathcal{O}(T)$ である。
関連論文リスト
- Cost Aware Best Arm Identification [13.380383930882784]
emphCost Aware Best Arm Identification (CABAI)と呼ぶ。
平方根規則に基づくemphChernoff Overlap (CO)と呼ばれる単純なアルゴリズムを提案する。
この結果から,不均一な動作コストを無視すると,実行時の準最適性が得られ,また,簡単なアルゴリズムにより,幅広い問題に対してほぼ最適性能が得られることがわかった。
論文 参考訳（メタデータ） (2024-02-26T16:27:08Z) - Stochastic Approximation with Delayed Updates: Finite-Time Rates under Markovian Sampling [73.5602474095954]
マルコフサンプリングの遅延更新による近似スキームの非漸近的性能について検討した。
我々の理論的な発見は、幅広いアルゴリズムの遅延の有限時間効果に光を当てた。
論文 参考訳（メタデータ） (2024-02-19T03:08:02Z) - Exploration by Optimization with Hybrid Regularizers: Logarithmic Regret
with Adversarial Robustness in Partial Monitoring [46.30750729936261]
敵環境における最適境界を実現するための最適化による探索(ExO)が提案された。
まず,ハイブリッド正規化器を用いたExOの新しいフレームワークと解析手法を構築した。
特に、$O(sum_a neq a* k2 log T / Delta_a)$で、$a*$は最適なアクションであり、$Delta_a$はアクションの亜最適ギャップである。
論文 参考訳（メタデータ） (2024-02-13T09:34:22Z) - Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。
SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
論文 参考訳（メタデータ） (2023-12-13T11:08:25Z) - Non-stationary Online Convex Optimization with Arbitrary Delays [50.46856739179311]
本稿では,非定常環境における遅延オンライン凸最適化(OCO)について検討する。
まず, 遅延勾配の勾配降下ステップを, 到着順に応じて行う単純なアルゴリズム, DOGDを提案する。
DOGDが達成した動的後悔境界を$O(sqrtbardT(P_T+1))$に削減する改良アルゴリズムを開発した。
論文 参考訳（メタデータ） (2023-05-20T07:54:07Z) - Finite-Time Error Bounds for Greedy-GQ [20.51105692499517]
We show that Greedy-GQ algorithm converges fast-time error。
我々の分析は、ステップサイズを選択するために、より高速な収束ステップサイズを提供する。
論文 参考訳（メタデータ） (2022-09-06T15:04:57Z) - Mean-based Best Arm Identification in Stochastic Bandits under Reward
Contamination [80.53485617514707]
本稿では,ギャップベースアルゴリズムと逐次除去に基づく2つのアルゴリズムを提案する。
具体的には、ギャップベースのアルゴリズムでは、サンプルの複雑さは定数要素まで最適であり、連続的な除去では対数因子まで最適である。
論文 参考訳（メタデータ） (2021-11-14T21:49:58Z) - Optimal and Efficient Dynamic Regret Algorithms for Non-Stationary
Dueling Bandits [27.279654173896372]
我々は,非定常的あるいは時間的に異なる選好の下で,$K$のDueling Banditsにおける空力的後悔の最小化問題について検討した。
これは、エージェントが各ラウンドで一対のアイテムを選択し、このペアに対する相対的な二項のウィンロスフィードバックのみを観察するオンライン学習設定である。
論文 参考訳（メタデータ） (2021-11-06T16:46:55Z) - 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) - Lenient Regret for Multi-Armed Bandits [72.56064196252498]
エージェントが順番に行動を選択し、その行動に対する報酬を観察するマルチアーマッド・バンディット(MAB)問題を考察する。
アルゴリズムの大多数は、後悔、すなわち最高の行動の報酬とエージェントの行動の累積的な差を最小化しようとするが、この基準は望ましくない結果をもたらすかもしれない。
我々は、いくつかの$epsilon$よりも小さな最適性ギャップを無視した、より寛大で寛大で後悔すべき基準を提案する。
論文 参考訳（メタデータ） (2020-08-10T08:30:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。