Fugu-MT 論文翻訳(概要): Thompson Sampling Is 2-Competitive for Mistakes

論文の概要: Thompson Sampling Is 2-Competitive for Mistakes

arxiv url: http://arxiv.org/abs/2607.12389v1
Date: Tue, 14 Jul 2026 06:02:18 GMT
ステータス: 翻訳完了
システム内更新日: 2026-07-15 17:08:30.048806
Title: Thompson Sampling Is 2-Competitive for Mistakes
Title（参考訳）: トンプソン・サンプリング、2倍の競争力を持つ-関係者
Abstract要約: ベイズ的バンディットモデルについて考察し、トンプソンサンプリングが他の政策として期待される2倍の誤り(準最適腕の選択)を犯すことを示す。我々の分析は、潜伏する腕のプロセスが独立している限り適用され、各腕は演奏時にのみ進化する。
参考スコア（独自算出の注目度）: 17.39167498520606
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We consider Bayesian bandit models and prove that Thompson sampling makes at most twice the expected number of mistakes (selections of a suboptimal arm) as any other policy. Our analysis applies as long as the latent arm processes are independent and each arm evolves only when played. For stochastic bandits with best arm defined via mean reward, this confirms a conjecture of Guha and Munagala from 2014, where the factor $2$ is already best possible. The result holds under any nonincreasing sequence of round weights, including fixed horizon and geometric discounting.
Abstract（参考訳）: ベイズ的バンディットモデルについて考察し、トンプソンサンプリングが他の政策として期待されるミス数(準最適腕の選択)を少なくとも2倍にすることを証明する。我々の分析は、潜伏する腕のプロセスが独立している限り適用され、各腕は演奏時にのみ進化する。平均報酬によって定義された最高の腕を持つ確率的盗賊にとって、これは2014年のGuhaとMunagalaの予想を裏付けるものである。その結果は、固定地平線や幾何割引を含む、任意の非増加的な丸みを帯びる。

関連論文リスト

Optimism Stabilizes Thompson Sampling for Adaptive Inference [9.558593674952654]
トンプソンサンプリング(TS)は多武装の包帯に広く用いられているが、適応データ収集における推論特性は微妙である。我々は、この現象を$K$武器のガウス・バンディットで研究し、エンホプティミズムをエンホスタビリティの回復の鍵となるメカニズムとして認識する。分散膨張型TS citephalder2025stableは、複数のアームが最適である難易度を含む、任意のK ge 2$に対して安定であることを示す。
論文参考訳（メタデータ） (2026-02-05T18:52:54Z)
Fixed-Confidence Best Arm Identification with Decreasing Variance [12.018304940341793]
腕の報酬の変動を時間的に減少させるマルチアームバンディットにおけるベストアーム識別の問題に焦点をあてる。学習者によるコストは、最適な腕を特定するのに必要な時間の重み付けされた和としてモデル化される。
論文参考訳（メタデータ） (2025-02-11T02:47:20Z)
Bridging Rested and Restless Bandits with Graph-Triggering: Rising and Rotting [67.1631453378926]
Graph-Triggered Banditsは、安静と安静のバンディットを一般化するフレームワークである。本研究は,2種類の単調包帯に焦点をあてる: 立ち上がり, 腕の期待される報酬が増加する, 引き金の数が増える, 回転する, 反対の行動が起こる。
論文参考訳（メタデータ） (2024-09-09T18:23:07Z)
A General Framework for Clustering and Distribution Matching with Bandit Feedback [81.50716021326194]
我々は,帯域幅フィードバックを用いたクラスタリングと分散マッチング問題のための一般的なフレームワークを開発する。誤り確率が$delta$を超えない任意のオンラインアルゴリズムに対して、平均アームプル数に基づいて漸近的でない下界を導出する。我々の洗練された分析により、アルゴリズムの平均的なアームプル数が、$delta$が消えるにつれて、基本的限界に収束する速度に縛られる新しい現象が明らかになった。
論文参考訳（メタデータ） (2024-09-08T12:19:12Z)
Thompson Exploration with Best Challenger Rule in Best Arm Identification [59.02170783023547]
本稿では,バンドイットフレームワークにおける固定信頼度最良腕識別問題について検討する。我々は、トンプソンサンプリングと、ベストチャレンジャールールとして知られる計算効率の良いアプローチを組み合わせた新しいポリシーを提案する。
論文参考訳（メタデータ） (2023-10-01T01:37:02Z)
Top Two Algorithms Revisited [14.783452541904365]
トップ2のアルゴリズムは、トンプソンサンプリングの多腕バンディットモデルにおける最高の腕識別への適応として現れた。本稿では,トップ2手法の一般解析を行い,リーダーの望ましい特性,挑戦者,および腕の(おそらくは非パラメトリックな)分布を同定する。提案手法は,トンプソンサンプリングから受け継いだリーダの選択に使用されるサンプリングステップを,他の選択に置き換えることができることを示す。
論文参考訳（メタデータ） (2022-06-13T09:03:24Z)
Best Arm Identification in Restless Markov Multi-Armed Bandits [85.55466536537293]
マルチアームバンディット環境における最適な腕を特定することの問題点について検討する。決定エンティティは、上限誤差確率を条件として、ベストアームのインデックスをできるだけ早く見つけることを希望する。このポリシーは、$R$に依存する上限を達成し、$Rtoinfty$として単調に増加しないことを示す。
論文参考訳（メタデータ） (2022-03-29T04:58:04Z)
Combinatorial Bandits without Total Order for Arms [52.93972547896022]
セット依存報酬分布を捕捉し、武器の合計順序を仮定しない報酬モデルを提案する。我々は、新しい後悔分析を開発し、$Oleft(frack2 n log Tepsilonright)$ gap-dependent regret boundと$Oleft(k2sqrtn T log Tright)$ gap-dependent regret boundを示す。
論文参考訳（メタデータ） (2021-03-03T23:08:59Z)
Thompson Sampling for Unsupervised Sequential Selection [3.5436187733613087]
教師なしシークエンシャルセレクション(USS)問題に対するトンプソンサンプリングに基づくアルゴリズムについて検討する。 USS問題(英語: USS problem)は、観測されたフィードバックから腕の喪失を推測できないマルチアームバンディット問題の変種である。我々は,Thompson Sampling をベースとした USS 問題に対するアルゴリズムが,ほぼ最適な後悔を達成し,既存のアルゴリズムよりも優れた数値性能を有することを示す。
論文参考訳（メタデータ） (2020-09-16T08:48:17Z)
MOTS: Minimax Optimal Thompson Sampling [89.2370817955411]
トンプソンサンプリングがミニマックス下限の$Omega(sqrtKT)$と$K$の武器付きバンディット問題に一致するかどうかという未解決の問題のままである。我々は,各タイミングで選択した腕のサンプリングインスタンスを適応的にクリップするMOTSと呼ばれるトンプソンサンプリングの変種を提案する。我々は、この単純なトンプソンサンプリングの変種が、有限時間地平線に対して$O(sqrtKT)$のミニマックス最適後悔境界と、$T$が無限に近づくときのガウス報酬に対する最適後悔境界を達成することを証明した。
論文参考訳（メタデータ） (2020-03-03T21:24:39Z)

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