Сегодня мы сосредоточимся на разработке концепции Q-learning для решения MDP. О псевдокоде и реализации Q-learning на Python мы поговорим в нашей следующей статье. В предыдущих историях мы реализовали как обучаемый ADP на основе моделей, так и обучающийся MC без моделей. Теперь пришло время объединить преимущества обоих и перейти к Q-обучению.

Оглавление:

  1. Концепции обучения в обучении с подкреплением
  2. Выборочное среднее против постоянного размера шага
  3. От игры к игре шаг за шагом
  4. Ученик MC vs Q-обучаемый

Концепции обучения в обучении с подкреплением

Чтобы развить Q-обучающегося, давайте сначала рассмотрим некоторые характеристики MC-обучаемого. Как мы обсуждали в предыдущем рассказе, для любой пары состояние-действие (s, a) мы получаем оценку ее значения всякий раз, когда эта пара появляется в игре. . Поскольку мы продолжаем играть в игру неоднократно, мы получаем оценку G₁ из первой игры, в которой появляется эта пара, G₂ из второй игры, в которой появляется эта пара, …, Gₖ из k-й игры, в которой появляется эта пара.

Используя принцип метода Монте-Карло, мы получаем ожидаемое значение Q путем усреднения выборок значений G. Другими словами, Q-значение — это среднее значение всех G-значений, которые у нас есть.

Например, если мы сосредоточимся только на играх, в которых появляется определенная пара состояние-действие, то после первой игры мы оценим Q как

После второй игры мы оцениваем Q как

Точно так же после k игр мы оцениваем Q как

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

В нашей предыдущей истории мы объяснили, что правило обновления можно переписать как

В результате имеем

Мы можем обобщить это как

Что это значит?

Перед k-й игрой у нас есть Q-значение из предыдущих k−1 игр. Это наша старая оценка или старое знание, которое равно среднему значению G из этих k−1 игр.

Из нашей новой игры, которая является k-й игрой, мы получаем новую оценку Gₖ. Это называется target, потому что оно предоставляет некоторую информацию об истинном значении и как бы показывает направление, в котором мы должны двигаться. Мы также можем назвать это нашей новой информацией.

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

В этом обновлении термин [Цель — OldEstimate] обычно называется ошибка, что является разницей между нашими старыми знаниями и новой информацией. Нам необходимо обновить наши знания в направлении уменьшения этой разницы. Однако, если мы просто добавим эту ошибку к нашим знаниям, мы получим

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

Используя размер шага меньше 1, мы объединяем часть наших старых знаний и часть новой информации. Обычно мы используем 𝛼 для обозначения размера шага.

Выборочное среднее против постоянного размера шага

В нашем ученике MC у нас есть

Используя концепцию размера шага, которую мы обсуждали выше, мы можем переписать это уравнение как

где 𝛼 — размер шага как функция от k, а k — количество игр, сыгранных на данный момент.

В обучающемся MC Q принимается как среднее значение всех G выборок, которые у нас есть в это время. Если мы сыграли k игр, Q — это среднее значение от G₁ до Gₖ. Поэтому этот подход называется усреднением по выборке и имеет размер шага 1/k.

Однако это не единственный размер шага, который мы можем использовать. Мы также можем использовать постоянное значение в качестве размера шага независимо от того, сколько игр мы сыграли. Например, мы можем использовать 0,3 как 𝛼 на каждом шаге. Этот подход называется constant-𝛼.

Как это вообще могло работать? Давайте посмотрим на простой пример.

Предположим, мы сыграли 10 игр. Для конкретной пары состояние-действие у нас есть оценка по каждой игре.

Чтобы визуализировать выборочно-средний подход, давайте воспользуемся таблицей для перечисления результатов.

Как мы доказали выше, использование 1/k в качестве 𝛼 эквивалентно выборочному усреднению. Например,

и так далее.

Теперь давайте попробуем подход с постоянными 𝛼. Например, давайте попробуем 0,3.

После 10 игр метод выборочного среднего дает нам значение Q, равное 5,5, что является в точности средним значением всех 10 значений G. Подход с постоянными 𝛼 дает нам значение Q 5,46, что достаточно близко. Давайте поместим результаты этих двух подходов на одну диаграмму, чтобы увидеть, как они себя ведут.

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

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

Меньший 𝛼 подчеркивает старую оценку, а больший 𝛼 подчеркивает только что изученную цель. Например, давайте попробуем еще два крайних случая 𝛼: 0,1 и 0,9.

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

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

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

От игры к игре шаг за шагом

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

Давайте воспользуемся предельно простым примером, чтобы продемонстрировать этот процесс. Предположим, что у задачи MDP четыре состояния от s₁ до s₄ и только одно действие a.

После k−1 игр у нас есть следующая оценка для каждого состояния

Теперь мы играем в нашу k-ю игру, последовательность s, a, r следующая:

Из этой игры мы получаем новую информацию Gₖ:

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

После того, как мы получим G-значения для каждой пары, пришло время обновить Q-значения. Предполагая, что мы используем константу 𝛼, равную 0,2, мы можем обновить значения Q следующим образом:

Одно важное замечание заключается в том, что Q(k-1) нигде не используется при вычислении Gₖ. Другими словами, Gₖ определяется только тем, что произошло в k-й игре. Оценивая G-значения, учащийся MC рассматривает каждую новую игру как новый старт. Каждая пара состояние-действие оценивается только по ее поведению в текущей игре, независимо от того, что происходило в предыдущих играх.

