論文の概要: A Broader View of Thompson Sampling

• arxiv url: http://arxiv.org/abs/2510.07208v1
• Date: Wed, 08 Oct 2025 16:43:02 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-09 16:41:20.635982
• Title: A Broader View of Thompson Sampling
• Title（参考訳）: トンプソンサンプリングの広帯域化
• Authors: Yanlin Qu, Hongseok Namkoong, Assaf Zeevi,
• Abstract要約: トンプソンサンプリングは、最も広く使われ研究されているバンディットアルゴリズムの1つである。 トンプソンサンプリングが「適切に」探究と搾取のバランスをとることができる正確なメカニズムは謎である。 本稿では,トンプソンサンプリングをオンライン最適化アルゴリズムとして再放送する。
• 参考スコア（独自算出の注目度）: 13.204555981031966
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Thompson Sampling is one of the most widely used and studied bandit algorithms, known for its simple structure, low regret performance, and solid theoretical guarantees. Yet, in stark contrast to most other families of bandit algorithms, the exact mechanism through which posterior sampling (as introduced by Thompson) is able to "properly" balance exploration and exploitation, remains a mystery. In this paper we show that the core insight to address this question stems from recasting Thompson Sampling as an online optimization algorithm. To distill this, a key conceptual tool is introduced, which we refer to as "faithful" stationarization of the regret formulation. Essentially, the finite horizon dynamic optimization problem is converted into a stationary counterpart which "closely resembles" the original objective (in contrast, the classical infinite horizon discounted formulation, that leads to the Gittins index, alters the problem and objective in too significant a manner). The newly crafted time invariant objective can be studied using Bellman's principle which leads to a time invariant optimal policy. When viewed through this lens, Thompson Sampling admits a simple online optimization form that mimics the structure of the Bellman-optimal policy, and where greediness is regularized by a measure of residual uncertainty based on point-biserial correlation. This answers the question of how Thompson Sampling balances exploration-exploitation, and moreover, provides a principled framework to study and further improve Thompson's original idea.
• Abstract（参考訳）: トンプソンサンプリングは最も広く使われ、研究されているバンディットアルゴリズムの1つであり、単純な構造、低い後悔性能、堅固な理論的保証で知られている。 しかし、他の多くのバンディットアルゴリズムとは対照的に、後続サンプリング(トンプソンが導入した)が「適切な」均衡探索と搾取が可能な正確なメカニズムは謎のままである。 本稿では,Thompson Samplingをオンライン最適化アルゴリズムとして再キャストすることに由来する。 これを蒸留するために重要な概念ツールを導入し、これを後悔の定式化の「忠実な」固定化と呼ぶ。 本質的には、有限地平線動的最適化問題は、元の目的(対照的に、古典的な無限地平線割引の定式化は、ギッティンス指数に結びつき、問題と目的をあまりに重要な方法で変更する)を「ほぼ類似」する定常的問題に変換される。 新たに作成された時間不変の目的は、時間不変の最適ポリシーにつながるベルマンの原理を用いて研究することができる。 このレンズを通して見るとき、トンプソン・サンプリングは、ベルマン・最適ポリシーの構造を模倣する単純なオンライン最適化形式を認め、点-双対相関に基づく不確かさの尺度によって欲求性が正則化される。 これはトンプソンサンプリングがどのように探索-探索のバランスをとるかという問題に答え、さらにトンプソンの元々の考えを研究・改善するための原則的な枠組みを提供する。

関連論文リスト

• Asymptotically Optimal Linear Best Feasible Arm Identification with Fixed Budget [55.938644481736446]
  本稿では,誤差確率の指数的減衰を保証し,最適な腕識別のための新しいアルゴリズムを提案する。 我々は,複雑性のレベルが異なる様々な問題インスタンスに対する包括的経験的評価を通じて,アルゴリズムの有効性を検証する。
  論文  参考訳（メタデータ） (2025-06-03T02:56:26Z)
• Thompson Sampling for High-Dimensional Sparse Linear Contextual Bandits [17.11922027966447]
  この研究は、高次元およびスパースな文脈的包帯におけるトンプソンサンプリングの理論的な保証を提供する。 より高速な計算のために、MCMCの代わりに未知のパラメータと変分推論をモデル化するために、スパイク・アンド・スラブを用いる。
  論文  参考訳（メタデータ） (2022-11-11T02:23:39Z)
• Langevin Monte Carlo for Contextual Bandits [72.00524614312002]
  Langevin Monte Carlo Thompson Sampling (LMC-TS) が提案されている。 提案アルゴリズムは,文脈的帯域幅の特別な場合において,最高のトンプソンサンプリングアルゴリズムと同じサブ線形残差を達成できることを示す。
  論文  参考訳（メタデータ） (2022-06-22T17:58:23Z)
• Diffusion Approximations for Thompson Sampling in the Small Gap Regime [6.508628820027702]
  我々は,小さなギャップ状態におけるトンプソンサンプリングのプロセスレベルダイナミクスについて検討した。 トンプソンサンプリングのプロセスレベルダイナミクスは、ある微分方程式や常微分方程式の解に弱収束することを示す。
  論文  参考訳（メタデータ） (2021-05-19T16:28:01Z)
• Doubly-Adaptive Thompson Sampling for Multi-Armed and Contextual Bandits [28.504921333436833]
  本稿では,トンプソンサンプリングに基づくアルゴリズムの変種について,両腕の真の平均報酬に対する2倍頑健な推定器の項を適応的に再検討する。 提案アルゴリズムは, 半合成実験における最適(最小)後悔率とその経験的評価に適合する。 このアプローチは、適応データ収集とは別に、より多くのバイアス源が存在するコンテキスト的包帯に拡張する。
  論文  参考訳（メタデータ） (2021-02-25T22:29:25Z)
• Analysis and Design of Thompson Sampling for Stochastic Partial Monitoring [91.22679787578438]
  部分モニタリングのためのトンプソンサンプリングに基づく新しいアルゴリズムを提案する。 局所可観測性を持つ問題の線形化変種に対して,新たなアルゴリズムが対数問題依存の擬似回帰$mathrmO(log T)$を達成することを証明した。
  論文  参考訳（メタデータ） (2020-06-17T05:48:33Z)
• Latent Bandits Revisited [55.88616813182679]
  潜伏盗賊問題は、学習エージェントが未知の離散潜伏状態に条件付けられた腕の報酬分布を知知する問題である。 本稿では, 上位信頼境界(UCB)とトンプソンサンプリング(Thompson sample)の両方に基づいて, この設定のための一般的なアルゴリズムを提案する。 我々はアルゴリズムの統一的な理論的解析を行い、遅延状態の数がアクションよりも小さい場合、古典的なバンディットポリシーよりも後悔度が低い。
  論文  参考訳（メタデータ） (2020-06-15T19:24:02Z)
• 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)

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

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