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

• arxiv url: http://arxiv.org/abs/2109.13595v1
• Date: Tue, 28 Sep 2021 10:11:06 GMT
• ステータス: 処理完了
• システム内更新日: 2021-09-29 14:31:40.472049
• Title: The Fragility of Optimized Bandit Algorithms
• Title（参考訳）: 最適化バンドアルゴリズムの脆弱性
• Authors: Lin Fan and Peter W. Glynn
• Abstract要約: 帯域幅アルゴリズムの最適設計に関する文献の多くは、期待される後悔の最小化に基づいている。 このような最適化された設計を使用する場合、関連するアルゴリズムは、後悔分布の尾部が不規則なコーシー分布のように振る舞うような望ましくない特徴を持つことを示す。 最適化されたトンプソンサンプリングと UCB バンディット設計も脆弱であることを示し,問題をわずかに誤特定した場合,その後悔は従来の理論よりはるかに早く増大することを示した。
• 参考スコア（独自算出の注目度）: 9.384123241346382
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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 associated algorithms necessarily have the undesirable feature that the tail of the regret distribution behaves like 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 number of sub-optimal arm plays. We show that optimized Thompson sampling and UCB bandit designs are also fragile, in the sense that 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 that make that arm appear to be sub-optimal, thereby causing the algorithm to sample a truly sub-optimal arm much more than would be optimal.
• Abstract（参考訳）: バンディットアルゴリズムの最適設計に関する多くの文献は、期待された後悔の最小化に基づいている。 ある指数関数族に対して最適である設計は、レイ・ロビンズの下界に支配される速度で、腕の遊びの数で対数的に増加する期待された後悔を達成できることはよく知られている。 本稿では,このような最適化設計を行う場合,関連するアルゴリズムは必ずしも,後悔分布の尾部が切れたコーシー分布のように振る舞うような望ましくない特徴を持つことを示す。 さらに、$p>1$では、後悔分布の$p$'thモーメントは、多対数に比較して、特に、サブ最適アームの回数のパワーとして急速に増加する。 最適化されたトンプソンサンプリングと 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)

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

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