Wie kann ich ein Problem als MDP modellieren, wenn der Agent nicht der Reihenfolge der Zustände folgt?
In meinem Problem folgt der Agent nicht der aufeinanderfolgenden Reihenfolge der Zustände, sondern wählt mit aus $\epsilon$-Geed das beste Paar (Status, Aktion) aus einer Prioritätswarteschlange. Genauer gesagt, wenn mein Agent in einen Staat geht$s$ und öffnet die verfügbaren Aktionen $\{ a_i \}$, dann schätzt es jeden $(s,a)$Paar (Regression mit DQN) und speichert es in der Warteschlange. Damit mein Agent in den Status wechselt$s'$wählt das beste Paar aus der Warteschlange aus, anstatt einer der verfügbaren Aktionen zu folgen $\{ a_i \}$ von $s$. Ich stelle fest, dass ein Staat eine teilweise andere Aktion hat als die anderen.
Wie kann ich jedoch auf diese Weise mein MDP modellieren, wenn mein Agent nicht der Reihenfolge der Zustände folgt?
Insbesondere habe ich einen fokussierten Crawler, der einige Start-URLs eingibt. Ich möchte so viele relevante URLs wie möglich mit den Seeds ausgeben. Ich modelliere das RL-Framework wie folgt.
- Zustand: die Webseite,
- Aktionen: die Outlink-URLs der staatlichen Webseite,
- Belohnung: Aus externer Quelle weiß ich, ob der Inhalt der Webseite relevant ist.
Das Problem besteht darin, dass der Agent beim Crawlen, wenn er den sukzessiven Statusübergang weiter verfolgt, in Crawler-Traps oder lokale Optima fallen kann. Dies ist der Grund, warum eine Prioritätswarteschlange beim Crawlen wichtig ist. Der Crawler folgt nicht mehr der aufeinanderfolgenden Reihenfolge der Zustandsübergänge. Jedes Status-Aktions-Paar wird mit seinem geschätzten Aktionswert zur Prioritätswarteschlange hinzugefügt. Für jedes Mal wird das vielversprechendste Status-Aktions-Paar unter allen Paaren in der Warteschlange ausgewählt. Ich stelle fest, dass jede URL-Aktion unter Berücksichtigung der Status-Webseite, auf der sie extrahiert wurde, geschätzt werden kann.
Antworten
Ihr Problem besteht im Wesentlichen darin, dass Sie den Status und die Aktionen in dieser Einstellung verwirren. Webseiten sind nicht Ihre Staaten; Ihr Status ist die gesamte Prioritätswarteschlange von (website-outlink)
Paaren + den (new_website-outlink)
Paaren. Ihre Aktion ist, welches Paar Sie auswählen.
Dies ist nun eine Problemeinstellung für den Zustandsraum mit variabler Größe und den Aktionsraum mit variabler Größe gleichzeitig. Um damit umzugehen, stellen wir zunächst fest, state==observation
dass dies (im Allgemeinen) nicht erforderlich ist . Was ist Ihre Beobachtung? Ihre Beobachtung ist eine Charge mit variabler Größe von entweder:
(website-outlink)
Paare odernext_website
(wobei jedesnext_website
durch sein entsprechendes Paar bestimmt wird)
Diese beiden Beobachtungen könnten gut funktionieren. Die Wahl zwischen den beiden Beobachtungen hängt nur davon ab, ob Ihr Agent erfahren soll, "welche Links vor dem Öffnen geöffnet werden sollen" oder "welche Links sinnvoll sind (nach dem Öffnen)".
Was Ihre Prioritätswarteschlange im Wesentlichen tut, ist nur einen ordentlichen Trick hinzuzufügen, der:
- Spart die rechnerische Komplexität
website
, wenn der Status geordnet bleibt (denken Sie daran, dass Ihr Status kein Status ist , sondern die Liste / Charge vonwebsite-outlink
). - Vermeidet die unnötige Neuberechnung der Q-Werte für jede Ihrer Aktionen (denken Sie daran, dass eine Aktion keinen Gliederungslink
new_website
auswählt, sondern einen Gliederungspunkt aus allen verfügbaren Auswahlmöglichkeiten in der Warteschlange auswählt).
Beachten Sie jedoch, dass es für die zweite Speicherung wichtig ist, die Q-Werte für jedes Paar zu speichern !!!
Als letztes ist zu beachten, dass Sie in einem Szenario, in dem Sie einen Wiederholungspuffer verwenden (was wahrscheinlich davon ausgeht, dass Sie einen DQN ausgewählt haben), die Prioritätswarteschlange nicht verwenden können, während Sie vom RB lernen. Um zu sehen, warum (und um detailliert zu sehen, wie Ihr Lernprozess tatsächlich aussieht), denken Sie zunächst daran, dass Ihre Q-Wert-Aktualisierungen durch die Formel hier angegeben werden . Ihr Bundesstaat s_t
ist eine (quasi geordnete 1 ) Charge von Paaren. Q(s_t, a_t)
ist nur der Ausgang Ihrer DQN Regression läuft gerade die beste Website / pair in dieser Charge (Sie habenHinzufügen eines Index, um die beste Wahl beim Hinzufügen von Übergängen zum RB zu kennzeichnen, um konsistent zu sein, welche Aktion aus diesem Zustand heraus ergriffen wurde). Um die Schätzung des optimalen zukünftigen Werts zu berechnen, müssen Sie jedoch den Q-Wert jeder einzelnen Website / jedes einzelnen Paares im nächsten Status neu berechnen. Sie können die Prioritätswarteschlange NICHT verwenden, wenn Sie vom RB aus trainieren.
1 Sie haben die Prioritätswarteschlange für alle Websites bestellt, die Sie beim Betrachten der letzten Website darin hatten, aber alle new_website-outlink
Paare, die Sie jetzt hinzufügen, sind noch nicht bestellt. Sie müssen den Agenten noch auf ihnen ausführen und können sie dann mit dem Rest der Prioritätswarteschlange bestellen, um den nächsten Status zu generieren (der immer noch nicht bestellt wird, weil Sie new_new_website-outink
Paare haben).