8803 LGO, Ideas for Projects

One of the course requirements is to do project, which you may do in groups of 2 or 3. A project might involve conducting an experiment or thinking about a theoretical problem, or trying to relate two problems. It could even just be reading 3 research papers and explaining how they relate. The end result should be a 8-10 page report, and a 30 - 45 minute presentation. Here are a few ideas for possible topics for projects.

Project Ideas

Internal Regret and Correlated Equilibria

S. Hart and A. Mas-Colell A Simple Adaptive Procedure Leading to Correlated Equilibrium. Econometrica, 2000.
Gilles Stoltz Incomplete information and internal regret in prediction of individual sequences. PhD dissertation, Université, Paris-Sud, 2005.

Online Learning and Optimization

N. Alon, B. Awerbuch, Y. Azar, N. Buchbinder and J. Naor A The online set cover problem. STOC 2003.
N. Bansal, A. Blum, S. Chawla, and A. Meyerson Online Oblivious Routing. SPAA 2003.
A. Kalai, S. Vempala Efficient algorithms for online decision problems. JCSS 2005.
M. Zinkievich Online convex programming and generalized infinitesimal gradient ascent. ICML 2003.

The Multi-Armed Bandit Problem:

P. Auer, N. Cesa-Bianchi, Y. Freund, and R. Schapire The nonstochastic multiarmed bandit problem. SICOMP 2002.
P. Auer, N. Cesa-Bianchi, and P. Fischer Finite time analysis of the multiarmed bandit problem. ML 2002.

Uncoupled Dynamics and Nash Equilibria:

S. Hart and Y. Mansour The Communication Complexity of Uncoupled Nash Equilibrium Procedures. STOC 2009.
S. Hart and A. Mas-Colell Uncoupled Dynamics Do Not Lead to Nash Equilibrium. American Economic Review 2003.

Learning and Repeated Games:

Y. Freund and R. Schapire Adaptive Game Playing Using Multiplicative Weights. Games and Economic Behavour 1999.
D. Foster and R. Vohra Regret in the On-line Decision Problem . Games and Economic Behavior 1999
E. Even-Dar, Y. Mansour and U. Nadav On the convergence of regret minimization dynamics in socially concave games. STOC 2009.

Preference Elicitation and Learning:

A. Blum, M. Zinkevich, and T. Sandholm. On Polynomial-Time Preference Elicitation with Value Queries. EC 2003.
T. Sandholm and C. Boutilier On Preference Elicitation in Combinatorial Auctions.

Game Theory for Engineered Systems:

J.R. Marden, G. Arslan, and J.S. Shamma Cooperative control and potential games". IEEE Transacions on Systems, Man, and Cybernetics 2009.
G. Arslan, J.R. Marden and J.S. Shamma.Autonomous vehicle-target assignment: A game theoretical formulation. ASME Journal of Dynamic Systems, Measurement, and Control, special issue on "Analysis and Control of Multi-Agent Dynamic Systems.

Learning in Markov Decision Processes: See M. Kearns's home page and Y. Mansour's home page for a number of good papers. Also S. Kakade's thesis.