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

Внедрение модульной структуры и повышение производительности модели

Делиться

После публикации моей предыдущей статьи о сравнительном анализе методов табличного обучения с подкреплением (RL) меня не покидало ощущение, что что-то не так. Результаты выглядели не совсем удачно, и я не был полностью ими доволен.

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

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

Обновленный код можно найти на GitHub.

Рамки

Самое большое изменение по сравнению с предыдущей версией кода заключается в том, что методы решения RL теперь реализованы в виде классов . Эти классы предоставляют общие методы, такие как act() (для выбора действий) и update() (для настройки параметров модели).

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

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

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

def train_single_player( env: ParametrizedEnv, method: RLMethod, max_steps: int = 100, callback: Callable | None = None, ) -> tuple[bool, int]: «»»Обучает метод в однопользовательских средах. Аргументы: env: используемая среда method: используемый метод max_steps: максимальное количество шагов обновления callback: обратный вызов для определения, решает ли метод уже данную задачу Возвращает: кортеж успеха, найденная политика, количество шагов обновления «»» для шага в диапазоне (max_steps): observation, _ = env.env.reset() terminated = truncated = False episode = [] cur_episode_len = 0 пока не завершен и не усечен: action = method.act(observation, step) observation_new, reward, terminated, truncated, _ = env.step( action, observation ) episode.append(ReplayItem(observation, action, reward)) method.update(episode, step) observation = observation_new # ПРИМЕЧАНИЕ: это сильно зависит от размера среды cur_episode_len += 1 if cur_episode_len > env.get_max_num_steps(): break episode.append(ReplayItem(observation_new, -1, reward, [])) method.finalize(episode, step) if callback and callback(method, step): return True, step env.env.close() return False, step

Давайте представим, как выглядит завершенный эпизод и когда в ходе процесса вызываются методы update() и finalize():

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

Чтобы привести конкретный пример, давайте кратко рассмотрим, как это работает для Q-learning .

Напомним правило обновления Q-обучения:

Когда происходит второй вызов update(), мы имеем St = s1, At = a1 и Rt+1 = r2.

Используя эту информацию, агент Q-learning соответствующим образом обновляет свои оценки значений.

Неподдерживаемые методы

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

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

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

Ошибки

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

Расчет вероятности неправильного действия

Некоторые методы требуют вероятности выбранного действия на этапе обновления. В более ранней версии кода мы имели:

def _get_action_prob(Q: np.ndarray) -> float: return ( Q[observation_new, a] / sum(Q[observation_new, :]) if sum(Q[observation_new, :]) else 1 )

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

Исправленная версия правильно обрабатывает как положительные, так и отрицательные значения Q, используя подход softmax:

def _get_action_prob(self, observation: int, action: int) -> float: probs = [self.Q[observation, a] for a in range(self.env.get_action_space_len())] probs = np.exp(probs — np.max(probs)) return probs[action] / sum(probs)

Эта ошибка существенно повлияла на Expected SARSA и n-step Tree Backup , поскольку их обновления сильно зависели от вероятностей действий.

Разрешение ничьей в жадном выборе действий

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

def get_eps_greedy_action(q_values: np.ndarray, eps: float = 0.05) -> int: если random.uniform(0, 1) < eps или np.all(q_values ​​== q_values[0]): вернуть int(np.random.choice([a for a in range(len(q_values))])) else: вернуть int(np.argmax(q_values))

Однако это некорректно обрабатывало ничью , то есть случаи, когда несколько действий имели одинаковое максимальное значение Q. Обновлённый метод act() теперь включает справедливое разрешение ничьей:

def act( self, state: int, step: int | None = None, mask: np.ndarray | None = None ) -> int: allowed_actions = self.get_allowed_actions(mask) if self._train and step and random.uniform(0, 1) < self.env.eps(step): return random.choice(allowed_actions) else: q_values ​​= [self.Q[state, a] for a in allowed_actions] max_q = max(q_values) max_actions = [a for a, q in zip(allowed_actions, q_values) if q == max_q] return random.choice(max_actions)

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

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

