An ideal class project would extend your current research in an interesting new direction with use of game theory. If you do not have more specific idea, come talk to us. For inspiration, here are some suggestions.

In the lecture, we will show that the empirical frequencies of actions of two no regret learning algorithms (in adversarial setting) playing each other in a finite zero-sum game converge to a Nash equilibrium of the game at rate O(1/√T). There are three related questions you can investigate in the assignment.

1) Does this hold also in infinite games? Under what conditions?

2) Regret matching+ seems to empirically converge much faster than the bound in self-play in zero-sum games. Find an example game and show that the convergence rate is indeed ω(1/T). Investigate sufficient and necessary conditions for faster convergence.

3) Recent years brought several CFR improvements that do not have basis in theory and are evaluated only in poker. Implement and evaluate the speed of convergence of one of these improvements in various games implemented in gtlib2 framework implemented at the department.