論文の概要: Thompson sampling: Precise arm-pull dynamics and adaptive inference

• arxiv url: http://arxiv.org/abs/2601.21131v1
• Date: Thu, 29 Jan 2026 00:12:04 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-30 16:22:49.4845
• Title: Thompson sampling: Precise arm-pull dynamics and adaptive inference
• Title（参考訳）: トンプソンサンプリング:精密アームプルダイナミクスと適応推論
• Authors: Qiyang Han,
• Abstract要約: 我々は、トンプソン型アルゴリズムの別の標準クラスにおける正確なアームプルダイナミクスについて研究する。 アームパール数が決定論的であることと、アームが最適以下であるか、あるいは一意の最適アームである場合に限り、アームパール数は決定論的であることを示す。 正常化された腕は、安定な腕の制限と不安定な腕の半普遍的非ガウス的制限により、同じ二分法に従うことを意味する。
• 参考スコア（独自算出の注目度）: 0.7614628596146601
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Adaptive sampling schemes are well known to create complex dependence that may invalidate conventional inference methods. A recent line of work shows that this need not be the case for UCB-type algorithms in multi-armed bandits. A central emerging theme is a `stability' property with asymptotically deterministic arm-pull counts in these algorithms, making inference as easy as in the i.i.d. setting. In this paper, we study the precise arm-pull dynamics in another canonical class of Thompson-sampling type algorithms. We show that the phenomenology is qualitatively different: the arm-pull count is asymptotically deterministic if and only if the arm is suboptimal or is the unique optimal arm; otherwise it converges in distribution to the unique invariant law of an SDE. This dichotomy uncovers a unifying principle behind many existing (in)stability results: an arm is stable if and only if its interaction with statistical noise is asymptotically negligible. As an application, we show that normalized arm means obey the same dichotomy, with Gaussian limits for stable arms and a semi-universal, non-Gaussian limit for unstable arms. This not only enables the construction of confidence intervals for the unknown mean rewards despite non-normality, but also reveals the potential of developing tractable inference procedures beyond the stable regime. The proofs rely on two new approaches. For suboptimal arms, we develop an `inverse process' approach that characterizes the inverse of the arm-pull count process via a Stieltjes integral. For optimal arms, we adopt a reparametrization of the arm-pull and noise processes that reduces the singularity in the natural SDE to proving the uniqueness of the invariant law of another SDE. We prove the latter by a set of analytic tools, including the parabolic Hörmander condition and the Stroock-Varadhan support theorem.
• Abstract（参考訳）: 適応サンプリングスキームは、従来の推論手法を無効にするような複雑な依存を生み出すことがよく知られている。 最近の研究は、多腕バンディットにおける UCB 型アルゴリズムは必要ないことを示している。 中心的な新興テーマは、これらのアルゴリズムにおいて漸近的に決定的なアームプル数を持つ「安定」プロパティであり、推論はi.d.設定と同様に容易である。 本稿では、トンプソンサンプリング型アルゴリズムの別の標準クラスにおける正確なアームプルダイナミクスについて検討する。 アーム・プル数が漸近的に決定論的であることと、アームが最適以下であるか、あるいは一意の最適アームである場合に限り、SDEのユニークな不変法則に収束することである。 この二分法は、多くの既存の(不安定な)結果の背後にある統一的な原理を明らかにする: 腕が安定であることと、統計ノイズとの相互作用が漸近的に無視可能であること。 応用として、正規化された腕は、安定な腕に対するガウス的限界と不安定な腕に対する半ユニバーサル的非ガウス的限界とで、同じ二分法に従うことを示す。 このことは、非正規性にもかかわらず未知の平均報酬に対する信頼区間の構築を可能にするだけでなく、安定な状態を超えて、引き込み可能な推論手順を開発する可能性も示している。 証明は2つの新しいアプローチに依存している。 準最適アームに対しては、スティルチェス積分によるアームプルカウント過程の逆過程を特徴付ける「逆過程」アプローチを開発する。 最適なアームに対しては、自然SDEの特異点を減少させ、他のSDEの不変法則の特異性を証明するために、アームプルとノイズプロセスの再パラメータ化を採用する。 後者を、放物的ヘルマンダー条件やストロック・バラダン支持定理を含む解析ツールの集合で証明する。

関連論文リスト

• Best-Arm Identification in Unimodal Bandits [24.001611176749158]
  本研究では, 固定信頼度ベストアーム識別問題について検討する。 我々は任意の境界の停止時間で2つ下げる。 腕の数に対する線形依存は、信頼性に依存しないコストでは避けられないことを示す。
  論文  参考訳（メタデータ） (2024-11-04T09:05:11Z)
• Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
  我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。 特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
  論文  参考訳（メタデータ） (2023-12-19T13:17:43Z)
• Mean-based Best Arm Identification in Stochastic Bandits under Reward Contamination [80.53485617514707]
  本稿では,ギャップベースアルゴリズムと逐次除去に基づく2つのアルゴリズムを提案する。 具体的には、ギャップベースのアルゴリズムでは、サンプルの複雑さは定数要素まで最適であり、連続的な除去では対数因子まで最適である。
  論文  参考訳（メタデータ） (2021-11-14T21:49:58Z)
• The Countable-armed Bandit with Vanishing Arms [8.099977107670918]
  我々は、数え切れないほど多くの腕を有限個の「型」に分割したバンドイット問題を考える。 非定常分布は、腕の個体群における各腕型の相対的な存在量を支配しており、いわゆる「腕貯水池」である。
  論文  参考訳（メタデータ） (2021-10-23T02:47:55Z)
• A Unifying Theory of Thompson Sampling for Continuous Risk-Averse Bandits [91.3755431537592]
  本稿では,多腕バンディット問題に対するリスク-逆トンプソンサンプリングアルゴリズムの解析を統一する。 大規模偏差理論における収縮原理を用いることで、連続リスク汎関数に対する新しい濃度境界が証明される。 リスク関数の幅広いクラスと「ニセ」関数が連続性条件を満たすことを示す。
  論文  参考訳（メタデータ） (2021-08-25T17:09:01Z)
• Optimal Best-arm Identification in Linear Bandits [79.3239137440876]
  サンプルの複雑さが既知のインスタンス固有の下界と一致する単純なアルゴリズムを考案する。 既存のベストアーム識別戦略とは異なり、我々のアルゴリズムは武器の数に依存しない停止規則を用いる。
  論文  参考訳（メタデータ） (2020-06-29T14:25:51Z)
• Robustness Guarantees for Mode Estimation with an Application to Bandits [131.21717367564963]
  平均ではなく報酬分布のモードを値とするマルチアームバンディットの理論を導入する。 我々は,我々のアルゴリズムが逆雑音列による腕の摂動に頑健であることを示すシミュレーションで示す。
  論文  参考訳（メタデータ） (2020-03-05T21:29:27Z)

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

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