COUNTABLE STATE DISCOUNTED MARKOVIAN DECISION PROCESSES WITH UNBOUNDED REWARDS.
STANFORD UNIV CALIF DEPT OF OPERATIONS RESEARCH
Pagination or Media Count:
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 n1 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 n1 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 Blackwells work on discounted dynamic programming a central role is played by Banachs 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
- Administration and Management
- Operations Research