Craig Boutilier

ICLR Conference 2025 Conference Paper

Inference-Aware Fine-Tuning for Best-of-N Sampling in Large Language Models

• Yinlam Chow
• Guy Tennenholtz
• Izzeddin Gur
• Vincent Zhuang
• Bo Dai 0001
• Aviral Kumar
• Rishabh Agarwal
• Sridhar Thiagarajan

Recent studies indicate that effectively utilizing inference-time compute is crucial for attaining good performance from large language models (LLMs). Specifically, the Best-of-N (BoN) inference strategy, where an LLM generates multiple responses and a verifier selects the best, has shown strong empirical performance. Motivated by this, we develop a novel inference-aware fine-tuning paradigm, which encompasses the BoN-aware inference framework as a special case. We devise the first imitation learning and reinforcement learning (RL) methods for fine-tuning LLMs using BoN, overcoming the challenging, non-differentiable argmax operator in BoN. We empirically demonstrate that our BoN-aware models implicitly learn a per-example "meta-strategy", which interleaves best responses with more diverse responses that might be better suited to a test-time input—a process reminiscent of the exploration-exploitation trade-off in RL. Our experiments demonstrate the effectiveness of BoN-aware fine-tuning in terms of improved performance and inference-time compute. In particular, we show that our methods improve the BoN performance of Gemma 2B on Hendrycks MATH from 26.8% to 30.8%, and Pass@K from 60% to 67%.

ICML Conference 2025 Conference Paper

Preference Adaptive and Sequential Text-to-Image Generation

• Ofir Nabati
• Guy Tennenholtz
• Chih-Wei Hsu
• Moonkyung Ryu
• Deepak Ramachandran
• Yinlam Chow
• Xiang Li
• Craig Boutilier

We address the problem of interactive text-to-image (T2I) generation, designing a reinforcement learning (RL) agent which iteratively improves a set of generated images for a user through a sequence of prompt expansions. Using human raters, we create a novel dataset of sequential preferences, which we leverage, together with large-scale open-source (non-sequential) datasets. We construct user-preference and user-choice models using an EM strategy and identify varying user preference types. We then leverage a large multimodal language model (LMM) and a value-based RL approach to suggest an adaptive and diverse slate of prompt expansions to the user. Our Preference Adaptive and Sequential Text-to-image Agent (PASTA) extends T2I models with adaptive multi-turn capabilities, fostering collaborative co-creation and addressing uncertainty or underspecification in a user’s intent. We evaluate PASTA using human raters, showing significant improvement compared to baseline methods. We also open-source our sequential rater dataset and simulated user-rater interactions to support future research in user-centric multi-turn T2I systems.

ICLR Conference 2024 Conference Paper

Demystifying Embedding Spaces using Large Language Models

• Guy Tennenholtz
• Yinlam Chow
• Chih-Wei Hsu
• Jihwan Jeong
• Lior Shani
• Azamat Tulepbergenov
• Deepak Ramachandran
• Martin Mladenov

Embeddings have become a pivotal means to represent complex, multi-faceted information about entities, concepts, and relationships in a condensed and useful format. Nevertheless, they often preclude direct interpretation. While downstream tasks make use of these compressed representations, meaningful interpretation usually requires visualization using dimensionality reduction or specialized machine learning interpretability methods. This paper addresses the challenge of making such embeddings more interpretable and broadly useful, by employing large language models (LLMs) to directly interact with embeddings -- transforming abstract vectors into understandable narratives. By injecting embeddings into LLMs, we enable querying and exploration of complex embedding data. We demonstrate our approach on a variety of diverse tasks, including: enhancing concept activation vectors (CAVs), communicating novel embedded entities, and decoding user preferences in recommender systems. Our work couples the immense information potential of embeddings with the interpretative power of LLMs.

NeurIPS Conference 2024 Conference Paper

Density-based User Representation using Gaussian Process Regression for Multi-interest Personalized Retrieval

• Haolun Wu
• Ofer Meshi
• Masrour Zoghi
• Fernando Diaz
• Xue Liu
• Craig Boutilier
• Maryam Karimzadehgan

Accurate modeling of the diverse and dynamic interests of users remains a significant challenge in the design of personalized recommender systems. Existing user modeling methods, like single-point and multi-point representations, have limitations w. r. t. \ accuracy, diversity, and adaptability. To overcome these deficiencies, we introduce density-based user representations (DURs), a novel method that leverages Gaussian process regression (GPR) for effective multi-interest recommendation and retrieval. Our approach, GPR4DUR, exploits DURs to capture user interest variability without manual tuning, incorporates uncertainty-awareness, and scales well to large numbers of users. Experiments using real-world offline datasets confirm the adaptability and efficiency of GPR4DUR, while online experiments with simulated users demonstrate its ability to address the exploration-exploitation trade-off by effectively utilizing model uncertainty.

NeurIPS Conference 2024 Conference Paper

DynaMITE-RL: A Dynamic Model for Improved Temporal Meta-Reinforcement Learning

• Anthony Liang
• Guy Tennenholtz
• Chih-Wei Hsu
• Yinlam Chow
• Erdem Biyik
• Craig Boutilier

We introduce DynaMITE-RL, a meta-reinforcement learning (meta-RL) approach to approximate inference in environments where the latent state evolves at varying rates. We model episode sessions---parts of the episode where the latent state is fixed---and propose three key modifications to existing meta-RL methods: (i) consistency of latent information within sessions, (ii) session masking, and (iii) prior latent conditioning. We demonstrate the importance of these modifications in various domains, ranging from discrete Gridworld environments to continuous-control and simulated robot assistive tasks, illustrating the efficacy of DynaMITE-RL over state-of-the-art baselines in both online and offline RL settings.

NeurIPS Conference 2024 Conference Paper

Embedding-Aligned Language Models

• Guy Tennenholtz
• Yinlam Chow
• Chih-Wei Hsu
• Lior Shani
• Ethan Liang
• Craig Boutilier

We propose a novel approach for training large language models (LLMs) to adhere to objectives defined within a latent embedding space. Our method leverages reinforcement learning (RL), treating a pre-trained LLM as an environment. Our embedding-aligned guided language (EAGLE) agent is trained to iteratively steer the LLM's generation towards optimal regions of the latent embedding space, w. r. t. some predefined criterion. We demonstrate the effectiveness of the EAGLE agent using the MovieLens 25M and Amazon Review datasets to surface content gaps that satisfy latent user demand. We also demonstrate the benefit of using an optimal design of a state-dependent action set to improve EAGLE's efficiency. Our work paves the way for controlled and grounded text generation using LLMs, ensuring consistency with domain-specific knowledge and data representations.

IJCAI Conference 2024 Conference Paper

Model-Free Preference Elicitation

• Carlos Martin
• Craig Boutilier
• Ofer Meshi
• Tuomas Sandholm

In recommender systems, preference elicitation (PE) is an effective way to learn about a user's preferences to improve recommendation quality. Expected value of information (EVOI), a Bayesian technique that computes expected gain in user utility, has proven to be effective in selecting useful PE queries. Most EVOI methods use probabilistic models of user preferences and query responses to compute posterior utilities. By contrast, we develop model-free variants of EVOI that rely on function approximation to obviate the need for specific modeling assumptions. Specifically, we learn user response and utility models from existing data (often available in real-world recommender systems), which are used to estimate EVOI rather than relying on explicit probabilistic inference. We augment our approach by using online planning, specifically, Monte Carlo tree search, to further enhance our elicitation policies. We show that our approach offers significant improvement in recommendation quality over standard baselines on several PE tasks.

AAAI Conference 2024 Conference Paper

Recommender Ecosystems: A Mechanism Design Perspective on Holistic Modeling and Optimization

• Craig Boutilier
• Martin Mladenov
• Guy Tennenholtz

Modern recommender systems lie at the heart of complex recommender ecosystems that couple the behavior of users, content providers, vendors, advertisers, and other actors. Despite this, the focus of much recommender systems research and deployment is on the local, myopic optimization of the recommendations made to individual users. This comes at a significant cost to the long-term utility that recommender systems generate for their users. We argue that modeling the incentives and behaviors of these actors, and the interactions among them induced by the recommender systems, is needed to maximize value and improve overall ecosystem health. Moreover, we propose the use of economic mechanism design, an area largely overlooked in recommender systems research, as a framework for developing such models. That said, one cannot apply “vanilla” mechanism design to recommender ecosystem modeling optimization out of the box—the use of mechanism design raises a number of subtle and interesting research challenges. We outline a number of these in this talk (and paper), emphasizing the need to develop nonstandard approaches to mechanism design that intersect with numerous areas of research, including preference modeling, reinforcement learning and exploration, behavioral economics, and generative AI, among others.

ICLR Conference 2023 Conference Paper

A Mixture-of-Expert Approach to RL-based Dialogue Management

• Yinlam Chow
• Azamat Tulepbergenov
• Ofir Nachum
• Dhawal Gupta
• Moonkyung Ryu
• Mohammad Ghavamzadeh
• Craig Boutilier

Despite recent advancements in language models (LMs), their application to dialogue management (DM) problems and ability to carry on rich conversations remain a challenge. We use reinforcement learning (RL) to develop a dialogue agent that avoids being short-sighted (outputting generic utterances) and maximizes overall user satisfaction. Most existing RL approaches to DM train the agent at the word-level, and thus, have to deal with a combinatorially complex action space even for a medium-size vocabulary. As a result, they struggle to produce a successful and engaging dialogue even if they are warm-started with a pre-trained LM. To address this issue, we develop a RL-based DM using a novel mixture of expert language model (MoE-LM) that consists of (i) a LM capable of learning diverse semantics for conversation histories, (ii) a number of specialized LMs (or experts) capable of generating utterances corresponding to a particular attribute or personality, and (iii) a RL-based DM that performs dialogue planning with the utterances generated by the experts. Our MoE approach provides greater flexibility to generate sensible utterances with different intents and allows RL to focus on conversational-level DM. We compare it with SOTA baselines on open-domain dialogues and demonstrate its effectiveness both in terms of the diversity and sensibility of the generated utterances and the overall DM performance.

NeurIPS Conference 2023 Conference Paper

DPOK: Reinforcement Learning for Fine-tuning Text-to-Image Diffusion Models

• Ying Fan
• Olivia Watkins
• Yuqing Du
• Hao Liu
• Moonkyung Ryu
• Craig Boutilier
• Pieter Abbeel
• Mohammad Ghavamzadeh

Learning from human feedback has been shown to improve text-to-image models. These techniques first learn a reward function that captures what humans care about in the task and then improve the models based on the learned reward function. Even though relatively simple approaches (e. g. , rejection sampling based on reward scores) have been investigated, fine-tuning text-to-image models with the reward function remains challenging. In this work, we propose using online reinforcement learning (RL) to fine-tune text-to-image models. We focus on diffusion models, defining the fine-tuning task as an RL problem, and updating the pre-trained text-to-image diffusion models using policy gradient to maximize the feedback-trained reward. Our approach, coined DPOK, integrates policy optimization with KL regularization. We conduct an analysis of KL regularization for both RL fine-tuning and supervised fine-tuning. In our experiments, we show that DPOK is generally superior to supervised fine-tuning with respect to both image-text alignment and image quality. Our code is available at https: //github. com/google-research/google-research/tree/master/dpok.

NeurIPS Conference 2023 Conference Paper

Offline Reinforcement Learning for Mixture-of-Expert Dialogue Management

• Dhawal Gupta
• Yinlam Chow
• Azamat Tulepbergenov
• Mohammad Ghavamzadeh
• Craig Boutilier

Reinforcement learning (RL) has shown great promise for developing agents for dialogue management (DM) that are non-myopic, conduct rich conversations, and maximize overall user satisfaction. Despite the advancements in RL and language models (LMs), employing RL to drive conversational chatbots still poses significant challenges. A primary issue stems from RL’s dependency on online exploration for effective learning, a process that can be costly. Moreover, engaging in online interactions with humans during the training phase can raise safety concerns, as the LM can potentially generate unwanted outputs. This issue is exacerbated by the combinatorial action spaces facing these algorithms, as most LM agents generate responses at the word level. We develop various RL algorithms, specialized in dialogue planning, that leverage recent Mixture-of-Expert Language Models (MoE-LMs)---models that capture diverse semantics, generate utterances reflecting different intents, and are amenable for multi-turn DM. By exploiting the MoE-LM structure, our methods significantly reduce the size of the action space and improve the efficacy of RL-based DM. We evaluate our methods in open-domain dialogue to demonstrate their effectiveness with respect to the diversity of intent in generated utterances and overall DM performance.

ICML Conference 2023 Conference Paper

Reinforcement Learning with History Dependent Dynamic Contexts

• Guy Tennenholtz
• Nadav Merlis
• Lior Shani
• Martin Mladenov
• Craig Boutilier

We introduce Dynamic Contextual Markov Decision Processes (DCMDPs), a novel reinforcement learning framework for history-dependent environments that generalizes the contextual MDP framework to handle non-Markov environments, where contexts change over time. We consider special cases of the model, with a focus on logistic DCMDPs, which break the exponential dependence on history length by leveraging aggregation functions to determine context transitions. This special structure allows us to derive an upper-confidence-bound style algorithm for which we establish regret bounds. Motivated by our theoretical results, we introduce a practical model-based algorithm for logistic DCMDPs that plans in a latent space and uses optimism over history-dependent features. We demonstrate the efficacy of our approach on a recommendation task (using MovieLens data) where user behavior dynamics evolve in response to recommendations.

IJCAI Conference 2022 Conference Paper

IMO^3: Interactive Multi-Objective Off-Policy Optimization

• Nan Wang
• Hongning Wang
• Maryam Karimzadehgan
• Branislav Kveton
• Craig Boutilier

Most real-world optimization problems have multiple objectives. A system designer needs to find a policy that trades off these objectives to reach a desired operating point. This problem has been studied extensively in the setting of known objective functions. However, we consider a more practical but challenging setting of unknown objective functions. In industry, optimization under this setting is mostly approached with online A/B testing, which is often costly and inefficient. As an alternative, we propose Interactive Multi-Objective Off-policy Optimization (IMO^3). The key idea of IMO^3 is to interact with a system designer using policies evaluated in an off-policy fashion to uncover which policy maximizes her unknown utility function. We theoretically show that IMO^3 identifies a near-optimal policy with high probability, depending on the amount of designer's feedback and training data for off-policy estimation. We demonstrate its effectiveness empirically on several multi-objective optimization problems.

AAAI Conference 2022 Conference Paper

Subjective Attributes in Conversational Recommendation Systems: Challenges and Opportunities

• Filip Radlinski
• Craig Boutilier
• Deepak Ramachandran
• Ivan Vendrov

The ubiquity of recommender systems has increased the need for higher-bandwidth, natural and efficient communication with users. This need is increasingly filled by recommenders that support natural language interaction, often conversationally. Given the inherent semantic subjectivity present in natural language, we argue that modeling subjective attributes in recommenders is a critical, yet understudied, avenue of AI research. We propose a novel framework for understanding different forms of subjectivity, examine various recommender tasks that will benefit from a systematic treatment of subjective attributes, and outline a number of research challenges.

ICML Conference 2021 Conference Paper

Meta-Thompson Sampling

• Branislav Kveton
• Mikhail Konobeev
• Manzil Zaheer
• Chih-Wei Hsu
• Martin Mladenov
• Craig Boutilier
• Csaba Szepesvári

Efficient exploration in bandits is a fundamental online learning problem. We propose a variant of Thompson sampling that learns to explore better as it interacts with bandit instances drawn from an unknown prior. The algorithm meta-learns the prior and thus we call it MetaTS. We propose several efficient implementations of MetaTS and analyze it in Gaussian bandits. Our analysis shows the benefit of meta-learning and is of a broader interest, because we derive a novel prior-dependent Bayes regret bound for Thompson sampling. Our theory is complemented by empirical evaluation, which shows that MetaTS quickly adapts to the unknown prior.

IJCAI Conference 2020 Conference Paper

BRPO: Batch Residual Policy Optimization

• Sungryull Sohn
• Yinlam Chow
• Jayden Ooi
• Ofir Nachum
• Honglak Lee
• Ed Chi
• Craig Boutilier

In batch reinforcement learning (RL), one often constrains a learned policy to be close to the behavior (data-generating) policy, e. g. , by constraining the learned action distribution to differ from the behavior policy by some maximum degree that is the same at each state. This can cause batch RL to be overly conservative, unable to exploit large policy changes at frequently-visited, high-confidence states without risking poor performance at sparsely-visited states. To remedy this, we propose residual policies, where the allowable deviation of the learned policy is state-action-dependent. We derive a new for RL method, BRPO, which learns both the policy and allowable deviation that jointly maximize a lower bound on policy performance. We show that BRPO achieves the state-of-the-art performance in a number of tasks.

ICLR Conference 2020 Conference Paper

CAQL: Continuous Action Q-Learning

• Moonkyung Ryu
• Yinlam Chow
• Ross Anderson
• Christian Tjandraatmadja
• Craig Boutilier

