Achieving an $O(1/N)$ Optimality Gap in Average-Reward Weakly-Coupled MDPs

Weakly-coupled Markov decision processes (WCMDPs) model sequential resource allocation across many independent agents that share a common budget. Each of the N arms transitions independently given its state and action, but at every step the total cost across all arms must stay within per-type budget limits. This structure appears in online advertising, healthcare scheduling, surveillance, and machine maintenance. The goal is to maximize long-run average reward per arm. The optimality gap—the difference between the best achievable reward and what a policy delivers—typically shrinks as N grows. For the restless-bandit special case (two actions, one budget), prior work has established O(1/√N) gaps under general conditions and exponential gaps under stronger assumptions. For general WCMDPs with multiple actions, multiple budgets, and state-dependent costs, however, no result had broken the O(1/√N) barrier. This paper closes that gap, proving an O(1/N) optimality gap for homogeneous WCMDPs under three assumptions: aperiodic unichain, non-degeneracy, and local stability.

The O(1/√N) Barrier in Weakly-Coupled MDPs

Restless bandits are a narrow subclass of WCMDPs: each arm has exactly two actions (active and passive), a single budget caps the fraction of arms that can be active, and costs do not depend on state. In that setting, priority policies derived from an LP relaxation achieve exponentially small gaps when the LP solution is non-degenerate and the induced mean-field dynamics satisfy a uniform global attractor property (UGAP). Earlier work by the same authors replaced UGAP with a weaker local-stability condition and still achieved exponential gaps using a two-set policy that alternates between a "steering" subroutine and a "refinement" subroutine.

General WCMDPs are messier. Arms can have many actions, multiple budget constraints, and costs that vary with both state and action. A single priority order no longer tells you how to trade off competing budgets. Prior average-reward results for this setting either required only one budget (giving o(1) gaps) or settled for O(1/√N) with fully heterogeneous arms. The O(1/√N) rate comes from the central-limit-theorem fluctuations of the empirical state distribution around its mean; without additional structure, you cannot beat those fluctuations.

How Local Linearity Beats the Priority Paradigm

The paper's central insight is that the priority structure itself is not what enables sub-1/√N gaps. The real enabler is local linearity of the mean-field dynamics near the optimal stationary distribution μ*. When the empirical state distribution is close to μ*, the reward and mean transition depend linearly on it. This lets you compare the *expected* empirical distribution to μ* rather than the random realization, so deviations can cancel in expectation. The expected deviation can then be smaller than the CLT fluctuation scale.

To import this idea into general WCMDPs, the authors construct an auxiliary linear system (Equation 6) that computes target state-action frequencies y from the current empirical distribution x. The system enforces four constraints: y must respect the support of the optimal LP solution y*, actions are uniform on transient states, tight budgets stay tight, and the marginals match the current x. When x = μ*, the system recovers y*. For x near μ*, the solution y(x) is an affine function of x, giving the desired local linearity.

Rounding the fractional target frequencies to integer action counts introduces an O(1/N) residual in reward and mean transition. This rounding residual—not the CLT noise—becomes the dominant term in the gap bound, yielding O(1/N) instead of O(1/√N).

The Two-Set Policy: Fixed-Ratio Control and LP Fixed-Point

The two-set policy partitions the N arms into two subsets at each step. One subset runs the π*̄-Fixed-Ratio Control: each arm independently samples an action from the optimal single-armed policy π*̄(a|s) derived from the LP solution. By Assumption 1 (aperiodic unichain), this subset's expected state distribution converges to μ*. The other subset runs the LP Fixed-Point subroutine: it computes the target frequencies y(x) from the linear system and implements them by allocating arms to actions according to those frequencies (rounded to integers). LP Fixed-Point is locally linear and near-optimal when the subset's empirical distribution is already close to μ*.

The policy adaptively grows the LP Fixed-Point subset. Arms whose state distribution is within a shrinking neighborhood of μ* join the refinement set; the rest stay under Fixed-Ratio Control to be steered toward μ*. This dynamic partitioning ensures that most arms eventually operate under the locally linear, near-optimal regime.

Non-Degeneracy and Local Stability: The Key Assumptions

Two assumptions make the LP Fixed-Point well-defined and stable. Assumption 2 (non-degeneracy) requires the coefficient matrix C* of the linear system to have full column rank. This guarantees a unique (or consistently chosen) solution y(x) for every x. For restless bandits, this reduces to the familiar condition that the LP has exactly one "neutral" state where both actions are used. Assumption 3 (local stability) requires the spectral radius of the matrix Φ = C*_S⁺P - 1μ*^⊤C*_S⁺P to be strictly less than 1. Here C*_S⁺ is the left-inverse of C* corresponding to the marginal-distribution equations, and P is the transition tensor. Intuitively, Φ governs the linearized mean dynamics of x(t) - μ* under LP Fixed-Point; spectral radius < 1 means deviations decay geometrically.

Both assumptions are checkable from the LP solution and the single-arm transition kernel. They replace the stronger UGAP used in earlier restless-bandit work and are strictly easier to verify.

From O(1/√N) to O(1/N): The Optimality Gap Analysis

The analysis uses a Lyapunov framework. A weighted ℓ₂ norm tracks the distance between the empirical state distribution and μ*. The proof has two stages: first showing an O(1/√N) gap (which follows from standard concentration and the steering property of Fixed-Ratio Control), then refining it to O(1/N) by exploiting the local linearity of LP Fixed-Point. The key step is bounding the expected deviation of the empirical distribution from μ*—not the high-probability deviation. Because the mean dynamics are linear near μ*, the expected deviation accumulates only the rounding residual, which is O(1/N). The rounding error enters through the difference between the fractional target y(x) and the integer action counts actually implemented; this difference is at most O(1/N) per step and does not amplify under the locally stable dynamics.

What This Means for Sequential Resource Allocation

For practitioners building large-scale resource-allocation systems, the result offers a concrete prescription: if your problem fits the homogeneous WCMDP model (identical arms, multiple actions and budgets, state-dependent costs) and the LP relaxation yields a non-degenerate, locally stable solution, the two-set policy will achieve an optimality gap that shrinks as 1/N rather than 1/√N. In concrete terms, doubling the number of arms halves the gap instead of reducing it by only √2. The policy is implementable without solving an LP at every step—only the offline LP relaxation and the online linear system (Equation 6) are needed. The paper also provides a clear path for finite-horizon variants and hints at extensions to typed heterogeneity, though fully heterogeneous arms remain open.