Adaptive Control of Markov Chains: An Optimization Oriented Approach (Queueing Networks, Stochastic Models, Computer)

100 p.Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1985.In this thesis we consider the control of a dynamic system modeled as a Markov chain. The transition probability matrix of the Markov chain depends on the control u and also on an unknown parameter (alpha)('o). The unknown parameter belongs to a given finite set A. The performance of the system is measured by a long run average cost criterion. A direct approach to the optimization of the performance is not feasible. A common procedure calls for an on-line estimation of the unknown parameter and the minimization of the cost functional using the estimate in lieu of the true parameter. This certainty equivalence (CE) solution may fail to achieve optimal performance.We give a game theoretic interpretation of the set of possible equilibria of the system when the CE controller is used. This interpretation suggests a new optimization oriented approach to adaptive control. We consider a compatible functional which simultaneously takes care of the estimation and control aspects of the problem. The global minimum of this composite functional coincides with the minimum of the original functional. Thus its joint minimization with respect to control and parameter estimates would yield the optimal control policy. Although joint minimization is not feasible, it suggests an algorithm that asymptotically achieves the desired goal. In fact, we prove that the adaptive control law converges to the optimal one in a Cesaro sense and the optimal performance is attained almost surely. We also show that when a strong identifiability condition holds, the probability that the control to be applied at time t differs from the optimal one is upper bounded by a term that decreases geometrically in t. Upper bounds for the modeling accuracy that guarantees convergence of the algorithm to the control law associated with one of the members of the possible imperfect modeling set are obtained.We discuss the applicability of the proposed algorithm to Queueing Systems, in general, and multiprogrammed computer models in particular.U of I OnlyRestricted to the U of I community idenfinitely during batch ingest of legacy ETD