Введение в понимание двойного Q-Learning
Q-обучение (Watkins, 1989) считается одним из прорывов в алгоритме обучения с подкреплением управления TD.
Однако в своей статье Двойное Q-Learning Хадо ван Хасселт объясняет, почему Q-Learning очень плохо работает в некоторых стохастических средах. Он указал, что низкая производительность вызвана большим переоценкой значений действий из-за использования Max Q (s ’, a) в Q-обучении.
Чтобы решить эту проблему, он предложил метод двойного Q-обучения.
Эта проблема
Рассмотрим MDP, имеющий четыре состояния, два из которых являются конечными.
Состояние A всегда считается начальным и имеет два действия: Right или Left. Действие «Вправо» дает нулевое вознаграждение и переходит в конечное состояние C.
Действие «Влево» перемещает агента в состояние B с нулевым вознаграждением.
Состояние B имеет ряд действий, они переводят агента в конечное состояние D. Однако (это важно) награда R за каждое действие от B до D имеет случайное значение, которое следует нормальному распределению со средним значением -0,5. и отклонение 1,0.
Ожидаемое значение R, как известно, отрицательное (-0,5). Это означает, что в большом количестве экспериментов среднее значение R меньше нуля.
Исходя из этого предположения, ясно, что двигаться влево от точки А - всегда плохая идея. Однако, поскольку некоторые значения R положительны, Q-Learning будет обманут, чтобы считать, что перемещение влево от A максимизирует вознаграждение. На самом деле это плохое решение, потому что даже если оно сработает для некоторых эпизодов, в долгосрочной перспективе это гарантированно будет отрицательной наградой.
Так почему же Q-Learning завышает оценку?
Чтобы ответить на этот вопрос, мы рассмотрим следующий сценарий:
Пусть X1 и X2 - две случайные величины, которые представляют собой награду за два действия в состоянии B. Поскольку они являются случайными величинами. , мы вычислим их ожидаемые значения E (X1) и E (X2). Однако существует проблема: мы не знаем их ожидаемых значений, поэтому мы можем использовать оценки этих ожидаемых значений, вычисляя инкрементное среднее 1 и 2. Эти оценки несмещены, потому что по мере увеличения количества выборок среднее значение по всему набору значений приближается к E (X1) и E (X2), как показано в таблице ниже.
Однако Q-Learning использует Max Q (s ’, a), представленный в таблице как Max (𝝁). Из таблицы (см. Красные ячейки) ясно видно, что E (Max (𝝁)) отличается от Max E (X). Это говорит о том, что Max (𝝁) не является хорошей оценкой для Max E (X). Это предвзято!
Другими словами, при обновлении Q (s, a) с помощью Max Q (s ', a), Q (s, a) не приближается к ожидаемому значению действий в состоянии B, которое составляет -0,5.
Этот сценарий дает интуитивное представление о том, почему Q-Learning переоценивает значения. Формальную математическую демонстрацию можно найти в статье.
Решение
Предлагаемое решение состоит в том, чтобы поддерживать две функции Q-значения QA и QB, каждая из которых получает обновление от другой для следующего состояния.
Обновление состоит из поиска действия a *, которое максимизирует QA в следующем состоянии (Q ( s ', a *) = Max Q (s', a)), затем используйте *, чтобы получить значение QB (s ', a *), чтобы обновить QA (s, a).
Приведенный ниже псевдокод показывает, как ведет себя алгоритм. Обратите внимание, что в конце статьи есть код Python, в котором сравниваются два метода.
Строка 3 алгоритма показывает, как выбрать действие из двух функций Q-значения. Например, можно объединить два Q (усреднить значения для каждого действия), а затем применить epsilon-greedy.
Алгоритм обновляет как QA, так и QB равновероятным образом.
На диаграммах ниже показано сравнение двойного Q-обучения и Q-обучения, когда количество действий в состоянии B равно 10 и 100 последовательно.
Очевидно, что двойное Q-обучение сходится быстрее, чем Q-обучение. < br /> Обратите внимание, что когда количество действий в B увеличивается, Q-обучение требует гораздо большего обучения, чем Double Q-Learning.
Почему это работает?
Ван Хасселт доказывает в своей статье, что E (Q2 (s ', a *)) ≤ Max Q1 (s', a *).
Таким образом, после достаточного количества экспериментов ожидаемое значение Q2 (s ', a *) ) меньше или равно Max Q1 (s ', a *), что означает, что Q1 (s, a) не обновляется с максимальным значением.
В таблице ниже показана эволюция Q-значений действия Left в состоянии A по мере увеличения количества эпизодов.
Обратите внимание, что в Q-Learning Q (A, Left) является положительным, потому что на него влияет положительные награды, которые существуют в состоянии B. Из-за этого положительного значения алгоритм больше заинтересован в выполнении левого действия в надежде максимизировать вознаграждение. Как вы можете видеть, процент левого действия продолжает увеличиваться до 50-го эпизода.
В Double Q-Learning Q1 (A, левый) и Q2 (A, левый) начинаются слегка отрицательными.
В результате процентное соотношение левого действия начинает уменьшаться очень рано, что экономит время обучения.
Заключение
В документе показано, что двойное Q-обучение может иногда недооценивать ценность действия, но позволяет избежать ошибки завышенной оценки, которую делает Q-обучение. Это также показывает, что это тип проблем, двойное Q-обучение достигает хороших уровней производительности намного быстрее.
Код Python
Следующий код Python моделирует как Double Q-Learning, так и Q-Learning и выводит таблицу и сравнительный график для этих двух методов.
