Semi-gradient TD (0) Choix d'une action

Question

Je suis en train d'écrire un agent de contrôle optimal pour un jeu simple qui ressemble à ceci:

L'agent ne peut se déplacer le long de l'axe x, et a trois actions dont elle dispose: à gauche, à droite, et ne rien faire. Un nombre aléatoire de chutes de pierres sont donné naissance à des positions arbitraires le long de la rangée supérieure. Le but est de survivre le plus longtemps possible en évitant une collision sur chaque pas de temps.

Voici ce que je l'ai fait jusqu'à présent:

1) J'utilise un vecteur caractéristique $ F $ avec F_0 $ (s) $ étant le courant coordonnée x de l'agent et F_1 $ (s) ... F_n (s) $ prise sur 0 ou 1 ( 1 indiquant la présence d'une roche).

2) est initialisé de $ du vecteur poids correspondant $ à 0 pour tous les poids. J'ai donc l'approximation de fonction linéaire $$ \ hat v (s, ?) = \ {sum_ i = 0} ^ nF_i (s) ?_i $$

3) La récompense sur chaque pas de temps est égal à 1, et 0 en cas de collision.

Je suis en train de mettre en œuvre effectivement l'algorithme ci-dessous de Sutton et 2017 projet de Barto .

---

Semi-gradient TD (0) pour estimer $ \ hat {v} \ environ v _ {\ pi} $

Entrée: $ la politique {\ pi} $ à évaluer
Entrée: une fonction dérivable $ \ hat {v}: \ mathbf {S ^ +} \ times de la mathbb {R} ^ n \ rightarrow \ mathbb {R} $ tel que $ \ hat {v} (borne, ·) = 0 $
Initialiser poids valeur à fonction $ \ theta $ arbitrairement (par exemple, $ \ theta = 0 $)
Répétez (pour chaque épisode):
$ \ Qquad $ Initialiser $ S $
$ \ Qquad $ Répétez (pour chaque étape de l'épisode):
$ \ Qquad \ qquad $ Choisissez $ A \ sim \ pi (· | S) \ qquad $ # Je ne sais pas comment choisir l'action ici $ \ Qquad \ qquad $ Prendre des mesures $ A $, $ R observer, S '$
$ \ Qquad \ qquad \ theta \ leftarrow \ theta + \ alpha [R + \ gamma \ hat {v} (S », \ theta) - \ hat {v} (S, \ theta)] \ nabla \ hat {v } (S, \ theta) $
$ \ Qquad \ qquad S \ leftarrow S '$
$ \ Qquad $ jusqu'à $ S '$ est borne

---

Mon problème est le suivant:

1) Est-ce même un algorithme approprié d'appliquer à ce genre de tâche? Il se sent comme une approche de gradient de politique serait plus approprié.

2) Si oui à 1), comment choisir une action Dans l'algorithme ci-dessus, cela apparaît comme? "Choisissez $ A \ sim \ pi (· | S) $" Depuis la la politique est implicite, je calcule la valeur approximative de l'état comme indiqué dans 2) ci-dessus, puis greedify au cours des trois actions (pas e-avide, cependant), mais la seule chose qui change est F_0 $ (s) $. Je suis certainement manque quelque chose.

Answer 1

1) Est-ce même un algorithme approprié d'appliquer à ce genre de tâche?

Non, vous avez sélectionné un algorithme d'évaluation du chapitre 9 du livre. Aucun des algorithmes dans le chapitre 9 sont des algorithmes de contrôle. Ils sont tous conçus pour estimer la fonction de la valeur d'une politique fournie en entrée. Les algorithmes de contrôle correspondants sont décrits dans le chapitre 10.

Le projet actuel du livre ne donne pas l'algorithme de contrôle TD (0) correspondant à l'estimateur linéaire. Cependant, cet algorithme existe et peut être adaptée (avec des réserves). En fait, dans votre cas, il pourrait même avoir des avantages par rapport aux méthodes basées sur la valeur de l'action, parce que vous réduisez la portée des estimations requises par un facteur de 3. Ceci est quelque chose que vous pouvez profiter de seulement si vous avez un modèle complet de l'environnement , peut donc regarder en avant un pas de temps pour déterminer la meilleure action. Sans un modèle de l'environnement, ou si vous ne voulez pas utiliser le modèle dans votre agent, vous devez utiliser une valeur d'action algorithme basé comme Monte Carlo, SARSA ou Q apprentissage.

2) Si oui à 1), comment choisir une action?

Eh bien, il était un non, mais vous pouvez utiliser la version de contrôle de TD (0). Ensuite, vous avez le problème de l'utilisation de votre fonction de valeur d'état de comprendre la politique. La règle ici est que pour utiliser les valeurs d'état, vous devez utiliser un modèle de l'environnement. Plus précisément, vous devez être en mesure de prédire le prochain Etat et récompense immédiate étant donné l'état actuel et de l'action. Dans le livre, ce qui est généralement représenté par la fonction de transition $ p (s ', r | s, a) $, ce qui donne la probabilité de chaque Etat successeur possible et récompense. Dans un jeu totalement déterministe, la probabilité est juste 1,0 pour un état cible et la récompense due à chaque action. Dans votre cas, vous avez de nouvelles roches qui apparaissent au hasard en haut. Pour être complet, vous auriez probablement de modéliser en détail (ce qui serait très lent). Cependant, étant donné l'influence très faible de cette rangée du haut, et la façon dont peu de planification de l'agent peut faire pour y faire face, je serais tenté de tout l'échantillon, il.

En supposant que vous voulez choisir l'action gourmande, alors vous pouvez trouver une politique en prenant $ argmax_a $ au cours de la prochaine étape. Lorsque vous avez une fonction de valeur d'état, alors vous devez exécuter le pas en avant dans la simulation pour comprendre l'attente sur chaque action. Ceci est le même calcul pour la politique avide utilisée dans la programmation dynamique (retour au chapitre 4 du livre):

$ \ pi (s) = argmax_a \ sum_ {s '} p (l', r | s, a) (r + \ gamma \ hat {v} (s', \ theta)) $

Bien sûr, cela est beaucoup plus simple si vous avez utilisé des valeurs d'action istead (par exemple dans SARSA):

$ \ pi (s) = argmax_a \ hat {q} (s, a, \ theta) $

. . . malgré le fait que cela soit moins efficace, vous pouvez utiliser des valeurs d'action pour moins d'effort dans cette partie.

---

Une chose supplémentaire que vous êtes susceptibles d'avoir des problèmes avec: Votre choix de la représentation de l'Etat n'a pas une bonne relation linéaire avec la vraie fonction de valeur. L'estimateur linéaire est assez limité dans ce qu'il peut faire. Un meilleur estimateur ici serait un réseau de neurones avec au moins une couche cachée.

Cependant, vous pouvez probablement modifier la représentation légèrement pour obtenir quelque chose qui fonctionne un peu avec un estimateur linéaire - l'astuce est d'avoir la roche partie de l'état représenté par rapport à l'agent - à-dire n'ont pas une grille de positions absolues des roches, mais faire de la grille par rapport à l'agent. De cette façon, un rocher directement au-dessus de l'agent sera toujours la même contribution à la valeur de l'état actuel, ce qui est important. Sans ce tweak, et en utilisant un approximator linéaire, votre agent n'apprendra pas un contrôle optimal, il sera plutôt apprendre une sorte de fatalisme « avec ces nombreux rochers, j'ai à peu près tout ce temps pour vivre » fonction de la valeur et probablement prendre des actions au hasard (si la répartition des roches est même pas qu'il pourrait apprendre à se déplacer à unecolonne particulière. . .)