論文の概要: Near-Optimal Reinforcement Learning with Multi-Step Transition Lookahead

• arxiv url: http://arxiv.org/abs/2609.11807v1
• Date: Thu, 10 Sep 2026 16:58:21 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-11 23:53:35.452003
• Title: Near-Optimal Reinforcement Learning with Multi-Step Transition Lookahead
• Title（参考訳）: 多段階遷移ルックアヘッドを用いた準最適強化学習
• Abstract要約: 本研究は, エージェントがどの状態に訪問するかを観察し, 行動の連続を観察できるような, トランジション・ルックアヘッドを用いた強化学習について検討する。 ルックアヘッドは達成可能な性能を大幅に向上させることができるが、マルチステップ遷移ルックアヘッドによる最適計画はNPハードである。
• 参考スコア（独自算出の注目度）: 26.599514971653615
• 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. Although look-ahead can substantially improve achievable performance, it is known that optimal planning with multi-step transition look-ahead is NP-hard, but this hardness was established using discount factors arbitrarily close to one. It was therefore unknown whether the problem remains hard for any discount factor, and whether near-optimal planning can nevertheless be performed efficiently. We resolve both questions. First, we show that for every fixed rational discount factor ($γ\in(0,1)$), exact planning remains NP-hard. Second, we introduce a randomized polynomial-time approximation scheme for every fixed look-ahead depth. We then extend our approach to unknown transitions and stochastic rewards using optimism and variance-adaptive confidence bounds. The resulting algorithm achieves cumulative regret whose leading term matches classical tabular discounted RL up to logarithmic factors. Thus, although exact planning with transition look-ahead is NP-hard, efficient near-optimal planning and learning remain possible.
• Abstract（参考訳）: そこで, エージェントは, アクションの行程を決定する前に, どのような状態が訪問されるかを観察することができる。 ルックアヘッドは達成可能な性能を大幅に向上させることができるが,マルチステップ遷移ルックアヘッドを用いた最適計画がNPハードであることが知られている。 したがって、この問題はいかなる割引要因に対しても困難なままであり、しかしながら、最適に近い計画が効率的に実施できるかどうかは不明である。 どちらの問題も解決する。 まず、固定された有理割引係数 (γ\in(0,1)$) に対して、正確な計画がNPハードであることを示す。 第二に、固定されたルックアヘッド深度毎にランダム化された多項式時間近似スキームを導入する。 次に、楽観主義と分散適応的信頼境界を用いて、未知の遷移と確率的報酬にアプローチを拡張します。 得られたアルゴリズムは、先行項が古典的な表付き割引RLと対数因子に一致した累積後悔を実現する。 したがって、トランジション・ルックアヘッドによる正確な計画はNPハードであるが、効率的な準最適計画と学習は引き続き可能である。

関連論文リスト

• Near-Optimal Primal-Dual Algorithm for Learning Linear Mixture CMDPs with Adversarial Rewards [0.8984888893275712]
  有限-水平線形混合制約マルコフ決定過程における安全強化学習について検討する。 本稿では, 後悔と制約違反境界を実現するプリミティブ・デュアルポリシー最適化アルゴリズムを提案する。 これは、線形混合CMDPと逆効果を持つ最初の証明可能な効率のよいアルゴリズムである。
  論文  参考訳（メタデータ） (2026-03-29T21:51:33Z)
• On the hardness of RL with Lookahead [34.030963310653874]
  そこで, エージェントは, アクションの行程を決定する前に, 任意の$ell$アクションの実行時にどの状態が訪問されるかを観察することができる。 このような情報は達成可能な性能を大幅に向上させることができるが、最適にこの情報を使用すると、潜在的に禁止的な計算コストがかかることを示す。
  論文  参考訳（メタデータ） (2025-10-22T08:47:18Z)
• Optimistically Optimistic Exploration for Provably Efficient Infinite-Horizon Reinforcement and Imitation Learning [13.429541377715296]
  無限水平割引線形マルコフ決定過程において, 速度-最適後悔保証を実現するための計算効率のよいアルゴリズムを提案する。 正規化された近似的動的プログラミングスキームと組み合わせると、結果のアルゴリズムは、$tildemathcalO (sqrtd3 (1 - gamma)- 7 / 2 T)$, $T$ はサンプル遷移の総数、$gamma in (0,1)$ は割引係数、$d$ は特徴次元を後悔する。
  論文  参考訳（メタデータ） (2025-02-19T17:32:35Z)
• Model-Based Reinforcement Learning with Multinomial Logistic Function Approximation [10.159501412046508]
  マルコフ決定過程(MDP)におけるモデルベース強化学習(RL)について検討する。 我々は,多項ロジスティックモデルにより状態遷移が与えられるMPPに対して,証明可能な効率のよいRLアルゴリズムを確立する。 我々の知る限りでは、証明可能な保証付き多項ロジスティック関数近似を用いたモデルベースRLアルゴリズムとしてはこれが初めてである。
  論文  参考訳（メタデータ） (2022-12-27T16:25:09Z)
• 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)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。 本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
  論文  参考訳（メタデータ） (2021-06-02T22:03:36Z)
• Provably Breaking the Quadratic Error Compounding Barrier in Imitation Learning, Optimally [58.463668865380946]
  状態空間 $mathcalS$ を用いたエピソードマルコフ決定過程 (MDPs) における模擬学習の統計的限界について検討する。 rajaraman et al (2020) におけるmdアルゴリズムを用いた準最適性に対する上限 $o(|mathcals|h3/2/n)$ を定式化する。 Omega(H3/2/N)$ $mathcalS|geq 3$ であるのに対して、未知の遷移条件はよりシャープレートに悩まされる。
  論文  参考訳（メタデータ） (2021-02-25T15:50:19Z)
• Nearly Optimal Regret for Learning Adversarial MDPs with Linear Function Approximation [92.3161051419884]
  我々は、敵対的な報酬と完全な情報フィードバックで有限正方体エピソディックマルコフ決定プロセスのための強化学習を研究します。 我々は、$tildeO(dHsqrtT)$ regretを達成できることを示し、$H$はエピソードの長さである。 また、対数因子までの$tildeOmega(dHsqrtT)$の値が一致することを証明する。
  論文  参考訳（メタデータ） (2021-02-17T18:54:08Z)
• Upper Confidence Primal-Dual Reinforcement Learning for CMDP with Adversarial Loss [145.54544979467872]
  マルコフ決定過程(CMDP)に対するオンライン学習の検討 本稿では,遷移モデルから標本化した軌跡のみを必要とする,新しいEmphupper confidence primal-dualアルゴリズムを提案する。 我々の分析では、ラグランジュ乗算過程の新たな高確率ドリフト解析を、高信頼強化学習の記念後悔解析に組み入れている。
  論文  参考訳（メタデータ） (2020-03-02T05:02:23Z)

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

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