Reinforcement learning (RL) with value-based methods (e.g., Q-learning) has shown success in a variety of domains such as games and recommender systems (RSs). When the action space is finite, these algorithms implicitly finds a policy by learning the optimal value function, which are often very efficient. However, one major challenge of extending Q-learning to tackle continuous-action RL problems is that obtaining optimal Bellman backup requires solving a continuous action-maximization (max-Q) problem. While it is common to restrict the parameterization of the Q-function to be concave in actions to simplify the max-Q problem, such a restriction might lead to performance degradation. Alternatively, when the Q-function is parameterized with a generic feed-forward neural network (NN), the max-Q problem can be NP-hard. In this work, we propose the CAQL method which minimizes the Bellman residual using Q-learning with one of several plug-and-play action optimizers. In particular, leveraging the strides of optimization theories in deep NN, we show that max-Q problem can be solved optimally with mixed-integer programming (MIP)---when the Q-function has sufficient representation power, this MIP-based optimization induces better policies and is more robust than counterparts, e.g., CEM or GA, that approximate the max-Q solution. To speed up training of CAQL, we develop three techniques, namely (i) dynamic tolerance, (ii) dual filtering, and (iii) clustering. To speed up inference of CAQL, we introduce the action function that concurrently learns the optimal policy. To demonstrate the efficiency of CAQL we compare it with state-of-the-art RL algorithms on benchmark continuous control problems that have different degrees of action constraints and show that CAQL significantly outperforms policy-based methods in heavily constrained environments.

ICML Conference 2020 Conference Paper

ConQUR: Mitigating Delusional Bias in Deep Q-Learning

• DiJia Andy Su
• Jayden Ooi
• Tyler Lu
• Dale Schuurmans
• Craig Boutilier

Delusional bias is a fundamental source of error in approximate Q-learning. To date, the only techniques that explicitly address delusion require comprehensive search using tabular value estimates. In this paper, we develop efficient methods to mitigate delusional bias by training Q-approximators with labels that are "consistent" with the underlying greedy policy class. We introduce a simple penalization scheme that encourages Q-labels used across training batches to remain (jointly) consistent with the expressible policy class. We also propose a search framework that allows multiple Q-approximators to be generated and tracked, thus mitigating the effect of premature (implicit) policy commitments. Experimental results demonstrate that these methods can improve the performance of Q-learning in a variety of Atari games, sometimes dramatically.

NeurIPS Conference 2020 Conference Paper

Differentiable Meta-Learning of Bandit Policies

• Craig Boutilier
• Chih-Wei Hsu
• Branislav Kveton
• Martin Mladenov
• Csaba Szepesvari
• Manzil Zaheer

Exploration policies in Bayesian bandits maximize the average reward over problem instances drawn from some distribution P. In this work, we learn such policies for an unknown distribution P using samples from P. Our approach is a form of meta-learning and exploits properties of P without making strong assumptions about its form. To do this, we parameterize our policies in a differentiable way and optimize them by policy gradients, an approach that is pleasantly general and easy to implement. We derive effective gradient estimators and propose novel variance reduction techniques. We also analyze and experiment with various bandit policy classes, including neural networks and a novel softmax policy. The latter has regret guarantees and is a natural starting point for our optimization. Our experiments show the versatility of our approach. We also observe that neural network policies can learn implicit biases expressed only through the sampled instances.

AAAI Conference 2020 Conference Paper

Gradient-Based Optimization for Bayesian Preference Elicitation

• Ivan Vendrov
• Tyler Lu
• Qingqing Huang
• Craig Boutilier

Effective techniques for eliciting user preferences have taken on added importance as recommender systems (RSs) become increasingly interactive and conversational. A common and conceptually appealing Bayesian criterion for selecting queries is expected value of information (EVOI). Unfortunately, it is computationally prohibitive to construct queries with maximum EVOI in RSs with large item spaces. We tackle this issue by introducing a continuous formulation of EVOI as a differentiable network that can be optimized using gradient methods available in modern machine learning computational frameworks (e. g. , TensorFlow, PyTorch). We exploit this to develop a novel Monte Carlo method for EVOI optimization, which is much more scalable for large item spaces than methods requiring explicit enumeration of items. While we emphasize the use of this approach for pairwise (or k-wise) comparisons of items, we also demonstrate how our method can be adapted to queries involving subsets of item attributes or “partial items, ” which are often more cognitively manageable for users. Experiments show that our gradientbased EVOI technique achieves state-of-the-art performance across several domains while scaling to large item spaces.

NeurIPS Conference 2020 Conference Paper

Latent Bandits Revisited

• Joey Hong
• Branislav Kveton
• Manzil Zaheer
• Yinlam Chow
• Amr Ahmed
• Craig Boutilier

A latent bandit is a bandit problem where the learning agent knows reward distributions of arms conditioned on an unknown discrete latent state. The goal of the agent is to identify the latent state, after which it can act optimally. This setting is a natural midpoint between online and offline learning, where complex models can be learned offline and the agent identifies the latent state online. This is of high practical relevance, for instance in recommender systems. In this work, we propose general algorithms for latent bandits, based on both upper confidence bounds and Thompson sampling. The algorithms are contextual, and aware of model uncertainty and misspecification. We provide a unified theoretical analysis of our algorithms, which have lower regret than classic bandit policies when the number of latent states is smaller than actions. A comprehensive empirical study showcases the advantages of our approach.

AIJ Journal 2020 Journal Article

On the equivalence of optimal recommendation sets and myopically optimal query sets

• Paolo Viappiani
• Craig Boutilier

Preference elicitation is an important component in many AI applications, including decision support and recommender systems. Such systems must assess user preferences, based on interactions with their users, and make recommendations using (possibly incomplete and imprecise) beliefs about those preferences. Mechanisms for explicit preference elicitation—asking users to answer direct queries about their preferences—can be of great value; but due to the cognitive and time cost imposed on users, it is important to minimize the number of queries by asking those that have high (expected) value of information. An alternative approach is to simply make recommendations and have users provide feedback (e. g. , accept a recommendation or critique it in some way) and use this more indirect feedback to gradually improve the quality of the recommendations. Due to inherent uncertainty about a user's true preferences, often a set of recommendations is presented to the user at each stage. Conceptually, a set of recommendations can also be viewed as choice query, in which the user indicates which option is most preferred from that set. Because of the potential tension between making a good set recommendation and asking an informative choice query, we explore the connection between the two. We consider two different models of preference uncertainty and optimization: (a) a Bayesian framework in which a posterior over user utility functions is maintained, optimal recommendations are assessed using expected utility, and queries are assessed using expected value of information; and (b) a minimax-regret framework in which user utility uncertainty is strict (represented by a polytope), recommendations are made using the minimax-regret robustness criterion, and queries are assessed using worst-case regret reduction. We show that, somewhat surprisingly, in both cases, there is no tradeoff to be made between good recommendations and good queries: we prove that the optimal recommendation set of size k is also an optimal choice query of size k. We also examine the case where user responses to choice queries are error prone (using both constant and mixed multinomial logit noise models) showing the results are robust to this form of noise. In both frameworks, our theoretical results have practical consequences for the design of interactive recommenders. Our results also allow us to design efficient algorithms to compute optimal query/recommendation sets. We develop several such algorithms (both exact and approximate) for both settings and provide empirical validation of their performance.

ICML Conference 2020 Conference Paper

Optimizing Long-term Social Welfare in Recommender Systems: A Constrained Matching Approach

• Martin Mladenov
• Elliot Creager
• Omer Ben-Porat
• Kevin Swersky
• Richard S. Zemel
• Craig Boutilier

Most recommender systems (RS) research assumes that a user’s utility can be maximized independently of the utility of the other agents (e. g. , other users, content providers). In realistic settings, this is often not true – the dynamics of an RS ecosystem couple the long-term utility of all agents. In this work, we explore settings in which content providers cannot remain viable unless they receive a certain level of user engagement. We formulate this problem as one of equilibrium selection in the induced dynamical system, and show that it can be solved as an optimal constrained matching problem. Our model ensures the system reaches an equilibrium with maximal social welfare supported by a sufficiently diverse set of viable providers. We demonstrate that even in a simple, stylized dynamical RS model, the standard myopic approach to recommendation - always matching a user to the best provider - performs poorly. We develop several scalable techniques to solve the matching problem, and also draw connections to various notions of user regret and fairness, arguing that these outcomes are fairer in a utilitarian sense.

AIJ Journal 2020 Journal Article

Preference elicitation and robust winner determination for single- and multi-winner social choice

• Tyler Lu
• Craig Boutilier

The use of voting schemes based on rankings of alternatives to solve social choice problems can often impose significant burden on voters, both in terms of communication and cognitive requirements. In this paper, we develop techniques for preference elicitation in voting settings (i. e. , vote elicitation) that can alleviate this burden by minimizing the amount of preference information needed to find (approximately or exactly) optimal outcomes. We first describe robust optimization techniques for determining winning alternatives given partial preference information (i. e. , partial rankings) using the notion of minimax regret. We show that the corresponding computational problem is tractable for some important voting rules, and intractable for others. We then use the solution to the minimax-regret optimization as the basis for vote elicitation schemes that determine appropriate preference queries for voters to quickly reduce potential regret. We apply these techniques to multi-winner social choice problems as well, in which a slate of alternatives must be selected, developing both exact and greedy robust optimization procedures. Empirical results on several data sets validate the effectiveness of our techniques.

IJCAI Conference 2019 Conference Paper

Advantage Amplification in Slowly Evolving Latent-State Environments

• Martin Mladenov
• Ofer Meshi
• Jayden Ooi
• Dale Schuurmans
• Craig Boutilier

Latent-state environments with long horizons, such as those faced by recommender systems, pose significant challenges for reinforcement learning (RL). In this work, we identify and analyze several key hurdles for RL in such environments, including belief state error and small action advantage. We develop a general principle called advantage amplification that an overcome these hurdles through the use of temporal abstraction. We propose several aggregation methods and prove they induce amplification in certain settings. We also bound the loss in optimality incurred by our methods in environments where latent state evolves slowly and demonstrate their performance empirically in a stylized user-modeling task.

AIJ Journal 2019 Journal Article

Empathetic decision making in social networks

• Amirali Salehi-Abari
• Craig Boutilier
• Kate Larson

Social networks play a central role in the transactions and decision making of individuals by correlating the behaviors and preferences of connected agents. We introduce a notion of empathy in social networks, in which individuals derive utility based on both their own intrinsic preferences, and empathetic preferences determined by the satisfaction of their neighbors in the network. After theoretically analyzing the properties of our empathetic framework, we study the problem of group recommendation, or consensus decision making, within this framework. We show how this problem translates into a weighted form of classical preference aggregation (e. g. , social welfare maximization or certain forms of voting), and develop scalable optimization algorithms for this task. Furthermore, we show that our framework can be generalized to encompass other multiagent systems problems, such as constrained resource allocation, and provide scalable iterative algorithms for these generalizations. Our empirical experiments demonstrate the value of accounting for empathetic preferences in group decisions, and the tractability of our algorithms.

AAMAS Conference 2019 Conference Paper

Experiential Preference Elicitation for Autonomous Heating and Cooling Systems

• Andrew Perrault
• Craig Boutilier

AI systems that act on behalf of users require knowledge of user preferences, which can be acquired by preference elicitation. In many settings, users can respond more easily and accurately to preference queries reflecting their current, or recently experienced, context (e. g. , state of the environment), than to those reflecting contexts further removed. We develop and study a formal model of experiential elicitation (EE) in which query costs and response noise are state-dependent. EE settings tightly couple the problems of control and elicitation. We provide some analysis of this abstract model, and illustrate its applicability in household heating/cooling management. We propose the use of relative value queries, asking the user to compare the immediate utility of two states, whose difficulty is related to the degree and recency of a user’s experience with those states. We develop a Gaussian process-based approach for modeling user preferences in dynamic EE domains and show that it accrues higher reward than several natural baselines.

UAI Conference 2019 Conference Paper

Perturbed-History Exploration in Stochastic Linear Bandits

• Branislav Kveton
• Csaba Szepesvári
• Mohammad Ghavamzadeh
• Craig Boutilier

We propose a new online algorithm for cumulative regret minimization in a stochastic linear bandit. The algorithm pulls the arm with the highest estimated reward in a linear model trained on its perturbed history. Therefore, we call it perturbed-history exploration in a linear bandit (LinPHE). The perturbed history is a mixture of observed rewards and randomly generated i. i. d. pseudo-rewards. We derive a $\tilde{O}(d \sqrt{n})$ gap-free bound on the $n$-round regret of LinPHE, where $d$ is the number of features. The key steps in our analysis are new concentration and anti-concentration bounds on the weighted sum of Bernoulli random variables. To show the generality of our design, we generalize LinPHE to a logistic model. We evaluate our algorithms empirically and show that they are practical.

IJCAI Conference 2019 Conference Paper

Perturbed-History Exploration in Stochastic Multi-Armed Bandits

• Branislav Kveton
• Csaba Szepesvári
• Mohammad Ghavamzadeh
• Craig Boutilier

We propose an online algorithm for cumulative regret minimization in a stochastic multi-armed bandit. The algorithm adds O(t) i. i. d. pseudo-rewards to its history in round t and then pulls the arm with the highest average reward in its perturbed history. Therefore, we call it perturbed-history exploration (PHE). The pseudo-rewards are carefully designed to offset potentially underestimated mean rewards of arms with a high probability. We derive near-optimal gap-dependent and gap-free bounds on the n-round regret of PHE. The key step in our analysis is a novel argument that shows that randomized Bernoulli rewards lead to optimism. Finally, we empirically evaluate PHE and show that it is competitive with state-of-the-art baselines.

IJCAI Conference 2019 Conference Paper

SlateQ: A Tractable Decomposition for Reinforcement Learning with Recommendation Sets

• Eugene Ie
• Vihan Jain
• Jing Wang
• Sanmit Narvekar
• Ritesh Agarwal
• Rui Wu
• Heng-Tze Cheng
• Tushar Chandra

Reinforcement learning methods for recommender systems optimize recommendations for long-term user engagement. However, since users are often presented with slates of multiple items---which may have interacting effects on user choice---methods are required to deal with the combinatorics of the RL action space. We develop SlateQ, a decomposition of value-based temporal-difference and Q-learning that renders RL tractable with slates. Under mild assumptions on user choice behavior, we show that the long-term value (LTV) of a slate can be decomposed into a tractable function of its component item-wise LTVs. We demonstrate our methods in simulation, and validate the scalability and effectiveness of decomposed TD-learning on YouTube.

NeurIPS Conference 2018 Conference Paper

Data center cooling using model-predictive control

• Nevena Lazic
• Craig Boutilier
• Tyler Lu
• Eehern Wong
• Binz Roy
• MK Ryu
• Greg Imwalle

Despite impressive recent advances in reinforcement learning (RL), its deployment in real-world physical systems is often complicated by unexpected events, limited data, and the potential for expensive failures. In this paper, we describe an application of RL “in the wild” to the task of regulating temperatures and airflow inside a large-scale data center (DC). Adopting a data-driven, model-based approach, we demonstrate that an RL agent with little prior knowledge is able to effectively and safely regulate conditions on a server floor after just a few hours of exploration, while improving operational efficiency relative to existing PID controllers.

NeurIPS Conference 2018 Conference Paper

Non-delusional Q-learning and value-iteration

• Tyler Lu
• Dale Schuurmans
• Craig Boutilier

We identify a fundamental source of error in Q-learning and other forms of dynamic programming with function approximation. Delusional bias arises when the approximation architecture limits the class of expressible greedy policies. Since standard Q-updates make globally uncoordinated action choices with respect to the expressible policy class, inconsistent or even conflicting Q-value estimates can result, leading to pathological behaviour such as over/under-estimation, instability and even divergence. To solve this problem, we introduce a new notion of policy consistency and define a local backup process that ensures global consistency through the use of information sets---sets that record constraints on policies consistent with backed-up Q-values. We prove that both the model-based and model-free algorithms using this backup remove delusional bias, yielding the first known algorithms that guarantee optimal results under general conditions. These algorithms furthermore only require polynomially many information sets (from a potentially exponential support). Finally, we suggest other practical heuristics for value-iteration and Q-learning that attempt to reduce delusional bias.

IJCAI Conference 2018 Conference Paper

Planning and Learning with Stochastic Action Sets

• Craig Boutilier
• Alon Cohen
• Avinatan Hassidim
• Yishay Mansour
• Ofer Meshi
• Martin Mladenov
• Dale Schuurmans

In many practical uses of reinforcement learning (RL) the set of actions available at a given state is a random variable, with realizations governed by an exogenous stochastic process. Somewhat surprisingly, the foundations for such sequential decision processes have been unaddressed. In this work, we formalize and investigate MDPs with stochastic action sets (SAS-MDPs) to provide these foundations. We show that optimal policies and value functions in this model have a structure that admits a compact representation. From an RL perspective, we show that Q-learning with sampled action sets is sound. In model-based settings, we consider two important special cases: when individual actions are available with independent probabilities, and a sampling-based model for unknown distributions. We develop polynomial-time value and policy iteration methods for both cases, and provide a polynomial-time linear programming solution for the first case.

