論文の概要: Towards instance-dependent regret optimality in Episodic MDPs with Posterior Sampling

• arxiv url: http://arxiv.org/abs/2610.26029v1
• Date: Mon, 19 Oct 2026 08:51:00 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-24 02:49:45.005139
• Title: Towards instance-dependent regret optimality in Episodic MDPs with Posterior Sampling
• Title（参考訳）: 事後サンプリングを用いたエピソードMDPのインスタンス依存的後悔最適性に向けて
• Abstract要約: 有限水平マルコフ決定過程(MDP)における後悔の最小化に関する研究 固定参照ポリシーに従って,後部サンプルを用いて探索のタイミングを決定するPSRLの変種を導入する。 提案手法は, エピソードMDPにおける問題依存的再帰境界を導出する新しい証明構造を示す。
• 参考スコア（独自算出の注目度）: 17.39312362863294
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study regret minimization in finite-horizon episodic Markov Decision Processes (MDPs). While minimax-optimal algorithms are known, tractable approaches to instance-dependent optimality are still lacking. Motivated by this gap, we introduce $π_0$-PSRL, a variant of PSRL that uses posterior samples to decide when exploration is needed, while following a fixed reference policy $π_0$ during exploration episodes. This decouples the test for exploration, triggered when the sampled and empirical MDPs have different optimal policies, from the choice of the policy used to gather information. The resulting design addresses a limitation of standard PSRL, where the sampled optimal policy may not be the optimal choice for exploration. We prove instance-dependent regret bounds for $π_0$-PSRL, identifying the logarithmic exploration cost induced by $π_0$ and taking a step toward matching asymptotic lower bounds for episodic RL. Our proof techniques showcase a novel proof structure to derive problem-dependent regret bounds in episodic MDPs, and concentration results for Dirichlet random variables, that may be of independent interest.
• Abstract（参考訳）: 有限水平マルコフ決定過程(MDP)における後悔の最小化について検討した。 ミニマックス最適化アルゴリズムは知られているが、インスタンス依存の最適性に対する抽出可能なアプローチはまだ不足している。 このギャップに触発されたPSRLはPSRLの変種であり、探査の際、固定参照ポリシーである$π_0$-PSRLを踏襲しながら、探査のタイミングを決定するために後部サンプルを用いる。 このことは、サンプルと実証的なMDPが、情報収集に使用されるポリシーの選択から、異なる最適なポリシーを持つときに引き起こされる探索の試験を分離する。 結果として得られた設計は標準PSRLの制限に対処し、サンプル化された最適ポリシーは探索に最適な選択肢ではないかもしれない。 我々は, π_0$-PSRLのインスタンス依存後悔境界を証明し, π_0$によって引き起こされる対数探索コストを同定し, エピソードRLの漸近下界との整合に向けて一歩踏み出した。 提案手法は, エピソードMDPにおける問題依存的再帰境界を導出する新しい証明構造を示し, ディリクレ確率変数の濃度分布は, 独立な関心を持つ可能性がある。

関連論文リスト

• Optimal Posterior Sampling for Policy Identification in Tabular Markov Decision Processes [3.2959629354399484]
  有限水平エピソードマルコフ決定における$(varepsilon, )$PAC-PACポリシー識別問題について検討する。 本稿では,後続サンプリングとオンライン学習アルゴリズムを組み合わせてMDPを誘導する,最適ポリシー識別のためのランダムで効率的なアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2026-05-05T16:16:57Z)
• A View of the Certainty-Equivalence Method for PAC RL as an Application of the Trajectory Tree Method [5.238591085233903]
  本稿では,CEMが実際にTTMの応用と見なされるという驚くべき発見に起因した理論的研究を提案する。 我々は,非定常MPPと定常MPPの双方に対して,CEMの試料複雑度上限を(3)改良した。 また, 有限ホライズン MDP に対する標本複雑性の低い値を示し, 非定常 MDP に対する上界の最小値最適性を確立する。
  論文  参考訳（メタデータ） (2025-01-05T20:37:34Z)
• Efficient Learning of POMDPs with Known Observation Model in Average-Reward Setting [56.92178753201331]
  我々は,POMDPパラメータを信念に基づくポリシを用いて収集したサンプルから学習することのできる観測・認識スペクトル(OAS)推定手法を提案する。 提案するOAS-UCRLアルゴリズムに対して,OASプロシージャの整合性を示し,$mathcalO(sqrtT log(T)$の残差保証を証明した。
  論文  参考訳（メタデータ） (2024-10-02T08:46:34Z)
• Optimal Horizon-Free Reward-Free Exploration for Linear Mixture MDPs [60.40452803295326]
  線形マルコフ決定過程(MDP)を学習するための新たな報酬なしアルゴリズムを提案する。 我々のアルゴリズムの核心は、探索駆動の擬似回帰を用いた不確実性重み付き値目標回帰である。 我々のアルゴリズムは$tilde O(d2varepsilon-2)$ episodesを探索するだけで、$varepsilon$-optimal policyを見つけることができる。
  論文  参考訳（メタデータ） (2023-03-17T17:53:28Z)
• Near-Optimal Deployment Efficiency in Reward-Free Reinforcement Learning with Linear Function Approximation [16.871660060209674]
  本研究では, 線形関数近似を用いた展開効率向上強化学習(RL)の課題を, 遠近自由探索条件下で検討する。 我々は,最大$widetildeO(fracd2H5epsilon2)$ trajectoriesを$H$デプロイメント内で収集し,$epsilon$-Optimal Policyを任意の(おそらくはデータに依存した)報酬関数の選択に対して識別するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-10-03T03:48:26Z)
• Reinforcement Learning from Partial Observation: Linear Function Approximation with Provable Sample Efficiency [111.83670279016599]
  部分観察決定過程(POMDP)の無限観測および状態空間を用いた強化学習について検討した。 線形構造をもつPOMDPのクラスに対する部分可観測性と関数近似の最初の試みを行う。
  論文  参考訳（メタデータ） (2022-04-20T21:15:38Z)
• Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processes [61.11090361892306]
  Reward-free reinforcement learning (RL) は、エージェントが探索中に報酬関数にアクセスできないような環境を考える。 この分離は線形MDPの設定には存在しないことを示す。 我々は$d$次元線形 MDP における報酬のない RL に対する計算効率の良いアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-01-26T22:09:59Z)
• Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning [52.76230802067506]
  漸進的強化学習における後悔を最小限に抑えるために,新しいモデルフリーアルゴリズムを提案する。 提案アルゴリズムは、2つのQ-ラーニングシーケンスの助けを借りて、初期設定された参照更新ルールを用いる。 初期の分散還元法の設計原理は、他のRL設定とは独立した関心を持つかもしれない。
  論文  参考訳（メタデータ） (2021-10-09T21:13:48Z)

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

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