Optimal Control of Random Walks.
Richard F. Serfozo · 1977
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)