AAMAS Conference 2018 Conference Paper

Toward User-Centric Recommender Systems

• Craig Boutilier

Artificial intelligence and machine learning technologies continue to broaden and influence our access to information, entertainment, products and services—and each other—through data-driven recommendations. While the increased access afforded by AI has undoubtedly improved certain aspects of social welfare, the ability of recommenders to generate genuinely personalized recommendations and engage users in meaningful ways remains limited. Furthermore, our understanding of how AI recommenders shape long-term user behavior is poorly understood. In this talk, I will discuss the role that various AI techniques have to play in next-generation, user-centric recommender systems. Among these are preference modeling and preference elicitation; reinforcement learning and latent state models; behavioral decision theory and economics; and modeling of user behavioral preferences. I will also highlight challenges that emerge when putting these methods into practice.

IJCAI Conference 2017 Conference Paper

Logistic Markov Decision Processes

• Martin Mladenov
• Craig Boutilier
• Dale Schuurmans
• Ofer Meshi
• Gal Elidan
• Tyler Lu

User modeling in advertising and recommendation has typically focused on myopic predictors of user responses. In this work, we consider the long-term decision problem associated with user interaction. We propose a concise specification of long-term interaction dynamics by combining factored dynamic Bayesian networks with logistic predictors of user responses, allowing state-of-the-art prediction models to be seamlessly extended. We show how to solve such models at scale by providing a constraint generation approach for approximate linear programming that overcomes the variable coupling and non-linearity induced by the logistic regression predictor. The efficacy of the approach is demonstrated on advertising domains with up to 2^54 states and 2^39 actions.

AAMAS Conference 2017 Conference Paper

Multiple-Profile Prediction-of-Use Games

• Andrew Perrault
• Craig Boutilier

Prediction-of-use (POU) games were developed by Vinyals et al. [4] to address the mismatch between the costs of energy suppliers and the incentives imposed on consumers by a fixed-rate electricity tariff. However, the POU games framework does not address the question of how consumers should coordinate to maximize social welfare. To address this, we develop an extension to POU games, which we term MPOU games, where agents report multiple acceptable electricity use profiles. We show that MPOU games have many of the same properties that make POU games attractive, e. g. , convexity. Despite this, MPOU games introduce new incentive issues that prevent the consequences of convexity from being exploited directly, a problem we analyze and resolve. We validate our approach with experimental results using utility models learned from real electricity use data.

IJCAI Conference 2017 Conference Paper

Multiple-Profile Prediction-of-Use Games

• Andrew Perrault
• Craig Boutilier

Prediction-of-use (POU) games (Robu et al. , 2017) address the mismatch between energy supplier costs and the incentives imposed on consumers by a fixed-rate electricity tariff. However, the framework does not address how consumers should coordinate to maximize social welfare. To address this, we develop MPOU games, an extension of POU games in which agents report multiple acceptable electricity use profiles. We show that MPOU games share many attractive properties with POU games (e. g. , convexity). Despite this, MPOU games introduce new incentive issues that prevent the consequences of convexity from being exploited directly, a problem we analyze and resolve. We validate our approach with experimental results using utility models learned from real electricity use data.

UAI Conference 2016 Conference Paper

Budget Allocation using Weakly Coupled, Constrained Markov Decision Processes

• Craig Boutilier
• Tyler Lu

We consider the problem of budget (or other resource) allocation in sequential decision problems involving a large number of concurrently running sub-processes, whose only interaction is through their consumption of budget. Our first contribution is the introduction of budgeted MDPs (BMDPs), an MDP model in which policies/values are a function of available budget, (c. f. constrained MDPs which are solved given a fixed budget). BMDPs allow one to explicitly trade off allocated budget and expected value. We show that optimal value functions are concave, non-decreasing in budget, and piecewise-linear in the finite horizon case, and can be computed by dynamic programming (and support ready approximation). Our second contribution is a method that exploits BMDP solutions to allocate budget to a large number of independent BMDPs, coupled only by their common budget pool. The problem can be cast as a multiple-choice knapsack problem, which admits an efficient, optimal greedy algorithm. Empirical results in an online advertising domain confirm the efficacy of our methods.

IJCAI Conference 2015 Conference Paper

Approximately Stable Pricing for Coordinated Purchasing of Electricity

• Andrew Perrault
• Craig Boutilier

Matching markets are often used in exchange settings (e. g. , supply chain) to increase economic efficiency while respecting certain global constraints on outcomes. We investigate their application to pricing and cost sharing in group purchasing of electricity in smart grid settings. The task is complicated by the complexities of producer cost functions due to constraints on generation from different sources (they are sufficiently complex that welfare-optimal matchings are not usually in equilibrium). We develop two novel cost sharing schemes: one based on Shapley values that is “fair, ” but computationally intensive; and one that captures many of the essential properties of Shapley pricing, but scales to large numbers of consumers. Empirical results show these schemes achieve a high degree of stability in practice and can be made more stable by sacrificing small amounts (< 2%) of social welfare.

AIJ Journal 2015 Journal Article

Optimal social choice functions: A utilitarian view

• Craig Boutilier
• Ioannis Caragiannis
• Simi Haber
• Tyler Lu
• Ariel D. Procaccia
• Or Sheffet

We adopt a utilitarian perspective on social choice, assuming that agents have (possibly latent) utility functions over some space of alternatives. For many reasons one might consider mechanisms, or social choice functions, that only have access to the ordinal rankings of alternatives by the individual agents rather than their utility functions. In this context, one possible objective for a social choice function is the maximization of (expected) social welfare relative to the information contained in these rankings. We study such optimal social choice functions under three different models, and underscore the important role played by scoring functions. In our worst-case model, no assumptions are made about the underlying distribution and we analyze the worst-case distortion—or degree to which the selected alternative does not maximize social welfare—of optimal (randomized) social choice functions. In our average-case model, we derive optimal functions under neutral (or impartial culture) probabilistic models. Finally, a very general learning-theoretic model allows for the computation of optimal social choice functions (i. e. , ones that maximize expected social welfare) under arbitrary, sampleable distributions. In the latter case, we provide both algorithms and sample complexity results for the class of scoring functions, and further validate the approach empirically.

AAAI Conference 2015 Conference Paper

The Pricing War Continues: On Competitive Multi-Item Pricing

• Omer Lev
• Joel Oren
• Craig Boutilier
• Jeffrey Rosenschein

We study a game with strategic vendors (the agents) who own multiple items and a single buyer with a submodular valuation function. The goal of the vendors is to maximize their revenue via pricing of the items, given that the buyer will buy the set of items that maximizes his net payoff. We show this game may not always have a pure Nash equilibrium, in contrast to previous results for the special case where each vendor owns a single item. We do so by relating our game to an intermediate, discrete game in which the vendors only choose the available items, and their prices are set exogenously afterwards. We further make use of the intermediate game to provide tight bounds on the price of anarchy for the subset games that have pure Nash equilibria; we find that the optimal PoA reached in the previous special cases does not hold, but only a logarithmic one. Finally, we show that for a special case of submodular functions, efficient pure Nash equilibria always exist.

AAAI Conference 2015 Conference Paper

Value-Directed Compression of Large-Scale Assignment Problems

• Tyler Lu
• Craig Boutilier

Data-driven analytics—in areas ranging from consumer marketing to public policy—often allow behavior prediction at the level of individuals rather than population segments, offering the opportunity to improve decisions that impact large populations. Modeling such (generalized) assignment problems as linear programs, we propose a general value-directed compression technique for solving such problems at scale. We dynamically segment the population into cells using a form of column generation, constructing groups of individuals who can provably be treated identically in the optimal solution. This compression allows problems, unsolvable using standard LP techniques, to be solved effectively. Indeed, once a compressed LP is constructed, problems can solved in milliseconds. We provide a theoretical analysis of the methods, outline the distributed implementation of the requisite data processing, and show how a single compressed LP can be used to solve multiple variants of the original LP nearoptimally in real-time (e. g. , to support scenario analysis). We also show how the method can be leveraged in integer programming models. Experimental results on marketing contact optimization and political legislature problems validate the performance of our technique.

AAAI Conference 2014 Conference Paper

A Game-Theoretic Analysis of Catalog Optimization

• Joel Oren
• Nina Narodytska
• Craig Boutilier

Vendors of all types face the problem of selecting a slate of product offerings—their assortment or catalog—that will maximize their profits. The profitability of a catalog is determined by both customer preferences and the offerings of their competitors. We develop a game-theoretic model for analyzing the vendor catalog optimization problem in the face of competing vendors. We show that computing a best response is intractable in general, but can be solved by dynamic programming given certain informational or structural assumptions about consumer preferences. We also analyze conditions under which pure Nash equilibria exist and provide several price of anarchy/stability results

JMLR Journal 2014 Journal Article

Effective Sampling and Learning for Mallows Models with Pairwise-Preference Data

• Tyler Lu
• Craig Boutilier

Learning preference distributions is a critical problem in many areas (e.g., recommender systems, IR, social choice). However, many existing learning and inference methods impose restrictive assumptions on the form of user preferences that can be admitted as evidence. We relax these restrictions by considering as data arbitrary pairwise comparisons of alternatives, which represent the fundamental building blocks of ordinal rankings. We develop the first algorithms for learning Mallows models (and mixtures thereof) from pairwise comparison data. At the heart of our technique is a new algorithm, the generalized repeated insertion model (GRIM), which allows sampling from arbitrary ranking distributions, and conditional Mallows models in particular. While we show that sampling from a Mallows model with pairwise evidence is computationally difficult in general, we develop approximate samplers that are exact for many important special cases--and have provable bounds with pairwise evidence--and derive algorithms for evaluating log-likelihood, learning Mallows mixtures, and non-parametric estimation. Experiments on real-world data sets demonstrate the effectiveness of our approach. (Some parts of this paper appeared in: T. Lu and C. Boutilier, Learning Mallows Models with Pairwise Preferences, Proceedings of the Twenty- Eighth International Conference on Machine Learning (ICML 2011), pp.145-152, Bellevue, WA (2011).) [abs] [ pdf ][ bib ] &copy JMLR 2014. ( edit, beta )

AIJ Journal 2014 Journal Article

On the value of using group discounts under price competition

• Reshef Meir
• Tyler Lu
• Moshe Tennenholtz
• Craig Boutilier

The increasing use of group discounts has provided opportunities for buying groups with diverse preferences to coordinate their behavior in order to exploit the best offers from multiple vendors. We analyze this problem from the viewpoint of the vendors, asking under what conditions a vendor should adopt a volume-based price schedule rather than posting a fixed price. We consider both the case of monopolist vendors and cases where a vendor competes with other vendors. When vendors have uncertainty about buyers' valuations specified by a known distribution, we show that a vendor is always better off posting a fixed price, provided that buyer types (valuations) are i. i. d. and that other vendors also use fixed prices. We also show that these assumptions cannot be relaxed: if buyer types are not i. i. d. , or other vendors post discount schedules, then posting a schedule may yield a higher profit for the vendor. We provide similar results under a distribution-free uncertainty model, where vendors minimize their maximum regret over all type realizations.

AAAI Conference 2014 Conference Paper

Preference Elicitation and Interview Minimization in Stable Matchings

• Joanna Drummond
• Craig Boutilier

While stable matching problems are widely studied, little work has investigated schemes for effectively eliciting agent preferences using either preference (e. g. , comparison) queries or interviews (to form such comparisons); and no work has addressed how to combine both. We develop a new model for representing and assessing agent preferences that accommodates both forms of information and (heuristically) minimizes the number of queries and interviews required to determine a stable matching. Our Refine-then-Interview (RtI) scheme uses coarse preference queries to refine knowledge of agent preferences and relies on interviews only to assess comparisons of relatively “close” options. Empirical results show that RtI compares favorably to a recent pure interview minimization algorithm, and that the number of interviews it requires is generally independent of the size of the market.

AAAI Conference 2014 Conference Paper

Regret-Based Optimization and Preference Elicitation for Stackelberg Security Games with Uncertainty

• Thanh Nguyen
• Amulya Yadav
• Bo An
• Milind Tambe
• Craig Boutilier

Stackelberg security games (SSGs) have been deployed in a number of real-world domains. One key challenge in these applications is the assessment of attacker payoffs, which may not be perfectly known. Previous work has studied SSGs with uncertain payoffs modeled by interval uncertainty and provided maximin-based robust solutions. In contrast, in this work we propose the use of the less conservative minimax regret decision criterion for such payoff-uncertain SSGs and present the first algorithms for computing minimax regret for SSGs. We also address the challenge of preference elicitation, using minimax regret to develop the first elicitation strategies for SSGs. Experimental results validate the effectiveness of our approaches.

AAAI Conference 2014 Conference Paper

Robust Winners and Winner Determination Policies under Candidate Uncertainty

• Craig Boutilier
• Jérôme Lang
• Joel Oren
• Héctor Palacios

We consider voting situations in which some candidates may turn out to be unavailable. When determining availability is costly (e. g. , in terms of money, time, or computation), voting prior to determining candidate availability and testing the winner’s availability after the vote may be beneficial. However, since few voting rules are robust to candidate deletion, winner determination requires a number of such availability tests. We outline a model for analyzing such problems, defining robust winners relative to potential candidate unavailability. We assess the complexity of computing robust winners for several voting rules. Assuming a distribution over availability, and costs for availability tests/queries, we describe algorithms for computing optimal query policies, which minimize the expected cost of determining true winners.

IJCAI Conference 2013 Conference Paper

Analysis and Optimization of Multi-Dimensional Percentile Mechanisms

• Xin Sui
• Craig Boutilier
• Tuomas Sandholm

We consider the mechanism design problem for agents with single-peaked preferences over multi-dimensional domains when multiple alternatives can be chosen. Facility location and committee selection are classic embodiments of this problem. We propose a class of percentile mechanisms, a form of generalized median mechanisms, that are strategy-proof, and derive worst-case approximation ratios for social cost and maximum load for L1 and L2 cost models. More importantly, we propose a samplebased framework for optimizing the choice of percentiles relative to any prior distribution over preferences, while maintaining strategy-proofness. Our empirical investigations, using social cost and maximum load as objectives, demonstrate the viability of this approach and the value of such optimized mechanisms vis-à-vis mechanisms derived through worst-case analysis.

IJCAI Conference 2013 Conference Paper

Efficient Vote Elicitation under Candidate Uncertainty

• Joel Oren
• Yuval Filmus
• Craig Boutilier

Top-k voting is an especially natural form of partial vote elicitation in which only length k prefixes of rankings are elicited. We analyze the ability of top-k vote elicitation to correctly determine true winners, with high probability, given probabilistic models of voter preferences and candidate availability. We provide bounds on the minimal value of k required to determine the correct winner under the plurality and Borda voting rules, considering both worst-case preference profiles and profiles drawn from the impartial culture and Mallows probabilistic models. We also derive conditions under which the special case of zero-elicitation (i. e. , k = 0) produces the correct winner. We provide empirical results that confirm the value of top-k voting.

IJCAI Conference 2013 Conference Paper

Elicitation and Approximately Stable Matching with Partial Preferences

• Joanna Drummond
• Craig Boutilier

Algorithms for stable marriage and related matching problems typically assume that full preference information is available. While the Gale-Shapley algorithm can be viewed as a means of eliciting preferences incrementally, it does not prescribe a general means for matching with incomplete information, nor is it designed to minimize elicitation. We propose the use of maximum regret to measure the (inverse) degree of stability of a matching with partial preferences; minimax regret to find matchings that are maximally stable in the presence of partial preferences; and heuristic elicitation schemes that use max regret to determine relevant preference queries. We show that several of our schemes find stable matchings while eliciting considerably less preference information than Gale- Shapley and are much more appropriate in settings where approximate stability is viable.

IJCAI Conference 2013 Conference Paper

Multi-Dimensional Single-Peaked Consistency and Its Approximations

• Xin Sui
• Alex Francois-Nienaber
• Craig Boutilier

Single-peakedness is one of the most commonly used domain restrictions in social choice. However, the extent to which agent preferences are single-peaked in practice, and the extent to which recent proposals for approximate single-peakedness can further help explain voter preferences, is unclear. In this article, we assess the ability of both single-dimensional and multi-dimensional approximations to explain preference profiles drawn from several real-world elections. We develop a simple branch-andbound algorithm that finds multi-dimensional, singlepeaked axes that best fit a given profile, and which works with several forms of approximation. Empirical results on two election data sets show that preferences in these elections are far from single-peaked in any onedimensional space, but are nearly single-peaked in two dimensions. Our algorithms are reasonably efficient in practice, and also show excellent anytime performance.

IJCAI Conference 2013 Conference Paper

Multi-Winner Social Choice with Incomplete Preferences

• Tyler Lu
• Craig Boutilier

