Внедрение САРСА

Question

Я узнал о реализации алгоритма SARSA и у меня возник вопрос. Я понимаю, что общий этап "обучения" принимает форму:

Робот (r) находится в состоянии s. Доступны четыре действия:

North (n), East (e), West (w) and South (s)

такой, что список действий,

a = {n,w,e,s}

Робот случайным образом выбирает действие и обновляет его следующим образом:

Q(a,s) = Q(a,s) + L[r + DQ(a',s1) - Q(a,s)]

куда L скорость обучения, r это награда, связанная с (a,s), Q(s',a') ожидаемая награда от действия a' в новом состоянии s' а также D коэффициент дисконтирования

Во-первых, я не понимаю роль термина - Q(a,s)Почему мы повторно вычитаем текущее значение Q?

Во-вторых, при выборе действий a а также a' почему они должны быть случайными? Я знаю, в некоторых реализациях или SARSA все возможно Q(s', a') учитываются и выбирается самое высокое значение. (Я полагаю, что это Эпсилон-Жадный?) Почему бы и не выбрать Q(a,s) значение для обновления? Или почему бы не обновить все Q(a,s) для текущего s?

Наконец, почему SARSA ограничивается одним шагом вперед? Почему, скажем, не заглянуть в гипотетический Q(s'',a'')?

Я полагаю, что в целом мои вопросы сводятся к тому, что делает SARSA лучше, чем другой алгоритм поиска, основанный на дыхании или глубине?

Answer 1

Почему мы вычитаем Q(a,s)? r + DQ(a',s1) это награда, которую мы получили на этом пробеге от получения до государства s предпринимая действия a, В теории это значение, которое Q(a,s) должен быть установлен в. Однако мы не всегда будем предпринимать одно и то же действие после перехода к состоянию s из действия. a и награды, связанные с переходом в будущие штаты, изменятся в будущем. Так что мы не можем просто установить Q(a,s) равно r + DQ(a',s1), Вместо этого мы просто хотим подтолкнуть его в правильном направлении, чтобы оно в конечном итоге сходилось на правильном значении. Итак, мы смотрим на ошибку в прогнозировании, которая требует вычитания Q(a,s) от r + DQ(a',s1) , Это сумма, которую нам нужно изменить Q(a,s) для того, чтобы он идеально соответствовал награде, которую мы только что наблюдали. Поскольку мы не хотим делать это все сразу (мы не знаем, всегда ли это будет лучшим вариантом), мы умножаем этот коэффициент ошибки на скорость обучения, l и добавьте это значение к Q(a,s) для более постепенного сближения по правильному значению.

Почему мы выбираем действия случайно? Причина, по которой мы не всегда выбираем следующее состояние или действие детерминированным способом, заключается в том, что наше предположение о том, какое состояние лучше, может быть неверным. Когда мы впервые запускаем SARSA, у нас есть таблица, полная 0. Мы помещаем ненулевые значения в таблицу, исследуя эти области пространства состояний и обнаруживая, что с ними связаны награды. В результате, что-то не страшное, что мы исследовали, будет выглядеть лучше, чем то, что мы не исследовали. Может быть это. Но, возможно, то, что мы еще не исследовали, на самом деле намного лучше, чем мы уже видели. Это называется проблемой исследования против эксплуатации - если мы просто продолжаем делать то, что мы знаем, как работать, мы никогда не найдем наилучшего решения. Выбор следующих шагов случайным образом гарантирует, что мы увидим больше наших вариантов.

Почему мы не можем просто предпринять все возможные действия из данного состояния? Это заставит нас в основном просматривать всю таблицу обучения на каждой итерации. Если для решения проблемы мы используем что-то вроде SARSA, таблица, вероятно, слишком велика, чтобы сделать это за разумное время.

Почему SARSA может сделать только один шаг вперед? Хороший вопрос. Идея SARSA заключается в том, что она распространяет ожидаемые награды в обратном направлении через таблицу. Коэффициент дисконтирования D гарантирует, что в конечном решении вы будете постепенно увеличивать ожидаемое вознаграждение, ведущее к лучшему вознаграждению. Если вы заполнили таблицу наугад, это не всегда будет правдой. Это не обязательно нарушает алгоритм, но я подозреваю, что это приводит к неэффективности.

Почему САРСА лучше, чем поиск? Опять же, это сводится к эффективности вещи. Основная причина того, что кто-то использует алгоритмы обучения, а не алгоритмы поиска, заключается в том, что алгоритмы поиска слишком медленные, когда у вас слишком много вариантов состояний и действий. Чтобы узнать, какое наилучшее действие следует предпринять из любой другой пары действий состояния (что и рассчитывает SARSA), вам необходимо выполнить поиск по всему графику по каждому узлу. Это займет O(s*(s+a)) время. Если вы пытаетесь решить реальные проблемы, это обычно слишком долго.