Online Agent Modelling in Human-Scale Problems Open Access
- Other title
- Type of item
- 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 of Computing Science
- Date accepted
- Graduation date
Doctor of Philosophy
- Degree level
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.
- 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.
- Date Uploaded
- Date Modified
- Audit Status
- Audits have not yet been run on this file.
File format: pdf (PDF/A)
Mime type: application/pdf
File size: 2089359
Last modified: 2016:06:16 16:54:03-06:00
Original checksum: 2d1afedeac907d25ab3042d0007de332
Activity of users you follow