Broad Area Colloquium For AI-Geometry-Graphics-Robotics-Vision

New Directions in Reinforcement Learning

Michael Kearns
Chief Technology Officer
Syntek Capital

Monday, May 21, 2001, 4:15PM


Within the machine learning community, reinforcement learning has become a standard and successful approach to the problem of learning sequential actions in stochastic environments. The most heavily studied algorithms are value iteration and its generalizations, and the majority of applications use reinforcement learning in control problems. In this talk I will describe some new and rather different algorithms and applications for reinforcement learning.

The new algorithms are designed to allow faster learning and planning in environments with an exponential or infinite number of states, and are based on principles of sparse sampling. They exploit tools from the statistical theory of uniform convergence, and reveal close connections between reinforcement learning and important topics in supervised learning (such as the well-known VC dimension). The algorithms described include a near-optimal solution to the exploration-exploitation trade-off, an algorithm for near-optimal planning with no dependence on the number of states, and reductions of reinforcement learning problems to standard supervised learning scenarios.

The new applications model the interaction between a system and a human user population by a Markov decision process, and use reinforcement learning to optimize the system with respect to this population. In particular, we have investigated this idea extensively in the area of spoken dialogue systems, which use speech recognition and text-to-speech in order to provide users spoken language access to a back-end database. I will describe our design and construction of a reinforcement learning dialogue system, and a carefully controlled large-scale experiment that validates the success of the approach.

About the Speaker

Dr. Michael Kearns is Chief Technology Officer of Syntek Capital, a recently-formed technology investment firm based in Munich and with offices in London, Milan, New York and Tel Aviv. Prior to joining Syntek, Dr. Kearns spent nearly a decade at AT&T Labs Research and AT&T Bell Labs, where he was the head of research in Artificial Intelligence and Machine Learning. Dr. Kearns has led a broad range of foundational and systems work in AI and related areas, including reinforcement learning, computational learning theory, data mining, Bayesian networks, software agents, electronic commerce, and spoken dialogue systems. He received a Ph.D. in Computer Science from Harvard University in 1989, and undergraduate degrees in Mathematics and Computer Science from the University of California at Berkeley. He held postdoctoral fellowships at the Massachusetts Institute of Technology and the International Computer Science Institute. Dr. Kearns' doctoral dissertation received a Distinguished Dissertation Award from the Association for Computing Machinery and was published by MIT Press. He is also the author of over 60 scientific publications on a variety of topics in AI, as well as a textbook on the theory of machine learning.

In addition to AI, Dr. Kearns has interests in cryptography and computer security, theoretical computer science, and game theory. His research web page can be found at


Back to the Colloquium Page