Как я могу смоделировать проблему как MDP, если агент не следует последовательному порядку состояний?

Dec 31 2020

В моей проблеме агент не следует последовательному порядку состояний, а выбирает с помощью $\epsilon$-greedy лучшая пара (состояние, действие) из приоритетной очереди. В частности, когда мой агент переходит в состояние$s$ и открывает доступные действия $\{ a_i \}$, то оценивает каждый $(s,a)$пара (регрессия с DQN) и сохраняет ее в очереди. Чтобы мой агент перешел в состояние$s'$, он выбирает лучшую пару из очереди вместо того, чтобы следовать одному из доступных действий $\{ a_i \}$ из $s$. Замечу, что в одном состоянии набор действий частично отличается от других.

Однако, таким образом, как я могу смоделировать свой MDP, если мой агент не следует последовательному порядку состояний?

В частности, у меня есть специализированный поисковый робот, который вводит несколько URL-адресов семян. Я хочу вывести как можно больше релевантных URL-адресов с семенами. Я моделирую структуру RL следующим образом.

  • Состояние: веб-страница,
  • Действия: URL-адреса исходящих ссылок государственной веб-страницы,
  • Награда: из внешнего источника я знаю, актуально ли содержимое веб-страницы.

Проблема в том, что во время сканирования, если агент продолжает движение вперед, следуя последовательному переходу состояния, он может попасть в ловушки сканирования или локальные оптимумы. Это причина того, почему приоритетная очередь используется при сканировании. Агент сканирования больше не следует последовательному порядку смены состояний. Каждая пара состояние-действие добавляется в очередь приоритетов со своим предполагаемым значением действия. Каждый раз он выбирает наиболее многообещающую пару состояние-действие среди всех пар в очереди. Замечу, что каждое действие URL можно оценить с учетом состояния веб-страницы, на которой оно было извлечено.

Ответы

1 FedericoMalerba Jan 03 2021 at 15:38

Основная проблема заключается в том, что вы не понимаете, что такое состояние и действия в этой настройке. Веб-страницы - это не ваши состояния; ваше состояние - это вся приоритетная очередь (website-outlink)пар + (new_website-outlink)пары. Ваше действие - это то, какую пару вы выбираете.

Теперь это проблема пространства состояний переменного размера и пространства действий переменного размера одновременно. Чтобы справиться с этим давайте начнем, отметив , что state==observationнеобходимо не быть (в целом). Итак, каковы ваши наблюдения? Ваше наблюдение представляет собой пакет переменного размера:

  1. (website-outlink)пары или
  2. next_website(где каждый next_websiteопределяется соответствующей парой)

Оба эти наблюдения могут работать нормально, выбор между тем или другим - это просто вопрос того, хотите ли вы, чтобы ваш агент узнал, «какие ссылки открывать перед их открытием» или «какие ссылки имеют значение (после их открытия)».

По сути, ваша приоритетная очередь просто добавляет изящный трюк, который:

  • Сохраняет вычислительную сложность сохранения упорядоченного состояния (помните, что ваше состояние не a website, а список / партия website-outlink)
  • Избегает ненужного пересчета Q-значений для каждого из ваших действий (помните, что действие не выбирает исходящую ссылку из new_website, а выбирает исходящую ссылку из всех доступных вариантов в очереди)

Обратите внимание, однако, что для второго сохранения важно сохранить Q-значения для каждой пары !!!

Последнее важное замечание: в сценарии, где вы используете буфер воспроизведения (что, я думаю, вероятно, учитывая, что вы выбрали DQN), вы не можете использовать приоритетную очередь во время обучения из RB. Чтобы понять, почему (и подробно рассмотреть, как на самом деле выглядит ваш процесс обучения), начните с запоминания того, что ваши обновления Q-значения задаются формулой здесь ; ваше состояние s_t- это (квазиупорядоченная 1 ) партия пар. Q(s_t, a_t)это просто результат выполнения вашей регрессии DQN только на лучшем веб-сайте / паре в этом пакете (у вас естьдля добавления индекса для обозначения наилучшего выбора при добавлении переходов в RB, чтобы быть последовательным в отношении того, какое действие было предпринято из этого состояния). Однако, чтобы вычислить оценку оптимального будущего значения, вам придется пересчитать Q-значение каждого отдельного веб-сайта / пары в следующем состоянии. НЕЛЬЗЯ использовать приоритетную очередь при обучении из РБ.

1 У вас есть приоритетная очередь, упорядоченная для всех веб-сайтов, которые у вас были, когда вы просматривали последний веб-сайт, но все new_website-outlinkпары, которые вы сейчас добавляете, еще не упорядочены. Вам все равно нужно запустить на них агент, а затем вы можете заказать их вместе с остальной частью очереди приоритетов для генерации следующего состояния (которое все равно не будет упорядочено, потому что у вас будут new_new_website-outinkпары).