Machine Learning Summer School 2006 - Taipei

Reinforcement Learning Theory

author:John Langford, Yahoo! Research
published: Feb. 25, 2007, recorded: July 2006, views: 908

Slides

Slides
0:05	Modern Reinforcement Learning Theory
0:22	Reinforcement Learning is Always Relevant
2:47	The answer to: \"Is this an RL problem?\" is always \"yes\"
6:22	Outline
7:08	What is a sample complexity guarantee?
12:04	The E3 guarantee
17:23	E3 Theorem Statement
29:03	The Known(h) MDP
31:10	The Known(h) MDP 01
32:07	The Known(h) MDP 02
32:17	The Known(h) MDP 03
33:05	The Unknown(h) MDP
36:01	Dynamic Program
41:46	E3(h) Explicit Explore or Exploit Algorithm
46:04	The proof uses (5!) MDPs
48:05	Proof Sketch:
55:48	R-Max(h) Modification
61:00	Delayed Q-learning
64:35	Outline
64:57	The Limits of Sample Complexity: A lower bound
65:36	Proof
68:43	Implications
69:35	Attempt 1: Factored - E3
73:57	Attempt 2: Metric - E3
79:21	Do we really want the guarantee these algorithms provide?

Related content

Visitors who watched this lecture also watched...

04:58:57

Reinforcement Learning
1395 views - Satinder Singh, 2006

05:47:38

Introduction to Reinforcement Learning
872 views - Csaba Szepesvari, 2008

19:38

Introduction to Reinforcement Learning and Bayesian learning
1013 views - Mohammad Ghavamzadeh, 2007

05:09:25

Reinforcement Learning
290 views - Peter L. Bartlett, 2002

04:59:19

Machine Learning, Probability and Graphical Models
18419 views - Sam Roweis, 2006

01:31:32

Reinforcement Learning
202 views - Douglas Aberdeen, 2005

01:20:19

Policy-gradient Reinforcement Learning
437 views - Douglas Aberdeen, 2006

01:00:47

Gaussian Process Basics
12603 views - David MacKay, 2006

03:54:31

Support Vector Machines
12745 views - Chih-Jen Lin, 2006

05:02:23

Statistical Learning Theory
7988 views - John Shawe-Taylor, 2004

Report a problem or upload files

If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.

Lecture popularity: You need to login to cast your vote.

Watch videos: (click on thumbnail to launch)

Part 1 1:21:22 Flash video

!NOW PLAYING

Part 2 0:54:20 Flash video

Description

The tutorial is on several new pieces of Reinforcement learning theory developed in the last 7 years. This includes:
1. Sample based analysis of RL including E3 and sparse sampling.
2. Generalization based analysis of RL including conservative policy iteration and RL-to-Classification reductions.
For each of these forms of theory, we cover the basic results and cover the weaknesses and strengths of the approach in context.