Обучение с подкреплением простое введение в итерацию оценки значения

Простое введение в итерацию оценки значения при обучении с подкреплением.

Изучите основы RL и как применить итерацию значений к простой проблеме-примеру

Итерация значений (VI) обычно является одним из первых алгоритмов, вводимых на пути обучения усиленного обучения (RL). Особенности алгоритма вводят некоторые из самых фундаментальных аспектов RL и, следовательно, важно овладеть VI перед переходом к более сложным алгоритмам RL. Однако это может быть сложно понять.

Эта статья представляет собой простое и понятное введение в VI, которое предполагает, что читатель новичок в области RL. Давайте начнем.

Уже знакомы с основами RL? → Перейдите к тому, как использовать итерацию значений.

Основы RL

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

Обзор процесса обучения усиленного обучения

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

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

Книга “Введение в усиленное обучение” Ричарда С. Саттона и Эндрю Г. Барто считается лучшей в своей области для тех, кто хочет получить прочное понимание RL.. и она доступна бесплатно!

Определим простую проблему-пример

Возможные состояния для игры в гольф

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

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

В RL каждое из этих положений называется состоянием среды. Можно представлять себе состояние как снимок текущей среды (гольф-поля), который также записывает положение мяча.

Возможные действия в игре в гольф

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

Вероятности перехода в игре в гольф

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

Например, мы можем промахнуться, когда делаем удар с фэрвея и остаемся все еще на фэрвее. В терминах RL, если мы находимся в состоянии мяча на фэрвее и делаем действие ударить на грина, то существует 90% вероятность, что мы перейдем в состояние мяча на грине, но 10% вероятность, что мы снова вернемся в состояние мяча на фэрвее.

Вознаграждение в 10 за попадание мяча в лунку

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

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

Марковские процессы принятия решений

Для представления проблемы так, чтобы агент понимал ее, мы должны формализовать ее как Марковский процесс принятия решений (MDP).

MDP – это математическая модель, которая описывает нашу проблему структурированным образом. Он представляет взаимодействие агента с окружением как последовательный процесс принятия решений (т.е. одно действие за другим).

Он состоит из динамики окружения (я собираюсь добавить некоторую математическую нотацию, чтобы сократить объем):

  • конечное множество состояний s ∈ S.
  • конечное множество действий a ∈ A.
  • функция перехода T(s′∣s,a), возвращающая вероятность достижения состояния s′ при текущем состоянии s и текущем действии a.
  • функция вознаграждения R(s,a,s′), возвращающая скалярное вознаграждение на основе достижения следующего состояния s′ после нахождения в состоянии s и совершения действия a.

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

Визуализируя нашу проблему с гольфом как MDP, она выглядит примерно так же, как на изображениях, изображенных ранее. Мы будем использовать S = {s1, s2, s3} для краткости.

Наш пример с гольфом, записанный как MDP

Использование MDP предполагает, что то, что произойдет дальше в окружении, зависит только от того, что происходит прямо сейчас – текущего состояния и действия – и не от того, что произошло раньше. Это называется марковским свойством и оно важно в RL, так как снижает вычислительную сложность. Я объясню это подробнее позже.

Что такое итерация значения?

Итерация значения (VI) – это алгоритм, используемый для решения проблем RL, подобных упомянутому выше примеру с гольфом, где у нас есть полное знание всех компонентов MDP. Он работает путем итеративного улучшения оценки “значения” нахождения в каждом состоянии. Он делает это, рассматривая мгновенные вознаграждения и ожидаемые будущие вознаграждения при выполнении разных доступных действий. Эти значения отслеживаются с помощью таблицы значений, которая обновляется на каждом шаге. В конечном итоге, эта последовательность улучшений сходится, давая оптимальную политику отображения состояния → действия, которую агент может следовать, чтобы принимать наилучшие решения в данной среде.

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

Сейчас это не будет иметь много смысла. Самый простой способ изучить VI – разбить его на шаги, так что давайте сделаем это.

Как работает алгоритм итерации значений?

На рисунке ниже показаны шаги алгоритма. Не бойтесь, это проще, чем кажется.

Алгоритм итерации значений

Сначала нам нужно определить некоторые параметры для нашего обучения.

  • Theta θ представляет собой порог сходимости. Как только мы достигнем θ, мы можем прервать цикл обучения и сгенерировать политику. Это в основном просто способ гарантировать, что созданная нами политика достаточно точна. Если мы остановим обучение слишком рано, мы можем не научиться выбирать лучшие действия.
  • Gamma γ представляет собой коэффициент дисконтирования. Это значение определяет, насколько наш агент ценит будущие вознаграждения по сравнению с немедленными вознаграждениями. Более высокий коэффициент дисконтирования (ближе к 1) указывает на то, что агент более ценит долгосрочные вознаграждения, в то время как более низкий коэффициент дисконтирования (ближе к 0) уделяет большее внимание немедленным вознаграждениям.

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

