Announcements
- 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.
- Useful readings for week 8:
- 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).
- Lecture notes for week 7
are now online.
- Lecture notes for week 6 are still under construction.
However, an overview of the content of week 6 can be found
in Sections 3.5 and 3.6 of the paper by Arora, Hazan, and
Kale, listed first among the following readings. The
remaining papers on the list go into greater depth on
the two main topics of Week 6, namely boosting (the
second and third papers on the list) and hard-core
sets (the fourth and fifth papers on the list).
- The
Multiplicative Weights Update Method: A Meta Algorithm and Applications,
S. Arora, E. Hazan, and S. Kale, preprint. (This preprint is a
rough draft only. Some sections have not even been written yet!)
- A Decision-Theoretic Generalization of On-line Learning and an
Application to Boosting, Y. Freund and R. E. Schapire, Journal of Computer and System Sciences 55(1):119-139, 1997.
-
Boosting a Weak Learning Algorithm By Majority, Y. Freund,
Information and Computation 121(2):256-285, 1995.
- Hardcore Distributions for Somewhat Hard Problems, R. Impagliazzo, FOCS 1995.
- Boosting and Hard-Core Sets, A. Klivans and R. Servedio, FOCS 1999.
- Homework #2 is now online.
The homework is due March 9.
- Lecture notes for week 5
(excluding Friday's lecture) are now online.
- Useful reading for Week 6:
- The
Multiplicative Weights Update Method: A Meta Algorithm and Applications,
S. Arora, E. Hazan, and S. Kale, preprint. (This preprint is a
rough draft only. Some sections have not even been written yet!)
- A Decision-Theoretic Generalization of On-line Learning and an
Application to Boosting, Y. Freund and R. E. Schapire, Journal of Computer and System Sciences 55(1):119-139, 1997.
-
Boosting a Weak Learning Algorithm By Majority, Y. Freund,
Information and Computation 121(2):256-285, 1995.
- Hardcore Distributions for Somewhat Hard Problems, R. Impagliazzo, FOCS 1995.
- Boosting and Hard-Core Sets, A. Klivans and R. Servedio, FOCS 1999.
- Lecture notes
for Week 3
and Week 4 have been posted.
- Solutions for Homework #1
have been posted.
- Useful reading for Weeks 3 and 4:
- Sections 7.4-7.8 of Prediction, Learning, and Games (Cesa-Bianchi and Lugosi).
- Chapter 8 of The Theory of Learning in Games (Fudenberg and Levine).
- Regret in the On-line Decision Problem,
D. Foster and R. Vohra, Games and Economic Behavior 29: 7-36, 1999.
- A Simple Adaptive Procedure Leading to Correlated Equilibrium S. Hart and A. Mas-Colell, Econometrica 68: 1127-1150, 2000.
- Existence of Correlated Equilibria S. Hart and D. Schmeidler, Mathematics of Operations Research 14:18-25, 1989.
- Computing correlated equilibria in multiplayer games C. Papadimitriou, Proceedings of STOC 2005, 49-56.
- Lecture notes from Week 2 are now available online.
- Useful reading for Week 2:
- Homework #1 is due on Friday,
February 2.
- Lecture notes from Week 1 are now available online.
-
Useful reading for Week 1: