Cornell University - CS 683

Cornell University - CS 683

Course Outline for CS 683, Spring 2007

1. Prediction from expert advice
   1. Prediction, regret, and game-theoretic equilibria
      1. The weighted majority algorithm
      2. Solving zero-sum games by adaptive game playing
      3. Algorithmic consequences of zero-sum games: Yao's lemma, LP duality
      4. Log-loss and forecasting
      5. Calibration
      6. Blackwell's approachability theorem
      7. Internal regret
      8. Correlated equilibrium
      9. Learning processes which converge to correlated equilibrium
      10. Deterministic calibration
      11. Learning processes which converge to Nash equilibrium
   2. Other applications
      1. PAC learning, boosting
      2. Approximation algorithms
      3. AdWords
      4. The XOR lemma
   3. Learning with many experts
      1. The Hannan-Kalai-Vempala algorithm
      2. Zinkevich's algorithm
      3. Universal portfolios
   4. Learning and evolution
      1. Evolutionary game theory I: Evolutionarily stable strategies
      2. Evolutionary game theory II: Replicator dynamics
      3. Evolvability
2. Multi-armed bandit problems
   1. Stochastic formulations
      1. Markov decision processes
      2. Golfing with two golf balls
      3. Multi-armed bandits and Gittins indices
      4. Logarithmic-regret algorithms: Lai-Robbins, UCB1
   2. Non-stochastic formulations
      1. The Exp3 algorithm
      2. Information-theoretic lower bound
      3. Bandits with many arms I: barycentric spanners and online linear optimization
      4. Bandits with many arms II: anytime bandit algorithms
   3. Applications
      1. Recommendation systems, trust, and collaborative learning
      2. Online pricing I: Incomplete learning in the long run
      3. Online pricing II: Upper bounds on regret
      4. Online pricing III: Lower bounds on regret
3. Electronic markets
   1. Offline auction mechanisms
      1. Basic mechanism design definitions
      2. Myerson mechanisms
      3. Competitive auctions I: The randomized auctions of Goldberg et. al.
      4. Competitive auctions II: Derandomized auctions
      5. Competitive auctions III: Mechanism design via machine learning
      6. Optimal multi-product pricing
   2. Online auctions
      1. Expiring-goods auctions and set-Nash equilibrium
      2. Temporal strategyproofness and secretary problems
      3. Multiple-choice secretary problems
      4. Prophet inequalities and online mechanisms