Your browser doesn't support the features required by impress.js, so you are presented with a simplified version of this presentation.

For the best experience please use the latest Chrome, Safari or Firefox browser.

Course References, Links and Random Notes

Title: Probabilistic Reasoning and Reinforcement Learning
Info: ECE 493 Topic 42 - Technical Electives
Instructor: Prof. Mark Crowley, ECE Department, UWaterloo

Website: markcrowley.ca/rlcourse

Course Description :

Introduction to Reinforcement Learning (RL) theory and algorithms for learning decision-making policies in situations with uncertainty and limited information. Topics include Markov decision processes, classic exact/approximate RL algorithms such as value/policy iteration, Q-learning, State-action-reward-state-action (SARSA), Temporal Difference (TD) methods, policy gradients, actor-critic, and Deep RL such as Deep Q-Learning (DQN), Asynchronous Advantage Actor Critic (A3C), and Deep Deterministic Policy Gradient (DDPG). [Offered: S, first offered Spring 2019]

Course Resources

Topics

Primary Textbook : Reinforcement Learning: An Introduction
Small : Richard S. Sutton and Andrew G. Barto, 2018 [SB]

Some topics are not covered in the SB textbook or they are covered in much more detail than the lectures. We will continue to update this list with references as the term progresses.

  1. Motivation & Context [SB 1.1, 1.2, 17.6]
  2. Decision Making Under Uncertainty [SB 2.1-2.3, 2.7, 3.1-3.3]
  3. Solving MDPs [SB 3.5, 3.6, 4.1-4.4]
  4. The RL Problem [SB 3.7, 6.4, 6.5]
  5. TD Learning [SB 12.1, 12.2]
  6. Policy Search [SB 13.1, 13.2, 13.5]
  7. State Representation & Value Function Approximation
  8. Basics of Neural Networks
  9. Deep RL
  10. POMDPs, MARL (skipped in 2020)
  11. MCTS, AlphaGo (mentioned briefly in 2020)

Week 1 - Course Introduction

Topic 1 - Basics of Probability

ECE 657A Youtube Videos

Introductory topics on this from my graduate course ECE 657A are available on youtube and mostly applicable to this course as well.

ECE 108 YouTube Videos

For a very fundamental view of probability from another course of Prof. Crowley you can view the lectures and tutorials for ECE 108

ECE 108 Youtube (look at “future lectures” and “future tutorials” for S20): https://www.youtube.com/channel/UCHqrRl12d0WtIyS-sECwkRQ/playlists

The last few lectures and tutorials are on probability definitions as seen from the perspective of discrete math and set theory.

Likelihood, Loss and Risk

A Good article summarizing how likelihood, loss functions, risk, KL divergence, MLE, MAP are all connected.
https://quantivity.wordpress.com/2011/05/23/why-minimize-negative-log-likelihood/

Probability Intro Markdown Notes

From the course website for a previous year. Some of this we won’t need so much but they are all useful to know for Machine Learning methods in general.

https://compthinking.github.io/RLCourseNotes/

  • Basic probability definitions
  • conditional probability
  • Expectation
  • Inference in Graphical Models
  • Variational Inference

Topic 2.1 - Basic Decision Making Models - Multiarmed Bandits

Week 2
Textbook Sections: [SB 1.1, 1.2, 17.6]

Videos

- Part 1 - Live Lecture May 17, 2021 on Virtual Classroom - View Live Here

Multiarmed Bandit : Solving it via Reinforcement Learning in Python

Thompson Sampling

Topic 3 - Markov Decision Processes

Week 3

Textbook Sections

  • Markov Decision Processes
    [SB 3.0-3.4]
  • Solving MDPs Exactly
    [SB 3.5, 3.6, 3.7]

Playlist:

Individual Videos:

Topic 4 - Dynamic Programming

Week 4
Former title: The Reinforcement Learning Problem
Textbook Sections:[SB 4.1-4.4]

