Sur les taux de convergence globaux des méthodes de gradient de politique Softmax

Nous apportons trois contributions à une meilleure compréhension des méthodes de gradient de politique dans le cadre tabulaire. Premièrement, nous montrons qu'avec le vrai gradient, le gradient de politique avec une paramétrisation softmax converge à un taux O(1/t), avec des constantes dépendant du problème et de l'initialisation. Ce résultat élargit considérablement les résultats récents de convergence asymptotique. L'analyse repose sur deux constatations : le gradient de la politique de softmax satisfait une inégalité de Łojasiewicz, et la probabilité minimale d'une action optimale pendant l'optimisation peut être limitée en fonction de sa valeur initiale. Deuxièmement, nous analysons le gradient de politique régularisé par l'entropie et montrons qu'il bénéficie d'un taux de convergence linéaire significativement plus rapide O(e-t) vers la politique optimale softmax. Ce résultat résout une question ouverte dans la littérature récente. Enfin, en combinant les deux résultats ci-dessus et de nouveaux résultats supplémentaires de borne inférieure Ω(1/t), nous expliquons comment la régularisation entropique améliore l'optimisation de la politique, même avec le vrai gradient, du point de vue du taux de convergence. La séparation des taux est expliquée plus en détail en utilisant la notion de degré de Łojasiewicz non-uniforme. Ces résultats fournissent une compréhension théorique de l'impact de l'entropie et corroborent les études empiriques existantes.

Remerciements

Jincheng Mei tient à remercier Bo Dai et Lihong Li pour leurs discussions utiles et leurs commentaires sur une version préliminaire de ce manuscrit. Jincheng Mei tient à remercier Ruitong Huang pour ses discussions éclairantes au début du projet.