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

Недавно я наткнулся на вопрос по литкоду: Кратчайший путь в сетке с устранением препятствий. Задача Кратчайший путь в сетке с устранением препятствий включает в себя поиск кратчайшего пути от начальной ячейки до целевой ячейки в двумерной сетке, содержащей препятствия, где вам разрешено устранить до k препятствий, лежащих на пути. Сетка представлена ​​двумерным массивом m x n, состоящим из 0 (пустые ячейки) и 1 (ячейки с препятствиями).

Цель состоит в том, чтобы найти кратчайший путь от начальной ячейки (0, 0) до целевой ячейки (m-1, n-1), проходя через пустые ячейки, пока устраняя не более k препятствий. Устранение препятствия означает преобразование ячейки препятствия (1) в пустую ячейку (0), чтобы путь мог пройти через нее.

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

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

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

class Solution:
    def shortestPath(self, grid: List[List[int]], k: int) -> int:
        rows, cols = len(grid), len(grid[0])
        target = (rows - 1, cols - 1)

        # if we have sufficient quotas to eliminate the obstacles in the worst case,
        # then the shortest distance is the Manhattan distance
        if k >= rows + cols - 2:
            return rows + cols - 2

        # (row, col, remaining quota to eliminate obstacles)
        state = (0, 0, k)
        # (steps, state)
        queue = deque([(0, state)])
        seen = set([state])

        while queue:
            steps, (row, col, k) = queue.popleft()

            # we reach the target here
            if (row, col) == target:
                return steps

            # explore the four directions in the next step
            for new_row, new_col in [(row, col + 1), (row + 1, col), (row, col - 1), (row - 1, col)]:
                # if (new_row, new_col) is within the grid boundaries
                if (0 <= new_row < rows) and (0 <= new_col < cols):
                    new_eliminations = k - grid[new_row][new_col]
                    new_state = (new_row, new_col, new_eliminations)
                    # add the next move in the queue if it qualifies
                    if new_eliminations >= 0 and new_state not in seen:
                        seen.add(new_state)
                        queue.append((steps + 1, new_state))

        # did not reach the target
        return -1

Небольшое введение в обучение с подкреплением

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

Давайте углубимся в эти темы по терминам:

  • Агент. Агент – это гипотетическая сущность, которая контролирует ход действий. Вы можете представить себе гипотетического робота, скажем, агента Рая, который начинает с определенной позиции и исследует окружающую среду. Например, у Рая есть два возможных варианта: позиция (0, 0), которая идет вправо, или позиция (0, 1), которая идет вниз, и обе эти позиции имеют разные награды.
  • Среда. Среда — это контекст, в котором работает наш агент, который является двумерным (в данном случае сеткой).
  • Состояние: состояние представляет текущую ситуацию игрока. В нашем случае это текущая позиция игрока и количество оставшихся нарушений.
  • Система вознаграждений: вознаграждение — это балл, который мы получаем в результате выполнения определенного действия. В данном случае: -1 балл за пустую ячейку, +20 баллов за достижение пункта назначения и -10 баллов, если у нас закончится количество нарушений, k.

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

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

Q-функция

Q(s, a) представляет собой ожидаемое совокупное вознаграждение, которое агент может получить, выполнив действие a в состоянии s, следуя политике π.

Где

  • π : политика, принятая агентом.
  • s : текущее состояние.
  • a : действие, предпринятое агентом в состоянии s.

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

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

Давайте теперь перейдем к коду того, как все это работает.

Вот как мы определяем агента и связанные с ним переменные.

Функция вознаграждения: функция вознаграждения принимает текущее состояние и возвращает вознаграждение, полученное за это состояние.

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

Как нам следует обновить Q-таблицу, чтобы она имела наилучшее значение для каждой позиции и действия? Для произвольного количества итераций агент начинает с позиции (0, 0, k), где k обозначает разрешенное количество нарушений. На каждом временном шаге агент переходит в новое состояние, либо исследуя случайным образом, либо используя изученные значения Q для жадного перемещения.

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

Вот уравнение для уравнения Беллмана:

Вот как процесс обучения выглядит в коде:

Путь построения: для пути мы используем максимальное значение Q для каждой позиции сетки, чтобы определить оптимальное действие, которое следует предпринять в этой позиции. Значения Q, по сути, кодируют наилучшее возможное действие в каждом месте на основе долгосрочного вознаграждения. Например, для всех действий k в позиции (0,0) максимальное значение Q соответствует действию «1», которое представляет движение вправо. Жадно выбирая на каждом шаге действие с наибольшим значением Q, мы можем построить оптимальный путь через сетку.

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

Вот ссылка на весь код в одном файле: shortest_path_rl.py

Заключение

В реальных сценариях обучения с подкреплением среда, с которой взаимодействует агент, может быть огромной, с редкими вознаграждениями.
Если вы измените конфигурацию доски, изменив 0 и 1, этот жестко запрограммированный подход с использованием Q-таблицы потерпит неудачу. обобщать. Наша цель — обучить агента, который изучает общее представление конфигураций сетчатого мира и может находить оптимальные пути в новых макетах. В следующем посте я собираюсь заменить жестко закодированные значения Q-таблицы на Deep Q Network (DQN). DQN — это нейронная сеть, которая принимает на вход комбинацию состояния-действия и полную структуру сетки и выводит оценку значения Q. Этот DQN должен позволить агенту находить оптимальные пути даже в новых макетах сетки, с которыми он не сталкивался во время обучения.

Если вы хотите быстро поговорить и подключиться, свяжитесь со мной в LinkedIn: https://www.linkedin.com/in/pratikdaher/