About This Course

This book is about decisions that are made in sequence, where each decision changes the situation in which the next one is made. A warehouse orders stock before it knows demand, a maintenance crew decides whether to repair a machine whose condition it can only guess, a seller turns down an offer in the hope of a better one, a spacecraft fires or coasts. In every case the object to be chosen is not a number but a rule, called a policy, that says what to do in each situation that can arise. The book teaches how to find the best such rule and how to prove that it is best.

It is written for a reader working alone: an advanced undergraduate or beginning graduate student in mathematics, engineering, operations research, economics, or computer science. You need four things before starting. From Probability Theory: conditional probability, expectation, and conditional expectation for discrete random variables. From Stochastic Processes: what a Markov chain and its transition matrix are; this book does not develop their theory, it chooses among them. From Continuous Optimization: first-order conditions for minimizing a differentiable function, with and without constraints, and what convexity buys. From Differential Equations and Linear Algebra: solving linear systems of differential equations, and positive definite matrices. When a result owned by one of those courses is used, it is stated with the hypotheses the argument needs and marked once with its library identifier; it is not proved again here.

The book aims at six abilities, each of which you should be able to exercise with the book closed. Formulate a sequential decision problem with a state that is small enough to compute with and large enough to be correct. Solve a finite-horizon problem by backward induction and read both a value and a policy from the table. Solve a discounted infinite-horizon problem by value iteration or policy iteration, and bound the error of a value function that has not yet converged. Replace an unobserved state by a belief and update it. Recognise a threshold rule in a stopping problem and compute the threshold. Write the Hamilton–Jacobi–Bellman equation and the Pontryagin conditions for a continuous-time problem, solve the linear-quadratic case through a Riccati equation, and work a minimum-time problem to its switching curve.

The notation is fixed across the book. Time is discrete in Chapters 1 to 8 and 10, with stages \(k=0,1,\dots,N-1\) ; the state at stage \(k\) is \(x_k\) , the control is \(u_k\) , and the random disturbance is \(w_k\) . A policy is \(\pi=(\mu_0,\dots,\mu_{N-1})\) , where \(\mu_k\) maps states to controls. The optimal cost from stage \(k\) onward is \(J_k\) , and in infinite-horizon problems the optimal cost is \(J^\star\) . Costs are minimized unless a problem is stated in terms of rewards, in which case the text says so and maximizes. In Chapter 9 time is continuous, the value function is \(V(t,x)\) , the Hamiltonian is \(H\) , and the costate is \(p(t)\) . Vectors are columns and \(A^{\top}\) is a transpose. For symmetric matrices, \(K\succeq 0\) means positive semidefinite and \(K\succ 0\) positive definite.

Each chapter ends with exercises that run from recall through computation to proof. The companion solutions give full arguments for some, hints for others, and bare answers for a few. Many of the worked examples and solutions have been recomputed by machine, and you are encouraged to do the same: nearly every table in this book can be reproduced with a dozen lines of code, and writing those lines is the fastest way to find out whether you have understood a recursion. A number of exercises present an argument that sounds right and is wrong, and ask you to say where it fails. Sequential decision problems are rich in such arguments, and learning to locate the faulty step is part of learning the subject.