Comments on the Origin and Application of Markov Decision Processes

R a European mathematician who had spent many years on the theoretical study of Markov decision processes visited me and inquired about the range of application. I replied that I knew of very few practical applications and that I had found only one in the course of my career that I considered really successful. He was somewhat taken aback until we discussed the problem of the very large data requirements imposed by the Markov decision process formulation. Of course, he then asked me how these data requirements were met in my one successful application, and we spent the balance of his visit in discussing this application. I was reminded of this episode when Dr. Martin Puterman asked me a few months ago if I would comment on the origins of Markov decision processes. It occurred to me that the story of my one successful application might suit his purposes and be as interesting to the conference participants as it was to my European visitor. You see, my one successful application was the original application that sparked my interest in this whole research area. The story begins about twenty years ago, when I was a graduate student in electrical engineering at M.I.T., working part time with the Operations Research Group of Arthur D. Little, Inc. It was a period of great excitement in the Operations Research Group, for the first commercial applications were being performed with success, and there was considerable intellectual stimulation arising from many discussions of the fundamentals of the subject. Our mentor was Dr. George Kimball, who taught me and many of my colleagues the most valuable lessons I ever learned on the subject of operations research. The group had an important relationship with Sears, Roebuck and Company and helped that firm with a number of its problems. When I became involved, Sears’ management was becoming increasingly concerned with the effectiveness of the operation by which they sent catalogs to present and prospective customers. There were many options. A customer could receive up to fourteen individual mailings a year, ranging from the general catalog to individual sales fliers. Or, he might receive any subset of these mailings. The cost of any particular mailing was easily determined, but what was the benefit? To answer that question, let me take you back with me to a grey Chicago day, twenty years ago, when I first saw the Sears’ catalog information system. It was an unforgettable sight. Imagine, if you will, two or three acres of green steel filing cabinets. Each cabinet contained steel Addressograph plates, about four inches square. Each plate had a stencil for printing the customer’s name and address, and, as inserts, three small cards with several punched holes. These holes provided a limited summary over three seasons of the customer’s purchasing history as a Sears mail order client. About 100 young women continually circulated among the filing cabinets. They were supplied with one copy of the customer’s latest mail order, and it was their job to update the punches on the cards to incorporate the effect of the order. The information recorded was highly quantized in terms of the number and amount of the orders. The key to the system was the machine that used the steel plates to print labels for the catalog to be mailed. A drawer of plates was stacked into the machine. The machine examined the punched holes in the cards on each plate and determined, according to wired-board logic, whether this pattern of holes qualified the customer to receive the particular catalog being distributed at that time. If the pattern was favorable, a label was printed; otherwise, not. Thus, for example, the management could decide to send the general catalog only to customers who purchased more than $20 during the present season. By wiring the machine appropriately, this decision was implemented simply by passing every drawer of cards through the labeling machine. In making this decision, the management had traditionally looked at the direct profit to be expected from a customer as measured by the difference between the marginal profit on his purchases and the cost of sending him the catalog. As we examined the operation, we began to wonder whether it might be profitable to send catalogs, not just on the basis of the profit they might produce during the present season, but also for the impact they might have in moving the customer into more profitable categories in the future. We decided to model this system by what has come to be known as a Markovian decision process. Each customer’s state was described by his purchase history; there were a