⚡ electrical engineering

Approximations and Learning for Continuous State and Action MDPs under Average Cost Criteria

This paper establishes error bounds for discretization-based approximations of continuous-state and action MDPs under average cost criteria by relaxing continuity assumptions to weak or Wasserstein continuity, and proposes synchronous and asynchronous quantized Q-learning algorithms that converge to the optimal values of the approximate model, thereby ensuring near-optimality.

Original authors: Ali Devran Kara, Serdar Yuksel

Published 2026-06-02

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Ali Devran Kara, Serdar Yuksel

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

Imagine you are trying to teach a robot how to navigate a vast, smooth, and continuous landscape (like a giant, open field) to find the path that costs the least amount of energy over a very long time. This is the problem of Markov Decision Processes (MDPs) under an Average Cost Criterion.

The challenge is that the robot's world is too big and smooth to map perfectly. You can't write down every single point on the field. The paper by Kara and Yükel is like a guidebook on how to build a simplified, blocky map of this smooth world, teach the robot using that blocky map, and prove that the robot will still do a great job in the real, smooth world.

Here is the breakdown of their work using simple analogies:

1. The Problem: The "Smooth World" vs. The "Pixelated Map"

Think of the real world as a high-resolution photograph. It has infinite detail. To teach a computer, we usually need to turn this photo into a low-resolution, pixelated image (a grid).

The Old Way: Previous researchers said, "To make this pixelated map work, the transition between pixels must be extremely predictable and rigid (Total Variation continuity)." This is like saying the photo must be made of perfect, non-blurry blocks.
The New Way: These authors say, "We don't need such a strict photo. We can work with a 'fuzzy' or 'wobbly' photo (Weak or Wasserstein continuity)." They proved that even if the transitions between states are a bit "soft" or "fuzzy," you can still build a reliable pixelated map.

2. The Solution: Building a "Blocky" Approximation

The authors propose a method to chop the continuous world into finite chunks (bins), like cutting a cake into slices.

The Approximation: Instead of tracking the robot's exact position, you only track which "slice" of the cake the robot is in.
The Guarantee: They calculated exactly how much "error" (or extra cost) this pixelation introduces.
- If the world is "fuzzy" but stable, the error gets smaller as you make the slices thinner.
- They showed that if you make the slices small enough, the strategy the robot learns on the blocky map will be almost as good as the perfect strategy for the smooth world.

3. The Learning: Teaching the Robot with "Quantized Q-Learning"

Once the world is chopped into slices, the robot needs to learn the best moves. The paper introduces two ways to teach the robot:

Synchronous Learning (The "Classroom" Approach): Imagine a teacher who asks the robot, "If you are in Slice A and you move Left, what happens?" The teacher then simulates every possible move from every slice at the same time, updating the robot's knowledge all at once. The authors proved this method converges (stops changing and settles on a solution).
Asynchronous Learning (The "Real-Life" Approach): Imagine the robot is just walking around the field on its own, making mistakes and learning as it goes. It doesn't get to see every slice at once; it only sees the slice it is currently in. The authors proved that even with this messy, one-step-at-a-time data, the robot will eventually learn the correct values for the blocky map.

Crucial Insight: The authors point out that the robot's "blocky" view of the world is actually a bit of a trick. Because the robot only knows which slice it's in, but not the exact spot within that slice, it's technically learning a "Partially Observable" problem (like playing a game where you can't see the whole board). Despite this, their math proves the robot still learns the optimal strategy for the blocky map.

4. The Result: "Near-Optimality"

The most important claim is about the final result.

The robot learns the best strategy for the blocky, pixelated map.
The authors prove that this strategy is also nearly optimal for the real, smooth world.
Think of it like learning to drive on a simulator with a low-resolution screen. The authors prove that if the simulator is good enough (the slices are small enough), the driving skills you learn there will transfer almost perfectly to driving a real car on a real highway.

Summary of the "Magic"

The paper does three main things:

Relaxed the Rules: They showed you don't need a perfectly rigid world to build a good approximation; a "fuzzy" world works too.
Built the Bridge: They created specific algorithms (Synchronous and Asynchronous) that let a robot learn on a simplified, blocky version of a complex world.
Proved the Transfer: They mathematically guaranteed that the strategy learned on the blocky map is so close to the perfect strategy that it's practically the same, provided the blocks are small enough.

In short, they figured out how to teach a robot to navigate a smooth, infinite world by letting it practice on a simplified, blocky version, and they proved the practice makes perfect.

Technical Summary: Q-Learning Under Average Cost Criteria for Continuous MDPs

1. Problem Formulation

This paper addresses the challenge of solving Markov Decision Processes (MDPs) with continuous state and action spaces under the infinite-horizon average cost criterion. The model is defined by a tuple $(X, U, \mathcal{T}, c)$ , where $X$ and $U$ are standard Borel spaces (complete, separable metric spaces), $\mathcal{T}$ is the transition kernel, and $c$ is the cost function. The objective is to find a policy $\pi$ that minimizes the long-run average cost:
$J^*(x) := \inf_{\pi} \limsup_{T \to \infty} \frac{1}{T} \mathbb{E}^\pi_x \left[ \sum_{t=0}^{T-1} c(x_t, u_t) \right]$

The authors highlight that while finite-horizon and discounted-cost problems for continuous spaces are well-studied using contraction properties of Bellman operators, average-cost problems present unique difficulties. Specifically, the lack of a discount factor removes the immediate contraction mapping, requiring alternative stability and ergodicity assumptions. Furthermore, existing literature on average-cost reinforcement learning (RL) largely focuses on finite spaces or imposes restrictive structural assumptions (e.g., linear dynamics, Lipschitz policies) that limit applicability to general continuous spaces.

2. Methodology

The paper employs a two-pronged approach: finite approximation via quantization and reinforcement learning algorithms designed for these approximations.

2.1 Discretization and Approximation

The core methodology involves constructing a finite-state, finite-action approximate MDP by quantizing the continuous spaces.

State Quantization: The state space $X$ is partitioned into disjoint bins $\{B_i\}_{i=1}^M$ with representative states $y_i$ . A mapping $q: X \to Y$ (where $Y$ is the finite set of representatives) is defined.
Action Quantization: The action space $U$ is approximated by a finite set $\Lambda$ .
Approximate Model Construction: The approximate model $(\hat{X}, \hat{U}, \hat{\mathcal{T}}, \hat{c})$ is defined using a weight measure $\mu$ (often the invariant measure of the state process). The approximate cost and transition kernels are averages of the original functions over the quantization bins:
$\hat{c}(y_i, u) = \int_{B_i} c(z, u) \mu_{y_i}(dz), \quad \hat{\mathcal{T}}(A|y_i, u) = \int_{B_i} \mathcal{T}(A|z, u) \mu_{y_i}(dz)$
Relaxed Continuity Conditions: A significant methodological shift is the relaxation of the Total Variation (TV) continuity condition, which is standard in prior approximation literature (e.g., Saldi et al., 2018). The authors establish approximation results under:
1. Weak Continuity (Feller): Sufficient for asymptotic convergence of errors as grid sizes vanish.
2. Wasserstein Continuity: Sufficient for establishing explicit convergence rates (error bounds) as grid sizes vanish.

2.2 Reinforcement Learning Algorithms

The paper proposes Quantized Q-Learning algorithms to learn the optimal policy for the approximate model directly from data.

Synchronous Algorithm (Algorithm 1): Updates Q-values for all state-action pairs in the finite grid simultaneously. It relies on sampling states from each bin according to a pre-determined measure.
Asynchronous Algorithm (Algorithm 2): Updates Q-values based on a single trajectory of the original continuous process. This is more practical but introduces a non-Markovian noise term because the quantized process $q(X_t)$ is not a Markov chain (it is a Partially Observable MDP from the perspective of the quantized state).
Convergence Mechanism: To handle the average cost criterion and the lack of boundedness in Q-iterates (unlike discounted cases), the authors utilize:
- Span Semi-norms for synchronous updates.
- Ergodicity Assumptions: The exploration policy must induce a unique invariant measure with full support over the quantized bins.
- Shifted Updates: The asynchronous algorithm subtracts a reference value (based on a specific bin) to stabilize the iteration, treating the quantized process as a POMDP.

