Quelle est la différence entre l'itération de valeur et l'itération de politique?

Dans l'apprentissage par renforcement, quelle est la différence entre l'itération des politiques et l' itération des valeurs ?

Autant que je sache, dans l'itération de la valeur, vous utilisez l'équation de Bellman pour résoudre la politique optimale, tandis que, dans l'itération de la politique, vous sélectionnez au hasard une politique π et trouvez la récompense de cette politique.

Mon doute est que si vous sélectionnez une politique aléatoire π dans PI, comment est-elle garantie d'être la politique optimale, même si nous choisissons plusieurs politiques aléatoires.

Regardons-les côte à côte. Les éléments clés de la comparaison sont mis en évidence. Les chiffres sont tirés du livre de Sutton et Barto: Reinforcement Learning: An Introduction .

Points clés:

1. L'itération des politiques comprend: l'évaluation des politiques + l'amélioration des politiques , et les deux sont répétées de manière itérative jusqu'à ce que la politique converge.
2. L'itération de valeur comprend: la recherche d'une fonction de valeur optimale + une extraction de politique . Il n'y a pas de répétition des deux car une fois que la fonction de valeur est optimale, alors la politique en dehors de celle-ci devrait également être optimale (c'est-à-dire convergée).
3. La recherche d'une fonction de valeur optimale peut également être vue comme une combinaison d'amélioration de la politique (due à max) et d'évaluation de politique tronquée (la réaffectation de v_ (s) après un seul balayage de tous les états, indépendamment de la convergence).
4. Les algorithmes pour l'évaluation des politiques et la recherche de la fonction de valeur optimale sont très similaires, sauf pour une opération max (comme mis en évidence)
5. De même, les étapes clés de l'amélioration des politiques et de l'extraction des politiques sont identiques, sauf que la première implique un contrôle de stabilité.

D'après mon expérience, l'itération de politique est plus rapide que l' itération de valeur , car une politique converge plus rapidement qu'une fonction de valeur. Je me souviens que cela est également décrit dans le livre.

Je suppose que la confusion provenait principalement de tous ces termes quelque peu similaires, qui m'avaient également confondu auparavant.

Dans les algorithmes d' itération de stratégie , vous commencez avec une stratégie aléatoire, puis recherchez la fonction de valeur de cette stratégie (étape d'évaluation de stratégie), puis recherchez une nouvelle stratégie (améliorée) basée sur la fonction de valeur précédente, et ainsi de suite. Dans ce processus, chaque politique est garantie d'être une amélioration stricte par rapport à la précédente (à moins qu'elle ne soit déjà optimale). Étant donné une politique, sa fonction de valeur peut être obtenue à l'aide de l' opérateur Bellman .

Dans l' itération de valeur , vous commencez avec une fonction de valeur aléatoire, puis vous trouvez une nouvelle fonction de valeur (améliorée) dans un processus itératif, jusqu'à atteindre la fonction de valeur optimale. Notez que vous pouvez facilement dériver la stratégie optimale à partir de la fonction de valeur optimale. Ce processus est basé sur l' optimalité de l'opérateur Bellman .

Dans un certain sens, les deux algorithmes partagent le même principe de fonctionnement, et ils peuvent être considérés comme deux cas d' itération de politique généralisée . Cependant, l'opérateur Bellman d'optimalité contient un opérateur max , qui n'est pas linéaire et, par conséquent, il a des caractéristiques différentes. De plus, il est possible d'utiliser des méthodes hybrides entre l'itération de valeur pure et l'itération de politique pure.

La différence fondamentale est -

Dans l'itération de politique - Vous sélectionnez au hasard une politique et trouvez la fonction de valeur qui lui correspond, puis trouvez une nouvelle politique (améliorée) basée sur la fonction de valeur précédente, et ainsi de suite, cela conduira à une politique optimale.

Dans Itération de valeur - Vous sélectionnez au hasard une fonction de valeur, puis trouvez une nouvelle fonction de valeur (améliorée) dans un processus itératif, jusqu'à atteindre la fonction de valeur optimale, puis dérivez la politique optimale à partir de cette fonction de valeur optimale.

L'itération des politiques fonctionne sur le principe de «Évaluation des politiques -> Amélioration des politiques».

L'itération de valeur fonctionne sur le principe de la «fonction de valeur optimale —-> politique optimale».

En ce qui me concerne, contrairement à l'idée de @zyxue, VI est généralement beaucoup plus rapide que PI.

La raison est très simple, comme vous le saviez déjà, l'équation de Bellman est utilisée pour résoudre la fonction de valeur pour une politique donnée. Puisque nous pouvons résoudre directement la fonction de valeur pour une politique optimale , résoudre la fonction de valeur pour la politique actuelle est évidemment une perte de temps.

Quant à votre question sur la convergence de l'IP, je pense que vous pourriez ignorer le fait que si vous améliorez la stratégie pour chaque état d'information, alors vous améliorez la stratégie pour l'ensemble du jeu. Ceci est également facile à prouver, si vous étiez familier avec la minimisation contrefactuelle des regrets - la somme des regrets pour chaque état d'information a formé la limite supérieure du regret global, et ainsi minimiser le regret pour chaque état minimisera le regret global, ce qui conduit à la politique optimale.