論文の概要: Computational Hardness of Reinforcement Learning with Partial $q^π$-Realizability

• arxiv url: http://arxiv.org/abs/2510.21888v1
• Date: Fri, 24 Oct 2025 01:18:49 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-28 15:28:14.637979
• Title: Computational Hardness of Reinforcement Learning with Partial $q^π$-Realizability
• Title（参考訳）: 部分$q^π$-Realizabilityを用いた強化学習の計算困難性
• Authors: Shayan Karimi, Xiaoqi Tan,
• Abstract要約: 本稿では, 線形関数近似系における強化学習の計算複雑性を部分的に$qpi$-realizability と呼ぶ。 この設定で$epsilon$-optimal Policyを学習することは、計算的に困難であることを示す。 我々の結果は$q*$-realizability(英語版)を反映し、$Pi$が最適ポリシーを超えて拡張された場合でも計算困難が持続することを示す。
• 参考スコア（独自算出の注目度）: 1.6328866317851185
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper investigates the computational complexity of reinforcement learning in a novel linear function approximation regime, termed partial $q^{\pi}$-realizability. In this framework, the objective is to learn an $\epsilon$-optimal policy with respect to a predefined policy set $\Pi$, under the assumption that all value functions for policies in $\Pi$ are linearly realizable. The assumptions of this framework are weaker than those in $q^{\pi}$-realizability but stronger than those in $q^*$-realizability, providing a practical model where function approximation naturally arises. We prove that learning an $\epsilon$-optimal policy in this setting is computationally hard. Specifically, we establish NP-hardness under a parameterized greedy policy set (argmax) and show that - unless NP = RP - an exponential lower bound (in feature vector dimension) holds when the policy set contains softmax policies, under the Randomized Exponential Time Hypothesis. Our hardness results mirror those in $q^*$-realizability and suggest computational difficulty persists even when $\Pi$ is expanded beyond the optimal policy. To establish this, we reduce from two complexity problems, $\delta$-Max-3SAT and $\delta$-Max-3SAT(b), to instances of GLinear-$\kappa$-RL (greedy policy) and SLinear-$\kappa$-RL (softmax policy). Our findings indicate that positive computational results are generally unattainable in partial $q^{\pi}$-realizability, in contrast to $q^{\pi}$-realizability under a generative access model.
• Abstract（参考訳）: 本稿では,新しい線形関数近似系における強化学習の計算複雑性を,部分$q^{\pi}$-realizability と呼ぶ。 このフレームワークでは、$\Pi$ のポリシーに対するすべての値関数が線形に実現可能であるという前提の下で、事前定義されたポリシーセット $\Pi$ について $\epsilon$-optimal Policy を学ぶことが目的である。 このフレームワークの仮定は、$q^{\pi}$-実現可能性の仮定よりも弱いが、$q^*$-実現可能性の仮定よりも強い。 この設定で$\epsilon$-optimal Policyを学習することは、計算的に困難であることを示す。 具体的には、パラメータ化された欲求ポリシーセット(argmax)の下でNP硬度を確立し、NP = RP がなければ(特徴ベクトル次元における)指数的な下界は、ポリシーセットがソフトマックスポリシーを含むとき、ランダム化された指数時間仮説の下で成り立つことを示す。 我々の硬さは、$q^*$-realizabilityのものを反映し、$\Pi$が最適ポリシーを超えて拡張された場合でも計算困難が持続することを示す。 これを確立するために、$\delta$-Max-3SAT と $\delta$-Max-3SAT(b) という2つの複雑性問題から GLinear-$\kappa$-RL (greedy policy) と SLinear-$\kappa$-RL (softmax policy) のインスタンスへ還元する。 この結果から, 部分的な$q^{\pi}$-realizabilityでは, 生成的アクセスモデルでは$q^{\pi}$-realizabilityとは対照的に, 正の計算結果は一般に達成不可能であることが示唆された。

関連論文リスト

