Course Outline for CS 683, Spring 2007

- Prediction from expert advice
- Prediction, regret, and game-theoretic equilibria
- The weighted majority algorithm
- Solving zero-sum games by adaptive game playing
- Algorithmic consequences of zero-sum games:
Yao's lemma, LP duality
- Log-loss and forecasting
- Calibration
- Blackwell's approachability theorem
- Internal regret
- Correlated equilibrium
- Learning processes which converge to correlated equilibrium
- Deterministic calibration
- Learning processes which converge to Nash equilibrium

- Other applications
- PAC learning, boosting
- Approximation algorithms
- AdWords
- The XOR lemma

- Learning with many experts
- The Hannan-Kalai-Vempala algorithm
- Zinkevich's algorithm
- Universal portfolios

- Learning and evolution
- Evolutionary game theory I: Evolutionarily stable strategies
- Evolutionary game theory II: Replicator dynamics
- Evolvability

- Multi-armed bandit problems
- Stochastic formulations
- Markov decision processes
- Golfing with two golf balls
- Multi-armed bandits and Gittins indices
- Logarithmic-regret algorithms: Lai-Robbins, UCB1

- Non-stochastic formulations
- The Exp3 algorithm
- Information-theoretic lower bound
- Bandits with many arms I: barycentric spanners and
online linear optimization
- Bandits with many arms II: anytime bandit algorithms

- Applications
- Recommendation systems, trust, and collaborative learning
- Online pricing I: Incomplete learning in the long run
- Online pricing II: Upper bounds on regret
- Online pricing III: Lower bounds on regret

- Electronic markets
- Offline auction mechanisms
- Basic mechanism design definitions
- Myerson mechanisms
- Competitive auctions I: The randomized auctions of Goldberg et. al.
- Competitive auctions II: Derandomized auctions
- Competitive auctions III: Mechanism design via machine learning
- Optimal multi-product pricing

- Online auctions
- Expiring-goods auctions and set-Nash equilibrium
- Temporal strategyproofness and secretary problems
- Multiple-choice secretary problems
- Prophet inequalities and online mechanisms