論文の概要: Fast and Regret Optimal Best Arm Identification: Fundamental Limits and
Low-Complexity Algorithms
- arxiv url: http://arxiv.org/abs/2309.00591v1
- Date: Fri, 1 Sep 2023 17:12:43 GMT
- ステータス: 処理完了
- システム内更新日: 2023-09-04 12:51:09.034338
- Title: Fast and Regret Optimal Best Arm Identification: Fundamental Limits and
Low-Complexity Algorithms
- Title（参考訳）: 高速かつレグレトな最適アーム同定法:基本極限と低複雑さアルゴリズム
- Authors: Qining Zhang, Lei Ying
- Abstract要約: 本稿では,2つの目的を持つマルチアーム・バンディット(MAB)問題について考察する。
両目的の同時実現は依然として未解決の問題である。
本稿では,これら2つの目的を達成することを目的としたEmphRegret Best Arm Identification (ROBAI)を提案する。
- 参考スコア（独自算出の注目度）: 17.76565371753346
- 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 the $\mathsf{EOCP}$ algorithm 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 sample complexity) of ROBAI, showing that $\mathsf{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 $\mathsf{UCB}$ algorithms, such that $\mathsf{EOCP}$ has
smaller regret even though it stops exploration much earlier than
$\mathsf{UCB}$ ($\mathcal{O}(\log T)$ versus $\mathcal{O}(T)$), which suggests
over-exploration is unnecessary and potentially harmful to system performance.
- Abstract（参考訳）: 本稿では,2つの目的を持つ確率的マルチアームバンディット(MAB)問題について考察する。
(i)最適腕に対する迅速な識別及びコミットメント、及び
(ii)連続ラウンドの連続で最大報酬を最大化すること。
それぞれの目的が個別によく研究されている、すなわち、最良の腕の識別である。
(i)及び後悔の最小化
(ii) 実用的重要性にもかかわらず, 両目的の同時実現は未解決の問題である。
本稿では,これら2つの目的を達成することを目的とした,emph{Regret Optimal Best Arm Identification} (ROBAI)を紹介する。
事前決定された停止時間と適応停止時間の両方の条件でroboaiを解くために、それぞれ$\mathsf{eocp}$アルゴリズムとその変種を示し、ガウスおよび一般のバンディットにおいて漸近的最適後悔を達成するだけでなく、事前決定された停止時間を持つ$\mathcal{o}(\log t)$ラウンドと適応停止時間で$\mathcal{o}(\log^2 t)$ラウンドの最適アームにコミットする。
さらに,robaiのコミットメント時間(サンプル複雑性に相当)に対する下限を特徴付け,$\mathsf{eocp}$とその変種が予め決定された停止時間に最適であり,適応停止時間にほぼ最適であることを示す。
数値計算の結果から、従来の$\mathsf{ucb}$ アルゴリズムが持つ興味深い ``over-exploration'' 現象が明らかになる。$\mathsf{eocp}$ は、$\mathsf{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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。