論文の概要: Confident Approximate Policy Iteration for Efficient Local Planning in $q^\pi$-realizable MDPs

• arxiv url: http://arxiv.org/abs/2210.15755v1
• Date: Thu, 27 Oct 2022 20:19:31 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-31 15:05:00.276175
• Title: Confident Approximate Policy Iteration for Efficient Local Planning in $q^\pi$-realizable MDPs
• Title（参考訳）: q^\pi$-realizable MDPにおける効率的なローカルプランニングのための信頼度近似政策イテレーション
• Authors: Gell\'ert Weisz and Andr\'as Gy\"orgy and Tadashi Kozuno and Csaba Szepesv\'ari
• Abstract要約: 我々は、$gamma$-discounted Markov決定過程における近似動的プログラミングについて考察する。 私たちの最初のコントリビューションは、CAPI(Confident Approximate Policy Iteration)と呼ばれる、新しいバージョンの近似ポリシーイテレーション(API)です。 CAPIは、最適エラーバウンドスケーリングによる決定論的定常ポリシーを、有効地平線$H$と最悪の近似誤差$epsilon$の積と線形に計算する。
• 参考スコア（独自算出の注目度）: 2.5652904661855076
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider approximate dynamic programming in $\gamma$-discounted Markov decision processes and apply it to approximate planning with linear value-function approximation. Our first contribution is a new variant of Approximate Policy Iteration (API), called Confident Approximate Policy Iteration (CAPI), which computes a deterministic stationary policy with an optimal error bound scaling linearly with the product of the effective horizon $H$ and the worst-case approximation error $\epsilon$ of the action-value functions of stationary policies. This improvement over API (whose error scales with $H^2$) comes at the price of an $H$-fold increase in memory cost. Unlike Scherrer and Lesner [2012], who recommended computing a non-stationary policy to achieve a similar improvement (with the same memory overhead), we are able to stick to stationary policies. This allows for our second contribution, the application of CAPI to planning with local access to a simulator and $d$-dimensional linear function approximation. As such, we design a planning algorithm that applies CAPI to obtain a sequence of policies with successively refined accuracies on a dynamically evolving set of states. The algorithm outputs an $\tilde O(\sqrt{d}H\epsilon)$-optimal policy after issuing $\tilde O(dH^4/\epsilon^2)$ queries to the simulator, simultaneously achieving the optimal accuracy bound and the best known query complexity bound, while earlier algorithms in the literature achieve only one of them. This query complexity is shown to be tight in all parameters except $H$. These improvements come at the expense of a mild (polynomial) increase in memory and computational costs of both the algorithm and its output policy.
• Abstract（参考訳）: 我々は、$\gamma$-discounted Markov決定過程における近似動的プログラミングを考察し、線形値関数近似を用いた近似計画に適用する。 私たちの最初の貢献は、slanced approximation policy iteration(capi)と呼ばれる新しいタイプの近似ポリシーイテレーション(api)です。これは、効果的なホライズン$h$と最悪の場合の近似エラー$\epsilon$の積と線形にスケーリングする最適なエラー境界を持つ決定論的定常ポリシーを計算します。 api(エラーは$h^2$でスケールする)に対するこの改善は、メモリコストが$h$-foldの値で増加する。 Scherrer と Lesner [2012] が同様の改善(メモリオーバーヘッドが同じ)を達成するために非定常ポリシーの計算を推奨しているのとは異なり、我々は定常ポリシーに固執することができる。 これにより、シミュレータへのローカルアクセスと$d$次元線形関数近似によるプランニングへのCAPIの適用が可能になります。 そこで我々は,CAPIを適用した計画アルゴリズムを設計し,動的に進化する状態の集合上で連続的に改良されたアキュラシーを持つ一連のポリシーを得る。 このアルゴリズムは、$\tilde O(dH^4/\epsilon^2)$クエリをシミュレータに出力した後、$\tilde O(\sqrt{d}H\epsilon)$-Optimal Policyを出力し、同時に最適な精度境界と既知のクエリ複雑性境界を達成する。 このクエリの複雑さは、$H$を除くすべてのパラメータで厳密である。 これらの改善は、アルゴリズムと出力ポリシーの両方のメモリと計算コストの軽度(ポリノミカル)の増加を犠牲にしている。

