Почему Q-обучение не сходится при использовании приближения функций?

12

Алгоритм табличного Q-обучения гарантированно найдет оптимальную Q функцию, Q , при условии, что выполнены следующие условия (условия Роббинса-Монро ) относительно скорости обучения

  1. tαt(s,a)=
  2. tαt2(s,a)<

где αt(s,a) означает скорость обучения, используемую при обновлении значения Q связанного с состоянием s и действием a на временном шаге T , где 0αt(s,a)<1 предполагается истинным, для все состояния s и действия a .

По-видимому, учитывая, что 0αt(s,a)<1 , чтобы оба условия выполнялись, все пары состояния-действия должны посещаться бесконечно часто: об этом также говорится в книге « Обучение подкреплению: введение» , помимо того , что это должно быть широко известно и является обоснование использования в ϵ -greedy политики (или аналогичной политики) во время тренировки.

Полное доказательство того, что Q обучение находит оптимальную функцию Q можно найти в статье « Сходимость Q-обучения: простое доказательство» (Франсиско С. Мело). Он использует такие понятия, как сопоставление сокращений , чтобы определить оптимальную функцию Q (см. Также Что такое оператор Беллмана в обучении подкреплению? ), Которая является фиксированной точкой этого оператора сжатия. Он также использует теорему (п. 2) о случайном процессе, который сходится к 0 , учитывая несколько предположений. (Доказательство может быть нелегким, если вы не математик.)

Если нейронная сеть используется для представления Q функции, не имеет место сходимость гарантий Q - Learning еще держать? Почему (или нет) Q-обучение сходятся при использовании приближения функции? Существует ли формальное доказательство такой не сходимости Q обучения с помощью приближения функций?

Я ищу разные типы ответов, от тех, которые дают интуицию за не сходимостью Q обучения при использовании приближения функций к тем, которые предоставляют формальное доказательство (или ссылку на статью с формальным доказательством).

нбро
источник
2
Отличный вопрос!
Джон Дусетт
Книга, на которую вы ссылались, рассказывает об этой проблеме в главе 11, так что вы можете прочитать ее. Кроме того, я не думаю, что есть формальное доказательство того, почему это происходит, но есть несколько примеров, которые показывают расхождение даже в простых средах (например, Цициклис и ван Рой).
Brale_

Ответы:

8

Вот интуитивное описание ответа:

Аппроксимация функции может быть выполнена с помощью любой параметризуемой функции. Рассмотрим проблему пространства Q(s,a) где s - положительные вещественные числа, a - 0 или 1 , а истинная Q-функция - Q(s,0)знак равноs2 и Q(s,1)знак равно2s2 , для всех состояний. Если ваш аппроксиматор функции Q(s,a)=ms+na+b , не существует параметров, которые могли бы точно представить истиннуюфункциюQ (мы пытаемся подобрать линию к квадратичной функции). Следовательно, даже если вы выбрали хорошую скорость обучения и бесконечно часто посещаете все состояния, ваша функция приближения никогда не будет сходиться к истиннойфункцииQ

А вот немного подробнее:

  1. Нейронные сети приближенных функций. Функция может быть аппроксимирована в большей или меньшей степени с помощью более или менее сложных полиномов для аппроксимации. Если вы знакомы с приближением Тейлора, эта идея должна показаться довольно естественной. Если нет, подумайте о функции , как синус-волны на интервале [0 - π/2 ). Вы можете приблизить это (плохо) с прямой линией. Вы можете приблизить его лучше с помощью квадратичной кривой. Увеличивая степень многочлена, который мы используем для аппроксимации кривой, мы можем получить то, что подходит к кривой все более близко.
  2. Нейронные сети являются универсальными аппроксиматорами функций . Это означает, что если у вас есть функция, вы также можете создать нейронную сеть, достаточно глубокую или широкую, чтобы она могла приближаться к функции, которую вы создали, в произвольно точной степени. Однако любая топология сети, которую вы выберете, не сможет изучить все функции, если она не будет бесконечно широкой или бесконечно глубокой. Это аналогично тому, как, если вы выберете правильные параметры, линия может соответствовать любым двум точкам, но не любым 3 точкам. Если вы выберете сеть с определенной конечной шириной или глубиной, я всегда могу создать функцию, для которой нужно еще несколько нейронов, чтобы соответствовать.

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

Джон Дусетт
источник
Где из приведенного мною доказательства видно, что «границы Q-обучения имеют место только тогда, когда представление Q-функции является точным», верно?
nbro
Таким образом, мы можем аппроксимировать любую (разумную) функцию, используя некоторую нейронную сеть (архитектуру), но, учитывая фиксированную архитектуру нейронной сети (которую нам нужно выбрать в начале фазы обучения Q- обучения), Q- обучение может не сходиться с использованием этой конкретной архитектуры Z , потому что Z может быть недостаточно выразительным, чтобы представлять Q . ZQQZZQ*
nbro
@nbro Доказательство не говорит этого явно, но оно предполагает точное представление Q-функции (то есть, что точные значения вычисляются и сохраняются для каждой пары состояние / действие). Для бесконечных пространств состояний ясно, что это точное представление может быть бесконечно большим в худшем случае (простой пример: пусть Q (s, a) = sth цифра числа pi). Ваш второй комментарий хорошо подводит итог. Более формально, если истинная гипотеза Q * не является элементом пространства гипотез H, из которого вы выбираете модель, вы не можете сходиться к Q * даже с бесконечным временем или данными.
Джон Дусетт
4

Насколько я знаю, все еще остается открытой проблемой получить действительно четкое, формальное понимание того, почему / когда мы получаем недостаточную конвергенцию - или, что еще хуже, иногда опасность расхождения. Как правило, это связано с «смертельной триадой» (см. 11.3 второго издания книги Саттона и Барто):

  1. Функция приближения, И
  2. Q
  3. Q

Это только дает нам (возможно, не исчерпывающее) описание случаев, когда у нас отсутствует сходимость и / или существует опасность расхождения, но все же не говорит нам, почему это происходит в этих случаях.


Q*

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


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

Q(s,a)(s,a)Q


МаксимумМаксимум

Q(s,a)

Q(s,a)Q(s,a)+α[Максимумa'Q(s',a')-Q(s,a)],

Максимумa'Q(s',a')QQ(s,a)Максимумa'Q(s',a')


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

Деннис Соемерс
источник
1
Но разве использование нейронной сети также не связано с предположением, что определенные состояния очень похожи на каждое? Очень похожие состояния (например, последовательные кадры в игре) часто имеют очень похожие (или одинаковые) оптимальные действия, поэтому я не уверен, что объяснение в первой статье является верным (я должен прочитать его, чтобы полностью понять их основные моменты).
nbro
1
@nbro Да, часто именно по этой причине обобщение считается преимуществом, а не проблемой. Если он работает как «предназначенный», он может быть очень мощным и ускорять обучение, потому что мы переводим все, что мы изучаем, в аналогичные состояния / сходные действия, а не обучаемся для каждого слегка отличающегося состояния / действия изолированно. Но это также может привести к проблемам, особенно в теории, но и на практике. Полагаю, это как «обоюдоострый меч».
Деннис Соемерс
1
@DennisSoemers Супер интересный ответ. Неразумный вопрос Q-обучения имеет массу смысла. Поиск правильной Q-функции означает поиск фиксированной точки для вашего правила обновления, но, похоже, аппроксимация функции может привести к циклическим обновлениям в Q-learning, если вы подумаете об этом таким образом.
Джон Дусетт