Usage
  • 111 views
  • 347 downloads

Monte Carlo Sampling and Regret Minimization for Equilibrium Computation and Decision-Making in Large Extensive Form Games

  • Author / Creator
    Lanctot, Marc
  • In this thesis, we investigate the problem of decision-making in large two-player zero-sum games using Monte Carlo sampling and regret minimization methods. We demonstrate four major contributions. The first is Monte Carlo Counterfactual Regret Minimization (MCCFR): a generic family of sample-based algorithms that compute near-optimal equilibrium strategies. Secondly, we develop a theory for applying counterfactual regret minimization to a generic subset of imperfect recall games as well as a lossy abstraction mechanism for reducing the size of very large games. Thirdly, we describe Monte Carlo Minimax Search (MCMS): an adversarial search algorithm based on *-Minimax that uses sparse sampling. We then present variance reduction techniques that can be used in these settings, with a focused application to Monte Carlo Tree Search (MCTS). We thoroughly evaluate our algorithms in practice using several different domains and sampling strategies.

  • Subjects / Keywords
  • Graduation date
    2013-06
  • Type of Item
    Thesis
  • Degree
    Doctor of Philosophy
  • DOI
    https://doi.org/10.7939/R3K085
  • License
    This thesis is made available by the University of Alberta Libraries with permission of the copyright owner solely for non-commercial purposes. This thesis, or any portion thereof, may not otherwise be copied or reproduced without the written consent of the copyright owner, except to the extent permitted by Canadian copyright law.
  • Language
    English
  • Institution
    University of Alberta
  • Degree level
    Doctoral
  • Department
    • Department of Computing Science
  • Supervisor / co-supervisor and their department(s)
    • Michael Bowling (Computing Science)
  • Examining committee members and their departments
    • Duane Szafron (Computing Science)
    • Michael Bowling (Computing Science)
    • Joerg Sander (Computing Science)
    • Michael Wellman (Computer Science & Engineering, University of Michigan)
    • Martin Mueller (Computing Science)
    • Csaba Szepesvari (Computing Science)