(1) Инициализация: Теперь, когда у нас определены параметры, мы хотим инициализировать нашу функцию значения V(s) для всех состояний в S. Обычно это означает, что мы устанавливаем все значения равными 0 (или какой-то другой произвольной константе) для каждого состояния. Представьте функцию значения как таблицу, которая отслеживает значение для каждого состояния, часто обновляясь.

Инициализированная таблица значений

(2) Внешний цикл: Теперь все готово, мы можем начать итерационный процесс обновления наших значений. Мы начинаем с внешнего цикла, который повторяется, пока не будут выполнены критерии сходимости (пока Δ < θ).

На каждом проходе внешнего цикла мы начинаем с установки Δ = 0. Дельта Δ используется для представления изменения оценок значений по всем состояниям, и алгоритм продолжает итерацию, пока это изменение Δ не упадет ниже указанного порога θ.

(3) Внутренний цикл: Для каждого состояния s в S мы:

  • устанавливаем переменную v в текущее значение этого состояния V(s), помните – это извлекается из нашей таблицы значений (так что на первом проходе v = V(s) = 0)
  • выполняем уравнение Беллмана для обновления V(s)
  • обновляем Δ (мы вернемся к этому позже)

Уравнение Беллмана

Эта строка алгоритма является наиболее важной. Она требует от нас обновить значение текущего состояния, на которое мы смотрим в цикле. Это значение рассчитывается с учетом всех доступных действий из этого конкретного состояния (взгляд на 1 шаг вперед). Когда мы выполняем каждое из этих возможных действий, оно представляет собой набор возможных следующих состояний s′ и соответствующих вознаграждений r.

Итак, для каждого из этих следующих состояний s′ и соответствующих вознаграждений r, мы выполняем p(s′, r|s, a)[r + γV(s′)]. Давайте разберем это:

  • p(s′, r|s, a) – вероятность нахождения в состоянии s, совершения действия a и перехода в следующее состояние s′ (это просто наша функция перехода)
  • [r + γV(s′)] – вознаграждение r за переход в следующее состояние s′ (мы получаем его из нашей функции вознаграждения) + наша скидка γ * на значение этого следующего состояния s′ (мы получаем его из нашей таблицы значений)
  • Затем мы умножаем эти две части p(s′, r|s, a) * [r + γV(s′)]

Помните, что эта расчетная формула применяется только к одному следующему состоянию s′ (третьему уровню дерева), нам нужно повторить это для каждого возможного следующего состояния s′ после выполнения действия a.

После того, как мы это сделаем, мы складываем все полученные результаты Σₛ′, ᵣ p(s′, r|s, a) * [r + γV(s′)]. Затем мы повторяем это для каждого действия a (второго уровня в дереве).

После завершения этих шагов, у нас будет значение, связанное с каждым возможным действием a из текущего состояния, которое мы рассматриваем во внутреннем цикле s. Мы выбираем наибольшее значение с помощью maxₐ и устанавливаем его равным нашему новому значению для этого состояния V(s)←maxₐ Σₛ′, ᵣ p(s′, r|s, a) * [r + γV(s′)].

Помните, что этот процесс касается только одного состояния s (первого уровня в дереве)

Если бы мы программировали это, у нас было бы 3 цикла for для каждого уровня в дереве:

(3) Внутренний цикл (продолжение): Перед переходом к следующему проходу во внутреннем цикле мы выполняем сравнение между текущим значением Δ и разницей между предыдущим значением этого состояния v и новым значением для этого состояния, которое мы только что рассчитали V(s). Мы обновляем Δ до большего из этих двух значений: Δ ← max(Δ,| v – V(s)|). Это помогает нам отслеживать, насколько близки мы к сходимости.

Хорошо, этот процесс завершает один проход внутреннего цикла. Мы выполняем шаг (3) для каждого s в S перед выходом из внутреннего цикла и проверкой условия сходимости Δ < θ. Если это условие выполняется, мы выходим из внешнего цикла, если нет, мы возвращаемся к шагу (2).

(4) Извлечение политики: К этому моменту мы, вероятно, выполнили несколько проходов через внешний цикл, пока не достигли сходимости. Это означает, что наша таблица значений будет обновлена для представления конечного значения каждого состояния (другими словами, “насколько хорошо находиться в каждом состоянии”). Теперь мы можем извлечь политику из этого.

