Learning Weakly Communicating Average-Reward CMDPs: Strong Duality and Improved Regret

• URL: http://arxiv.org/abs/2605.11586v1
• Date: Tue, 12 May 2026 06:13:00 GMT
• Title: Learning Weakly Communicating Average-Reward CMDPs: Strong Duality and Improved Regret
• Abstract summary: Our contributions are twofold.<n>First, we adapts strong duality for weakly average-reward CMDPs.<n>Second, we propose an algorithm for learning weakly communicating average-reward linear CMDPs.
• Score: 0.7646713951724009
• 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. Our contributions are twofold. First, we establish strong duality for weakly communicating average-reward CMDPs over stationary policies with finite state and action spaces. Despite the absence of a linear programming formulation and the resulting nonconvexity under the weakly communicating setting, we show that strong duality still holds by carefully exploiting the geometric structure of the occupation measure set. Second, building on this result, we propose a primal--dual clipped value iteration algorithm for learning weakly communicating average-reward linear CMDPs. Our algorithm achieves regret and constraint violation bounds of $\widetilde{\mathcal{O}}(T^{2/3})$, improving upon the best known bounds, where $T$ denotes the number of interactions. Our approach extends clipped value iteration to the constrained setting and adapts it to a finite-horizon approximation, which stabilizes the dual variable and is crucial for achieving improved regret bounds. To analyze this, we develop a novel approach based on strong duality that enables the decomposition of the composite Lagrangian regret into separate bounds on regret and constraint violation.

Related papers

• Primal-Dual Policy Optimization for Linear CMDPs with Adversarial Losses [0.8984888893275712]
  We introduce and run with a new class of policies, which we call weighted LogSumExp softmax policies.<n>Two novel algorithmic components -- periodic policy mixing and a regularized dual update -- allow us to effectively control both the covering number and the dual variable.
  arXiv  Detail & Related papers  (2026-05-12T05:02:02Z)
• Near-Optimal Primal-Dual Algorithm for Learning Linear Mixture CMDPs with Adversarial Rewards [0.8984888893275712]
  We study safe reinforcement learning in finite-horizon linear mixture constrained Markov decision processes.<n>We propose a primal-dual policy optimization algorithm that achieves regret and constraint violation bounds.<n>This is the first provably efficient algorithm for linear mixture CMDPs with adversarial rewards.
  arXiv  Detail & Related papers  (2026-03-29T21:51:33Z)
• Near-Constant Strong Violation and Last-Iterate Convergence for Online CMDPs via Decaying Safety Margins [31.581870065866568]
  We study safe online reinforcement learning in Constrained Markov Decision Processes (CMDPs) under strong regret and violation metrics.<n>Existing primal-dual methods that achieve sublinear strong reward regret incur growing strong constraint violation or are restricted to average-iterate convergence due to inherent oscillations.<n>We propose the Flexible safety Domain Optimization via Margin-regularized Exploration (FlexDOME) algorithm, the first to provably achieve near-constant $tildeO(1)$ strong constraint violation alongside sublinear strong regret and non-asymptotic last-iterate convergence.
  arXiv  Detail & Related papers  (2026-02-11T14:54:26Z)
• AL-CoLe: Augmented Lagrangian for Constrained Learning [79.45233551350152]
  Despite the non-ity of most modern machine learning parameterizations, Lagrangian duality has become a popular tool for addressing constrained learning problems.<n>We demonstrate its effectiveness on constrained classification tasks.
  arXiv  Detail & Related papers  (2025-10-23T20:46:49Z)
• Learning Adversarial MDPs with Stochastic Hard Constraints [37.24692425018]
  We study online learning in constrained Markov decision processes (CMDPs) with adversarial losses and hard constraints.<n>Our work is the first to study CMDPs involving both adversarial losses and hard constraints.
  arXiv  Detail & Related papers  (2024-03-06T12:49:08Z)
• Double Duality: Variational Primal-Dual Policy Optimization for Constrained Reinforcement Learning [132.7040981721302]
  We study the Constrained Convex Decision Process (MDP), where the goal is to minimize a convex functional of the visitation measure. Design algorithms for a constrained convex MDP faces several challenges, including handling the large state space.
  arXiv  Detail & Related papers  (2024-02-16T16:35:18Z)
• Algorithm for Constrained Markov Decision Process with Linear Convergence [55.41644538483948]
  An agent aims to maximize the expected accumulated discounted reward subject to multiple constraints on its costs. A new dual approach is proposed with the integration of two ingredients: entropy regularized policy and Vaidya's dual. The proposed approach is shown to converge (with linear rate) to the global optimum.
  arXiv  Detail & Related papers  (2022-06-03T16:26:38Z)
• Policy-based Primal-Dual Methods for Concave CMDP with Variance Reduction [18.95829896746939]
  We study Concave CMDPs where both the objective and constraints are defined as concave functions of the state-action occupancy measure. We propose the Variance-Reduced Primal-Dual Policy Gradient, which updates the primal variable via policy gradient ascent and the dual variable via projected sub-gradient descent.
  arXiv  Detail & Related papers  (2022-05-22T02:50:16Z)
• A Fully Problem-Dependent Regret Lower Bound for Finite-Horizon MDPs [117.82903457289584]
  We derive a novel problem-dependent lower-bound for regret in finite-horizon Markov Decision Processes (MDPs) We show that our lower-bound is considerably smaller than in the general case and it does not scale with the minimum action gap at all. We show that this last result is attainable (up to $poly(H)$ terms, where $H$ is the horizon) by providing a regret upper-bound based on policy gaps for an optimistic algorithm.
  arXiv  Detail & Related papers  (2021-06-24T13:46:09Z)
• A Stochastic Composite Augmented Lagrangian Method For Reinforcement Learning [9.204659134755795]
  We consider the linear programming (LP) formulation for deep reinforcement learning. The augmented Lagrangian method suffers the double-sampling obstacle in solving the LP. A deep parameterized augment Lagrangian method is proposed.
  arXiv  Detail & Related papers  (2021-05-20T13:08:06Z)
• Exploration-Exploitation in Constrained MDPs [79.23623305214275]
  We investigate the exploration-exploitation dilemma in Constrained Markov Decision Processes (CMDPs) While learning in an unknown CMDP, an agent should trade-off exploration to discover new information about the MDP. While the agent will eventually learn a good or optimal policy, we do not want the agent to violate the constraints too often during the learning process.
  arXiv  Detail & Related papers  (2020-03-04T17:03:56Z)
• Upper Confidence Primal-Dual Reinforcement Learning for CMDP with Adversarial Loss [145.54544979467872]
  We consider online learning for episodically constrained Markov decision processes (CMDPs) We propose a new emphupper confidence primal-dual algorithm, which only requires the trajectories sampled from the transition model. Our analysis incorporates a new high-probability drift analysis of Lagrange multiplier processes into the celebrated regret analysis of upper confidence reinforcement learning.
  arXiv  Detail & Related papers  (2020-03-02T05:02:23Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.