Comprendre l'effet de la stochasticité dans l'optimisation des politiques

Résumé :

Nous étudions l'effet de la stochasticité dans l'optimisation des politiques on-policy, et apportons les quatre contributions suivantes. Premièrement, nous montrons que la préférence des méthodes d'optimisation dépend de manière critique de l'utilisation de gradients stochastiques ou exacts. En particulier, contrairement au cadre du gradient exact, les informations géométriques ne peuvent pas être facilement exploitées dans le cas stochastique pour accélérer l'optimisation des politiques sans conséquences néfastes ou hypothèses peu pratiques. Deuxièmement, pour expliquer ces résultats, nous introduisons le concept de taux d'engagement pour l'optimisation stochastique des politiques, et nous montrons qu'il peut servir de critère pour déterminer la convergence presque certaine vers l'optimalité globale. Troisièmement, nous montrons qu'en l'absence d'informations d'oracle externes, qui permettent à un algorithme de déterminer la différence entre les actions optimales et sous-optimales à partir d'échantillons de politique, il existe un compromis inhérent entre l'exploitation de la géométrie pour accélérer la convergence et l'obtention presque certaine de l'optimalité. En d'autres termes, un algorithme non informé converge vers une politique globalement optimale avec une probabilité de 1, mais à un taux qui n'est pas meilleur que O(1/t), ou bien il atteint une convergence plus rapide que O(1/t), mais doit ensuite échouer à converger vers la politique globalement optimale avec une certaine probabilité positive. Enfin, nous utilisons la théorie du taux d'engagement pour expliquer pourquoi les méthodes pratiques d'optimisation des politiques sont sensibles à l'initialisation aléatoire, puis nous développons une méthode d'ensemble qui peut être garantie pour obtenir des solutions quasi-optimales avec une probabilité élevée.