Videos:

Topic 5 - Temporal Difference Learning - Part 1

Week 5 (June 7-11)

Textbook Sections: Selections from [SB chap 5], [SB 6.0 - 6.5]

  • Quick intro to Monte-Carlo methods
  • Temporal Difference Updating

Videos

Parts:

Topic 5.1 - TD Learning - Part 2

Week 6 (June 14-17)

  • SARSA
  • Q-Learning
  • Expected SARSA
  • Double Q-Learning

Videos

Live Lecture/Discussion June 14 4pm

There will be given as a Live Lecture on June 14, 2021 during the 4pm-5:30pm ET Live Session.

According to my youtube analytics, very few people have watched the first two lectures on Temporal Difference Learning or Monte Carlo. But there were a fair number looking at SARSA and QLearning (probably because they are the most famous, fair enough).

test caption
This plot is views per video. I removed the even higher video from the first three weeks.
The first bar is “Dynamic Programming 1” with 76 views. (as of June 11, 2021 5:27pm ET)

I was planning to record a new video (that isn’t on youtube yet) on the following during the live session on Monday:

  • Expected SARSA and Double Q-Learning - these are just modifications of those important algorithms, that have their own benefits. So there will be time to review the essentials of SARSA/QL here at the same time. If there are few people attending or no other discussion here, I will do that.

But… if lots of people show up, we could also:

  • go over something else from earlier in the course they didn’t quite understand
  • or something that they didn’t get a chance to watch yet

So let me know here what topic you would want to go over, or redo live:

  • Maybe it’s all the essentials from TD1 and TD2 that you really need for SARSA and QLearning.
  • Or maybe it’s essentials from some of these earlier topics that people seemed to have skipped like Dynamic Programming, or Mont-Carlo methods.

I’ll check this post on Sunday/Monday and see which option it will be.

Part 1 Review

Week 7 (June 21 - 25)
Go over any questions or open topics from first 6 weeks.

MIDTERM Exam

Week 7
Questions on Midterm (June 23-25) can be on any topics up to this point, Weeks 1-6 inclusive.

(!SKIP!) Topic 5.2 - N-Step TD and Eligibility Traces

optional topic
Textbook Sections: [SB 12.1, 12.2]

Note: Given the pace that people are watching videos, we will drop this topic. It is less essential in the Deep RL era although very interesting theoretically. Calendar will be updated accordingly.

Eligibility traces, in a tabular setting, lead to a significant benefit in training time in additional to the Temporal Difference method.

In Deep RL it is very common to use experience replay to reduce overfitting and bias to recent experiences. However, experience replay makes it very hard to leverage eligibility traces which require a sequence of actions to distribute reward backwards.

Videos:

Other Resources:

Topic 6 - State Representation & Value Function Approximation

Week 8 (June 28- July 2)

VFA Concept

A Value Function Approximation (VFA)
is a necessary technique to use whenever the size of the state of action spaces become too large to represent the value function explicitly as a table. In practice, any practical problem needs to use a VFA.

Benefits of VFA

  • Reduce memory need to store the functions (transition, reward, value etc)
  • Reduce computation to look up values
  • Reduce experience needed to find the optimal value or policy (sample efficiency)
  • For continuous state spaces, a coarse coding or tile coding can be effective

Types of Function Approximators

  • Linear function approximations (linear combination of features)
  • Neural Networks
  • Decision Trees
  • Nearest Neighbors
  • Fourier/ wavelet bases

Finding an Optimal Value Function

When using a VFA, you can use a Stochastic Gradient Descent (SGD) method to search for the best weights for your value function according to experience.
This parametric form the value function will then be used to obtain a greedy or epsilon-greedy policy at run-time.

This is why using a VFA + SGD is still different from a Direct Policy Search approach where you optimize the parameters of the policy directly.

Video:

Other Resources:

Topic 7 - Direct Policy Search

