論文の概要: 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 Fixed Budget: A Large Deviation Perspective [54.305323903582845]
我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
論文 参考訳(メタデータ) (2023-12-19T13:17:43Z) - Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits [56.457634640638254]
本稿では, 一般化線形モデル(GLM)から, デュエルアームのバイナリ比較を生成するコンテキストデュエルバンド問題について検討する。
本稿では,SupLinUCB型アルゴリズムを提案する。このアルゴリズムは,計算効率と分散を意識したリセットバウンド$tilde Obig(dsqrtsum_t=1Tsigma_t2 + dbig)$を提案する。
我々の後悔は、比較が決定論的である場合の直感的な期待と自然に一致し、アルゴリズムは$tilde O(d)$ regretにのみ悩まされる。
論文 参考訳(メタデータ) (2023-10-02T08:15:52Z) - Complexity Analysis of a Countable-armed Bandit Problem [9.163501953373068]
遊びの地平線上で期待される累積的後悔を最小限に抑えるという古典的問題を考察する。
我々は、$K=2$のとき、$mathcalOleft(log n right)$の率最適有限時間インスタンス依存後悔を実現するアルゴリズムを提案する。
問題に対する後悔の順序と複雑さは、古典的MAB問題と非常に類似していることを示しているが、アルゴリズム設計における性能境界の特性と健全な側面は、後者とはかなり異なる。
論文 参考訳(メタデータ) (2023-01-18T00:53:46Z) - Finite-Time Regret of Thompson Sampling Algorithms for Exponential
Family Multi-Armed Bandits [88.21288104408556]
本研究では,指数関数族バンドイットに対するトンプソンサンプリング (TS) アルゴリズムの遺残について検討する。
最適な腕の過小評価を避けるために,新しいサンプリング分布を用いたトンプソンサンプリング(Expulli)を提案する。
論文 参考訳(メタデータ) (2022-06-07T18:08:21Z) - The Countable-armed Bandit with Vanishing Arms [8.099977107670918]
我々は、数え切れないほど多くの腕を有限個の「型」に分割したバンドイット問題を考える。
非定常分布は、腕の個体群における各腕型の相対的な存在量を支配しており、いわゆる「腕貯水池」である。
論文 参考訳(メタデータ) (2021-10-23T02:47: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) - 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 [14.834625066344584]
我々は、サブサンプルのグリードアルゴリズムが、多くの武装政権におけるベルヌーイの盗賊に対するレート最適化であることを示している。
これらの結果は、欲求アルゴリズムの恩恵を受ける多腕体制における新たな自由探索形態を示唆している。
論文 参考訳(メタデータ) (2020-02-24T08:59:34Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。