Author: Steve Nadis | MIT Laboratory for Information and Decision Systems<\/p>\n
Whether you\u2019re playing poker against a single opponent or find yourself in a bidding war over a home purchase with another prospective buyer, you are operating under conditions of imperfect information. You know what cards you\u2019re holding in the poker game, and you also know how much above the home\u2019s asking price you can afford, but you don\u2019t know your opponent\u2019s hand in the card game or how high the other home buyer is willing to go.\u00a0<\/p>\n
A paper<\/a> co-authored by MIT researchers and presented in April at the International Conference on Learning Representations in Rio De Janeiro won\u2019t tell you what to do in these situations, specifically. But it does offer new insights into so-called imperfect-information games that involve two contestants facing off in a \u201czero-sum\u201d competition, where one player\u2019s gain means the other player\u2019s loss.<\/p>\n MIT researchers on the project include Sobhan Mohammadpour, a PhD student in MIT\u2019s Department of Electrical Engineering and Computer Science (EECS) and the Laboratory for Information and Decision Systems (LIDS); and Gabriele Farina, an assistant professor in EECS and a principal investigator at LIDS. Additional co-authors include Max Rudolph of the University of Texas at Austin (UT), Nathan Lichtl\u00e9 of the University of California at Berkeley (UCB), Alexandre Bayen of UCB, J. Zico Kolter of Carnegie Mellon University (CMU), Amy X. Zhang \u201911, MNG \u201912 of UT; Eugene Vinitsky of New York University; and Samuel Sokota of CMU.\u00a0<\/p>\n The focus of the new work is on algorithms that could be used to train neural networks to participate in imperfect-information games. The assumption, long-held in the field, was that algorithms grounded in principles of game theory would, in this setting, clearly outcompete a general-purpose variety of algorithms called policy gradient methods, which came into use for decision-making in the 1990s. The term \u201cpolicy\u201d in this context basically means strategy, whereas \u201cgradient\u201d refers to a path that leads in the direction of greatest change \u2014 to the top (or bottom) of a hill, for example. Policy gradient methods are being used to train neural networks to make decisions that move \u2014 in small, sequential steps \u2014 toward a particular goal (like reaching a summit, metaphorically speaking), with continual adjustments and course corrections made along the way to bring the agent closer to the intended destination.<\/p>\n Although strategic games were not on the original agenda when policy gradient methods were conceived in the early 1990s, the authors of the new paper still wondered how this class of algorithms might fare in two-player games. These methods become more complicated to analyze in multi-agent settings, according to Farina. \u201cThere is still a direction you can move in to improve your circumstances, but, because of the other player\u2019s actions, that direction can constantly change over the course of the game. And those shifts can be rapid.\u201d<\/p>\n \u201cIt had been pretty much taken for granted that specialized game-theoretic algorithms were the right approach for this setting,\u201d says Sokota. \u201cOur study showed that policy gradient methods can work better than these specialized algorithms, and that the specialized algorithms may not work as well as people thought \u2014 which raises an interesting sociological question about why this went unnoticed for so long. Part of the answer is that the field hadn\u2019t done the engineering work required to rigorously evaluate the algorithms, so it was hard to tell what worked and what didn\u2019t.\u201d<\/p>\n Consequently, a major contribution of this work has been to provide an even-handed way of appraising different algorithms that can teach agents \u2014 i.e., neural networks \u2014 how to compete in imperfect-information games. \u201cWe\u2019re taking a different approach,\u201d notes Rudolph. \u201cUnlike many of the papers published in this field, we\u2019re not proposing a new algorithm that can beat out other algorithms. We\u2019re proposing a benchmark that can assess these algorithms.\u201d<\/p>\n Simply put, a benchmark consists of software designed to rate the performance of algorithms. \u201cWhat we\u2019re offering is a testing grounds, or playing grounds, where people can take their algorithms, train them for a specific task, and see how well they do,\u201d says Farina.<\/p>\n The group calculates a player\u2019s performance in terms of a concept called exploitability, which measures how well a player does against the \u201cworst-case adversary,\u201d Sokota explains. \u201cIn a game like poker, this opponent wouldn\u2019t know what my hand is, but would know how I would behave for any given hand.\u201d Achieving a zero on this scale implies perfect play, whereas a high exploitability score indicates far-from-optimal play.<\/p>\n Five games were played in experiments carried out by the team: two versions of Phantom Tic-Tac-Toe, in which players can\u2019t see what their opponent has done, along with two imperfect-information variants of a board game called Hex, and another game of deception called Liar\u2019s Dice.<\/p>\n The biggest challenge faced by the researchers was getting the exploitability measure to work on games of this size, which may include as many as 30 billion states. A \u201cstate\u201d in this case is not just all the possible board positions, but also encompasses the entire history of the game, including every step and misstep along the way.\u00a0<\/p>\n \u201cIt\u2019s like looking into a dark room that\u2019s filled with objects you can\u2019t see,\u201d says Mohammadpour. \u201cSomehow, you need to figure out where these objects are and exactly how they got there.\u201d Previous researchers, Mohammadpour adds, have typically used exploitability for games that are 100,000 times smaller than the ones analyzed in their study.<\/p>\n In the experiments carried out on these five games, neural networks trained with policy gradient algorithms got better (lower) exploitability scores than networks trained on game theory-based algorithms. In head-to-head competitions, which took place in the next round, the policy gradient-trained networks again beat their game theory-trained opponents. \u201cThose results were reassuring,\u201d Rudolph says, \u201cbecause they give us more confidence in our benchmarking approach.\u201d<\/p>\n The team has made their benchmarking software freely available and convenient to use. \u201cYou don\u2019t need a supercomputer,\u201d Mohammadpour says. \u201cYou can run it on an ordinary laptop. And all you have to do is add a single line of code to a commonly used collection of benchmarking software called OpenSpiel.\u201d<\/p>\n Although their experiments involved some fairly obscure games, Farina would like to put this work into a broader context. \u201cKeep in mind that the term ‘game’ really applies to any multi-agent strategic interaction,\u201d he says. \u201cSo the lessons we learn from this research are by no means limited to recreational games.\u201d<\/p>\n Vinitsky agrees. \u201cHidden information is a very important property of the world,\u201d he says. \u201cIt pervades a range of things \u2014 including military operations, trading scenarios, and negotiations \u2014 all of which are carried out under conditions of hidden information. The idea that we can improve on these games suggests that we can also do better in these other settings as well.\u201d<\/p>\n Ian Gemp \u2014 a computer scientist and game theory expert at Google DeepMind who was not involved in this study \u2014 finds these results encouraging. \u201cThis work serves as a compelling reminder,\u201d he says, \u201cthat modernizing classical tools [like policy gradient methods] remains a highly productive path for solving complex strategic problems.\u201d<\/p>\n<\/div>\n Go to Source<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"