Vers une méthode de gradient de politique pratique et principielle pour les bandits et les MDP tabulaires

Nous considérons les méthodes de gradient de politique softmax (stochastiques) pour les bandits et les processus de décision de Markov (MDP) tabulaires. Bien que l'objectif de PG soit non-convexe, des recherches récentes ont utilisé la douceur de l'objectif et les propriétés de domination du gradient pour atteindre la convergence vers une politique optimale. Cependant, ces résultats théoriques nécessitent de régler les paramètres de l'algorithme en fonction de quantités dépendantes du problème inconnues (par exemple, l'action optimale ou le vecteur de récompense réel dans un problème de bandit). Pour remédier à ce problème, nous empruntons des idées de la littérature d'optimisation pour concevoir des méthodes PG pratiques et principielle tant dans les cas exacts que stochastiques. Dans le cadre exact, nous utilisons une recherche de ligne d'Armijo pour définir la taille de pas pour PG softmax et démontrons empiriquement un taux de convergence linéaire. Dans le cadre stochastique, nous utilisons des tailles de pas décroissantes exponentiellement et caractérisons le taux de convergence de l'algorithme résultant. Nous montrons que l'algorithme proposé offre des garanties théoriques similaires à celles des résultats de pointe, mais ne nécessite pas la connaissance de quantités semblables à celles d'un oracle. Pour le cadre du bandit à plusieurs bras, nos techniques aboutissent à un algorithme PG théoriquement principiel qui ne nécessite pas d'exploration explicite, la connaissance de l'écart de récompense, des distributions de récompense, ou du bruit. Enfin, nous comparons empiriquement les méthodes proposées aux approches PG qui nécessitent des connaissances d'oracle, et démontrons une performance compétitive.