Dynamic Programming

Isaac Meilijson
Department of Statistics and Operations Research
Office Hours: Tuesdays 15-16. 311 Schreiber.
Phone: +972-3-640-8826.

Tel Aviv University course number: 0365-4432

Class Hours, Spring Semester 2006:

Tuesdays 17:10-20:00 at 102 Ornstein

Due to the multiplicity of Tuesday holidays, two additional classes will be held, each at the regular schedule 17-20: on Sunday April 9, 2006 (first day of the Passover vacation) and on Thursday April 20, 2006 (Mimouna Day).

Course Content:


  1. Definition of a stochastic DP problem, policy, discounting. Examples.
  2. Contraction operators and the Banach fixed point theorem.
  3. Discounted Dynamic Programming. The fundamental theorem. Stationary policies. Howard and Eaton-Zadeh improvement routines. The discounted Chow & Robbins search problem.
  4. Negative Dynamic Programming. The main theorem. Markovian policies. Howard improvement. Solution of the Needle in a Haystack problem. Priority rules in Queueing. The role of future irrelevance. The two-armed bandit problem.
  5. Positive Dynamic Programming. Optimality of bold play in subfair casinos with fixed goal. The role of excessivity. Martingale proofs via excessivity.
  6. One-optimal solutions and their relation to the average cost criterion. The Blackwell algorithm.
  7. Optimal stopping. Backwards induction, passage to the limit. The Secretary problem. Wald's Sequential Probability Ratio Test. The Chow & Robbins search problem with cost per observation.
  8. The Gittins index. Time sharing of a single server queue by a number of types of customers.

Helpful references; TENTATIVE - IN PREPARATION.

Last update: March 08, 2006