Multi-winner social choice considers the problem of selecting a slate of K options to realize some social objective. It has found application in the construction of political legislatures and committees, product recommendation, and related problems, and has recently attracted attention from a computational perspective. We address the multi-winner problem when facing incomplete voter preferences, using the notion of minimax regret to determine a robust slate of options in the presence of preference uncertainty. We analyze the complexity of this problem and develop new exact and greedy robust optimization algorithms for its solution. Using these techniques, we also develop preference elicitation heuristics which, in practice, allow us to find near-optimal slates with considerable savings in the preference information required vis-à-vis complete votes.

AAAI Conference 2013 Conference Paper

On the Value of Using Group Discounts under Price Competition

• Reshef Meir
• Tyler Lu
• Moshe Tennenholtz
• Craig Boutilier

The increasing use of group discounts has provided opportunities for buying groups with diverse preferences to coordinate their behavior in order to exploit the best offers from multiple vendors. We analyze this problem from the viewpoint of the vendors, asking under what conditions a vendor should adopt a volume-based price schedule rather than posting a fixed price, either as a monopolist or when competing with other vendors. When vendors have uncertainty about buyers’ valuations specified by a known distribution, we show that a vendor is always better off posting a fixed price, provided that buyers’ types are i. i. d. and that other vendors also use fixed prices. We also show that these assumptions cannot be relaxed: if buyers are not i. i. d. , or other vendors post discount schedules, then posting a schedule may yield higher profit for the vendor. We provide similar results under a distribution-free uncertainty model, where vendors minimize their maximum regret over all type realizations.

RLDM Conference 2013 Conference Abstract

Preference Elicitation for Social Choice: A Study in Stable Matching and Voting

• Craig Boutilier

(Joint work with Joanna Drummond and Tyler Lu) While the methods of social choice provide firm foundations for many decision problems involving groups of individuals, their practical realization requires some means of eliciting, assessing, or learning the underlying preferences of participants. This can impose a tremendous cognitive burden on participants, who may be required provide precise rankings or utilities for dozens, hundreds, or thousands of alternatives, only to discover that much of this information has no impact on the ultimate decision. In this talk, I will describe methods for robust optimization in social choice problems given only partial user preference information, using the concept of minimax regret. I will also describe techniques for effectively eliciting user preferences, driven by the robust solutions of the partial preference problems, that allow the computation of optimal decisions with relatively little preference information. I will focus on the application of these techniques to stable matching problems, but also briefly describe the application to voting problems as time permits. And while I emphasize their use in distribution-free models, I will briefly describe how to probabilistic preference models to further reduce the elicitation burden.

AAAI Conference 2012 Conference Paper

A Dynamic Rationalization of Distance Rationalizability

• Craig Boutilier
• Ariel Procaccia

Distance rationalizability is an intuitive paradigm for developing and studying voting rules: given a notion of consensus and a distance function on preference profiles, a rationalizable voting rule selects an alternative that is closest to being a consensus winner. Despite its appeal, distance rationalizability faces the challenge of connecting the chosen distance measure and consensus notion to an operational measure of social desirability. We tackle this issue via the decisiontheoretic framework of dynamic social choice, in which a social choice Markov decision process (MDP) models the dynamics of voter preferences in response to winner selection. We show that, for a prominent class of distance functions, one can construct a social choice MDP, with natural preference dynamics and rewards, such that a voting rule is (votewise) rationalizable with respect to the unanimity consensus for a given distance function iff it is a (deterministic) optimal policy in the MDP. This provides an alternative rationale for distance rationalizability, demonstrating the equivalence of rationalizable voting rules in a static sense and winner selection to maximize societal utility in a dynamic process.

ICML Conference 2012 Conference Paper

Active Learning for Matching Problems

• Laurent Charlin
• Richard S. Zemel
• Craig Boutilier

UAI Conference 2012 Conference Paper

Bayesian Vote Manipulation: Optimal Strategies and Impact on Welfare

• Tyler Lu
• Pingzhong Tang
• Ariel D. Procaccia
• Craig Boutilier

Most analyses of manipulation of voting schemes have adopted two assumptions that greatly diminish their practical import. First, it is usually assumed that the manipulators have full knowledge of the votes of the nonmanipulating agents. Second, analysis tends to focus on the probability of manipulation rather than its impact on the social choice objective (e.g., social welfare). We relax both of these assumptions by analyzing optimal Bayesian manipulation strategies when the manipulators have only partial probabilistic information about nonmanipulator votes, and assessing the expected loss in social welfare (in the broad sense of the term). We present a general optimization framework for the derivation of optimal manipulation strategies given arbitrary voting rules and distributions over preferences. We theoretically and empirically analyze the optimal manipulability of some popular voting rules using distributions and real data sets that go well beyond the common, but unrealistic, impartial culture assumption. We also shed light on the stark difference between the loss in social welfare and the probability of manipulation by showing that even when manipulation is likely, impact to social welfare is slight (and often negligible).

AAMAS Conference 2012 Conference Paper

Eliciting Forecasts from Self-interested Experts: Scoring Rules for Decision Makers

• Craig Boutilier

Scoring rules for eliciting expert predictions of random variables are usually developed assuming that experts derive utility only from the quality of their predictions. We study more realistic settings in which (a) the principal is a decision maker who takes a decision based on the expert's prediction; and (b) the expert has an inherent \emph{interest} in the decision. Not surprisingly, in such situations, the expert usually has an incentive to misreport her forecast to influence the choice of the decision maker. We develop a general model for this setting and introduce the concept of a \emph{compensation rule}. When combined with the expert's inherent utility for decisions, a compensation rule induces a \emph{net scoring rule} that behaves like a traditional scoring rule. Assuming full knowledge of expert utility, we provide a complete characterization of all (strictly) proper compensation rules. We then analyze the case when the expert's utility function is not fully known to the decision maker. We show bounds on: (a) expert incentive to misreport; (b) the degree to which an expert will misreport; and (c) decision maker loss in utility due to such uncertainty. These bounds depend in natural ways on the degree of uncertainty, the local degree of convexity of net scoring function, and properties of the decision maker's utility function. Finally, we briefly discuss the use of compensation rules in prediction markets.

UAI Conference 2011 Conference Paper

A Framework for Optimizing Paper Matching

• Laurent Charlin
• Richard S. Zemel
• Craig Boutilier

At the heart of many scientific conferences is the problem of matching submitted papers to suitable reviewers. Arriving at a good assignment is a major and important challenge for any conference organizer. In this paper we propose a framework to optimize paper-to-reviewer assignments. Our framework uses suitability scores to measure pairwise affinity between papers and reviewers. We show how learning can be used to infer suitability scores from a small set of provided scores, thereby reducing the burden on reviewers and organizers. We frame the assignment problem as an integer program and propose several variations for the paper-to-reviewer matching domain. We also explore how learning and matching interact. Experiments on two conference data sets examine the performance of several learning methods as well as the effectiveness of the matching formulations.

IJCAI Conference 2011 Conference Paper

Budgeted Social Choice: From Consensus to Personalized Decision Making

• Tyler Lu
• Craig Boutilier

We develop a general framework for social choice problems in which a limited number of alternatives can be recommended to an agent population. In our budgeted social choice model, this limit is determined by a budget, capturing problems that arise naturally in a variety of contexts, and spanning the continuum from pure consensus decision making (i. e. , standard social choice) to fully personalized recommendation. Our approach applies a form of segmentation to social choice problems- requiring the selection of diverse options tailored to different agent types-and generalizes certain multi-winner election schemes. We show that standard rank aggregation methods perform poorly, and that optimization in our model is NP-complete; but we develop fast greedy algorithms with some theoretical guarantees. Experiments on real-world datasets demonstrate the effectiveness of our algorithms.

AAAI Conference 2011 Conference Paper

Efficiency and Privacy Tradeoffs in Mechanism Design

• Xin Sui
• Craig Boutilier

A key problem in mechanism design is the construction of protocols that reach socially efficient decisions with minimal information revelation. This can reduce agent communication, and further, potentially increase privacy in the sense that agents reveal no more private information than is needed to determine an optimal outcome. This is not always possible: previous work has explored the tradeoff between communication cost and efficiency, and more recently, communication and privacy. We explore a third dimension: the tradeoff between privacy and efficiency. By sacrificing efficiency, we can improve the privacy of a variety of existing mechanisms. We analyze these tradeoffs in both second-price auctions and facility location problems (introducing new incremental mechanisms for facility location along the way). Our results show that sacrifices in efficiency can provide gains in privacy (and communication), in both the average and worst case.

IJCAI Conference 2011 Conference Paper

Eliciting Additive Reward Functions for Markov Decision Processes

• Kevin Regan
• Craig Boutilier

Specifying the reward function of a Markov decision process (MDP) can be demanding, requiring human assessment of the precise quality of, and tradeoffs among, various states and actions. However, reward functions often possess considerable structure which can be leveraged to streamline their specification. We develop new, decision-theoretically sound heuristics for eliciting rewards for factored MDPs whose reward functions exhibit additive independence. Since we can often find good policies without complete reward specification, we also develop new (exact and approximate) algorithms for robust optimization ofimprecise-reward MDPs with such additive reward. Our methods are evaluated in two domains: autonomic computing and assistive technology.

ICML Conference 2011 Conference Paper

Learning Mallows Models with Pairwise Preferences

• Tyler Lu
• Craig Boutilier

AAAI Conference 2011 Conference Paper

Recommendation Sets and Choice Queries: There Is No Exploration/Exploitation Tradeoff!

• Paolo Viappiani
• Craig Boutilier

IJCAI Conference 2011 Conference Paper

Robust Approximation and Incremental Elicitation in Voting Protocols

• Tyler Lu
• Craig Boutilier

While voting schemes provide an effective means for aggregating preferences, methods for the effective elicitation of voter preferences have received little attention. We address this problem by first considering approximate winner determination when incomplete voter preferences are provided. Exploiting natural scoring metrics, we use max regret to measure the quality or robustness of proposed winners, and develop polynomial time algorithms for computing the alternative with minimax regret for several popular voting rules. We then show how minimax regret can be used to effectively drive incremental preference/vote elicitation and devise several heuristics for this process. Despite worst-case theoretical results showing that most voting protocols require nearly complete voter preferences to determine winners, we demonstrate the practical effectiveness of regret-based elicitation for determining both approximate and exact winners on several real-world data sets.

IJCAI Conference 2011 Conference Paper

Robust Online Optimization of Reward-Uncertain MDPs

• Kevin Regan
• Craig Boutilier

Imprecise-reward Markov decision processes (IRMDPs) are MDPs in which the reward function is only partially specified (e. g. , by some elicitation process). Recent work using minimax regret to solve IRMDPs has shown, despite their theoretical intractability, how the set of policies that are nondominated w. r. t. reward uncertainty can be exploited to accelerate regret computation. However, the number of nondominated policies is generally so large as to undermine this leverage. In this paper, we show how the quality of the approximation can be improved online by pruning/adding nondominated policies during reward elicitation, while maintaining computational tractability. Drawing insights from the POMDP literature, we also develop a new anytime algorithm for constructing the set of nondominated policies with provable (anytime) error bounds. These bounds can be exploited to great effect in our online approximation scheme.

AAAI Conference 2010 Conference Paper

Automated Channel Abstraction for Advertising Auctions

• William Walsh
• Craig Boutilier
• Tuomas Sandholm
• Rob Shields
• George Nemhauser
• David Parkes

The use of simple auction mechanisms like the GSP in online advertising can lead to significant loss of efficiency and revenue when advertisers have rich preferences—even simple forms of expressiveness like budget constraints can lead to suboptimal outcomes. While the optimal allocation of inventory can provide greater efficiency and revenue, natural formulations of the underlying optimization problems grow exponentially in the number of features of interest, presenting a key practical challenge. To address this problem, we propose a means for automatically partitioning inventory into abstract channels so that the least relevant features are ignored. Our approach, based on LP/MIP column and constraint generation, dramatically reduces the size of the problem, thus rendering optimization computationally feasible at practical scales. Our algorithms allow for principled tradeoffs between tractability and solution quality. Numerical experiments demonstrate the computational practicality of our approach as well as the quality of the resulting abstractions.

NeurIPS Conference 2010 Conference Paper

Optimal Bayesian Recommendation Sets and Myopically Optimal Choice Query Sets

• Paolo Viappiani
• Craig Boutilier

Bayesian approaches to utility elicitation typically adopt (myopic) expected value of information (EVOI) as a natural criterion for selecting queries. However, EVOI-optimization is usually computationally prohibitive. In this paper, we examine EVOI optimization using \emph{choice queries}, queries in which a user is ask to select her most preferred product from a set. We show that, under very general assumptions, the optimal choice query w. r. t. \ EVOI coincides with \emph{optimal recommendation set}, that is, a set maximizing expected utility of the user selection. Since recommendation set optimization is a simpler, submodular problem, this can greatly reduce the complexity of both exact and approximate (greedy) computation of optimal choice queries. We also examine the case where user responses to choice queries are error-prone (using both constant and follow mixed multinomial logit noise models) and provide worst-case guarantees. Finally we present a local search technique that works well with large outcome spaces.

AAAI Conference 2010 Conference Paper

Robust Policy Computation in Reward-Uncertain MDPs Using Nondominated Policies

• Kevin Regan
• Craig Boutilier

The precise specification of reward functions for Markov decision processes (MDPs) is often extremely difficult, motivating research into both reward elicitation and the robust solution of MDPs with imprecisely specified reward (IRMDPs). We develop new techniques for the robust optimization of IR- MDPs, using the minimax regret decision criterion, that exploit the set of nondominated policies, i. e. , policies that are optimal for some instantiation of the imprecise reward function. Drawing parallels to POMDP value functions, we devise a Witness-style algorithm for identifying nondominated policies. We also examine several new algorithms for computing minimax regret using the nondominated set, and examine both practically and theoretically the impact of approximating this set. Our results suggest that a small subset of the nondominated set can greatly speed up computation, yet yield very tight approximations to minimax regret.

JAAMAS Journal 2010 Journal Article

Sequentially optimal repeated coalition formation under uncertainty

• Georgios Chalkiadakis
• Craig Boutilier

Abstract Coalition formation is a central problem in multiagent systems research, but most models assume common knowledge of agent types. In practice, however, agents are often unsure of the types or capabilities of their potential partners, but gain information about these capabilities through repeated interaction. In this paper, we propose a novel Bayesian, model-based reinforcement learning framework for this problem, assuming that coalitions are formed (and tasks undertaken) repeatedly. Our model allows agents to refine their beliefs about the types of others as they interact within a coalition. The model also allows agents to make explicit tradeoffs between exploration (forming “new” coalitions to learn more about the types of new potential partners) and exploitation (relying on partners about which more is known), using value of information to define optimal exploration policies. Our framework effectively integrates decision making during repeated coalition formation under type uncertainty with Bayesian reinforcement learning techniques. Specifically, we present several learning algorithms to approximate the optimal Bayesian solution to the repeated coalition formation and type-learning problem, providing tractable means to ensure good sequential performance. We evaluate our algorithms in a variety of settings, showing that one method in particular exhibits consistently good performance in practice. We also demonstrate the ability of our model to facilitate knowledge transfer across different dynamic tasks.

AAAI Conference 2010 Conference Paper

Simultaneous Elicitation of Preference Features and Utility

• Craig Boutilier
• Kevin Regan
• Paolo Viappiani

Most frameworks for utility elicitation assume a predefined set of features over which user preferences are expressed. We consider utility elicitation in the presence of subjective or user-defined features, whose definitions are not known in advance. We treat the problem of learning a user’s feature definition as one of concept learning, but whose goal is to learn only enough about the concept definition to enable a good decision to be made. This is complicated by the fact that user utility is unknown. We describe computational procedures for identifying optimal alternatives w. r. t minimax regret in the presence of both utility and concept uncertainty; and develop several heuristic query strategies that focus simultaneously on reduction of relevant concept and utility uncertainty.

ICML Conference 2009 Conference Paper

Online feature elicitation in interactive optimization

• Craig Boutilier
• Kevin Regan 0001
• Paolo Viappiani

AIJ Journal 2009 Journal Article

Practical solution techniques for first-order MDPs

• Scott Sanner
• Craig Boutilier

Many traditional solution approaches to relationally specified decision-theoretic planning problems (e. g. , those stated in the probabilistic planning domain description language, or PPDDL) ground the specification with respect to a specific instantiation of domain objects and apply a solution approach directly to the resulting ground Markov decision process (MDP). Unfortunately, the space and time complexity of these grounded solution approaches are polynomial in the number of domain objects and exponential in the predicate arity and the number of nested quantifiers in the relational problem specification. An alternative to grounding a relational planning problem is to tackle the problem directly at the relational level. In this article, we propose one such approach that translates an expressive subset of the PPDDL representation to a first-order MDP (FOMDP) specification and then derives a domain-independent policy without grounding at any intermediate step. However, such generality does not come without its own set of challenges—the purpose of this article is to explore practical solution techniques for solving FOMDPs. To demonstrate the applicability of our techniques, we present proof-of-concept results of our first-order approximate linear programming (FOALP) planner on problems from the probabilistic track of the ICAPS 2004 and 2006 International Planning Competitions.

UAI Conference 2009 Conference Paper

Regret-based Reward Elicitation for Markov Decision Processes

• Kevin Regan 0001
• Craig Boutilier

criteria. The “observability” of reward is a convenient fiction often assumed in the RL literature. The specification of a Markov decision process (MDP) can be difficult. Reward function specification is especially problematic; in practice, it is often cognitively complex and time-consuming for users to precisely specify rewards. This work casts the problem of specifying rewards as one of preference elicitation and aims to minimize the degree of precision with which a reward function must be specified while still allowing optimal or near-optimal policies to be produced. We first discuss how robust policies can be computed for MDPs given only partial reward information using the minimax regret criterion. We then demonstrate how regret can be reduced by efficiently eliciting reward information using bound queries, using regret-reduction as a means for choosing suitable queries. Empirical results demonstrate that regret-based reward elicitation offers an effective way to produce near-optimal policies without resorting to the precise specification of the entire reward function. Reward specification is difficult for three reasons. First, it requires the translation of user preferences—which states and actions are “good” and “bad”—into precise numerical rewards. As has been well-recognized in decision analysis, people find it extremely difficult to quantify their strength of preferences precisely using utility functions (and, by extension, reward functions) [10]. Second, the requirement to assess rewards and costs for all states and actions imposes an additional burden (one that can be somewhat alleviated by the use of multiattribute models in factored MDPs [5]). Finally, the elicitation problem in MDPs is further exacerbated by the potential conflation of immediate reward (i. e. , r(s, a)) with long-term value (either Q(s, a) or V (s)): states can be viewed as good or bad based on their ability to make other good states reachable.

AAAI Conference 2008 Conference Paper

Expressive Banner Ad Auctions and Model-Based Online Optimization for Clearing

• Craig Boutilier
• Tuomas Sandholm

We present the design of a banner advertising auction which is considerably more expressive than current designs. We describe a general model of expressive ad contracts/bidding and an allocation model that can be executed in real time through the assignment of fractions of relevant ad channels to specific advertiser contracts. The uncertainty in channel supply and demand is addressed by the formulation of a stochastic combinatorial optimization problem for channel allocation that is rerun periodically. We solve this in two different ways: fast deterministic optimization with respect to expectations; and a novel online sample-based stochastic optimization method— that can be applied to continuous decision spaces—which exploits the deterministic optimization as a black box. Experiments demonstrate the importance of expressive bidding and the value of stochastic optimization. 1

AAMAS Conference 2008 Conference Paper

Sequential Decision Making in Repeated Coalition Formation under Uncertainty

• Georgios Chalkiadakis
• Craig Boutilier

The problem of coalition formation when agents are uncertain about the types or capabilities of their potential partners is a critical one. In [3] a Bayesian reinforcement learning framework is developed for this problem when coalitions are formed (and tasks undertaken) repeatedly: not only does the model allow agents to refine their beliefs about the types of others, but uses value of information to define optimal exploration policies. However, computational approximations in that work are purely myopic. We present novel, non-myopic learning algorithms to approximate the optimal Bayesian solution, providing tractable means to ensure good sequential performance. We evaluate our algorithms in a variety of settings, and show that one, in particular, exhibits consistently good sequential performance. Further, it enables the Bayesian agents to transfer acquired knowledge among different dynamic tasks.

UAI Conference 2008 Conference Paper

Toward Experiential Utility Elicitation for Interface Customization

• Bowen Hui
• Craig Boutilier

User preferences for automated assistance often vary widely, depending on the situation, and quality or presentation of help. Developing effective models to learn individual preferences online requires domain models that associate observations of user behavior with their utility functions, which in turn can be constructed using utility elicitation techniques. However, most elicitation methods ask for users’ predicted utilities based on hypothetical scenarios rather than more realistic experienced utilities. This is especially true in interface customization, where users are asked to assess novel interface designs. We propose experiential utility elicitation methods for customization and compare these to predictive methods. As experienced utilities have been argued to better reflect true preferences in behavioral decision making, the purpose here is to investigate accurate and efficient procedures that are suitable for software domains. Unlike conventional elicitation, our results indicate that an experiential approach helps people understand stochastic outcomes, as well as better appreciate the sequential utility of intelligent assistance.

IJCAI Conference 2007 Conference Paper

• Nathana
• euml; l Hyafil
• Craig Boutilier

Classic direct mechanisms require full utility revelation from agents, which can be very difficult in practical multi-attribute settings. In this work, we study partial revelation within the framework of one-shot mechanisms. Each agent's type space is partitioned into a finite set of partial types and agents (should) report the partial type within which their full type lies. A classic result implies that implementation in dominant strategies is impossible in this model. We first show that a relaxation to Bayes-Nash implementation does not circumvent the problem. We then propose a class of partial revelation mechanisms that achieve approximate dominant strategy implementation, and describe a computationally tractable algorithm for myopically optimizing the partitioning of each agent's type space to reduce manipulability and social welfare loss. This allows for the automated design of one-shot partial revelation mechanisms with worst-case guarantees on both manipulability and efficiency.

IJCAI Conference 2007 Conference Paper

• Tuomas Sandholm
• Vincent Conitzer
• Craig Boutilier

Mechanism design is the study of preference aggregation protocols that work well in the face of self-interested agents. We present the first general-purpose techniques for automatically designing multistage mechanisms. These can reduce elicitation burden by only querying agents for information that is relevant given their answers to previous queries. We first show how to turn a given (e. g. , automatically designed using constrained optimization techniques) single-stage mechanism into the most efficient corresponding multistage mechanism given a specified elicitation tree. We then present greedy and dynamic programming (DP) algorithms that determine the elicitation tree (optimal in the DP case). Next, we show how the query savings inherent in the multistage model can be used to design the underlying single-stage mechanism to maximally take advantage of this approach. Finally, we present negative results on the design of multistage mechanisms that do not correspond to dominant-strategy single-stage mechanisms: an optimal multistage mechanism in general has to randomize over queries to hide information from the agents.

IJCAI Conference 2007 Conference Paper

• Georgios Chalkiadakis
• Craig Boutilier

Coalition formation is a problem of great interest in AI, allowing groups of autonomous, individually rational agents to form stable teams. Automating the negotiations underlying coalition formation is, naturally, of special concern. However, research to date in both AI and economics has largely ignored the potential presence of uncertainty in coalitional bargaining. We present a model of discounted coalitional bargaining where agents are uncertain about the types (or capabilities) of potential partners, and hence the value of a coalition. We cast the problem as a Bayesian game in extensive form, and describe its Perfect Bayesian Equilibria as the solutions to a polynomial program. We then present a heuristic algorithm using iterative coalition formation to approximate the optimal solution, and evaluate its performance.

ICAPS Conference 2007 Conference Paper

Approximate Solution Techniques for Factored First-Order MDPs

• Scott Sanner
• Craig Boutilier

Most traditional approaches to probabilistic planning in relationally specified MDPs rely on grounding the problem w. r. t. specific domain instantiations, thereby incurring a combinatorial blowup in the representation. An alternative approach is to lift a relational MDP to a first-order MDP (FOMDP) specification and develop solution approaches that avoid grounding. Unfortunately, state-of-the-art FOMDPs are inadequate for specifying factored transition models or additive rewards that scale with the domain size -- structure that is very natural in probabilistic planning problems. To remedy these deficiencies, we propose an extension of the FOMDP formalism known as a factored FOMDP and present generalizations of symbolic dynamic programming and linear-value approximation solutions to exploit its structure. Along the way, we also make contributions to the field of first-order probabilistic inference (FOPI) by demonstrating novel first-order structures that can be exploited without domain grounding. We present empirical results to demonstrate that we can obtain solutions whose complexity scales polynomially in the logarithm of the domain size -- results that are impossible to obtain with any previously proposed solution method.

AAMAS Conference 2007 Conference Paper

Coalition Formation under Uncertainty: Bargaining Equilibria and the Bayesian Core Stability Concept

• Georgios Chalkiadakis
• Evangelos Markakisy
• Craig Boutilier

Coalition formation is a problem of great interest in AI, allowing groups of autonomous, rational agents to form stable teams. Fur- thermore, the study of coalitional stability concepts and their re- lation to equilibria that guide the strategic interactions of agents during bargaining has lately attracted much attention. However, research to date in both AI and economics has largely ignored the potential presence of uncertainty when studying either coalitional stability or coalitional bargaining. This paper is the first to relate a (cooperative) stability concept under uncertainty, the Bayesian core (BC), with (non-cooperative) equilibrium concepts of coali- tional bargaining games. We prove that if the BC of a coalitional game (and of each subgame) is non-empty, then there exists an equilibrium of the corresponding bargaining game that produces a BC element; and conversely, if there exists a coalitional bargain- ing equilibrium (with certain properties), then it induces a BC configuration. We thus provide a non-cooperative justification of the BC stability concept. As a corollary, we establish a sufficient condition for the existence of the BC. Finally, for small games, we provide an algorithm to decide whether the BC is non-empty.

UAI Conference 2007 Conference Paper

Minimax regret based elicitation of generalized additive utilities

• Darius Braziunas
• Craig Boutilier

Abstract We describe the semantic foundations for elicitation of generalized additively independent (GAI) utilities using the minimax regret criterion, and propose several new query types and strategies for this purpose. Computational feasibility is obtained by exploiting the local GAI structure in the model. Our results provide a practical approach for implementing preference-based constrained configuration optimization as well as effective search in multiattribute product databases.

AIJ Journal 2006 Journal Article

Constraint-based optimization and utility elicitation using the minimax decision criterion

• Craig Boutilier
• Relu Patrascu
• Pascal Poupart
• Dale Schuurmans

In many situations, a set of hard constraints encodes the feasible configurations of some system or product over which multiple users have distinct preferences. However, making suitable decisions requires that the preferences of a specific user for different configurations be articulated or elicited, something generally acknowledged to be onerous. We address two problems associated with preference elicitation: computing a best feasible solution when the user's utilities are imprecisely specified; and developing useful elicitation procedures that reduce utility uncertainty, with minimal user interaction, to a point where (approximately) optimal decisions can be made. Our main contributions are threefold. First, we propose the use of minimax regret as a suitable decision criterion for decision making in the presence of such utility function uncertainty. Second, we devise several different procedures, all relying on mixed integer linear programs, that can be used to compute minimax regret and regret-optimizing solutions effectively. In particular, our methods exploit generalized additive structure in a user's utility function to ensure tractable computation. Third, we propose various elicitation methods that can be used to refine utility uncertainty in such a way as to quickly (i. e. , with as few questions as possible) reduce minimax regret. Empirical study suggests that several of these methods are quite successful in minimizing the number of user queries, while remaining computationally practical so as to admit real-time user interaction.

UAI Conference 2006 Conference Paper

Practical Linear Value-approximation Techniques for First-order MDPs

• Scott Sanner
• Craig Boutilier

Recent work on approximate linear programming (ALP) techniques for first-order Markov Decision Processes (FOMDPs) represents the value function linearly w.r.t. a set of first-order basis functions and uses linear programming techniques to determine suitable weights. This approach offers the advantage that it does not require simplification of the first-order value function, and allows one to solve FOMDPs independent of a specific domain instantiation. In this paper, we address several questions to enhance the applicability of this work: (1) Can we extend the first-order ALP framework to approximate policy iteration to address performance deficiencies of previous approaches? (2) Can we automatically generate basis functions and evaluate their impact on value function quality? (3) How can we decompose intractable problems with universally quantified rewards into tractable subproblems? We propose answers to these questions along with a number of novel optimizations and provide a comparative empirical evaluation on logistics problems from the ICAPS 2004 Probabilistic Planning Competition.

IJCAI Conference 2005 Conference Paper

A Decision-Theoretic Approach to Task Assistance for Persons with Dementia

• Jennifer Boger
• Pascal Poupart
• Jesse Hoey
• Craig Boutilier
• Geoff Fernie
• Alex

Cognitive assistive technologies that aid people with dementia (such as Alzheimer’s disease) hold the promise to provide such people with an increased level of independence. However, to realize this promise, such systems must account for the specific needs and preferences of individuals. We argue that this form of customization requires a sequential, decision-theoretic model of interaction. We describe both fully and partially observable Markov decision process (POMDP) models of a handwashing task, and show that, despite the potential computational complexity, these can be effectively solved and produce policies that are evaluated as useful by professional caregivers.

UAI Conference 2005 Conference Paper

Approximate Linear Programming for First-order MDPs

• Scott Sanner
• Craig Boutilier

We introduce a new approximate solution technique for first-order Markov decision processes (FOMDPs). Representing the value function linearly w.r.t. a set of first-order basis functions, we compute suitable weights by casting the corresponding optimization as a first-order linear program and show how off-the-shelf theorem prover and LP software can be effectively used. This technique allows one to solve FOMDPs independent of a specific domain instantiation; furthermore, it allows one to determine bounds on approximation error that apply equally to all domain instantiations. We apply this solution technique to the task of elevator scheduling with a rich feature space and multi-criteria additive reward, and demonstrate that it outperforms a number of intuitive, heuristicallyguided policies.

UAI Conference 2005 Conference Paper

Local Utility Elicitation in GAI Models

• Darius Braziunas
• Craig Boutilier

Structured utility models are essential for the effective representation and elicitation of complex multiattribute utility functions. Generalized additive independence (GAI) models provide an attractive structural model of user preferences, offering a balanced tradeoff between simplicity and applicability. While representation and inference with such models is reasonably well understood, elicitation of the parameters of such models has been studied less from a practical perspective. We propose a procedure to elicit GAI model parameters using only "local" utility queries rather than "global" queries over full outcomes. Our local queries take full advantage of GAI structure and provide a sound framework for extending the elicitation procedure to settings where the uncertainty over utility parameters is represented probabilistically. We describe experiments using a myopic value-of-information approach to elicitation in a large GAI model.

IJCAI Conference 2005 Conference Paper

Regret-based Utility Elicitation in Constraint-based Decision Problems

• Craig Boutilier
• Relu Patrascu
• Pascal Poupart
• Dale

We propose new methods of preference elicitation for constraint-based optimization problems based on the use of minimax regret. Specifically, we assume a constraintbased optimization problem (e. g. , product configuration) in which the objective function (e. g. , consumer preferences) are unknown or imprecisely specified. Assuming a graphical utility model, we describe several elicitation strategies that require the user to answer only binary (bound) queries on the utility model parameters. While a theoretically motivated algorithm can provably reduce regret quickly (in terms of number of queries), we demonstrate that, in practice, heuristic strategies perform much better, and are able to find optimal (or near-optimal) configurations with far fewer queries.

AAMAS Conference 2004 Conference Paper

Bayesian Reinforcement Learning for Coalition Formation Under Uncertainty

• Georgios Chalkiadakis
• Craig Boutilier

AAAI Conference 2004 Conference Paper

Eliciting Bid Taker Non-price Preferences in (Combinatorial) Auctions

• Craig Boutilier

Recent algorithms provide powerful solutions to the problem of determining cost-minimizing (or revenue-maximizing) allocations of items in combinatorial auctions. However, in many settings, criteria other than cost (e. g. , the number of winners, the delivery date of items, etc.) are also relevant in judging the quality of an allocation. Furthermore, the bid taker is usually uncertain about her preferences regarding tradeoffs between cost and nonprice features. We describe new methods that allow the bid taker to determine (approximately) optimal allocations despite this. These methods rely on the notion of minimax regret to guide the elicitation of preferences from the bid taker and to measure the quality of an allocation in the presence of utility function uncertainty. Computational experiments demonstrate the practicality of minimax computation and the efficacy of our elicitation techniques.

UAI Conference 2004 Conference Paper

Regret Minimizing Equilibria and Mechanisms for Games with Strict Type Uncertainty

• Nathanael Hyafil
• Craig Boutilier

Mechanism design has found considerable application to the construction of agent-interaction protocols. In the standard setting, the type (e.g., utility function) of an agent is not known by other agents, nor is it known by the mechanism designer. When this uncertainty is quantified probabilistically, a mechanism induces a game of incomplete information among the agents. However, in many settings, uncertainty over utility functions cannot easily be quantified. We consider the problem of incomplete information games in which type uncertainty is strict or unquantified. We propose the use of minimax regret as a decision criterion in such games, a robust approach for dealing with type uncertainty. We define minimax-regret equilibria and prove that these exist in mixed strategies for finite games. We also consider the problem of mechanism design in this framework by adopting minimax regret as an optimization criterion for the designer itself, and study automated optimization of such mechanisms.

AAAI Conference 2004 Conference Paper

Stochastic Local Search for POMDP Controllers

• Darius Braziunas
• Craig Boutilier

The search for finite-state controllers for partially observable Markov decision processes (POMDPs) is often based on approaches like gradient ascent, attractive because of their relatively low computational cost. In this paper, we illustrate a basic problem with gradient-based methods applied to POMDPs, where the sequential nature of the decision problem is at issue, and propose a new stochastic local search method as an alternative. The heuristics used in our procedure mimic the sequential reasoning inherent in optimal dynamic programming (DP) approaches. We show that our algorithm consistently finds higher quality controllers than gradient ascent, and is competitive with (and, for some problems, superior to) other state-of-the-art controller and DP-based algorithms on large-scale POMDPs.

NeurIPS Conference 2004 Conference Paper

VDCBPI: an Approximate Scalable Algorithm for Large POMDPs

• Pascal Poupart
• Craig Boutilier

Existing algorithms for discrete partially observable Markov decision processes can at best solve problems of a few thousand states due to two important sources of intractability: the curse of dimensionality and the policy space complexity. This paper describes a new algorithm (VDCBPI) that mitigates both sources of intractability by combining the Value Directed Compression (VDC) technique [13] with Bounded Pol- icy Iteration (BPI) [14]. The scalability of VDCBPI is demonstrated on synthetic network management problems with up to 33 million states. 1 Introduction Partially observable Markov decision processes (POMDPs) provide a natural and expres- sive framework for decision making, but their use in practice has been limited by the lack of scalable solution algorithms. Two important sources of intractability plague discrete model-based POMDPs: high dimensionality of belief space, and the complexity of policy or value function (VF) space. Classic solution algorithms [4, 10, 7], for example, compute value functions represented by exponentially many value vectors, each of exponential size. As a result, they can only solve POMDPs with on the order of 100 states. Consequently, much research has been devoted to mitigating these two sources of intractability. The complexity of policy/VF space has been addressed by observing that there are often very good policies whose value functions are representable by a small number of vectors. Various algorithms such as approximate vector pruning [9], point-based value iteration (PBVI) [12, 16], bounded policy iteration (BPI) [14], gradient ascent (GA) [11, 1] and stochastic local search (SLS) [3] exploit this fact to produce (often near-optimal) policies of low complexity (i. e. , few vectors) allowing larger POMDPs to be solved. Still these scale to problems of only roughly 1000 states, since each value vector may still have ex- ponential dimensionality. Conversely, it has been observed that belief states often carry more information than necessary. Hence, one can often reduce vector dimensionality by using compact representations such as decision trees (DTs) [2], algebraic decision dia- grams (ADDs) [8, 9], or linear combinations of small basis functions (LCBFs) [6], or by indirectly compressing the belief space into a small subspace by a value-directed compres- sion (VDC) [14] or exponential PCA [15]. Once compressed, classic solution methods can be used. However, since none of these approaches address the exponential complexity of policy/VF space, they can only solve slightly larger POMDPs (up to 8250 states [15]). Scalable POMDP algorithms can only be realized when both sources of intractability are tackled simultaneously. While Hansen and Feng [9] implemented such an algorithm by combining approximate state abstraction with approximate vector pruning, they didn't demonstrate the scalability of the approach on large problems. In this paper, we describe how to combine value directed compression (VDC) with bounded policy iteration (BPI) and demonstrate the scalability of the resulting algorithm (VDCBPI) on synthetic network management problems of up to 33 million states. Among the techniques that deal with the curse of dimensionality, VDC offers the advantage that the compressed POMDP can be di- rectly fed into existing POMDP algorithms with no (or only slight) adjustments. This is not the case for exponential-PCA, nor compact representations (DTs, ADDs, LCBFs). Among algorithms that mitigate policy space complexity, BPI distinguishes itself by its ability to avoid local optima (cf. GA), its efficiency (cf. SLS) and the fact that belief state monitoring is not required (cf. PBVI, approximate vector pruning). Beyond the combination of VDC with BPI, we offer two other contributions. We propose a new simple heuristic to compute good lossy value directed compressions. We also augment BPI with the ability to bias its policy search to reachable belief states. As a result, BPI can often find a much smaller policy of similar quality for a given initial belief state. 2 POMDP Background A POMDP is defined by: states S; actions A; observations Z; transition function T, where T (s, a, s ) denotes Pr(s |s, a); observation function Z, where Z(s, z) is the probability Pr(z|s, a) of observation z in state s after executing a; and reward function R, where R(s, a) is the immediate reward associated with s when executing a. We assume discrete state, action and observation sets and focus on discounted, infinite horizon POMDPs with discount factor 0 V (n, s) = Pr(a|n)R(s, a) + Pr(s |s, a) Pr(z|s, a) Pr(n |n, z)V (n, s ) (1) a z n The value V (n, b) of each node n is thus linear w. r. t the belief state; hence the value function of the controller is piecewise-linear and convex. The optimal value function V often has a large (if not infinite) number of vectors, each corresponding to a different node. The optimal value function V satisfies Bellman's equation: V (b) = max R(b, a) + Pr(z|b, a)V (ba) (2) z a z max s. t. V (n, s) + [Pr(a|n)R(s, a) + Pr(s |s, a) Pr(z|s, a) Pr(a, n |n, z)V (n, s )], s a s, z Pr(a|n) = 1; Pr(a, n |n, z) = Pr(a|n), a a n Pr(a|n) 0, a; Pr(a, n |n, z) 0, a, z Table 1: LP to uniformly improve the value function of a node. max o(s, n) s, n s, n s. t. V (n, s) + s, n [Pr(a|n)R(s, a) + Pr(s |s, a) Pr(z|s, a) Pr(a, n |n, z)V (n, s )], s a s, z Pr(a|n) = 1; Pr(a, n |n, z) = Pr(a|n), a a n Pr(a|n) 0, a; Pr(a, n |n, z) 0, a, z Table 2: LP to improve the value function of a node in a non-uniform way according to the steady state occupancy o(s, n). 3 Bounded Policy Iteration We briefly review the bounded policy iteration (BPI) algorithm (see [14] for details) and describe a simple extension to bias its search toward reachable belief states. BPI incre- mentally constructs an FSC by alternating policy improvement and policy evaluation. Un- like policy iteration [7], this is done by slowly increasing the number of nodes (and value vectors). The policy improvement step greedily improves each node n by optimizing its action and observation strategies by solving the linear program (LP) in Table 1. This LP uniformly maximizes the improvement in the value function by optimizing n's distribu- tions Pr(a, n |n, z). The policy evaluation step computes the value function of the current controller by solving Eq. 1. The algorithm monotonically improves the policy until con- vergence to a local optimum, at which point new nodes are introduced to escape the local optimum. BPI is guaranteed to converge to a policy that is optimal at the "tangent" belief states while slowly growing the size of the controller [14]. In practice, we often wish to find a policy suitable for a given initial belief state. Since only a small subset of belief space is often reachable, it is generally possible to construct much smaller policies tailored to the reachable region. We now describe a simple way to bias BPI's efforts toward the reachable region. Recall that the LP in Table 1 optimizes the parameters of a node to uniformly improve its value at all belief states. We propose a new LP (Table 2) that weighs the improvement by the (unnormalized) discounted occupancy distribution induced by the current policy. This accounts for belief states reachable for the node by aggregating them together. The (unnormalized) discounted occupancy distribution is given by: o(s, n ) = b0(s, n ) + o(s, n) Pr(a|n) Pr(z|a, s) Pr(n |n, z) s, n s, a, z, n The LP in Table 2 is obtained by introducing variables s, n for each s, replacing the ob- jective by o(s, n) s, n s, n and replacing in each constraint by the corresponding s, n. When using the modified LP, BPI naturally tries to improve the policy at the reachable be- lief states before the others. Since the modification ensures that the value function doesn't decrease at any belief state, focusing the efforts on reachable belief states won't decrease policy value at other belief states. Furthermore, though the policy is initially biased toward reachable states, BPI will eventually improve the policy for all belief states. T ~ ~ T T T f ~ b ~ b b' b' ~ ~ R R R R r r' Figure 1: Functional flow of a POMDP (dotted arrows) and a compressed POMDP (solid arrows). 4 Value-Directed Compression We briefly review the sufficient conditions for a lossless compression of POMDPs [13] and describe a simple new algorithm to obtain good lossy compressions. Belief states constitute a sufficient statistic summarizing all information available to the decision maker (i. e. , past actions and observations). However, as long as enough information is available to evaluate the value of each policy, one can still choose the best policy. Since belief states often contain information irrelevant to the estimation of future rewards, one can often compress belief states into some lower-dimensional representation. Let f be a compression function that maps each belief state b into some lower dimensional compressed belief state ~ b (see Figure 1). Here ~ b can be viewed as a bottleneck that filters the information contained in b before it is used to estimate future rewards. We desire a compression f such that ~ b corresponds to the smallest statistic sufficient for accurately predicting the current reward r as well as the next compressed belief state ~ b (since it captures all the information in b necessary to accurately predict subsequent rewards). Such a compression f exists if we can also find compressed transition dynamics ~ T a, z and a compressed reward function ~ R such that: R = ~ R f and f T a, z = ~ T a, z f a A, z Z (3) Given an f, ~ R and ~ T a, z satisfying Eq. 3, we can evaluate any policy using the compressed POMDP dynamics to obtain ~ V. Since V = ~ V f, the compressed POMDP is equivalent to the original. When restricting f to be linear (represented by matrix F ), we can rewrite Eq. 3 R = F ~ R and T a, zF = F ~ T a, z a A, z Z (4) That is, the column space of F spans R and is invariant w. r. t. each T a, z. Hence, the columns of the best linear lossless compression mapping F form a basis for the smallest invariant subspace (w. r. t. each T a, z) that spans R, i. e. , the Krylov subspace. We can find the columns of F by Krylov iteration: multiplying R by each T a, z until the newly generated vectors are linear combinations of previous ones. 1 The dimensionality of the compressed space is equal to the number of columns of F, which is necessarily smaller than or equal to the dimensionality of the original belief space. Once F is found, we can compute ~ R and each ~ T a, z by solving the system in Eq. 4. Since linear lossless compressions are not always possible, we can extend the technique of [13] to find good lossy compressions with early stopping of the Krylov iteration. We retain only the vectors that are "far" from being linear combinations of prior vectors. For instance, if v is a linear combination of v1, v2, .. ., vn, then there are coefficients c1, c2, .. ., cn s. t. the error ||v - c i i vi ||2 is zero. Given a threshold or some upper bound k on the desired number of columns in F, we run Krylov iteration, retaining only the vectors with an error greater than, or the k vectors with largest error. When F is computed by approximate 1For numerical stability, one must orthogonalize each vector before multiplying by T a, z. Krylov iteration, we cannot compute ~ R and ~ T a, z by solving the linear system in Eq. 4-- due to the lossy nature of the compression, the system is overconstrained. But we can find suitable ~ R and ~ T a, z by computing a least square approximation, solving: F R = F F ~ R and F T a, zF = F F ~ T a, z a A, z Z While compression is required when the dimensionality of belief space is too large, unfortu- nately, the columns of F have the same dimensionality. Factored POMDPs of exponential dimension can, however, admit practical Krylov iteration if carried out using a compact representation (e. g. , DTs or ADDs) to efficiently compute F, ~ R and each ~ T a, z. 5 Bounded Policy Iteration with Value-Directed Compression In principle, any POMDP algorithm can be used to solve the compressed POMDPs pro- duced by VDC. If the compression is lossless and the POMDP algorithm exact, the com- puted policy will be optimal for the original POMDP. In practice, POMDP algorithms are usually approximate and lossless compressions are not always possible, so care must be taken to ensure numerical stability and a policy of high quality for the original POMDP. We now discuss some of the integration issues that arise when combining VDC with BPI. Since V = F ~ V, maximizing the compressed value vector ~ V of some node n automatically maximizes the value V of n w. r. t. the original POMDP when F is nonnegative; hence it is essential that F be nonnegative. Otherwise, the optimal policy of the compressed POMDP may not be optimal for the original POMDP. Fortunately, when R is nonnegative then F is guaranteed to be nonnegative by the nature of Krylov iteration. If some rewards are negative, we can add a sufficiently large constant to R to make it nonnegative without changing the decision problem. Since most algorithms, including BPI, compute approximately optimal policies it is also critical to normalize the columns of F. Suppose F has two columns f1 and f2 with L1- lengths 1 and 100, respectively. Since V = F ~ V = ~ v1f1 + ~v2f2, changes in ~v2 have a much greater impact on V than changes in ~ v1. Such a difference in sensitivity may bias the search for a good policy to an undesirable region of the belief space, or may even cause the algorithm to return a policy that is far from optimal for the original POMDP despite the fact that it is -optimal for the compressed POMDP. We note that it is "safer" to evaluate policies iteratively by successive approximation rather than solving the system in Eq. 1. By definition, the transition matrices T a, z have eigen- values with magnitude 1. In contrast, lossy compressed transition matrices ~ T a, z are not guaranteed to have this property. Hence, solving the system in Eq. 1 may not correspond to policy evaluation. It is thus safer to evaluate policies by successive approximation for lossy compressions. Finally several algorithms including BPI compute witness belief states to verify the domi- nance of a value vector. Since the compressed belief space ~ B is different from the original belief space B, this must be approached with care. B is a simplex corresponding to the convex hull of the state points. In contrast, since each row vector of F is the compressed version of some state point, ~ B corresponds to the convex hull of the row vectors of F. When F is non-negative, it is often possible to ignore this difference. For instance, when verifying the dominance of a value vector, if there is a compressed witness ~ b, there is al- ways an uncompressed witness b, but not vice-versa. This means that we can properly identify all dominating value vectors, but we may erroneously classify a dominated vector as dominating. In practice, this doesn't impact the correctness of algorithms such as policy iteration, bounded policy iteration, incremental pruning, witness algorithm, etc. but it will slow them down since they won't be able to prune as many value vectors as possible. cycle16 cycle19 cycle22 105 120 100 130 115 95 125 110 90 Expected Rewards Expected Rewards 105 Expected Rewards 120 250 250 250 200 120 200 120 200 120 100 150 100 100 80 150 80 150 80 60 100 60 60 40 100 40 100 40 20 50 20 20 # of basis fns 50 50 # of nodes # of basis fns # of nodes # of basis fns # of nodes cycle25 3legs16 3legs19 120 135 150 115 130 145 110 125 105 120 140 100 115 Expected Rewards Expected Rewards Expected Rewards 135 95 110 250 250 250 200 120 200 120 200 120 100 150 100 100 80 150 80 150 80 60 100 60 60 40 100 40 100 40 20 50 20 20 # of basis fns 50 50 # of nodes # of basis fns # of nodes # of basis fns # of nodes 3legs22 3legs25 cycle25 150 12 145 160 10 8 140 155 6 135 150 4 130 145 Expected Rewards Expected Rewards 2 Time (1000 seconds) 125 140 250 250 250 200 120 200 120 200 120 100 150 100 100 80 150 80 150 80 60 100 60 60 40 100 40 100 40 20 50 20 20 # of basis fns 50 50 # of nodes # of basis fns # of nodes # of basis fns # of nodes Figure 2: Experimental results for cycle and 3legs network configurations of 16, 19, 22 and 25 machines. The bottom right graph shows the running time of BPI on compressed versions of a cycle network of 25 machines. 3legs cycle 16 19 22 25 16 19 22 25 VDCBPI 120. 9 137. 0 151. 0 164. 8 103. 9 121. 3 134. 3 151. 4 heuristic 100. 6 118. 3 138. 3 152. 3 102. 5 117. 9 130. 2 152. 3 doNothing 98. 4 112. 9 133. 5 147. 1 91. 6 105. 4 122. 0 140. 1 Table 3: Comparison of the best policies achieved by VDCBPI to the doNothing and heuristic policies. The above tips work well when VDC is integrated with BPI. We believe they are sufficient to ensure proper integration of VDC with other POMDP algorithms, though we haven't verified this empirically.

IJCAI Conference 2003 Conference Paper

A Bayesian Approach to Imitation in Reinforcement Learning

• Bob Price
• Craig Boutilier

In multiagent environments, forms of social learning such as teaching and imitation have been shown to aid the transfer of knowledge from experts to learners in reinforcement learning (RL). We recast the problem of imitation in a Bayesian framework. Our Bayesian imitation model allows a learner to smoothly pool prior knowledge, data obtained through interaction with the environment, and information inferred from observations of expert agent behaviors. Our model integrates well with recent Bayesian exploration techniques, and can be readily generalized to new settings.

UAI Conference 2003 Conference Paper

Active Collaborative Filtering

• Craig Boutilier
• Richard S. Zemel
• Benjamin M. Marlin

Collaborative filtering (CF) allows the preferences of multiple users to be pooled to make recommendations regarding unseen products. We consider in this paper the problem of online and interactive CF: given the current ratings associated with a user, what queries (new ratings) would most improve the quality of the recommendations made? We cast this terms of expected value of information (EVOI); but the online computational cost of computing optimal queries is prohibitive. We show how offline prototyping and computation of bounds on EVOI can be used to dramatically reduce the required online computation. The framework we develop is general, but we focus on derivations and empirical study in the specific case of the multiple-cause vector quantization model

NeurIPS Conference 2003 Conference Paper

Bounded Finite State Controllers

• Pascal Poupart
• Craig Boutilier

