Fugu-MT 論文翻訳(概要): On the Suboptimality of Thompson Sampling in High Dimensions

論文の概要: On the Suboptimality of Thompson Sampling in High Dimensions

arxiv url: http://arxiv.org/abs/2102.05502v1
Date: Wed, 10 Feb 2021 15:44:43 GMT
ステータス: 処理完了
システム内更新日: 2021-02-11 14:44:15.107814
Title: On the Suboptimality of Thompson Sampling in High Dimensions
Title（参考訳）: 高次元トンプソンサンプリングの準最適性について
Authors: Raymond Zhang and Richard Combes
Abstract要約: 我々は、トンプソンサンプリングが半帯域の準最適であることを実証する。トンプソンサンプリングは、高次元において非常に低性能であることを示す。
参考スコア（独自算出の注目度）: 7.198362232890585
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: In this paper we consider Thompson Sampling for combinatorial semi-bandits. We demonstrate that, perhaps surprisingly, Thompson Sampling is sub-optimal for this problem in the sense that its regret scales exponentially in the ambient dimension, and its minimax regret scales almost linearly. This phenomenon occurs under a wide variety of assumptions including both non-linear and linear reward functions. We also show that including a fixed amount of forced exploration to Thompson Sampling does not alleviate the problem. We complement our theoretical results with numerical results and show that in practice Thompson Sampling indeed can perform very poorly in high dimensions.
Abstract（参考訳）: 本稿では,Thompson Sampling for combinatorial semi-banditsについて考察する。我々は、おそらく驚くべきことに、トンプソンサンプリングは、その後悔が周囲の次元において指数関数的にスケールし、ミニマックスの後悔がほぼ線形にスケールするという意味で、この問題に対して最適であることを示した。この現象は、非線形と線形の報酬関数を含む様々な仮定の下で起こる。また、Thompson Samplingに一定の量の強制探査を含めることは問題を軽減するものではないことも示しています。我々は理論結果を数値的な結果で補完し、実際にトンプソンサンプリングは高次元において非常に低性能であることを示す。

関連論文リスト

Accelerating Approximate Thompson Sampling with Underdamped Langevin Monte Carlo [7.968641076961955]
本稿では,Langevin Monte Carlo を用いた近似トンプソンサンプリング手法を提案する。標準スムーズ性および対数凹凸性条件に基づき,加速後濃度およびサンプリングについて検討した。提案アルゴリズムは,高次元バンディット問題における合成実験により実験的に検証される。
論文参考訳（メタデータ） (2024-01-22T02:54:58Z)
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)
Feel-Good Thompson Sampling for Contextual Bandits and Reinforcement Learning [17.860102738896096]
我々はトンプソンサンプリングの理論解析を行い、頻繁な後悔境界に焦点をあてる。我々は、トンプソンサンプリングが新しい行動の探索に十分な積極的ではないことを示し、悲観的な状況下では準最適性をもたらすことを示した。理論的枠組みは、標準的なトンプソンサンプリングに対するベイズ的後悔境界と、Feel-Good Thompson Samplingに対する頻繁な後悔境界を導出するのに利用できることを示す。
論文参考訳（メタデータ） (2021-10-02T20:10:40Z)
A Unifying Theory of Thompson Sampling for Continuous Risk-Averse Bandits [91.3755431537592]
本稿では,多腕バンディット問題に対するリスク-逆トンプソンサンプリングアルゴリズムの解析を統一する。大規模偏差理論における収縮原理を用いることで、連続リスク汎関数に対する新しい濃度境界が証明される。リスク関数の幅広いクラスと「ニセ」関数が連続性条件を満たすことを示す。
論文参考訳（メタデータ） (2021-08-25T17:09:01Z)
Asymptotic Convergence of Thompson Sampling [0.0]
トンプソンサンプリングは、様々なオンライン学習タスクにおいて効果的なポリシーであることが示されている。我々は、準線形ベイズ的後悔を仮定して、トンプソンサンプリングの収束結果を証明した。この結果はトンプソンサンプリングに固有のマーチンゲール構造に依存している。
論文参考訳（メタデータ） (2020-11-08T07:36:49Z)
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)

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