論文の概要: Rethinking Langevin Thompson Sampling from A Stochastic Approximation Perspective
- arxiv url: http://arxiv.org/abs/2510.05023v1
- Date: Mon, 06 Oct 2025 17:01:29 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-10-07 16:52:59.999796
- Title: Rethinking Langevin Thompson Sampling from A Stochastic Approximation Perspective
- Title（参考訳）: 確率近似の観点からのランゲヴィン・トンプソンサンプリングの再考
- Authors: Weixin Wang, Haoyang Zheng, Guang Lin, Wei Deng, Pan Xu,
- Abstract要約: 本稿では、トンプソンサンプリング(TS)フレームワークに近似(SA)を組み込んだTS-SAを紹介する。
各ラウンドにおいて、TS-SAは直近の報酬のみを用いて後部近似を構築し、時間とともにノイズの多い提案にSAステップを適用する。
これは、アルゴリズム全体を通して静止後ターゲットを近似するものとして解釈できる。
- 参考スコア（独自算出の注目度）: 17.53150194998013
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Most existing approximate Thompson Sampling (TS) algorithms for multi-armed bandits use Stochastic Gradient Langevin Dynamics (SGLD) or its variants in each round to sample from the posterior, relaxing the need for conjugacy assumptions between priors and reward distributions in vanilla TS. However, they often require approximating a different posterior distribution in different round of the bandit problem. This requires tricky, round-specific tuning of hyperparameters such as dynamic learning rates, causing challenges in both theoretical analysis and practical implementation. To alleviate this non-stationarity, we introduce TS-SA, which incorporates stochastic approximation (SA) within the TS framework. In each round, TS-SA constructs a posterior approximation only using the most recent reward(s), performs a Langevin Monte Carlo (LMC) update, and applies an SA step to average noisy proposals over time. This can be interpreted as approximating a stationary posterior target throughout the entire algorithm, which further yields a fixed step-size, a unified convergence analysis framework, and improved posterior estimates through temporal averaging. We establish near-optimal regret bounds for TS-SA, with a simplified and more intuitive theoretical analysis enabled by interpreting the entire algorithm as a simulation of a stationary SGLD process. Our empirical results demonstrate that even a single-step Langevin update with certain warm-up outperforms existing methods substantially on bandit tasks.
- Abstract（参考訳）: 既存の近似トンプソンサンプリング(TS)アルゴリズムは、SGLD(Stochastic Gradient Langevin Dynamics)またはその変種を用いて、後方からサンプルを採取し、バニラTSの事前分布と報酬分布の間の共役仮定の必要性を緩和する。
しかし、それらはしばしば、バンドイット問題の異なるラウンドで異なる後部分布を近似する必要がある。
これは、動的学習率などのハイパーパラメータのトリッキーでラウンド特異的なチューニングを必要とし、理論解析と実践的な実装の両方において困難を引き起こす。
この非定常性を軽減するため、TSフレームワークに確率近似(SA)を組み込んだTS-SAを導入する。
各ラウンドでTS-SAは、最新の報酬のみを使用して後部近似を構築し、Langevin Monte Carlo (LMC) 更新を実行し、時間とともにノイズの多い提案にSAステップを適用する。
これは、アルゴリズム全体を通して定常的な後方目標を近似したものと解釈でき、これはさらに、固定ステップサイズ、統合収束分析フレームワーク、時間平均化による後方推定の改善をもたらす。
SGLDプロセスのシミュレーションとしてアルゴリズム全体を解釈することにより、TS-SAのほぼ最適後悔境界を確立し、よりシンプルで直感的な理論的解析を可能にした。
実験結果から, あるウォームアップを伴う単一ステップのLangevin更新でも, バンドイットタスクにおいて, 既存の手法を著しく上回る結果が得られた。
関連論文リスト
- SACn: Soft Actor-Critic with n-step Returns [3.305353787222645]
SAC(Soft Actor-Critic)は、オンラインのオンラインモデルフリー強化学習(RL)手法の1つである。
SACは、通常の組み合わせが非政治アルゴリズムにバイアスをもたらすため、nステップのリターンと組み合わせることが難しいことが知られている。
本研究では,SACとnステップの戻り値を組み合わせ,この問題を克服する。
論文 参考訳（メタデータ） (2025-12-15T10:23:13Z) - Inference-Time Scaling of Diffusion Language Models with Particle Gibbs Sampling [70.8832906871441]
我々は、モデルを再訓練することなく、所望の報酬に向けて世代を操る方法を研究する。
従来の手法では、通常は1つの認知軌道内でサンプリングやフィルタを行い、軌道レベルの改善なしに報酬をステップバイステップで最適化する。
本稿では,拡散言語モデル(PG-DLM)の粒子ギブスサンプリングについて紹介する。
論文 参考訳（メタデータ） (2025-07-11T08:00:47Z) - Faster Sampling via Stochastic Gradient Proximal Sampler [28.422547264326468]
非log-concave分布からのサンプリングのための近位サンプリング器 (SPS) について検討した。
対象分布への収束性は,アルゴリズムの軌道が有界である限り保証可能であることを示す。
我々は、Langevin dynamics(SGLD)とLangevin-MALAの2つの実装可能な変種を提供し、SPS-SGLDとSPS-MALAを生み出した。
論文 参考訳（メタデータ） (2024-05-27T00:53:18Z) - 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) - The Choice of Noninformative Priors for Thompson Sampling in
Multiparameter Bandit Models [56.31310344616837]
トンプソンサンプリング(TS)は、様々な報酬モデルにまたがる理論的な保証によって支持される卓越した経験的性能で知られている。
本研究では,理論的理解の欠如のある新しいモデルを扱う際に,非形式的事前選択がTSの性能に与える影響について考察する。
論文 参考訳（メタデータ） (2023-02-28T08:42:42Z) - Langevin Monte Carlo for Contextual Bandits [72.00524614312002]
Langevin Monte Carlo Thompson Sampling (LMC-TS) が提案されている。
提案アルゴリズムは,文脈的帯域幅の特別な場合において,最高のトンプソンサンプリングアルゴリズムと同じサブ線形残差を達成できることを示す。
論文 参考訳（メタデータ） (2022-06-22T17:58:23Z) - Utilising the CLT Structure in Stochastic Gradient based Sampling :
Improved Analysis and Faster Algorithms [14.174806471635403]
粒子ダイナミック(IPD)に対するグラディエント・ランゲヴィン・ダイナミクス(SGLD)やランダムバッチ法(RBM)などのサンプリングアルゴリズムの近似を考察する。
近似によって生じる雑音は中央極限定理(CLT)によりほぼガウス的であるが、ブラウン運動はまさにガウス的である。
この構造を利用して拡散過程内の近似誤差を吸収し、これらのアルゴリズムの収束保証を改善する。
論文 参考訳（メタデータ） (2022-06-08T10:17:40Z) - Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and
Beyond [63.59034509960994]
シャッフルに基づく変種(ミニバッチと局所ランダムリシャッフル)について検討する。
ポリアック・ロジャシエヴィチ条件を満たす滑らかな函数に対して、これらのシャッフル型不変量(英語版)(shuffling-based variants)がそれらの置換式よりも早く収束することを示す収束境界を得る。
我々は, 同期シャッフル法と呼ばれるアルゴリズムの修正を提案し, ほぼ均一な条件下では, 下界よりも収束速度が速くなった。
論文 参考訳（メタデータ） (2021-10-20T02:25:25Z) - On the Convergence of Stochastic Extragradient for Bilinear Games with
Restarted Iteration Averaging [96.13485146617322]
本稿では, ステップサイズが一定であるSEG法の解析を行い, 良好な収束をもたらす手法のバリエーションを示す。
平均化で拡張した場合、SEGはナッシュ平衡に確実に収束し、スケジュールされた再起動手順を組み込むことで、その速度が確実に加速されることを証明した。
論文 参考訳（メタデータ） (2021-06-30T17:51:36Z) - Diffusion Approximations for Thompson Sampling in the Small Gap Regime [6.508628820027702]
我々は,小さなギャップ状態におけるトンプソンサンプリングのプロセスレベルダイナミクスについて検討した。
トンプソンサンプリングのプロセスレベルダイナミクスは、ある微分方程式や常微分方程式の解に弱収束することを示す。
論文 参考訳（メタデータ） (2021-05-19T16:28:01Z) - Analysis and Design of Thompson Sampling for Stochastic Partial
Monitoring [91.22679787578438]
部分モニタリングのためのトンプソンサンプリングに基づく新しいアルゴリズムを提案する。
局所可観測性を持つ問題の線形化変種に対して,新たなアルゴリズムが対数問題依存の擬似回帰$mathrmO(log T)$を達成することを証明した。
論文 参考訳（メタデータ） (2020-06-17T05:48:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。