論文の概要: Rate-Optimal Algorithm for Adversarial Linear CMDPs

• arxiv url: http://arxiv.org/abs/2610.00927v2
• Date: Tue, 06 Oct 2026 06:59:55 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-08 02:58:29.251505
• Title: Rate-Optimal Algorithm for Adversarial Linear CMDPs
• Title（参考訳）: 逆線形CMDPのレート最適アルゴリズム
• Abstract要約: 逆線形制約マルコフ決定過程(CMDP)を未知の遷移で検討する。 本稿では,Slater の条件を仮定することなく,$widetildemathcalO(sqrtK)$ regret と cumulative 制約違反を実現する,新しい原始双対アルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 8.015940996821541
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study episodic adversarial linear constrained Markov decision processes (CMDPs) with unknown transitions, where both the loss and constraint functions may vary adversarially across episodes. The best previous algorithm achieves $\widetilde{\mathcal{O}}(K^{3/4})$ regret and cumulative constraint violation, leaving a gap to the optimal $\widetilde{\mathcal{O}}(\sqrt{K})$ dependence on the number of episodes $K$. We close this gap by proposing a new primal dual algorithm that achieves $\widetilde{\mathcal{O}}(\sqrt{K})$ regret and cumulative constraint violation without assuming Slater's condition. We further extend the algorithm to achieve the same $\widetilde{\mathcal{O}}(\sqrt{K})$ guarantees for regret and hard constraint violation, which does not allow constraint violations to cancel across episodes. The main challenge is that learning linear CMDPs requires uniform concentration over a value function class with a controlled covering number, whereas standard techniques in constrained online learning, such as policy mixing, can make this class more complex. Our algorithm combines adaptive Follow the Regularized Leader (FTRL), contracted value estimation, and an exponential Lyapunov function. An adaptive dual regularizer offsets the dependence on the dual weights in the primal regret bound, removing the need for policy mixing. We further show that the normalization in the FTRL update bounds the policy parameters independently of the magnitudes of the dual weights, which explains why the resulting policy class remains compatible with uniform concentration. Under feature access, the computational complexity is independent of the size of the state space.
• Abstract（参考訳）: 本研究は,各エピソードにおける損失関数と制約関数の相違について,未知の遷移を伴うエピソード逆線形制約マルコフ決定過程(CMDP)について検討する。 最上級のアルゴリズムは、$\widetilde{\mathcal{O}}(K^{3/4})$ 後悔と累積的制約違反を達成し、最適な$\widetilde{\mathcal{O}}(\sqrt{K})$ エピソード数に依存する。 我々は、スレーターの条件を仮定することなく、後悔と累積的制約違反を$\widetilde{\mathcal{O}}(\sqrt{K})で達成する新しい原始双対アルゴリズムを提案することにより、このギャップを埋める。 さらにアルゴリズムを拡張して、同じ$\widetilde{\mathcal{O}}(\sqrt{K})$で、後悔と厳しい制約違反を保証します。 主な課題は、線形CMDPの学習は、制御された被覆数を持つ値関数クラスに対して一様濃度を必要とするのに対し、ポリシーミキシングのような制約付きオンライン学習における標準技術は、このクラスをより複雑にすることができることである。 本アルゴリズムは,適応Follow the Regularized Leader(FTRL),契約値推定,指数的リアプノフ関数を組み合わせた。 適応二元正則化器は、原始後悔境界における双対重みへの依存をオフセットし、政策混合の必要性を除去する。 さらに、FTRL更新における正規化は、双対重みの大きさとは無関係にポリシーパラメータを束縛していることが示され、結果として生じるポリシークラスが一様濃度と相容れない理由が説明される。 特徴アクセスの下では、計算複雑性は状態空間のサイズとは無関係である。

関連論文リスト

• Stability-Constrained Approximation in Spline KANs: Exact Layer Balancing and Budget-Compatible Saturation [51.56484100374058]
  我々は、ハードレイヤーワイドリプシッツ予算の下で近似を研究する。 構成条件下では、対応するレイヤエラーをキャンセルする必要はないことを示す。 クラスのすべての作用素に対して、安定した深さ-$L$タワーが存在し、累積誤差の定数分を実現できる。
  論文  参考訳（メタデータ） (2026-09-14T20:17:04Z)
• Primal-Dual Policy Optimization for Linear CMDPs with Adversarial Losses [0.8984888893275712]
  我々は、LogSumExpソフトマックスポリシーと呼ばれる新しいクラスのポリシーを導入し、実行します。 周期的ポリシーミキシングと正規化された二重更新という2つの新しいアルゴリズムコンポーネントは、被覆数と二重変数の両方を効果的に制御できる。
  論文  参考訳（メタデータ） (2026-05-12T05:02:02Z)
• Near-Optimal Primal-Dual Algorithm for Learning Linear Mixture CMDPs with Adversarial Rewards [0.8984888893275712]
  有限-水平線形混合制約マルコフ決定過程における安全強化学習について検討する。 本稿では, 後悔と制約違反境界を実現するプリミティブ・デュアルポリシー最適化アルゴリズムを提案する。 これは、線形混合CMDPと逆効果を持つ最初の証明可能な効率のよいアルゴリズムである。
  論文  参考訳（メタデータ） (2026-03-29T21:51:33Z)
• Near-Optimal Sample Complexity for Online Constrained MDPs [10.479589616736193]
  CMDP(Constrained Markov Decision Processs)は、性能を最適化しながら安全性の制約を強制するために一般的に用いられる。 既存の手法は、しばしば重大な安全違反に悩まされるか、あるいは準最適ポリシーを生成するために高いサンプルの複雑さを必要とする。 本稿では,後悔と制約違反のバランスをとるモデルベース原始双対アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2026-02-16T05:16:13Z)
• Provably Efficient RL under Episode-Wise Safety in Constrained MDPs with Linear Function Approximation [32.74649239695449]
  制約決定過程(CMDP)における強化学習問題について検討する。 本稿では,リニアCMDPに対するRLアルゴリズムを提案する。 その結果,近年の線形CMDPアルゴリズムでは,制約に違反するか,指数計算コストに悪影響を及ぼす結果が得られた。
  論文  参考訳（メタデータ） (2025-02-14T13:07:25Z)
• Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiency [90.40062452292091]
  本稿では,不整合雑音を持つ線形帯域に対する計算効率のよい最初のアルゴリズムを提案する。 我々のアルゴリズムは未知のノイズの分散に適応し、$tildeO(d sqrtsum_k = 1K sigma_k2 + d)$ regretを達成する。 また、強化学習において、線形混合マルコフ決定過程(MDP)に対する分散適応アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-02-21T00:17:24Z)
• Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
  我々は,損失関数が約1,300ドル以上のエピソードに対して任意に変化するような,敵対的決定過程(MDP)の学習を検討する。 本稿では,同じ設定で$tildemathcal O(K2/3)$に対する後悔を改善する2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-30T14:37:21Z)
• 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)

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

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