🤖 machine learning

Lyapunov-Based Sample Complexity Analysis for Weakly-Coupled MDPs

This paper presents a novel Lyapunov-based analysis framework that establishes the first finite-sample PAC guarantees with polynomial sample and computational complexity for learning near-optimal policies in weakly-coupled Markov decision processes and restless bandits, overcoming the exponential state-space limitations of naive tabular approaches.

Original authors: Tianhao Wu, Matthew Zurek, Weina Wang, Qiaomin Xie

Published 2026-06-15

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Tianhao Wu, Matthew Zurek, Weina Wang, Qiaomin Xie

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: The "Orchestra" Problem

Imagine you are the conductor of a massive orchestra with $N$ musicians (let's say 1,000 or 10,000). Each musician is playing their own instrument (a "sub-system" or "arm").

The Goal: You want the whole orchestra to play a beautiful, harmonious song that maximizes the "reward" (applause) over a very long time.
The Catch: You have a strict rule: at any given moment, the total volume of the brass section cannot exceed a certain limit, and the percussion section has its own limit. These are the global constraints.
The Problem: If you try to treat this as one giant, single problem, the number of possible combinations of notes every musician could play is astronomical. It's like trying to find the perfect recipe by tasting every possible combination of ingredients in the universe. In computer science terms, the "state space" is exponentially large, making it impossible to learn the best strategy quickly.

This paper tackles a specific type of orchestra where the musicians are weakly coupled. This means they mostly play their own parts independently, but they have to coordinate just enough to stay within the volume limits.

The Core Challenge: Learning Without a Cheat Sheet

Usually, to learn how to conduct this orchestra, you would need to try every possible combination of notes millions of times to see what works. Because there are so many musicians, this would take forever (exponential time).

The authors ask: "Can we learn a near-perfect conducting strategy quickly, without needing to try every single combination?"

Their answer is yes, but only if we use a clever trick: The "Plug-in" Approach.

The Solution: The "Plug-in" Strategy

Instead of trying to learn the whole orchestra at once, the authors suggest a two-step process:

Listen to Individuals: First, you listen to each musician individually. You ask them, "If you were playing alone, what is the best note to play in this situation?" You build a small, simple model for each musician based on data you collect.
Plug into a Master Plan: You take these individual "best practices" and plug them into a pre-existing, efficient algorithm (a "reference policy") that knows how to coordinate them.

Think of it like a traffic control system. Instead of trying to predict the movement of every single car in a city simultaneously (which is impossible), you teach each car the best route for itself. Then, you use a central computer to slightly adjust the timing of traffic lights so that the cars don't crash into each other.

The Two Types of Orchestras

The paper looks at two specific scenarios:

The Heterogeneous Orchestra (WCMDPs): Every musician plays a different instrument with different rules.
- Result: The authors prove that by using their method, the "mistake" (optimality gap) in the final performance shrinks as you add more musicians. Specifically, the error gets smaller at a rate of $1/\sqrt{N}$ . If you double the number of musicians, the error doesn't get worse; it actually gets easier to manage because the "noise" averages out.
The Homogeneous Orchestra (Restless Bandits): Every musician plays the exact same instrument with the exact same rules.
- Result: This is even easier. Under certain conditions, the error shrinks exponentially fast (like $e^{-N}$ ). This means with a large enough orchestra, the performance is almost perfect.

The Secret Sauce: The "Lyapunov" Framework

This is the most technical part of the paper, but here is the simple version.

To prove their method works, the authors had to show that the "Plug-in" strategy doesn't fall apart when the data is slightly imperfect (which it always is, because you can't listen to every note perfectly).

The Old Way: Previous methods tried to use a "bias function" to measure how far off the plan was. But this function is like a ghost—it's hard to see, hard to define, and hard to control.
The New Way (Lyapunov): The authors invented a new tool called a Lyapunov function. Think of this as a thermometer or a speedometer for the system.
- They built this thermometer explicitly so they could guarantee it wouldn't get too hot (too large).
- They used a technique called "Drift Transfer." Imagine you have a map of the real world (the true orchestra) and a slightly blurry map (the empirical data). They showed that if the "temperature" (drift) is controlled on the real map, it stays controlled on the blurry map, provided the blur isn't too bad.

