Research map / Reinforcement learning / MDPs and planning

Projection-based Lyapunov method for fully heterogeneous weakly-coupled MDPs

NeurIPS 2025 · Reinforcement learning › MDPs and planning · approach: Robust MDP policy gradient · 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.

Proposes an ID policy with arm reassignment for fully heterogeneous average-reward weakly-coupled MDPs, proving an O(1/sqrt(N)) optimality gap via projection-based Lyapunov functions.

Problem

Planning for fully heterogeneous average-reward weakly-coupled MDPs (arms with distinct parameters, global budget constraints), where the state space is exponential in N and no asymptotically optimal efficient policy was known.

Approach

An ID policy with reassignment that gives each arm its own optimal single-armed policy from an LP relaxation, reorders arm IDs so budget consumption is smooth across contiguous segments, and uses projection-based Lyapunov functions (features = discounted-by-gamma future expected rewards and costs) to show convergence to an optimal region under full heterogeneity.

Key results

• Theorem: the ID policy with reassignment achieves optimality gap R*(N) - R(pi) <= C_ID/sqrt(N), the first such result for fully heterogeneous average-reward WCMDPs under an aperiodic unichain and uniform mixing-time assumption.
• Simulations with N from 100 to 3200 show the optimality ratio of the ID policy approaches 1 as N grows.
• ID policy shows slight improvement over the ERC policy in some instances and comparable performance in others on a single-budget typed-heterogeneous instance.

Measured effects reported in the paper

Limitations

• Constant C_ID scales as K^5 max(r,c)^7 tau^4 / alpha_min^6, not optimized
• Requires aperiodic unichain assumption with uniform mixing-time bound on optimal single-armed policies
• Planning setting only; all model parameters assumed known

Experimental setup

Datasets: randomly generated synthetic WCMDP instances

Benchmarks: synthetic fully heterogeneous WCMDP instances (10 states, 4 actions, 4 budget constraints) typed heterogeneous synthetic WCMDP instance (10 types, single budget)

Metrics: optimality ratio (policy reward / LP upper bound)

Baselines: ERC policy

Builds on: ID policy Whittle index policy LP-Priority policy Follow-the-Virtual-Advice

Closest papers by meaning

• Augmented Lagrangian Method for Last-Iterate Convergence for Constrained MDPs (NeurIPS 2026 · similarity 0.87)
• Learning Weakly Communicating Average-Reward CMDPs: Strong Duality and Improved Regret (NeurIPS 2026 · similarity 0.86)
• Provable Policy Gradient for Robust Average-Reward MDPs Beyond Rectangularity (ICML 2025 · similarity 0.86)
• Faster Fixed-Point Methods for Multichain MDPs (NeurIPS 2025 · similarity 0.86)
• Solving Non-rectangular Reward-Robust MDPs via Frequency Regularization (AAAI 2024 · similarity 0.86)
• Solving Robust Markov Decision Processes: Generic, Reliable, Efficient (AAAI 2025 · similarity 0.86)