論文の概要: Minimax-Optimality of Posterior Sampling for Reinforcement Learning

• arxiv url: http://arxiv.org/abs/2609.33246v1
• Date: Sun, 27 Sep 2026 05:36:53 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-06 01:51:35.627135
• Title: Minimax-Optimality of Posterior Sampling for Reinforcement Learning
• Title（参考訳）: 強化学習における後方サンプリングの極小最適性
• Abstract要約: 強化学習のための後方サンプリング(PSRL)は、最も単純かつ効果的な探索手法の1つである。 任意の相関した事前条件下で, Exact vanilla PSRL は前順序ベイズ的後悔に最適であることを示す。
• 参考スコア（独自算出の注目度）: 2.9220076568786335
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Posterior sampling for reinforcement learning (PSRL) is one of the simplest and most effective exploration methods, but a basic question has remained open: does unmodified PSRL achieve minimax regret without structural assumptions on the prior? We answer yes. Exact vanilla PSRL is minimax optimal in leading-order Bayesian regret under arbitrary correlated priors. The difficulty is that a posterior-sampled transition model is coupled with its own continuation value. We overcome this with a common empirical transition reference that isolates the resulting value mismatch and a Bellman-based variance argument that controls it without an extra leading-order state-space factor. For finite-horizon, time-inhomogeneous tabular MDPs with unknown stochastic rewards, this yields the minimax $\widetilde{O}(\sqrt{SAH^3K})$ regret rate under arbitrary joint priors over rewards and transitions. The same proof principle gives the minimax $\widetilde{O}(d\sqrt{H^3K})$ rate for linear-mixture MDPs under arbitrary joint parameter priors.
• Abstract（参考訳）: 強化学習のための後方サンプリング(PSRL)は、最も単純かつ効果的な探索手法の1つであるが、基本的な問題は未修正PSRLは、事前の構造的仮定なしで、最小限の後悔を達成できるのか? 私たちはイエスに答える。 厳密なバニラPSRLは任意の相関した先行条件の下で前順序ベイズ的後悔に最適である。 困難は、後サンプル遷移モデルが自身の継続値と結合されることである。 我々はこれを、結果の値ミスマッチを分離する共通の経験的遷移参照と、余分な先行順序状態空間因子なしで制御するベルマン型分散引数で克服する。 有限ホライゾン、時間不均質な表形式 MDP に対して、確率的な報酬が未知である場合、これは報酬と遷移に対する任意のジョイントの先行の下で、minimax $\widetilde{O}(\sqrt{SAH^3K})$ 後悔率をもたらす。 同じ証明原理は、任意の関節パラメータの前の線形混合 MDP に対する minimax $\widetilde{O}(d\sqrt{H^3K})$ rate を与える。

関連論文リスト

• Near-Optimal Primal-Dual Algorithm for Learning Linear Mixture CMDPs with Adversarial Rewards [0.8984888893275712]
  有限-水平線形混合制約マルコフ決定過程における安全強化学習について検討する。 本稿では, 後悔と制約違反境界を実現するプリミティブ・デュアルポリシー最適化アルゴリズムを提案する。 これは、線形混合CMDPと逆効果を持つ最初の証明可能な効率のよいアルゴリズムである。
  論文  参考訳（メタデータ） (2026-03-29T21:51:33Z)
• Improved Algorithm for Adversarial Linear Mixture MDPs with Bandit Feedback and Unknown Transition [71.33787410075577]
  線形関数近似,未知遷移,および逆損失を用いた強化学習について検討した。 我々は高い確率で$widetildeO(dsqrtHS3K + sqrtHSAK)$ regretを実現する新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-03-07T15:03:50Z)
• Settling the Sample Complexity of Online Reinforcement Learning [92.02082223856479]
  バーンインコストを発生させることなく、最小限の最適後悔を実現する方法を示す。 最適値/コストや一定の分散といった問題依存量の影響を明らかにするために、我々の理論を拡張します。
  論文  参考訳（メタデータ） (2023-07-25T15:42:11Z)
• Safe Posterior Sampling for Constrained MDPs with Bounded Constraint Violation [8.849815837266977]
  制約付きマルコフ決定プロセス(CMDP)は、多くのアプリケーションにおいてますます重要になっている複数の目的を持つシーケンシャルな意思決定のシナリオをモデル化する。 我々は,そのような仮定を必要とせず,しかも非常によく機能するSafe PSRL (posterior sample-based RL)アルゴリズムを提案する。 準線形$tildemathcal Oleft(H2.5 sqrt|mathcalS|2 |mathcalA|K right)$上界をベイズ賞の目的的後悔と、有界なイデアルとともに成立させる。
  論文  参考訳（メタデータ） (2023-01-27T06:18:25Z)
• Optimistic Posterior Sampling for Reinforcement Learning with Few Samples and Tight Guarantees [43.13918072870693]
  強化学習(OPSRL)のための楽観的後部サンプリングアルゴリズムを提案する。 殆どの$widetildemathcalO(sqrtH3SAT)$ ignoring $textpolylog(HSAT)$ termsにおいて、高い確率で再帰的な順序境界を保証する。 我々の境界は位数$Omega(sqrtH3SAT)$の下位境界と一致し、Agrawal と Jia が提起した開問題に答える。
  論文  参考訳（メタデータ） (2022-09-28T20:49:34Z)
• Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning [52.76230802067506]
  漸進的強化学習における後悔を最小限に抑えるために,新しいモデルフリーアルゴリズムを提案する。 提案アルゴリズムは、2つのQ-ラーニングシーケンスの助けを借りて、初期設定された参照更新ルールを用いる。 初期の分散還元法の設計原理は、他のRL設定とは独立した関心を持つかもしれない。
  論文  参考訳（メタデータ） (2021-10-09T21:13:48Z)

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

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