Decision Making Under Uncertainty
overview   syllabus   class schedule and readings   references

Fall/Winter 2006-07

Instructor: Craig Boutilier
Email: cebly@cs.toronto.edu
Phone: +1 (416) 978-2980
Office: Pratt (PT) 398C
But usually found in the Chair's Office: SF3302

Class Schedule and Logistics

Class will be held every second Monday at 4:00PM-5:30PM in PT266. First meeting will be held on Monday, Sept.25. The class will run from September through March. There will be occasional weeks where the class is cancelled (with advance warning) for travel commitments. Please consult here for the latest schedule periodically. Upcoming classes:
  • Monday, Jan.15, PT266
  • Monday, Jan.29, PT266
  • Monday, Feb.12, PT266
    • The class Schedule and Readings page will provide a more detailed schedule allong with a list of readings.

    Course Overview

    This course is a non-credit seminar in decision making under uncertainty. The intent is to provide students in a variety of disciplines with exposure to many of the basic models and algorithms and techniques for decision making under uncertainty in "modern AI". This course is a non-credit version of CSC2534, which has not been offered in several years. Unlike the "for credit" version, there will be no formal assignments or projects. However, informal assignments will be handed out (followed by sample solutions) for the more energetic in attendance.

    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, knowledge representation, and reasoning methods and spend a short time discussing Bayesian networks. 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 elicitation). We will spend quite a bit of 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 a number of 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). We conclude by considering complications that arise in multiagent decision problems. We will discuss some 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. Finally, we will consider recent research on the use of AI methods for tackling economic models.

    Informal prerequisites

    You should have a basic AI background, some familiarity with propositional logic, and a basic comfort level with probabilistic concepts and reasoning. Please come talk to me if you have any questions.

    Topics Covered

    A list of topics that will likely be covered:
  • The components of decision making and rational action.
  • Probabilistic semantics for belief.
  • Representation of probabilities, Bayesian networks (briefly)
  • Inference in Bayesian networks (briefly)
  • Preferences and utilities.
  • Rational decision-making.
  • Foundations of utility theory.
  • Multi-attribute utility theory.
  • Preference elicitation.
  • Optimal planning, and multi-stage decision making.
  • Markov decision processes.
  • Structured computational techniques for MDPs.
  • Function approximation and simulation.
  • Partially-observable Markov decision processes.
  • Multiagent decision making.
  • Basics of game theory.
  • Refinements of Nash equilibria.
  • Stochastic and Markov games.
  • Cooperation.
  • Games of incomplete information (Bayesian games)
  • Mechanism design (and computational approaches to MD).
  • Auction theory (as an illustration of mechanism design).
  • Bargaining.
    • The topics covered (and especially the emphasis) will depend on the interests of the participants. There will be a special emphasis on game-theoretic and economic approaches to decision making.

    Organization

    The class will meet roughly once every two weeks on Mondays, beginning Sept.25. Unfortunately, as department chair, my schedule can get rather constrained (especially with travel), so there may be weeks where the class does not meet: such cancellations will be announced at least two weeks in advance. 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 (or background readings) before class and contribute to the discussion.

    There will be no formal evaluation since this is a non-credit course. However, informal assignments will be made available periodically for interested students, and sample solutions will be distributed for your own self-assessment.

    Text and Readings

    We will use a new (as yet unpublished text by Yoav Shoham and Kevin-Leyton Brown, "Mulitagent Systems", for a portion of this class. The authors have given permission to distribute relevant draft chapters to class participants. Specific readings will be assigned  as the class progresses. For some basic background in various topics, Russell and Norvig's AI text, "Artficial Intelligence: A Modern Approach" may prove useful for some. A list of readings can be found on the class Schedule and Readings page.