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
TCSEQ 201
http://robotics.stanford.edu/ba-colloquium/
Abstract
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 http://www.cis.upenn.edu/~mkearns.
Contact: bac-coordinators@cs.stanford.edu
Back to the Colloquium Page