Со времени последних статей мы все больше и больше переходили от теории к практике. Последние две статьи о методах Монте-Карло использовались для решения проблемы прогнозирования и проблемы управления в обучении с подкреплением.

Продолжая методы Монте-Карло, в этой статье мы рассмотрим другой метод, называемый Обучение по временной разнице (TD).

TD-обучение — центральная и новая идея обучения с подкреплением. Его можно рассматривать как комбинацию двух других основных элементов методов Монте-Карло (MC) и динамического программирования (DP).

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

Как и методы Монте-Карло, методы TD обсуждаются в двух статьях.

В первой части я хочу осветить проблему прогнозирования TD, ошибку TD, преимущества TD-прогнозирования и Оптимальность TD(0).

Итак, давайте начнем с проблемы предсказания…

ТД для задачи предсказания

TD-обучение использует опыт для решения задачи предсказания, как и Методы Монте-Карло. Оба метода обучения обновляют значение V нетерминального состояния, s,которое возникает в опыте. Однако они отличаются оценкой целевого значения. (Что такое функция ценности?)

Методам Монте-Карло необходимо дождаться конца эпизода, чтобы определить приращение к V(S_t), потому что только тогда известен возврат G_t, тогда как методы TD просто должны дождитесь следующего временного шага. В момент времени t+1 они немедленно формируют цель и вносят полезное обновление, используя наблюдаемое вознаграждение R_(t+1) и оценку V(S_(t +1)).

В приведенных уравнениях хорошо видна разница в выборе целевого значения для этапа обновления. MC использует G в качестве целевого значения, а целевое значение для TD в случае TD(0) равно R_(t+1) + V(s_(t +1)). Поскольку он использует только значение следующего состояния для вычисления цели, он называется одношаговым TD или TD(0).

Существуют и другие методы, такие как n-step TD или TD(лямбда), основанные на этом простом одноэтапном обновлении TD, но они представлены в последующих статьях.

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

Важно отметить, что количество:

в обновлении TD(0) есть ошибка измерения разницы между оценочным значением s и лучшей оценкой R_(t+1) + gamma * V . Таким образом, эта ошибка называется Ошибка TD и возникает в различных формах повсюду в мире обучения с подкреплением.

Следует также иметь в виду, что ошибка TD зависит от следующего состояния и следующего вознаграждения, что означает, что она фактически доступна только на следующем временном шаге.

Как и в статье о методе Монте-Карло, я также реализовал основные алгоритмы обучения TD. Результаты и реализацию можно посмотреть в репозитории GitHub:

На изображении ниже показаны прогнозируемые значения состояния среды Gridworld после обучения:

Преимущества прогноза TD

Итак, теперь, если вы читали и работали с кодом прошлой статьи о MC, вы знаете как о методах MC, так и о TD для прогнозирования. Теперь было бы интересно узнать, в чем состоят преимущества каждого метода. TD узнает, что их оценки основаны на других оценках, а это значит, что они загрузились. Но является ли такая самонастройка хорошим способом?Учиться угадывать на основе другого предположения?

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

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

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

Но как насчет проблемы методов TD, изучающих догадку на догадке? Являются ли методы TD надежными и надежными, сходятся ли они?
С удовольствием, если вы посетите блокнот на GitHub для реализации TD(0) или внимательно изучите по результатам, опубликованным выше, мы можем сказать, что да, методы TD (0) сходятся! Для любой фиксированной политики pi было доказано, что TD(0) сходится к v_pi.

Следующий логичный вопрос: какой метод, MC или TD, сходится/обучается быстрее?

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

На практике методы TD обычно сходятся быстрее, чем методы MC в стохастических задачах. Также рассмотрите лучшую применимость методов TD для задач с длинными эпизодами или непрерывными задачами!

Оптимальность ТД(0)

Чтобы понять оптимальность методов TD(0), их отличие и более быструю сходимость, рассмотрим пример пакетного обновления.

Во-первых, что такое пакетное обновление. Представьте, что мы взаимодействовали с окружающей средой в течение 3 эпизодов. Таким образом, для каждого шага обновления мы рассматриваем все события в эпизоде ​​как одну партию и повторно повторяем каждый эпизод для каждого шага обучения, пока алгоритм не сойдется. Тогда как после каждого шага обучения проигрывается один эпизод, который добавляется в нашу память. Итак, исходя из нашего примера, шаг обучения будет следующим:
 – учиться из пакетов ep1, ep2, ep3
 – играть ep4
- учиться на ep1, ep2, ep3, ep4
- играть ep5
- …
Это называется пакетным обновлением, потому что обновления значения производятся только после обработки каждого полного пакета обучающих данных. То есть функция значения изменяется только один раз на сумму всех приращений.

Учитывая это пакетное обновление, MC и TD(0) сходятся к одному, но другому ответу. Ниже вы можете увидеть результаты сравнения MC и TD (0) для пакетного обновления задачи прогнозирования случайных блужданий на основе их среднеквадратичной ошибки с функцией значений v_pi.

Мы знаем, что MC использует выборочные средние фактические доходы, полученные после посещения каждого состояния s. Это оптимальные оценки в том смысле, что они минимизируют среднеквадратичную ошибку.
Но почему TD(0) работает лучше, чем этот оптимальный метод? Ответ заключается в том, что методы MC оптимальны лишь в ограниченном смысле, а методы TD — это оптимальные способы, более подходящие для прогнозирования доходности. Чтобы понять это более ясно, давайте рассмотрим этот пример прогноза:

Представьте, что у нас есть 8 эпизодов опыта, заданных как состояние и награда марковского процесса вознаграждения, и мы хотим обновить функцию ценности.
Эп1: (A,0), (B, 0)
Эпизод 2: (B,1)
Эпизод 3: (B,1)
Эпизод 4: (B,1)
Эпизод 5: (B,1)
Эпизод 6: (B,1)
Эпизод 7: (B,1)
Эпизод 8: (B,0)
Вычисление значения для состояния B кажется интуитивно простым сV(B) = ¾. Но какова будет ценность для A? Есть два разумных ответа.

Ответ для метода TD также будет ¾. Поскольку мы уже решили, что B имеет значение 3/4, и мы переходим из состояния A непосредственно в состояние с вознаграждением 0. Следовательно, A также должно иметь значение, если 3/4. Один из способов рассмотрения этого ответа состоит в том, что он основан на первом моделировании марковского процесса (показанного ниже), а затем на вычислении правильных оценок с учетом модели, что действительно в данном случае дает V(A) = ¾. Вы также можете посмотреть на шаг обновления методов TD.

Ответ, который дал бы MC, равен 0. Мы видели A один раз, и общий доход, который следовал за ним, пока эпизод не закончился, был равен 0. Следовательно, оценка V(A) = 0. Это также ответ, который дает минимальную среднеквадратичную ошибку на обучающих данных. Несмотря на то, что MC достигает ошибки 0, мы считаем первый ответ (TD) лучшим. Поскольку если используется марковский процесс, мы ожидаем, что первый ответ будет давать меньшую ошибку для будущих данных, даже если ответ MC лучше для существующих данных.
Методы пакетного MC всегда найти оценки, которые минимизируют MSE на обучающем наборе, тогда как пакет TD (0) всегда находит оценки, которые были бы точно правильными для модели максимального правдоподобия марковского процесса.

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

Надеюсь, это поможет вам понять, почему методы TD сходятся быстрее, чем методы MC. В пакетной форме TD(0) работает быстрее, чем методы MC, поскольку вычисляет истинную оценку достоверности-эквивалентности.

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