論文の概要: On the Pareto Frontier of Regret Minimization and Best Arm Identification in Stochastic Bandits

• arxiv url: http://arxiv.org/abs/2110.08627v1
• Date: Sat, 16 Oct 2021 17:52:32 GMT
• ステータス: 処理完了
• システム内更新日: 2021-10-21 10:29:00.331461
• Title: On the Pareto Frontier of Regret Minimization and Best Arm Identification in Stochastic Bandits
• Title（参考訳）: 確率帯域におけるレギュレット最小化とベストアーム識別のパレートフロンティアについて
• Authors: Zixin Zhong, Wang Chi Cheung, Vincent Y. F. Tan
• Abstract要約: 悪用と探検のバランスは、後悔の最小化(RM)と固定水平線を持つ最高の腕識別(BAI)の両方に不可欠である。 本稿ではまず, RM や BAI の順番最適性能を実現するBOBW-lil'UCB$(gamma)$アルゴリズムの設計と解析を行う。 与えられたBAI故障確率を持つ任意のアルゴリズムによって達成可能な後悔に対する非自明な下界を確立する。
• 参考スコア（独自算出の注目度）: 90.49629596156473
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the Pareto frontier of two archetypal objectives in stochastic 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 make this precise, we first design and analyze the BoBW-lil'UCB$({\gamma})$ algorithm, which achieves order-wise optimal performance for RM or BAI under different values of ${\gamma}$. Complementarily, we show that no algorithm can simultaneously perform optimally for both the RM and BAI objectives. More precisely, we establish non-trivial lower bounds on the regret achievable by any algorithm with a given BAI failure probability. This analysis shows that in some regimes BoBW-lil'UCB$({\gamma})$ achieves Pareto-optimality up to constant or small terms. Numerical experiments further demonstrate that when applied to difficult instances, BoBW-lil'UCB outperforms a close competitor UCB$_{\alpha}$ (Degenne et al., 2019), which is designed for RM and BAI with a fixed confidence.
• Abstract（参考訳）: 確率的包帯における2つの根尖目標のパレートフロンティア、すなわち、後悔の最小化(RM)とベストアーム識別(BAI)を固定地平線で検討した。 RMとBAIの双方にとって, エクスプロイトと探索のバランスは重要であるが, 後者の目的を達成するためには, 探索がより重要である。 これを正確にするために、まずbobw-lil'ucb$({\gamma})$アルゴリズムを設計・解析し、${\gamma}$の異なる値の下でrmまたはbaiのオーダーワイズ最適性能を達成する。 補完的に、RMとBAIの両方の目的に対して最適なアルゴリズムを同時に実行できないことを示す。 より正確には、与えられたBAI失敗確率を持つ任意のアルゴリズムによって達成可能な後悔に対する非自明な下界を確立する。 この分析は、いくつかのレジームにおいて、BoBW-lil'UCB$({\gamma})$ はパレート最適性を定数あるいは小項まで達成していることを示している。 さらに、難しい事例に適用した場合、BoBW-lil'UCB は RM と BAI のために固定された信頼度で設計された近接競合 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)

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

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