Come posso modellare un problema come un MDP se l'agente non segue l'ordine successivo degli stati?

Dec 31 2020

Nel mio problema, l'agente non segue l'ordine successivo degli stati, ma seleziona con $\epsilon$-Greedy la migliore coppia (stato, azione) da una coda di priorità. Più specificamente, quando il mio agente va in uno stato$s$ e apre le sue azioni disponibili $\{ a_i \}$, quindi stima ciascuno $(s,a)$pair (regressione con DQN) e la memorizza nella coda. Affinché il mio agente possa passare allo stato$s'$, seleziona la coppia migliore dalla coda invece di seguire una delle azioni disponibili $\{ a_i \}$ di $s$. Noto che uno stato ha un insieme di azioni parzialmente diverso dagli altri.

Tuttavia, in questo modo, come posso modellare il mio MDP se il mio agente non segue l'ordine successivo degli stati?

Più specificamente, ho un crawler mirato che ha un input di pochi URL seed. Voglio produrre il maggior numero possibile di URL pertinenti con i seed. Modello il framework RL come segue.

  • Stato: la pagina web,
  • Azioni: gli URL del collegamento in uscita della pagina web dello stato,
  • Ricompensa: da fonte esterna so se il contenuto della pagina web è pertinente.

Il problema è che, durante la scansione, se l'agente continua ad andare avanti seguendo la successiva transizione di stato, può cadere in trappole di scansione o ottimali locali. Questo è il motivo per cui una coda prioritaria viene utilizzata in modo importante durante la scansione. L'agente di ricerca per indicizzazione non segue più l'ordine successivo delle transizioni di stato. Ogni coppia stato-azione viene aggiunta alla coda di priorità con il suo valore di azione stimato. Per ogni volta, seleziona la coppia stato-azione più promettente tra tutte le coppie nella coda. Noto che ogni azione URL può essere stimata tenendo conto della pagina web dello stato in cui è stata estratta.

Risposte

1 FedericoMalerba Jan 03 2021 at 15:38

Fondamentalmente il tuo problema è che stai confondendo lo stato e le azioni in questo contesto. Le pagine web non sono i tuoi stati; il tuo stato è l' intera coda di priorità delle (website-outlink)coppie + le (new_website-outlink)coppie. La tua azione è quale coppia selezioni.

Ora questo è un problema di spazio di stato di dimensioni variabili e di spazio di azione di dimensioni variabili allo stesso tempo. Per far fronte a questo Iniziamo notando che state==observationnecessità di non essere (in generale). Allora qual è la tua osservazione? La tua osservazione è un batch di dimensioni variabili di:

  1. (website-outlink)coppie o
  2. next_website(dove ciascuno next_websiteè determinato dalla sua coppia corrispondente)

Entrambe queste osservazioni potrebbero funzionare bene, scegliere tra l'una o l'altra è solo questione di sapere se vuoi che il tuo agente impari "quali collegamenti aprire prima di aprirli" o "quali collegamenti sono significativi (dopo averli aperti)".

Ciò che la tua coda prioritaria sta essenzialmente facendo è semplicemente aggiungere un trucco accurato che:

  • Salva la complessità computazionale di mantenere lo stato ordinato (ricorda che il tuo stato non è a website, ma l'elenco / lotto di website-outlink)
  • Evita di ricalcolare inutilmente i valori Q per ciascuna delle tue azioni (ricorda che un'azione non è selezionare un outlink da new_website, ma selezionare un outlink da tutte le scelte disponibili nella coda)

Nota comunque che per avere effettivamente il secondo salvataggio è fondamentale memorizzare i valori Q per ogni coppia !!!

L'ultima cosa importante da notare è che in uno scenario in cui usi un Replay Buffer (che immagino sia probabilmente dato che hai scelto un DQN), non puoi usare la coda di priorità mentre impari dal RB. Per vedere perché (e per vedere in dettaglio come appare effettivamente il tuo processo di apprendimento), inizia ricordando che i tuoi aggiornamenti del valore Q sono dati dalla formula qui ; il tuo stato s_tè un lotto di coppie (quasi ordinato 1 ). Q(s_t, a_t)è solo l'uscita del esegue il regressione DQN sul solo il miglior sito web / pair in questo batch (si haiper aggiungere un indice per indicare la scelta migliore quando si aggiungono transizioni a RB, in modo da essere coerenti su quale azione è stata intrapresa da questo stato). Per calcolare la stima del valore ottimale futuro tuttavia si dovrà ricalcolare il Q-valore di ogni singolo sito / pair nello stato successivo. NON è possibile utilizzare la coda di priorità durante l'allenamento dal RB.

1 Hai la coda di priorità ordinata per tutti i siti web che avevi in ​​essa mentre guardavi l'ultimo sito web, ma tutte le new_website-outlinkcoppie che stai aggiungendo non sono ancora state ordinate. Devi ancora eseguire l'agente su di loro e poi puoi ordinarli con il resto della coda di priorità per generare lo stato successivo (che ancora non verrà ordinato perché avrai new_new_website-outinkcoppie).