Как обсуждалось ранее, и как мы увидим ниже, методы обучения с подкреплением демонстрируют высокую дисперсию, что затрудняет точное измерение влияния таких изменений. Однако эта корректировка, по-видимому, немного улучшила эффективность нескольких методов: Sarsa , Q-learning , Double Q-learning и Sarsa-n .

Обновленные результаты

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

Но сначала коротко напомним о задаче, которую мы решаем: мы работаем со средой GridWorld от Gymnasium [2] — по сути, это задача по решению лабиринта:

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

Чтобы оценить производительность каждого метода, мы масштабируем размер gridworld и измеряем количество шагов обновления до достижения сходимости .

Методы Монте-Карло

Эти методы не были затронуты недавними изменениями реализации, поэтому мы наблюдаем результаты, соответствующие нашим предыдущим выводам:

• Оба способны решать задачи размером до 25×25 .

• Эффективность MC при соблюдении политики немного выше, чем при его отсутствии.

Методы временной разницы

Для них мы измеряем следующие результаты:

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

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

ТД-н

Для методов TD-n наши результаты выглядят совершенно иначе:

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

Планирование

Для планирования у нас остался только Dyna-Q, который тоже, похоже, немного улучшился:

Сравнение лучших методов решения проблем в более крупных средах

Итак, давайте визуализируем наиболее эффективные методы из всех категорий на одной диаграмме. В связи с удалением некоторых методов, таких как DP, я выбрал MC на основе политики, Sarsa, Q-learning, Sarsa-n, резервное копирование дерева на n-шагах и Dyna-Q.

Начнем с показа результатов для сетчатых миров размером до 50 x 50:

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

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

Далее мы наблюдаем средний кластер: Sarsa, Q-learning и Dyna-Q — причем Sarsa немного превосходит остальные.
Несколько удивительно, что обновления на основе модели в Dyna-Q не приводят к повышению производительности. Это может указывать на ограничения точности модели или количества используемых этапов планирования. Q-обучение , как правило, неэффективно из-за повышенной дисперсии, обусловленной его несоответствием политике.

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

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

Заключение и выводы

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

Затем мы применили обновленные методы к все более крупным средам GridWorld и получили следующие результаты:

• В целом лучшим методом оказалось n-шаговое резервное копирование дерева благодаря ожидаемым многошаговым обновлениям, которые сочетают преимущества как обучения в рамках политики, так и обучения вне ее.
• Затем были применены методы Монте-Карло , показавшие удивительно высокую эффективность благодаря их непредвзятым оценкам и промежуточным вознаграждениям, направляющим обучение.
• Затем последовал кластер методов TD — Q-learning, Sarsa и Dyna-Q. Несмотря на обновления Dyna-Q на основе моделей, он не смог значительно превзойти свои аналоги без моделей.
• Sarsa-n показал наихудшие результаты, вероятно, из-за совокупного смещения и дисперсии, вызванных выборкой n-шаговых возвратов.

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

Другие публикации в этой серии

• Часть 1: Введение в обучение с подкреплением и решение задачи «Многорукий бандит»
• Часть 2: Введение в марковские процессы принятия решений, создание сред спортзалов и их решение с помощью методов динамического программирования
• Часть 3: Методы Монте-Карло для решения задач обучения с подкреплением
• Часть 4: Обучение на основе временных различий: сочетание динамического программирования и методов Монте-Карло для обучения с подкреплением
• Часть 5: Введение в n-шаговые методы временной разности
• Часть 6: Планирование и обучение в обучении с подкреплением
• Часть 7: Сравнительный анализ алгоритмов табличного обучения с подкреплением

Ссылки

[1] http://incompleteideas.net/book/RLbook2020.pdf

[2] https://gymnasium.farama.org/

Источник: towardsdatascience.com