CSC2534: Decision Making Under Uncertainty
overview   syllabus   class schedule and readings   references   assignments, projects, etc.  


Fall 2014

Instructor: Craig Boutilier

Email:
cebly@cs.toronto.edu

Phone:
+1 (416) 946-5714

Office: Pratt (PT) 398C

Important Notices


Class Schedule and Logistics

Please Note Room Change: Class will be held Tuesday 1:00PM-3:00PM in the Anthropology Building, AP 120.Bahen Center: BA B026. The class Schedule and Readings page will provide a more detailed schedule along with a list of readings.

Course Overview

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.

Informal prerequisites

You should have a some familiarity with propositional logic, "abstract" algorithm design, and a basic comfort level with probabilistic concepts and reasoning. Some basic AI background is helpful, but certainly not necessary. 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.
  • This may be covered in a separate tutorial session.
  • 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.
  • Intro to Reinforcement Learning (time-permitting)
  • Multiagent decision making: Game theory
  • 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).
  • Multiagent decision making: Social choice
  • Elements of social choice and voting.
  • Voting rules.
  • Computational considerations.
  • Manipulation and control.
  • Voting with partial information.
  • Matching problems.
  • Other forms of "mechanism design without money".
  • There will be a special emphasis on multiagent decision making, using game-theoretic models from economics and social choice.

    Organization

    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.

    Text and Readings

    A list of readings can be found on the class Schedule and Readings page. General background references can be found on the class General background readings page.