We describe a new approximation algorithm for solving partially observ- able MDPs. Our bounded policy iteration approach searches through the space of bounded-size, stochastic finite state controllers, combining sev- eral advantages of gradient ascent (efficiency, search through restricted controller space) and policy iteration (less vulnerability to local optima).

UAI Conference 2003 Conference Paper

Cooperative Negotiation in Autonomic Systems using Incremental Utility Elicitation

• Craig Boutilier
• Rajarshi Das
• Jeffrey O. Kephart
• Gerald Tesauro
• William E. Walsh

Decentralized resource allocation is a key problem for large-scale autonomic (or self-managing) computing systems. Motivated by a data center scenario, we explore efficient techniques for resolving resource conflicts via cooperative negotiation. Rather than computing in advance the functional dependence of each element's utility upon the amount of resource it receives, which could be prohibitively expensive, each element's utility is elicited incrementally. Such incremental utility elicitation strategies require the evaluation of only a small set of sampled utility function points, yet they find near-optimal allocations with respect to a minimax regret criterion. We describe preliminary computational experiments that illustrate the benefit of our approach.

AAMAS Conference 2003 Conference Paper

Coordination in Multiagent Reinforcement Learning: A Bayesian Approach

• Georgios Chalkiadakis
• Craig Boutilier

AIJ Journal 2003 Journal Article

Editorial

• Craig Boutilier
• Tom Dean
• Sven Koenig

IJCAI Conference 2003 Conference Paper

Incremental Utility Elicitation with the Minimax Regret Decision Criterion

• Tianhan Wang
• Craig Boutilier

Utility elicitation is a critical function of any automated decision aid, allowing decisions to be tailored to the preferences of a specific user. However, the size and complexity of utility functions often precludes full elicitation, requiring that decisions be made without full utility information. Adopting the minimax regret criterion for decision making with incomplete utility information, we describe and empirically compare several new procedures for incremental elicitation of utility functions that attempt to reduce minimax regret with as few questions as possible. Specifically, using the (continuous) space of standard gamble queries, we show that myopically optimal queries can be computed effectively (in polynomial time) for several different improvement criteria. One such criterion, in particular, empirically outperforms the others we examine considerably, and has provable improvement guarantees.

IJCAI Conference 2003 Conference Paper

On the Foundations of Expected Expected Utility

• Craig Boutilier

Intelligent agents often need to assess user utility functions in order to make decisions on their behalf, or predict their behavior. When uncertainty exists over the precise nature of this utility function, one can model this uncertainty using a distribution over utility functions. This view lies at the core of games with incomplete information and, more recently, several proposals for incremental preference elicitation. In such cases, decisions (or predicted behavior) are based on computing the expected expected utility (EEU) of decisions with respect to the distribution over utility functions. Unfortunately, decisions made under EEU are sensitive to the precise representation of the utility function. We examine the conditions under which EEU provides for sensible decisions by appeal to the foundational axioms of decision theory. We also discuss the impact these conditions have on the enterprise of preference elicitation more broadly.

IJCAI Conference 2003 Conference Paper

Towards Cooperative Negotiation for Decentralized Resource Allocation in Autonomic Computing Systems

• Craig Boutilier
• Rajarshi Das
• Jeffrey O. Kephart
• William E. Walsh

AAAI Conference 2002 Conference Paper

A POMDP Formulation of Preference Elicitation Problems

• Craig Boutilier

Preference elicitation is a key problem facing the deployment of intelligent systems that make or recommend decisions on the behalf of users. Since not all aspects of a utility function have the same impact on object-level decision quality, determining which information to extract from a user is itself a sequential decision problem, balancing the amount of elicitation effort and time with decision quality. We formulate this problem as a partially-observable Markov decision process (POMDP). Because of the continuous nature of the state and action spaces of this POMDP, standard techniques cannot be used to solve it. We describe methods that exploit the special structure of preference elicitation to deal with parameterizedbelief states overthe continuousstate space, and gradient techniques for optimizing parameterized actions. These methods can be used with a number of different belief state representations, including mixture models.

AAAI Conference 2002 Conference Paper

Solving Concisely Expressed Combinatorial Auction Problems

• Craig Boutilier

Combinatorial auctions provide a valuable mechanism for the allocation of goods in settings where buyer valuations exhibit complex structure with respect to substitutability and complementarity. Most algorithms are designed to work with explicit “flat” bids for concrete bundles of goods. However, logical bidding languages allow the expression of complex utility functions in a natural and concise way, and have recently attracted considerable attention. Despite the power of logical languages, no current winner determination algorithms exploit the specific structure of logically specified bids to solve problems more effectively. In this paper, we describe techniques to do just this. Specifically, we propose a direct integer program (IP) formulation of the winner determination problem for bids in the LGB logical language. This formulation is linear in the size of the problemand can be solved effectively using standard optimization packages. We compare this formulation and its solution time to those of the correspondingset of flat bids, demonstratingthe immense utility of exploiting the structure of logically expressed bids. We also consider an extension of LGB and show that these can also be solved using linear constraints.

NeurIPS Conference 2002 Conference Paper

Value-Directed Compression of POMDPs

• Pascal Poupart
• Craig Boutilier

We examine the problem of generating state-space compressions of POMDPs in a way that minimally impacts decision quality. We analyze the impact of compres- sions on decision quality, observing that compressions that allow accurate policy evaluation (prediction of expected future reward) will not affect decision qual- ity. We derive a set of sufficient conditions that ensure accurate prediction in this respect, illustrate interesting mathematical properties these confer on lossless lin- ear compressions, and use these to derive an iterative procedure for finding good linear lossy compressions. We also elaborate on how structured representations of a POMDP can be used to find such compressions.

UAI Conference 2001 Conference Paper

UCP-Networks: A Directed Graphical Representation of Conditional Utilities

• Craig Boutilier
• Fahiem Bacchus
• Ronen I. Brafman

