CS6700: Reinforcement learning

Course information

• When: Jul-Nov 2018

• Lectures: Slot J

• Where: CS26

• Teaching Assistants: Ajay Kumar Pandey, Nirav Bhavsar, Nithia V

• Office Hours: Wednesday, 3:30pm to 4:30pm

Course Content

Markov Decision Processes

• Finite horizon model

  • General theory

  • DP algorithm

• Infinite horizon model: (1) Stochastic shortest path

  • General theory: Contraction mapping, Bellman equation

  • Computational solution schemes: Value and policy iteration, convergence analysis

• Infinite horizon model: (2) Discounted cost MDPs

  • General theory: Contraction mapping, Bellman equation

  • Classical solution techniques: value and policy iteration

Reinforcement learning

• Stochastic iterative algorithm

  • Convergence result for contraction mappings

• Tabular methods

  • Monte Carlo policy evaluation

  • Temporal difference learning

    • TD(0), TD(lambda)

    • Convergence analysis

  • Q-learning and its convergence analysis

• Function approximation

  • Approximate policy iteration and error bounds

  • Approximate policy evaluation using TD(lambda)

    • The case of linear function approximation

    • Convergence analysis

    • Least-squares methods: LSTD and LSPI

  • Q-learning

• Tentative list of other topics:

  • Policy-gradient and actor-critic algorithms

    • Policy gradient theorem

    • Gradient estimation using likelihood ratios

    • Actor-critic methods: Compatible features, essential features, advantage updating

  • Regret minimization in MDPs

    • Introduction to bandits and UCB algorithm

    • UCRL and PSRL algorithms

The portion on MDPs roughly coincides with Chapters 1 of Vol. I of Dynamic programming and optimal control book of Bertsekas and Chapter 2, 4, 5 and 6 of Neuro dynamic programming book of Bertsekas and Tsitsiklis. For several topics, the book by Sutton and Barto is an useful reference, in particular, to obtain an intuitive understanding. Also, Chapter 6 and 7 of DP/OC Vol II is a useful reference of the advanced topics under RL with function approximation.

Honourable omissions: Neural networks, Average cost models.

Grading

• Project: 35%

• Homeworks: 30% (Best 3 out of 4)

• Quizzes: 30% (15% for each quiz)

• Paper summary: 5%

Important Dates

Paper review

Each individual student is expected to read a paper from a list to be provided soon and submit a 1-page critical review that identifies the strengths and areas of improvement of the paper studied. A paraphrase of the paper content is strongly discouraged. A list of interesting (albeit non-exhaustive) RL papers will be made available soon.

Course project

• The project could be theoretical and/or practical.

• Theoretical projects could involve a novel problem formulation or algorithmic adaptation or extension of existing theory of RL algorithms.

• Practical projects could involve implementation of existing or new RL algorithms on a new benchmark.

• Given the limited timeframe of the course, working out a new result in theory may not be completely feasible and in that case, the project could be converted into an empirical investigation of the algorithms that the students familiarized with, while attempting to formulate/solve a RL problem.

• The report is expected to provide a detailed description of the problem, accompanying algorithms and novel theoretical results or findings from an empirical investigation.

The evaluation would be as follows: 5% for the project proposal, 25% for the final report and 5% for a 15-minute presentation of the work done.

Textbooks/References

• D.P.Bertsekas, Dynamic Programming and Optimal Control, Vol. I, Athena Scientific, 2017

• D.P.Bertsekas, Dynamic Programming and Optimal Control, Vol. II, Athena Scientific, 2012

• D.P.Bertsekas and J.N.Tsitsiklis, Neuro-Dynamic Programming, Athena Scientific, 1996

• R.S.Sutton and A.G.Barto, Reinforcement Learning: An Introduction, MIT Press, 1998. For an updated draft, Click here

Quizzes and homeworks

• Homework 1

• Homework 2

• Homework 3

• Quiz 1

• Quiz 2 (Note: Q3 requires f to be monotone)

Schedule

{}{raw} <p style=“font-size:0.6em;color:grey”> <i> The lectures marked * are 75 minutes long, while the rest are of 50 minutes duration. <i> <p>