Computation and Structure of Optimal Reset Policies
Ellis L. Johnson · Journal of the American Statistical Association · 1967
Suppose there are a finite number of possible states of a system, the state is observable at the beginning of each period, and it can be changed at that time to any other state with a cost for changing the state or resetting. In addition, an immediate loss is incurred depending on the state at the beginning of the period, but after resetting. The problem is, then, for which states to reset and where to reset to. For the infinite horizon problem with discount factor 0 ≤ β < 1 and for average cost per period, a computational procedure is given which amounts essentially to inverting a matrix the size of the number of states for which it is optimal to not reset. In terms of the corresponding linear program, once certain columns enter the basis, they do not subsequently drop from the basis. Some results on structure of optimal policies are also given.