ОБЗОР МЕТОДОВ ПЕРЕИСПОЛЬЗОВАНИЯ ВЗАИМОДЕЙСТВИЙ СО СРЕДОЙ ДЛЯ УСКОРЕНИЯ СХОДИМОСТИ АЛГОРИТМОВ ОБУЧЕНИЯ С ПОДКРЕПЛЕНИЕМ

Обучение с подкреплением это раздел машинного обучения, который изучает нахождение алгоритма поведения для агентов, действующих в некоторой среде, который максимизирует некоторую заданную функцию награды.

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

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

2. В процессе обучения агент может хорошо научиться действовать в какой-то ситуации S, так как она встречалась много раз. Далее агент становится более умным и уже не попадает в эту ситуацию, а попадает в другие и учится хорошо действовать в них. При этом он может "забыть" опыт, который приобрел за многие разы, которые он оказывался в ситуации S и перестать действовать в ней должным образом.

3. Многие алгоритмы обучения с подкреплением основаны на стохастическом градиентном спуске. Для их эффективной работы требуется, чтобы данные, на основе которых совершаются шаги по градиенту были выбраны из одного распределения и не были независимы друг от друга. Если же обновлять параметры модели после каждого взаимодействия со средой, то требование независимости нарушается, так как изменения параметров на основе последовательных взаимодействий со средой часто сильно скореллированы друг с другом.

Для решения вышеописанных проблем в работе [1] предлагается механизм повторения опыта (Experience replay). Суть механизма заключается в том, что история взаимодействий агента со средой сохраняется в специальный буфер фиксированного размера. Далее для обновления параметров агента используется не самое новое его взаимодействие со средой, а выбирается случайное взаимодействие из буфера. Это не позволяет окончательно решить ни одну из трех вышеописанных проблем, но на практике позволяет значительно уменьшить влияние каждой из них. В статье [1] успешно используется experience replay вместе с q-обучением с использованием глубоких нейронных сетей.

В работе [2] предлагается дальнейшее развитие механизма experience replay в применении его к алгоритму q-обучения, которой называется prioritized experience replay. Оно заключается в том, чтобы сэмплировать взаимодействия со средой из буфера не равновероятно. Предлагается чаще выбирать те взаимодействия со средой, для которых TD-ошибка (различие между значением Q-функции, посчитанным на основе данного взаимодействия со средой, и аппроксимацией этого значения, которое на данный момент выучила модель) больше. Неформально это значит, что мы будем чаще обновлять параметры модели на тех взаимодействия, значение Q-функции для которых модель аппроксимирует неправильно.

Формально, для выбора взаимодействия из буфера, которое будет использовать для обновления параметров модели делается следующее. Для взаимодействия со средой i (взаимодействие представлено кортежем [s_i, a_i, r_i, f_i], где s_i это начальное состояние; a_i совершенное действие; r_i награда, полученная за это действие; f_i состояние, в котором агент оказался после выполнения этого действия) в буфере хранится значение TD-ошибки , посчитанное при добавлении этого взаимодействия в буфер. Стоит обратить внимание на то, что по мере изменения параметров модели величина ошибки для данного взаимодействия может изменяться, но обновлять значения этих величин для всех величин в буфере довольно затратно, поэтому в буфере хранятся не всегда актуальные значения. Взаимодействие из буфера выбирается случайно. Вероятность выбрать взаимодействие i полагается равной

где  это коэффициент, определяющий силу приоритезации. Далее рассматриваются два варианта выбора значений . В первом варианте , где  это маленькая положительная константа, прибавляемая для того, чтобы избежать деления на 0. Во втором варианте , где rank(k) это номер это ранг взаимодействия k в отсортированном по  списке элементов из буфера. Предполагается, что второй вариант должен быть более устойчивым, так как он не зависит от масштаба разницы между значениями TD-ошибки у разных взаимодействий.   После выбора случайного элемента из буфера в соответствии с вышеописанным распределением вероятностей происходит обновление параметров модели, пересчитывается TD-ошибка для данного взаимодействия и оно снова помещается в буфер. Из двух способов задания функции  при тестировании на известном бенчмарке, состоящем из игр Atari, лучше всего себя показывает первый способ.

Для эффективной реализации буфера можно использовать структуру данных дерево отрезков [3], что позволит эффективно реализовать добавление новых элементов в буфер, а также получение случайного элемента.

Список литературы:

1. Playing Atari with Deep Reinforcement Learning [Электронный ресурс] // Arxiv. – Режим доступа: https://arxiv.org/abs/1312.5602 . – Дата обращения: 01.10.2019.
2. Prioritized Experience Replay [Электронный ресурс] // Arxiv. – Режим доступа: https://arxiv.org/abs/1511.05952 . – Дата обращения: 01.10.2019.
3. Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ / Кормен, Т. и др. – М.: Вильямс, 2005 – 1296 с.