Times: Tuesday and Thursday, 2 – 3:15 pm
Location: Whitaker building, room 1103
Instructor: Vidya K Muthukumar
Office Hours: Tuesdays 3:30-4:30 pm (tentative), 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 20-21): 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 |
| 23 Aug | Logistics and introduction | |
| 25 Aug | Review session on probability and basics of ML | Probability review Basics of ML review |
| 30 Aug | Basics of prediction of an adversarial sequence | Lecture note |
| 1 Sep | The multiplicative weights algorithm | Lecture note |
| 6 Sep | The multiplicative weights algorithm and decision-making using expert advice | Lecture note |
| 8 Sep | No-regret through perturbation | Lecture note |
| 13 and 15 Sep | No-regret through perturbation, continued | Lecture note |
| 20 Sep | Online linear optimization | |
| 22 Sep | Online convex optimization and stochastic optimization | |
| 27 Sep | Overview of adaptive methods in online learning | |
| 29 Sep | Introduction to limited-information feedback | |
| 4 Oct | Limited-information feedback and UCB | |
| 6 Oct | Limited-information feedback and UCB, continued | |
| 11 Oct | Wrapping up UCB; informal discussion of lower bound | |
| 13 Oct | Thompson sampling algorithm, Part 1 | |
| 20 Oct (asynchronous due to midterm) | Thompson sampling algorithm, Part 2 | |
| 25 Oct | Structured bandits: Linear and Gaussian processes | |
| 27 Oct | Contextual bandits | |
| 1 Nov | Dynamic programming and optimal control | |
| 3 Nov | Tabular RL with a generative model | |
| 8 Nov | Model-based exploration in tabular RL | |
| 10 Nov | Value iteration and Q-learning | |
| 15 Nov | Policy-based methods | |
| 17 Nov | An overview of RL theory with function approximation | |
| 22 Nov | Bonus lecture: RL and function approximation in practice | |
| 29 Nov (asynchronous due to instructor travel) | Online learning and zero-sum game theory | |
| 1 Dec (asynchronous due to instructor travel) | Online learning and non-zero-sum game theory | |
| 6 Dec | LAST DAY OF CLASS: Poster presentations |
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 | 23 Aug | 30 Aug | N/A |
| Homework 1 | Fundamentals of adversarial prediction | 1 Sep | 14 Sep | 21 Sep |