Computationally efficient adpative control algorithms for Markov chains

Note:Iterative algorithms are proposed for adaptive long-run average cost control of finite state Markov chains. The algorithms estimate the unknown parameter using a strongly consistent estimator, and use this estimate to update the control policy. No prior knowledge of the optimal control policies is assumed. The main contribution of this thesis is the on line computation of an optimal control based on strongly consistent estimates of the unknown parameters. At each iteration, the actions of any number of states, as few as one or as many as all states, may be updated as long as the actions of the states along the sample path of the chain are updated in the order that those states are generated; in this sense the algorithms are referred to as asynchronous as opposed to synchronous algorithms where all states must be updated simultaneously at each iteration. It is illustrated, through simulation results, that by updating only the actions of the states along the sample path of the chain, the algorithms reach a policy whose long-run average cost is within 5% of an optimal one after an amount of computation which is considerably smaller than that required by value-iteration of dynamic programming. The algorithms converge to a stationary optimal policy in finite time.Nous proposons ici des procédures itératives pour le calcul des politiques optimales de contrôle dans les chaines de Markov. Nous considérons des chaines de Markov dont les probabilités de transition sont inconnues et dépendent d'un paramètre. L'objectif étant de minimiser les couts moyens de la chaine de Markov en état stationnaire, ces procédures doivent à la fois estimer le paramètre inconnu et déterminer la meilleure politique de contrôle. À chaque itération un estimateur "fortement consistent" du paramètre inconnu est calculé et subséquemment utilise pour bonifier la politique de contrôle. L'apport principal de cette thèse est le calcul en temps réel du contrôle optimal à partir d'une estimation "fortement consistent" du paramètre inconnu du système. À chaque itération la politique de contrôle est mise à jour pour un sous ensemble non-vide des états du système; ce sous-ensemble doit contenir, au moins, l'état observe. Dans ce sens, nos algorithmes peuvent être qualifies d'asynchrones par opposition aux algorithmes synchrones qui eux requièrent la mise à jour du contrôle pour tous les états du système a chaque itération. Nous démontrons qu'un nombre fini d'étapes est requis pour que nos procédures convergent (avec probabilité un) a la politique optimale de contrôle. Par simulation nous constatons que le nombre d'itérations requis par nos procédures pour atteindre une précision de 5% est de beaucoup inférieur au nombre requis par la méthode "value-itération" en programmation dynamique