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 No Class (Statutory Holiday)
Convex Optimization: A Brief Introduction
How 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 Optimization
How 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 No Class (Statutory Holiday)
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 No Class (Statutory Holiday)
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 Learning
How 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 Design
How 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 No Class (Reading Week Break)
Nov. 11 No Class (Reading Week Break)
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