Course on Algorithms and Uncertainty

In many real-world settings, algorithms have to make decisions under uncertainty. This uncertainty might stem from incomplete information, changing environments, or unpredictable events. In this course, we study how to mathematically model uncertainty, how to design algorithms that make decisions under uncertainty and how to analyze them rigorously, providing provable performance guarantees.

The course is divided into three main areas: online algorithms, where no prior information about inputs is known; stochastic optimization, which assumes some probabilistic knowledge about the inputs; and online learning, where knowledge is gradually gained from experience.

I frequently teach this course at the University of Bonn. Lecture notes and video recordings are available below.

There is a Welcome Video on YouTube and also a playlist of all videos on YouTube.

Current Set of Lectures

  1. Ski rental
    [Most Recent Lecture Notes] [Lecture Notes for Video] [Video on YouTube]
  2. Online Steiner Tree
    [Most Recent Lecture Notes] [Lecture Notes for Video] [Video on YouTube]
  3. Online Set Cover: Introduction and LP Duality
    [Most Recent Lecture Notes] [Lecture Notes for Video] [Video on YouTube]
  4. Online Set Cover: Fractional Algorithm
    [Most Recent Lecture Notes] [Lecture Notes for Video] [Video on YouTube]
  5. Online Set Cover: Randomized Rounding and Extensions
    [Most Recent Lecture Notes] [Lecture Notes for Video] [Video on YouTube]
  6. Yao’s Principle
    [Most Recent Lecture Notes] [Lecture Notes for Video] [Video on YouTube]
  7. Online Bipartite Matching
    [Most Recent Lecture Notes] [Lecture Notes for Video] [Video on YouTube]
  8. Markov Decision Processes
    [Most Recent Lecture Notes] [Lecture Notes for Video] [Video on YouTube]
  9. Optimal Stopping: Known Distributions
    [Most Recent Lecture Notes] [Lecture Notes for Video] [Video on YouTube]
  10. Optimal Stopping: Secretary Problem
    [Most Recent Lecture Notes] [Lecture Notes for Video] [Video on YouTube]
  11. Online Steiner Tree in Probabilistic Models
    [Most Recent Lecture Notes] [Lecture Notes for Video] [Video on YouTube]
  12. Pandora's Box
    [Most Recent Lecture Notes] [Lecture Notes for Video] [Video on YouTube]
  13. Adaptivity Gap
    [Most Recent Lecture Notes] [Lecture Notes for Video] [Video on YouTube]
  14. Stochastic Two-Stage Set Cover
    [Most Recent Lecture Notes] [Lecture Notes for Video] [Video on YouTube]
  15. Stochastic Two-Stage Steiner Tree
    [Most Recent Lecture Notes] [Lecture Notes for Video] [Video on YouTube]
  16. Learning for Pandora’s Box
    [Most Recent Lecture Notes]
  17. Stochastic Multi-Armed Bandits
    [Most Recent Lecture Notes] [Lecture Notes for Video] [Video on YouTube]
  18. No-Regret Learning: Experts
    [Most Recent Lecture Notes] [Lecture Notes for Video] [Video on YouTube]
  19. No-Regret Learning: Multi-Armed Bandits 1
    [Most Recent Lecture Notes] [Lecture Notes for Video] [Video on YouTube]
  20. No-Regret Learning: Multi-Armed Bandits 2
    [Most Recent Lecture Notes] [Lecture Notes for Video] [Video on YouTube]
  21. No-Regret Learning: Lower Bound
    [Most Recent Lecture Notes] [Lecture Notes for Video] [Video on YouTube]
  22. Basics of Online Convex Optimization
    [Most Recent Lecture Notes] [Lecture Notes for Video] [Video on YouTube]
  23. Basics of Online Convex Optimization
    [Most Recent Lecture Notes] [Lecture Notes for Video] [Video on YouTube]
  24. Max-Flow via Experts
    [Most Recent Lecture Notes] [Lecture Notes for Video] [Video on YouTube]
  25. Bandits with Knapsacks
    [Most Recent Lecture Notes]
  26. No-Regret Learning and Zero-Sum Games
    [Most Recent Lecture Notes] [Lecture Notes for Video] [Video on YouTube]

Other Lectures