TWO SHORT NOTES ON MARKOV PROCESSES: I. A TEST FOR SUB-OPTIMAL ACTIONS IN MARKOVIAN DECISION PROBLEMS. II. AN INTRINSICALLY DETERMINED MARKOV CHAIN,
Abstract
In a Markovian decision problem choice of an action determines an immediate return and the probability of moving to the next state. It is desired to maximize the expected total of discounted future returns. If upper and lower bounds on the optimal expected return are available, a simple test is described which may show that certain actions are sub-optimal, permanently eliminating them from further consideration. This test may be incorporated into the dynamic programming routine for solving the decision problem. This was tried on Howard's automobile replacement problem, using the upper and lower bounds described in 'A MModified dynamic programming method' (J. of Math. Anal. and Appl, 14 April, 1966). The amount of computation required by the dynamic programming routine was reduced, conservatively, by 75%. (Note I) This paper describes a situation where there is a transient Markov chain with one absorbing state, such that the transition law of the process itself depends on the probability of the process being trapped in the absorbing state. Thus the process is defined implicitly, by its own behavior, so to speak. The existence and uniqueness of a transition law satisfying the given conditions is established. This result may give rise to additional ways of characterizing optimal policies, as is suggested by interpreting the result in terms of the behavior of a gambler. (Note II)
Document Details
- Document Type
- Technical Report
- Publication Date
- Aug 01, 1966
- Accession Number
- AD0641195
Entities
People
- James B. Macqueen