ERA

Download the full-sized PDF of Online Agent Modelling in Human-Scale ProblemsDownload the full-sized PDF

Analytics

Share

Permanent link (DOI): https://doi.org/10.7939/R32N4ZV1T

Download

Export to: EndNote  |  Zotero  |  Mendeley

Communities

This file is in the following communities:

Graduate Studies and Research, Faculty of

Collections

This file is in the following collections:

Theses and Dissertations

Online Agent Modelling in Human-Scale Problems Open Access

Descriptions

Other title
Subject/Keyword
Opponent modelling
Machine learning
Poker
Artificial intelligence
Agent modelling
Extensive-form games
Online learning
Type of item
Thesis
Degree grantor
University of Alberta
Author or creator
Bard, Nolan DC
Supervisor and department
Michael Bowling (Department of Computing Science, University of Alberta)
Examining committee member and department
Peter Stone (Department of Computer Science, The University of Texas at Austin)
Robert Holte (Department of Computing Science, University of Alberta)
Martin Müller (Department of Computing Science, University of Alberta)
Dale Schuurmans (Department of Computing Science, University of Alberta)
Department
Department of Computing Science
Specialization

Date accepted
2016-03-31T13:52:32Z
Graduation date
2016-06
Degree
Doctor of Philosophy
Degree level
Doctoral
Abstract
Ideal agent behaviour in multiagent environments depends on the behaviour of other agents. Consequently, acting to maximize utility is challenging since an agent must gather and exploit knowledge about how the other (potentially adaptive) agents behave. In this thesis, we investigate how an agent can efficiently tailor its behaviour to other agents during interaction in order to maximize its performance. This thesis presents three main contributions. First and foremost, the thesis characterizes and contrasts the traditional agent modelling approach – where practitioners explicitly estimate and subsequently respond to a generative model of an agent's behaviour – with an alternative approach called implicit modelling. Using traditional explicit modelling in complex human-scale domains is difficult since an agent must efficiently estimate sophisticated behaviours from observations that may be stochastic and partially observable. Even after estimating a generative model, it may be impractical to compute a response that is robust to modelling error during interaction. The implicit modelling framework avoids many of these challenges by estimating the utilities of a portfolio of strategies. Furthermore, implicit modelling naturally affords the opportunity to generate the portfolio offline, which provides practitioners with the time necessary for computationally expensive robust response techniques. We introduce an end-to-end approach for building an implicit modelling agent and empirically validate it in several poker domains. Second, the thesis contributes the first empirical analysis of how the granularity of an agent's representation of a multiagent environment – including its beliefs about the other agents – impacts two common objectives: performance against suboptimal agents and robustness against worst-case agents. We show that using asymmetric representations allows for practitioners to trade off these objectives whereas commonplace symmetric representations optimize neither. Third, we contribute a novel decision-theoretic clustering algorithm. While many existing clustering techniques optimize for spatial similarity between objects, we demonstrate that such spatial clustering can fail to capture similarity in how an agent should respond to the clusters to maximize utility. Our algorithm exploits structure in the utility function to allow for an efficient greedy approximation to this computationally hard optimization. We prove worst-case approximation bounds for our algorithm and empirically validate the approach by clustering agent behaviours in extensive-form games. These three contributions provide practitioners with a foundation of practical techniques for constructing an effective portfolio of strategies and using the portfolio to adapt an agent's behaviour. Our empirical evaluation of implicit modelling agents in a variety of poker games demonstrates that implicit modelling is an effective agent modelling approach for online real-time adaptation in complex human-scale domains.
Language
English
DOI
doi:10.7939/R32N4ZV1T
Rights
This thesis is made available by the University of Alberta Libraries with permission of the copyright owner solely for the purpose of private, scholarly or scientific research. 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.
Citation for previous publication
Bard, Nolan, Michael Johanson, Neil Burch, and Michael Bowling (2013). “Online Implicit Agent Modelling”. In: Proceedings of the Twelfth International Conference on Au- tonomous Agents and Multi-Agent Systems. AAMAS 2013, pp. 255–262.Bard, Nolan, Michael Johanson, and Michael Bowling (2014). “Asymmetric Abstractions for Adversarial Settings”. In: Proceedings of the Thirteenth International Conference on Autonomous Agents and Multi-Agent Systems. AAMAS 2014, pp. 501–508.Bard, Nolan, Deon Nicholas, Csaba Szepesvári, and Michael Bowling (2015). “Decision-theoretic Clustering of Strategies”. In: Proceedings of the Fourteenth International Conference on Autonomous Agents and Multi-Agent Systems. AAMAS 2015, pp. 17–25.

File Details

Date Uploaded
Date Modified
2016-03-31T19:52:39.452+00:00
Audit Status
Audits have not yet been run on this file.
Characterization
File format: pdf (PDF/A)
Mime type: application/pdf
File size: 2089359
Last modified: 2016:06:16 16:54:03-06:00
Filename: Bard_Nolan_DC_201603_PhD.pdf
Original checksum: 2d1afedeac907d25ab3042d0007de332
Activity of users you follow
User Activity Date