論文の概要: The Typical Behavior of Bandit Algorithms

• arxiv url: http://arxiv.org/abs/2210.05660v1
• Date: Tue, 11 Oct 2022 17:56:01 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-12 17:56:21.828340
• Title: The Typical Behavior of Bandit Algorithms
• Title（参考訳）: バンディットアルゴリズムの典型的な挙動
• Authors: Lin Fan, Peter W. Glynn
• Abstract要約: 我々は、トンプソンサンプリング(Thompson sample)と UCB (UCB) の2つを後悔するために、大数の法則と中心極限定理を定めている。 後悔分布のキャラクタリゼーションは,後悔分布の尾のキャラクタリゼーションを補完する。
• 参考スコア（独自算出の注目度）: 6.973549388623401
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We establish strong laws of large numbers and central limit theorems for the regret of two of the most popular bandit algorithms: Thompson sampling and UCB. Here, our characterizations of the regret distribution complement the characterizations of the tail of the regret distribution recently developed by Fan and Glynn (2021) (arXiv:2109.13595). The tail characterizations there are associated with atypical bandit behavior on trajectories where the optimal arm mean is under-estimated, leading to mis-identification of the optimal arm and large regret. In contrast, our SLLN's and CLT's here describe the typical behavior and fluctuation of regret on trajectories where the optimal arm mean is properly estimated. We find that Thompson sampling and UCB satisfy the same SLLN and CLT, with the asymptotics of both the SLLN and the (mean) centering sequence in the CLT matching the asymptotics of expected regret. Both the mean and variance in the CLT grow at $\log(T)$ rates with the time horizon $T$. Asymptotically as $T \to \infty$, the variability in the number of plays of each sub-optimal arm depends only on the rewards received for that arm, which indicates that each sub-optimal arm contributes independently to the overall CLT variance.
• Abstract（参考訳）: 我々は、最も人気のあるバンディットアルゴリズムであるトンプソンサンプリングとucbの後悔のために、大きな数の強い法則と中心極限定理を確立する。 ここで、後悔分布の特性は、最近Fan and Glynn (2021) (arXiv:2109.13595) によって開発された後悔分布の尾の特性を補完する。 尾部の特徴は、最適腕の平均値が過小評価される軌道上の非定型的包帯行動と関連しており、最適腕の誤同定と大きな後悔をもたらす。 対照的に、我々のSLLNとCLTは、最適な腕の平均が適切に推定される軌道上での後悔の典型的な挙動と変動を記述している。 我々は, トンプソンサンプリングと UCB が同じ SLLN と CLT を満たすこと, SLLN と (平均) 中心配列の両方の漸近が, 期待された後悔の漸近と一致することを見出した。 CLTの平均と分散はともに、時間軸の$T$で$\log(T)$レートで成長する。 漸近的に$T \to \infty$として、各サブ最適アームのプレイ数の変動は、各サブ最適アームが全体のCLT分散に独立に寄与することを示す、そのアームに対して受け取った報酬にのみ依存する。

関連論文リスト

• Best Arm Identification with Minimal Regret [55.831935724659175]
  最高の腕識別問題 優雅にアマルガメートは、最小化とBAIを後悔している。 エージェントの目標は、所定の信頼度で最高の腕を特定することである。 二重KL-UCBアルゴリズムは、信頼度がゼロになる傾向があるため、最適性を達成する。
  論文  参考訳（メタデータ） (2024-09-27T16:46:02Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
  論文  参考訳（メタデータ） (2023-12-13T11:08:25Z)
• 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)
• Mean-based Best Arm Identification in Stochastic Bandits under Reward Contamination [80.53485617514707]
  本稿では,ギャップベースアルゴリズムと逐次除去に基づく2つのアルゴリズムを提案する。 具体的には、ギャップベースのアルゴリズムでは、サンプルの複雑さは定数要素まで最適であり、連続的な除去では対数因子まで最適である。
  論文  参考訳（メタデータ） (2021-11-14T21:49:58Z)
• 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)
• The Fragility of Optimized Bandit Algorithms [4.390757904176221]
  帯域幅アルゴリズムの最適設計に関する文献の多くは、期待される後悔の脆弱さに基づいている。 最適化された UCB バンディットの設計は,問題をわずかに誤定義した場合に脆弱であることを示す。 提案手法は, 誤り特定に対する強靭性を確保するために, UCBアルゴリズムを改良可能であることを示す。
  論文  参考訳（メタデータ） (2021-09-28T10:11:06Z)
• Asymptotically Optimal Bandits under Weighted Information [10.939683083130616]
  エージェントが各ラウンドで複数のアームを演奏できるマルチアームバンディット装置における後悔の問題について検討する。 本稿では,Thompson-Sampling ベースの戦略を提案する。この戦略は,各腕が最高の腕であるという後続の信念として,パワープロファイルを設計する。
  論文  参考訳（メタデータ） (2021-05-28T21:28:44Z)
• 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)

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

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