論文の概要: Langevin Monte Carlo for Contextual Bandits

• arxiv url: http://arxiv.org/abs/2206.11254v1
• Date: Wed, 22 Jun 2022 17:58:23 GMT
• ステータス: 処理完了
• システム内更新日: 2022-06-23 14:54:52.192938
• Title: Langevin Monte Carlo for Contextual Bandits
• Title（参考訳）: コンテキストバンドのためのLangevin Monte Carlo
• Authors: Pan Xu, Hongkai Zheng, Eric Mazumdar, Kamyar Azizzadenesheli, Anima Anandkumar
• Abstract要約: Langevin Monte Carlo Thompson Sampling (LMC-TS) が提案されている。 提案アルゴリズムは,文脈的帯域幅の特別な場合において,最高のトンプソンサンプリングアルゴリズムと同じサブ線形残差を達成できることを示す。
• 参考スコア（独自算出の注目度）: 72.00524614312002
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the efficiency of Thompson sampling for contextual bandits. Existing Thompson sampling-based algorithms need to construct a Laplace approximation (i.e., a Gaussian distribution) of the posterior distribution, which is inefficient to sample in high dimensional applications for general covariance matrices. Moreover, the Gaussian approximation may not be a good surrogate for the posterior distribution for general reward generating functions. We propose an efficient posterior sampling algorithm, viz., Langevin Monte Carlo Thompson Sampling (LMC-TS), that uses Markov Chain Monte Carlo (MCMC) methods to directly sample from the posterior distribution in contextual bandits. Our method is computationally efficient since it only needs to perform noisy gradient descent updates without constructing the Laplace approximation of the posterior distribution. We prove that the proposed algorithm achieves the same sublinear regret bound as the best Thompson sampling algorithms for a special case of contextual bandits, viz., linear contextual bandits. We conduct experiments on both synthetic data and real-world datasets on different contextual bandit models, which demonstrates that directly sampling from the posterior is both computationally efficient and competitive in performance.
• Abstract（参考訳）: 文脈的包帯に対するトンプソンサンプリングの効率性について検討する。 既存のトンプソンサンプリングに基づくアルゴリズムは、後方分布のラプラス近似(すなわちガウス分布)を構築する必要があり、これは一般共分散行列に対する高次元応用では標本化に非効率である。 さらに、ガウス近似は一般報酬生成関数の後方分布に対する良いサロゲートではないかもしれない。 我々は,マルコフ・チェイン・モンテ・カルロ法(MCMC)を用いて,文脈的包帯における後部分布から直接サンプリングする,効率的な後部サンプリングアルゴリズムであるLangevin Monte Carlo Thompson Sampling (LMC-TS)を提案する。 本手法は,後方分布のラプラス近似を構築することなく,ノイズ勾配降下更新のみを行うため,計算効率が高い。 提案手法は,コンテキストバンディット,viz.,リニアコンテクストバンディットの特別な場合において,最高のトンプソンサンプリングアルゴリズムと同等のサブリニア後悔値が得られることを証明した。 我々は,異なる文脈のバンディットモデル上で合成データと実世界のデータセットの両方について実験を行い,後方からの直接サンプリングが計算効率と性能の両立を実証した。

関連論文リスト

• Online Posterior Sampling with a Diffusion Prior [20.24212000441531]
  ガウス事前の文脈的包帯における後方サンプリングは、ラプラス近似を用いて正確にあるいはほぼ実施することができる。 そこで本研究では,拡散モデルを用いた文脈帯域に対する近似的な後方サンプリングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-10-04T20:47:16Z)
• Distributed Markov Chain Monte Carlo Sampling based on the Alternating Direction Method of Multipliers [143.6249073384419]
  本論文では,乗算器の交互方向法に基づく分散サンプリング手法を提案する。 我々は,アルゴリズムの収束に関する理論的保証と,その最先端性に関する実験的証拠の両方を提供する。 シミュレーションでは,線形回帰タスクとロジスティック回帰タスクにアルゴリズムを配置し,その高速収束を既存の勾配法と比較した。
  論文  参考訳（メタデータ） (2024-01-29T02:08:40Z)
• 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)
• Thompson Sampling for High-Dimensional Sparse Linear Contextual Bandits [17.11922027966447]
  この研究は、高次元およびスパースな文脈的包帯におけるトンプソンサンプリングの理論的な保証を提供する。 より高速な計算のために、MCMCの代わりに未知のパラメータと変分推論をモデル化するために、スパイク・アンド・スラブを用いる。
  論文  参考訳（メタデータ） (2022-11-11T02:23:39Z)
• Thompson Sampling for Unimodal Bandits [21.514495320038712]
  本稿では, 半順序の腕に対して期待される報酬が一様であるアンフンモダル・バンディットに対するトンプソンサンプリングアルゴリズムを提案する。 ガウスの報酬に対して、我々のアルゴリズムの後悔は$mathcalO(log T)$であり、標準的なトンプソンサンプリングアルゴリズムよりもはるかに優れている。
  論文  参考訳（メタデータ） (2021-06-15T14:40:34Z)
• Plug-And-Play Learned Gaussian-mixture Approximate Message Passing [71.74028918819046]
  そこで本研究では,従来のi.i.d.ソースに適した圧縮圧縮センシング(CS)リカバリアルゴリズムを提案する。 我々のアルゴリズムは、Borgerdingの学習AMP(LAMP)に基づいて構築されるが、アルゴリズムに普遍的な復調関数を採用することにより、それを大幅に改善する。 数値評価により,L-GM-AMPアルゴリズムは事前の知識を必要とせず,最先端の性能を実現する。
  論文  参考訳（メタデータ） (2020-11-18T16:40:45Z)
• 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)

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

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