Optimization of stochastic finite state systems
R.L. Kashyap · IEEE Transactions on Automatic Control · 1966
A class of stochastic dynamic systems is considered in which the setSof allowable states, the setQof all the inputs, and the setOof the outputs are all finite. For the subclass of the systems in which the state can be exactly measured, a method is given to find the optimal control, so as to optimize a suitable criterion function. The set of probabilitiesProb(q(t) = q_{k}/s(t) =s_{j}), q_{k} \in Q, s_{j} \in S, whereq(t)ands(t)are the input and state at timet, respectively, plays the role of control. The determination of the optimal control involves only a solution of a set ofNdifference equations, whereNis the total number of states. These results will be extended for systems in which the measured output is noisy. In this case, by control one means the set of probabilities Prob(q(t) = q_{k}/y(1),... , Y(t)), q_{k} \in Qwherey(t)is the measured output at timet. These probabilities are found to be products of the current estimate of the state of the systems(t), based on all the available measurements with certain precomputable constants. These results are applied to the analysis of time-sharing computer systems like project MAC, and demonstrate how to choose an optimal queue discipline among the various available queue disciplines for scheduling the various users.