Помните, что политика π по существу является отображением из состояний → действий, и для каждого состояния она выбирает действие, которое максимизирует ожидаемый доход. Для расчета этого мы выполняем точно такой же процесс, как и раньше, но вместо получения значения для состояния s с помощью maxₐ, мы получаем действие a, которое дает нам лучшее значение с помощью argmaxₐ.

И вот и все!

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

Решение примера с помощью итерации значения

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

Мы начнем с определения наших параметров модели, используя довольно стандартные значения:

γ = 0.9 // коэффициент дисконтированияθ = 0.01 // порог сходимости

Затем мы инициализируем нашу таблицу значений нулем для состояний в S:

// таблица значенийV(s0) = 0V(s1) = 0V(s2) = 0

Теперь мы можем начать внешний цикл:

Δ = 0

И три прохода внутреннего цикла для каждого состояния в S:

// Правило обновления Беллмана// V(s) ← maxₐ Σₛ′, ᵣ p(s′, r|s, a) * [r + γV(s′)]//******************* состояние s0 *******************//v = 0// мы рассмотрели только одно действие здесь, так как только одно доступно из s0// мы знаем, что другие действия невозможны и, следовательно, суммируются с 0V(s0) = max[T(s0 | s0, попадание на зеленую) * (R(s0, попадание на зеленую, s0) + γ * V(s0)) +            T(s1 | s0, попадание на зеленую) * (R(s0, попадание на зеленую, s1) + γ * V(s1))]V(s0) = max[0.1 * (0 + 0.9 * 0) +             0.9 * (0 + 0.9 * 0)]V(s0) = max[0] = 0// Правило обновления дельты// Δ ← max(Δ,| v - V(s)|)Δ = max[Δ, |v - v(s0)|] = max[0, |0 - 0|] = 0//******************* состояние s1 *******************//v = 0// здесь доступны 2 действияV(s1) = max[T(s0 | s1, попадание на поляну) * (R(s1, попадание на поляну, s0) + γ * V(s0)) +             T(s1 | s1, попадание на поляну) * (R(s1, попадание на поляну, s1) + γ * V(s1)),            T(s1 | s1, попадание в лунку) * (R(s1, попадание в лунку, s1) + γ * V(s1)) +             T(s2 | s1, попадание в лунку) * (R(s1, попадание в лунку, s2) + γ * V(s2))]V(s1) = max[0.9 * (0 + 0.9 * 0) +             0.1 * (0 + 0.9 * 0),            0.1 * (0 + 0.9 * 0) +             0.9 * (10 + 0.9 * 0)]V(s1) = max[0, 9] = 9Δ = max[Δ, |v - v(s1)|] = max[0, |0 - 9|] = 9//******************* состояние s2 *******************//// терминальное состояние без действий

Это дает нам следующее обновление нашей таблицы значений:

V(s0) = 0V(s1) = 9V(s2) = 0

Нам не нужно беспокоиться о s2, так как это терминальное состояние, что означает, что здесь невозможны действия.

Теперь мы выходим из внутреннего цикла и продолжаем внешний цикл, выполняя проверку сходимости на:

Δ < θ = 9 < 0.01 = Ложь

Так как мы еще не сошлись, мы выполняем вторую итерацию внешнего цикла:

Δ = 0

И еще 3 прохода внутреннего цикла, используя обновленную таблицу значений:

//******************* состояние s0 *******************//v = 0V(s0) = max[T(s0 | s0, попадание в зеленую зону) * (R(s0, попадание в зеленую зону, s0) + γ * V(s0)) +            T(s1 | s0, попадание в зеленую зону) * (R(s0, попадание в зеленую зону, s1) + γ * V(s1))]V(s0) = max[0.1 * (0 + 0.9 * 0) +             0.9 * (0 + 0.9 * 9)]V(s0) = max[7.29] = 7.29Δ = max[Δ, |v - v(s0)|] = max[0, |0 - 7.29|] = 7.29//******************* состояние s1 *******************//v = 9V(s1) = max[T(s0 | s1, попадание в равнину) * (R(s1, попадание в равнину, s0) + γ * V(s0)) +             T(s1 | s1, попадание в равнину) * (R(s1, попадание в равнину, s1) + γ * V(s1)),            T(s1 | s1, попадание в лунку) * (R(s1, попадание в лунку, s1) + γ * V(s1)) +             T(s2 | s1, попадание в лунку) * (R(s1, попадание в лунку, s2) + γ * V(s2))]V(s1) = max[0.9 * (0 + 0.9 * 7.29) +             0.1 * (0 + 0.9 * 9),            0.1 * (0 + 0.9 * 9) +             0.9 * (10 + 0.9 * 0)]V(s1) = max(6.7149, 9.81) = 9.81Δ = max[Δ, |v - v(s1)|] = max[7.29, |9 - 9.81|] = 7.29//******************* состояние s2 *******************//// терминальное состояние без действий

