Recursive least squares and quadratic prediction in continuous multistep problems

ABSTRACT

XCS with computed prediction, namely XCSF, has been recently extended in several ways. In particular, a novel prediction update algorithm based on recursive least squares and the extension to polynomial prediction led to significant improvements of XCSF. However, these extensions have been studied so far only on single step problems and it is currently not clear if these findings might be extended also to multistep problems. In this paper we investigate this issue by analyzing the performance of XCSF with recursive least squares and with quadratic prediction on continuous multistep problems. Our results show that both these extensions improve the convergence speed of XCSF toward an optimal performance. As showed by the analysis reported in this paper, these improvements are due to the capabilities of recursive least squares and of polynomial prediction to provide a more accurate approximation of the problem value function after the first few learning problems.

REFERENCES

• 1: Justin A. Boyan and Andrew W. Moore. Generalization in reinforcement learning: Safely approximating the value function. In Advances in Neural Information Processing Systems 7, pages 369--376, Cambridge, MA, 1995. The MIT Press.
• 2: Martin V. Butz and Martin Pelikan. Analyzing the evolutionary pressures in XCS. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2001), pages 935--942, San Francisco, California, USA, 7-11 July 2001. Morgan Kaufmann.
• 3: Martin V. Butz and Stewart W. Wilson. An algorithmic description of XCS. Journal of Soft Computing, 6(3-4):144--153, 2002.
• 4: Graham C. Goodwin and Kwai Sang Sin. Adaptive Filtering: Prediction and Control. Prentice-Hall information and system sciences series, March 1984.
• 5: Simon Haykin, Adaptive filter theory (2nd ed.), Prentice-Hall, Inc., Upper Saddle River, NJ, 1991
• 6: P. L. Lanzi and D. Loiacono. XCSF with neural prediction. In Evolutionary Computation, 2006. CEC 2006. IEEE Congress on, pages 2270--2276, 2006.
• 7: Pier Luca Lanzi , Daniele Loiacono , Stewart W. Wilson , David E. Goldberg, Extending XCSF beyond linear approximation, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068319]
• 8: Pier Luca Lanzi , Daniele Loiacono , Stewart W. Wilson , David E. Goldberg, Extending XCSF beyond linear approximation, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068319]
• 9: Pier Luca Lanzi , Daniele Loiacono , Stewart W. Wilson , David E. Goldberg, Extending XCSF beyond linear approximation, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068319]
• 10: Pier Luca Lanzi , Daniele Loiacono , Stewart W. Wilson , David E. Goldberg, Extending XCSF beyond linear approximation, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068319]
• 11: Pier Luca Lanzi , Daniele Loiacono , Stewart W. Wilson , David E. Goldberg, Generalization in the XCSF Classifier System: Analysis, Improvement, and Extension, Evolutionary Computation, v.15 n.2, p.133-168, Summer 2007 [doi>10.1162/evco.2007.15.2.133]
• 12: Daniele Loiacono , Andrea Marelli , Pier Luca Lanzi, Support vector regression for classifier prediction, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England [doi>10.1145/1276958.1277320]
• 13: C.J.C.H. Watkins. Learning from delayed reward. PhD thesis, 1989.
• 14: Christopher J. C. H. Watkins , Peter Dayan, Technical Note: $\backslash cal\; Q$-Learning, Machine Learning, v.8 n.3-4, p.279-292, May 1992 [doi>10.1007/BF00992698]
• 15: Bernard Widrow , Marcian E. Hoff, Adaptive switching circuits, Neurocomputing: foundations of research, MIT Press, Cambridge, MA, 1988
• 16: Stewart W. Wilson, Classifier fitness based on accuracy, Evolutionary Computation, v.3 n.2, p.149-175, Summer 1995 [doi>10.1162/evco.1995.3.2.149]
• 17: Stewart W. Wilson, Mining Oblique Data with XCS, Revised Papers from the Third International Workshop on Advances in Learning Classifier Systems, p.158-176, September 15-16, 2000
• 18: Stewart W. Wilson, Mining Oblique Data with XCS, Revised Papers from the Third International Workshop on Advances in Learning Classifier Systems, p.158-176, September 15-16, 2000
• 19: Stewart W. Wilson. Classifier systems for continuous payoff environments. In Genetic and Evolutionary Computation -- GECCO-2004, Part II, volume 3103 of Lecture Notes in Computer Science, pages 824--835, Seattle, WA, USA, 26-30 June 2004. Springer-Verlag.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

General Terms:
Algorithms, Performance

Keywords:
learning classifier systems, multistep problems, recursive least squares