論文の概要: 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分散に独立に寄与することを示す、そのアームに対して受け取った報酬にのみ依存する。
関連論文リスト
- Clustered Switchback Experiments: Near-Optimal Rates Under
Spatiotemporal Interference [50.17596656599103]
我々は, 平均治療効果 (GATE) を推定し, 全単位を常に治療やコントロールに曝露した平均結果の差を推定した。
そこで我々は,単位をクラスタにグループ化し,時間ステップをブロックにグループ化する,クラスタ化されたスイッチバック設計を提案する。
良好なクラスタリングを許容するグラフに対して,Horvitz-Thompson推定器が$tilde O(1/NT)$ mean-squared error (MSE)を達成し,$Omega (1/NT)$ lower bound to logarithmic termsと一致することを示す。
論文 参考訳(メタデータ) (2023-12-25T01:00:58Z) - Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。
SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
論文 参考訳(メタデータ) (2023-12-13T11:08:25Z) - Combinatorial Bandits for Maximum Value Reward Function under Max
Value-Index Feedback [9.771002043127728]
本稿では,最大値報酬関数に対する最大値と指数フィードバックに基づくマルチアームバンディット問題を考察する。
有限なサポートを持つ任意の分布にしたがって、アーム結果を持つ問題インスタンスに対して、アルゴリズムを提案し、後悔の束縛を与える。
我々のアルゴリズムは、$O(((k/Delta)log(T))$ distribution-dependent と $tildeO(sqrtT)$ distribution-independent regret を達成する。
論文 参考訳(メタデータ) (2023-05-25T14:02:12Z) - 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 [6.973549388623401]
帯域幅アルゴリズムの最適設計に関する文献の多くは、期待される後悔の脆弱さに基づいている。
最適化された 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。