Advanced Topics:

Algorithmic game Theory and Machine Learning

**Tentative Schedule:**

Lecture 1: Oct 31, 2011

Introduction. Regret Minimization, Online Convex Optimization.
Regularized Follow The Leader Prime- Dual using Berman
Divergence

source: Elad Hazan, The convex
optimization approach to regret minimization (sections 1.2 and 1.3)

Lecture 2: Nov 5, 2011

Stochastic sub-gradient
decent

Logarithmic regret for
strict convex function

sources:

Boyd, Xiao and Mutapcic, Subgradient Methods also here

Shai Shalev Shwatz, Class notes, lecture 6

Lecture
3.

Regret in Large Action
spaces.

sources:

A. Kalai
and S. Vempala, Efficient
algorithms for online decision problems

S. Kakade,
A. Kalai and K. Ligett, Playing
Games with Approximation Algorithms

Lecture Notes

Lecture
4.

Multi-Arm Bandit,

Adversarial Model,

P. Auer, N. Cesa-Bianchi, Y. Freund and R. E. Schapire,
The Nonstochastic Multi-Armed Bandit Problem (Section 3 and
7)

Lecture
5.

Lower Bound

Multi-Arm Bandit & Supervised
learning (using KL-divergence)

P. Auer, N. Cesa-Bianchi, Y. Freund and R. E. Schapire,
The Nonstochastic Multi-Armed Bandit Problem (section 5)

Lecture
6. Dec. 5, 2011

MAB Gradient Descent

Abraham Flaxman, Adam Tauman Kalai, H. Brendan McMahan Online convex
optimization in the bandit setting: gradient descent without a gradient

Oblivious versus Adaptive
adversary

Varsha Dan and Thomas P. Hayes, How to Beat the Adaptive Multi-Armed Bandit(section 8)

Lecture
7. Dec. 12, 2011

Bayesian approach to MAB: Gittins index

J. Gittins,
K. Glazerbrook and R. Weber, Multi-Arm Bandit
Allocation Indices

John
N. Tsitsiklis, A short proof of
the Gittins index theorem

Lecture
8. Dec. 19, 2011

Information Cascading [sources]

Lecture
9. Dec. 26, 2011

Sponsored search
optimization.

Nikhil Devanur
Online
Algorithms with Stochastic Input

Nikhil Devanur and Tom Hayes The
Adwords Problem: Online Keyword Matching with
Budgeted Bidders under Random Permutations

Lecture
10. Jan. 2, 2012

Market Equilibrium and
Convex Programming

Combinatorial Algorithms
for Market Equilibria, Vijai
Vazirani, Chapter 5 sections
5.2 and 5.11 in Algorithmic
Game Theory, editors: Nisan, Roughgarden, Tardos, and Vazirani.

A
Polynomial Time Algorithm for Computing an Arrow–Debreu
Market Equilibrium for Linear Utilities, Kamal
Jain (Sections 3 and 5)

Lecture 11, Jan 9, 2012

Indivisible items and
market equilibrium

Avinatan Hassidim, Haim Kaplan, Yishay Mansour and Noam Nisan, Non-Price Equilibria
in Markets of Discrete Goods

Lecture 12, Jan 16, 2012

Uriel Feige, On
Maximizing Welfare when Utility Functions are Subadditive

Lecture 13, Jan 23, 2012

Regret Minimization of Global Cost functions

Lecture 14, Jan 30, 2012

Nash Equilibrium and
communication complexity

**Home Work:**