論文の概要: On Query-efficient Planning in MDPs under Linear Realizability of the
Optimal State-value Function
- arxiv url: http://arxiv.org/abs/2102.02049v1
- Date: Wed, 3 Feb 2021 13:23:15 GMT
- ステータス: 処理完了
- システム内更新日: 2021-02-04 17:51:41.985539
- Title: On Query-efficient Planning in MDPs under Linear Realizability of the
Optimal State-value Function
- Title（参考訳）: 最適状態値関数の線形実現性を考慮したMDPのクエリ効率プランニングについて
- Authors: Gellert Weisz, Philip Amortila, Barnab\'as Janzer, Yasin
Abbasi-Yadkori, Nan Jiang, Csaba Szepesv\'ari
- Abstract要約: 固定水平マルコフ決定過程(MDP)における局所的計画の問題点を生成モデルを用いて考察する。
最近の下界は、最適ポリシーの作用値関数が線形に実現可能である場合の関連する問題は指数的なクエリ数を必要とすることを証明している。
本研究では,アクションセットが小さい場合,ポリ$(H, d)$学習が(状態値関数の実現可能性を持つ)可能であることを確かめる。
- 参考スコア（独自算出の注目度）: 14.205660708980988
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the problem of local planning in fixed-horizon Markov Decision
Processes (MDPs) with a generative model under the assumption that the optimal
value function lies in the span of a feature map that is accessible through the
generative model. As opposed to previous work where linear realizability of all
policies was assumed, we consider the significantly relaxed assumption of a
single linearly realizable (deterministic) policy. A recent lower bound
established that the related problem when the action-value function of the
optimal policy is linearly realizable requires an exponential number of
queries, either in H (the horizon of the MDP) or d (the dimension of the
feature mapping). Their construction crucially relies on having an
exponentially large action set. In contrast, in this work, we establish that
poly$(H, d)$ learning is possible (with state value function realizability)
whenever the action set is small (i.e. O(1)). In particular, we present the
TensorPlan algorithm which uses poly$((dH/\delta)^A)$ queries to find a
$\delta$-optimal policy relative to any deterministic policy for which the
value function is linearly realizable with a parameter from a fixed radius ball
around zero. This is the first algorithm to give a polynomial query complexity
guarantee using only linear-realizability of a single competing value function.
Whether the computation cost is similarly bounded remains an interesting open
question. The upper bound is complemented by a lower bound which proves that in
the infinite-horizon episodic setting, planners that achieve constant
suboptimality need exponentially many queries, either in the dimension or the
number of actions.
- Abstract（参考訳）: 生成モデルを用いた固定正則マルコフ決定プロセス(MDP)における局所計画の問題点を,生成モデルを通じてアクセス可能な特徴マップのスパンに最適値関数が存在することを前提として検討する。
すべてのポリシーの線形実現可能性を仮定する以前の研究とは対照的に、単一の線形実現可能な(決定論的)ポリシーの非常に緩やかな仮定を考える。
最近の下界は、最適ポリシーの作用値関数が線形実現可能である場合に、H(MDPの地平線)またはd(特徴写像の次元)の指数的な数のクエリを必要とすることを証明した。
彼らの構成は指数関数的に大きなアクションセットを持つことに大きく依存している。
対照的に、本研究では、アクション集合が小さい場合(すなわち、)にpoly$(h, d)$学習が可能(状態値関数実現可能性)となることを定めている。
O(1))。
特に,ポリ$((dH/\delta)^A)$クエリを用いて,値関数がゼロ付近の固定半径球からのパラメータと線形に実現可能な任意の決定的ポリシに対して,$\delta$-optimal Policyを求めるTensorPlanアルゴリズムを提案する。
これは、単一の競合値関数の線形実現性のみを使用して多項式クエリの複雑性を保証する最初のアルゴリズムである。
計算コストが同じように有界であるかどうかは、まだ興味深い疑問である。
上界は下界で補われ、無限ホリゾンエピソディック設定では、一定の部分最適化性を達成するプランナーは、次元やアクションの数において指数関数的に多くのクエリを必要とする。
関連論文リスト
- Confident Natural Policy Gradient for Local Planning in $q_π$-realizable Constrained MDPs [44.69257217086967]
制約付きマルコフ決定プロセス(CMDP)フレームワークは、安全性や他の重要な目的を課すための重要な強化学習アプローチとして出現する。
本稿では,線形関数近似が$q_pi$-realizabilityで与えられる学習問題に対処する。
論文 参考訳（メタデータ） (2024-06-26T17:57:13Z) - Provably Efficient Reinforcement Learning via Surprise Bound [66.15308700413814]
本稿では,一般値関数近似を用いた効率の良い強化学習アルゴリズムを提案する。
本アルゴリズムは, 線形設定と疎高次元線形設定の両方に適用した場合に, 合理的な後悔境界を達成できる。
論文 参考訳（メタデータ） (2023-02-22T20:21:25Z) - Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision
Processes [80.89852729380425]
そこで本研究では,最小限の最小残差である$tilde O(dsqrtH3K)$を計算効率よく実現したアルゴリズムを提案する。
我々の研究は線形 MDP を用いた最適 RL に対する完全な答えを提供する。
論文 参考訳（メタデータ） (2022-12-12T18:58:59Z) - On Instance-Dependent Bounds for Offline Reinforcement Learning with
Linear Function Approximation [80.86358123230757]
本稿では,Bootstrapped and Constrained Pessimistic Value Iteration (BCP-VI) というアルゴリズムを提案する。
部分的なデータカバレッジの仮定の下で、BCP-VI は最適な Q-値関数に正のギャップがあるときに、オフライン RL に対して $tildemathcalO(frac1K)$ の高速レートを得る。
これらは、アダプティブデータからの線形関数近似を持つオフラインRLに対してそれぞれ、最初の$tildemathcalO(frac1K)$boundと絶対零部分最適境界である。
論文 参考訳（メタデータ） (2022-11-23T18:50:44Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - TensorPlan and the Few Actions Lower Bound for Planning in MDPs under
Linear Realizability of Optimal Value Functions [0.0]
我々は,オンラインプランニングにおけるミニマックスクエリの複雑さを,固定水平決定プロセスにおける生成モデルを用いて検討する。
A=Omega(min(d1/4,H1/2)) が指数的に大きい下界を持つことを示す。
論文 参考訳（メタデータ） (2021-10-05T17:42:46Z) - Efficient Local Planning with Linear Function Approximation [27.90696655434707]
線形関数近似とシミュレータを用いたクエリと計算効率のよい計画アルゴリズムについて検討する。
本稿では,モンテカルロ最小二乗政策反復(MC-LSPI)というアルゴリズムを提案する。
我々の研究の技術的貢献の1つは、仮想ポリシーアルゴリズムを利用した新しい証明手法の導入である。
論文 参考訳（メタデータ） (2021-08-12T04:56:33Z) - Nearly Optimal Regret for Learning Adversarial MDPs with Linear Function
Approximation [92.3161051419884]
我々は、敵対的な報酬と完全な情報フィードバックで有限正方体エピソディックマルコフ決定プロセスのための強化学習を研究します。
我々は、$tildeO(dHsqrtT)$ regretを達成できることを示し、$H$はエピソードの長さである。
また、対数因子までの$tildeOmega(dHsqrtT)$の値が一致することを証明する。
論文 参考訳（メタデータ） (2021-02-17T18:54:08Z) - Provably Efficient Safe Exploration via Primal-Dual Policy Optimization [105.7510838453122]
制約付きマルコフ決定過程(CMDP)を用いた安全強化学習(SRL)問題について検討する。
本稿では,関数近似設定において,安全な探索を行うCMDPの効率の良いオンラインポリシー最適化アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-03-01T17:47:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。