TIME-SHARING POLICIES FOR CONTROLLED MARKOV-CHAINS

We propose a class of nonstationary policies called policy time sharin g (PTS), which possesses several desirable properties for problems whe re the criteria are of the average-cost type; an optimal policy exists within this class, the computation of optimal policies is straightfor ward, and the implementation of this policy is easy. While in the fini te state case stationary policies are also known to share these proper ties, the new policies are much more flexible, in the sense that they can be applied to solve adaptive problems, and they suggest new ways t o incorporate the particular structure of the problem at-hand into the derivation of optimal policies. In addition, they provide insight int o the pathwise-structure of controlled Markov chains. To use PTS polic ies one alternates between the use of several stationary deterministic policies, switching when reaching some predetermined state. In some ( countable state) cases optimal solutions of the PTS type are available and easy to compute, whereas optimal stationary policies are not avai lable. Examples that illustrate the last point and the usefulness of t he new approach are discussed, involving constrained optimization prob lems with countable state space or compact action space.