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

Question

Dans l'apprentissage par renforcement, quelle est la différence entre la politique de l'itération et de la valeur de l'itération?

Autant que je comprends, dans la valeur de l'itération, vous utilisez le Chasseur équation à résoudre pour la politique optimale, tandis que, dans la politique de l'itération, vous choisissez au hasard une politique π, et de trouver la récompense de cette politique.

Mon doute, c'est que si vous êtes à la sélection aléatoire d'une politique π PI, comment est-il garanti la politique optimale, même si nous faisons le choix aléatoire de plusieurs politiques.

Answer 1

Examinons-les de l'autre côté. Les principaux éléments de comparaison sont mis en évidence. Les chiffres sont issus de Sutton et Barto du livre: l'Apprentissage par Renforcement: Une Introduction.

Points clés:

1. La politique de l'itération comprend: l'évaluation de la politique + amélioration de la politique, et les deux sont répétées de manière itérative jusqu'à ce que la politique de converge.
2. La valeur de l'itération comprend: trouver la valeur optimale de la fonction + une politique de l'extraction. Il n'y a pas de répétition de deux parce qu'une fois que la fonction de valeur optimale, puis la politique de il devrait également être optimale (c'est à dire convergente).
3. Trouver la valeur optimale de la fonction peut aussi être vu comme une combinaison de l'amélioration de la politique (en raison de max) et tronquée d'évaluation de la politique (la réaffectation de v_(s) après juste un balayage de tous les états, indépendamment de convergence).
4. Les algorithmes pour l'évaluation de la politique et de trouver la valeur optimale de la fonction sont très similaires, sauf pour un max de fonctionnement (comme l'a souligné)
5. De même, l'étape clé d' amélioration de la politique et de la politique de l'extraction sont identiques, sauf la première implique un contrôle de stabilité.

Dans mon expérience, le politique itération est plus rapide que la valeur de l'itération, comme une politique converge plus rapidement que la valeur de la fonction. Je me souviens de cette procédure est également décrite dans le livre.

Je suppose que la confusion est surtout venue de tous ces quelque peu les termes semblables, qui a également confondu moi avant.

Answer 2

Dans la politique de l'itération algorithmes, vous commencez avec un nombre aléatoire de la politique, puis de trouver la valeur de la fonction de cette politique (évaluation de la politique de l'étape), puis de trouver un nouveau (amélioré) de la politique fondée sur la valeur précédente de la fonction, et ainsi de suite. Dans ce processus, chaque stratégie est la garantie d'une stricte amélioration par rapport à la précédente (sauf si c'est déjà optimale). Donné un la politique, sa fonction de valeur peut être obtenue à l'aide de l' opérateur de Bellman.

Dans la valeur de l'itération, vous commencez avec une valeur aléatoire de fonction et ensuite trouver un nouveau (amélioré) de la valeur de la fonction dans un processus itératif, jusqu'à atteindre la valeur optimale de la fonction. Notez que vous pouvez tirer facilement la politique optimale à partir de la valeur optimale de la fonction. Ce processus est basé sur l' optimalité de Bellman opérateur.

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

Answer 3

Pour autant que je suis concerné, contrairement à @zyxue l'idée, VI est généralement beaucoup plus rapide que PI.

La raison en est très simple, comme vous le saviez déjà, le Groom Équation est utilisée pour la résolution de la valeur de la fonction pour une politique donnée. Depuis que nous pouvons régler la valeur de la fonction pour optimale de la politique directement, de la résolution de la valeur de la fonction de courant politique est évidemment une perte de temps.

Quant à votre question sur la convergence maximale de PI, je pense que vous avez peut négliger le fait que si vous améliorer la stratégie pour chaque information de l'état, alors vous améliorer la stratégie pour l'ensemble du jeu. C'est aussi facile de prouver que, si vous étiez familier avec Contrefactuel Regret de Minimisation -- la somme de regret pour chaque information de l'etat a formé le upperbound de l'ensemble de regret, et donc de réduire le regret de chaque état de minimiser l'ensemble des regrets, ce qui conduit à la politique optimale.