Reinforcement Algorithms Using Functional Approximation for Generalization and their Application to Cart Centering and Fractal Compression

Clifford Claussen, Srinivas Gutta, Harry Wechsler

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$).

Decision regions in the state space (position $x$ vs velocity $v$) for the cart-centering problem, showing the learned control policy.

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.

Comparison of compression time (seconds) versus compression ratio for LearnFrac, JPEG, and FRACCOMP.

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

BibTeX
@inproceedings{claussen1999reinforcement,
  author = {Clifford Claussen and Srinivas Gutta and Harry Wechsler},
  title = {{Reinforcement Algorithms Using Functional Approximation for Generalization and their Application to Cart Centering and Fractal Compression}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1999},
}
Figure