Person:

Pfeffer, Avi

We show that genetic algorithms (GA) find optimized dynamic support vector machines (DSVMs) more efficiently than the grid search (GS) optimization approach. In addition, we show that GA-DSVMs find extremely low-error solutions for a number of oft-cited benchmarks. Unlike standard support vector machines, DSVMs account for the fact that data further back in a time series are generally less predictive than more-recent data. In order to tune the discounting factors, DSVMs require two new free parameters for a total of five. Because of the five free parameters, traditional GS optimization becomes intractable for even modest grid resolutions. GA optimization finds better results while using fewer computational resources.

This paper describes IBAL, a high level representation language for probabilistic AI. IBAL integrates several aspects of probability-based rational behavior, including probabilistic reasoning, Bayesian parameter estimation and decision theoretic utility maximization. IBAL is based on the functional programming paradigm, and is an ideal rapid prototyping language for probabilistic modeling. The paper presents the IBAL language, and presents a number of examples in the language. It then discusses the semantics of IBAL, presenting the semantics in two different ways. Finally, the inference algorithm of IBAL is presented. Seven desiderata are listed for inference, and it is shown how the algorithm fulfills each of them.

Computer agents participate in many collaborative and competitive multi-agent domains in which humans make decisions. For computer agents to interact successfully with people in such environments, an understanding of human reasoning is beneficial. In this paper, we investigate the question of how people reason strategically about others under uncertainty and the implications of this question for the design of computer agents. Using a situated partial-information negotiation game, we conduct human-subjects trials to obtain data on human play. We then construct a hierarchy of models that explores questions about human reasoning: Do people explicitly reason about other players in the game? If so, do people also consider the possible states of other players for which only partial information is known? Is it worth trying to capture such reasoning with computer models and subsequently utilize them in computer agents? We further address these questions by constructing computer agents that use our models; we deploy our agents in further human-subjects trials for evaluation. Our results indicate that people do reason about other players in our game and that the computer agents that best model human play obtain superior scores.

In addressing the challenge of exponential scaling with the number of agents we adopt a cluster-based representation to approximately solve asymmetric games of very many players. A cluster groups together agents with a similar “strategic view ” of the game. We learn the clustered approximation from data consisting of strategy profiles and payoffs, which may be obtained from observations of play or access to a simulator. Using our clustering we construct a reduced “twins” game in which each cluster is associated with two players of the reduced game. This allows our representation to be individuallyresponsive because we align the interests of every individual agent with the strategy of its cluster. Our approach provides agents with higher payoffs and lower regret on average than model-free methods as well as previous cluster-based methods, and requires only few observations for learning to be successful. The “twins ” approach is shown to be an important component of providing these low regret approximations.

We provide a formal scripting language to capture the semantics of market mechanisms. The language is based on a set of well-defined principles, and is designed to capture an agent’s rights, as derived from property, and an agent’s obligations, as derived from restrictions placed on its actions, either voluntarily or as a consequence of other actions. Rights and obligations are viewed as first-class goods, from which we define fundamental axioms about well-functioning market-oriented worlds. Coupled with the scripting language is a run-time system that is able to monitor and enforce rights and obligations. Our treatment extends to represent a variety of market mechanisms, ranging from simple two-agent single-good exchanges to complicated combinatorial auctions.

Many environments in which people and computer agents interact involve deploying resources to accomplish tasks and satisfy goals. This paper investigates the way that the contextual setting in which decisions are made affects the behavior of people and the performance of computer agents that interact with people in such environments. It presents experiments that measured negotiation behavior in two types of contextual settings. One provided a task context that made explicit the relationship between goals, tasks and resources, The other provided a completely abstract context in which the payoffs for all decision choices were listed. Results show that people are more helpful, less selfish, and less competitive when making decisions in task contexts than when making them in completely abstract contexts. Further, their overall performance was better in task contexts. A predictive computational model that was trained on data obtained in task contexts outperformed a model that was trained under abstract contexts. These results indicate that modeling the way people make decisions in context is essential for the design of computer agents that will interact with people.

In strategic multi-agent decision making, it is often the case that a strategic reasoner must hold beliefs about other agents and use these beliefs to inform its decision making. The behavior thus produced by the reasoner reflects an interaction between the reasoner’s beliefs about other agents and the reasoner’s own preferences. In this paper, we are interested to investigate human reasoning, particularly the interaction between a human’s utility function and the beliefs the human holds to reason about other agents. A significant challenge faced by model designers, therefore, is how to model such a reasoner’s behavior so that the reasoner’s preferences and beliefs can each be identified and distinguished from each other. In this paper, we introduce a model of strategic human reasoning that allows us to distinguish between the human’s utility function and the human’s beliefs about another agent’s utility function as well as the human’s beliefs about how that agent might interact with yet other agents. We show that our model is uniquely identifiable. We then illustrate the performance of our model in a multi-agent negotiation game.

In descriptive decision and game theory, one specifies a model of a situation faced by agents and uses the model to predict or explain their behavior. We present Influence Diagram Networks, a language for descriptive decision and game theory that is based on graphical models. Our language relaxes the assumption traditionally used in economics that beliefs of agents are consistent, i.e. conditioned on a common prior distribution. In the single-agent case one can model situations in which the agent has an incorrect model of the way the world works, or in which a modeler has uncertainty about the agent's model. In the multi-agent case, one can model agents' uncertain beliefs about other agents' decision-making models. We present an algorithm that computes the actions of agents under the assumption that they are rational with respect to their own model, but not necessarily with respect to the real world. Applications of our language include determining the cost to an agent of using an incorrect model, opponent modeling in games, and modeling bounded rationality.

This work presents a new approach to monitoring large dynamic systems. The approach is based on factored particles, which adapts particle filtering by factoring the system into weakly interacting subsystems and maintaining particles over the factors, thus allowing much larger systems to be tracked. Our approach, hybrid factored sampling, works with systems that involve both discrete and continuous variables, including systems where discrete variables depend on continuous parents. The framework lends itself to asynchronous inference—each factor can be reasoned about independently, and the factors joined only when there exists sufficient correlation between them. This allows us to reason about each factor at its appropriate time granularity. In addition, hybrid factored sampling exploits the factorization to provide tractable look-ahead prediction, allowing sampling from the posterior probability given new observations, and considerably improving performance. Empirical results show that hybrid factored sampling is an efficient and versatile method for inference in large hybrid systems.