Decision Making Under Uncertainty (noncredit)

Course Overview -- Fall/Winter 2006-07

Instructor: Craig Boutilier



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

Class Schedule

Class will be held every second Monday at 11AM-12:30PM (tentative) in PT266 (tentative). 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, Sept.25, 11AM PT266
  • Monday, Oct.9, 11AM PT266
  • Monday, Oct.23 11AM PT266
  • 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.
  • Auction theory (as an illustration of mechanism design).
  • The topics covered (and especially the emphasis) will depend on the interests of the participants.

    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 half 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

    Text and Readings

    While this is not a required text, we will use Russell and Norvig's text Artificial Intelligence: A Modern Approach (Prentice-Hall, 1995) as the basis for certain background material in decision theory, etc.

    Research articles to be discussed in class will form the bulk of the class reading. More comprehensive references in specific areas will be provided for those who find these topics of interest. Research articles for class, as well as background and optional material will be made available through the course website.

    A draft text on game theory and economics models may be made available for our use by Prof. Yoav Shoham. I will post further info as it becomes available. (The text is being revised, so I'll be obtaining up to date chapters a couple of weeks before we obtain that material.)


    Return to Craig's HomePage