論文の概要: Analysis and Design of Thompson Sampling for Stochastic Partial
Monitoring
- arxiv url: http://arxiv.org/abs/2006.09668v2
- Date: Thu, 10 Jun 2021 09:00:24 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-19 19:34:55.600673
- Title: Analysis and Design of Thompson Sampling for Stochastic Partial
Monitoring
- Title（参考訳）: 確率的部分監視のためのトンプソンサンプリングの解析と設計
- Authors: Taira Tsuchiya, Junya Honda, Masashi Sugiyama
- Abstract要約: 部分モニタリングのためのトンプソンサンプリングに基づく新しいアルゴリズムを提案する。
局所可観測性を持つ問題の線形化変種に対して,新たなアルゴリズムが対数問題依存の擬似回帰$mathrmO(log T)$を達成することを証明した。
- 参考スコア（独自算出の注目度）: 91.22679787578438
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We investigate finite stochastic partial monitoring, which is a general model
for sequential learning with limited feedback. While Thompson sampling is one
of the most promising algorithms on a variety of online decision-making
problems, its properties for stochastic partial monitoring have not been
theoretically investigated, and the existing algorithm relies on a heuristic
approximation of the posterior distribution. To mitigate these problems, we
present a novel Thompson-sampling-based algorithm, which enables us to exactly
sample the target parameter from the posterior distribution. Besides, we prove
that the new algorithm achieves the logarithmic problem-dependent expected
pseudo-regret $\mathrm{O}(\log T)$ for a linearized variant of the problem with
local observability. This result is the first regret bound of Thompson sampling
for partial monitoring, which also becomes the first logarithmic regret bound
of Thompson sampling for linear bandits.
- Abstract（参考訳）: 有限確率部分モニタリングは,フィードバックが限定された逐次学習の一般的なモデルである。
トンプソンサンプリングは、様々なオンライン意思決定問題の最も有望なアルゴリズムの1つであるが、確率的部分監視の特性は理論的には研究されておらず、既存のアルゴリズムは後方分布のヒューリスティック近似に依存している。
これらの問題を緩和するために,後方分布からターゲットパラメータを正確にサンプリングできる新しいトンプソンサンプリングに基づくアルゴリズムを提案する。
さらに、新しいアルゴリズムが局所可観測性を持つ問題の線形変種に対して対数問題依存の期待値である$\mathrm{o}(\log t)$ を達成することを証明した。
この結果は、部分的監視のためのトンプソンサンプリングの最初の後悔バウンドであり、線形バンドイットに対するトンプソンサンプリングの最初の対数的後悔バウンドとなる。
関連論文リスト
- VITS : Variational Inference Thompson Sampling for contextual bandits [10.028119153832346]
我々は、文脈的帯域幅に対するトンプソンサンプリング(TS)アルゴリズムの変種を導入・解析する。
ガウス変分推論に基づく新しいアルゴリズムであるValational Inference Thompson sample VITSを提案する。
我々は,VITS が線形文脈帯域に対して従来の TS の次元とラウンド数で同じ順序のサブ線形後悔境界を達成することを示す。
論文 参考訳（メタデータ） (2023-07-19T17:53:22Z) - 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) - A Unifying Theory of Thompson Sampling for Continuous Risk-Averse
Bandits [91.3755431537592]
本稿では,多腕バンディット問題に対するリスク-逆トンプソンサンプリングアルゴリズムの解析を統一する。
大規模偏差理論における収縮原理を用いることで、連続リスク汎関数に対する新しい濃度境界が証明される。
リスク関数の幅広いクラスと「ニセ」関数が連続性条件を満たすことを示す。
論文 参考訳（メタデータ） (2021-08-25T17:09:01Z) - Diffusion Approximations for Thompson Sampling [4.390757904176221]
本研究では,SDEの水平線とODEの離散バージョンに基づいてトンプソンサンプリングのダイナミクスが進化することを示す。
我々の弱収束理論は、連続写像定理を用いて第一原理から発展する。
論文 参考訳（メタデータ） (2021-05-19T16:28:01Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳（メタデータ） (2020-09-28T15:22:24Z) - Active Model Estimation in Markov Decision Processes [108.46146218973189]
マルコフ決定過程(MDP)をモデル化した環境の正確なモデル学習のための効率的な探索の課題について検討する。
マルコフに基づくアルゴリズムは,本アルゴリズムと極大エントロピーアルゴリズムの両方を小サンプル方式で上回っていることを示す。
論文 参考訳（メタデータ） (2020-03-06T16:17:24Z) - On Thompson Sampling with Langevin Algorithms [106.78254564840844]
多武装バンディット問題に対するトンプソンサンプリングは理論と実践の両方において良好な性能を享受する。
計算上のかなりの制限に悩まされており、反復ごとに後続分布からのサンプルを必要とする。
本稿では,この問題に対処するために,トンプソンサンプリングに適した2つのマルコフ連鎖モンテカルロ法を提案する。
論文 参考訳（メタデータ） (2020-02-23T22:35:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。