Что следует знать о динамическом программировании и итерации политик

Глава 4 учебника RL Саттона и Барто. Вы узнаете, как работают оценка и улучшение политик, а также разницу между итерацией политики/значения и GPI.

Это вторая часть серии учебников Обучение с подкреплением (RL) Саттона и Барто. Дополнительную информацию см. в первой статье. Опять же, это дополнение, а не замена учебника.

Динамическое программирование (глава 4)

Без лишних слов, давайте углубимся в технические детали!

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

Очень простой пример — применение ДП вместо рекурсии для решения последовательности Фибоначчи.

Предварительные условия

Прежде чем продолжить, убедитесь, что у вас есть четкое представление о том, что такое функция. Для тех, кто менее склонен к математике и предпочитает визуализировать примеры, это может помочь. Если независимая переменная одномерная, у вас есть линия или кривая, например y(x) = sin(2x). Если есть две одномерные независимые переменные, у вас есть поверхность, например f(x,y) = sin(x+y).

Теперь предположим, что у нас есть переменная s, которая представляет точку в двумерном пространстве. Согласны ли вы, что функция f(s) тоже поверхность? Когда мы говорим о решении v_{\pi}(s), это именно то, что мы пытаемся решить!

Конечно, состояние s вполне может иметь гораздо более высокие измерения. Это то же самое; мы просто получаем гиперповерхность в гиперпространстве.

Оценка политики

В разделе 4.1 рассказывается о вычислении функции значения состояния v_{\pi} для произвольной политики π. Здесь речь не идет о каком-то разумном выборе действий. Это просто вопрос оценки ожидаемого G для некоторой заданной политики π, которая может быть даже случайной.

Саттон и Барто также отметили, что если динамика окружающей среды полностью известна, уравнение (4.4) представляет собой систему линейных уравнений, где количество уравнений равно числу уникальных состояний. (Для упрощения представления давайте обозначим $\left|\mathcal{S}\right|$ как n.)

Почему это так? Потому что v_{\pi}(s) по сути является кривой или поверхностью/гиперповерхностью, охватывающей n неизвестных точек. Мы можем записать уравнение (4.4) 9 способами, подставляя значение каждого уникального состояния в левую часть каждого уравнения. Зная p(s',r|s,a), правую часть уравнения можно расширить. Мы можем вычислить ожидаемый дисконтированный доход для всех возможных других состояний, умноженный на вероятность перехода (которая вполне может быть равна нулю, если невозможно перейти из s в s' с вознаграждением r, выполнив действие a), сама сумма взвешивается вероятностью действия. по данной политике π.

При одновременном решении мы можем получить решение напрямую, без итераций. [См. математические уравнения и код для примера 3.8 в разделе ключевые выводы 1 (бандиты, MDP и нотации), где точное решение было найдено аналитически.]

Вы увидите, как Саттон и Барто говорят об итеративной оценке политики. Применительно к Примеру 3.8 мы получим следующее.

import numpy as np
from copy import deepcopy
from tqdm import tqdm
import matplotlib.pyplot as plt
import seaborn as sns

class Env:
    def __init__(self):
        self.min_row = 0
        self.max_row = 4
        self.min_col = 0
        self.max_col = 4
    
    def transition(self, state, action):
        if state == [0,1]:
            state = [4,1]
            reward = 10
        elif state == [0,3]:
            state = [2,3]
            reward = 5
        else:
            if action == 0:
                state[1] += 1   # move right one column
            elif action == 1:
                state[0] += 1   # move down one row
            elif action == 2:
                state[1] -= 1   # move left one column
            elif action == 3:
                state[0] -= 1   # move up one row
            else:
                assert False, "Invalid action"
            
            if (state[0] < self.min_row) or (state[1] < self.min_col) \
                or (state[0] > self.max_row) or (state[1] > self.max_col):
                reward = -1
            else:
                reward = 0
        
        next_state = np.clip(state, [0,0], [4,4]).tolist()
        return reward, next_state

