論文の概要: Learning Infinite-Horizon Average-Reward Markov Decision Processes with
Constraints
- arxiv url: http://arxiv.org/abs/2202.00150v1
- Date: Mon, 31 Jan 2022 23:52:34 GMT
- ステータス: 処理完了
- システム内更新日: 2022-02-02 14:39:11.136537
- Title: Learning Infinite-Horizon Average-Reward Markov Decision Processes with
Constraints
- Title(参考訳): 制約付き無限水平平均逆マルコフ決定過程の学習
- Authors: Liyu Chen, Rahul Jain, Haipeng Luo
- Abstract要約: 本研究では,無限水平平均回帰マルコフ決定過程(MDP)のコスト制約による後悔について検討する。
我々のアルゴリズムはエルゴディックMDPに対して$widetildeO(sqrtT)$ regret and constant constraint violationを保証します。
これらは、MDPをコスト制約で弱い通信を行うための最初の証明可能なアルゴリズムである。
- 参考スコア(独自算出の注目度): 39.715977181666766
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study regret minimization for infinite-horizon average-reward Markov
Decision Processes (MDPs) under cost constraints. We start by designing a
policy optimization algorithm with carefully designed action-value estimator
and bonus term, and show that for ergodic MDPs, our algorithm ensures
$\widetilde{O}(\sqrt{T})$ regret and constant constraint violation, where $T$
is the total number of time steps. This strictly improves over the algorithm of
(Singh et al., 2020), whose regret and constraint violation are both
$\widetilde{O}(T^{2/3})$. Next, we consider the most general class of weakly
communicating MDPs. Through a finite-horizon approximation, we develop another
algorithm with $\widetilde{O}(T^{2/3})$ regret and constraint violation, which
can be further improved to $\widetilde{O}(\sqrt{T})$ via a simple modification,
albeit making the algorithm computationally inefficient. As far as we know,
these are the first set of provable algorithms for weakly communicating MDPs
with cost constraints.
- Abstract(参考訳): 本研究では,無限水平平均逆マルコフ決定過程(MDP)のコスト制約による最小化について検討する。
まず、アクション値推定器とボーナス項を慎重に設計したポリシー最適化アルゴリズムを設計し、エルゴードmdpの場合、このアルゴリズムは$\widetilde{o}(\sqrt{t})$ regret and constant constraints violationを保証し、$t$は時間ステップの総数であることを示した。
これは(Singh et al., 2020)のアルゴリズムよりも厳密に改善され、その後悔と制約違反はともに$\widetilde{O}(T^{2/3})$である。
次に、弱通信型MDPの最も一般的なクラスについて考察する。
有限ホライズン近似により、このアルゴリズムを計算的に非効率にするために、$\widetilde{O}(T^{2/3})$後悔と制約違反を伴う別のアルゴリズムを開発し、さらに$\widetilde{O}(T^{2/3})$に改善することができる。
私たちが知る限り、これらのアルゴリズムは、コスト制約でMDPを弱めに通信するための最初の証明可能なアルゴリズムです。
関連論文リスト
- Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳(メタデータ) (2024-02-14T07:52:00Z) - Towards Optimal Regret in Adversarial Linear MDPs with Bandit Feedback [30.337826346496385]
線形マルコフ決定過程におけるオンライン強化学習について,敵対的損失と帯域幅フィードバックを用いて検討した。
既存の手法と比較して、後悔性能を向上させるアルゴリズムを2つ導入する。
論文 参考訳(メタデータ) (2023-10-17T19:43:37Z) - Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
我々は,損失関数が約1,300ドル以上のエピソードに対して任意に変化するような,敵対的決定過程(MDP)の学習を検討する。
本稿では,同じ設定で$tildemathcal O(K2/3)$に対する後悔を改善する2つのアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-01-30T14:37:21Z) - Counterfactual Optimism: Rate Optimal Regret for Stochastic Contextual
MDPs [48.98020692698762]
我々は, UC$3$RL アルゴリズムを用いて, 残酷な文脈的 MDP (CMDPs) を提案する。
我々のアルゴリズムは効率的な(効率的なオフライン回帰オラクルを仮定すると)、$widetildeO(H3 sqrtT |S| |A|(log (|mathcalF|/delta) + log (|mathcalP|/delta) )$ regret guarantee。
論文 参考訳(メタデータ) (2022-11-27T20:38:47Z) - Efficient Algorithms for Planning with Participation Constraints [74.74967476995572]
我々は[Zhang et al., 2022]に導入された参加制約を伴う計画の問題を考える。
この問題では、プリンシパルが決定プロセスのアクションを選択し、プリンシパルとエージェントの別々のユーティリティが生成される。
有限ホライズン設定では,これまでは$varepsilon$-approximationという付加値しか知られていなかった。
論文 参考訳(メタデータ) (2022-05-16T15:47:41Z) - Achieving Zero Constraint Violation for Constrained Reinforcement
Learning via Primal-Dual Approach [37.80609997145897]
強化学習は、環境と対話しながらシーケンシャルな決定を行う必要があるアプリケーションで広く使われている。
決定要件がいくつかの安全制約を満たすことを含むと、問題はより難しくなります。
CMDP問題をモデルのない方法で解き、$epsilon$-optimal cumulative rewardを$epsilon$-factible Policyで達成することができる。
ここでの重要な疑問は、制約違反ゼロで$epsilon$-optimal cumulative rewardを達成できるかどうかである。
論文 参考訳(メタデータ) (2021-09-13T21:27:03Z) - A Provably Efficient Algorithm for Linear Markov Decision Process with
Low Switching Cost [53.968049198926444]
スイッチングコストの低い線形MDPのための最初のアルゴリズムを提案する。
このアルゴリズムは$widetildeoleft(sqrtd3h4kright)$ regretをほぼ最適の$oleft(d hlog kright)$グローバルスイッチングコストで達成する。
論文 参考訳(メタデータ) (2021-01-02T18:41:27Z) - Learning Infinite-horizon Average-reward MDPs with Linear Function
Approximation [44.374427255708135]
線形関数近似を用いた無限水平平均逆設定でマルコフ決定過程を学習するための新しいアルゴリズムを開発した。
まず,最適$widetildeO(sqrtT)$ regretの計算非効率アルゴリズムを提案する。
次に,逆線形包帯から着想を得て,$widetildeO(sqrtT)$ regretのアルゴリズムを新たに開発した。
論文 参考訳(メタデータ) (2020-07-23T08:23:44Z) - Provably Efficient Model-Free Algorithm for MDPs with Peak Constraints [38.2783003051101]
本稿では,有限地平線における全報酬の最大化と,各エポックにおける制約を確率1で満たすため,エージェントがポリシーを選択する,制約付きマルコフ決定プロセス(PCMDP)について考察する。
そこで本研究では,PCMDP問題を制約のない問題に変換するモデルフリーアルゴリズムを提案し,Q-ラーニングに基づくアプローチを適用した。
論文 参考訳(メタデータ) (2020-03-11T23:23:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。