This paper will appear in Proceedings of the Seventeenth International Conference on Machine Learning (ICML'00), Stanford, CA, June 29 to July 2, 2000.

Multi-agent Q-learning and Regression Trees for Automated Pricing Decisions

Manu Sridharan
Dept. of Electrical Engineering and Computer Science
MIT 38-401, Cambridge MA 02139 USA
msridhar@mit.edu

Gerald J. Tesauro
IBM Institute for Advanced Commerce
IBM Thomas J. Watson Research Center
P.O. Box 704, Yorktown Heights, NY 10598, USA
tesauro@watson.ibm.com

Abstract:

We study the use of single-agent and multi-agent Q-learning to learn seller pricing strategies in three different two-seller models of agent economies, using a simple regression tree approximation scheme to represent the Q-functions. Our results are highly encouraging - regression trees match the training times and policy performance of lookup table Q-learning, while offering significant advantages in storage size and amount of training data required, and better expected scaling to large numbers of agents. Clear advantages are seen over neural networks, which yield inferior policies and require much longer training times. Our work is among the first to demonstrate success in combining Q-learning with regression trees. Also, with regression trees, Q-learning appears much more feasible as a practical approach to learning strategies in large multi-agent economies.

• Introduction
• Model agent economies
• Single and Multi-agent Q-learning
  • Learning algorithm
  • Results of lookup table learning
  • Difficulties of neural network training
• Q-learning with regression trees
• Results
• Conclusions
• About this document ...