論文の概要: The Fragility of Optimized Bandit Algorithms

• arxiv url: http://arxiv.org/abs/2109.13595v8
• Date: Tue, 12 Nov 2024 21:17:48 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-15 15:22:49.575503
• Title: The Fragility of Optimized Bandit Algorithms
• Title（参考訳）: 最適化バンドアルゴリズムの脆弱性
• Authors: Lin Fan, Peter W. Glynn,
• Abstract要約: 帯域幅アルゴリズムの最適設計に関する文献の多くは、期待される後悔の脆弱さに基づいている。 最適化された UCB バンディットの設計は,問題をわずかに誤定義した場合に脆弱であることを示す。 提案手法は, 誤り特定に対する強靭性を確保するために, UCBアルゴリズムを改良可能であることを示す。
• 参考スコア（独自算出の注目度）: 4.390757904176221
• License:
• Abstract: Much of the literature on optimal design of bandit algorithms is based on minimization of expected regret. It is well known that designs that are optimal over certain exponential families can achieve expected regret that grows logarithmically in the number of arm plays, at a rate governed by the Lai-Robbins lower bound. In this paper, we show that when one uses such optimized designs, the regret distribution of the associated algorithms necessarily has a very heavy tail, specifically, that of a truncated Cauchy distribution. Furthermore, for $p>1$, the $p$'th moment of the regret distribution grows much faster than poly-logarithmically, in particular as a power of the total number of arm plays. We show that optimized UCB bandit designs are also fragile in an additional sense, namely when the problem is even slightly mis-specified, the regret can grow much faster than the conventional theory suggests. Our arguments are based on standard change-of-measure ideas, and indicate that the most likely way that regret becomes larger than expected is when the optimal arm returns below-average rewards in the first few arm plays, thereby causing the algorithm to believe that the arm is sub-optimal. To alleviate the fragility issues exposed, we show that UCB algorithms can be modified so as to ensure a desired degree of robustness to mis-specification. In doing so, we also show a sharp trade-off between the amount of UCB exploration and the heaviness of the resulting regret distribution tail.
• Abstract（参考訳）: 帯域幅アルゴリズムの最適設計に関する文献の多くは、期待される後悔の最小化に基づいている。 ある指数関数族に対して最適である設計は、レイ・ロビンズの下界に支配される速度で、腕の遊びの数で対数的に増加する期待された後悔を達成できることはよく知られている。 本稿では、そのような最適化された設計を用いる場合、関連するアルゴリズムの後悔の分布は、必ずしも非常に重い尾、具体的には、切り詰められたコーシー分布を持つ。 さらに、$p>1$の場合、後悔分布の$p$'th モーメントは多対数的よりもはるかに速く成長する。 最適化された UCB バンディットの設計は, 若干の誤特定が生じた場合, 従来の理論よりはるかに早く, より脆弱であることを示す。 我々の議論は、標準的な測定の考え方に基づいており、予想よりも後悔が大きくなる可能性が最も高いのは、最初の数本の腕で、最適腕が平均以下の報酬を返すときであり、その結果、アルゴリズムがアームが最適以下であると信じるようになることである。 露呈した脆弱性の問題を軽減するため,UDBアルゴリズムは,不特定性に対して所望の堅牢性を確保するために変更可能であることを示す。 また, UCB探鉱量と, 結果として生じる残存分布の重みとの間には, 急激なトレードオフを示す。

関連論文リスト

• Best Arm Identification with Minimal Regret [55.831935724659175]
  最高の腕識別問題 優雅にアマルガメートは、最小化とBAIを後悔している。 エージェントの目標は、所定の信頼度で最高の腕を特定することである。 二重KL-UCBアルゴリズムは、信頼度がゼロになる傾向があるため、最適性を達成する。
  論文  参考訳（メタデータ） (2024-09-27T16:46:02Z)
• Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
  我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。 特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
  論文  参考訳（メタデータ） (2023-12-19T13:17:43Z)
• Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits [53.281230333364505]
  本稿では, 一般化線形モデル(GLM)から, デュエルアームのバイナリ比較を生成するコンテキストデュエルバンド問題について検討する。 本稿では,SupLinUCB型アルゴリズムを提案する。このアルゴリズムは,計算効率と分散を意識したリセットバウンド$tilde Obig(dsqrtsum_t=1Tsigma_t2 + dbig)$を提案する。 我々の後悔は、比較が決定論的である場合の直感的な期待と自然に一致し、アルゴリズムは$tilde O(d)$ regretにのみ悩まされる。
  論文  参考訳（メタデータ） (2023-10-02T08:15:52Z)
• Suboptimal Performance of the Bayes Optimal Algorithm in Frequentist Best Arm Identification [5.176134438571082]
  正規分布による報酬を伴う固定予算ベストアーム識別問題を考察する。 この問題では、予測者は、腕(または治療)が$K$、タイムステップが$T$である。 アルゴリズムの性能は、推定されたベストアームの品質を反映して、単純な後悔によって評価される。
  論文  参考訳（メタデータ） (2022-02-10T17:50:26Z)
• 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)
• Regret Minimization in Heavy-Tailed Bandits [12.272975892517039]
  マルチアームバンディット設定における古典的後悔最小化問題を再考する。 本稿では,1次項における下界を正確に一致させる最適アルゴリズムを提案する。 我々の指数は、よく知られたトリミングまたはトリミングされた経験的平均推定値よりも速く集中していることを示す。
  論文  参考訳（メタデータ） (2021-02-07T07:46:24Z)
• Online Model Selection: a Rested Bandit Formulation [49.69377391589057]
  静止したバンディット設定における最善のアーム識別問題を紹介し,解析する。 我々は、この問題の後悔の新しい概念を定義し、ゲームの終わりに最小の期待損失を持つ腕を常に再生するポリシーと比較します。 最近のバンディット文献における既知のモデル選択の試みとは異なり、アルゴリズムは問題の特定の構造を利用して、予想される損失関数の未知のパラメータを学習する。
  論文  参考訳（メタデータ） (2020-12-07T08:23:08Z)
• Lenient Regret for Multi-Armed Bandits [72.56064196252498]
  エージェントが順番に行動を選択し、その行動に対する報酬を観察するマルチアーマッド・バンディット(MAB)問題を考察する。 アルゴリズムの大多数は、後悔、すなわち最高の行動の報酬とエージェントの行動の累積的な差を最小化しようとするが、この基準は望ましくない結果をもたらすかもしれない。 我々は、いくつかの$epsilon$よりも小さな最適性ギャップを無視した、より寛大で寛大で後悔すべき基準を提案する。
  論文  参考訳（メタデータ） (2020-08-10T08:30:52Z)
• 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)
• Bandits with Mean Bounds [33.00136718515412]
  本研究では,各アームの平均値に有界な側情報を与えるバンディット問題の変種について検討する。 これらがより厳密なガウス因子の推定に変換されることを証明し、これらの推定を利用する新しいアルゴリズムを開発する。
  論文  参考訳（メタデータ） (2020-02-19T19:36:43Z)

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

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