論文の概要: Learning Infinite-Horizon Average-Reward CMDPs via State Augmentation

• arxiv url: http://arxiv.org/abs/2609.39093v1
• Date: Wed, 30 Sep 2026 06:31:55 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-01 18:57:27.288599
• Title: Learning Infinite-Horizon Average-Reward CMDPs via State Augmentation
• Title（参考訳）: 状態拡張による無限水平平均逆CMDPの学習
• Abstract要約: 本稿では, 無限水平平均逆制約マルコフ決定過程(CMDP)について, 弱い通信仮定の下で検討する。 計算効率のよい最初のアルゴリズムを提案し、高い確率で$widetildemathcalO(sqrtT)$ regretと累積制約違反を実現する。
• 参考スコア（独自算出の注目度）: 0.8984888893275712
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study infinite-horizon average-reward constrained Markov decision processes (CMDPs) under the weakly communicating assumption. Existing high-probability guarantees for this setting either require computationally inefficient algorithms or have suboptimal dependence on the number of interactions $T$. We propose, to the best of our knowledge, the first computationally efficient algorithm that achieves $\widetilde{\mathcal{O}}(\sqrt{T})$ regret and cumulative constraint violation with high probability in the tabular setting. The $\sqrt{T}$ dependence is optimal up to logarithmic factors. Our approach incorporates cumulative constraint violation into the state and defines a reshaped reward through differences of a Huber potential. The added state determines the penalty on further violations while the reward function remains fixed on the augmented state space. Since the added state has known deterministic dynamics, only the original transition kernel needs to be estimated. The bounded slope of the Huber potential keeps the per-step reward bounded, and the potential differences telescope to relate the reshaped return to the original cumulative reward and the terminal potential. These properties allow us to apply finite-horizon approximation and optimistic value iteration with clipping, as used in unconstrained average-reward MDPs, without worsening the regret rate in $T$.
• Abstract（参考訳）: 本稿では, 無限水平平均逆制約マルコフ決定過程(CMDP)について, 弱い通信仮定の下で検討する。 この設定の既存の高確率保証は、計算的に非効率なアルゴリズムを必要とするか、相互作用の数に最適な依存を持つかのいずれかである。 我々は、我々の知る限り、表の設定において高い確率で、後悔と累積的制約違反を伴って$\widetilde{\mathcal{O}}(\sqrt{T})を達成した最初の計算効率の良いアルゴリズムを提案する。 $\sqrt{T}$ 依存は対数因子に最適である。 我々のアプローチでは、累積的制約違反を状態に含み、ハマーポテンシャルの差によるリフォーム報酬を定義する。 追加状態は、追加状態空間上で報酬関数が固定されている間、さらなる違反に対するペナルティを決定する。 加算状態には決定論的ダイナミクスが知られているため、元の遷移カーネルのみを推定する必要がある。 ハマーポテンシャルの有界勾配はステップ当たりの報酬を有界に保ち、変形したリターンを元の累積報酬と終端電位に関連付ける電位差望遠鏡である。 これらの特性により, クリッピングによる有限水平近似と楽観的な値反復を, 制限のない平均回帰MDPで用いることができ, 後悔率を$T$で悪化させることなく適用することができる。

関連論文リスト

• Constrained Online Learning with Noisy Constraint Values [55.29259818039367]
  一般的な実現可能性の下では、我々のLEDGERアルゴリズムは、期待される損失$O(sqrt T)と期待される予算違反$O(sqrtTlog(eT))を達成します。 スレーター条件、フィードバックチャネル間の独立性、絶対的制約値境界は不要である。
  論文  参考訳（メタデータ） (2026-09-07T01:38:41Z)
• Risk-Sensitive Reinforcement Learning with Smoothed Quantile Objectives [2.153824429735596]
  モデルに基づく楽観的学習アルゴリズムを開発し、遷移カーネルの信頼セットと低バッファの量子化基準を用いて計画する。 チューリング時間短縮の下で, 正確な点量子化評価と, 正確な低バッファ化量子化評価がPPハードであることを証明する。
  論文  参考訳（メタデータ） (2026-08-23T05:41:32Z)
• Near-Optimal Primal-Dual Algorithm for Learning Linear Mixture CMDPs with Adversarial Rewards [0.8984888893275712]
  有限-水平線形混合制約マルコフ決定過程における安全強化学習について検討する。 本稿では, 後悔と制約違反境界を実現するプリミティブ・デュアルポリシー最適化アルゴリズムを提案する。 これは、線形混合CMDPと逆効果を持つ最初の証明可能な効率のよいアルゴリズムである。
  論文  参考訳（メタデータ） (2026-03-29T21:51:33Z)
• Provably Efficient Algorithms for S- and Non-Rectangular Robust MDPs with General Parameterization [85.91302339486673]
  我々は、s-正方形および非正方形不確実性集合の下で、一般的な政策パラメータ化を伴うロバストマルコフ決定過程(RMDP)について検討する。 無限状態空間に拡張する一般政策パラメタライゼーションに対する新しいリプシッツ・リプシッツ・スムースネス特性を証明した。 本研究では,S-正方形不確かさに対する勾配降下アルゴリズムと非正方形不確かさに対するFrank-Wolfeアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2026-02-11T21:44:20Z)
• Maximum-Likelihood Inverse Reinforcement Learning with Finite-Time Guarantees [56.848265937921354]
  逆強化学習(IRL)は報酬関数と関連する最適ポリシーを回復することを目的としている。 IRLの多くのアルゴリズムは本質的にネスト構造を持つ。 我々は、報酬推定精度を損なわないIRLのための新しいシングルループアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-10-04T17:13:45Z)
• Provably Efficient Model-Free Constrained RL with Linear Function Approximation [4.060731229044571]
  我々は,大規模システムにおいても,サブリニア後悔とサブリニア制約違反を実現するための,最初のモデルフリーシミュレータフリーアルゴリズムを開発した。 本結果は,標準LSVI-UCBアルゴリズムの新たな適応により達成される。
  論文  参考訳（メタデータ） (2022-06-23T17:54:31Z)
• Softmax Policy Gradient Methods Can Take Exponential Time to Converge [60.98700344526674]
  Softmax Policy gradient(PG)メソッドは、現代の強化学習におけるポリシー最適化の事実上の実装の1つです。 ソフトマックス PG 法は、$mathcalS|$ および $frac11-gamma$ の観点から指数時間で収束できることを実証する。
  論文  参考訳（メタデータ） (2021-02-22T18:56:26Z)
• Upper Confidence Primal-Dual Reinforcement Learning for CMDP with Adversarial Loss [145.54544979467872]
  マルコフ決定過程(CMDP)に対するオンライン学習の検討 本稿では,遷移モデルから標本化した軌跡のみを必要とする,新しいEmphupper confidence primal-dualアルゴリズムを提案する。 我々の分析では、ラグランジュ乗算過程の新たな高確率ドリフト解析を、高信頼強化学習の記念後悔解析に組み入れている。
  論文  参考訳（メタデータ） (2020-03-02T05:02:23Z)
• Provably Efficient Safe Exploration via Primal-Dual Policy Optimization [105.7510838453122]
  制約付きマルコフ決定過程(CMDP)を用いた安全強化学習(SRL)問題について検討する。 本稿では,関数近似設定において,安全な探索を行うCMDPの効率の良いオンラインポリシー最適化アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-03-01T17:47:03Z)

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

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