Dynamic programming and Markov processes

✍ Scribed by Ronald A. Howard

• Publisher: Technology Press of Massachusetts Institute of Technology
• Year: 1960
• Tongue: English
• Leaves: 146
• Category: Library

✦ Table of Contents

Dynamic Programming and Markov Processes
Preface
Contents
Introduction
Markov Processes
The Toymaker Example—State Probabilities
The ^-Transformation
n < 0
2 f(n + l)zn = 2 —/(0)]
n=0 m=1
z-Transform Analysis of Markov Processes
Transient, Multichain, and Periodic Behavior
Markov Processes with Rewards
Solution by Recurrence Relation
The Toymaker Example
^-Transform Analysis of the Markov Process with Rewards
v(n + 1) = q + Pv(n) n = 0, 1, 2, • • • (2.6)
- v(0)] = y^— q + Pv(z)
(I - zP)r(z) = yA_ q + V(O)
v(s) = —(I - zP)-iq + (I — zP)-iv(O) (2.7) 1 — z
= * (I _ 2P)-iq (2.8)
F(n) = n
Asymptotic Behavior
The Solution of the
Sequential Decision Process by Value Iteration
Introduction of Alternatives
The Toymaker’s Problem Solved by Value Iteration
Evaluation of the Value-Iteration Approach
The Policy-Iteration Method for the Solution of
Sequential Decision Processes
The Value-Determination Operation
or
The Policy-Improvement Routine
The Iteration Cycle
The Toymaker’s Problem
A Proof of the Properties of the Policy-Iteration Method
Use of the Policy-Iteration Method in Problems of Taxicab Operation, Baseball, and Automobile Replacement
An Example—Taxicab Operation
A Baseball Problem
The Replacement Problem
The Policy-Iteration Method for Multiple-Chain Processes
The Value-Determination Operation
The Policy-Improvement Routine
A Multichain Example
Properties of the Iteration Cycle
0.
The Sequential Decision Process with Discounting
- v(0)] = p-1— q + pPc(z) 1 — z
(I_pzP)v(z) = rA-q + v(O)
(I - 1-.P) =
The Sequential Decision Process with Discounting Solved by Value Iteration
The Value-Determination Operation
2 (ppy q + pnP”v(0)
The Policy-Improvement Routine
An Example
Proof of the Properties of the Iteration Cycle
The Sensitivity of the Optimal Policy to the Discount Factor
The Automobile Problem with Discounting
Summary
The Continuous-Time
Decision Process
The Continuous-Time Markov Process
The Solution of Continuous-Time Markov Processes by Laplace Transformation
The Continuous-Time Markov Process with Rewards
The Continuous-Time Decision Problem
The Value-Determination Operation
The Policy-Improvement Routine
Completely Ergodic Processes
The Foreman’s Dilemma
Computational Considerations
The Continuous-Time Decision Process with Discounting
v = (al — A)-1q
Policy Improvement
Comparison with Discrete-Time Case
Conclusion
The Relationship of Transient to Recurrent Behavior
Mv = q
v = M-1q
-W-if
UW = I