論文の概要: Diffusion Approximations for Thompson Sampling
- arxiv url: http://arxiv.org/abs/2105.09232v1
- Date: Wed, 19 May 2021 16:28:01 GMT
- ステータス: 処理完了
- システム内更新日: 2021-05-20 13:37:22.039954
- Title: Diffusion Approximations for Thompson Sampling
- Title(参考訳): トンプソンサンプリングのための拡散近似
- Authors: Lin Fan, Peter W. Glynn
- Abstract要約: 我々はトンプソンサンプリングのダイナミクスがSDEとランダムODEの離散バージョンに応じて進化していることを示す。
我々の弱収束理論は古典的な多重武装と線形バンディットの設定の両方をカバーしている。
我々の理論は第一原理から発展し、他のサンプリングベースの帯域幅アルゴリズムの解析にも適用できる。
- 参考スコア(独自算出の注目度): 9.384123241346382
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the behavior of Thompson sampling from the perspective of weak
convergence. In the regime where the gaps between arm means scale as
$1/\sqrt{n}$ with the time horizon $n$, we show that the dynamics of Thompson
sampling evolve according to discrete versions of SDEs and random ODEs. As $n
\to \infty$, we show that the dynamics converge weakly to solutions of the
corresponding SDEs and random ODEs. (Recently, Wager and Xu (arXiv:2101.09855)
independently proposed this regime and developed similar SDE and random ODE
approximations.) Our weak convergence theory covers both the classical
multi-armed and linear bandit settings, and can be used, for instance, to
obtain insight about the characteristics of the regret distribution when there
is information sharing among arms, as well as the effects of variance
estimation, model mis-specification and batched updates in bandit learning. Our
theory is developed from first-principles and can also be adapted to analyze
other sampling-based bandit algorithms.
- Abstract(参考訳): 我々は弱い収束の観点からトンプソンサンプリングの挙動を研究する。
アーム間のギャップが1/\sqrt{n}$と時間的地平線$n$となる状態において、トンプソンサンプリングのダイナミクスはSDEとランダムODEの離散バージョンに従って進化することを示す。
n \to \infty$ として、力学は対応する SDE およびランダムODE の解に弱収束することを示す。
(近年、WagerとXu(arXiv:2101.09855)は独立してこの体制を提唱し、SDEとランダムODE近似を開発した。)
我々の弱い収束理論は、古典的マルチアームと線形バンディットの設定の両方をカバーしており、例えば、アーム間での情報共有がある場合の後悔分布の特性や、分散推定、モデルミス特定、およびバンドディット学習におけるバッチ更新の影響の洞察を得るのに利用できる。
この理論は第一原理から開発され、他のサンプリングベースのバンディットアルゴリズムの解析にも応用できる。
関連論文リスト
- Gaussian Mixture Solvers for Diffusion Models [84.83349474361204]
本稿では,拡散モデルのためのGMSと呼ばれる,SDEに基づく新しい解法について紹介する。
画像生成およびストロークベース合成におけるサンプル品質の観点から,SDEに基づく多くの解法よりも優れる。
論文 参考訳(メタデータ) (2023-11-02T02:05:38Z) - VITS : Variational Inference Thomson Sampling for contextual bandits [11.878329445504527]
我々は、文脈的帯域幅に対するトンプソンサンプリング(TS)アルゴリズムの変種を導入・解析する。
ガウス変分推論に基づく新しいアルゴリズムであるValational Inference Thompson sample VITSを提案する。
我々は,VITS が線形文脈帯域に対して従来の TS の次元とラウンド数で同じ順序のサブ線形後悔境界を達成することを示す。
論文 参考訳(メタデータ) (2023-07-19T17:53:22Z) - Towards Faster Non-Asymptotic Convergence for Diffusion-Based Generative
Models [49.81937966106691]
我々は拡散モデルのデータ生成過程を理解するための非漸近理論のスイートを開発する。
従来の研究とは対照的に,本理論は基本的だが多目的な非漸近的アプローチに基づいて開発されている。
論文 参考訳(メタデータ) (2023-06-15T16:30:08Z) - A Geometric Perspective on Diffusion Models [60.69328526215776]
本稿では,人気のある分散拡散型SDEのODEに基づくサンプリングを検証し,そのサンプリングダイナミクスの興味深い構造を明らかにした。
我々は、最適なODEベースのサンプリングと古典的な平均シフト(モード探索)アルゴリズムの理論的関係を確立する。
論文 参考訳(メタデータ) (2023-05-31T15:33:16Z) - Finite-Time Regret of Thompson Sampling Algorithms for Exponential
Family Multi-Armed Bandits [88.21288104408556]
本研究では,指数関数族バンドイットに対するトンプソンサンプリング (TS) アルゴリズムの遺残について検討する。
最適な腕の過小評価を避けるために,新しいサンプリング分布を用いたトンプソンサンプリング(Expulli)を提案する。
論文 参考訳(メタデータ) (2022-06-07T18:08:21Z) - Improving Robustness and Uncertainty Modelling in Neural Ordinary
Differential Equations [0.2538209532048866]
本研究では,NODE における不確実性をモデル化するための新しい手法を提案する。
また、各データポイントが終末時間に異なる後続分布を持つことができる適応遅延時間NODE(ALT-NODE)を提案する。
本研究では,合成画像と実世界の画像分類データを用いた実験により,不確実性とロバスト性をモデル化する手法の有効性を実証する。
論文 参考訳(メタデータ) (2021-12-23T16:56:10Z) - From Optimality to Robustness: Dirichlet Sampling Strategies in
Stochastic Bandits [0.0]
本研究では、腕の観察を再サンプリングした経験的指標のペア比較に基づいて、ジェネリックディリクレサンプリング(DS)アルゴリズムについて検討する。
この戦略の異なる変種は、分布が有界であるときに証明可能な最適後悔保証と、半有界分布に対して軽度量子状態の対数後悔を実現することを示す。
論文 参考訳(メタデータ) (2021-11-18T14:34:21Z) - A Unifying Theory of Thompson Sampling for Continuous Risk-Averse
Bandits [91.3755431537592]
本稿では,多腕バンディット問題に対するリスク-逆トンプソンサンプリングアルゴリズムの解析を統一する。
大規模偏差理論における収縮原理を用いることで、連続リスク汎関数に対する新しい濃度境界が証明される。
リスク関数の幅広いクラスと「ニセ」関数が連続性条件を満たすことを示す。
論文 参考訳(メタデータ) (2021-08-25T17:09:01Z) - Random Effect Bandits [22.322646330965476]
我々は,古典的なオンライン学習問題であるマルチアームバンディットの後悔について研究する。
実験の結果,ReUCBは様々なシナリオにおいてトンプソンサンプリングより優れていることがわかった。
論文 参考訳(メタデータ) (2021-06-23T07:15:31Z) - Analysis and Design of Thompson Sampling for Stochastic Partial
Monitoring [91.22679787578438]
部分モニタリングのためのトンプソンサンプリングに基づく新しいアルゴリズムを提案する。
局所可観測性を持つ問題の線形化変種に対して,新たなアルゴリズムが対数問題依存の擬似回帰$mathrmO(log T)$を達成することを証明した。
論文 参考訳(メタデータ) (2020-06-17T05:48:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。