論文の概要: Provably Efficient Model-Free Constrained RL with Linear Function Approximation

• arxiv url: http://arxiv.org/abs/2206.11889v1
• Date: Thu, 23 Jun 2022 17:54:31 GMT
• ステータス: 処理完了
• システム内更新日: 2022-06-24 12:42:19.695272
• Title: Provably Efficient Model-Free Constrained RL with Linear Function Approximation
• Title（参考訳）: 線形関数近似を用いた効率的モデルフリー制約付きrl
• Authors: Arnob Ghosh, Xingyu Zhou, Ness Shroff
• Abstract要約: 我々は,大規模システムにおいても,サブリニア後悔とサブリニア制約違反を実現するための,最初のモデルフリーシミュレータフリーアルゴリズムを開発した。 本結果は,標準LSVI-UCBアルゴリズムの新たな適応により達成される。
• 参考スコア（独自算出の注目度）: 4.060731229044571
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the constrained reinforcement learning problem, in which an agent aims to maximize the expected cumulative reward subject to a constraint on the expected total value of a utility function. In contrast to existing model-based approaches or model-free methods accompanied with a `simulator', we aim to develop the first model-free, simulator-free algorithm that achieves a sublinear regret and a sublinear constraint violation even in large-scale systems. To this end, we consider the episodic constrained Markov decision processes with linear function approximation, where the transition dynamics and the reward function can be represented as a linear function of some known feature mapping. We show that $\tilde{\mathcal{O}}(\sqrt{d^3H^3T})$ regret and $\tilde{\mathcal{O}}(\sqrt{d^3H^3T})$ constraint violation bounds can be achieved, where $d$ is the dimension of the feature mapping, $H$ is the length of the episode, and $T$ is the total number of steps. Our bounds are attained without explicitly estimating the unknown transition model or requiring a simulator, and they depend on the state space only through the dimension of the feature mapping. Hence our bounds hold even when the number of states goes to infinity. Our main results are achieved via novel adaptations of the standard LSVI-UCB algorithms. In particular, we first introduce primal-dual optimization into the LSVI-UCB algorithm to balance between regret and constraint violation. More importantly, we replace the standard greedy selection with respect to the state-action function in LSVI-UCB with a soft-max policy. This turns out to be key in establishing uniform concentration for the constrained case via its approximation-smoothness trade-off. We also show that one can achieve an even zero constraint violation while still maintaining the same order with respect to $T$.
• Abstract（参考訳）: 本研究では,実効関数の期待総値に対する制約による期待累積報酬を最大化することを目的とした,制約付き強化学習問題について検討する。 モデルベースアプローチやモデルフリーな手法に‘simulator’が付随する手法とは対照的に,大規模システムにおいてもサブリニア後悔とサブリニア制約違反を実現する,モデルフリーでシミュレータフリーなアルゴリズムを開発することを目指している。 この目的のために,線形関数近似を用いたマルコフ決定過程を考察し,遷移ダイナミクスと報酬関数を既知の特徴写像の線形関数として表現することができる。 我々は、$\tilde{\mathcal{O}}(\sqrt{d^3H^3T})$ regret and $\tilde{\mathcal{O}}(\sqrt{d^3H^3T})$ constraint violation boundsを達成できることを示し、$d$は特徴写像の次元であり、$H$はエピソードの長さであり、$T$はステップの総数である。 我々の境界は、未知の遷移モデルを明示的に推定したり、シミュレータを必要とすることなく達成され、それらは特徴マッピングの次元を通してのみ状態空間に依存する。 したがって、状態の数が無限になるときでさえ、我々の境界は保たれる。 本研究の主な成果は,標準LSVI-UCBアルゴリズムの新規適応によるものである。 特に,後悔と制約違反のバランスをとるために,LSVI-UCBアルゴリズムに初期双対最適化を導入する。 さらに、LSVI-UCBにおける状態作用関数に対する標準グリーディ選択をソフトマックスポリシーで置き換える。 これは、その近似-滑らか性トレードオフを通じて制約されたケースの均一な濃度を確立する上で鍵となる。 また、$t$に関して同じ順序を維持しながら、ゼロの制約違反をも達成できることも示しています。

関連論文リスト

• Settling Constant Regrets in Linear Markov Decision Processes [57.34287648914407]
  強化学習(RL)における絶え間ない後悔の保証について検討する。 我々は不特定線形マルコフ決定過程(MDP)に対するアルゴリズムCert-LSVI-UCBを導入する。 Cert-LSVI-UCB は $tildemathcalO(d3H5/Delta)$ の累積後悔と高い確率を持つ MDP に対して、$zeta$ が $tildemathcalO(Delta / (sqrtd) 以下であることを仮定する。
  論文  参考訳（メタデータ） (2024-04-16T17:23:19Z)
• Horizon-Free Regret for Linear Markov Decision Processes [92.02082223856479]
  最近の一連の研究は、強化学習における残念な境界が(ほぼ)計画的地平から独立していることを示している。 我々は、人気のある線形マルコフ決定過程(MDP)設定に対して、最初の地平面自由境界を与える。 遷移モデルを明示的に推定し、不均一な値関数を計算する先行研究とは対照的に、直接値関数と信頼集合を推定する。
  論文  参考訳（メタデータ） (2024-03-15T23:50:58Z)
• Reinforcement Learning with General Utilities: Simpler Variance Reduction and Large State-Action Space [17.366915676628867]
  一般用途における強化学習の課題について考察する。 我々のアルゴリズムは、$tildemathcalO(epsilon-3)$と$tildemathcalO(epsilon-2)$サンプル複雑度を達成する。
  論文  参考訳（メタデータ） (2023-06-02T18:16:35Z)
• Minimax Optimal Quantization of Linear Models: Information-Theoretic Limits and Efficient Algorithms [59.724977092582535]
  測定から学習した線形モデルの定量化の問題を考える。 この設定の下では、ミニマックスリスクに対する情報理論の下限を導出する。 本稿では,2層ReLUニューラルネットワークに対して,提案手法と上界を拡張可能であることを示す。
  論文  参考訳（メタデータ） (2022-02-23T02:39:04Z)
• First-Order Regret in Reinforcement Learning with Linear Function Approximation: A Robust Estimation Approach [57.570201404222935]
  我々は,大規模状態空間を用いた強化学習において,$mathcalO(sqrtV_1star K)$として,後悔のスケーリングが得られることを示す。 この結果を得るためには,少なくとも2乗推定に基づく既存手法は不十分であることを示す。
  論文  参考訳（メタデータ） (2021-12-07T00:29:57Z)
• Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning [52.76230802067506]
  漸進的強化学習における後悔を最小限に抑えるために,新しいモデルフリーアルゴリズムを提案する。 提案アルゴリズムは、2つのQ-ラーニングシーケンスの助けを借りて、初期設定された参照更新ルールを用いる。 初期の分散還元法の設計原理は、他のRL設定とは独立した関心を持つかもしれない。
  論文  参考訳（メタデータ） (2021-10-09T21:13:48Z)
• Primal-dual Learning for the Model-free Risk-constrained Linear Quadratic Regulator [0.8629912408966145]
  リスク対応コントロールは、予期せぬイベントに取り組むことを約束しながら、既知のダイナミックなモデルを必要とする。 本稿では,線形システムに着目したリスク対応制御系を学習するためのモデルフレームワークを提案する。
  論文  参考訳（メタデータ） (2020-11-22T04:40:15Z)
• Model-based Reinforcement Learning for Continuous Control with Posterior Sampling [10.91557009257615]
  連続状態空間における強化学習(PSRL)のためのモデルベース後方サンプリングについて検討した。 MPC-PSRLはモデルに基づく後部サンプリングアルゴリズムであり,行動選択のためのモデル予測制御を行う。
  論文  参考訳（メタデータ） (2020-11-20T21:00:31Z)
• Online DR-Submodular Maximization with Stochastic Cumulative Constraints [17.660958043781154]
  線形長期制約を伴うオンライン連続DR-サブモジュラーを考える。 オンラインラグランジアンFrank-Wolfe (OLFW) アルゴリズムは、この種のオンライン問題を解く。
  論文  参考訳（メタデータ） (2020-05-29T17:55:42Z)
• Provably Efficient Safe Exploration via Primal-Dual Policy Optimization [105.7510838453122]
  制約付きマルコフ決定過程(CMDP)を用いた安全強化学習(SRL)問題について検討する。 本稿では,関数近似設定において,安全な探索を行うCMDPの効率の良いオンラインポリシー最適化アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-03-01T17:47:03Z)

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

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