Bruno Gaujal, équipe MESCAL, IMAG, Grenoble.
Les transparents.
On considère un système dynamique discret général (par exemple un automate d’état fini) dans lequel les transitions sont probabilistes. Si on considère une fonction de coût qui dépend des états et des transitions, le problème de l’optimisation du coût total des T premières transitions (ou sur un horizon infini) est compliqué par le caractère aléatoire du système.
La théorie des processus de décision Markoviens permet de poser ce problème sous forme d’une équation de programmation dynamique (ou de point fixe dans le cas d’un temps infini), appelée l’équation de Bellman. Sa résolution est linéaire en le nombre d’états et le nombre de transitions. Cette complexité linéaire cache cependant la “malédiction de la dimensionalité” (curse of dimensionality) qui provient de l’ explosion combinatoire du nombre des états en la taille du système.
Optimisation distribuée
Une première approche pour lutter contre l’explosion combinatoire est de distribuer le calcul de la stratégie optimale sur les composants du système: Chaque contrôleur agit sur un état local et n’est pas confronté à l’explosion de la taille globale.
Ici les questions qui seront abordées sont la modélisation sous forme de jeu et le calcul d’équilibres sans communications directes entre les composants.
Limite en champs moyen et optimisation
Une autre approche pour combattre l’explosion combinatoire quand le nombre de composants N devient grand, est de passer à la limite quand N tend vers l’infini.
Une simplification se produit à la limite: comme pour la loi des grands nombres, le système limite se comporte comme une moyenne statistique, qui est déterministe et continu alors que le système d’origine est stochastique et discret.
On expliquera pourquoi ce changement d’échelle est compatible avec la technique d’optimisation de Bellman.
Jeux en champs moyen
Enfin, on montrera comment on peut combiner les deux approches, le passage à l’échelle et la distribution du contrôle sur les composants pour introduire les jeux en champs moyen.
Exemples d’applications
Ces quatre parties seront illustrées par des exemples illustratifs respectifs:
- Comment gagner aux échecs contre un adversaire qui joue mieux?
1b Comment choisir le meilleur candidat pour faire un stage? - Comment calculer localement des routes stables dans un réseau de communication ?
- Pourquoi un peu de centralisation peut aider dans des très grands systèmes de calcul.
- Calcul d’une politique de vaccination optimale.