論文の概要: Exponential Hardness of Reinforcement Learning with Linear Function Approximation

• arxiv url: http://arxiv.org/abs/2302.12940v1
• Date: Sat, 25 Feb 2023 00:19:49 GMT
• ステータス: 処理完了
• システム内更新日: 2023-02-28 19:54:17.149475
• Title: Exponential Hardness of Reinforcement Learning with Linear Function Approximation
• Title（参考訳）: 線形関数近似を用いた強化学習の指数硬度
• Authors: Daniel Kane, Sihan Liu, Shachar Lovett, Gaurav Mahajan, Csaba Szepesv\'ari, Gell\'ert Weisz
• Abstract要約: 指数時間仮説に基づく線形強化学習において,特徴・地平線で指数関数的な計算下界を示す。 また、地平線依存に最適化された下界が$exp(sqrtH)$の最もよく知られた上界とほぼ一致することを示す。
• 参考スコア（独自算出の注目度）: 20.066210529358177
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A fundamental question in reinforcement learning theory is: suppose the optimal value functions are linear in given features, can we learn them efficiently? This problem's counterpart in supervised learning, linear regression, can be solved both statistically and computationally efficiently. Therefore, it was quite surprising when a recent work \cite{kane2022computational} showed a computational-statistical gap for linear reinforcement learning: even though there are polynomial sample-complexity algorithms, unless NP = RP, there are no polynomial time algorithms for this setting. In this work, we build on their result to show a computational lower bound, which is exponential in feature dimension and horizon, for linear reinforcement learning under the Randomized Exponential Time Hypothesis. To prove this we build a round-based game where in each round the learner is searching for an unknown vector in a unit hypercube. The rewards in this game are chosen such that if the learner achieves large reward, then the learner's actions can be used to simulate solving a variant of 3-SAT, where (a) each variable shows up in a bounded number of clauses (b) if an instance has no solutions then it also has no solutions that satisfy more than (1-$\epsilon$)-fraction of clauses. We use standard reductions to show this 3-SAT variant is approximately as hard as 3-SAT. Finally, we also show a lower bound optimized for horizon dependence that almost matches the best known upper bound of $\exp(\sqrt{H})$.
• Abstract（参考訳）: 強化学習理論の基本的な質問は: 与えられた特徴において最適値関数が線形であると仮定すると、それらを効率的に学べるだろうか? 教師付き学習におけるこの問題の対応する線形回帰は、統計的にも計算的にも効率的に解くことができる。 したがって、最近の研究 \cite{kane2022computational} が線形強化学習の計算統計的ギャップを示したとき、非常に驚きであった: 多項式サンプル複雑性アルゴリズムがあるにもかかわらず、NP = RP がなければ、この設定に多項式時間アルゴリズムは存在しない。 本研究では,Randomized Exponential Time hypothesisに基づく線形強化学習において,特徴次元と地平線で指数的に指数関数的な計算下界を示すために,それらの結果に基づいて構築する。 これを証明するために,学習者が未知のベクトルをユニットハイパーキューブで探索するラウンドベースゲームを構築した。 このゲームの報酬は、学習者が大きな報酬を得た場合、学習者の行動が3-SATの変種をシミュレートするために使用できるように選択される。 (a)各変数が有界な節数で現れること (b) インスタンスに解がなければ、節の(1-$\epsilon$)-フラクションを満足する解も存在しない。 この3-SAT変種は3-SATとほぼ同程度硬いことを示すために,標準的な縮小法を用いている。 最後に、地平線依存に最適化された下限が、最もよく知られた$\exp(\sqrt{H})$とほぼ一致することを示す。

関連論文リスト

• Polynomial-Time Solutions for ReLU Network Training: A Complexity Classification via Max-Cut and Zonotopes [70.52097560486683]
  我々は、ReLUネットワークの近似の難しさがマックス・カッツ問題の複雑さを反映しているだけでなく、特定の場合において、それと完全に一致することを証明した。 特に、$epsilonleqsqrt84/83-1approx 0.006$とすると、目的値に関して相対誤差$epsilon$でReLUネットワーク対象の近似グローバルデータセットを見つけることはNPハードであることが示される。
  論文  参考訳（メタデータ） (2023-11-18T04:41:07Z)
• Exploring and Learning in Sparse Linear MDPs without Computationally Intractable Oracles [39.10180309328293]
  本稿では,特徴選択の観点から線形MDPを再考する。 我々の主な成果は、この問題に対する最初のアルゴリズムである。 コンベックスプログラミングによって効率よく計算できることを示す。
  論文  参考訳（メタデータ） (2023-09-18T03:35:48Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• Computational-Statistical Gaps in Reinforcement Learning [23.517741855454044]
  そこでは,CNF式を決定論的遷移,動作の定数数,低次元線形最適値関数を備えたMDP仮説に変換する。 この結果は線形関数近似を用いた強化学習における最初の計算統計的ギャップを示す。
  論文  参考訳（メタデータ） (2022-02-11T04:48:35Z)
• Optimal Gradient-based Algorithms for Non-concave Bandit Optimization [76.57464214864756]
  この研究は、未知の報酬関数が非可逆であるようなバンドイット問題の大群を考察する。 我々のアルゴリズムは、非常に一般化されたゼロ階最適化のパラダイムに基づいている。 標準的な楽観的アルゴリズムは次元因子によって準最適であることを示す。
  論文  参考訳（メタデータ） (2021-07-09T16:04:24Z)
• Randomized Exploration for Reinforcement Learning with General Value Function Approximation [122.70803181751135]
  本稿では,ランダム化最小二乗値反復(RLSVI)アルゴリズムに着想を得たモデルレス強化学習アルゴリズムを提案する。 提案アルゴリズムは,スカラーノイズを用いたトレーニングデータを簡易に摂動させることにより,探索を促進する。 我々はこの理論を、既知の困難な探査課題にまたがる実証的な評価で補完する。
  論文  参考訳（メタデータ） (2021-06-15T02:23:07Z)
• Learning from Survey Propagation: a Neural Network for MAX-E-$3$-SAT [0.0]
  本稿では,最大3-Stisfiability (MAX-E-$3$-SAT) 問題に対して$Theta(N)$で近似解を計算するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-12-10T07:59:54Z)
• 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)

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

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