Jak mogę modelować problem jako MDP, jeśli agent nie przestrzega kolejnej kolejności stanów?

Dec 31 2020

W moim problemie agent nie śledzi kolejnej kolejności stanów, ale dokonuje selekcji $\epsilon$-greedy najlepsza para (stan, akcja) z kolejki priorytetowej. Dokładniej, kiedy mój agent przechodzi do stanu$s$ i otwiera dostępne akcje $\{ a_i \}$, a następnie szacuje każdy $(s,a)$sparować (regresja z DQN) i zapisuje go w kolejce. Aby mój agent zmienił stan$s'$, wybiera najlepszą parę z kolejki zamiast wykonywać jedną z dostępnych akcji $\{ a_i \}$ z $s$. Zauważam, że stan ma częściowo inny zestaw działań niż pozostałe.

Jednak w ten sposób, jak mogę modelować mój MDP, jeśli mój agent nie przestrzega kolejnej kolejności stanów?

Mówiąc dokładniej, mam wyspecjalizowanego robota indeksującego, który wprowadza kilka początkowych adresów URL. Chcę wyświetlić jak najwięcej odpowiednich adresów URL z nasionami. Modeluję strukturę RL w następujący sposób.

  • Stan: strona internetowa,
  • Działania: adresy URL linków wychodzących strony internetowej państwa,
  • Nagroda: ze źródła zewnętrznego wiem, czy treść strony jest odpowiednia.

Problem polega na tym, że jeśli podczas indeksowania agent będzie kontynuował działanie, podążając za kolejnymi zmianami stanu, może wpaść w pułapki indeksujące lub lokalne optymalizacje. To jest powód, dla którego kolejka priorytetowa jest tak ważna podczas indeksowania. Agent przeszukiwania nie śledzi już kolejnej kolejności przejść stanów. Każda para stan-akcja jest dodawana do kolejki priorytetów wraz z szacowaną wartością akcji. Za każdym razem wybiera najbardziej obiecującą parę stan-akcja spośród wszystkich par w kolejce. Zwracam uwagę, że każdą akcję adresu URL można oszacować biorąc pod uwagę stan strony internetowej, z której została wyodrębniona.

Odpowiedzi

1 FedericoMalerba Jan 03 2021 at 15:38

Twój podstawowy problem polega na tym, że mylisz stan i działania w tym otoczeniu. Strony internetowe nie są Twoimi stanami; Twój stan to cała priorytetowa kolejka (website-outlink)par + (new_website-outlink)pary. Twoim działaniem jest wybrana przez Ciebie para.

Jest to równoczesne ustawienie problemu przestrzeni stanów o zmiennej wielkości i przestrzeni działań o zmiennej wielkości. Aby sobie z tym poradzić, zacznijmy od zauważenia, że niestate==observation musi tak być (ogólnie). Więc jaka jest twoja obserwacja? Twoja obserwacja to zbiór o zmiennej wielkości:

  1. (website-outlink)pary lub
  2. next_website(gdzie każdy next_websitejest określony przez odpowiednią parę)

Obie te obserwacje mogą działać dobrze, wybór między jednym a drugim jest tylko kwestią tego, czy chcesz, aby agent dowiedział się, „które linki otworzyć przed ich otwarciem”, czy też „które linki mają znaczenie (po ich otwarciu)”.

To, co zasadniczo robi twoja kolejka priorytetowa, to po prostu dodanie zgrabnej sztuczki, która:

  • Zapisuje złożoność obliczeniową związaną z utrzymywaniem porządku (pamiętaj, że twój stan to nie a website, ale lista / partia website-outlink)
  • Pozwala uniknąć niepotrzebnego przeliczania wartości Q dla każdego z twoich działań (pamiętaj, że akcja nie polega na wybieraniu linku wychodzącego z new_website, ale wybieraniu linku wychodzącego ze wszystkich dostępnych opcji w kolejce)

Zwróć jednak uwagę, że aby faktycznie mieć drugą oszczędność, ważne jest, aby zapisać wartości Q dla każdej pary !!!

Ostatnią ważną rzeczą, na którą należy zwrócić uwagę, jest to, że w scenariuszu, w którym używasz bufora powtórek (co, jak sądzę, jest prawdopodobne, biorąc pod uwagę, że wybrałeś DQN), nie możesz użyć kolejki priorytetów podczas uczenia się od RB. Aby zrozumieć, dlaczego (i zobaczyć, w jaki sposób Twój proces uczenia się faktycznie wygląda), start, pamiętając, że aktualizacje Q-wartość podane są według wzoru tutaj ; twój stan s_tto (quasi-uporządkowana 1 ) partia par. Q(s_t, a_t)jest po prostu wyjście prowadzenie regresji DQN na tylko najlepszej strony / pary w tej partii (trzeba miećdodać indeks, aby wskazać najlepszy wybór podczas dodawania przejść do RB, aby być spójnym co do tego, jakie działanie zostało podjęte z tego stanu). Aby obliczyć oszacowanie optymalnej przyszłej wartości, będziesz jednak musiał ponownie obliczyć wartość Q każdej witryny / pary w następnym stanie. NIE MOŻESZ używać kolejki priorytetów podczas treningu z RB.

1 Masz kolejkę priorytetową uporządkowaną dla wszystkich stron internetowych, które miałeś w niej podczas przeglądania ostatniej witryny, ale wszystkie new_website-outlinkpary, które teraz dodajesz, nie są jeszcze uporządkowane. Nadal musisz uruchomić na nich agenta, a następnie możesz nakazać im z resztą kolejki priorytetowej wygenerowanie następnego stanu (który nadal nie zostanie zamówiony, ponieważ będziesz mieć new_new_website-outinkpary).