論文の概要: Non-Asymptotic Best Policy Identification Guarantees in Online Reinforcement Learning

• arxiv url: http://arxiv.org/abs/2607.17201v1
• Date: Sun, 19 Jul 2026 11:48:09 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-21 18:48:37.39137
• Title: Non-Asymptotic Best Policy Identification Guarantees in Online Reinforcement Learning
• Title（参考訳）: オンライン強化学習における非漸近的ベストポリシー識別保証
• Abstract要約: これは、学習者の目的が、信頼性の高い意思決定プロセス(MDP)における最適なポリシーを特定することにある、活発なシーケンシャルな仮説テスト問題である。 決定論的報酬を伴うオンライン・セッティングについて検討し、エージェントは効果的に探索するためにMDPをナビゲートする必要がある。
• 参考スコア（独自算出の注目度）: 27.12987353045116
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: In this work we study the Best Policy Identification (BPI) problem in online, tabular Reinforcement Learning. This is an active sequential hypothesis testing problem in which the learner's objective is to identify an optimal policy in a Markov Decision Process (MDP) with high confidence, while minimizing the expected sample complexity to do so. We consider an online setting with deterministic rewards, where the agent must strategically navigate through the MDP in order to effectively explore. Previous works in the literature have provided asymptotically optimal methods for BPI, such as the Navigate and Stop (NaS) algorithm and its variants, however existing analysis remains asymptotic. In this work, we fill that gap by providing the first non-asymptotic sample complexity guarantees for NaS, showing that its sample complexity depends not only on the characteristic time, but also on the connectivity of the underlying MDP, the curvature of the optimal characteristic time, and other instance-dependent quantities. We identify these additional attributes and make explicit their contributions to the overall sample complexity.
• Abstract（参考訳）: 本研究では,オンライン表型強化学習におけるBPI(Best Policy Identification)問題について検討する。 これは、学習者の目的が、期待されるサンプルの複雑さを最小限に抑えつつ、信頼性の高いマルコフ決定プロセス(MDP)において最適なポリシーを特定することにある、活発なシーケンシャルな仮説テスト問題である。 エージェントは効果的に探索するためにMDPを通して戦略的にナビゲートする必要がある。 これまでの文献では、Navigate and Stop (NaS)アルゴリズムやその変種など、BPIの漸近的最適手法が提供されていたが、既存の分析は漸近的のままである。 本研究は,NaSの非漸近的試料複雑性保証を初めて提供することによって,そのギャップを埋めるものであり,そのサンプルの複雑性は特性時間だけでなく,基礎となるMDPの接続性,最適特性時間の曲率,その他のインスタンス依存量にも依存することを示す。 これらの属性を同定し、サンプルの複雑さ全体への貢献を明確にする。

関連論文リスト

• Sample Complexity of Offline Distributionally Robust Linear Markov Decision Processes [37.15580574143281]
  オフライン強化学習(RL) 本稿では、オフラインデータを用いた全変動距離を特徴とする不確実性を伴う分布安定線形マルコフ決定過程(MDP)のサンプル複雑性について考察する。 我々は悲観的なモデルに基づくアルゴリズムを開発し、最小限のデータカバレッジ仮定の下でそのサンプルの複雑さを確立する。
  論文  参考訳（メタデータ） (2024-03-19T17:48:42Z)
• Towards Instance-Optimality in Online PAC Reinforcement Learning [28.156332484814616]
  そこで本研究では,PACの同定に要するサンプルの複雑さに対する最初のインスタンス依存下限について提案する。 我々は、citeWagenmaker22linearMDPのPEDELアルゴリズムのサンプル複雑さがこの下界に近づいたことを実証する。
  論文  参考訳（メタデータ） (2023-10-31T19:26:36Z)
• Online POMDP Planning with Anytime Deterministic Optimality Guarantees [13.824288326240927]
  近似解と最適解の間の離散POMDPに対する決定論的関係を導出する。 我々の導出は、新しいアルゴリズムセットの道を提供し、既存のアルゴリズムにアタッチできることを示します。
  論文  参考訳（メタデータ） (2023-10-03T04:40:38Z)
• Faster Stochastic Variance Reduction Methods for Compositional MiniMax Optimization [50.10952609321302]
  合成ミニマックス最適化は、さまざまな機械学習領域において重要な課題である。 構成最小最適化の現在の方法は、最適以下の複雑さや、大きなバッチサイズに大きく依存することによって悩まされている。 本稿では,Nested STOchastic Recursive Momentum (NSTORM)と呼ばれる新しい手法を提案する。
  論文  参考訳（メタデータ） (2023-08-18T14:57:21Z)
• Provably Efficient UCB-type Algorithms For Learning Predictive State Representations [55.00359893021461]
  逐次決定問題は、予測状態表現(PSR)によってモデル化された低ランク構造が認められる場合、統計的に学習可能である 本稿では,推定モデルと実モデル間の全変動距離を上限とする新しいボーナス項を特徴とする,PSRに対する最初のUCB型アプローチを提案する。 PSRに対する既存のアプローチとは対照的に、UCB型アルゴリズムは計算的トラクタビリティ、最優先の準最適ポリシー、モデルの精度が保証される。
  論文  参考訳（メタデータ） (2023-07-01T18:35:21Z)
• Offline Reinforcement Learning with Additional Covering Distributions [0.0]
  我々は,関数近似を用いて,ログ化されたデータセット,すなわちオフラインRLから最適ポリシーを学習する。 一般のMDPに対するサンプル効率のよいオフラインRLは、部分的カバレッジデータセットと弱い実現可能な関数クラスだけで実現可能であることを示す。
  論文  参考訳（メタデータ） (2023-05-22T03:31:03Z)
• Pessimism in the Face of Confounders: Provably Efficient Offline Reinforcement Learning in Partially Observable Markov Decision Processes [99.26864533035454]
  半可観測マルコフ決定過程におけるオフライン強化学習(RL)について検討する。 本稿では,UnderlineProxy変数 underlinePessimistic UnderlinePolicy UnderlineOptimization (textttP3O)アルゴリズムを提案する。 textttP3Oは、確立されたデータセットを持つPOMDPのための証明可能な最初のオフラインRLアルゴリズムである。
  論文  参考訳（メタデータ） (2022-05-26T19:13:55Z)
• Pessimistic Q-Learning for Offline Reinforcement Learning: Towards Optimal Sample Complexity [51.476337785345436]
  有限水平マルコフ決定過程の文脈におけるQ-ラーニングの悲観的変種について検討する。 ほぼ最適サンプル複雑性を実現するために,分散再現型悲観的Q-ラーニングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-02-28T15:39:36Z)
• Sequential Information Design: Markov Persuasion Process and Its Efficient Reinforcement Learning [156.5667417159582]
  本稿では,逐次情報設計の新たなモデル,すなわちマルコフ説得過程(MPP)を提案する。 MPPのプランニングは、ミオピックレシーバーに同時に説得されるシグナルポリシーを見つけ、送信者の最適な長期累積ユーティリティを誘導する、というユニークな課題に直面している。 我々は,楽観主義と悲観主義の両原理の新たな組み合わせを特徴とする,実証可能な効率のよい非回帰学習アルゴリズム,Optimism-Pessimism Principle for Persuasion Process (OP4) を設計する。
  論文  参考訳（メタデータ） (2022-02-22T05:41:43Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Sample-Efficient Reinforcement Learning of Undercomplete POMDPs [91.40308354344505]
  この研究は、これらの硬度障壁が、部分観測可能決定過程(POMDP)の豊かで興味深いサブクラスに対する効率的な強化学習を妨げないことを示している。 提案手法は, 観測回数が潜伏状態の数よりも大きく, 探索が学習に不可欠であり, 先行研究と区別できるような, エピソード有限不完全POMDPに対するサンプル効率アルゴリズムOOM-UCBを提案する。
  論文  参考訳（メタデータ） (2020-06-22T17:58:54Z)

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

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