【5min Paper】Глубокое обучение с подкреплением с двойным Q-обучением

Тема эссе: Глубокое обучение с подкреплением с двойным Q-обучением

Проблема решена?

Q-LearningВ алгоритме имеет место завышение функции ценности действия (overestimate action values) (поскольку его уравнение обновления содержитmaximizationэлемент функции значения действия), повлияет ли такая проблема переоценки на производительность его алгоритма? Можем ли мы избежать такой проблемы переоценки?

задний план

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

Используемый метод?

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

Предположим, у вас есть две сети $\theta$ и $\theta^{'}$ . Один используется для выбора действия, решенияgreedy policy, другой используется для определения функции значения действия. Для удобства иDQNСравнение алгоритмов, сначала напишите сюдаDQNФормула:

Y_{t}^{\mathrm{Q}}=R_{t+1}+\gamma Q\left(S_{t+1}, \underset{a}{ \text { argmax }} Q\left(S_{t+1}, a ; \boldsymbol{\theta}_{t}\right) ; \boldsymbol{\theta}_{t}\right)

Double Q-LearningФормула выглядит следующим образом:

Y_{t}^{\text {DoubleQ }} \equiv R_{t+1}+\gamma Q\left(S_{t+1}, \underset{a}{\operatorname{argmax}} Q\left(S_{t+1}, a ; \boldsymbol{\theta}_{t}\right) ; \boldsymbol{\theta}_{t}^{\prime}\right)

Основное различие между ними заключается в следующем.TargetИспользуются ли выбор политики и оценка политики в одной и той же сети.

Достигнутый эффект?

Автор эксперимента использует многочлен, чтобы подобрать кривую через точки выборки. Исходный текст выглядит следующим образом: Оценка представляет собой полином d-степени, который соответствует истинным значениям в выборочных состояниях, где d = 6 (верхняя и средняя строки) или d = 9 (нижняя строка). На рисунке ниже: сравнение между экспериментами в первой строке и второй строке предназначено для анализа общности проблемы переоценки, а эксперименты во второй строке и третьей строке — для анализа взаимосвязи между проблемой завышения и подгоночная способность приближенной функции.

Автор разработал эту среду, и функция оптимального значения действия связана только с текущим состоянием. Самая оптимальная функция «действие-ценность» имеет следующий вид: $Q_{*}(s,a)=sin(s)$ , средняя и нижняя линии выполнены в виде $Q_{*}(s,a)=2 exp(-s^{2})$ . На рисунке слева показана аппроксимация функции значения действия состояния, а зеленые точки — это точки выборки во время эксперимента.

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

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

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

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

На самом деле так и будет. Результаты эксперимента следующие:

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

Опубликованная информация? Информация об авторе?

2016годDeepMindКоманда Опубликовано вational conference on artificial intelligenceпредыдущий пост автораHado van Hasselt,GoogleDeepMindнаучный сотрудник,Rich Suttonколлега.

Домашняя страница:hadovanhasselt.com/about/

Доказательство теоремы

Theorem1

Теорема 1 Описание: задано состояние, его истинная оптимальная функция действия-ценности и функция ценности удовлетворяют уравнению: $Q_{*}(s,a)=V_{*}(s)$ . Предположение $Q_{t}$ является произвольной функцией значения действия в текущем состоянии, и ее несмещенная оценка выражается как: $\sum_{a}(Q_{t}(s,a)-V_{*}(s))=0$ . Но это описание не совсем корректно, например: $\frac{1}{m}\sum_{a}(Q_{t}(s,a)-V_{*}(s))^{2}=C$ . в C > 0 , $m \geq 2$ Указывает количество действий, которые можно выбрать в текущем состоянии. При указанных выше условиях получается следующее неравенство:

max_{a}Q_{t}(s,a) \geq V_{*}(s) + \sqrt{\frac{C}{m-1}}

Приведенная выше теорема на самом деле утверждает, что даже если ваши оценки функции действия-ценности в среднем верны, то есть $\sum_{a}(Q_{t}(s,a)-V_{*}(s))=0$ , небольшое возмущение все равно приведет к переоценке, что приведет к отклонению от истинной функции оптимального значения.

На рисунке ниже показано, что нижняя нижняя граница переоценки уменьшается по мере увеличения размерности пространства действий.

Теорема 1 Доказательство:

определить ошибку для каждого действия $\epsilon_{a}=Q_{t}(s,a)-V_{*}(s)$ . предположим, что существует $max_{a} \epsilon_{a} < \sqrt{\frac{C}{m-1}}$ такая коллекция $\{\epsilon_{a} \}$ , у которого естьнабор положительных чисел $\{\epsilon_{a}^{+} \}$ , m-n набор отрицательных чисел $\{\epsilon_{a}^{-} \}$ ( $\{\epsilon_{a} \}=\{\epsilon_{a}^{+} \} \cup \{\epsilon_{a}^{-} \}$ ). если n=m ,Зависит от $\sum_{a} \epsilon_{a}=0$ может быть запущен $\epsilon_{a}=0$ , что то же самое, что $\vee a$ удовлетворить $\sum_{a} \epsilon_{a}^{2}=mC$ противоречивы, поэтому должно быть n < m-1 . Из этого можно сделать вывод, что: $\sum_{i=1}^{n} \epsilon_{i}^{+} \leq n \max _{i} \epsilon_{i}^{+}<n \sqrt{\frac{C}{m-1}}$ ,использовать $\sum_{a} \epsilon_{a}=0$ может получить $\sum_{j=1}^{m-n}\left|\epsilon_{j}^{-}\right|<n \sqrt{\frac{C}{m-1}}$ ,это означает $\max _{j}\left|\epsilon_{j}^{-}\right|<n \sqrt{\frac{C}{m-1}}$ . Это приводит к следующей формуле:

\begin{aligned} \sum_{j=1}^{m-n}\left(\epsilon_{j}^{-}\right)^{2} & \leq \sum_{j=1}^{m-n}\left|\epsilon_{j}^{-}\right| \cdot \max _{j}\left|\epsilon_{j}^{-}\right| \\ &<n \sqrt{\frac{C}{m-1}} n \sqrt{\frac{C}{m-1}} \end{aligned}

Теперь мы можем объединить эти отношения, чтобы вычислить все $\epsilon_{a}$ верхний предел суммы квадратов.

\begin{aligned} \sum_{a=1}^{m}\left(\epsilon_{a}\right)^{2} &=\sum_{i=1}^{n}\left(\epsilon_{i}^{+}\right)^{2}+\sum_{j=1}^{m-n}\left(\epsilon_{j}^{-}\right)^{2} \\ &<n \frac{C}{m-1}+n \sqrt{\frac{C}{m-1}} n \sqrt{\frac{C}{m-1}} \\ &=C \frac{n(n+1)}{m-1} \\ & \leq m C \end{aligned}

Это то же самое, что и предполагаемое $\sum_{a=1}^{m} \epsilon_{a}^{2}=mC$ противоречиво, поэтому множество $\epsilon$ Элемент удовлетворяет ограничению $max_{a} \epsilon_{a} \geq \sqrt{\frac{C}{m-1}}$ . мы можем установить $\epsilon_{a}=\sqrt{\frac{C}{m-1}}$ ,правильно $a=1,\cdots,m-1$ ,и $\epsilon_{m}=-\sqrt{(m-1)C}$ иди проверь этонижняя частьверно. можно проверить $\sum_{a}\epsilon_{a}^{2}=mC$ и $\sum_{a}\epsilon_{a}=0$ .

Theorem2

Теорема 2 Описание:

Данное состояние, для всех действительно оптимальных функций действия-ценности с $Q_{*}(s,a)=V_{*}$ уравнение. Гипотетическая ошибка оценки $Q_{t}(s,a)-Q_{*}(s,a)$ существует [-1,1] удовлетворяет независимому равномерному случайному распределению. имеют:

\mathbb{E}\left[\max _{a} Q_{t}(s, a)-V_{*}(s)\right]=\frac{m-1}{m+1}

Теорема 2 Доказательство:

Определение $\epsilon_{a} = Q_{t}(s,a)-Q_{*}(s,a)$ ; это [-1,1] Равномерная случайная величина в пространстве. $max_{a} \epsilon_{a} \leq x$ Вероятность эквивалентна одновременному, $\epsilon_{a} \leq x$ Вероятность. Поскольку ошибки оценок независимы, мы можем вывести:

\begin{aligned} P\left(\max _{a} \epsilon_{a} \leq x\right) &=P\left(X_{1} \leq x \wedge X_{2} \leq x \wedge \ldots \wedge X_{m} \leq x\right) \\ &=\prod_{a=1}^{m} P\left(\epsilon_{a} \leq x\right) \end{aligned}

функция $P(\epsilon_{a} \leq x)$ да $\epsilon_{a}$ Кумулятивная функция распределения (cumulative distribution function(CDF)), определяемый просто как:

P\left(\epsilon_{a} \leq x\right)=\left\{\begin{array}{ll} {0} & {\text { if } x \leq-1} \\ {\frac{1+x}{2}} & {\text { if } x \in(-1,1)} \\ {1} & {\text { if } x \geq 1} \end{array}\right.

это означает:

\begin{aligned} P\left(\max \epsilon_{a} \leq x\right) &=\prod_{a=1}^{m} P\left(\epsilon_{a} \leq x\right) \\ &=\left\{\begin{array}{ll} {0} & {\text { if } x \leq-1} \\ {\left(\frac{1+x}{2}\right)^{m}} & {\text { if } x \in(-1,1)} \\ {1} & {\text { if } x \geq 1} \end{array}\right. \end{aligned}

Дана случайная величина $max_{a} \epsilon_{a}$ , ее математическое ожидание можно записать в следующем интегральном виде:

\mathbb{E}\left[\max _{a} \epsilon_{a}\right]=\int_{-1}^{1} x f_{\max }(x) \mathrm{d} x

в $f_{max}$ - функция плотности вероятности этой переменной, определяемая какCDFПроизводное от : $f_{max}(x)=\frac{d}{dx}P(max_{a} \epsilon_{a} \leq x)$ . Поэтому $x \in [-1,1]$ ,У нас есть $f_{max}(x)=\frac{m}{2}(\frac{1+x}{2})^{m-1}$ , а затем вычислить его интеграл следующим образом:

\begin{aligned} \mathbb{E}\left[\max _{a} \epsilon_{a}\right] &=\int_{-1}^{1} x f_{\max }(x) \mathrm{d} x \\ &=\left[\left(\frac{x+1}{2}\right)^{m} \frac{m x-1}{m+1}\right]_{-1}^{1} \\ &=\frac{m-1}{m+1} \end{aligned}

Ссылка на ссылку

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

Thrun and A. Schwartz. Issues in using function approximation for reinforcement learning. In M. Mozer, P. Smolensky, D. Touretzky, J. Elman, and A. Weigend, editors, Proceedings of the 1993 Connectionist Models Summer School, Hillsdale, NJ, 1993. Lawrence Erlbaum.

или добавить немного шума

van Hasselt. Double Q-learning, Достижения в области нейронных систем обработки информации, 23:2613–2621, 2010.
van Hasselt. Insights in Reinforcement Learning. PhD thesis, Utrecht University, 2011.

мойИмя общедоступной учетной записи WeChat: Глубокое обучение и расширенное интеллектуальное принятие решенийИдентификатор официального аккаунта WeChat: Мультиагент1024Введение в публичный аккаунт: В основном исследуйте и делитесь соответствующим контентом, таким как глубокое обучение, машинные игры и обучение с подкреплением! Ждем вашего внимания, добро пожаловать учиться и обмениваться прогрессом вместе!