Abstract: In this paper, we propose an approximate relative value learning (ARVL) algorithm for non-parametric MDPs with continuous state space and finite actions and average reward criterion. It is a sample-based algorithm that combines kernel density estimation with nearest-neighbor regression to learn optimal policies without requiring state-space discretization.
Introduction
Markov Decision Processes (MDPs) serve as the standard mathematical framework for sequential decision-making. However, real-world applications—ranging from robotics to financial modeling—often involve continuous state spaces and long-term average reward objectives. Traditional approaches to these problems typically rely on "quantizing" or discretizing the state space into a finite grid. This approach inevitably leads to the "curse of dimensionality," where the number of grid points grows exponentially with the state space's dimensions.
Furthermore, the average reward criterion is notoriously more difficult to analyze than the discounted reward case. In discounted MDPs, a fixed discount factor ensures that value iteration algorithms act as contractions, guaranteeing convergence. In the average reward setting, stability depends on the complex underlying dynamics of the system, requiring more sophisticated algorithmic structures to ensure provable convergence.
The ARVL Algorithm
Researchers from the University of Southern California have introduced Approximate Relative Value Learning (ARVL), the first algorithm for continuous-state MDPs with average reward criteria that provides provable convergence without resorting to fixed-grid discretization. The ARVL algorithm operates through a non-parametric pipeline designed to handle unknown transition dynamics directly from samples.
Core Components
- Sampling and Density Estimation: Instead of requiring a known transition model, ARVL uses samples to estimate the probability of moving from one state to another. It employs Kernel Density Estimation (KDE), specifically using Gaussian kernels, to approximate the transition density $p(y|x,a)$.
- Approximate Bellman Operator: The algorithm applies a modified Bellman equation that integrates these estimated densities to update the value function.
- Relative Value Iteration: To maintain mathematical stability in the average-reward regime, the algorithm performs "relative" updates. By subtracting a reference value (such as the minimum value) at each step, it keeps the iterates bounded and prevents the values from diverging to infinity.
- Nearest Neighbor Regression: To generalize from discrete sample points back to the entire continuous state space, ARVL utilizes $n$-Nearest Neighbors ($n$-NN) regression. This ensures the value function remains smooth (Lipschitz continuous) across the domain.
Theoretical Foundations
The primary theoretical contribution of this work is proving that this sequence of random, approximate steps behaves as a "random contraction." The authors utilize a stochastic dominance argument to show that the error of the algorithm is bounded by a specific type of Markov chain that eventually reaches a steady state. This proves that the algorithm will converge to the optimal value function with high probability, provided the function approximation method (like $n$-NN) is "non-expansive"—meaning it does not amplify existing data errors.
Experimental Validation
The ARVL algorithm was validated using the Machine Replacement Problem, a classic benchmark where a machine's condition degrades continuously over time. The agent must decide whether to perform maintenance (low cost) or replace the machine (high one-time cost) to maximize the long-term average reward.
As shown in Figure 1, the estimated value function tracks the analytical "ground truth" with high precision. The experiments demonstrated that increasing the number of next-state samples ($M$) significantly smooths the density estimation (as seen in Figure 2), leading to a more accurate and stable value function. The results confirm that as the number of states sampled ($N$) and neighbors ($n$) increase, the algorithm's output converges to the optimal solution.
Conclusion and Future Work
ARVL represents a significant advancement in Reinforcement Learning by breaking the reliance on state-space discretization for average-reward problems. While the algorithm provides rigorous convergence guarantees, it still faces the "dimensionality tax" common to nearest-neighbor methods, where the required sample size grows with the dimension of the state space. Future research will focus on scaling these methods to higher-dimensional environments, potentially by integrating deep neural networks while maintaining the same level of theoretical rigor.
Summary updated