We propose a new directed graphical representation of utility functions, called UCP-networks, that combines aspects of two existing graphical models: generalized additive models and CP-networks. The network decomposes a utility function into a number of additive factors, with the directionality of the arcs reflecting conditional dependence of preference statements---in the underlying (qualitative) preference ordering---under a {em ceteris paribus} (all else being equal) interpretation. This representation is arguably natural in many settings. Furthermore, the strong CP-semantics ensures that computation of optimization and dominance queries is very efficient. We also demonstrate the value of this representation in decision making. Finally, we describe an interactive elicitation procedure that takes advantage of the linear nature of the constraints on ``tradeoff weights'' imposed by a UCP-network. This procedure allows the network to be refined until the regret of the decision with minimax regret (with respect to the incompletely specified utility function) falls below a specified threshold (e.g., the cost of further questioning.

UAI Conference 2001 Conference Paper

Value-Directed Sampling Methods for POMDPs

• Pascal Poupart
• Luis E. Ortiz
• Craig Boutilier

We consider the problem of approximate belief-state monitoring using particle filtering for the purposes of implementing a policy for a partially-observable Markov decision process (POMDP). While particle filtering has become a widely-used tool in AI for monitoring dynamical systems, rather scant attention has been paid to their use in the context of decision making. Assuming the existence of a value function, we derive error bounds on decision quality associated with filtering using importance sampling. We also describe an adaptive procedure that can be used to dynamically determine the number of samples required to meet specific error bounds. Empirical evidence is offered supporting this technique as a profitable means of directing sampling effort where it is needed to distinguish policies.

UAI Conference 2001 Conference Paper

Vector-space Analysis of Belief-state Approximation for POMDPs

• Pascal Poupart
• Craig Boutilier

We propose a new approach to value-directed belief state approximation for POMDPs. The value-directed model allows one to choose approximation methods for belief state monitoring that have a small impact on decision quality. Using a vector space analysis of the problem, we devise two new search procedures for selecting an approximation scheme that have much better computational properties than existing methods. Though these provide looser error bounds, we show empirically that they have a similar impact on decision quality in practice, and run up to two orders of magnitude more quickly.

UAI Conference 2000 Conference Paper

Approximately Optimal Monitoring of Plan Preconditions

• Craig Boutilier

Monitoring plan preconditions can allow for replanning when a precondition fails, generally far in advance of the point in the plan where the precondition is relevant. However, monitoring is generally costly, and some precondition failures have a very small impact on plan quality. We formulate a model for optimal precondition monitoring, using partially-observable Markov decisions processes, and describe methods for solving this model efficitively, though approximately. Specifically, we show that the single-precondition monitoring problem is generally tractable, and the multiple-precondition monitoring policies can be efficitively approximated using single-precondition soultions.

NeurIPS Conference 2000 Conference Paper

APRICODD: Approximate Policy Construction Using Decision Diagrams

• Robert St-Aubin
• Jesse Hoey
• Craig Boutilier

We propose a method of approximate dynamic programming for Markov decision processes (MDPs) using algebraic decision diagrams (ADDs). We produce near-optimal value functions and policies with much lower time and space requirements than exact dynamic programming. Our method reduces the sizes of the intermediate value functions generated during value iteration by replacing the values at the terminals of the ADD with ranges of values. Our method is demonstrated on a class of large MDPs (with up to 34 billion states), and we compare the results with the optimal value functions.

AAAI Conference 2000 Conference Paper

Decision-Theoretic, High-Level Agent Programming in the Situation Calculus

• Craig Boutilier
• and Mikhail Soutchanski

We propose a frameworkfor robot programming which allows the seamless integration of explicit agent programming with decision-theoretic planning. Specifically, the DTGolog model allows one to partially specify a control program in a highlevel, logical language, and provides an interpreter that, given a logical axiomatization of a domain, will determine the optimal completion of that program (viewed as a Markov decision process). We demonstrate the utility of this model with results obtained in an office delivery robotics domain.

AIJ Journal 2000 Journal Article

Stochastic dynamic programming with factored representations

• Craig Boutilier
• Richard Dearden
• Moisés Goldszmidt

Markov decision processes (MDPs) have proven to be popular models for decision-theoretic planning, but standard dynamic programming algorithms for solving MDPs rely on explicit, state-based specifications and computations. To alleviate the combinatorial problems associated with such methods, we propose new representational and computational techniques for MDPs that exploit certain types of problem structure. We use dynamic Bayesian networks (with decision trees representing the local families of conditional probability distributions) to represent stochastic actions in an MDP, together with a decision-tree representation of rewards. Based on this representation, we develop versions of standard dynamic programming algorithms that directly manipulate decision-tree representations of policies and value functions. This generally obviates the need for state-by-state computation, aggregating states at the leaves of these trees and requiring computations only for each aggregate state. The key to these algorithms is a decision-theoretic generalization of classic regression analysis, in which we determine the features relevant to predicting expected value. We demonstrate the method empirically on several planning problems, showing significant savings for certain types of domains. We also identify certain classes of problems for which this technique fails to perform well and suggest extensions and related ideas that may prove useful in such circumstances. We also briefly describe an approximation scheme based on this approach.

UAI Conference 2000 Conference Paper

Value-Directed Belief State Approximation for POMDPs

• Pascal Poupart
• Craig Boutilier

We consider the problem belief-state monitoring for the purposes of implementing a policy for a partially-observable Markov decision process (POMDP), specifically how one might approximate the belief state. Other schemes for belief-state approximation (e.g., based on minimixing a measures such as KL-diveregence between the true and estimated state) are not necessarily appropriate for POMDPs. Instead we propose a framework for analyzing value-directed approximation schemes, where approximation quality is determined by the expected error in utility rather than by the error in the belief state itself. We propose heuristic methods for finding good projection schemes for belief state estimation - exhibiting anytime characteristics - given a POMDP value fucntion. We also describe several algorithms for constructing bounds on the error in decision quality (expected utility) associated with acting in accordance with a given belief state approximation.

UAI Conference 1999 Conference Paper

Continuous Value Function Approximation for Sequential Bidding Policies

• Craig Boutilier
• Moisés Goldszmidt
• Bikash Sabata

Market-based mechanisms such as auctions are being studied as an appropriate means for resource allocation in distributed and mulitagent decision problems. When agents value resources in combination rather than in isolation, they must often deliberate about appropriate bidding strategies for a sequence of auctions offering resources of interest. We briefly describe a discrete dynamic programming model for constructing appropriate bidding policies for resources exhibiting both complementarities and substitutability. We then introduce a continuous approximation of this model, assuming that money (or the numeraire good) is infinitely divisible. Though this has the potential to reduce the computational cost of computing policies, value functions in the transformed problem do not have a convenient closed form representation. We develop {em grid-based} approximation for such value functions, representing value functions using piecewise linear approximations. We show that these methods can offer significant computational savings with relatively small cost in solution quality.

ICML Conference 1999 Conference Paper

Implicit Imitation in Multiagent Reinforcement Learning

• Bob Price
• Craig Boutilier

UAI Conference 1999 Conference Paper

Reasoning With Conditional Ceteris Paribus Preference Statements

• Craig Boutilier
• Ronen I. Brafman
• Holger H. Hoos
• David Poole 0001

IJCAI Conference 1999 Conference Paper

Sequential Auctions for the Allocation of Resources with Complementarities

• Craig Boutilier
• Moists Goldszmidt
• Bikash Sahata

Market-based mechanisms such as auctions are being studied as an appropriate means for resource allocation in distributed and inultiagcnl decision problems. When agents value resources in combination rather than in isolation, one generally relies on combinatorial auctions where agents bid tor resource bundles. or simultaneous auctions for all resources. We develop a different model, where agents bid for required resources sequentially. This model has the advantage that it can be applied in settings where combinatorial and simultaneous models are infeasible (e. g. . when resources are made available at different points in time by different parties), as well as certain benefits in settings where combinatorial models are applicable. We develop a dynamic programming model tor agents to compute bidding policies based on estimated distributions over prices. We also describe how these distributions are updated to provide a learning model for bidding behavior.

IJCAI Conference 1999 Conference Paper

Sequential Optimality and Coordination in Multiagent Systems

• Craig Boutilier

Coordination of agent activities is a key problem in multiagent systems. Set in a larger decision theoretic context, the existence of coordination problems leads to difficulty in evaluating the utility of a situation. This in turn makes defining optimal policies for sequential decision processes problematic. We propose a method for solving sequential multiagent decision problems by allowing agents to reason explicitly about specific coordination mechanisms. We define an extension of value iteration in which the system's state space is augmented with the state of the coordination mechanism adopted, allowing agents to reason about the short and long term prospects for coordination, the long term consequences of (mis)coordination, and make decisions to engage or avoid coordination problems based on expected value. We also illustrate the benefits of mechanism generalization.

UAI Conference 1999 Conference Paper

SPUDD: Stochastic Planning using Decision Diagrams

• Jesse Hoey
• Robert St-Aubin
• Alan J. Hu
• Craig Boutilier

Markov decisions processes (MDPs) are becoming increasing popular as models of decision theoretic planning. While traditional dynamic programming methods perform well for problems with small state spaces, structured methods are needed for large problems. We propose and examine a value iteration algorithm for MDPs that uses algebraic decision diagrams(ADDs) to represent value functions and policies. An MDP is represented using Bayesian networks and ADDs and dynamic programming is applied directly to these ADDs. We demonstrate our method on large MDPs (up to 63 million states) and show that significant gains can be had when compared to tree-structured representations (with up to a thirty-fold reduction in the number of nodes required to represent optimal value functions).

AIJ Journal 1998 Journal Article

A unified model of qualitative belief change: a dynamical systems perspective

• Craig Boutilier

Belief revision and belief update have been proposed as two types of belief change serving different purposes, revision intended to capture changes in belief state reflecting new information about a static world, and update intended to capture changes of belief in response to a changing world. We argue that routine belief change involves elements of both and present a model of generalized update that allows updates in response to external changes to inform an agent about its prior beliefs. This model of update combines aspects of revision and update, providing a more realistic characterization of belief change. We show that, under certain assumptions, the original update postulates are satisfied. We also demonstrate that plain revision and plain update are special cases of our model. We also draw parallels to models of stochastic dynamical systems, and use this to develop a model that deals with iterated update and noisy observations in qualitative settings that is analogous to Bayesian updating in a quantitative setting.

AAAI Conference 1998 Conference Paper

Belief Revision with Unreliable Observations

• Craig Boutilier

Research in belief revision has been dominated by work that lies firmly within the classic AGM paradigm, characterized by a well-known set of postulates governing the behavior of “rational” revision functions. A postulate that is rarely criticized is the success postulate: the result of revising by an observed proposition ' results in belief in '. This postulate, however, is often undesirable in settings where an agent’s observations may be imprecise or noisy. We propose a semantics that captures a new ontology for studying revision functions, which can handle noisy observations in a natural way while retaining the classical AGM model as a special case. We present a characterization theorem for our semantics, and describe a numberof natural specialcasesthat allow easeof specification and reasoning with revision functions. In particular, by making the Markov assumption, we can easily specify and reason about revision.

UAI Conference 1998 Conference Paper

Hierarchical Solution of Markov Decision Processes using Macro-actions

• Milos Hauskrecht
• Nicolas Meuleau
• Leslie Pack Kaelbling
• Thomas L. Dean
• Craig Boutilier

We investigate the use of temporally abstract actions, or macro-actions, in the solution of Markov decision processes. Unlike current models that combine both primitive actions and macro-actions and leave the state space unchanged, we propose a hierarchical model (using an abstract MDP) that works with macro-actions only, and that significantly reduces the size of the state space. This is achieved by treating macroactions as local policies that act in certain regions of state space, and by restricting states in the abstract MDP to those at the boundaries of regions. The abstract MDP approximates the original and can be solved more efficiently. We discuss several ways in which macro-actions can be generated to ensure good solution quality. Finally, we consider ways in which macro-actions can be reused to solve multiple, related MDPs; and we show that this can justify the computational overhead of macro-action generation.

UAI Conference 1998 Conference Paper

Structured Reachability Analysis for Markov Decision Processes

• Craig Boutilier
• Ronen I. Brafman
• Christopher W. Geib

AIJ Journal 1997 Journal Article

Abstraction and approximate decision-theoretic planning

• Richard Dearden
• Craig Boutilier

Markov decision processes (MDPs) have recently been proposed as useful conceptual models for understanding decision-theoretic planning. However, the utility of the associated computational methods remains open to question: most algorithms for computing optimal policies require explicit enumeration of the state space of the planning problem. We propose an abstraction technique for MDPs that allows approximately optimal solutions to be computed quickly. Abstractions are generated automatically, using an intensional representation of the planning problem (probabilistic strips rules) to determine the most relevant problem features and optimally solving a reduced problem based on these relevant features. The key features of our method are: abstractions can be generated quickly; the abstract solution can be applied directly to the original problem; and the loss of optimality can be bounded. We also describe methods by which the abstract solution can be viewed as a set of default reactions that can be improved incrementally, and used as a heuristic for search-based planning or other MDP methods. Finally, we discuss certain difficulties that point toward other forms of aggregation for MDPs.

UAI Conference 1997 Conference Paper

Correlated Action Effects in Decision Theoretic Regression

• Craig Boutilier

Much recent research in decision theoretic planning has adopted Markov decision processes (MDPs) as the model of choice, and has attempted to make their solution more tractable by exploiting problem structure. One particular algorithm, structured policy construction achieves this by means of a decision theoretic analog of goal regression using action descriptions based on Bayesian networks with tree-structured conditional probability tables. The algorithm as presented is not able to deal with actions with correlated effects. We describe a new decision theoretic regression operator that corrects this weakness. While conceptually straightforward, this extension requires a somewhat more complicated technical approach.

AIJ Journal 1997 Journal Article

Economic principles of multi-agent systems

• Craig Boutilier
• Yoav Shoham
• Michael P. Wellman

AAAI Conference 1997 Conference Paper

Planning with Concurrent Interacting Actions

• Craig Boutilier

In order to generate plans for agents with multiple actuators or agent teams, we must be able to represent and plan using concurrent actions with interacting effects. Historically, this has been considered a challenging task that could require a temporal planner. We show that, with simple modifications, the STRIPS action representation language can be used to represent concurrent interacting actions. Moreover, current algorithms for partial-order planning require only small modifications in order to handle this language and produce coordinated multiagent plans. These results open the way to partial order planners for cooperative multiagent systems.

IJCAI Conference 1997 Conference Paper

Prioritized Goal Decomposition of Markov Decision Processes: Toward a Synthesis of Classical and Decision Theoretic Planning

• Craig Boutilier
• Rotten I. Brafman
• Christopher Ck'ib

We describe an approach to goal decomposition for a certain class of Markov decision processes (MDPs). An abstraction mechanism is used to generate abstract MDPs associated with different objectives, and several methods for merging the policies for these different objectives are considered. In one technique, causal (least-commitment) structures are generated for abstract policies and plan merging techniques, exploiting the relaxation of policy commitments reflected in this structure, are used to piece the results into a single policy. Abstract value functions provide guidance if plan repair is needed. This work makes some first steps toward the synthesis of classical and decision theoretic planning methods.

UAI Conference 1997 Conference Paper

Structured Arc Reversal and Simulation of Dynamic Probabilistic Networks

• Adrian Y. W. Cheuk
• Craig Boutilier

We present an algorithm for arc reversal in Bayesian networks with tree-structured conditional probability tables, and consider some of its advantages, especially for the simulation of dynamic probabilistic networks. In particular, the method allows one to produce CPTs for nodes involved in the reversal that exploit regularities in the conditional distributions. We argue that this approach alleviates some of the overhead associated with arc reversal, plays an important role in evidence integration and can be used to restrict sampling of variables in DPNs. We also provide an algorithm that detects the dynamic irrelevance of state variables in forward simulation. This algorithm exploits the structured CPTs in a reversed network to determine, in a time-independent fashion, the conditions under which a variable does or does not need to be sampled.

AIJ Journal 1996 Journal Article

Abduction to plausible causes: an event-based model of belief update

• Craig Boutilier

The Katsuno and Mendelzon (KM) theory of belief update has been proposed as a reasonable model for revising beliefs about a changing world. However, the semantics of update relies on information which is not readily available. We describe an alternative semantical view of update in which observations are incorporated into a belief set by: (a) explaining the observation in terms of a set of plausible events that might have caused that observation; and (b) predicting further consequences of those explanations. We also allow the possibility of conditional explanations. We show that this picture naturally induces an update operator conforming to the KM postulates under certain assumptions. However, we argue that these assumptions are not always reasonable, and they restrict our ability to integrate update with other forms of revision when reasoning about action.

ICML Conference 1996 Conference Paper

Approximate Value Trees in Structured Dynamic Programming

• Craig Boutilier
• Richard Dearden

AAAI Conference 1996 Conference Paper

Computing Optimal Policies for Partially Observable Decision Processes Using Compact Representations

• Craig Boutilier

Partially-observable Markov decision processes provide a general model for decision theoretic planning problems, allowing trade-offs between various courses of actions to be determined under conditions of uncertainty, and incorporating partial observations ma& by an agent. Dynamic programming algorithms based on the belief state of an agent can be used to construct optimal policies without explicit consideration of past history, but at high computational cost. In this paper, we discuss how structured representations of system dynamics can be incorporated in classic POMDP solution algorithms. We use Bayesian networks with structured conditional probability matrices to represent POMDPs, and use this model to structure the belief space for POMDP algorithms, allowing irrelevant distinctions to be ignored. Apart from speeding up optimal policy construction, we suggest that such representations can be exploited in the development of useful approximation methods.

UAI Conference 1996 Conference Paper

Context-Specific Independence in Bayesian Networks

• Craig Boutilier
• Nir Friedman
• Moisés Goldszmidt
• Daphne Koller

Bayesian networks provide a language for qualitatively representing the conditional independence properties of a distribution. This allows a natural and compact representation of the distribution, eases knowledge acquisition, and supports effective inference algorithms. It is well-known, however, that there are certain independencies that we cannot capture qualitatively within the Bayesian network structure: independencies that hold only in certain contexts, i.e., given a specific assignment of values to certain variables. In this paper, we propose a formal notion of context-specific independence (CSI), based on regularities in the conditional probability tables (CPTs) at a node. We present a technique, analogous to (and based on) d-separation, for determining when such independence holds in a given network. We then focus on a particular qualitative representation scheme---tree-structured CPTs---for capturing CSI. We suggest ways in which this representation can be used to support effective inference algorithms. In particular, we present a structural decomposition of the resulting network which can improve the performance of clustering algorithms, and an alternative algorithm based on cutset conditioning.

UAI Conference 1996 Conference Paper

Learning Conventions in Multiagent Stochastic Domains using Likelihood Estimates

• Craig Boutilier

Fully cooperative multiagent systems---those in which agents share a joint utility model--is of special interest in AI. A key problem is that of ensuring that the actions of individual agents are coordinated, especially in settings where the agents are autonomous decision makers. We investigate approaches to learning coordinated strategies in stochastic domains where an agent's actions are not directly observable by others. Much recent work in game theory has adopted a Bayesian learning perspective to the more general problem of equilibrium selection, but tends to assume that actions can be observed. We discuss the special problems that arise when actions are not observable, including effects on rates of convergence, and the effect of action failure probabilities and asymmetries. We also use likelihood estimates as a means of generalizing fictitious play learning models in our setting. Finally, we propose the use of maximum likelihood as a means of removing strategies from consideration, with the aim of convergence to a conventional equilibrium, at which point learning and deliberation can cease.

TARK Conference 1996 Conference Paper

Planning, Learning and Coordination in Multiagent Decision Processes

• Craig Boutilier

There has been a growing interest in AI in the design of multiagent systems, especially in multiagent cooperative planning. In this paper, we investigate the extent to which methods from single-agentplanning and learning can be applied in multiagent settings. We survey a number of different techniques from decision-theoreticplanning and reinforcement learning and describe a number of interesting issues that arise with regard to coordinating the policies of individual agents. To this end, we describe multiagent Markov decision processes as a general model in which to frame this discussion. These are special n-person cooperative games in which agents share the same utility function. We discuss coordination mechanisms based on imposed conventions (or social laws) as well as learning methods for coordination. Our focus is on the decomposition of sequential decision processes so that coordination can be learned (or imposed) locally, at the level of individual states. We also discuss the use of structured problem representations and their role in the generalization of learned conventions and in approximation.

AIJ Journal 1995 Journal Article

Abduction as belief revision

• Craig Boutilier
• Veronica Beche

We propose a model of abduction based on the revision of the epistemic state of an agent. Explanations must be sufficient to induce belief in the sentence to be explained (for instance, some observation), or ensure its consistency with other beliefs, in a manner that adequately accounts for factual and hypothetical sentences. Our model will generate explanations that nonmonotonically predict an observation, thus generalizing most current accounts, which require some deductive relationship between explanation and observation. It also provides a natural preference ordering on explanations, defined in terms of normality or plausibility. To illustrate the generality of our approach, we reconstruct two of the key paradigms for model-based diagnosis, abductive and consistency-based diagnosis, within our framework. This reconstruction provides an alternative semantics for both and extends these systems to accommodate our predictive explanations and semantic preferences on explanations. It also illustrates how more general information can be incorporated in a principled manner.

IJCAI Conference 1995 Conference Paper

Process-Oriented Planning and Average-Reward Opumalirv

• Craig Boutilier
• Martin L Puterman

AIJ Journal 1994 Journal Article

Conditional logics of normality: A modal approach

• Craig Boutilier

Several conditional theories of default reasoning have recently been proposed for the representation of statements about normal states of affairs or prototypical properties. The natural semantics of these systems and their ability to reason about default rules make these approaches quite appealing. We present a family of modal logics in which we define a conditional connective for statements of normality and examine its properties. We also demonstrate that two of the most important conditional approaches are equivalent to fragments of our conditional logics of normality (and to standard modal logics). The approach we take is general enough to allow the expression of a number of different forms of defeasible reasoning, and can be used to illustrate the relationship between these types of reasoning (e. g. , belief revision, subjunctive and autoepistemic reasoning) and our default logics. This relationship is explored in a companion paper.

UAI Conference 1994 Conference Paper

Integrating Planning and Execution in Stochastic Domains

• Richard Dearden
• Craig Boutilier

We investigate planning in time-critical domains represented as Markov Decision Processes, showing that search based techniques can be a very powerful method for finding close to optimal plans. To reduce the computational cost of planning in these domains, we execute actions as we construct the plan, and sacrifice optimality by searching to a fixed depth and using a heuristic function to estimate the value of states. Although this paper concentrates on the search algorithm, we also discuss ways of constructing heuristic functions suitable for this approach. Our results show that by interleaving search and execution, close to optimal policies can be found without the computational requirements of other approaches.

AIJ Journal 1994 Journal Article

Unifying default reasoning and belief revision in a modal framework

• Craig Boutilier

We present a logic for reasoning about belief revision in which the process of revising a knowledge base by some sentence is represented with a conditional connective. The conditional is not primitive however; it is defined in terms of two unary modal operators. We show that our notion of revision is equivalent to that determined by the classic AGM postulates. Furthermore, unlike current models of revision, our approach does not require the Limit Assumption. We also present a model for subjunctive query answering that allows the expression of subjunctive or factual premises, integrity constraints, and notions of entrenchment and plausibility. The modal framework we adopt is sufficiently general to allow the expression of other forms of defeasible reasoning, and facilitates the demonstration of some interesting connections between revision, default reasoning and autoepistemic logic. In particular, we show that the normative conditional for default reasoning (developed in a companion paper) and our subjunctive conditional are identical. Default reasoning can thus be viewed as the revision of a theory of expectations in manner that naturally relates priorities of default rules to the entrenchment of expectations.

AAAI Conference 1994 Conference Paper

Using Abstractions for Decision-Theoretic Planning with Time Constraints

• Craig Boutilier

Recently Markov decision processes and optimal control policies have been applied to the problem of decision-theoretic planning. However, the classical methods for generating optimal policies are highly intractable, requiring explicit enumeration of large state spaces. We explore a method for generating abstractionsthat allow approximately optimal policies to be constructed; computational gains are achieved through reduction of the state space. Abstractions are generated by identifying propositions that are “relevant” either through their direct impact on utility, or their influence on actions. This information is gleaned from the representation of utilitiesand actions. We prove boundson the loss in value due to abstraction and describe some preliminary experimentalresults.

AAAI Conference 1993 Conference Paper

Abduction As Belief Revision: A Model of Preferred Explanations

• Craig Boutilier

AAAI Conference 1993 Conference Paper

Revision by Conditional Beliefs

• Craig Boutilier

IJCAI Conference 1993 Conference Paper

Revision Sequences and Nested Conditionals

• Craig Boutilier

The truth conditions for conditional sentences have been well-studied, but few compelling attempts have been made to define means of evaluating iterated or nested conditionals. In particular, most approaches impose very few constraints on the set of conditionals an agent can hold after revision of its belief set. In this paper we describe the method of natural revision that ensures the preservation of conditional beliefs after revision by an objective belief. Our model, based on a simple modal logic for beliefs and conditionals, extends the AGM theory of belief revision to account for sentiences of objective revisions of a belief set. This model of revision ensures that an agent makes as few changes as possible to the conditional component of its belief set. Adopting the Ramsey test, natural revision provides truth conditions for arbitrary right-nested conditionals. We show that the problem of determining acceptance of any such nested conditional can be reduced to acceptance tests for unnested conditionals, indicating that iterated revision can be simulated by virtual updates. We also briefly describe certain reductions to (sometimes tractable) propositional inference, and other informational properties.

UAI Conference 1993 Conference Paper

The Probability of a Possibility: Adding Uncertainty to Default Rules

• Craig Boutilier

We present a semantics for adding uncertainty to conditional logics for default reasoning and belief revision. We are able to treat conditional sentences as statements of conditional probability, and express rules for revision such as "If A were believed, then B would be believed to degree p." This method of revision extends conditionalization by allowing meaningful revision by sentences whose probability is zero. This is achieved through the use of counterfactual probabilities. Thus, our system accounts for the best properties of qualitative methods of update (in particular, the AGM theory of revision) and probabilistic methods. We also show how our system can be viewed as a unification of probability theory and possibility theory, highlighting their orthogonality and providing a means for expressing the probability of a possibility. We also demonstrate the connection to Lewis's method of imaging.

AAAI Conference 1992 Conference Paper

A Logic for Revision and Subjunctive Queries

• Craig Boutilier

We present a logic for belief revision in which revision of a theory by a sentence is represented using a conditional connective. The conditional is not primitive, but rather defined using two unary modal operators. Our approach captures and extends the classic AGM model without relying on the Limit Assumption. Reasoning about counterfactual or hypothetical situations is also crucial for AI. Existing logics for such subjunctive queries are lacking in several respects, however, primarily in failing to make explicit the epistemic nature of such queries. We present a logical model for subjunctives based on our logic of revision that appeals explicitly to the Ramsey test. We discuss a framework for answering subjunctive queries, and show how integrity constraints on the revision process can be expressed.

UAI Conference 1992 Conference Paper

Modal Logics for Qualitative Possibility and Beliefs

• Craig Boutilier

Possibilistic logic has been proposed as a numerical formalism for reasoning with uncertainty. There has been interest in developing qualitative accounts of possibility, as well as an explanation of the relationship between possibility and modal logics. We present two modal logics that can be used to represent and reason with qualitative statements of possibility and necessity. Within this modal framework, we are able to identify interesting relationships between possibilistic logic, beliefs and conditionals. In particular, the most natural conditional definable via possibilistic means for default reasoning is identical to Pearl's conditional for e-semantics.

AAAI Conference 1990 Conference Paper

Conditional Logics of Normality as Modal Systems

• Craig Boutilier

Recently, conditional logics have been developed for application to problems in default reasoning. We present a uniform framework for the development and investigation of conditional logics to represent and reason with “ normality”, and demonstrate these logics to be equivalent to extensions of the modal system S4. We also show that two conditional logics, recently proposed to reason with default knowledge, are equivalent to fragments of two logics developed in this framework.

IJCAI Conference 1989 Conference Paper

A Semantical Approach to Stable Inheritance Reasoning

• Craig Boutilier