Conditions de convergence des politiques et des algorithmes d'itération de valeurs

8

Des algorithmes d'itération de politiques et de valeurs peuvent être utilisés pour résoudre des problèmes de processus de décision de Markov. J'ai du mal à comprendre les conditions nécessaires à la convergence. Si la politique optimale ne change pas pendant deux étapes (c'est-à-dire pendant les itérations i et i + 1 ), peut-on conclure que les algorithmes ont convergé? Sinon, alors quand?

ELEC
la source

Réponses:

3

Pour répondre à votre question, permettez-moi d'abord d'écrire quelques (in) égalités importantes.

Équation d'optimalité de Bellman:

v(s)=maxaE[Rt+1+γv(St+1)St=s,At=a]=maxasp(ss,a)[r(s,a,s)+γv(s)]

v(.) est la fonction de valeur optimale.

Théorème d'amélioration des politiques ( Pit ):

Soit et n'importe quelle paire de politiques déterministes telles que, pour tout , Alors la politique doit être aussi bon ou meilleur que . Autrement dit, il doit obtenir un retour attendu supérieur ou égal de tous les états . ππsSqπ(s,π(s))vπ(s)ππsS:vπ(s)vπ(s)

(voir à la page 89 de Sutton & Barto, Renforcement de l'apprentissage: un livre d' introduction )

Nous pouvons améliorer une politique à chaque état par la règle suivante:π

π(s)=argmaxaqπ(s,a)=argmaxasp(ss,a)[r(s,a,s)+γvπ(s)]

Notre nouvelle politique satisfait la condition de Pit et est donc aussi bonne ou meilleure que . Si est aussi bon, mais pas meilleur que , alors pour tous les . De notre définition de nous déduisons que:ππππvπ(s)=vπ(s)sπ

vπ(s)=maxaE[Rt+1+γvπ(St+1)St=s,At=a]=maxasp(ss,a)[r(s,a,s)+γvπ(s)]

Mais cette égalité est la même que l'équation d'optimalité de Bellman, donc doit être égal à .vπv

D'après ce qui précède, il est clair, espérons-le, que si nous améliorons une politique et obtenons la même fonction de valeur que nous avions auparavant, la nouvelle politique doit être l'une des politiques optimales. Pour plus d'informations, voir Sutton & Barto (2012)

Jan Vainer
la source
1

Vous avez raison: soit l'estimation de la fonction de la valeur actuelle, soit l'estimation de la politique actuelle peut décrire complètement l'état de l'algorithme. Chacun implique un prochain choix unique pour l'autre. À partir du document lié ci-dessous,

"L'itération de stratégie se poursuit jusqu'à ce que ."Vn+1=Vn,αn+1=αn

https://editorialexpress.com/jrust/research/siam_dp_paper.pdf

eric_kernfeld
la source