Instructor: Bo Waggoner
Course webpage: https://www.bowaggoner.com/courses/2020/csci7000/
A group size of 2 is ideal.
Given the limited time of half a semester, I suggest starting from a single existing paper. If not, it should still be a concrete topic tied to a few papers or lecture notes.
First, fully understand the main idea in the paper. If you need to, write some code, run simulations, and/or rewrite proofs.
Then, decide what you want to change, investigate, or do differently compared to existing work. You may have started with an idea for this, or you may have discovered it while investigating the paper.
Then, formulate a research goal. For instance, it is not enough to implement an algorithm; you want to obtain and share new knowledge. Formulate a hypothesis, then rigorously investigate it. For example, you may hypothesize that an algorithm scales well with number of players but poorly with number of actions per player. Devise a rigorous set of simulations to test this hypothesis. Or, attempt to prove it as a theorem (perhaps under some assumptions).
Finally, you will write up your findings and also give a brief presentation. Think about how to structure these to best share the new knowledge you've gained. What is the setting? What was previously known? What was not known and how did this motivate your work? What are your conclusions? What is the evidence you collected for your conclusions?
In general, a great approach is to take an interesting paper we read in class and ask what is not satisfactory about it. This can lead to an improvement or investigation. Of course, you can also look ahead at future papers.
Each of the following could go in dozens of different directions!
Dynamics of online learning. When e.g. two online learning algorithms repeatedly play against each other, how do their strategies actually evolve? How does this relate to the time-average of their strategies? Does this lead to new suggestions for learning algorithms or computing equilibria?
Some relevant papers: Bailey et al. (Feb 07 reading); e.g. Last-iterate convergence rates for min-max optimization by Abernethy et al.
Solving large zero-sum games. What are the best algorithms to solve huge two-player zero-sum games like chess, go, poker, and more? Several modern algorithms make use of deep learning, for example. Why do they work well and where is there room for improvement?
Some relevant papers: Brown et al. (Feb 14 reading); Mastering the game of Go without human knowledge by DeepMind group; Simplified AlphaZero Tutorial; and more.
Connections of game-solving to reinforcement learning. This is closely related to the previous topic. How do reinforcement learning and online learning techniques combine to solve zero-sum games, and possibly also single-player games like Atari games? This can also be related to investigating "multi-armed bandit" algorithms.
Some relevant papers: Combining no-regret and Q-learning by Kash et al.; Playing Atari with deep reinforcement learning; and more.
Wagering mechanisms. What are good mechanisms to collect predictions and assign payments? What are drawbacks of current ones?
Relevant papers: Start from Freeman et al. (Mar 02 reading).
Decision markets and "futarchy". Can decision markets be used as an automated governance mechanism? How does one overcome the drawbacks? This project could include an implementation of some prediction markets or decision markets for a blockchain platform like Ethereum.
Relevant papers: Start from Teschner et al. (Mar 16 reading).
Decentralized prediction markets. How do we implement prediction markets without a trusted authority, e.g. on a blockchain? This can be closely related to the previous topic.
Some relevant papers: van Shreven et al. (Mar 20 reading); Crowdsourced outcome determination in prediction markets by Freeman et al.
Frontiers in social choice: liquid and statistical democracy. What are good voting systems and why? Can we accurately and ethically automate group decisionmaking?
Some relevant papers: Statistical foundations of virtual democracy by Kahng et al. (relevant to Feb 03 guest presentation); Efficient and thrifty voting by any means necessary"> by Mandal et al.
Formalizing and studying gerrymandering. What are ``fair'' ways to pick representatives? See the Wikipedia page on gerrymandering.
Some relevant papers: A partisan districting protocol with provably nonpartisan outcomes by Pegden et al.; Abating gerrymandering by mandating fairness by Benade and Procaccia.