論文の概要: Computational-Statistical Gaps in Reinforcement Learning

• arxiv url: http://arxiv.org/abs/2202.05444v1
• Date: Fri, 11 Feb 2022 04:48:35 GMT
• ステータス: 処理完了
• システム内更新日: 2022-02-14 14:24:27.602358
• Title: Computational-Statistical Gaps in Reinforcement Learning
• Title（参考訳）: 強化学習における計算統計的ギャップ
• Authors: Daniel Kane, Sihan Liu, Shachar Lovett, Gaurav Mahajan
• Abstract要約: そこでは,CNF式を決定論的遷移,動作の定数数,低次元線形最適値関数を備えたMDP仮説に変換する。 この結果は線形関数近似を用いた強化学習における最初の計算統計的ギャップを示す。
• 参考スコア（独自算出の注目度）: 23.517741855454044
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Reinforcement learning with function approximation has recently achieved tremendous results in applications with large state spaces. This empirical success has motivated a growing body of theoretical work proposing necessary and sufficient conditions under which efficient reinforcement learning is possible. From this line of work, a remarkably simple minimal sufficient condition has emerged for sample efficient reinforcement learning: MDPs with optimal value function $V^*$ and $Q^*$ linear in some known low-dimensional features. In this setting, recent works have designed sample efficient algorithms which require a number of samples polynomial in the feature dimension and independent of the size of state space. They however leave finding computationally efficient algorithms as future work and this is considered a major open problem in the community. In this work, we make progress on this open problem by presenting the first computational lower bound for RL with linear function approximation: unless NP=RP, no randomized polynomial time algorithm exists for deterministic transition MDPs with a constant number of actions and linear optimal value functions. To prove this, we show a reduction from Unique-Sat, where we convert a CNF formula into an MDP with deterministic transitions, constant number of actions and low dimensional linear optimal value functions. This result also exhibits the first computational-statistical gap in reinforcement learning with linear function approximation, as the underlying statistical problem is information-theoretically solvable with a polynomial number of queries, but no computationally efficient algorithm exists unless NP=RP. Finally, we also prove a quasi-polynomial time lower bound under the Randomized Exponential Time Hypothesis.
• Abstract（参考訳）: 関数近似による強化学習は、最近、大きな状態空間を持つアプリケーションで素晴らしい結果を得ている。 この実証的な成功は、効率的な強化学習が可能な必要十分条件を提唱する理論的な研究の展開を動機付けている。 最適値関数 $V^*$ および $Q^*$ を持つ MDP は、いくつかの既知の低次元特徴において線形である。 この設定において、最近の研究は、多くのサンプル多項式を必要とするサンプル効率の良いアルゴリズムを設計し、状態空間のサイズに依存している。 しかし、彼らは計算効率のよいアルゴリズムを将来の研究として発見し続けており、これはコミュニティにとって大きなオープンな問題だと考えられている。 そこで本研究では, rl に対する最初の計算下限を線形関数近似で提示し, 決定論的遷移 mdps に対して, np=rp がない限り, 一定数の作用数と線形最適値関数を持つ無作為多項式時間アルゴリズムは存在しない。 これを証明するために、一意satからの還元を示し、cnf公式を決定論的遷移、定数のアクション数、低次元の線形最適値関数を持つmdpに変換する。 この結果は線形関数近似による強化学習における最初の計算統計的ギャップも示しており、基礎となる統計問題は多項式数で情報理論的に解くことができるが、np=rpでなければ計算効率のよいアルゴリズムは存在しない。 最後に、ランダム化指数時間仮説の下で準多項時間下限が証明される。

関連論文リスト

• Sample and Oracle Efficient Reinforcement Learning for MDPs with Linearly-Realizable Value Functions [10.225358400539719]
  本稿では,線形作用が特徴写像に一般化される決定法(MDP)の効率的な強化アルゴリズムを提案する。 具体的には、この設定において、最適に近いポリシーを効率的に見つける新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-09-07T14:38:05Z)
• The Power of Resets in Online Reinforcement Learning [73.64852266145387]
  ローカルシミュレータアクセス(あるいはローカルプランニング)を用いたオンライン強化学習を通してシミュレータのパワーを探求する。 カバー性が低いMPPは,Qstar$-realizabilityのみのサンプル効率で学習可能であることを示す。 ローカルシミュレーターアクセス下では, 悪名高いExogenous Block MDP問題が抽出可能であることを示す。
  論文  参考訳（メタデータ） (2024-04-23T18:09:53Z)
• Efficient Model-Free Exploration in Low-Rank MDPs [76.87340323826945]
  低ランクマルコフ決定プロセスは、関数近似を持つRLに対して単純だが表現力のあるフレームワークを提供する。 既存のアルゴリズムは、(1)計算的に抽出可能であるか、または(2)制限的な統計的仮定に依存している。 提案手法は,低ランクMPPの探索のための最初の実証可能なサンプル効率アルゴリズムである。
  論文  参考訳（メタデータ） (2023-07-08T15:41:48Z)
• Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processes [80.89852729380425]
  そこで本研究では,最小限の最小残差である$tilde O(dsqrtH3K)$を計算効率よく実現したアルゴリズムを提案する。 我々の研究は線形 MDP を用いた最適 RL に対する完全な答えを提供する。
  論文  参考訳（メタデータ） (2022-12-12T18:58:59Z)
• Estimating a potential without the agony of the partition function [5.994412766684842]
  サンプルが与えられたギブス密度関数を推定することは、計算統計学と統計学において重要な問題である。 最大A-Posteriori (MAP) 推定器に基づく代替手法を提案する。
  論文  参考訳（メタデータ） (2022-08-19T16:27:02Z)
• On efficient algorithms for computing near-best polynomial approximations to high-dimensional, Hilbert-valued functions from limited samples [1.0650780147044159]
  スパース近似は、限られたサンプルから滑らかで高次元の関数を近似するのに欠かせないものとなっている。 本稿では,指数的あるいは代数的収束率を主張するアルゴリズムと理論的保証と,サンプリング,アルゴリズム的,物理的離散化誤差に対する頑健性を紹介する。
  論文  参考訳（メタデータ） (2022-03-25T20:56:07Z)
• Online Model Selection for Reinforcement Learning with Function Approximation [50.008542459050155]
  我々は、$tildeO(L5/6 T2/3)$ regretで最適な複雑性に適応するメタアルゴリズムを提案する。 また、メタアルゴリズムは、インスタンス依存の後悔境界を著しく改善することを示す。
  論文  参考訳（メタデータ） (2020-11-19T10:00:54Z)
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces [208.67848059021915]
  強化学習のコアにおける探索・探索トレードオフについて検討する。 特に、関数クラス $mathcalF$ の複雑さが関数の複雑さを特徴づけていることを証明する。 私たちの後悔の限界はエピソードの数とは無関係です。
  論文  参考訳（メタデータ） (2020-11-09T18:32:22Z)
• Reinforcement Learning with General Value Function Approximation: Provably Efficient Approach via Bounded Eluder Dimension [124.7752517531109]
  一般値関数近似を用いた効率の良い強化学習アルゴリズムを確立する。 我々のアルゴリズムは、$d$が複雑性測度である場合、$widetildeO(mathrmpoly(dH)sqrtT)$の後悔の限界を達成することを示す。 我々の理論は線形値関数近似によるRLの最近の進歩を一般化し、環境モデルに対する明示的な仮定をしない。
  論文  参考訳（メタデータ） (2020-05-21T17:36:09Z)

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

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