論文の概要: Achieving the Pareto Frontier of Regret Minimization and Best Arm Identification in Multi-Armed Bandits

• arxiv url: http://arxiv.org/abs/2110.08627v3
• Date: Fri, 9 Jun 2023 05:14:58 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-12 18:44:06.953026
• Title: Achieving the Pareto Frontier of Regret Minimization and Best Arm Identification in Multi-Armed Bandits
• Title（参考訳）: 多関節バンドにおけるレギュレット最小化のパレートフロンティア達成とベストアーム識別
• Authors: Zixin Zhong, Wang Chi Cheung, Vincent Y. F. Tan
• Abstract要約: 本稿では,BoBW-lil'UCB$(gamma)$アルゴリズムの設計と解析を行う。 i) RMとBAIの両方の目的に対して最適なアルゴリズムを同時に実行できないことを示す。 また、BoBW-lil'UCB$(gamma)$は、時間複雑性と後悔の点で競合よりも優れていることを示す。
• 参考スコア（独自算出の注目度）: 91.8283876874947
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the Pareto frontier of two archetypal objectives in multi-armed bandits, namely, regret minimization (RM) and best arm identification (BAI) with a fixed horizon. It is folklore that the balance between exploitation and exploration is crucial for both RM and BAI, but exploration is more critical in achieving the optimal performance for the latter objective. To this end, we design and analyze the BoBW-lil'UCB$(\gamma)$ algorithm. Complementarily, by establishing lower bounds on the regret achievable by any algorithm with a given BAI failure probability, we show that (i) no algorithm can simultaneously perform optimally for both the RM and BAI objectives, and (ii) BoBW-lil'UCB$(\gamma)$ achieves order-wise optimal performance for RM or BAI under different values of $\gamma$. Our work elucidates the trade-off more precisely by showing how the constants in previous works depend on certain hardness parameters. Finally, we show that BoBW-lil'UCB outperforms a close competitor UCB$_\alpha$ (Degenne et al., 2019) in terms of the time complexity and the regret on diverse datasets such as MovieLens and Published Kinase Inhibitor Set.
• Abstract（参考訳）: 多腕包帯における2つの根尖目標のパレートフロンティア、すなわち、後悔最小化(RM)とベストアーム識別(BAI)を固定地平線で検討した。 RMとBAIの双方にとって, エクスプロイトと探索のバランスは重要であるが, 後者の目的を達成するためには, 探索がより重要である。 この目的のために,BoBW-lil'UCB$(\gamma)$アルゴリズムの設計と解析を行う。 補足的に、与えられた bai の失敗確率を持つ任意のアルゴリズムで達成可能な後悔の限界を低く設定することで、そのことを示す。 i)RMとBAIの両方の目的に対して最適なアルゴリズムを同時に実行することができず、 (ii) BoBW-lil'UCB$(\gamma)$ は RM または BAI に対して$\gamma$ の異なる値で順番に最適な性能を達成する。 我々の研究は、以前の作業の定数が特定の硬さパラメータに依存するかを示すことによって、トレードオフをより正確に解明する。 最後に、BoBW-lil'UCBは、時間複雑性とMovieLensやPublished Kinase Inhibitor Setといった多様なデータセットに対する後悔の点において、競合するUCB$_\alpha$(Degenne et al., 2019)を上回っていることを示す。

関連論文リスト

• Best Arm Identification with Minimal Regret [55.831935724659175]
  最高の腕識別問題 優雅にアマルガメートは、最小化とBAIを後悔している。 エージェントの目標は、所定の信頼度で最高の腕を特定することである。 二重KL-UCBアルゴリズムは、信頼度がゼロになる傾向があるため、最適性を達成する。
  論文  参考訳（メタデータ） (2024-09-27T16:46:02Z)
• UCB Exploration for Fixed-Budget Bayesian Best Arm Identification [0.0]
  固定予算設定におけるベストアーム識別(BAI)について検討した。 ベイズ条件下での固定予算BAI問題に対して理論的かつ実験的に効率的であるUPB探索アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-08-09T05:15:36Z)
• Fast and Regret Optimal Best Arm Identification: Fundamental Limits and Low-Complexity Algorithms [15.038210624870656]
  2つの目的を持つマルチアーメッド・バンドイット(MAB)問題: (i) 最適なアームに対する迅速な識別とコミットメント、および (ii) 連続したラウンドで連続して$T$の報酬。 本稿では,これら2つの目的を達成することを目的としたemphRegret Best Arm Identification (ROBAI)を紹介する。
  論文  参考訳（メタデータ） (2023-09-01T17:12:43Z)
• Multi-Fidelity Multi-Armed Bandits Revisited [46.19926456682379]
  我々は,MF-MAB(Multi-fidelity multi-armed bandit)問題の拡張であるMF-MAB(Multi-fidelity multi-armed bandit)について検討した。 MF-MABは、各アームを異なるコスト(忠実さ)と観察精度で引っ張ることができる。
  論文  参考訳（メタデータ） (2023-06-13T13:19:20Z)
• Batch-Size Independent Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms or Independent Arms [59.8188496313214]
  半帯域 (CMAB) について検討し, 半帯域 (CMAB) におけるバッチサイズ (K$) の依存性の低減に着目した。 まず,確率的に引き起こされるアーム(CMAB-T)を用いたCMABの設定に対して,分散を考慮した信頼区間を持つBCUCB-Tアルゴリズムを提案する。 次に,独立アームを用いた非トリガ型CMABの設定に対して,TPVM条件の非トリガ型を利用したSESCBアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-08-31T13:09:39Z)
• Adversarially Robust Multi-Armed Bandit Algorithm with Variance-Dependent Regret Bounds [34.37963000493442]
  本稿では,マルチアーム・バンディット(MAB)問題について考察し,両対向的条件下でほぼ最適に機能する,新たなベスト・オブ・ボス・ワールド(BOBW)アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-06-14T12:58:46Z)
• Best Arm Identification under Additive Transfer Bandits [49.69203462561861]
  提案手法は, 未知であるにもかかわらず, ソースとターゲットMABインスタンスの間には, 付加的な関係があることが知られている。 本稿では,LUCBスタイルのアルゴリズムを理論的に解析し,高い確率で$epsilon$-optimal target armを同定する。
  論文  参考訳（メタデータ） (2021-12-08T02:20:18Z)
• Restless-UCB, an Efficient and Low-complexity Algorithm for Online Restless Bandits [61.490254407420906]
  我々は、各腕の状態がマルコフ連鎖に従って進化するオンラインレス・バンディット問題について研究する。 本研究では,探索研究の枠組みに従う学習方針であるReestless-UCBを提案する。
  論文  参考訳（メタデータ） (2020-11-05T05:16:04Z)
• Lenient Regret for Multi-Armed Bandits [72.56064196252498]
  エージェントが順番に行動を選択し、その行動に対する報酬を観察するマルチアーマッド・バンディット(MAB)問題を考察する。 アルゴリズムの大多数は、後悔、すなわち最高の行動の報酬とエージェントの行動の累積的な差を最小化しようとするが、この基準は望ましくない結果をもたらすかもしれない。 我々は、いくつかの$epsilon$よりも小さな最適性ギャップを無視した、より寛大で寛大で後悔すべき基準を提案する。
  論文  参考訳（メタデータ） (2020-08-10T08:30:52Z)

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

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