<div dir="ltr">This is a reminder that this talk is tomorrow, Tuesday, September 20th, at noon in NSH 3305.<div><br><div class="gmail_quote">---------- Forwarded message ----------<br>From: <b class="gmail_sendername">Ellen Vitercik</b> <span dir="ltr"><<a href="mailto:vitercik@cs.cmu.edu">vitercik@cs.cmu.edu</a>></span><br>Date: Fri, Sep 16, 2016 at 6:53 PM<br>Subject: AI Lunch -- Noam Brown -- September 20th, 2016<br>To: <a href="mailto:ai-seminar-announce@cs.cmu.edu">ai-seminar-announce@cs.cmu.edu</a><br><br><br><div dir="ltr">Dear faculty and students,<br><br>We look forward to seeing you this Tuesday, September 20th, at noon in NSH 3305 for AI lunch. To learn more about the seminar and lunch, please visit the <a href="http://www.cs.cmu.edu/~aiseminar/" target="_blank">AI Lunch webpage</a>.<div><div><br>On Tuesday, <a href="http://www.cs.cmu.edu/~noamb/" target="_blank">Noam Brown</a> will give a talk titled "Reduced Space and Faster Convergence in Imperfect-Information Games via Regret-Based Pruning."</div><div><br><b>Abstract</b>: Counterfactual Regret Minimization (CFR) is a leading algorithm for solving large zero-sum imperfect-information games. CFR is an iterative algorithm that repeatedly traverses the game tree, updating regrets at each information set. We introduce Regret-Based Pruning (RBP), an improvement to CFR that prunes any path of play in the tree, and its descendants, that has negative regret. It revisits that sequence at the earliest subsequent CFR iteration where the regret could have become positive, had that path been explored on every iteration. We prove that in zero-sum games it asymptotically prunes any action that is not part of a best response to some Nash equilibrium. This leads to provably faster convergence and lower space requirements. Experiments show that RBP can result in an order of magnitude reduction in both space and time needed to converge, and that the reduction factor increases with game size.<br><br>In partial fulfillment of the Speaking Requirement.<br><br>Best,<br>Ellen and Ariel</div></div></div>
</div><br></div></div>