CMPUT 676: Optimization and Decision-Making under Uncertainty
Fall 2026
Instructor: Xiaoqi Tan (xiaoqi.tan$\textsf{@}$ualberta.ca)
Location & Time: UComm 2-001, MW 1:00 PM – 2:20 PM
Office hour: After class or by appointment
Course Overview
Many real-world problems require us to make decisions before all relevant information is known. Such uncertainty arises in applications like online advertising, LLM inference serving, renewable energy grids, financial trading, and healthcare. Although these applications may appear quite different, we can study many of them using a common set of optimization models and algorithmic techniques.
In this course, we provide a broad survey of optimization and decision-making under uncertainty across four modules. We begin with a concise introduction to convex optimization in the first module, covering convex sets, functions, canonical problems, Lagrange multipliers, duality, optimality conditions, and core optimization algorithms (gradient descent, Newton’s and barrier methods, and dual ascent). This foundation supports the remaining three parts of the course. In our section on adversarial uncertainty, where future inputs are unknown or chosen adversarially, we study online algorithms and online optimization using competitive ratios and regret across online search, knapsack variants, online matching, online convex/linear programming, and framework developments beyond worst-case analysis. In statistical uncertainty, where outcomes are generated by stochastic processes, we examine multi-armed bandits, sample average approximation, stochastic approximation, and stochastic gradient descent and its adaptive variants. Finally, in strategic uncertainty, where outcomes depend on self-interested decision-makers, we explore game theory, learning in games, and mechanism design, including Nash equilibria, no-regret dynamics, correlated equilibria, auctions, VCG mechanisms, and prophet inequalities.
This course emphasizes conceptual breadth across theoretical computer science, machine learning, economics, operations research, and control theory. Most topics are theoretical, but practical applications and current research will help explain why the models are useful and where their assumptions matter. Students will complete a course project by evaluating selected research papers and carrying out a theoretical, computational, or empirical investigation.
Notes: Advanced undergraduate students are welcome to audit or take the course, subject to administrative approval.
Course Project
The main assignment of this course is to complete a course project which includes a proposal (20%), an in-class presentation (30%), and a final report (50%).
Proposal (20%): You need to select 1-2 papers from this list and prepare a one-page review (covering the main idea, methodologies, and key results of the selected papers) and a separate one-page proposal (containing potentially multiple ideas, such as improvements, alternative approaches, or new discoveries).
Presentation (30%): You will give an in-class presentation based on your paper review and proposal.
Final Report (50%): You are expected to complete this course with an 8-10 page final report. As a research-oriented graduate course, it is up to you to decide the focus of your final report—whether it be a proof of a new theorem, a new implementation, or a new survey—but it must be related to your proposal.
Notes on AI use: You are encouraged to use AI to assist with your course project, but you must remain the primary thinker and author throughout the process. You are responsible for understanding and verifying everything in your proposal, presentation, and final report. Be prepared to explain your work in class, defend your arguments and conclusions, and answer questions about any material you include.
Course Schedule and Readings
| Date | Topics | References and Readings |
|---|---|---|
| Sept. 2 | Lec 1: Overview Course topics; Logistics |
L1-slides |
| Sept. 7 | ||
Convex Optimization: A Brief IntroductionHow do we find good decisions when the objective and constraints are given? |
||
| Sept. 9 | Lec 2: Concepts Convex sets Convex functions Convex problems |
L2-slides BV book: Ch1-Ch4 |
| Sept. 14 | Lec 3: Theory Lagrange multipliers Duality theory Optimality conditions |
L3-slides BV book: Ch5 DB book |
| Sept. 16 | Lec 4: Algorithms Gradient descent Newton’s methods Barrier methods Dual ascent |
L4-slides BV book: Ch9-Ch11 |
Adverarial Uncertainty: Online OptimizationHow do we make decisions sequentially without knowing future inputs? |
||
| Sept. 21 | Lec 5: Online Algorithms (Basics) Ski rental problem Deterministic vs Randomized Yao’s principle |
L5-slides, L5-notes Ski rental |
| Sept. 23 | Lec 6: Online Primal-Dual Time series search $k$-max and $k$-min search Online selection (adversarial) The OPD approach (1st look) |
L6-slides, L6-notes Online search and one-way trading $k$-max and $k$-min search Online selection with convex costs |
| Sept. 28 | Lec 7: Online Knapsack Threshold-based algorithms The OPD approach (2nd look) |
L7-slides, L7-notes Online knapsack and variants Online multiple knapsack |
| Sept. 30 | ||
| Oct. 5 | Lec 8: Online Matching BALANCE + RANKING The OPD approach (3rd look) |
L8-slides, L8-notes AM survey, OPD survey Papers on RANKING: KVV paper; An elegant proof; Economic-based analysis; Randomized OPD analysis |
| Oct. 7 | Lec 9: Online Convex Optimization The Experts problem OCO: intro + algorithms + variants Competitive ratio vs. Regret (1st look) |
L9-slides EH book, FO book |
| Oct. 12 | ||
| Oct. 14 | Lec 10: Online Linear Programming Intro + variants Adversarial inputs vs. Random inputs Competitive ratio vs. Regret (2nd look) |
L10-slides Random-order models Online LP under ROM Online LP under IID |
| Oct. 19 | Lec 11: Beyond Worst-Case Analysis Intro: why + how Learning-augmented algorithms Data-driven algorithm design |
L11-slides Beyond WCA Algorithms with predictions Data-driven algorithm design |
Statistical Uncertainty: Stochastic Optimization, Approximation, and LearningHow do we learn to make better decisions from noisy observations? |
||
| Oct. 21 | Lec 12: Multi-Armed Bandits Intro + variants Stochatic bandits; Algorithms |
L12-slides, L12-notes (Kushagra Chandak) LS book |
| Oct. 26 | Lec 13: Stochastic Optimization (Part 1) Intro + variants Sample average approximation Stochastic approximation |
L13-14-slides Nemirovski et al 2009 SDR book |
| Oct. 28 | Lec 14: Stochastic Optimization (Part 2) Stochastic gradient descent (SGD) Adaptive SGD; Momentum Online vs. Stochastic |
BCN Review Duchi’s lecture notes |
Strategic Uncertainty: Games, Learning, and Mechanism DesignHow does decision-making work in multi-agent games? |
||
| Nov. 2 | Lec 15: Equilibrium Concepts Nash equilibrium (NE) Minimax theorem From NE to correlated equilibrium (CE) Why CS? |
L15-slides AGT book |
| Nov. 4 | Lec 16: Learning in Games The learning setting Zero-sum games: no-regret ⇒ minimax General-sum games: CE and CCE Vector payoffs: Blackwell approachability |
L16-slides Papers mentioned on the slides |
| Nov. 9 | ||
| Nov. 11 | ||
| Nov. 16 | Lec 17: Mechanism Design (Part 1: Offline) Key concepts Vickrey’s auctions; Myerson’s lemma;VCG mechanisms Revenue vs Welfare; Simple vs Optimal |
L17-18-slides AGT book Papers mentioned on the slides |
| Nov. 18 | Lec 18: Mechanism Design (Part 2: Online) Intro + variants Online auctions; Secretary auctions Prophet inequalities Course summary |
Course-Summary-slides Prophet Inequalities: Theory and Methods More TBD… |
Project Presentations |
||
| Nov. 23 | Kaiyuan, Grayson, Shengkuan & Feng, and Andrew & Ethan | |
| Nov. 25 | Ilya & Jaspreet, Haruto, Michael, and Jessica & Matthew | |
| Nov. 30 | Antony, Pranit, Weijia, and Sharvani | |
| Dec. 2 | Erik, Weilin, Zhikai, and Hui | |
| Dec. 7 | Afraz, Larkin, and Chong |