Comment puis-je modéliser un problème en tant que MDP si l'agent ne suit pas l'ordre successif des états?
Dans mon problème, l'agent ne suit pas l'ordre successif des états, mais sélectionne avec $\epsilon$-génère la meilleure paire (état, action) d'une file d'attente prioritaire. Plus précisément, lorsque mon agent entre dans un état$s$ et ouvre ses actions disponibles $\{ a_i \}$, puis il estime chaque $(s,a)$paire (régression avec DQN) et le stocke dans la file d'attente. Pour que mon agent change d'état$s'$, il sélectionne la meilleure paire de la file d'attente au lieu de suivre l'une des actions disponibles $\{ a_i \}$ de $s$. Je note qu'un état a un ensemble d'actions partiellement différent des autres.
Cependant, de cette manière, comment puis-je modéliser mon MDP si mon agent ne suit pas l'ordre successif des états?
Plus précisément, j'ai un robot d'exploration ciblé qui a une entrée de quelques URL de départ. Je souhaite générer autant d'URL pertinentes que possible avec les graines. Je modélise le cadre RL comme suit.
- État: la page Web,
- Actions: les URL de sortie de la page Web de l'état,
- Récompense: de source externe, je sais si le contenu de la page Web est pertinent.
Le problème est que, lors de l'exploration, si l'agent continue d'avancer en suivant la transition d'état successive, il peut tomber dans des pièges d'exploration ou des optima locaux. C'est la raison pour laquelle une file d'attente prioritaire est utilisée de manière importante lors de l'exploration. L'agent d'exploration ne suit plus l'ordre successif des transitions d'état. Chaque paire état-action est ajoutée à la file d'attente prioritaire avec sa valeur d'action estimée. Pour chaque fois, il sélectionne la paire état-action la plus prometteuse parmi toutes les paires de la file d'attente. Je note que chaque action d'URL peut être estimée en tenant compte de l'état de la page Web où elle a été extraite.
Réponses
Votre problème est fondamentalement que vous confondez l'état et les actions dans ce contexte. Les pages Web ne sont pas vos états; votre état est l' ensemble de la file d'attente prioritaire des (website-outlink)
paires + les (new_website-outlink)
paires. Votre action est la paire que vous sélectionnez.
Il s'agit maintenant d'un paramètre de problème d'espace d'état de taille variable et d'espace d'action de taille variable en même temps. Pour faire face à cela, commençons par noter qu'il state==observation
n'est pas nécessaire (en général). Alors, quelle est votre observation? Votre observation est un lot de taille variable de:
(website-outlink)
paires ounext_website
(où chacunnext_website
est déterminé par sa paire correspondante)
Ces deux observations pourraient très bien fonctionner, choisir entre l'une ou l'autre est juste une question de savoir si vous voulez que votre agent apprenne «quels liens ouvrir avant de les ouvrir» ou «quels liens sont significatifs (après les avoir ouverts)».
Ce que votre file d'attente prioritaire fait essentiellement, c'est simplement ajouter une astuce intéressante qui:
- Enregistre la complexité de calcul de garder l'état ordonné (rappelez-vous que votre état n'est pas un
website
, mais la liste / lot dewebsite-outlink
) - Évite de recalculer inutilement les valeurs Q pour chacune de vos actions (rappelez-vous qu'une action ne sélectionne pas un lien sortant
new_website
, mais sélectionne un lien sortant parmi tous les choix disponibles dans la file d'attente)
Notez cependant que pour avoir réellement la deuxième sauvegarde, il est crucial de stocker les valeurs Q pour chaque paire !!!
La dernière chose importante à noter est que dans un scénario où vous utilisez un tampon de relecture (ce qui, je suppose, est probable étant donné que vous avez choisi un DQN), vous ne pouvez pas utiliser la file d'attente prioritaire tout en apprenant du RB. Pour voir pourquoi (et pour voir en détail à quoi ressemble réellement votre processus d'apprentissage), commencez par vous rappeler que vos mises à jour de Q-value sont données par la formule ici ; votre état s_t
est un lot (quasi-ordonné 1 ) de paires. Q(s_t, a_t)
est juste la sortie de l' exécution de votre régression DQN sur tout le meilleur site / paire dans ce lot (vous avezpour ajouter un index pour désigner le meilleur choix lors de l'ajout de transitions au RB, afin d'être cohérent sur l'action entreprise à partir de cet état). Pour calculer l'estimation de la valeur future optimale mais vous devez recalculer la valeur Q de chaque site / paire dans l'état suivant. Vous NE POUVEZ PAS utiliser la file d'attente prioritaire lors de l'entraînement à partir du RB.
1 Vous avez la file d'attente prioritaire commandée pour tous les sites Web que vous aviez en regardant le dernier site Web, mais toutes les new_website-outlink
paires que vous ajoutez maintenant ne sont pas encore commandées. Vous devez toujours exécuter l'agent sur eux, puis vous pouvez les commander avec le reste de la file d'attente prioritaire pour générer l'état suivant (qui ne sera toujours pas ordonné car vous aurez des new_new_website-outink
paires).