3. Key Contributions

The paper makes three primary contributions, advancing the state of the art in continuous-space average-cost control:

Approximation Theory with Weaker Conditions:
- The authors provide error bounds for finite approximations under weak continuity and Wasserstein continuity, relaxing the strict Total Variation continuity required by previous works (e.g., Saldi et al., 2018).
- They establish that under Wasserstein continuity (with a contraction constant $K_T < 1$ ), the error in the optimal average cost decays at a rate proportional to the quantization error (specifically $L_X^\delta$ ).
- Under weak continuity alone, they prove asymptotic convergence of the approximate policy's cost to the optimal cost as the discretization becomes finer.
Convergence of Quantized Q-Learning:
- The paper establishes the almost sure convergence of both synchronous and asynchronous Q-learning algorithms for continuous spaces.
- Crucially, it proves that these algorithms converge to the optimal Q-values of the constructed finite approximate model, not just the original continuous model. This distinction is vital because the quantized process is not strictly Markovian.
- The analysis generalizes previous results (e.g., Kara and Yüksel, 2023) from discounted costs to the more challenging average cost criterion, requiring new technical analysis to handle unbounded Q-iterates.
Near-Optimality Guarantees:
- By combining the approximation error bounds with the convergence of the learning algorithms, the paper demonstrates that the policies learned via quantized Q-learning are near-optimal for the original continuous MDP.
- The performance loss is explicitly bounded in terms of the quantization resolution and the Lipschitz constants of the cost and transition kernels.

4. Key Results and Theorems

Theorem 1 & 2 (Approximation Bounds): Establish upper bounds on the difference between the optimal average cost of the original model ( $\rho$ $ρ$ ) and the approximate model ( $\hat{\rho}$ $\overset{ρ}{^}$ ).
- Under Wasserstein continuity: $|\rho - \hat{\rho}| \leq C \cdot (L_X)^\delta$ , where $L_X$ is the quantization error.
- Under weak continuity: $\lim_{n \to \infty} \rho(\pi_n) = \rho$ .
Theorem 5 & 6 (Algorithm Convergence): Prove that the synchronous and asynchronous Q-learning iterations converge to the optimal Q-values of the finite approximate model. The asynchronous convergence relies on the ergodicity of the state process under the exploration policy.
Corollary 1: Combines the approximation and learning results to show that the learned policy $\hat{\pi}$ satisfies $\rho(\hat{\pi}) - \rho \leq \epsilon$ , where $\epsilon$ vanishes as the discretization grid size approaches zero.

5. Significance and Claims

The authors position this work as a solution to open problems in the literature regarding reinforcement learning for average-cost MDPs with continuous spaces.

Relaxation of Assumptions: The paper claims a significant theoretical advance by moving away from Total Variation continuity, which is often too restrictive for practical models, to Weak and Wasserstein continuity. This broadens the class of systems (e.g., those with additive noise or specific dynamics) for which theoretical guarantees can be provided.
Bridging Theory and Practice: By proving that Q-learning converges to the solution of a well-defined finite approximation, the paper provides a rigorous justification for using discretization-based RL in continuous average-cost settings. It clarifies that the "near-optimality" is a direct consequence of the approximation quality, not an artifact of the learning algorithm.
Handling Non-Markovian Quantization: The paper explicitly addresses the technical difficulty that the quantized state process is a POMDP, not an MDP, and provides a convergence proof for asynchronous learning in this setting under average cost criteria, a gap previously noted in the literature (e.g., Wan et al., 2021).

The paper concludes with a numerical case study on a continuous control problem, demonstrating the convergence of the value functions and the reduction of regret as the quantization rate increases, validating the theoretical bounds.