Abstract
This paper presents two novel reinforcement learning (RL) algorithms, QLVQ and Quad-Q-learning, designed to mitigate the "curse of dimensionality" inherent in traditional Q-learning. By integrating functional approximation techniques—specifically Labeled Vector Quantization and quad-tree partitioning—the authors demonstrate that RL agents can achieve significantly faster convergence and superior generalization. These methods are evaluated on a time-optimal cart-centering control problem and a fractal image compression task, showing substantial improvements over standard tabular methods and conventional compression standards like JPEG at high ratios.
Introduction
Standard Q-learning is a robust "off-policy" reinforcement learning method. However, its primary limitation is the treatment of state-action pairs as independent entities. In continuous or high-dimensional state spaces, this lack of generalization forces the algorithm to learn every state variation from scratch, leading to slow convergence. This paper addresses two critical challenges: the exploration-exploitation trade-off and the difficulty of scaling RL to complex environments where interpolation between experiences is necessary.
Proposed Methods
QLVQ: Q-learning with Labeled Vector Quantization
To move beyond rigid state tables, the authors propose QLVQ. This method uses Labeled Vector Quantization (LVQ) to tessellate the state space using a set of "prototypes." * Mechanism: When an agent encounters a state, it identifies the nearest prototype to determine the optimal action. * Innovation: Unlike static discretization, QLVQ dynamically repositions these prototypes during the learning process. This allows the algorithm to "interpolate" between neighboring regions, creating smooth decision boundaries and reducing the total number of states required for effective control.
Quad-Q-learning
Quad-Q-learning is a hierarchical RL approach tailored for data structures like quad-trees.
- Mechanism: The agent's actions are structural decisions: whether to "split" a data block into four sub-blocks or "not split" and apply a specific transform (such as an affine transform).
- Innovation: By framing image compression as a cost-minimization problem, the agent uses linear regression to estimate the relationship between block variance and coding cost. This recursive "look-ahead" allows the agent to optimize the entire tree structure by summing the expected costs of future child blocks.
Experimental Evaluation
Cart Centering Simulation
The algorithms were first tested on a classic control problem: centering a cart on a frictionless track in minimal time. The state space consists of position ($x$) and velocity ($v$).
Empirical results highlighted the efficiency of functional approximation. While standard Q-learning failed to converge after 567 cycles, QLVQ converged in only 176 cycles. Furthermore, when the state grid was doubled in size, QLVQ maintained a low failure rate of 1.8%, compared to 11.9% for the standard method, demonstrating significantly better robustness to scaling.
Fractal Image Compression
The Quad-Q-learning method (referred to as "LearnFrac") was applied to the standard LENA image benchmark to evaluate efficiency and quality.
The agent learned to partition images based on local attributes like variance. LearnFrac outperformed JPEG at high compression ratios (above 11:1) in terms of Peak Signal-to-Noise Ratio (PSNR). As shown in the performance data, LearnFrac also demonstrated superior computational speed compared to existing fractal compression algorithms like FRACCOMP.
Conclusion
The integration of functional approximation into reinforcement learning provides a powerful solution to the scalability issues of tabular Q-learning. By using adaptive discretization (QLVQ) and hierarchical cost-estimation (Quad-Q-learning), the authors successfully applied RL to diverse domains ranging from mechanical control to image processing. Future work may involve establishing theoretical convergence bounds for moving-prototype systems and extending these hierarchical approaches to other complex data structures.
Summary updated