Making Under Uncertainty
schedule and readings
assignments, projects, etc.
One of the primary goals of AI is the design, control and analysis of agents or systems that behave appropriately in various circumstances. Such intelligent agents require not only the ability to act but also to decide how to act as circumstances vary. In turn, good decision making requires that the agent have knowledge or beliefs about its environment and its dynamics (including the presence of other agents), about its own abilities to observe and change the environment, and its goals and preferences.
In this course, we will examine some of the techniques for modeling decision problems of various types and the computational methods used to solve them. The course will focus on probabilistic models: probabilistic inference, decision making under uncertainty, and game theoretic models of multiagent interaction will be the emphasis.
We will begin with a brief overview of probabilistic inference and spend a short time discussing Bayesian networks (a useful representation that will pop up from time to time in the course). We then discuss preferences and utility theory as a basis for "rational decision making". We will start with single-step decision making (including discussion of topics such as risk-aversion, multiattribute utility theory, and utility elicitation). We will then spend time on the issues that arise in multi-stage decision processes and planning. We will focus on Markov decision processes (MDPs), both fully and partially observable, and will examine several techniques developed in the AI community for solving these over the last few years, including those exploiting compact representations of systems (such as dynamic Bayes nets or factorial HMMs, function approximation techniques, etc). Time and interest permitting, we will also discuss some simple reinforcement learning methods.
We will spend the last half of the course dealing with complications that arise in multiagent decision problems. We begin with basic concepts in game theory: strategic form games, several forms of equilibria, and discuss simple coordination methods (e.g., learning, conventions, etc.). After introducing Bayesian games, we will delve into mechanism design and certain elements of auction theory as an illustration of mechanism design and delve into a few AI-based themes and computational issues that arise in such economic models. Finally, we move onto problems in social choice, viewing it as a form of mechanism design with qualitatitive preferences and no monetary transfer. We will discuss voting theory in some depth, as well as stable matching problems, as illustrations of prototypical problems in social choice.
Roughly 50-60% of the classes (or parts of classes) will be devoted to the presentation of background material, and others will be centered around the discussion of a particular research article (or articles). All participants are expected to have read (at some reasonable level of detail) the articles and background readings before class and contribute to the discussion.
Participants will also be expected to complete a small course project. The project will be decided in consultation with the instructor and may consist of an implementation of a particular reasoning, decision-making or planning theory (or theories), a short research paper on problem related to a course topic, or a critical literature survey. Near the end of the course, before projects are due, participants may be required to give a short report on the current status of their project to the rest of the class. (Whether we do presentations will depend on course enrolment.) Note that projects need not be complete at this point, so the presentation should emphasize the problem description and proposed approach, possibly with some interim results included.
Evaluation for the course will be based on class participation, the course project (including presentation if required) and three problem sets.