Advanced Design and Analysis of Algorithms
Spring 2007 Topic:
Learning, Games, and Electronic Markets
In many contemporary applications of algorithms, it is necessary
to design algorithms which make better and better decisions
as information is revealed to them over time.
The central theme of this course will be a family of
algorithms for online learning and prediction, and
the applications of these algorithms to game theory
and the design of electronic markets.
The emphasis will
be on mathematical techniques for designing, analyzing,
and applying these algorithms. Topics will include
algorithms for predicting from expert advice, adaptive
game playing, Nash equilibrium and correlated equilibrium,
evolutionary game theory, multi-armed bandit problems,
Markov decision processes, optimal stopping,
pricing and auction theory, universal portfolios, collaborative learning
and reputation mechanisms.
Time and Place
165 Olin Hall
...or by appointment.
Familiarity with basic notions from
algorithms and elementary probability theory, and competence
with reading and writing mathematical proofs. If you have
not taken at least one class in algorithms (at the
level of CS 482) and at least one class in probability
(at the level of Math 471) you should seek permission
from the instructor.
Useful readings for week 8:
- Useful readings for weeks 13, 14:
- Lecture notes for week 9
are now online.
- Homework #4 is now online.
The homework is due at 17:00 on Monday, April 23.
- Useful readings for weeks 11, 12:
- Useful reading for week 10:
- Homework #3 is now online.
The homework is due at 17:00 on April 6.
- Lecture notes for week 8
are now online.
- Useful readings for week 9:
- For basic facts about Kullback-Leibler divergence (a.k.a.
relative entropy), one of the best sources is Cover and Thomas's
classic textbook Elements of Information Theory (sections
2.5 and 2.6, and Lemma 11.6.1).
- The lower bound proof for multi-armed bandits given in class
parallels the argument given in Section 6.9 of Prediction, Learning,
and Games by Cesa-Bianchi and Lugosi. The original source
for this proof is
The non-stochastic multi-armed bandit problem, P. Auer, N. Cesa-Bianchi, Y. Freund, and R. Schapire, SIAM J. Computing 32(1):48-77.
- For the Gittins index, recommended readings are
On Playing Golf with Two Golf Balls, I. Dumitriu, P. Tetali, and P. Winkler, SIAM J. Discrete Math. 16 (2003), 604-615, and On the Gittins Index for Multiarmed Bandits, R. Weber, Annals of Applied Probability 2(4):1024-1033, 1992.
- The non-stochastic multi-armed bandit problem, P. Auer, N. Cesa-Bianchi, Y. Freund, and R. Schapire, SIAM J. Computing 32(1):48-77.
- Adaptive routing with end-to-end feedback: Distributed learning and geometric approaches, B. Awerbuch and R. Kleinberg, STOC 2004.
- Robbing the bandit: Less regret in online geometric optimization against an adaptive adversary, V. Dani and T. Hayes, SODA 2006.
- Chapter 6 (especially sections 6.4-6.7) of
Prediction, Learning, and Games (Cesa-Bianchi and Lugosi).
There is no required textbook for the class, but there are
two recommended texts:
Both of these are on reserve in the Engineering Library.
The content of the course has a greater amount of overlap
with the first book, but we will also cover a few
selected topics from the second.
- Prediction, Learning, and Games
Cesa-Bianchi and Lugosi
- The Theory of Learning in Games
Fudenberg and Levine