関連論文リスト

• Narrowing the Gap between Adversarial and Stochastic MDPs via Policy Optimization [11.11876897168701]
  本稿では,次数$tildemathcalO(mathrmpoly(H)sqrtSAT)$の残差を求めるアルゴリズムを提案する。 提案したアルゴリズムと分析は、占有対策によって与えられる典型的なツールを完全に回避する。
  論文  参考訳（メタデータ） (2024-07-08T08:06:45Z)
• 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)
• Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
  我々は,損失関数が約1,300ドル以上のエピソードに対して任意に変化するような,敵対的決定過程(MDP)の学習を検討する。 本稿では,同じ設定で$tildemathcal O(K2/3)$に対する後悔を改善する2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-30T14:37:21Z)
• Maximum-Likelihood Inverse Reinforcement Learning with Finite-Time Guarantees [56.848265937921354]
  逆強化学習(IRL)は報酬関数と関連する最適ポリシーを回復することを目的としている。 IRLの多くのアルゴリズムは本質的にネスト構造を持つ。 我々は、報酬推定精度を損なわないIRLのための新しいシングルループアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-10-04T17:13:45Z)
• Optimistic Policy Optimization is Provably Efficient in Non-stationary MDPs [45.6318149525364]
  非定常線形カーネルマルコフ決定過程(MDP)におけるエピソード強化学習(RL)の研究 本稿では,$underlinetextp$eriodically $underlinetextr$estarted $underlinetexto$ptimistic $underlinetextp$olicy $underlinetexto$ptimization algorithm (PROPO)を提案する。
  論文  参考訳（メタデータ） (2021-10-18T02:33:20Z)
• Implicitly Regularized RL with Implicit Q-Values [42.87920755961722]
  Q$関数は多くの強化学習(RL)アルゴリズムにおいて中心的な量であり、RLエージェントは(ソフト)グレーディポリシーに従って振る舞う。 対数政治と値関数の和として、暗黙的に$Q$-関数をパラメータ化することを提案する。 我々は,大規模アクション空間に適した実用的な非政治的深部RLアルゴリズムを導出し,ポリシーと$Q$値とのソフトマックス関係を強制する。
  論文  参考訳（メタデータ） (2021-08-16T12:20:47Z)
• Improved Regret Bound and Experience Replay in Regularized Policy Iteration [22.621710838468097]
  無限ホライゾンマルコフ決定過程(mdps)における学習アルゴリズムを関数近似を用いて検討する。 まず、ほぼ同一の仮定の下で、Politexアルゴリズムの後悔解析を$O(T3/4)$から$O(sqrtT)$にシャープできることを示す。 その結果、計算効率の良いアルゴリズムに対して、最初の高い確率の$o(sqrtt)$ regretバウンドが得られる。
  論文  参考訳（メタデータ） (2021-02-25T00:55:07Z)
• Softmax Policy Gradient Methods Can Take Exponential Time to Converge [60.98700344526674]
  Softmax Policy gradient(PG)メソッドは、現代の強化学習におけるポリシー最適化の事実上の実装の1つです。 ソフトマックス PG 法は、$mathcalS|$ および $frac11-gamma$ の観点から指数時間で収束できることを実証する。
  論文  参考訳（メタデータ） (2021-02-22T18:56:26Z)
• Provably Efficient Safe Exploration via Primal-Dual Policy Optimization [105.7510838453122]
  制約付きマルコフ決定過程(CMDP)を用いた安全強化学習(SRL)問題について検討する。 本稿では,関数近似設定において,安全な探索を行うCMDPの効率の良いオンラインポリシー最適化アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-03-01T17:47:03Z)

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

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