Times: Tuesday and Thursday, 2 – 3:15 pm
Location: Whitaker building, room 1103
Instructor: Vidya K Muthukumar (vmuthukumar8@gatech.edu)
GTA: Seung-Wan Jin (swjin@gatech.edu)
Office Hours: Tuesdays 4-5 pm (in-person, ISyE Main building room 224), Thursdays 4-4:30 pm (virtual)
Prerequisites: undergraduate probability (ECE3077 or equivalent), undergraduate linear algebra (MATH 2551 or equivalent). Mathematical maturity and familiarity with proof-based arguments will be assumed.
Brief description: In many applications of machine learning (ML), data is collected sequentially; moreover, decisions can impact performance both in the present and the future. This class will deal with the design of ML algorithms for real- time decision making, including reinforcement learning. Classical applications in engineering and modern applications in the ML pipeline will both be discussed, but the focus of the course will be foundational — on understanding design principles and the inner workings of algorithms for online decision-making.
Upon successful completion of this course, students will be able to:
- Understand and explain the basic design principles of any online algorithm under diverse assumptions on the environment and reward feedback mechanism.
- Understand how these principles relate to classical concepts in information theory, signal processing, communications, and control theory.
- Assess the efficacy of an online algorithm for an engineering/machine learning application based on its performance guarantees, tractability of implementation, scalability and assumptions made on the environment.
- Appreciate how online algorithms relate to other aspects of the machine learning pipeline.
Grading/Format: The course will be graded as follows:
- Homeworks (top 4/5): 45%
- Midterm (take-home, tentative date Oct 23-24): 25%
- Course project: 30%
Piazza/Canvas: The primary mode of interactive communication in this course will be Piazza. Please sign up at the course page, and monitor Piazza for announcements regarding lecture, homeworks, midterm and project. As is standard, we will also use Canvas to keep track of assignments and share resources related to the class.
Resources and schedule
Lecture schedule:
| Date | Topic | Resources |
| 22 Aug | Logistics and introduction | Introductory slides |
| 24 Aug | Review session on probability and basics of ML | Probability review Basics of ML review |
| 29 Aug | Basics of prediction of an adversarial sequence | Lecture note |
| 31 Aug | The multiplicative weights algorithm | Lecture note |
| 5 Sep | The multiplicative weights algorithm and decision-making using expert advice | Lecture note |
| 7 Sep | No-regret through perturbation | Lecture note |
| 12 Sep | No-regret through perturbation | Lecture note |
| 14 Sep | No-regret through perturbation, introduction to online linear optimization | Lecture note |
| 19 Sep | Online linear optimization | Lecture note |
| 21 Sep | Online convex optimization and stochastic optimization | Lecture note |
| 26 Sep | Overview of adaptive methods in online learning | Lecture note |
| 28 Sep | Online learning and zero-sum game theory | Lecture note |
| 3 Oct | Introduction to limited-information feedback | Lecture note |
| 5 Oct | Limited-information feedback and UCB | Lecture note |
| 12 Oct | Wrapping up UCB; informal discussion of lower bound | Lecture note |
| 19 Oct | Thompson sampling algorithm, Part 1 | Lecture note |
| 26 Oct | Thompson sampling algorithm, Part 2 | Lecture note |
| 31 Oct | Structured bandits: Linear and Gaussian processes | Lecture note |
| 2 Nov | Contextual bandits and adversarial bandits | Lecture note |
| 7 Nov | Dynamic programming and optimal control | Lecture note |
| 9 Nov | Tabular RL with a generative model | Lecture note |
| 14 Nov | Model-based exploration in tabular RL | Lecture note |
| 16 Nov | Value iteration and Q-learning | Lecture note |
| 21 Nov | Policy-based methods | Lecture note |
| 28 Nov | An overview of RL theory with function approximation | Lecture note |
| 30 Nov | Guest lecture (Bo Dai): RL and function approximation in practice | |
| 5 Dec | LAST DAY OF CLASS: Poster presentations OR misc topics (TBD) |
Homework schedule:
Submission due date and self-grade upload deadline are both 11:59 ET. Submission and self-grade upload will be done via Canvas.
| Rough set of topics | Upload date | Due date | Self-grade due date | |
| Homework 0 (optional) | Review of probability and linear algebra | 22 Aug | 29 Aug | N/A |