論文の概要: Finite-Time Regret of Thompson Sampling Algorithms for Exponential
Family Multi-Armed Bandits
- arxiv url: http://arxiv.org/abs/2206.03520v1
- Date: Tue, 7 Jun 2022 18:08:21 GMT
- ステータス: 処理完了
- システム内更新日: 2022-06-09 13:22:10.932814
- Title: Finite-Time Regret of Thompson Sampling Algorithms for Exponential
Family Multi-Armed Bandits
- Title（参考訳）: 指数関数系多腕バンディットに対するトンプソンサンプリングアルゴリズムの有限時間後悔
- Authors: Tianyuan Jin, Pan Xu, Xiaokui Xiao, Anima Anandkumar
- Abstract要約: 本研究では,指数関数族バンドイットに対するトンプソンサンプリング (TS) アルゴリズムの遺残について検討する。
最適な腕の過小評価を避けるために,新しいサンプリング分布を用いたトンプソンサンプリング(Expulli)を提案する。
- 参考スコア（独自算出の注目度）: 88.21288104408556
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the regret of Thompson sampling (TS) algorithms for exponential
family bandits, where the reward distribution is from a one-dimensional
exponential family, which covers many common reward distributions including
Bernoulli, Gaussian, Gamma, Exponential, etc. We propose a Thompson sampling
algorithm, termed ExpTS, which uses a novel sampling distribution to avoid the
under-estimation of the optimal arm. We provide a tight regret analysis for
ExpTS, which simultaneously yields both the finite-time regret bound as well as
the asymptotic regret bound. In particular, for a $K$-armed bandit with
exponential family rewards, ExpTS over a horizon $T$ is sub-UCB (a strong
criterion for the finite-time regret that is problem-dependent), minimax
optimal up to a factor $\sqrt{\log K}$, and asymptotically optimal, for
exponential family rewards. Moreover, we propose ExpTS$^+$, by adding a greedy
exploitation step in addition to the sampling distribution used in ExpTS, to
avoid the over-estimation of sub-optimal arms. ExpTS$^+$ is an anytime bandit
algorithm and achieves the minimax optimality and asymptotic optimality
simultaneously for exponential family reward distributions. Our proof
techniques are general and conceptually simple and can be easily applied to
analyze standard Thompson sampling with specific reward distributions.
- Abstract（参考訳）: 本研究では,指数関数群に対するトンプソンサンプリング (TS) アルゴリズムの遺残について検討する。報奨分布は,ベルヌーイ,ガウス,ガンマ,指数など,多くの共通報酬分布をカバーする一次元指数関数族から得られるものである。
本研究では, 最適なアームの過大評価を避けるために, 新しいサンプリング分布を用いたトンプソンサンプリングアルゴリズムexptsを提案する。
我々はExpTSに対して厳密な後悔解析を行い、同時に有限時間後悔境界と漸近後悔境界の両方をもたらす。
特に、指数関数的な家族報酬を持つ$K$武装バンディットの場合、地平線上のExpTSはサブUCB(問題に依存しない有限時間後悔の強い基準)であり、最小限の最大値は$\sqrt{\log K}$であり、指数関数的な家族報酬に対して漸近的に最適である。
さらに,expts$^+$ を,expts のサンプリング分布に加えて欲張りなエクスプロイトステップを追加して,準最適アームの過剰推定を回避することを提案する。
ExpTS$^+$は任意の帯域幅アルゴリズムであり、指数関数的な家族報酬分布に対して極小最適化と漸近最適化を同時に達成する。
提案手法は一般的かつ概念的にシンプルであり,特定の報酬分布を持つ標準トンプソンサンプリングの解析に容易に適用できる。
関連論文リスト
- Finite-Time Frequentist Regret Bounds of Multi-Agent Thompson Sampling
on Sparse Hypergraphs [11.024467775280193]
マルチエージェントマルチアーム・バンドイット(MAMAB)問題について検討し,$m$エージェントを$rho$オーバーラップするグループに分解する。
そこで本稿では,MATS の効率的な変種として$epsilon$-exploring Multi-Agent Thompson Sampling (epsilon$-MATS) アルゴリズムを提案する。
我々は、$epsilon$-MATSが、時間地平線と局所アームサイズの両方においてサブ線形である最悪の頻繁な後悔境界を達成することを証明した。
論文 参考訳（メタデータ） (2023-12-24T21:41:01Z) - Thompson Exploration with Best Challenger Rule in Best Arm
Identification [66.33448474838342]
本稿では,バンドイットフレームワークにおける固定信頼度最良腕識別問題について検討する。
我々は、トンプソンサンプリングと、ベストチャレンジャールールとして知られる計算効率の良いアプローチを組み合わせた新しいポリシーを提案する。
論文 参考訳（メタデータ） (2023-10-01T01:37:02Z) - A General Recipe for the Analysis of Randomized Multi-Armed Bandit Algorithms [14.33758865948252]
我々は2つの有名なバンディットアルゴリズム、Minimum Empirical Divergence (MED)とThompson Sampling (TS)を再検討する。
MEDがこれらのモデルすべてに最適であることを示すとともに、最適性がすでに知られているTSアルゴリズムの簡単な後悔解析も提供する。
論文 参考訳（メタデータ） (2023-03-10T16:43:48Z) - Langevin Monte Carlo for Contextual Bandits [72.00524614312002]
Langevin Monte Carlo Thompson Sampling (LMC-TS) が提案されている。
提案アルゴリズムは,文脈的帯域幅の特別な場合において,最高のトンプソンサンプリングアルゴリズムと同じサブ線形残差を達成できることを示す。
論文 参考訳（メタデータ） (2022-06-22T17:58:23Z) - 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) - Thompson Sampling for Unimodal Bandits [21.514495320038712]
本稿では, 半順序の腕に対して期待される報酬が一様であるアンフンモダル・バンディットに対するトンプソンサンプリングアルゴリズムを提案する。
ガウスの報酬に対して、我々のアルゴリズムの後悔は$mathcalO(log T)$であり、標準的なトンプソンサンプリングアルゴリズムよりもはるかに優れている。
論文 参考訳（メタデータ） (2021-06-15T14:40:34Z) - MOTS: Minimax Optimal Thompson Sampling [89.2370817955411]
トンプソンサンプリングがミニマックス下限の$Omega(sqrtKT)$と$K$の武器付きバンディット問題に一致するかどうかという未解決の問題のままである。
我々は,各タイミングで選択した腕のサンプリングインスタンスを適応的にクリップするMOTSと呼ばれるトンプソンサンプリングの変種を提案する。
我々は、この単純なトンプソンサンプリングの変種が、有限時間地平線に対して$O(sqrtKT)$のミニマックス最適後悔境界と、$T$が無限に近づくときのガウス報酬に対する最適後悔境界を達成することを証明した。
論文 参考訳（メタデータ） (2020-03-03T21:24:39Z) - A General Theory of the Stochastic Linear Bandit and Its Applications [8.071506311915398]
本稿では,線形バンディット問題に対する一般解析フレームワークとアルゴリズム群を紹介する。
予測における最適化という新たな概念は、OFULの過剰探索問題を減少させるSieeved greedy(SG)と呼ばれる新しいアルゴリズムを生み出します。
SGが理論的に最適であることを示すことに加えて、実験シミュレーションにより、SGはgreedy、OFUL、TSといった既存のベンチマークよりも優れていることが示された。
論文 参考訳（メタデータ） (2020-02-12T18:54:41Z) - Thompson Sampling Algorithms for Mean-Variance Bandits [97.43678751629189]
我々は平均分散MABのためのトンプソンサンプリング型アルゴリズムを開発した。
我々はまた、ガウシアンとベルヌーイの盗賊に対する包括的後悔の分析も提供する。
我々のアルゴリズムは、全てのリスク許容度に対して既存のLCBベースのアルゴリズムを著しく上回っている。
論文 参考訳（メタデータ） (2020-02-01T15:33:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。