COUNTABLE STATE DISCOUNTED MARKOVIAN DECISION PROCESSES WITH UNBOUNDED REWARDS.
Abstract
Countable state, finite action Markov decision processes are investigated under a criterion of maximizing expected discounted rewards over an infinite planning horizon. Well-known results of Maitra and Blackwell are generalized, their assumption of bounded rewards being replaced by the following weaker condition: the expected absolute reward to be received at time n+1 minus the actual absolute reward received at time n (as a function of the state of the system of time n, the action taken at time n, and the decision rule to be followed at time n+1) can be bounded above. Under this condition it is shown that the expected discounted reward (over the infinite planning horizon) from each policy is finite and that there exists a stationary policy which is optimal. Additional results are presented concerning the policy improvement and successive approximations algorithms for computation of optimal policies. All of these results are extended to Markov renewal decision processes under one additional condition on the transition time distributions. As in Blackwell's work on discounted dynamic programming a central role is played by Banach's fixed point theorem for contraction mappings. Examples are presented of inventory and queueing control problems which satisfy our assumptions but do not exhibit bounded rewards. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Mar 12, 1970
- Accession Number
- AD0702409
Entities
People
- John M. Harrison
Organizations
- Stanford University