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 including internet advertising, electrical grids with renewable energy, financial trading, healthcare, and AI-enabled decision systems. 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 study optimization and sequential decision-making under three primary forms of uncertainty. We begin with a concise introduction to Convex Optimization, covering convex sets and functions, canonical convex problems, Lagrange multipliers, duality, optimality conditions, and standard algorithms. This foundation supports the three main parts of the course. Adversarial Uncertainty: Future inputs are unknown and may be arbitrary or chosen adversarially. We will study online algorithms and online optimization, using competitive ratios and regret to evaluate decisions made without knowledge of the future. Statistical Uncertainty: Outcomes are generated by an unknown or partially known stochastic process. We will examine stochastic optimization and learning, including Markov decision processes, multi-armed bandits, and stochastic approximation. Strategic Uncertainty: Outcomes depend on the actions and private information of other self-interested decision-makers. We will introduce algorithmic game theory and mechanism design, including equilibrium concepts, auctions, and online mechanisms, and explore related tools such as prophet inequalities.

The material is interdisciplinary, drawing connections to theoretical computer science, machine learning, economics, operations research, and control. While the course is theoretical, its models and methods will be motivated by practical applications and current research. Through a term project, students will critically examine selected research papers and undertake 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