Research map / Bandits and online learning / RL theory and MDPs

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

NeurIPS 2026 · Bandits and online learning › RL theory and MDPs · approach: Average-reward and latent MDPs · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Establishes strong duality for weakly communicating average-reward CMDPs over stationary policies, and uses it to design a primal-dual clipped value iteration algorithm for linear CMDPs achieving O(T^{2/3}) regret and constraint violation.

Problem

Learning infinite-horizon average-reward constrained MDPs under the weakly communicating assumption, where strong duality is unclear (no LP formulation, nonconvex occupation measure set) and prior linear CMDP regret bounds are O(T^{3/4}).

Approach

Shows the stationary occupation-measure set has polytope-like geometry (relative interior and extreme points included) enough to invoke LP strong duality despite nonconvexity; combines this with clipped value iteration on a finite-horizon approximation with a primal-dual dual-variable update, and uses strong duality to split composite Lagrangian regret into separate regret and violation bounds.

Key results

• Proves strong duality for weakly communicating average-reward CMDPs over stationary policies when the problem is feasible, with a dual minimizer existing.
• PD-LSCVI-UCB achieves Regret(T) = O((zeta+2/gamma)T^{2/3} + (zeta+1)(sqrt(d^3 T)+d^2 T^{1/3})) with high probability.
• Constraint violation bound is O((gamma zeta+2)T^{2/3} + gamma(zeta+1)(sqrt(d^3T)+d^2T^{1/3}) + gamma sp(v*) sqrt(T)), improving on the prior O(T^{3/4}).

Surprising findings

• Weakly communicating average-reward CMDPs over stationary policies may have no optimal stationary policy, even though strong duality holds.
• The occupation measure set for weakly communicating MDPs is nonconvex, yet LP strong duality still applies via relative-interior and extreme-point inclusions.

Limitations

• Computational complexity depends on the number of states due to min over states in value clipping.
• Regret remains O(T^{2/3}), not the optimal O(sqrt(T)), because of dual variable control terms.
• Strong duality is established only for finite state and action spaces.

Experimental setup

Metrics: regret constraint violation

Baselines: prior primal-dual average-reward linear CMDP algorithm (O(T^{3/4})) clipped value iteration for unconstrained average-reward linear MDPs

Builds on: clipped value iteration (unconstrained average-reward linear MDP) UCRL2-style optimism LP strong duality

Closest papers by meaning

• Learning General Parameterized Policies for Infinite Horizon Average Reward Constrained MDPs via Primal-Dual Policy Gradient Algorithm (NeurIPS 2024 · similarity 0.91)
• Efficient Exploration in Average-Reward Constrained Reinforcement Learning: Achieving Near-Optimal Regret With Posterior Sampling (ICML 2024 · similarity 0.90)
• Global Convergence for Average Reward Constrained MDPs with Primal-Dual Actor Critic Algorithm (NeurIPS 2025 · similarity 0.89)
• Span-Based Optimal Sample Complexity for Weakly Communicating and General Average Reward MDPs (NeurIPS 2024 · similarity 0.89)
• Optimal Non-Asymptotic Rates of Value Iteration for Average-Reward Markov Decision Processes (ICLR 2025 · similarity 0.88)
• Regret Analysis of Policy Gradient Algorithm for Infinite Horizon Average Reward Markov Decision Processes (AAAI 2024 · similarity 0.88)