Grant: Discovery Grants Program - Individual
University of Alberta
$62,000.00
Temporal-difference algorithms for reinforcement learning and artificial intelligence
FY 2016-17
Summary
Predicting long-term aspects of one's input stream is a ubiquitous problem facing intelligent agents both natural and artificial. You predict the weather on the weekend to plan your barbecue party, you predict the long-term trend of the stock market when you decide to invest, and you predict where the tennis ball will be when you move to meet intercept it. As you watch the tennis ball travel through the air you continually make a series of predictions and learn to make more accurate predictions in the future. Simultaneously, you predict how your weight will shift, how your limbs and racket will move, your probability of returning the ball effectively, and hundreds if not thousands of other things. Your brain performs an amazingly dense parallel computation using rich sensory input to make large numbers of predictions many times a second while simultaneously updating them to tune them to the current situation. We do all this effortlessly, so it is easy to overlook the enormous demands on our information processing system. The learning algorithms that we employ to do all this are of course not completely known, but the closest analogs in the field of artificial intelligence-the learning methods most suited to the special engineering requirements of making these kinds of predictions efficiently-are known as temporal difference (TD) learning algorithms and are the focus of this research project.
The proposed research pushes the frontiers of the theory, practice, and application of TD learning algorithms. Part of the challenge is to learn with both statistical efficiency and computational efficiency, and to balance the two when necessary. The computational complexity of existing TD methods scales linearly with both the number of predictions made and the number of features that are used to make them. Each prediction-feature pair is assigned a numerical weight that is adjusted by the learning process. At each time, the weights of all the features present at that time are added up to produce the prediction that approximates the correct answer. One complication is that the correct prediction depend on what you do. If you swing quickly you may intercept the tennis ball whereas if you are slow you are more likely to miss it. A long standing problem that we have recently solved is that all earlier linear-complexity TD methods were unable to learn about a way of acting unless you actually acted in exactly that way. This is inefficient in that the data should in principle inform the predictions for all ways of acting that are similar to what you did. This is called ""the problem of off-policy learning,"" and it has been open from 1995 until we started to solve it in 2009.
Our solution, however, is only the beginning. It has many refinements and generalizations that remain to be done, and it opens up new opportunities and capabilities, including hybrid methods of various kinds. We plan to develop TD learning into a very general and capable form that may someday be able to do all that people and animals can do. One way we test our algorithms is by running them on small robots to see if they can learn effectively at scale and in real time. Our largest demonstration to date updates and learns 6000 predictions, each a function of more than 6000 features, every 1/10th of a second. This robot learns more diverse predictive facts about its sensorimotor interaction with the world than possibly any other robot.
If successful, this research will affect and enhance all the different areas in which decision making is being automated, including communications networks, financial markets, self-driving cars, user interfaces, environmental controls for homes and factories, power systems, and control systems of all kinds.
Program
Discovery Grants Program - Individual
Recipient
Location
Alberta, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
RGPIN-2014-06224
Name nom
Sutton, Richard
Department département
Computing Science
Organization id
9
Institution établissement
University of Alberta
Province en
Alberta
Province fr
Alberta
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2016
Competition year année de concours
2014
Award amount
62000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
1207
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Information, computer and communication technologies
Area of application fr
Technologie de l'information, des ordinateurs et des réseaux de communications
Research subject code
2805
Research subject group en
Artificial intelligence
Research subject group fr
Intelligence artificielle
Research subject en
Learning and inference theories
Research subject fr
Théories de l'apprentissage et l'inférence
Partie
3
Nb partie
5
Application title
Temporal-difference algorithms for reinforcement learning and artificial intelligence
Keyword
NSERC
Application summary
Predicting long-term aspects of one's input stream is a ubiquitous problem facing intelligent agents both natural and artificial. You predict the weather on the weekend to plan your barbecue party, you predict the long-term trend of the stock market when you decide to invest, and you predict where the tennis ball will be when you move to meet intercept it. As you watch the tennis ball travel through the air you continually make a series of predictions and learn to make more accurate predictions in the future. Simultaneously, you predict how your weight will shift, how your limbs and racket will move, your probability of returning the ball effectively, and hundreds if not thousands of other things. Your brain performs an amazingly dense parallel computation using rich sensory input to make large numbers of predictions many times a second while simultaneously updating them to tune them to the current situation. We do all this effortlessly, so it is easy to overlook the enormous demands on our information processing system. The learning algorithms that we employ to do all this are of course not completely known, but the closest analogs in the field of artificial intelligence-the learning methods most suited to the special engineering requirements of making these kinds of predictions efficiently-are known as temporal difference (TD) learning algorithms and are the focus of this research project.
The proposed research pushes the frontiers of the theory, practice, and application of TD learning algorithms. Part of the challenge is to learn with both statistical efficiency and computational efficiency, and to balance the two when necessary. The computational complexity of existing TD methods scales linearly with both the number of predictions made and the number of features that are used to make them. Each prediction-feature pair is assigned a numerical weight that is adjusted by the learning process. At each time, the weights of all the features present at that time are added up to produce the prediction that approximates the correct answer. One complication is that the correct prediction depend on what you do. If you swing quickly you may intercept the tennis ball whereas if you are slow you are more likely to miss it. A long standing problem that we have recently solved is that all earlier linear-complexity TD methods were unable to learn about a way of acting unless you actually acted in exactly that way. This is inefficient in that the data should in principle inform the predictions for all ways of acting that are similar to what you did. This is called ""the problem of off-policy learning,"" and it has been open from 1995 until we started to solve it in 2009.
Our solution, however, is only the beginning. It has many refinements and generalizations that remain to be done, and it opens up new opportunities and capabilities, including hybrid methods of various kinds. We plan to develop TD learning into a very general and capable form that may someday be able to do all that people and animals can do. One way we test our algorithms is by running them on small robots to see if they can learn effectively at scale and in real time. Our largest demonstration to date updates and learns 6000 predictions, each a function of more than 6000 features, every 1/10th of a second. This robot learns more diverse predictive facts about its sensorimotor interaction with the world than possibly any other robot.
If successful, this research will affect and enhance all the different areas in which decision making is being automated, including communications networks, financial markets, self-driving cars, user interfaces, environmental controls for homes and factories, power systems, and control systems of all kinds.