論文の概要: On the hardness of RL with Lookahead

• arxiv url: http://arxiv.org/abs/2510.19372v1
• Date: Wed, 22 Oct 2025 08:47:18 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-25 03:08:15.434647
• Title: On the hardness of RL with Lookahead
• Title（参考訳）: Lookahead を用いた RL の硬さについて
• Authors: Corentin Pla, Hugo Richard, Marc Abeille, Nadav Merlis, Vianney Perchet,
• Abstract要約: そこで, エージェントは, アクションの行程を決定する前に, 任意の$ell$アクションの実行時にどの状態が訪問されるかを観察することができる。 このような情報は達成可能な性能を大幅に向上させることができるが、最適にこの情報を使用すると、潜在的に禁止的な計算コストがかかることを示す。
• 参考スコア（独自算出の注目度）: 34.030963310653874
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study reinforcement learning (RL) with transition look-ahead, where the agent may observe which states would be visited upon playing any sequence of $\ell$ actions before deciding its course of action. While such predictive information can drastically improve the achievable performance, we show that using this information optimally comes at a potentially prohibitive computational cost. Specifically, we prove that optimal planning with one-step look-ahead ($\ell=1$) can be solved in polynomial time through a novel linear programming formulation. In contrast, for $\ell \geq 2$, the problem becomes NP-hard. Our results delineate a precise boundary between tractable and intractable cases for the problem of planning with transition look-ahead in reinforcement learning.
• Abstract（参考訳）: そこで, エージェントは, アクションの行程を決定する前に, どのような状態が訪問されるかを観察することができる。 このような予測情報は、達成可能な性能を大幅に向上させることができるが、この情報を使用することが、潜在的に禁忌な計算コストに最適であることを示す。 具体的には、一段階のルックアヘッド($\ell=1$)による最適計画が、新しい線形プログラミングの定式化によって多項式時間で解けることを示す。 対照的に、$\ell \geq 2$ の場合、問題はNPハードになる。 本研究は,強化学習におけるトランジッション・ルック・アヘッドによる計画問題に対して,抽出可能なケースと難解なケースの正確な境界を定式化したものである。

関連論文リスト

• Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processes [80.89852729380425]
  そこで本研究では,最小限の最小残差である$tilde O(dsqrtH3K)$を計算効率よく実現したアルゴリズムを提案する。 我々の研究は線形 MDP を用いた最適 RL に対する完全な答えを提供する。
  論文  参考訳（メタデータ） (2022-12-12T18:58:59Z)
• Human-in-the-loop: Provably Efficient Preference-based Reinforcement Learning with General Function Approximation [107.54516740713969]
  本研究は,RL(Human-in-the-loop reinforcement learning)を軌道的嗜好で検討する。 各ステップで数値的な報酬を受ける代わりに、エージェントは人間の監督者から軌道上のペアよりも優先される。 一般関数近似を用いたPbRLの楽観的モデルベースアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-05-23T09:03:24Z)
• An Experimental Design Perspective on Model-Based Reinforcement Learning [73.37942845983417]
  環境からの状態遷移を観察するのは費用がかかる。 標準RLアルゴリズムは通常、学習するために多くの観測を必要とする。 本稿では,マルコフ決定過程について,状態-作用対がどの程度の情報を提供するかを定量化する獲得関数を提案する。
  論文  参考訳（メタデータ） (2021-12-09T23:13:57Z)
• Nearly Optimal Regret for Learning Adversarial MDPs with Linear Function Approximation [92.3161051419884]
  我々は、敵対的な報酬と完全な情報フィードバックで有限正方体エピソディックマルコフ決定プロセスのための強化学習を研究します。 我々は、$tildeO(dHsqrtT)$ regretを達成できることを示し、$H$はエピソードの長さである。 また、対数因子までの$tildeOmega(dHsqrtT)$の値が一致することを証明する。
  論文  参考訳（メタデータ） (2021-02-17T18:54:08Z)
• Efficient Learning in Non-Stationary Linear Markov Decision Processes [17.296084954104415]
  非定常線形(低ランク)マルコフ決定過程(MDP)におけるエピソード強化学習の研究 OPT-WLSVI は最小二乗の重み付け値に基づく楽観的なモデルフリーのアルゴリズムであり、指数重み付けを用いて過去のデータをスムーズに忘れる。 我々のアルゴリズムは、各時点で最高のポリシーと競合するときに、$d$$$widetildemathcalO(d5/4H2 Delta1/4 K3/4)$で上限付けられた後悔を実現する。
  論文  参考訳（メタデータ） (2020-10-24T11:02:45Z)

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

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