class Explorer:
    def __init__(self, Env):
        self.Env = Env
        self.state = [0,0]   # list indicating row and column
        self.policy = lambda s: np.random.choice(4)
        self.v_s = np.zeros((self.Env.max_row+1, self.Env.max_col+1))
        self.gamma = 0.9
        self.lr = 0.1
    
    def step(self, learn=True):
        # action = np.random.choice(4)   # 0:right, 1:down, 2:left, 3:up
        action = self.policy(self.state)
        
        # reward, self.state = self.Env.transition(self.state, action)
        cur_state = self.state
        reward, next_state = self.Env.transition(
            deepcopy(cur_state), action
        )
        
        if learn is True:
            self.lr *= 0.99999
            self.learn_value_fn(cur_state, reward, next_state)
            
        self.state = next_state
        return reward
    
    def learn_value_fn(self, cur_state, reward, next_state):
        self.v_s[cur_state[0],cur_state[1]] += \
            self.lr * (reward + \
                self.gamma*self.v_s[next_state[0],next_state[1]] \
                - self.v_s[cur_state[0],cur_state[1]]
            )
        # note that I used bootstrapping here, so as not to reveal
        # the answer to the assignment question which I will set.
    
    def run(self, n_iter=10000):
        G = 0
        for _ in tqdm(range(n_iter)):
            r = self.step()

env = Env()
agent = Explorer(env)

agent.run(500000)
sns.heatmap(
    agent.v_s, annot=True, cmap='coolwarm', fmt='.1f'
)

Мы видим правило обновления в уравнении (4.5). Не путайте v_{k+1}(s) с v_{\pi}(s). Здесь v_{k+1}(s) относится к функции ценности после k+1 итераций для политики π. Он вычисляется на основе v_{k}(s) других состояний, которые сами по себе могут быть подвержены изменениям при дальнейших итерациях. Авторы учебника описали процедуру реализации этого до сходимости.

Пример 4.1 и результаты, показанные на рисунке 4.2 (стр. 93), заслуживают дальнейшего внимания.

Обратите внимание на столбец «v_{k} для случайной политики». При k = ∞ показано, что значения состояния находятся в диапазоне от -22 до 0, а справа показана жадная политика, связанная с этой функцией значения. Эта «сходимость» при k = ∞ на самом деле соответствует только случайной политике, а каждая соответствующая политика справа — это просто argmax по отношению к вычисленным значениям состояния.

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

Улучшение политики

В разделе 4.2 мы учимся делать что-то значимое после оценки политики.

Уравнение (4.6) — это просто переформулировка уравнения (3.15) на стр. 75, с той лишь разницей, что у нас есть q_{\pi} вместо q_{*}, поскольку теперь это относится к некоторой политике π.

Это подводит нас к теореме улучшения политики. Уравнение (4.7) рассматривает случай, когда мы выбираем действие a, выбранное из политики π', и после этого следуем политике π. Если это приводит к тому, что функция значения действия q_{\pi} лучше (или так же хороша, как) v_{\pi} для всех состояний, тогда должно быть так, что функция значения состояния для π' лучше (или так же хороша, как и v_{\pi}). а) π. Применение строгого неравенства приводит к выводу, что если мы выберем подходящее действие a в каком-то конкретном состоянии s (и после этого сохраним исходное π) так, что G (ожидаемое совокупное вознаграждение со скидкой) увеличится, то мы улучшим политика.

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

Подождите минуту. Не кажется ли это обманчивым? Говорим ли мы, что лучше всего просто выбрать жадное действие? Нет!

Давайте вернемся к техническому определению и обратим внимание на детали. Согласно теореме об улучшении политики, мы имеем q_{\pi}(s,\pi’(s)) \geq v_{\pi}(s). Ожидаемое совокупное вознаграждение рассчитывается по правилу π, т.е. что мы получим, если будем действовать согласно политике π. Подумайте об этапе улучшения политики следующим образом: «Учитывая то, что я знаю сейчас (т. е. функцию ценности моей текущей политики), что лучше всего делать в каждом штате, если бы я оценивал на основе существующих знания?» Ну, это значит предпринять жадные действия. Однако сами существующие знания могут быть несовершенными, поэтому нам также необходимо исследовать.

Вернитесь к рисунку 4.2, чтобы проверить свое понимание (для вашего удобства я вставляю его ниже). Функции стоимости слева соответствуют функциям случайной политики, и выбор жадной политики в отношении этих оцененных функций стоимости обязательно приводит к улучшению исходной политики (которая в данном примере была случайной). Так уж получилось, что начиная с k=3 получается оптимальная политика (можно проверить путем наблюдения).