• Confident Natural Policy Gradient for Local Planning in $q_π$-realizable Constrained MDPs [44.69257217086967]
  制約付きマルコフ決定プロセス(CMDP)フレームワークは、安全性や他の重要な目的を課すための重要な強化学習アプローチとして出現する。 本稿では,線形関数近似が$q_pi$-realizabilityで与えられる学習問題に対処する。
  論文  参考訳（メタデータ） (2024-06-26T17:57:13Z)
• Reaching Goals is Hard: Settling the Sample Complexity of the Stochastic Shortest Path [106.37656068276902]
  本稿では,最短経路(SSP)問題において,$epsilon$-optimal Policyを学習する際のサンプル複雑性について検討する。 学習者が生成モデルにアクセスできる場合、複雑性境界を導出する。 我々は、$S$状態、$A$アクション、最小コスト$c_min$、およびすべての状態に対する最適ポリシーの最大期待コストを持つ最悪のSSPインスタンスが存在することを示す。
  論文  参考訳（メタデータ） (2022-10-10T18:34:32Z)
• Nearly Optimal Policy Optimization with Stable at Any Time Guarantee [53.155554415415445]
  citetshani 2020optimisticのポリシーベースのメソッドは、$tildeO(sqrtSAH3K + sqrtAH4K)$である。$S$は状態の数、$A$はアクションの数、$H$は地平線、$K$はエピソードの数、$sqrtSH$は情報理論の下限の$tildeOmega(sqrtSAH)と比べてギャップがある。
  論文  参考訳（メタデータ） (2021-12-21T01:54:17Z)
• Towards Instance-Optimal Offline Reinforcement Learning with Pessimism [34.54294677335518]
  我々は、未知マルコフ決定過程(MDP)における報酬最大化ポリシーの学習を目標とするオフライン強化学習(オフラインRL)問題について検討する。 本研究では、適応悲観的値反復法(APVI)アルゴリズムを分析し、[Oleft(sum_h=1Hsum_s_h,a_hdpistar_h(s_h,a_h)sqrtfracmathrmmathrmVar_]とほぼ一致する準最適上限を導出する。
  論文  参考訳（メタデータ） (2021-10-17T01:21:52Z)
• Agnostic Reinforcement Learning with Low-Rank MDPs and Rich Observations [79.66404989555566]
  我々は、リッチな観測空間を持つより現実的な非依存的RLの設定と、近似的ポリシーを含まないような固定されたポリシーのクラス$Pi$を考える。 我々は,MDPの階数$d$の誤差が有界な設定のためのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-06-22T03:20:40Z)
• The Curse of Passive Data Collection in Batch Reinforcement Learning [82.6026077420886]
  高い利害関係のアプリケーションでは、アクティブな実験は危険すぎると考えられ、データはしばしば受動的に収集される。 バンディットやパッシブ、アクティブなデータ収集などの単純な場合も同様に効果的であるが、制御された状態のシステムからデータを集める場合、パッシブサンプリングの価格ははるかに高い。
  論文  参考訳（メタデータ） (2021-06-18T07:54:23Z)
• Online Sub-Sampling for Reinforcement Learning with General Function Approximation [111.01990889581243]
  本稿では,RLアルゴリズムによって収集されたデータポイントの情報取得量を測定する,効率的なオンラインサブサンプリングフレームワークを確立する。 複雑性バウンド関数クラスを持つ値ベースのメソッドの場合、$proptooperatornamepolylog(K)$ timesに対してのみポリシーを更新する必要がある。 少なくとも$Omega(K)$倍のポリシーを更新する既存のアプローチとは対照的に、当社のアプローチはポリシーの解決における最適化コールの数を劇的に削減します。
  論文  参考訳（メタデータ） (2021-06-14T07:36:25Z)
• Improved Sample Complexity for Incremental Autonomous Exploration in MDPs [132.88757893161699]
  我々は $epsilon$-optimal 目標条件付きポリシーのセットを学び、$ L$ ステップ内で段階的に到達可能なすべての状態を達成します。 DisCoは、コストに敏感な最短経路問題に対して$epsilon/c_min$-optimalポリシーを返すことができる最初のアルゴリズムです。
  論文  参考訳（メタデータ） (2020-12-29T14:06:09Z)

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

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