論文の概要: Thompson Sampling for High-Dimensional Sparse Linear Contextual Bandits
- arxiv url: http://arxiv.org/abs/2211.05964v1
- Date: Fri, 11 Nov 2022 02:23:39 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-14 16:06:52.370677
- Title: Thompson Sampling for High-Dimensional Sparse Linear Contextual Bandits
- Title(参考訳): 高次元スパース線形コンテキストバンディットのためのトンプソンサンプリング
- Authors: Sunrit Chakraborty, Saptarshi Roy, Ambuj Tewari
- Abstract要約: この研究は、高次元およびスパースな文脈的包帯におけるトンプソンサンプリングの理論的な保証を提供する。
より高速な計算のために、MCMCの代わりに未知のパラメータと変分推論をモデル化するために、スパイク・アンド・スラブを用いる。
- 参考スコア(独自算出の注目度): 17.11922027966447
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider the stochastic linear contextual bandit problem with
high-dimensional features. We analyze the Thompson sampling (TS) algorithm,
using special classes of sparsity-inducing priors (e.g. spike-and-slab) to
model the unknown parameter, and provide a nearly optimal upper bound on the
expected cumulative regret. To the best of our knowledge, this is the first
work that provides theoretical guarantees of Thompson sampling in high
dimensional and sparse contextual bandits. For faster computation, we use
spike-and-slab prior to model the unknown parameter and variational inference
instead of MCMC to approximate the posterior distribution. Extensive
simulations demonstrate improved performance of our proposed algorithm over
existing ones.
- Abstract(参考訳): 高次元特徴を持つ確率線形文脈バンディット問題を考える。
トンプソンサンプリング(ts)アルゴリズムを,未知のパラメータをモデル化するために,スパーシティ誘導前兆(スパイク・アンド・スラブなど)の特殊クラスを用いて解析し,推定累積後悔の上限をほぼ最適に設定した。
我々の知る限りでは、これはトンプソンサンプリングの高次元およびスパースな文脈的包帯における理論的保証を提供する最初の作品である。
計算の高速化のために,MCMCの代わりに未知パラメータと変分推論をモデル化するためにスパイク・アンド・スラブを用いる。
シミュレーションにより,提案アルゴリズムの性能が既存アルゴリズムよりも向上したことを示す。
関連論文リスト
- Approximate Thompson Sampling for Learning Linear Quadratic Regulators with $O(\sqrt{T})$ Regret [10.541541376305243]
本稿では,線形二次レギュレータ(LQR)を改良したベイズ的残差値$O(sqrtT)$で学習する近似トンプソンサンプリングアルゴリズムを提案する。
励振信号は、プレコンディショナーの最小固有値を時間とともに増加させ、近似した後方サンプリングプロセスを加速させることを示す。
論文 参考訳(メタデータ) (2024-05-29T03:24:56Z) - VITS : Variational Inference Thompson Sampling for contextual bandits [10.028119153832346]
我々は、文脈的帯域幅に対するトンプソンサンプリング(TS)アルゴリズムの変種を導入・解析する。
ガウス変分推論に基づく新しいアルゴリズムであるValational Inference Thompson sample VITSを提案する。
我々は,VITS が線形文脈帯域に対して従来の TS の次元とラウンド数で同じ順序のサブ線形後悔境界を達成することを示す。
論文 参考訳(メタデータ) (2023-07-19T17:53:22Z) - Provable and Practical: Efficient Exploration in Reinforcement Learning via Langevin Monte Carlo [104.9535542833054]
我々は、強化学習のためのトンプソンサンプリングに基づくスケーラブルで効果的な探索戦略を提案する。
代わりに、Langevin Monte Carlo を用いて、Q 関数をその後部分布から直接サンプリングする。
提案手法は,Atari57スイートからのいくつかの挑戦的な探索課題において,最先端の深部RLアルゴリズムと比較して,より優れた,あるいは類似した結果が得られる。
論文 参考訳(メタデータ) (2023-05-29T17:11:28Z) - A Provably Efficient Model-Free Posterior Sampling Method for Episodic
Reinforcement Learning [50.910152564914405]
強化学習のための既存の後方サンプリング手法は、モデルベースであるか、線形MDPを超える最悪の理論的保証がないかによって制限される。
本稿では,理論的保証を伴うより一般的な補足的強化学習問題に適用可能な,後部サンプリングのモデルフリーな新しい定式化を提案する。
論文 参考訳(メタデータ) (2022-08-23T12:21:01Z) - Langevin Monte Carlo for Contextual Bandits [72.00524614312002]
Langevin Monte Carlo Thompson Sampling (LMC-TS) が提案されている。
提案アルゴリズムは,文脈的帯域幅の特別な場合において,最高のトンプソンサンプリングアルゴリズムと同じサブ線形残差を達成できることを示す。
論文 参考訳(メタデータ) (2022-06-22T17:58:23Z) - Analysis and Design of Thompson Sampling for Stochastic Partial
Monitoring [91.22679787578438]
部分モニタリングのためのトンプソンサンプリングに基づく新しいアルゴリズムを提案する。
局所可観測性を持つ問題の線形化変種に対して,新たなアルゴリズムが対数問題依存の擬似回帰$mathrmO(log T)$を達成することを証明した。
論文 参考訳(メタデータ) (2020-06-17T05:48:33Z) - On Thompson Sampling with Langevin Algorithms [106.78254564840844]
多武装バンディット問題に対するトンプソンサンプリングは理論と実践の両方において良好な性能を享受する。
計算上のかなりの制限に悩まされており、反復ごとに後続分布からのサンプルを必要とする。
本稿では,この問題に対処するために,トンプソンサンプリングに適した2つのマルコフ連鎖モンテカルロ法を提案する。
論文 参考訳(メタデータ) (2020-02-23T22:35:29Z) - Thompson Sampling Algorithms for Mean-Variance Bandits [97.43678751629189]
我々は平均分散MABのためのトンプソンサンプリング型アルゴリズムを開発した。
我々はまた、ガウシアンとベルヌーイの盗賊に対する包括的後悔の分析も提供する。
我々のアルゴリズムは、全てのリスク許容度に対して既存のLCBベースのアルゴリズムを著しく上回っている。
論文 参考訳(メタデータ) (2020-02-01T15:33:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。