Week 9 (July 5 - 9)
[SB 13.1, 13.2, 13.5]

  • Policy Gradients
  • Actor-Critic

Video:

Policy Gradient Algorithms

Some of the posts used for lecture on July 26.

Actor-Critic Algorithm

Very clear blog post on describing Actor-Critic Algorithms to improve Policy Gradients
https://www.freecodecamp.org/news/an-intro-to-advantage-actor-critic-methods-lets-play-sonic-the-hedgehog-86d6240171d/

Cutting Edge Algorithms

Going beyond what we covered in class, here are some exciting trends and new advances in RL research in the past few years to find out more about.
PG methods are a fast changing area of RL research. This post has a number of the successful algorithms in this area from a few years ago:
https://lilianweng.github.io/lil-log/2018/04/08/policy-gradient-algorithms.html#actor-critic

Topic 8 - Deep Learning Fundamentals

Week 10 (July 12 - July 16)

Assignments

  • Assignment 2 had an extended deadline and was due this Monday July 12. Good work everyone!
  • Assignment 3 is now out and can be looked found at Gitlab: ece493finalassignment

Lectures

This week is a good time to:

  • Catch up on topics from Week’s 8 and 9
  • Review, or learn, a bit about Deep Learning
    • See videos and content from DKMA Course (ECE 657A)
    • This youtube playlist is a targeted “Deep Learning Crash Course” ( #dnn-crashcourse-for-rl ) with just the essentials you’ll need for Deep RL.
    • That course also has more detailed videos on Deep Learning which won’t be specifically useful for ECE 493, but which you can refer to if interested.

Lect 9B - Deep Learning Introduction

In this video go over some of the fundamental concepts that led to neural networks (such as linear regression and logistic regression models), the basic structure and formulation of classic neural networks and the history of their development.

Tags

#deeplearning #introduction #overview

Lect 11A - 1 - Deep Learning Fundamentals

This video goes through a ground level description of logistic neural units, classic neural networks, modern activation functions and the idea of a Neural Network as a Universal Approximator.

Tags

#deeplearning #introduction #dnn-crashcourse-for-rl

Lect 11A - 1.2 - Deep Learning - Gradient Descent

In this video we discuss the nuts and bolts of how training in Neural Networks (Deep or Shallow) works as a process of incremental optimization of weights via gradient descent. Topics discussed: Backpropagation algorithm, gradient descent, modern optimizer methods.

Tags

#deeplearning #detail

Lect11B - 1 - DeepLearning - Fundamentals II

In this video we go over the fundamentals of Deep Learning from a different angle using the approach from Goodfellow et. al.’s Deep Learning Textbook and their network graph notation for neural networks.

We describe the network diagram notation, and how to view neural networks in this way, focussing on the relationship between sets of weights and layers.

Other topics include: gradient descent, loss functions, cross-entropy, network output distribution types, softmax output for classification.

Tags

#deeplearning #introduction #dnn-crashcourse-for-rl

Lect 11B - 2 - Deep Learning - Fundamentals III

This video continues with the approach from Goodfellow et. al.’s Deep Learning Textbook and goes into detail about computational methods, efficiency and defining the measure being used for optimization.

Topics covered include: relationship of network depth to generalization power, computation benefits of convolutional network structures, revisiting the meaning of backpropagation, methods for defining loss functions

Tags

#deeplearning #detail

Lect 11B - 3 - Deep Learning - Regularization

In this lecture I talk about some of the problems that can arise when training neural networks and how they can be mitigated. Topics include : overfitting, model complexity, vanishing gradients, catastrophic forgetting and interpretability.

Tags

#deeplearning #detail #dnn-crashcourse-for-rl

Lect 11B - 4 - Deep Learning - Data Augmentation and Vanishing Gradients

In this video we give an overview of several approaches for making DNNs more usable when data is limited with respect to the size of the network. Topics include data augmentation, residual network links, vanishing gradients.

Tags

#deeplearning #detail #overview

Topic 9 - Deep Reinforcement Learning

Week 12 (July 26-July 30)

  • DQN - new youtube lecture on this topic posted July 26, 2021
  • A2C - live/recorded lecture at 4pm on July 26, 2021 reviewing policy gradients and adding how A2C implements them using Deep Learning

Additional Topics

  • PPO
  • DDPG

A3C/A2C Resources

Topic 11 - Looking Ahead with Tree Search - MCTS and AlphaGo

Week 12 (July 26 - July 30)

  • Monte-Carlo Tree Search (MCTS)
  • How AlphaGo works (combining DQN and MCTS)
  • The Future of Deep RL

Review and End of Classes

Week 13 (Aug 1 - Aug 6)

Final Exam

Week 14 (Aug 12-14)

Primary References for Course

[SuttonBarto2018] - Reinforcement Learning: An Introduction. Book, free pdf of draft available.
http://incompleteideas.net/book/the-book-2nd.html

Additional Resources

Other Useful Textbooks

[Dimitrakakis2019] - Decision Making Under Uncertainty and Reinforcement Learning

http://www.cse.chalmers.se/~chrdimi/downloads/book.pdf
[Ghavamzadeh2016] - Bayesian Reinforcement Learning: A Survey. Ghavamzadeh et al. 2016.
https://arxiv.org/abs/1609.04436

Practical Resources

Deep Q Network vs Policy Gradients - An Experiment on VizDoom with Keras

A nice blog post on comparing DQN and Policy Gradient algorithms such A2C.
https://flyyufelix.github.io/2017/10/12/dqn-vs-pg.html

Open AI Reference Website

This website is a great resource. It lays out concepts from start to finish. Once you get through the first half of our course, many of the concepts on this site will be familiar to you.

Key Papers in Deep RL List

https://spinningup.openai.com/en/latest/spinningup/keypapers.html

Fundamental RL Concepts Overview

The fundamentals of RL are briefly covered here. We will go into all this and more in detail in our course.
https://spinningup.openai.com/en/latest/spinningup/rl_intro.html

Family Tree of Algorithms

Here, a list of algorithms at the cutting edge of RL as of 1 year ago to so, so it’s a good place to find out more. But in a fast growing field, it may be a bit out of date about the latest now.
https://spinningup.openai.com/en/latest/spinningup/rl_intro2.html

Reinforcement Learning Tutorial with Demo on GitHub

This is a thorough collection of slides from a few different texts and courses laid out with the essentials from basic decision making to Deep RL. There is also code examples for some of their own simple domains.
https://github.com/omerbsezer/Reinforcement_learning_tutorial_with_demo#ExperienceReplay

Online Courses

Videos to Watch on RL (Current Research)

Conferences 2020

Old Topics Archive

Other resources connected with previous versions of the course, I’m happy to talk about any of these if people are interested.

Bayes Nets (dropped)

Tools

SamIam Bayesian Network GUI Tool

Other Tools

References

Some videos and resources on Bayes Nets, d-seperation, Bayes Ball Algorithm and more:
https://metacademy.org/graphs/concepts/bayes_ball

Conjugate Priors (dropped)

https://en.wikipedia.org/wiki/Conjugate_prior#Table_of_conjugate_distributions

Primary References for Probabilistic Reasoning (mostly dropped)

[Ermon2019] - First half of notes are based on Stanford CS 228 (https://ermongroup.github.io/cs228-notes/) which goes even more into details on PGMs than we will.

[Cam Davidson 2018] - Bayesian Methods for Hackers - Probabilistic Programming textbook as set of python notebooks.
https://camdavidsonpilon.github.io/Probabilistic-Programming-and-Bayesian-Methods-for-Hackers/#contents

[Koller, Friedman, 2009] Probabilistic Graphical Models : Principles and Techniques
The extensive theoretical book on PGMs.
https://mitpress.mit.edu/books/probabilistic-graphical-models