Optimal Control of Random Walks.
Abstract
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 r(i,p,q) is received and the next step takes the walk to locations i+1, i-1, or i, with respective probabilities p, q and 1-p-q (when i=0 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)
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 1977
- Accession Number
- ADA043521
Entities
People
- Richard F. Serfozo
Organizations
- Syracuse University