論文の概要: A Provably-Efficient Model-Free Algorithm for Constrained Markov
Decision Processes
- arxiv url: http://arxiv.org/abs/2106.01577v1
- Date: Thu, 3 Jun 2021 03:53:27 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-04 12:19:21.816005
- Title: A Provably-Efficient Model-Free Algorithm for Constrained Markov
Decision Processes
- Title（参考訳）: 制約付きマルコフ決定過程に対する有理効率モデルフリーアルゴリズム
- Authors: Honghao Wei, Xin Liu, Lei Ying
- Abstract要約: 本稿では,制約付きマルコフ決定過程(CMDP)に対するモデルフリーでシミュレータフリーな強化学習アルゴリズムを提案する。
このアルゴリズムは、累積報酬のQ-関数、制約の累積効用Q-関数、累積制約違反を推定する仮想キューの3つの主要な成分を持つため、トリプルQと名付けられた。
- 参考スコア（独自算出の注目度）: 13.877420496703627
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper presents the first {\em model-free}, {\em simulator-free}
reinforcement learning algorithm for Constrained Markov Decision Processes
(CMDPs) with sublinear regret and zero constraint violation. The algorithm is
named Triple-Q because it has three key components: a Q-function (also called
action-value function) for the cumulative reward, a Q-function for the
cumulative utility for the constraint, and a virtual-Queue that
(over)-estimates the cumulative constraint violation. Under Triple-Q, at each
step, an action is chosen based on the pseudo-Q-value that is a combination of
the three Q values. The algorithm updates the reward and utility Q-values with
learning rates that depend on the visit counts to the corresponding (state,
action) pairs and are periodically reset. In the episodic CMDP setting,
Triple-Q achieves $\tilde{\cal O}\left(\frac{1 }{\delta}H^4
S^{\frac{1}{2}}A^{\frac{1}{2}}K^{\frac{4}{5}} \right)$ regret, where $K$ is the
total number of episodes, $H$ is the number of steps in each episode, $S$ is
the number of states, $A$ is the number of actions, and $\delta$ is Slater's
constant. Furthermore, Triple-Q guarantees zero constraint violation when $K$
is sufficiently large. Finally, the computational complexity of Triple-Q is
similar to SARSA for unconstrained MDPs and is computationally efficient.
- Abstract（参考訳）: 本稿では,制約付きマルコフ決定過程 (cmdps) に対する最初のモデルフリー, シミュレータフリーの強化学習アルゴリズムを提案する。
このアルゴリズムは、累積報酬のQ関数(アクション値関数とも呼ばれる)、制約の累積効用Q関数、累積制約違反を見積もる仮想キューという3つの重要な要素を持つため、トリプルQと名付けられた。
トリプルQでは、各ステップで、3つのQ値の組み合わせである擬似Q値に基づいてアクションが選択される。
アルゴリズムは、報酬と有用Q値を、訪問数に依存する学習率で更新し、対応する(状態、行動)ペアに周期的にリセットする。
エピソードCMDP設定では、Triple-Q は $\tilde{\cal O}\left(\frac{1 }{\delta}H^4 S^{\frac{1}{2}}A^{\frac{1}{2}}K^{\frac{4}{5}} \right)$ regret, where $K$ is the total number of episodes, $H$ is the number of steps in each episode, $S$ is the number of state, $A$ is the number of action, $\delta$ is Slater's constant。
さらに、Triple-Qは、$K$が十分に大きいときにゼロ制約違反を保証する。
最後に、Triple-Qの計算複雑性は制約のないMDPのSARSAと似ており、計算効率が良い。
関連論文リスト
- Computational Supremacy of Quantum Eigensolver by Extension of Optimized Binary Configurations [0.0]
我々は、D-Wave Quantum Annealer(D-Wave QA)に基づく量子固有解法を開発する。
このアプローチは、古典的コンピュータの導出を伴わない固有状態$vert psi rangle$を最適化するために反復的なQA測定を実行する。
提案したQEアルゴリズムは誤差の5倍の10～3$の正確な解を提供することを確認した。
論文 参考訳（メタデータ） (2024-06-05T15:19:53Z) - Average-Case Complexity of Tensor Decomposition for Low-Degree
Polynomials [93.59919600451487]
多くの統計的推論タスクにおいて「統計計算ギャップ」が発生する。
1つの成分が他の成分よりもわずかに大きいランダムオーダー3分解モデルを考える。
テンソルエントリは$ll n3/2$のとき最大成分を正確に推定できるが、$rgg n3/2$のとき失敗する。
論文 参考訳（メタデータ） (2022-11-10T00:40:37Z) - Reward-Mixing MDPs with a Few Latent Contexts are Learnable [75.17357040707347]
報酬混合マルコフ決定過程(RMMDP)におけるエピソード強化学習の検討
我々のゴールは、そのようなモデルにおける時間段階の累積報酬をほぼ最大化する、ほぼ最適に近いポリシーを学ぶことである。
論文 参考訳（メタデータ） (2022-10-05T22:52:00Z) - Polyak-Ruppert Averaged Q-Leaning is Statistically Efficient [90.14768299744792]
我々はPolyak-Ruppert 平均 Q-leaning (平均 Q-leaning) を用いた同期 Q-learning を$gamma$-discounted MDP で検討した。
繰り返し平均$barboldsymbolQ_T$に対して正規性を確立する。
要するに、我々の理論分析は、Q-Leaningの平均は統計的に効率的であることを示している。
論文 参考訳（メタデータ） (2021-12-29T14:47:56Z) - Tightening the Dependence on Horizon in the Sample Complexity of
Q-Learning [59.71676469100807]
この研究は、同期Q-ラーニングのサンプルの複雑さを、任意の$0varepsilon 1$に対して$frac|mathcalS| (1-gamma)4varepsilon2$の順序に絞る。
計算やストレージを余分に必要とせずに、高速なq-learningにマッチするvanilla q-learningの有効性を明らかにした。
論文 参考訳（メタデータ） (2021-02-12T14:22:05Z) - Model-Free Non-Stationary RL: Near-Optimal Regret and Applications in
Multi-Agent RL and Inventory Control [28.80743320843154]
非定常RLのための最初のモデルフリーアルゴリズムであるアッパー信頼境界を用いたリスタートQラーニング(RestartQ-UCB)を提案する。
我々は,情報理論的下限を$Omega(Sfrac13 Afrac13 Deltafrac13 Hfrac23 Tfrac23)$,非定常RLで最初の下限を設定すれば,アルゴリズムが最適であることを示す。
論文 参考訳（メタデータ） (2020-10-07T04:55:56Z) - Finite-Time Analysis for Double Q-learning [50.50058000948908]
二重Q-ラーニングのための非漸近的有限時間解析を初めて提供する。
同期と非同期の二重Q-ラーニングの両方が,グローバル最適化の$epsilon$-accurate近辺に収束することが保証されていることを示す。
論文 参考訳（メタデータ） (2020-09-29T18:48:21Z) - A Sample-Efficient Algorithm for Episodic Finite-Horizon MDP with
Constraints [8.849815837266977]
制約付きマルコフ決定プロセス(CMDP)は、シーケンシャルな意思決定問題を定式化する。
本稿では, 有限水平CMDPの線形計画法を利用して, 繰り返し楽観的な計画を立てるオンラインアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-09-23T19:30:46Z) - Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and
Variance Reduction [63.41789556777387]
非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。
Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
論文 参考訳（メタデータ） (2020-06-04T17:51:00Z) - Provably Efficient Model-Free Algorithm for MDPs with Peak Constraints [38.2783003051101]
本稿では,有限地平線における全報酬の最大化と,各エポックにおける制約を確率1で満たすため,エージェントがポリシーを選択する,制約付きマルコフ決定プロセス(PCMDP)について考察する。
そこで本研究では,PCMDP問題を制約のない問題に変換するモデルフリーアルゴリズムを提案し,Q-ラーニングに基づくアプローチを適用した。
論文 参考訳（メタデータ） (2020-03-11T23:23:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。