論文の概要: Beyond No Regret: Instance-Dependent PAC Reinforcement Learning
- arxiv url: http://arxiv.org/abs/2108.02717v1
- Date: Thu, 5 Aug 2021 16:34:17 GMT
- ステータス: 処理完了
- システム内更新日: 2021-08-06 14:51:33.209956
- Title: Beyond No Regret: Instance-Dependent PAC Reinforcement Learning
- Title（参考訳）: No Regretを超える: インスタンス依存のPAC強化学習
- Authors: Andrew Wagenmaker, Max Simchowitz, Kevin Jamieson
- Abstract要約: 低後悔を達成し、インスタンス最適率で$epsilon$-optimal Policyを特定できるというトレードオフが存在することを示す。
本稿では,このサンプル複雑性を実現する新しい計画ベースアルゴリズムの提案と解析を行う。
我々のアルゴリズムは最小限の最適値であり、いくつかの例では、インスタンス依存のサンプル複雑性は最悪のケース境界よりも大幅に改善されている。
- 参考スコア（独自算出の注目度）: 29.552894877883883
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The theory of reinforcement learning has focused on two fundamental problems:
achieving low regret, and identifying $\epsilon$-optimal policies. While a
simple reduction allows one to apply a low-regret algorithm to obtain an
$\epsilon$-optimal policy and achieve the worst-case optimal rate, it is
unknown whether low-regret algorithms can obtain the instance-optimal rate for
policy identification. We show that this is not possible -- there exists a
fundamental tradeoff between achieving low regret and identifying an
$\epsilon$-optimal policy at the instance-optimal rate.
Motivated by our negative finding, we propose a new measure of
instance-dependent sample complexity for PAC tabular reinforcement learning
which explicitly accounts for the attainable state visitation distributions in
the underlying MDP. We then propose and analyze a novel, planning-based
algorithm which attains this sample complexity -- yielding a complexity which
scales with the suboptimality gaps and the ``reachability'' of a state. We show
that our algorithm is nearly minimax optimal, and on several examples that our
instance-dependent sample complexity offers significant improvements over
worst-case bounds.
- Abstract（参考訳）: 強化学習の理論は、2つの基本的な問題に焦点をあてている: 後悔の少ないこと、そして$\epsilon$-Optimal Policyを同定する。
簡単な減算法では、$\epsilon$-optimal policy と the worst-casetimal rate をローレグレットアルゴリズムに適用できるが、低レグレットアルゴリズムがポリシー識別のインスタンス最適化率を得ることができるかどうかは不明である。
低い後悔を達成することと、インスタンス最適化率で$\epsilon$-Optimalポリシーを特定することの間には、根本的なトレードオフが存在する。
そこで本研究では, PAC表層強化学習において, MDPの達成可能な状態訪問分布を明示的に考慮し, インスタンス依存型サンプル複雑性の新たな尺度を提案する。
次に,このサンプル複雑性を達成するための新しい計画ベースアルゴリズムを提案し解析し,準最適ギャップと状態の'到達可能性'にスケールする複雑性をもたらす。
我々のアルゴリズムは最小限の最適値であり、いくつかの例では、インスタンス依存のサンプル複雑性は最悪のケース境界よりも大幅に改善されている。
関連論文リスト
- Towards Instance-Optimality in Online PAC Reinforcement Learning [28.156332484814616]
そこで本研究では,PACの同定に要するサンプルの複雑さに対する最初のインスタンス依存下限について提案する。
我々は、citeWagenmaker22linearMDPのPEDELアルゴリズムのサンプル複雑さがこの下界に近づいたことを実証する。
論文 参考訳（メタデータ） (2023-10-31T19:26:36Z) - Faster Stochastic Variance Reduction Methods for Compositional MiniMax
Optimization [50.10952609321302]
合成ミニマックス最適化は、さまざまな機械学習領域において重要な課題である。
構成最小最適化の現在の方法は、最適以下の複雑さや、大きなバッチサイズに大きく依存することによって悩まされている。
本稿では,Nested STOchastic Recursive Momentum (NSTORM)と呼ばれる新しい手法を提案する。
論文 参考訳（メタデータ） (2023-08-18T14:57:21Z) - Nearly Optimal Latent State Decoding in Block MDPs [74.51224067640717]
エピソードブロック MDP では、意思決定者は少数の潜在状態から生成される豊富な観測やコンテキストにアクセスすることができる。
まず、固定動作ポリシーに基づいて生成されたデータに基づいて、潜時状態復号関数を推定することに興味がある。
次に、報酬のないフレームワークにおいて、最適に近いポリシーを学習する問題について研究する。
論文 参考訳（メタデータ） (2022-08-17T18:49:53Z) - Optimistic PAC Reinforcement Learning: the Instance-Dependent View [24.256960622176305]
PAC RL, BPI-UCRL に対する楽観的アルゴリズムを提案する。
私たちの限界は、最小の訪問確率を特徴としていますが、それはまた、準最適ギャップという洗練された概念も特徴です。
決定論的遷移を持つMDPでは、BPI-UCRLが実際にはほぼ最適であることを示す。
論文 参考訳（メタデータ） (2022-07-12T21:35:03Z) - Instance-Dependent Near-Optimal Policy Identification in Linear MDPs via
Online Experiment Design [12.056495277232118]
この研究は、ほぼ最適ポリシーを学ぶことの「インスタンスに依存した」複雑さを理解することを目的としている。
本稿では,複雑性の詳細なインスタンス依存尺度を実現するアルゴリズムである textscPedel を提案する。
我々は、textscPedel が低regret, minimax-optimal アルゴリズムよりも有益であることを示す。
論文 参考訳（メタデータ） (2022-07-06T10:42:57Z) - Near Instance-Optimal PAC Reinforcement Learning for Deterministic MDPs [24.256960622176305]
エピソードマルコフ決定過程におけるPAC RLのサンプル複雑性について, 上界と下界の整合性について検討した。
私たちの境界は、決定論的リターンギャップ(deterministic return gap)と呼ばれる状態-作用ペアに対して、新たな最適ギャップ(sub-optimality gap)を特徴とする。
彼らの設計と分析は、最小フローや最大カットといったグラフ理論の概念を含む新しいアイデアを採用している。
論文 参考訳（メタデータ） (2022-03-17T11:19:41Z) - Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free
Reinforcement Learning [52.76230802067506]
漸進的強化学習における後悔を最小限に抑えるために,新しいモデルフリーアルゴリズムを提案する。
提案アルゴリズムは、2つのQ-ラーニングシーケンスの助けを借りて、初期設定された参照更新ルールを用いる。
初期の分散還元法の設計原理は、他のRL設定とは独立した関心を持つかもしれない。
論文 参考訳（メタデータ） (2021-10-09T21:13:48Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳（メタデータ） (2020-09-28T15:22:24Z) - Beyond Worst-Case Analysis in Stochastic Approximation: Moment
Estimation Improves Instance Complexity [58.70807593332932]
近似問題に対する勾配に基づく手法のオラクル複雑性について検討する。
最悪のケースの複雑さではなく、インスタンス依存の複雑さに焦点を当てます。
提案アルゴリズムとその解析はモーメント推定の成功を理論的に正当化する。
論文 参考訳（メタデータ） (2020-06-08T09:25:47Z) - The Simulator: Understanding Adaptive Sampling in the
Moderate-Confidence Regime [52.38455827779212]
エミュレータと呼ばれる適応サンプリングを解析するための新しい手法を提案する。
適切なログファクタを組み込んだトップk問題の最初のインスタンスベースの下位境界を証明します。
我々の新しい分析は、後者の問題に対するこの種の最初のエミュレータであるベストアームとトップkの識別に、シンプルでほぼ最適であることを示した。
論文 参考訳（メタデータ） (2017-02-16T23:42:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。