論文の概要: Provably Efficient RL under Episode-Wise Safety in Constrained MDPs with Linear Function Approximation
- arxiv url: http://arxiv.org/abs/2502.10138v2
- Date: Tue, 18 Feb 2025 02:30:30 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-02-19 10:42:21.926400
- Title: Provably Efficient RL under Episode-Wise Safety in Constrained MDPs with Linear Function Approximation
- Title(参考訳): 線形関数近似を用いた拘束型MDPにおけるエピソードワイズ安全下におけるRLの有効性
- Authors: Toshinori Kitamura, Arnob Ghosh, Tadashi Kozuno, Wataru Kumagai, Kazumi Kasaura, Kenta Hoshino, Yohei Hosoe, Yutaka Matsuo,
- Abstract要約: 制約決定過程(CMDP)における強化学習問題について検討する。
本稿では,リニアCMDPに対するRLアルゴリズムを提案する。
その結果,近年の線形CMDPアルゴリズムでは,制約に違反するか,指数計算コストに悪影響を及ぼす結果が得られた。
- 参考スコア(独自算出の注目度): 24.299769025346368
- License:
- Abstract: We study the reinforcement learning (RL) problem in a constrained Markov decision process (CMDP), where an agent explores the environment to maximize the expected cumulative reward while satisfying a single constraint on the expected total utility value in every episode. While this problem is well understood in the tabular setting, theoretical results for function approximation remain scarce. This paper closes the gap by proposing an RL algorithm for linear CMDPs that achieves $\tilde{\mathcal{O}}(\sqrt{K})$ regret with an episode-wise zero-violation guarantee. Furthermore, our method is computationally efficient, scaling polynomially with problem-dependent parameters while remaining independent of the state space size. Our results significantly improve upon recent linear CMDP algorithms, which either violate the constraint or incur exponential computational costs.
- Abstract(参考訳): 制約付きマルコフ決定過程(CMDP)における強化学習(RL)問題について検討し,各エピソードにおいて期待される全実用価値の制約を満たしつつ,予測累積報酬を最大化するためにエージェントが環境を探索する。
この問題は表の設定ではよく理解されているが、関数近似の理論的結果は乏しいままである。
本稿では, 線形CMDPに対するRLアルゴリズムの提案により, エピソード単位のゼロ違反保証により, $\tilde{\mathcal{O}}(\sqrt{K})$ regretを実現することにより, ギャップを埋める。
さらに,本手法は計算効率が高く,問題に依存したパラメータを多項式的にスケーリングするが,状態空間サイズには依存しない。
その結果,近年の線形CMDPアルゴリズムでは,制約に違反するか,指数計算コストに悪影響を及ぼす結果が得られた。
関連論文リスト
- Sample and Oracle Efficient Reinforcement Learning for MDPs with Linearly-Realizable Value Functions [10.225358400539719]
本稿では,線形作用が特徴写像に一般化される決定法(MDP)の効率的な強化アルゴリズムを提案する。
具体的には、この設定において、最適に近いポリシーを効率的に見つける新しいアルゴリズムを提案する。
論文 参考訳(メタデータ) (2024-09-07T14:38:05Z) - A safe exploration approach to constrained Markov decision processes [7.036452261968767]
無限水平制限マルコフ決定過程(CMDP)について考察する。
目標は、期待される累積的制約の対象となる累積的報酬を最大化する最適なポリシーを見つけることである。
安全クリティカルなシステムのオンライン学習におけるCMDPの適用により、モデルフリーでシミュレータフリーなアルゴリズムの開発に焦点をあてる。
論文 参考訳(メタデータ) (2023-12-01T13:16:39Z) - Provably Efficient CVaR RL in Low-rank MDPs [58.58570425202862]
リスクに敏感な強化学習(RL)について検討する。
本稿では, CVaR RLにおける探索, 搾取, 表現学習の相互作用のバランスをとるための, 新たなアッパー信頼境界(UCB)ボーナス駆動アルゴリズムを提案する。
提案アルゴリズムは,各エピソードの長さが$H$,アクション空間が$A$,表現の次元が$d$であるような,エプシロン$最適CVaRのサンプル複雑性を実現する。
論文 参考訳(メタデータ) (2023-11-20T17:44:40Z) - Anytime-Constrained Reinforcement Learning [6.981971551979697]
制約付きマルコフ決定過程(cMDP)を任意の制約で導入・研究する。
累積コストを付加した最適決定主義的政策が存在することを示す。
非自明な概略的ポリシーの計算は一般にNPハードであることが示される。
論文 参考訳(メタデータ) (2023-11-09T16:51:26Z) - Provably Efficient Model-Free Algorithms for Non-stationary CMDPs [10.930095238723327]
非定常制約マルコフ決定過程におけるモデルフリー強化学習アルゴリズムについて検討した。
非定常環境では、累積変動が一定の変動予算を超えない限り、報酬、ユーティリティ関数、遷移カーネルは時間とともに任意に変化する。
本稿では,非定常CMDPに対するサブ線形後悔と制約違反をゼロとする,モデルフリーでシミュレータフリーなRLアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-03-10T06:33:38Z) - Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision
Processes [80.89852729380425]
そこで本研究では,最小限の最小残差である$tilde O(dsqrtH3K)$を計算効率よく実現したアルゴリズムを提案する。
我々の研究は線形 MDP を用いた最適 RL に対する完全な答えを提供する。
論文 参考訳(メタデータ) (2022-12-12T18:58:59Z) - Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov
Decision Processes [61.11090361892306]
Reward-free reinforcement learning (RL) は、エージェントが探索中に報酬関数にアクセスできないような環境を考える。
この分離は線形MDPの設定には存在しないことを示す。
我々は$d$次元線形 MDP における報酬のない RL に対する計算効率の良いアルゴリズムを開発した。
論文 参考訳(メタデータ) (2022-01-26T22:09:59Z) - Settling the Horizon-Dependence of Sample Complexity in Reinforcement
Learning [82.31436758872715]
我々は,環境相互作用の$O(1)$のエピソードのみを用いて,同一のPAC保証を実現するアルゴリズムを開発した。
値関数と有限水平マルコフ決定過程の接続を確立する。
論文 参考訳(メタデータ) (2021-11-01T00:21:24Z) - Parallel Stochastic Mirror Descent for MDPs [72.75921150912556]
無限水平マルコフ決定過程(MDP)における最適政策学習の問題を考える。
リプシッツ連続関数を用いた凸プログラミング問題に対してミラー・ディクセントの変種が提案されている。
このアルゴリズムを一般の場合において解析し,提案手法の動作中に誤差を蓄積しない収束率の推定値を得る。
論文 参考訳(メタデータ) (2021-02-27T19:28:39Z) - Provably Efficient Safe Exploration via Primal-Dual Policy Optimization [105.7510838453122]
制約付きマルコフ決定過程(CMDP)を用いた安全強化学習(SRL)問題について検討する。
本稿では,関数近似設定において,安全な探索を行うCMDPの効率の良いオンラインポリシー最適化アルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-03-01T17:47:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。