論文の概要: When is Agnostic Reinforcement Learning Statistically Tractable?

• arxiv url: http://arxiv.org/abs/2310.06113v1
• Date: Mon, 9 Oct 2023 19:40:54 GMT
• ステータス: 処理完了
• システム内更新日: 2023-10-11 23:31:55.012560
• Title: When is Agnostic Reinforcement Learning Statistically Tractable?
• Title（参考訳）: 統計的にトラクタブルなAgnostic Reinforcement Learning
• Authors: Zeyu Jia, Gene Li, Alexander Rakhlin, Ayush Sekhari, Nathan Srebro
• Abstract要約: エンフスパンニング容量と呼ばれる新しい複雑性測度は、設定された$Pi$にのみ依存し、MDPダイナミクスとは独立である。 我々は、学習するためにスーパーポリノミカルな数のサンプルを必要とする制限付きスパンリング能力を持つポリシークラス$Pi$が存在することを示した。 これにより、生成的アクセスとオンラインアクセスモデルの間の学習可能性の驚くほどの分離が明らかになる。
• 参考スコア（独自算出の注目度）: 76.1408672715773
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the problem of agnostic PAC reinforcement learning (RL): given a policy class $\Pi$, how many rounds of interaction with an unknown MDP (with a potentially large state and action space) are required to learn an $\epsilon$-suboptimal policy with respect to $\Pi$? Towards that end, we introduce a new complexity measure, called the \emph{spanning capacity}, that depends solely on the set $\Pi$ and is independent of the MDP dynamics. With a generative model, we show that for any policy class $\Pi$, bounded spanning capacity characterizes PAC learnability. However, for online RL, the situation is more subtle. We show there exists a policy class $\Pi$ with a bounded spanning capacity that requires a superpolynomial number of samples to learn. This reveals a surprising separation for agnostic learnability between generative access and online access models (as well as between deterministic/stochastic MDPs under online access). On the positive side, we identify an additional \emph{sunflower} structure, which in conjunction with bounded spanning capacity enables statistically efficient online RL via a new algorithm called POPLER, which takes inspiration from classical importance sampling methods as well as techniques for reachable-state identification and policy evaluation in reward-free exploration.
• Abstract（参考訳）: 政策クラス$\Pi$を与えられた場合、未知のMDP(潜在的に大きな状態と行動空間を持つ)との相互作用のラウンドが、$\Pi$に関して$\epsilon$-suboptimal Policyを学習する必要があるか。 その目的に向けて、我々は、セット$\Pi$にのみ依存し、MDPダイナミクスとは独立な新しい複雑性測度である「emph{spanning capacity}」を導入する。 生成モデルを用いて、任意のポリシークラスに対して$\pi$の有界スパンニング能力がpac学習性を特徴付けることを示す。 しかし、オンラインRLの場合、状況はより微妙である。 我々は、学習するためにスーパーポリノミカルな数のサンプルを必要とする有界なスパンニング能力を持つポリシークラス$\Pi$が存在することを示した。 これは、生成的アクセスとオンラインアクセスモデル(およびオンラインアクセスにおける決定論的/系統的mdp)の間の不可知な学習可能性に対する驚くべき分離である。 正の面では,有界分散キャパシティと連動して,古典的重要度サンプリング手法や到達可能な状態同定および報酬のない探索における政策評価技術から着想を得たPOPLERと呼ばれる新しいアルゴリズムを用いて,統計的に効率的なオンラインRLを実現する,追加の \emph{sunflower} 構造を同定する。

関連論文リスト

• Online Policy Learning and Inference by Matrix Completion [12.527541242185404]
  行列完備帯域(MCB)として問題を定式化する。 我々は、$epsilon$-greedy banditとオンライン勾配降下について検討する。 より早く崩壊する探索は、より少ない後悔をもたらすが、最適なポリシーをより正確に学習する。
  論文  参考訳（メタデータ） (2024-04-26T13:19:27Z)
• Low-Rank MDPs with Continuous Action Spaces [42.695778474071254]
  本研究では,このような手法を連続的な動作を伴う設定に拡張する問題について検討する。 アルゴリズムを変更せずに、動作が連続することを許された場合、同様のPAC境界が得られることを示す。
  論文  参考訳（メタデータ） (2023-11-06T22:05:08Z)
• Offline RL With Realistic Datasets: Heteroskedasticity and Support Constraints [82.43359506154117]
  非均一な変数を持つデータから、典型的なオフライン強化学習手法が学習できないことを示す。 提案手法は,Atariゲーム,ナビゲーション,ピクセルベースの操作において,多種多様なオフラインRL問題にまたがる性能向上を図っている。
  論文  参考訳（メタデータ） (2022-11-02T11:36:06Z)
• Jump-Start Reinforcement Learning [68.82380421479675]
  本稿では、オフラインデータやデモ、あるいは既存のポリシーを使ってRLポリシーを初期化するメタアルゴリズムを提案する。 特に,タスク解決に2つのポリシーを利用するアルゴリズムであるJump-Start Reinforcement Learning (JSRL)を提案する。 実験により、JSRLは既存の模倣と強化学習アルゴリズムを大幅に上回っていることを示す。
  論文  参考訳（メタデータ） (2022-04-05T17:25:22Z)
• Near Instance-Optimal PAC Reinforcement Learning for Deterministic MDPs [24.256960622176305]
  エピソードマルコフ決定過程におけるPAC RLのサンプル複雑性について, 上界と下界の整合性について検討した。 私たちの境界は、決定論的リターンギャップ(deterministic return gap)と呼ばれる状態-作用ペアに対して、新たな最適ギャップ(sub-optimality gap)を特徴とする。 彼らの設計と分析は、最小フローや最大カットといったグラフ理論の概念を含む新しいアイデアを採用している。
  論文  参考訳（メタデータ） (2022-03-17T11:19:41Z)
• 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)
• Settling the Horizon-Dependence of Sample Complexity in Reinforcement Learning [82.31436758872715]
  我々は,環境相互作用の$O(1)$のエピソードのみを用いて,同一のPAC保証を実現するアルゴリズムを開発した。 値関数と有限水平マルコフ決定過程の接続を確立する。
  論文  参考訳（メタデータ） (2021-11-01T00:21:24Z)
• Pessimistic Model-based Offline RL: PAC Bounds and Posterior Sampling under Partial Coverage [33.766012922307084]
  一般関数近似を用いたモデルに基づくオフライン強化学習について検討する。 本稿では、一般関数クラスを活用し、ペシミズムを符号化するために制約を用いる制約付きポリシー最適化(CPPO)というアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-07-13T16:30:01Z)
• Online Sub-Sampling for Reinforcement Learning with General Function Approximation [111.01990889581243]
  本稿では,RLアルゴリズムによって収集されたデータポイントの情報取得量を測定する,効率的なオンラインサブサンプリングフレームワークを確立する。 複雑性バウンド関数クラスを持つ値ベースのメソッドの場合、$proptooperatornamepolylog(K)$ timesに対してのみポリシーを更新する必要がある。 少なくとも$Omega(K)$倍のポリシーを更新する既存のアプローチとは対照的に、当社のアプローチはポリシーの解決における最適化コールの数を劇的に削減します。
  論文  参考訳（メタデータ） (2021-06-14T07:36:25Z)

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

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