This allows them to mathematically prove that even with imperfect data, the strategy remains stable and close to optimal.

The "Perturbation" Discovery

A key side-discovery in the paper is about Robustness.

They analyzed the mathematical equations (Linear Programs) used to decide the strategy. They found that if you slightly change the input data (like a musician playing a slightly different note than expected), the core structure of the solution doesn't break.

Analogy: Imagine a puzzle. If you swap one piece for a slightly different one, the picture might change a tiny bit, but the overall shape of the puzzle remains the same. The "neutral" piece (the one that adjusts the balance) stays in the same spot, and the rest of the puzzle holds together. This proves the system is robust against small errors.

Summary of Results

Efficiency: The paper proves that you can learn to conduct this massive orchestra with a number of samples (practice runs) that grows polynomially (e.g., $N^2$ or $N^3$ ), not exponentially. This makes learning feasible for large systems.
Accuracy: The learned strategy is "near-optimal." For diverse groups, the error is small ( $1/\sqrt{N}$ ). For identical groups, the error is tiny (exponentially small).
Method: They replaced a hard-to-control "ghost" function with a custom-built "thermometer" (Lyapunov function) to prove stability.

In short, the authors found a way to teach a computer how to manage a massive, complex system by breaking it down into manageable pieces, proving that the whole is greater than the sum of its parts, and showing that small mistakes in data won't cause the whole system to collapse.

Technical Summary: Lyapunov-Based Sample Complexity Analysis for Weakly-Coupled MDPs

1. Problem Statement

This paper addresses the sample complexity of learning near-optimal policies in average-reward Weakly-Coupled Markov Decision Processes (WCMDPs) and Restless Bandits (RBs) under a generative model setting.

In these systems, $N$ independent arms (subsystems), each modeled as an MDP, are coupled through global cost constraints (e.g., a budget on the total number of active arms). The objective is to maximize the long-term average reward. The core challenge lies in the "curse of dimensionality": viewing the system as a single monolithic MDP results in a state-action space of size $|S|^N \times |A|^N$ , which is exponential in $N$ . Naive application of existing sample complexity bounds for tabular MDPs (which scale with the size of the state-action space) yields bounds exponential in $N$ , rendering learning intractable for large systems.

The paper seeks to answer: How can one learn a near-optimal policy in average-reward WCMDPs (or RBs) without incurring exponential dependence on the number of arms $N$ ?

2. Methodology

2.1. Plug-in Approach with Reference Policies

The authors adopt a plug-in approach. Instead of learning a policy directly from interaction, they:

Collect $n$ i.i.d. samples for each state-action pair of each arm to construct an empirical transition kernel ( $\hat{P}$ ).
Solve a planning algorithm on this empirical model to derive a policy.
Use specific, efficient planning algorithms as reference policies:
- For Heterogeneous WCMDPs: The ID policy (Zhang et al., 2025), which achieves an $O(1/\sqrt{N})$ optimality gap in the planning regime.
- For Homogeneous RBs: The two-set policy (Hong et al., 2024a), which achieves an exponentially small optimality gap ( $O(e^{-cN})$ ) under specific structural conditions.

2.2. Novel Lyapunov-Based Analysis Framework

The primary technical innovation is a new framework for analyzing the sample complexity of the plug-in approach.

