Optimal Control of Random Walks.
SYRACUSE UNIV N Y DEPT OF INDUSTRIAL ENGINEERING AND OPERATIONS RESEARCH
Pagination or Media Count:
This is a study of a random walk on the nonnegative integers whose steps are controlled as follows. Upon arriving at a location i, a pair of probabilities p,q is selected from a prescribed set, a reward ri,p,q is received and the next step takes the walk to locations i1, i-1, or i, with respective probabilities p, q and 1-p-q when i0 these probabilities are p, 0 and 1-p. This is repeated indefinitely. A rule for successively selecting the probabilities p,q is a control policy. Conditions are identified on the rewards and probabilities under which there exist monotonic optimal policies for discounted and average rewards. For example, in one case it is optimal to increase the probability of backward steps as the location i increases. Our results are based on 1 a criterion for monotone optimal policies, 2 a result describing when an upper envelope of concave functions is concave, and 3 a relation between optimal Policies for the discounted and average reward criteria. Procedures for computing optimal policies are also presented. Author
- Statistics and Probability
- Operations Research