Comprendre les fonctions de stratégie et de valeur apprentissage par renfort

Question

Vous avez une politique, qui est effectivement une distribution de probabilité d'actions pour tous mes états. Une fonction de valeur détermine le meilleur déroulement des actions pour obtenir la récompense la plus élevée.

J'ai donc une politique aléatoire. Je reçois la fonction de valeur. Je mets à jour ma politique avec une nouvelle distribution en fonction de la fonction value. J'obtiens une fonction de valeur de cette nouvelle politique mise à jour et réévalue encore une fois. De cette définition, j'ai de la difficulté à comprendre comment fonctionne l'itération de valeur et je pense que c'est à cause d'une mauvaise compréhension de ce qu'est une fonction de valeur.

Est-ce qu'une fonction de valeur n'est pas la meilleure des actions, c'est juste un cours d'actions qui déterminera une récompense? L'itération de politique recherche-t-elle simplement une fonction de valeur qui offre une récompense plus élevée que sa récompense actuelle et qui se met immédiatement à jour, ce qui donne une nouvelle distribution d'actions pour mes états (une nouvelle politique) et itérativement ?

Dans ce cas, l'itération de valeur recherche-t-elle la meilleure action possible à chaque état de la séquence (par opposition à un qui est juste meilleur)? Je me bats ici pour comprendre pourquoi un ne serait pas mettre à jour la politique?

Est-ce que ma compréhension de la politique et de la fonction de valeur, etc., est correcte?

Merci beaucoup!

Je pense que ma compréhension de la politique est certainement incorrecte: Si une politique est simplement une distribution sur toutes les actions possibles pour mes états alors je ne suis pas entièrement sûr de ce que cela veut dire "mise à jour". Si c'est simplement la mise à jour de la distribution, alors comment fonctionne exactement l'itération de valeur si elle fonctionne avec une distribution "pire" puisque la politique n'est-elle pas initialement aléatoire lorsqu'elle est initialisée? Je ne peux pas comprendre comment ceux-ci convergeraient et seraient également bons?

Answer 1

Edit: Wikipédia explique tout cela très bien https://en.wikipedia.org/wiki/Markov_decision_process#Value_iteration

Sutton a aussi un grand ressources sur ce sujet qui expliquent mieux que ci-dessous ainsi:

http://incompleteideas.net/sutton/book/ebook/node34.html 
http://incompleteideas.net/sutton/book/ebook/node43.html 
http://incompleteideas.net/sutton/book/ebook/node44.html 

Je ne peux pas vraiment dire par la formulation, mais je pense que vous avez mélangé la fonction de valeur et la politique.

La fonction valeur vous donne la valeur à chaque état. Avec l'équation de bellman, ça ressemble à ça.

V(S) = max_a[R(s,a) + gamma * ∑_s'T(s,a,s')V(s')]

Lorsque la valeur à un état particulier est l'action max qui vous donne la récompense, plus la récompense à prix réduit. Notez qu'il a un max au lieu de argmax. C'est parce qu'il vous donne la valeur. D'autre part, la politique est l'argmax de la récompense escomptée attendue compte tenu de la politique. La stratégie renvoie la meilleure action, tandis que la fonction value donne la valeur d'un état. la fonction politique ressemble à:

optimal_policy(s) = argmax_a ∑_s'T(s,a,s')V(s')

La politique optimale va vers l'action qui produit la plus grande valeur, comme vous pouvez le voir avec l'arg.

Avec cela à l'esprit, l'itération de la valeur commencerait par un utilitaire initial pour chaque état, puis exécutez:

V_t+1(s) = R(s) + gamma * max_a (∑_s'T(s,a,s')V_t(s'))

Où t est le timestep, et l est le prochain état possible. Cela convergera parce que la récompense est la «vérité» de l'État, nous tirant dans la bonne direction. Il y a des théorèmes qui le prouvent, mais cela dépasse le cadre de la question.

itération de la politique d'autre part ressemble à ceci:

optimal_policy_t+1(s) = argmax_a (∑_s' T(s,a,s')V_t(s'))

où est l'ensemble des actions possibles et V_t est la valeur. Mise à jour de la valeur ressemble à quelque chose comme:

V_t+1(s) = R(s) + gamma * max_a(∑_s' T(s,policy_t(s),s')V_t(s')

depuis que la politique représente la meilleure action à cette étape de temps. L'exécution de l'itération de stratégie est O (N^3).

Answer 2

Vous avez une politique, qui est effectivement une distribution de probabilité d'actions pour tous mes états.

Oui

Une fonction de valeur détermine la meilleure des actions pour atteindre la plus haute récompense.

Non Une fonction de valeur indique, pour une politique donnée, ce que la récompense cumulée attendue de prendre des mesures dans l'état as est. Oubliez l'itération de la valeur et l'itération des règles pour un instant.

Les deux choses que vous devriez essayer de comprendre sont l'évaluation des politiques et l'amélioration des politiques.

• Dans l'évaluation des politiques, vous figure la fonction de la valeur de l'Etat pour une politique donnée (qui vous indique votre récompense cumulative prévue pour être dans un état et d'agir conformément à la politique par la suite). Pour chaque état, vous regardez tous les états voisins et calculez la valeur attendue de la politique dans cet état (somme pondérée des valeurs des voisins par les probabilités de politique). Vous devez traverser tous les états faisant cela encore et encore. Cela converge dans la limite de la vraie fonction de valeur d'état pour cette politique (en pratique, vous arrêtez quand les changements deviennent petits). Dans l'amélioration de politique, vous examinez une fonction de valeur d'état et demandez, dans chaque état, quelle est la meilleure action que je pourrais prendre selon la fonction de valeur? L'action que la politique actuelle prend peut ne pas conduire au voisin de valeur la plus élevée. Si ce n'est pas le cas, nous pouvons trivialement faire une meilleure politique en agissant de manière à atteindre un meilleur voisin. La nouvelle politique qui en résulte est meilleure (ou pire, la même chose).

L'itération de politique est juste l'évaluation répétée de politique et l'amélioration de politique.

En itération de valeur, vous tronquez l'étape d'évaluation.Ainsi, au lieu de suivre le processus d'évaluation complet vers la convergence, vous effectuez une étape de recherche des états voisins, et au lieu de prendre une attente dans la stratégie, vous améliorez immédiatement la stratégie en stockant la valeur maximale voisine. L'évaluation et l'amélioration sont brouillées ensemble. Vous répétez cette étape tachée encore et encore, jusqu'à ce que le changement dans les valeurs est très faible. L'idée principale de pourquoi cette convergence est la même; vous évaluez la politique, puis vous l'améliorez jusqu'à ce qu'elle ne puisse plus être améliorée.

Il existe plusieurs façons de comprendre la stratégie et l'itération des valeurs. Vous pouvez en savoir plus sur cette évaluation et sur l'amélioration de l'encadrement au Apprentissage par renforcement: Introduction 2e éd. J'ai omis certains détails importants sur l'actualisation, mais j'espère que l'image globale est plus claire maintenant.