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 making decisions before all relevant information is known. Such uncertainty arises in applications such as internet advertising, electrical grids with renewable energy, financial trading, and healthcare. Although these applications may appear quite different, many can be studied using a common set of optimization models and algorithmic techniques.

In this research-oriented course, we provide a broad survey of optimization and sequential decision-making under three primary forms of uncertainty, emphasizing conceptual breadth across key techniques rather than deep mechanical derivations. We begin with a concise introduction to convex optimization, 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 three main parts of the course. Adversarial uncertainty: Future inputs are unknown and may be arbitrary or chosen adversarially; we study online algorithms and online optimization using competitive ratios and regret, covering online search, knapsack variants, online matching, online convex optimization, online linear programming, and framework developments beyond worst-case analysis. Statistical uncertainty: Outcomes are generated by a stochastic process; we examine multi-armed bandits, stochastic approximation, and stochastic gradient descent and its adaptive variants. Strategic uncertainty: Outcomes depend on the actions and private information of self-interested decision-makers; we explore algorithmic game theory and mechanism design, including Nash equilibria, auctions, VCG mechanisms, and prophet inequalities.

The course draws on theoretical computer science, machine learning, economics, operations research, and control. The emphasis is theoretical, but practical applications and current research will help explain why the models are useful and where their assumptions matter. Students are expected to complete a course project: study selected research papers and carry out a theoretical, computational, or empirical investigation related to the course.

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