論文の概要: Asymptotic Convergence of Thompson Sampling

• arxiv url: http://arxiv.org/abs/2011.03917v1
• Date: Sun, 8 Nov 2020 07:36:49 GMT
• ステータス: 処理完了
• システム内更新日: 2022-09-28 08:54:14.557171
• Title: Asymptotic Convergence of Thompson Sampling
• Title（参考訳）: トンプソンサンプリングの漸近収束
• Authors: Cem Kalkanli, Ayfer Ozgur
• Abstract要約: トンプソンサンプリングは、様々なオンライン学習タスクにおいて効果的なポリシーであることが示されている。 我々は、準線形ベイズ的後悔を仮定して、トンプソンサンプリングの収束結果を証明した。 この結果はトンプソンサンプリングに固有のマーチンゲール構造に依存している。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Thompson sampling has been shown to be an effective policy across a variety of online learning tasks. Many works have analyzed the finite time performance of Thompson sampling, and proved that it achieves a sub-linear regret under a broad range of probabilistic settings. However its asymptotic behavior remains mostly underexplored. In this paper, we prove an asymptotic convergence result for Thompson sampling under the assumption of a sub-linear Bayesian regret, and show that the actions of a Thompson sampling agent provide a strongly consistent estimator of the optimal action. Our results rely on the martingale structure inherent in Thompson sampling.
• Abstract（参考訳）: トンプソンサンプリングは、様々なオンライン学習タスクにまたがる効果的なポリシーであることが示されている。 多くの作品がトンプソンサンプリングの有限時間性能を分析し、幅広い確率的設定の下で線形な後悔を達成することを証明した。 しかし、その漸近的な行動はほとんど未調査のままである。 本稿では,半線形ベイズ的後悔を仮定して,トンプソンサンプリングの漸近収束結果を証明し,トンプソンサンプリングエージェントの作用が最適作用の強い一貫した推定値を与えることを示す。 我々の結果は、トンプソンサンプリングに固有のマルティンゲール構造に依存している。

関連論文リスト

• Finite-Time Regret of Thompson Sampling Algorithms for Exponential Family Multi-Armed Bandits [88.21288104408556]
  本研究では,指数関数族バンドイットに対するトンプソンサンプリング (TS) アルゴリズムの遺残について検討する。 最適な腕の過小評価を避けるために,新しいサンプリング分布を用いたトンプソンサンプリング(Expulli)を提案する。
  論文  参考訳（メタデータ） (2022-06-07T18:08:21Z)
• Asymptotic Performance of Thompson Sampling in the Batched Multi-Armed Bandits [0.0]
  我々は,トンプソンサンプリングがバッチで遅延フィードバックを受信しても,その性能を維持可能であることを示す。 同じ性能を維持しつつ,バッチ数を$Theta(log T)$に削減する適応型スキームを提案する。
  論文  参考訳（メタデータ） (2021-10-01T01:28:40Z)
• A Unifying Theory of Thompson Sampling for Continuous Risk-Averse Bandits [91.3755431537592]
  本稿では,多腕バンディット問題に対するリスク-逆トンプソンサンプリングアルゴリズムの解析を統一する。 大規模偏差理論における収縮原理を用いることで、連続リスク汎関数に対する新しい濃度境界が証明される。 リスク関数の幅広いクラスと「ニセ」関数が連続性条件を満たすことを示す。
  論文  参考訳（メタデータ） (2021-08-25T17:09:01Z)
• On the Suboptimality of Thompson Sampling in High Dimensions [7.198362232890585]
  我々は、トンプソンサンプリングが半帯域の準最適であることを実証する。 トンプソンサンプリングは、高次元において非常に低性能であることを示す。
  論文  参考訳（メタデータ） (2021-02-10T15:44:43Z)
• Policy Gradient Optimization of Thompson Sampling Policies [3.3345263849085582]
  一般化されたトンプソンサンプリングポリシーのクラスにおいて、ポリシー勾配アルゴリズムを用いて最適化する。 我々は,トンプソンサンプリング上での直接ポリシー探索が,アルゴリズムの既知の欠点のいくつかを自動的に修正することを示した。
  論文  参考訳（メタデータ） (2020-06-30T03:27:22Z)
• Analysis and Design of Thompson Sampling for Stochastic Partial Monitoring [91.22679787578438]
  部分モニタリングのためのトンプソンサンプリングに基づく新しいアルゴリズムを提案する。 局所可観測性を持つ問題の線形化変種に対して,新たなアルゴリズムが対数問題依存の擬似回帰$mathrmO(log T)$を達成することを証明した。
  論文  参考訳（メタデータ） (2020-06-17T05:48:33Z)
• Statistical Efficiency of Thompson Sampling for Combinatorial Semi-Bandits [56.31950477139053]
  半帯域フィードバック(CMAB)を用いたマルチアームバンディットの検討 我々は Combinatorial Thompson Smpling Policy (CTS) の変種を解析する。 この最終結果は,Y Combinatorial Bandit Policy (ESCB) の効率的なサンプリングに代わるものだ。
  論文  参考訳（メタデータ） (2020-06-11T17:12:11Z)
• 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)

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

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