Это дает нам еще одну возможность улучшить нашего ученика. Когда мы оцениваем значение полезности для пары состояние-действие, что, если мы рассматриваем ее поведение не только в текущей игре, но и в предыдущих играх? Как мы можем этого добиться? Что если мы будем обновлять Q-значения шаг за шагом, а не от игры к игре?

Возьмем тот же пример, после k−1игр у нас все еще есть

Наша k-я игра по-прежнему следующая:

После первого шага имеем

Вместо того, чтобы ждать конца игры, чтобы вычислить G-значение (s₁, a), мы воспользуемся другой информацией из этой игры, а именно: после этого шага наше следующее состояние — s₂». Для любого MDP полезность между текущим состоянием s и следующим состоянием s′ равна

Как мы объяснили в нашей предыдущей истории, полезность состояния может быть получена из Q-ценностей.

В нашем примере у нас есть только одно действие для каждого состояния, поэтому

Следовательно, мы можем оценить полезность Q(s, a) из Q(s em>′, а). В этом случае наша новая информация больше не G(s, a). Другими словами, мы говорим, что Q(s′, a) дает нам приблизительную оценку того, что произойдет в будущем. шаги в этой игре. В результате нам не нужно ждать окончания игры, чтобы посмотреть, что произойдет. Цель, которую мы узнали, просто

У нас уже есть старая оценка Q(s′, a) из предыдущих k−1 игр. В этом примере у нас есть Q(s′=s₂, a) = 40. Предполагая, что мы используем 0,9 как γ. Заносим это в нашу таблицу.

Затем мы можем использовать тот же размер шага с константой-𝛼 0,2, чтобы обновить значение Q первой пары состояние-действие. По сравнению с таблицей обучаемого MC мы просто заменяем Gₖ на r + γ Q( с′).

Не дожидаясь конца игры, мы обновили значение Q первой пары состояние-действие, с которой столкнулись на первом шаге. Теперь переходим ко второму шагу, на котором мы получили награду 10.

Точно так же после третьего шага, на котором мы получаем награду 1, мы можем обновить третью пару состояние-действие.

Ученик MC против Q-обучающегося

Сравнивая MC-обучающийся с нашим новым Q-обучающимся, оба следуют одному и тому же принципу обновления:

Тем не менее, они имеют несколько существенных отличий.

Во-первых, у них разные Target. У учащегося MC недавно изученная Цель равна Gₖ, что зависит только от серии вознаграждений r, полученных в этой игре, независимо от любых предыдущих оценка Q-значений. В Q-leaner вновь изученная Target равна r + γ Q(s′), который включает в себя оценку Q-значений других состояний, а не вознаграждений от будущих шагов.

Во-вторых, Q-leaner использует самозагрузку, а MC Learner — нет. В Q-Learner наше Target, которое является новой догадкой об истинном Q-значении, рассчитывается как r + γ Q(s′). В некотором смысле мы угадываем Q-значение определенной пары состояние-действие на основе Q-значения другой пары состояние-действие, что также является предположением. Это «угадай что-нибудь из других предположений» чем-то похоже на «подтяни себя за шнурки». Поэтому его обычно называют загрузкой.

В-третьих, учащийся MC должен дождаться окончания игры, чтобы обновить значения Q, а учащийся Q — нет. У учащегося MC вновь полученная информация Gₖ не может быть определена до конца игры, потому что Gₖ представляет собой сумму вознаграждений за каждый шаг от текущего до конца. конец игры. Напротив, недавно полученная информация Q-leaner составляет r + γ Q(s′), которые можно определить непосредственно на текущем шаге. Таким образом, ученик MC обновляет значения Q от игры к игре, в то время как ученик Q-leaner обновляет значения Q пошагово без необходимости дождаться окончания игры.

Короче говоря, как показано в этом визуальном сравнении, новая информация, полученная учащимся MC, представляет собой сумму вознаграждений, полученных в этой игре до самого конца. В данном примере это 2 + 10 + 1 +… до конца игры. Вот почему нам нужно дождаться окончания игры, чтобы определить это.

Напротив, Q-обучающийся использует существующие Q-значения следующего состояния, чтобы оценить, что произойдет в будущем. Как показано в визуальном примере, мы просто говорим, что существующее значение Q (s₂, a), равное 40, примерно равно (10 + 1 +…) вплоть до конца игры. Поэтому нам не нужно ждать окончания игры, чтобы получить оценку (s₁, a).

Кто-то может возразить, что Q-обучаемый менее точен, чем MC, потому что 40 — это лишь грубая оценка (10 + 1 +…), а не точное вычисление. Что ж, с точки зрения статистики, в каком-то смысле 40 может быть более точным. Почему это? Поскольку Q(s₂, a) из 40, используемых в Q-learn, представляет то, что произошло в предыдущем k−1игры после того, как мы посетили s₂, в то время как (10 + 1 + …) в учащемся MC представляет только то, что произошло в текущей одиночной игре после того, как мы посетили с₂. Следовательно, Q-leaner имеет тенденцию быть более эффективным и более результативным.

Теперь мы разработали концепции Q-обучения. Мы обсудим псевдокод и реализацию Q-обучения на Python в следующей статье. Следите за обновлениями!