論文の概要: 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を弱めに通信するための最初の証明可能なアルゴリズムです。

関連論文リスト

• Best-of-Both-Worlds Policy Optimization for CMDPs with Bandit Feedback [34.7178680288326]
  Stradi et al.(2024) は、マルコフ決定過程に制約のある最初のベスト・オブ・ボス・ワールドズ・アルゴリズムを提案した。 本稿では,CMDPにおける帯域幅フィードバックを用いたベスト・オブ・ワールドズ・アルゴリズムを提案する。 本アルゴリズムは政策最適化手法に基づいており, 占有率に基づく手法よりも効率的である。
  論文  参考訳（メタデータ） (2024-10-03T07:44:40Z)
• Achieving Tractable Minimax Optimal Regret in Average Reward MDPs [19.663336027878408]
  我々は,$widetildemathrmO(sqrtmathrmsp(h*) S A T)$のミニマックス最適後悔を伴う最初の抽出可能なアルゴリズムを提案する。 注目すべきは、我々のアルゴリズムは$mathrmsp(h*)$に関する事前情報を必要としないことである。
  論文  参考訳（メタデータ） (2024-06-03T11:53:44Z)
• Reinforcement Learning for Infinite-Horizon Average-Reward Linear MDPs via Approximation by Discounted-Reward MDPs [16.49229317664822]
  線形MDPを用いた無限水平平均逆強化学習について検討する。 本稿では,$widetildeO(sqrtT)$の後悔境界が,計算効率のよいアルゴリズムを実現することを提案する。
  論文  参考訳（メタデータ） (2024-05-23T20:58:33Z)
• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。 我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。 我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
  論文  参考訳（メタデータ） (2024-05-10T09:58:47Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
  我々は,損失関数が約1,300ドル以上のエピソードに対して任意に変化するような,敵対的決定過程(MDP)の学習を検討する。 本稿では,同じ設定で$tildemathcal O(K2/3)$に対する後悔を改善する2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-30T14:37:21Z)
• Efficient Algorithms for Planning with Participation Constraints [74.74967476995572]
  我々は[Zhang et al., 2022]に導入された参加制約を伴う計画の問題を考える。 この問題では、プリンシパルが決定プロセスのアクションを選択し、プリンシパルとエージェントの別々のユーティリティが生成される。 有限ホライズン設定では,これまでは$varepsilon$-approximationという付加値しか知られていなかった。
  論文  参考訳（メタデータ） (2022-05-16T15:47:41Z)
• 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)

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

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