論文の概要: Thompson Sampling for Infinite-Horizon Discounted Decision Processes

• arxiv url: http://arxiv.org/abs/2405.08253v2
• Date: Fri, 17 May 2024 05:58:07 GMT
• ステータス: 処理完了
• システム内更新日: 2024-05-20 11:55:15.359823
• Title: Thompson Sampling for Infinite-Horizon Discounted Decision Processes
• Title（参考訳）: 無限水平離散決定過程に対するトンプソンサンプリング
• Authors: Daniel Adelman, Cagla Keceli, Alba V. Olivares-Nadal,
• Abstract要約: 我々はトンプソンサンプリングと呼ばれるサンプリングベースアルゴリズムの挙動を研究する。 標準の(予想された)後悔を分解することで、期待された後悔という新しい尺度を開発します。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We model a Markov decision process, parametrized by an unknown parameter, and study the asymptotic behavior of a sampling-based algorithm, called Thompson sampling. The standard definition of regret is not always suitable to evaluate a policy, especially when the underlying chain structure is general. We show that the standard (expected) regret can grow (super-)linearly and fails to capture the notion of learning in realistic settings with non-trivial state evolution. By decomposing the standard (expected) regret, we develop a new metric, called the expected residual regret, which forgets the immutable consequences of past actions. Instead, it measures regret against the optimal reward moving forward from the current period. We show that the expected residual regret of the Thompson sampling algorithm is upper bounded by a term which converges exponentially fast to 0. We present conditions under which the posterior sampling error of Thompson sampling converges to 0 almost surely. We then introduce the probabilistic version of the expected residual regret and present conditions under which it converges to 0 almost surely. Thus, we provide a viable concept of learning for sampling algorithms which will serve useful in broader settings than had been considered previously.
• Abstract（参考訳）: 我々は、未知パラメータによってパラメータ化されたマルコフ決定過程をモデル化し、トンプソンサンプリングと呼ばれるサンプリングベースアルゴリズムの漸近挙動を研究する。 後悔の標準的な定義は、特に下層の連鎖構造が一般である場合、政策を評価するのに必ずしも適していない。 我々は、(予想された)後悔が(超)直線的に成長し、非自明な状態進化を伴う現実的な環境での学習の概念を捉えることができないことを示す。 標準的な(予想された)後悔を分解することで、期待された後悔という新しい尺度を開発し、過去の行動の不変な結果を無視します。 代わりに、現在の期間から進む最適な報酬に対して後悔を測る。 トンプソンサンプリングアルゴリズムの残差残差は指数関数的に0に収束する項によって上界化されていることを示す。 我々は、トンプソンサンプリングの後方サンプリング誤差がほぼ確実に0に収束する条件を示す。 次に、期待された残差残差の確率バージョンと、それがほぼ確実に 0 に収束する現在の条件を導入する。 そこで本研究では,これまで考えられてきたよりも広い環境において有用なアルゴリズムを抽出する学習方法を提案する。

関連論文リスト

• Approximate Thompson Sampling for Learning Linear Quadratic Regulators with $O(\sqrt{T})$ Regret [10.541541376305243]
  本稿では,線形二次レギュレータ(LQR)を改良したベイズ的残差値$O(sqrtT)$で学習する近似トンプソンサンプリングアルゴリズムを提案する。 励振信号は、プレコンディショナーの最小固有値を時間とともに増加させ、近似した後方サンプリングプロセスを加速させることを示す。
  論文  参考訳（メタデータ） (2024-05-29T03:24:56Z)
• The Sliding Regret in Stochastic Bandits: Discriminating Index and Randomized Policies [0.8158530638728501]
  バンディットのためのノンレグレットアルゴリズムのワンショット動作について検討する。 一定長さが無限に滑り落ちるタイムウインドウ上で最悪の擬似回帰を測定するスライディング後悔(slide regret)という新しい概念を導入する。
  論文  参考訳（メタデータ） (2023-11-30T10:37:03Z)
• Model-Based Uncertainty in Value Functions [89.31922008981735]
  MDP上の分布によって引き起こされる値の分散を特徴付けることに重点を置いている。 従来の作業は、いわゆる不確実性ベルマン方程式を解くことで、値よりも後方の分散を境界にしている。 我々は、解が値の真後分散に収束する新しい不確実性ベルマン方程式を提案する。
  論文  参考訳（メタデータ） (2023-02-24T09:18:27Z)
• Thompson Sampling for High-Dimensional Sparse Linear Contextual Bandits [17.11922027966447]
  この研究は、高次元およびスパースな文脈的包帯におけるトンプソンサンプリングの理論的な保証を提供する。 より高速な計算のために、MCMCの代わりに未知のパラメータと変分推論をモデル化するために、スパイク・アンド・スラブを用いる。
  論文  参考訳（メタデータ） (2022-11-11T02:23:39Z)
• Finite-Time Regret of Thompson Sampling Algorithms for Exponential Family Multi-Armed Bandits [88.21288104408556]
  本研究では,指数関数族バンドイットに対するトンプソンサンプリング (TS) アルゴリズムの遺残について検討する。 最適な腕の過小評価を避けるために,新しいサンプリング分布を用いたトンプソンサンプリング(Expulli)を提案する。
  論文  参考訳（メタデータ） (2022-06-07T18:08:21Z)
• A Unifying Theory of Thompson Sampling for Continuous Risk-Averse Bandits [91.3755431537592]
  本稿では,多腕バンディット問題に対するリスク-逆トンプソンサンプリングアルゴリズムの解析を統一する。 大規模偏差理論における収縮原理を用いることで、連続リスク汎関数に対する新しい濃度境界が証明される。 リスク関数の幅広いクラスと「ニセ」関数が連続性条件を満たすことを示す。
  論文  参考訳（メタデータ） (2021-08-25T17:09:01Z)
• Asymptotic Convergence of Thompson Sampling [0.0]
  トンプソンサンプリングは、様々なオンライン学習タスクにおいて効果的なポリシーであることが示されている。 我々は、準線形ベイズ的後悔を仮定して、トンプソンサンプリングの収束結果を証明した。 この結果はトンプソンサンプリングに固有のマーチンゲール構造に依存している。
  論文  参考訳（メタデータ） (2020-11-08T07:36:49Z)
• Analysis and Design of Thompson Sampling for Stochastic Partial Monitoring [91.22679787578438]
  部分モニタリングのためのトンプソンサンプリングに基づく新しいアルゴリズムを提案する。 局所可観測性を持つ問題の線形化変種に対して,新たなアルゴリズムが対数問題依存の擬似回帰$mathrmO(log T)$を達成することを証明した。
  論文  参考訳（メタデータ） (2020-06-17T05:48:33Z)
• 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)

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

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