Решение проблемы Leetcode с использованием обучения с подкреплением

Leetcode problem solving with reinforcement learning

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

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

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

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

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

• Моделирование данных для обычных смертных – Часть 2 Основы многомерного моделирования
• Связь идей Сравнение SQL и Python запросов с использованием аналитики книжного магазина
• OpenAI открывает ворота для предприятий искусственного интеллекта

Вот функция на языке 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 k >= rows + cols - 2:            return rows + cols - 2        # (строка, столбец, оставшаяся квота для устранения препятствий)        state = (0, 0, k)        # (шаги, состояние)        queue = deque([(0, state)])        seen = set([state])        while queue:            steps, (row, col, k) = queue.popleft()            # мы достигли цели здесь            if (row, col) == target:                return steps            # исследуем четыре направления на следующем шаге            for new_row, new_col in [(row, col + 1), (row + 1, col), (row, col - 1), (row - 1, col)]:                # если (new_row, new_col) находится в пределах границ сетки                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)                    # добавляем следующий ход в очередь, если он подходит                    if new_eliminations >= 0 and new_state not in seen:                        seen.add(new_state)                        queue.append((steps + 1, new_state))        # не достигли цели        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/