По окончании второй итерации наши значения:

V(s0) = 7.29V(s1) = 9.81V(s2) = 0

Проверяем сходимость снова:

Δ < θ = 7.29 < 0.01 = Ложь

По-прежнему нет сходимости, поэтому мы продолжаем тот же процесс, что и раньше, пока Δ < θ. Я не буду показывать все вычисления, достаточно двух, чтобы понять процесс.

После 6 итераций наша политика сходится. Это наши значения и скорость сходимости на каждой итерации:

Итерация   V(s0)        V(s1)        V(s2)        Δ             Сошелся1           0            9            0            9             Ложь2           7.29         9.81         0            7.29          Ложь3           8.6022       9.8829       0            1.3122        Ложь4           8.779447     9.889461     0            0.177247      Ложь5           8.80061364   9.89005149   0            0.02116664    Ложь6           8.8029969345 9.8901046341 0            0.0023832945  Верно

Теперь мы можем извлечь нашу политику:

// Правило извлечения политики// π(s) = argmaxₐ Σₛ′, ᵣ p(s′, r|s, a) * [r + γV(s′)]//******************* состояние s0 *******************//// мы знаем, что из s0 есть только одно возможное действие, но давайте сделаем это все равноπ(s0) = argmax[T(s0 | s0, попадание в зеленую зону) * (R(s0, попадание в зеленую зону, s0) + γ * V(s0)) +            T(s1 | s0, попадание в зеленую зону) * (R(s0, попадание в зеленую зону, s1) + γ * V(s1))π(s0) = argmax[0.1 * (0 + 0.9 * 8.8029969345) +             0.9 * (0 + 0.9 * 9.8901046341)]π(s0) = argmax[8.80325447773]π(s0) = попадание в зеленую зону//******************* состояние s1 *******************//π(s1) = argmax[T(s0 | s1, попадание в равнину) * (R(s1, попадание в равнину, s0) + γ * V(s0)) +             T(s1 | s1, попадание в равнину) * (R(s1, попадание в равнину, s1) + γ * V(s1)),            T(s1 | s1, попадание в лунку) * (R(s1, попадание в лунку, s1) + γ * V(s1)) +             T(s2 | s1, попадание в лунку) * (R(s1, попадание в лунку, s2) + γ * V(s2))]V(s1) = max[0.9 * (0 + 0.9 * 8.8029969345) +             0.1 * (0 + 0.9 * 9.8901046341),            0.1 * (0 + 0.9 * 9.8901046341) +             0.9 * (10 + 0.9 * 0)]π(s1) = argmax[8.02053693401, 9.89010941707]π(s1) = попадание в лунку

Наша окончательная политика такова:

π(s0) = ударить в зеленое π(s1) = ударить в лункуπ(s2) = терминальное состояние (без действия)

Таким образом, когда наш агент находится в состоянии Мяч на поляне (s0), лучшим действием является ударить в зеленое. Это кажется довольно очевидным, поскольку это единственное доступное действие. Однако, в состоянии s1, где есть два возможных действия, наша политика научилась ударять в лунку. Теперь мы можем передать эту изученную политику другим агентам, которые хотят играть в гольф!

И вот оно! Мы только что решили очень простую задачу RL с использованием Итерации Значения.

Ограничения динамического программирования

Важно отметить, что Итерация Значения, вместе с другими алгоритмами Динамического Программирования, имеет свои ограничения. Во-первых, он предполагает, что у нас есть полное знание о динамике MDP (мы называем это модельно-ориентированным RL). Однако, это редко бывает в реальных проблемах, например, мы можем не знать вероятности перехода. Для проблем, где это так, необходимо использовать другие подходы, такие как Q-обучение (безмодельный RL).

Проклятие размерности в шахматах

Во-вторых, для более крупных проблем, с увеличением числа состояний и действий, размер таблицы значений экспоненциально растет (подумайте о попытке определить все возможные состояния шахмат). Это приводит к проблеме “проклятия размерности”, при которой требования вычислительных и памятных ресурсов быстро возрастают, что затрудняет применение DP к высокоразмерным проблемам.

Тем не менее, ИЗ отлично подходит для изучения, так как он вводит некоторые из ключевых основных концепций RL, которые являются основой более сложных алгоритмов, которые вы можете изучить в дальнейшем.

Спасибо за чтение!

Я надеюсь, что этот статья предоставила понятное введение в обучение с подкреплением и, в частности, в Итерацию Значения.

Если вы узнали что-то новое здесь, пожалуйста, поставьте 👏 и подпишитесь!

Если не указано иначе, все изображения созданы автором.