Pourquoi l'algorithme d'itération de politique converge-t-il vers une fonction de politique et de valeur optimale?

10

Je lisais les notes de cours d' Andrew Ng sur l'apprentissage par renforcement et j'essayais de comprendre pourquoi l'itération des politiques convergeait vers la fonction de valeur optimale et la politique optimale .Vπ

L'itération de la politique de rappel est:

Initialize π randomlyRepeat{Let V:=Vπ \for the current policy, solve bellman's eqn's and set that to the current VLet π(s):=argmaxaAsPsa(s)V(s)}

Pourquoi un algorithme gourmand conduit-il à une politique optimale et à une fonction de valeur optimale? (Je sais que les algorithmes gourmands ne garantissent pas toujours cela, ou pourraient rester coincés dans les optima locaux, donc je voulais juste voir une preuve de son optimalité de l'algorithme).

De plus, il me semble que l'itération de politique est quelque chose d'analogue au clustering ou à la descente de gradient. Au clustering, car avec le réglage actuel des paramètres, on optimise. Similaire à la descente de gradient, car il choisit simplement une valeur qui semble augmenter certaines fonctions. Ces deux méthodes ne convergent pas toujours vers des maxima optimaux, et j'essayais de comprendre en quoi cet algorithme était différent des précédents que j'ai mentionnés.


Voici mes pensées jusqu'à présent:

Disons que nous commençons avec une politique , puis après la première étape, pour cette politique fixe, nous avons cela:π1

Vπ1(s)=R(s)+γsPsπ1(s)(s)Vπ1(s)

V(1):=Vπ1(s)

Où V ^ {(1)} est la fonction de valeur pour la première itération. Ensuite, après la deuxième étape, nous choisissons une nouvelle stratégie pour augmenter la valeur de . Maintenant, avec la nouvelle politique , si nous faisons la deuxième étape de l'algorithme, l'inégalité suivante est vraie:π2Vπ1(s)π2

R(s)+γsPsπ1(s)(s)Vπ1(s)R(s)+γsPsπ2(s)(s)Vπ1(s)

Parce que nous choisissons à la deuxième étape pour augmenter la fonction de valeur à l'étape précédente (c'est-à-dire pour améliorer . Jusqu'à présent, il est clair que le choix de ne peut qu'augmenter V ^ {(1)}, car c'est ainsi que nous choisissons . Cependant, ma confusion vient de l'étape de répétition, car une fois que nous répétons et revenons à l'étape 1, nous changeons complètement les choses, car nous recalculons pour la nouvelle stratégie . Qui donne:π2V(1)π2π2V2π2

Vπ2(s)=R(s)+γsPsπ2(s)(s)Vπ2(s)

mais ce n'est PAS:

Vπ1(s)=R(s)+γsPsπ2(s)(s)Vπ1(s)

Ce qui semble être un problème car été choisi pour améliorer , et non ce nouveau . Fondamentalement, le problème est que garantit d'améliorer en faisant place de lorsque la fonction de valeur est . Mais dans l'étape de répétition, nous changeons en , mais je ne vois pas comment cela garantit que la fonction de valeur s'améliore de façon monotone à chaque répétition car été calculé pour améliorer la fonction de valeur lorsque les fonctions de valeur restent àπ2V(1)Vπ2pi2R(s)+γsPsπ1(s)(s)Vπ1(s)π2pi1Vπ1Vπ1Vπ2π2Vπ1, mais l'étape 1 change en (ce qui est mauvais car I n'a amélioré que la fonction de valeur précédente que nous avions).Vπ1Vπ2π2

Pinocchio
la source
1
Juste une note: gourmand n'implique pas qu'un algorithme ne trouvera pas de solution optimale en général.
Regenschein
1
L'itération de valeur est un algorithme de programmation dynamique, plutôt qu'un algorithme gourmand. Les deux partagent certaines similitudes, mais il existe des différences. Jetez un œil à stackoverflow.com/questions/13713572/… .
francoisr
@francoisr personne ne m'a jamais dit ça. C'est peut-être pour ça que c'était (inutilement) mystérieux pour moi. Je connais assez bien DP. Merci quand même! :)
Pinocchio

Réponses:

4

Je pense que la pièce qui vous manque est que est garanti pour la même raison que nous pouvons commander . C'est essentiellement la définition d'une politique étant meilleure qu'une autre - que sa fonction de valeur est supérieure ou égale dans tous les États. Vous avez garanti cela en choisissant les actions de maximisation - aucune valeur d'état ne peut être pire qu'avant, et si un seul choix d'action a changé pour choisir une meilleure action de maximisation, alors vous savez déjà (mais peut-être pas avoir calculé) que le pour cet état va être supérieur à ce qu'il était pour .Vπ2Vπ1π2π1Vπ2(s)Vπ1(s)

Lorsque nous choisissons de maximiser les résultats pour générer , nous ne savons pas ce que les nouveaux vont être pour n'importe quel état, mais nous savons que .π2Vπ2(s)s:Vπ2(s)Vπ1(s)

Par conséquent, le fait de revenir dans la boucle et de calculer pour la nouvelle stratégie est garanti d'avoir des valeurs identiques ou supérieures à celles d'avant, et lorsqu'il s'agit de mettre à jour la stratégie à nouveau, .Vπ2π3π2π1

Neil Slater
la source
4

Voyons d'abord pourquoi l'algorithme d'itération de politique fonctionne. Il comporte deux étapes.

Étape d'évaluation des politiques:

vn=rdn+γPdnvn est la forme vectorielle générale du système d'équations linéaires.

Ici, les termes sont des récompenses immédiates et des lignes correspondantes de la matrice de transition.rdn,Pdn

Ces termes dépendent de la politiqueΠn

En résolvant le système d'équations ci-dessus, nous pouvons trouver les valeurs devn

Étape d'amélioration des politiques:

Supposons que nous avons pu trouver une nouvelle stratégie telle queΠn+1

rdn+1+γPdn+1vnrdn+γPdnvnrdn+1[IγPdn+1]vnsay this is eqn. 1

Maintenant, sur la base de la nouvelle stratégie , nous pouvons trouver , disons que c'est l'équation 2.Πn+1vn+1=rdn+1+γPdn+1vn+1

Nous allons montrer que ;vn+1vn

c'est-à-dire essentiellement pour tous les états, la nouvelle politique donne une meilleure valeur par rapport à la politique précédenteΠn+1Πn

Preuve:

De l'équation 2, nous avons,

[IγPdn+1]vn+1=rdn+1

De, , nous avons1&2

vn+1vn

Essentiellement, les valeurs augmentent de façon monotone à chaque itération.

Il est important de comprendre pourquoi l'Interaction politique ne sera pas bloquée au maximum local.

Une politique n'est rien d'autre qu'un espace d'action étatique.

À chaque étape d'itération de politique, nous essayons de trouver au moins une action d'état différente entre et et voyons si . Ce n'est que si la condition est satisfaite que nous calculerons la solution du nouveau système d'équations linéaires.Πn+1Πnrdn+1+γPdn+1vnrdn+γPdnvn

Supposons que et sont respectivement l'optimum global et local.ΠΠ#

Implique,vv#

Supposons que l'algorithme est bloqué à l'optimum local.

Si tel est le cas, l'étape d'amélioration de la politique ne s'arrêtera pas à l'espace d'action d'état optimal local , car il existe au moins une action d'état dans qui est différente de et donne une valeur plus élevée de par rapport àΠ#ΠΠ#vv#

ou, en d'autres termes,

[IγPd]v[IγPd]v#

rd[IγPd]v#

rd+γPdv#v#

rd+γPdv#rd#+γPd#v#

Par conséquent, l'itération de politique ne s'arrête pas à un optimum local

Honeybadger
la source