Это подводит нас к следующей части главы, которая посвящена итеративному улучшению как политики, так и расчета нашей функции ценности.

Итерация политики и значений

В разделе 4.3 мы видим чередующуюся последовательность оценки и улучшения политики. Это означает, что мы можем начать с любой политики \pi_{0}, оценить значение v_{\pi_{0}} (см. раздел 4.1), получить улучшенную политику \pi_{1} (см. раздел 4.2). и повторяйте этот процесс до тех пор, пока не будет получена оптимальная политика \pi_{*}.

Посмотрите на псевдокод на рисунке 4.3. «Шаг 2» сам по себе является итеративным процессом (до сходимости). Итерация политики включает в себя повторное выполнение шагов 2 и 3 до тех пор, пока политика не станет стабильной, т.е. когда нет никаких изменений в прогнозируемых действиях в пространстве состояний.

В разделе 4.4 Саттон и Барто определили итерацию значения как особый случай оценки политики с помощью всего лишь одного прохода. С точки зрения реализации меняется только одно — этап оценки политики сокращается. Здесь мы выполняем только одну итерацию на шаге 2 (вместо ожидания сходимости) и переходим от v_{k}(s) к v_{k+1}(s) для всех состояний s. Вы можете представить это как обновленную кривую или поверхность/гиперповерхность. На шаге 3 политика обновляется, и вероятность выполнения каждого действия меняется. Обратите внимание, что p(s',r|s,a) является свойством среды и остается неизменным. Индекс k в уравнении (4.10), следовательно, соответствует количеству раз, которое мы выполнили шаги 2 и 3.

Почему на каждом этапе оценки политики проводится одна проверка? Потому что не обязательно каждый раз получать v_{\infty}. Давайте вернемся к рисунку 4.2. Функция значения при k=3 уже дает нам очень хорошую улучшенную политику при жадных действиях — дальнейшие итерации до k=∞ — это просто пустая трата вычислительных ресурсов. Несмотря на то, что абсолютные значения существенно различаются, именно относительные значения определяют жадную политику.

Попробуйте самостоятельно написать решение примера 4.2 и посмотрите, будут ли результаты аналогичны показанным на рис. 4.4. Я считаю, что это хороший контрольный пункт для оценки вашего понимания концепций, и его нельзя пропускать.

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

Асинхронный ДП

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

Саттон и Барто также заявили, что «Некоторые штаты могут не нуждаться в поддержке своих ценностей так часто, как другие.». Особенно те, которые не имеют отношения к оптимальному поведению.

Я не хочу вдаваться в технические детали «асинхронности». Идти по этому пути также не имеет смысла, поскольку это может привести к тому, что мы потеряем фокус на том, что является ключевым выводом раздела 4.5. Речь идет не о параллельных или распределенных вычислениях.

Важная идея здесь заключается в том, что «некоторые состояния могут быть скопированы несколько раз, прежде чем значения других будут скопированы один раз». Например, это будет иметь место, если резервное копирование состояний выполняется по мере их посещения. Обратите внимание, что на самом деле это идет рука об руку с идеей онлайн-обучения.

В DQN и Actor-Critic (которые я считаю RL-эквивалентом ResNet в компьютерном зрении — громкие имена, которые существуют уже много лет и, хотя и не являются передовыми, но являются надежными приверженцами первоклассных решений), эта концепция естественным образом применяется. .

Вот несколько небольших оговорок для полноты картины. Содержимое, обсуждаемое до раздела 4.4, основано на моделях, где мы знаем p(s',r|s,a), тогда как DQN и Actor-Critic не содержат моделей и работают с образцами. Мы также не говорили об использовании аппроксимации функций (например, нейронной сети). Более того, когда мы используем воспроизведение опыта, мы можем создавать резервные копии состояний, возникших много эпизодов назад, а не «по мере и при посещении». Просто держите это в глубине души.

Итерация обобщенной политики

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

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

Что касается раздела 4.7, я считаю его комментарием, расширяющим раздел 4.5.

Заключение

Первоначально я намеревался охватить в этой статье главы 4 и 5 вместе. Однако это уже 10 минут времени чтения!

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

Как обычно, я буду рад прояснить ваши сомнения.

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