Classical Limitation: Traditional analysis relies on the simulation lemma, which bounds the performance gap using the bias function (relative value function) of the MDP. The bias function is often implicit, complex, and difficult to bound, especially for sophisticated planning algorithms like ID or two-set policies.
Proposed Solution: The authors replace the bias function with an explicitly constructed Lyapunov function ( $V$ $V$ ).
- Step 1 (Lyapunov Analysis): They establish that the reference policy satisfies a drift bound (the Lyapunov function decreases in expectation) and a gap dominance condition (the reward gap is bounded by the Lyapunov function) in the true system.
- Step 2 (Drift Transfer): They transfer these bounds to the empirical system. By explicitly bounding the norm of the constructed Lyapunov function, they control the error introduced by the model mismatch ( $P - \hat{P}$ ).
- Advantage: Since $V$ is explicitly constructed, its norm is tractable to bound, avoiding the difficulties associated with the implicit bias function.

2.3. Fine-Grained LP Perturbation Analysis

For the homogeneous RB case, a critical step involves analyzing the Linear Programming (LP) relaxation used to derive the optimal single-armed policy.

The authors prove that under mild structural assumptions (ergodicity, non-degeneracy, local stability), the solution to the LP is robust to perturbations in the transition kernel.
Specifically, they show that the support of the optimal solution (which actions are taken in which states) remains stable under small perturbations, except possibly at a single "neutral state."
This ensures that the empirical policy retains the structural properties required for the Lyapunov analysis to hold.

3. Key Results

3.1. Heterogeneous WCMDPs

For fully heterogeneous WCMDPs, the paper establishes the first finite-sample PAC (Probably Approximately Correct) guarantee with polynomial complexity.

Result: The learned policy $\hat{\pi}_{ID}$ achieves an optimality gap of:
$\rho^* - \rho_{\hat{\pi}_{ID}} \leq O\left(\frac{\sqrt{S + \log(N/\eta)}}{\sqrt{n}} \cdot N\right) + O\left(\frac{1}{\sqrt{N}}\right)$
where $n$ is the number of samples per state-action pair per arm.
Sample Complexity: To achieve a gap $\epsilon = \Omega(1/\sqrt{N})$ , the total number of samples required scales as polynomial in $N$ (specifically $O(N^3)$ total samples), rather than exponentially.

3.2. Homogeneous Restless Bandits

For homogeneous RBs, under mild structural assumptions (Assumptions 2 and 3), the learned policy $\hat{\pi}_{TS}$ achieves a significantly tighter bound.

Result: The optimality gap is bounded by:
$\rho^* - \rho_{\hat{\pi}_{TS}} \leq O\left(\frac{\sqrt{S + \log(1/\eta)}}{\sqrt{n}} \cdot N\right) + O(e^{-cN})$
Sample Complexity: Since the reference policy's inherent gap is exponentially small, the learning algorithm can achieve a gap of $\epsilon = \Omega(e^{-cN})$ with a sample size $n$ that scales polynomially in $N$ .
Blocking Scheme: The authors also propose a "blocking" technique for fixed sample sizes, partitioning arms into blocks to balance finite-sample error and the reference policy's optimality gap, further demonstrating the flexibility of the approach.

4. Significance and Claims

The paper claims three primary contributions:

Breaking the Exponential Barrier: It demonstrates that by exploiting the weakly-coupled structure, one can learn near-optimal policies with sample and computational complexities that are polynomial in $N$ . This formally resolves the learning challenge for large-scale WCMDPs and RBs, contrasting sharply with the exponential complexity of treating them as monolithic MDPs.
Novel Analysis Framework: The Lyapunov-based analysis framework is presented as a general tool for analyzing plug-in approaches in average-reward systems. By decoupling the analysis from the difficult-to-control bias function and using explicit Lyapunov functions, the framework provides a powerful method for establishing finite-sample guarantees for complex planning algorithms.
Robustness of LP-Based Policies: The fine-grained perturbation analysis of the LP relaxation reveals an intrinsic robustness property: policies constructed via this LP are stable against model perturbations. This result is of independent interest and can serve as a robustness module for analyzing other index and LP-priority policies in the literature.

The authors emphasize that their results are the first finite-sample PAC guarantees for these settings with polynomial complexity, moving beyond asymptotic optimality results or regret bounds that do not directly translate to sample complexity in the average-reward regime.