論文の概要: 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近似を開発した。) 我々の弱い収束理論は、古典的マルチアームと線形バンディットの設定の両方をカバーしており、例えば、アーム間での情報共有がある場合の後悔分布の特性や、分散推定、モデルミス特定、およびバンドディット学習におけるバッチ更新の影響の洞察を得るのに利用できる。 この理論は第一原理から開発され、他のサンプリングベースのバンディットアルゴリズムの解析にも応用できる。

関連論文リスト

• VITS : Variational Inference Thompson Sampling for contextual bandits [10.028119153832346]
  我々は、文脈的帯域幅に対するトンプソンサンプリング(TS)アルゴリズムの変種を導入・解析する。 ガウス変分推論に基づく新しいアルゴリズムであるValational Inference Thompson sample VITSを提案する。 我々は,VITS が線形文脈帯域に対して従来の TS の次元とラウンド数で同じ順序のサブ線形後悔境界を達成することを示す。
  論文  参考訳（メタデータ） (2023-07-19T17:53:22Z)
• Langevin Monte Carlo for Contextual Bandits [72.00524614312002]
  Langevin Monte Carlo Thompson Sampling (LMC-TS) が提案されている。 提案アルゴリズムは,文脈的帯域幅の特別な場合において,最高のトンプソンサンプリングアルゴリズムと同じサブ線形残差を達成できることを示す。
  論文  参考訳（メタデータ） (2022-06-22T17:58:23Z)
• Finite-Time Regret of Thompson Sampling Algorithms for Exponential Family Multi-Armed Bandits [88.21288104408556]
  本研究では,指数関数族バンドイットに対するトンプソンサンプリング (TS) アルゴリズムの遺残について検討する。 最適な腕の過小評価を避けるために,新しいサンプリング分布を用いたトンプソンサンプリング(Expulli)を提案する。
  論文  参考訳（メタデータ） (2022-06-07T18:08:21Z)
• A Unifying Theory of Thompson Sampling for Continuous Risk-Averse Bandits [91.3755431537592]
  本稿では,多腕バンディット問題に対するリスク-逆トンプソンサンプリングアルゴリズムの解析を統一する。 大規模偏差理論における収縮原理を用いることで、連続リスク汎関数に対する新しい濃度境界が証明される。 リスク関数の幅広いクラスと「ニセ」関数が連続性条件を満たすことを示す。
  論文  参考訳（メタデータ） (2021-08-25T17:09:01Z)
• Thompson Sampling for Unimodal Bandits [21.514495320038712]
  本稿では, 半順序の腕に対して期待される報酬が一様であるアンフンモダル・バンディットに対するトンプソンサンプリングアルゴリズムを提案する。 ガウスの報酬に対して、我々のアルゴリズムの後悔は$mathcalO(log T)$であり、標準的なトンプソンサンプリングアルゴリズムよりもはるかに優れている。
  論文  参考訳（メタデータ） (2021-06-15T14:40:34Z)
• Analysis and Design of Thompson Sampling for Stochastic Partial Monitoring [91.22679787578438]
  部分モニタリングのためのトンプソンサンプリングに基づく新しいアルゴリズムを提案する。 局所可観測性を持つ問題の線形化変種に対して,新たなアルゴリズムが対数問題依存の擬似回帰$mathrmO(log T)$を達成することを証明した。
  論文  参考訳（メタデータ） (2020-06-17T05:48:33Z)
• MOTS: Minimax Optimal Thompson Sampling [89.2370817955411]
  トンプソンサンプリングがミニマックス下限の$Omega(sqrtKT)$と$K$の武器付きバンディット問題に一致するかどうかという未解決の問題のままである。 我々は,各タイミングで選択した腕のサンプリングインスタンスを適応的にクリップするMOTSと呼ばれるトンプソンサンプリングの変種を提案する。 我々は、この単純なトンプソンサンプリングの変種が、有限時間地平線に対して$O(sqrtKT)$のミニマックス最適後悔境界と、$T$が無限に近づくときのガウス報酬に対する最適後悔境界を達成することを証明した。
  論文  参考訳（メタデータ） (2020-03-03T21:24:39Z)
• On Thompson Sampling with Langevin Algorithms [106.78254564840844]
  多武装バンディット問題に対するトンプソンサンプリングは理論と実践の両方において良好な性能を享受する。 計算上のかなりの制限に悩まされており、反復ごとに後続分布からのサンプルを必要とする。 本稿では,この問題に対処するために,トンプソンサンプリングに適した2つのマルコフ連鎖モンテカルロ法を提案する。
  論文  参考訳（メタデータ） (2020-02-23T22:35:29Z)
• Ensemble Sampling [18.85309520133554]
  本稿では,ニューラルネットワークのような複雑なモデルに直面した場合でも,トラクタビリティを維持しつつ,トンプソンサンプリングを近似するアンサンブルサンプリングを開発する。 我々は、このアプローチを支持する理論的基盤を確立し、さらなる洞察を提供する計算結果を示す。
  論文  参考訳（メタデータ） (2017-05-20T19:36:36Z)

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

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