Algorithms for Decision Making - Companion

Concepts, pictures, and code for Algorithms for Decision Making

This site is an independent, unofficial companion to Algorithms for Decision Making by Mykel Kochenderfer, Tim Wheeler, and Kyle Wray (MIT Press, 2022), the textbook for Stanford AA228/CS238. The book is freely available at algorithmsbook.com.

Every chapter has a page with the big picture, intuition, the key equations explained term by term, worked examples with real numbers, interactive figures, tested code in Python and Julia, and solved problems.

The book in one picture

The book is about one agent, or several, choosing actions under uncertainty. Part I builds the tools: probability to describe what we don’t know, and utility to say what we want. Parts II–V then each add one source of uncertainty (Figure 1): random outcomes of actions over time, an unknown model, a hidden state, and other agents. Within a Part, the chapters typically move from stating the problem, to solving it exactly, to approximating when exact is too expensive.

book intro Chapter 1 decisions under uncertainty p1 Part I  · Ch 2–6 probabilistic reasoning: represent, infer, learn, decide once intro->p1 start p2 Part II  · Ch 7–14 sequential problems: known model, random outcomes p1->p2 + time, random outcomes app Appendices A–F math, distributions, complexity, networks, search, problems p3 Part III  · Ch 15–18 model uncertainty: learn by acting p2->p3 + unknown model p4 Part IV  · Ch 19–23 state uncertainty: act on beliefs p2->p4 + hidden state p5 Part V  · Ch 24–27 multiagent systems: others choose too p3->p5 + other agents p4->p5 + other agents
Figure 1: How the Parts build on each other. Each labeled arrow adds what the next Part must handle; Part I supplies the probability and utility tools used everywhere.

Chapters

Chapter The question it answers
1 · Introduction What is a decision problem, and what are the ways to build a decision maker?
2 · Representation How do we write down uncertain beliefs compactly? (Bayesian networks)
3 · Inference Given some observations, how likely is everything else?
4 · Parameter Learning How do we fit the numbers in a model to data?
5 · Structure Learning How do we find which variables influence which?
6 · Simple Decisions How do we choose once, with utilities and the value of information?
Chapter The question it answers
7 · Exact Solution Methods How do we plan optimally in a small MDP? (value and policy iteration)
8 · Approximate Value Functions What if there are too many states for a table?
9 · Online Planning How do we plan only from the current state? (forward search, MCTS)
10 · Policy Search Can we search over policies directly, without values?
11 · Policy Gradient Estimation How do we estimate which way to change a policy?
12 · Policy Gradient Optimization How do we take safe, efficient steps with those gradients?
13 · Actor-Critic Methods How do a learned value and a learned policy help each other?
14 · Policy Validation How do we check that a policy is safe before we trust it?
Chapter The question it answers
15 · Exploration and Exploitation When should we try something new instead of using what works? (bandits)
16 · Model-Based Methods How do we learn a model while acting, and plan with it?
17 · Model-Free Methods Can we learn values directly from experience? (Q-learning, Sarsa)
18 · Imitation Learning How do we learn from an expert’s demonstrations?
Chapter The question it answers
19 · Beliefs How do we track a hidden state from noisy observations? (Bayes, Kalman and particle filters)
20 · Exact Belief State Planning How do we plan optimally over beliefs? (conditional plans, alpha vectors)
21 · Offline Belief State Planning How do we approximate a POMDP policy ahead of time, with bounds?
22 · Online Belief State Planning How do we plan from the current belief as we go?
23 · Controller Abstractions Can a small finite-state controller replace the belief?
Chapter The question it answers
24 · Multiagent Reasoning What should each player do in a one-shot game? (Nash and correlated equilibria)
25 · Sequential Problems What changes when games have states and time? (Markov games)
26 · State Uncertainty What if players can’t see the state either? (POMGs)
27 · Collaborative Agents How does a team with a shared goal act on private observations? (Dec-POMDPs)
Appendix What it covers
A · Mathematical Concepts Norms, convexity, information and entropy, gradient ascent, contraction
B · Probability Distributions Uniform, Gaussian, Beta, Dirichlet, and conjugate updates
C · Computational Complexity Big-O, P, NP, PSPACE, and why exact planning gets hard
D · Neural Representations Feedforward networks, backpropagation, regularization
E · Search Algorithms Forward search, branch and bound, dynamic programming, heuristics
F · Problems Every problem used on the site, with code to load it

Reading paths

You don’t have to read in order. Some routes through the site, each a chain of chapters that build on one another:

Table 1: Suggested orders for common goals.
If you want Read
The core of planning 7 → 8 → 9
Reinforcement learning 7 → 15 → 16 → 17
Policy gradients 10 → 11 → 12 → 13
Partial observability (POMDPs) 3 → 19 → 20 → 21 → 22
Games and teams 6 → 24 → 25 → 26 → 27
Probabilistic models 2 → 3 → 4 → 5

How to use this site

Each chapter page is laid out the same way:

  1. Big picture: where the chapter fits, its key ideas, and its vocabulary.
  2. Intuition: a concrete story before any math.
  3. Formalism: the definitions and key equations, in the book’s notation, each explained in words and term by term.
  4. Worked example: the ideas applied to real numbers.
  5. Interactive: figures you can change.
  6. Algorithms & code: implementations in Python and Julia, side by side.
  7. Solved problems: try each one before opening its solution.
  8. Recap and Cheat sheet & connections: the key points, the key equations, and links to related chapters.

Big picture and Intuition are written to stand alone: reading just those two sections of every chapter gives a tour of the whole book.

Each page states which language was executed to produce its figures. The code in the other language is tested separately.

Three reference pages collect material from across the site:

  • Notation: every symbol, grouped by Part.
  • Cheat sheets: every chapter’s key equations in one place.
  • Problems: the gallery of problems, with loading code in both languages.