| Craig Boutilier's Research Interests |
| biography
papers
research group
organizations
teaching
citation profiles
home
|
| |
|
This page is woefully out of date---the life of a department chair *sigh*---but will be updated soon.
My research primarily concerns the investigation, development and application of normative and computational theories of decision making under uncertainty in all of its guises. This includes decision theory and multiattribute decision making; preference elicitation; representations of preferences and utility functions; game theory and multiagent decision processes; economic models; mechanism design; (fully and partially observable) Markov decision processes (MDPs and POMDPs); reinforcement learning; and probabilistic inference. Here are a few of the more prominent themes that have drawn my attention over the last few years.
Much of my work over the last few years has focused on the problem of preference elicitation. If an intelligent system is to act on behalf of some user or organization, it must have knowledge of the utility function or preference function of that user. Elicitation of preferences is a fundamental bottleneck to the widespread deployment of decision support tools and intelligent agents. Key questions that I address in my work include: What are natural, compact and tractable preference representations? What are effective elicitation strategies (both from a computational and cognitive perspective? What preference or utility information is most relevant to a specific decision problem? What are the most effective ways to tradeoff the cost of preference elicition with the benefit (with respect to making an appropriate decision) of that preference information? What are suitable means of making decisions with incomplete preference information? Much of this work can be viewed as a form of interactive optimization.
Techniques and concepts used include: Bayesian and qualitative representations of utility function uncertainty; Bayesian and regret-based approached to decision making with incomplete information; constraint models and optimization methods; and graphical models of utility functions. Applications include auctions; combinatorial auctions; computational mechanism design (e.g., for automated bargaining and negotiation); product design and recommendation; cognitive assistive technologies; software customization and user modeling; autonomic computing; and collaborative filtering.
Current students working on some aspects of this research theme include: Darius Braziunas, Bowen Hui, Nathanael Hyafil, Michael Pavlin and Kevin Regan. Past students: Alex Kress, Pascal Poupart, Tianhan Wang.
Mechanism design can be viewed as designing interaction protocols to facilitate the interactions among a group of agents in order to implement a particular social choice function (i.e., some methods of choosing an outcome based on the preferences of the agents involved). Auction design, bargaining protocols and election schemes are prototypical applications. Almost all work in mechanism design addresses the problem by requiring agents to fully reveal their preferences over outcomes in a way that provides them incentives to do so truthfully. Much of my work in mechanism design tackles the associated preference elicitation problem: the computational, cognitive and communication burden, as well as privacy concerns, render this classical approach impractical. We have developed approaches for the automated design of mechanisms (both single-stage and multi-stage) that allow one to reveal less than complete information from participants, while maintaining approximate incentive properties. More generally, we address the rich tradeoffs to be made between outcome quality, elicitation/revelation effort, and incentives.
Applications include: auctions; combinatorial auctions; automated bargaining; and (ad hoc and wireline) network pricing and quality of service provisioning.
Current students working on some aspects of this research theme include: Nathanael Hyafil, and Michael Pavlin. Past students: Alex Kress.
The coordination of agent activities (whether or not such agents have aligned interests) is a critical activity in multiagent decision making scenarios. My work in this area adopts a gane-theoretic perspective, focusing on equilibrium behavior in one-shot and sequential decision processes. One key interest is in coalition (team) formation under uncertainty, where we have proposed new models for coalition formation with explicit uncertainty regarding partner abilities. Another key interest is in multiagent reinforcement learning, including methods for optimal exploration and convergence to optimal equilibria. Others include coordination protocols in sequential decision problems; learning methods for stochastic games; and methods for learning by observing the behavior of other agents (teaching and knowledge transfer).
Current students working on some aspects of this research theme include: Georgios Chalkiadakis. Past students: Caroline Kraus; Bob Price.
A lot of my time is devoted to the study of Markov decision processes as a conceptual and computational model for decision-theoretic planning and sequential decision problems. I work a lot with both MDPs and POMDPs. I am especially interested have been developing compact representations of MDPs that exploit different types of structure inherent in the underlying problem, and devising solution algorithms, both exact and approximate that exploit this structure.
Techniques and concepts used include: the use of Bayesian network (DBN) models and first-order representations of MDPs; graphical inference techniques; automated abstraction methods; (PCA-like) compression techniques; basis function representations and the automated construction of basis functions; finite-state controller policy representation; decompostion methods; the use of macro-models (or multi-time or semi-Markov models) and programming languages for MDPs.
Current students working on some aspects of this research theme include: Darius Braziunas, Yilan Gu, Bowen Hui, Scott Sanner. Past students: Adrian Cheuk, Richard Dearden, Roger Ford, Siu0Ki Leung, Pascal Poupart, Bob Price.
I have an ongoing collaboration with the Alex Mihailidis and his group in the Intelligent Assistive Technology and Systems Lab (IATSL) to apply decision-theoretic techniques to the development of assistive technologies for people with cognitive or physical impairments of various types. Specifically, we develop user profiling (learning) and MDP and POMDP models for these tasks and test their effectiveness in clininal settings. Applications include systems to monitor and prompt people with dementia (e.g., Alzheimer's disease) in activities of daily living; and devices to aid with stroke rehabilitation.
Current students working on some aspects of this research theme include: Bowen Hui.
Current students working on some aspects of this research theme include: Bowen Hui.
Intimately related to MDPs is the concept of reinforcement learning and its relationship with (and use in) decision-making tasks. I have been involved with the application of RL to the training of soccer-playing mobile robots, and am interested in model-based RL algorithms that can learn and exploit the types of MDP representations mentioned above. I am also interested in the use of RL in multiagent settings to enable agents to develop cooperative problem solving straegies (see above).
Naturally, good methods for probabilistic reasoning are necessary for reasoning and decision making under uncertainty. My interests in inference techniques are largely focused on approximation methods for decision making that can be tuned to account for impact on loss in decision quality.
I am also interested in qualitative theories of decision making, where qualitative notions of belief and likelihood and qualitative preference rankings hold sway. In many situations, this information is all one needs to make reasonably good decisions (and in many cases, it is the only type of information available). In my past life, I did a lot of work on default reasoning and belief revision with an eye toward this direction. I am still somewhat involved in research on qualitative representations of preferences and qualitative theories of decision making.
More to come...