Введение
Добро пожаловать в увлекательное путешествие в мир Reinforcement Learning (RL)! В этом уроке мы рассмотрим, как можно применить RL к задаче поиска пути, вдохновленной знаменитой музыкальной сказкой «Петя и волк», написанной Сергеем Прокофьевым. Присоединяйтесь к нам, пока мы обучаем алгоритмы машинного обучения, чтобы помочь Петру, отважному юному первопроходцу, исследовать лес и построить оптимальную навигационную карту.
Сеттинг: Мир Питера
В нашем сценарии мир Питера представлен в виде квадратной доски размером width
x height
. Каждая ячейка на этой доске может иметь разные атрибуты, в том числе:
- Земля: Питер и другие существа могут ходить по ней.
- Вода: Вы не можете ходить по воде.
- Дерево или трава: безопасные места, где можно отдохнуть.
- Яблоко: Что-то, что Питер был бы рад найти и съесть.
- Волк: опасен, и его следует избегать любой ценой.
Для взаимодействия с окружением мы определим класс с именем Board
. Для простоты мы перенесли детали реализации платы в отдельный модуль rlboard
. Давайте импортируем его и создадим случайную доску, чтобы визуализировать, как она выглядит:
import matplotlib.pyplot as plt import numpy as np import random import math from rlboard import * width, height = 8, 8 m = Board(width, height) m.randomize(seed=13) m.plot()
Обзор обучения с подкреплением
Прежде чем мы углубимся в специфику, давайте кратко разберемся в сути обучения с подкреплением (RL). RL — это тип машинного обучения, при котором агент учится взаимодействовать со средой для достижения определенной цели. Агент получает награды или штрафы от функции вознаграждения в зависимости от своих действий. Цель состоит в том, чтобы научиться оптимальному поведению, которое со временем максимизирует совокупное вознаграждение.
Действия и политика Агента
В нашей задаче действия, которые может предпринять Петя, представлены в виде словаря, отображающего их на пары соответствующих изменений координат:
actions = {"U": (0, -1), "D": (0, 1), "L": (-1, 0), "R": (1, 0)} action_idx = {a: i for i, a in enumerate(actions.keys())}
Стратегия агента, называемая политикой, направляет его процесс принятия решений. Мы начнем с простой политики, называемой случайным блужданием, в которой Питер выбирает действия случайным образом.
Случайная прогулка
Чтобы изначально решить нашу проблему, давайте реализуем стратегию случайного блуждания:
def random_policy(m): return random.choice(list(actions)) def walk(m, policy, start_position=None): n = 0 # number of steps # set initial position if start_position: m.human = start_position else: m.random_start() while True: if m.at() == Board.Cell.apple: return n # success! if m.at() in [Board.Cell.wolf, Board.Cell.water]: return -1 # eaten by wolf or drowned while True: a = actions[policy(m)] new_pos = m.move_pos(m.human, a) if m.is_valid(new_pos) and m.at(new_pos) != Board.Cell.water: m.move(a) # do the actual move break n += 1
Мы можем оценить политику случайного блуждания:
def print_statistics(policy): s, w, n = 0, 0, 0 for _ in range(100): z = walk(m, policy) if z < 0: w += 1 else: s += z n += 1 print(f"Average path length = {s/n}, eaten by wolf: {w} times") print_statistics(random_policy)
Функция вознаграждения
Чтобы сделать нашу политику более разумной, нам нужно понять, какие ходы «лучше», чем другие. Для этого мы определим функцию вознаграждения, которая обеспечивает обратную связь с агентом.
move_reward = -0.1 goal_reward = 10 end_reward = -10 def reward(m, pos=None): pos = pos or m.human if not m.is_valid(pos): return end_reward x = m.at(pos) if x == Board.Cell.water or x == Board.Cell.wolf: return end_reward if x == Board.Cell.apple: return goal_reward return move_reward
Q-Learning: сердце RL
Теперь давайте рассмотрим основу нашего алгоритма обучения с подкреплением: Q-Learning. Мы построим Q-Table, представленную в виде многомерного массива numpy формы width
x height
x len(actions)
:
Q = np.ones((width, height, len(actions)), dtype=np.float) * 1.0 / len(actions) m.plot(Q)
Q-таблица представляет «привлекательность» каждого действия в каждом состоянии. Чтобы обновить Q-Table, мы будем использовать уравнение Беллмана и реализуем алгоритм Q-Learning.
Суть Q-Learning: уравнение Беллмана и алгоритм обучения
Давайте наметим алгоритм Q-Learning с помощью уравнения Беллмана:
- Инициализируйте Q-таблицу
Q
с одинаковыми номерами для всех состояний и действий. - Установите скорость обучения
alpha
на 1. - Повторите симуляцию много раз: а. Начните со случайной позиции. б. Повторяйте до тех пор, пока не будет выполнено условие конца игры или общая награда не станет слишком маленькой:
- Выберите действие
a
в состоянииs
. - Выполните действие, перейдя в новое состояние
s'
. - Вычислите награду
r
в новом состоянии. - Обновите Q-функцию в соответствии с уравнением Беллмана:
Q(s, a) = (1 - alpha) * Q(s, a) + alpha * (r + gamma * max(Q(s', a')))
. - Перейдите в новое состояние
s
. - Обновите общую награду и уменьшите
alpha
.
Эксплуатация или исследование: поиск баланса
Чтобы найти баланс между разведкой и эксплуатацией, мы будем использовать метод, называемый эпсилон-жадностью. По мере того, как агент узнает больше об окружающей среде, он будет чаще следовать оптимальному маршруту, но все же иногда будет выбирать неизведанные пути.
Реализация Python: алгоритм обучения
Теперь давайте реализуем алгоритм Q-Learning. Мы запустим его на 5000 эпох:
from IPython.display import clear_output lpath = [] for epoch in range(5000): # Pick an initial point m.random_start() # Start traveling n = 0 cum_reward = 0 while True: x, y = m.human v = probs(Q[x, y]) a = random.choices(list(actions), weights=v)[0] dpos = actions[a] m.move(dpos, check_correctness=False) # Allow player to move outside the board, terminating the episode r = reward(m) cum_reward += r if r == end_reward or cum_reward < -1000: lpath.append(n) break alpha = np.exp(-n / 10e5) gamma = 0.5 ai = action_idx[a] Q[x, y, ai] = (1 - alpha) * Q[x, y, ai] + alpha * (r + gamma * Q[x + dpos[0], y + dpos[1]].max()) n += 1
После выполнения алгоритма Q-Learning в Q-Table будут добавлены значения, определяющие привлекательность различных действий на каждом этапе. Визуализируйте Q-таблицу на доске:
m.plot(Q)
Проверка политики
В Q-таблице указана «привлекательность» каждого действия в каждом состоянии. Мы можем использовать его для определения эффективной стратегии навигации для нашего агента. В простейшем случае мы можем просто выбрать действие, соответствующее наибольшему значению Q-Table:
def qpolicy_strict(m): x, y = m.human v = probs(Q[x, y]) a = list(actions)[np.argmax(v)] return a walk(m, qpolicy_strict)
Если вы попробуете код выше несколько раз, вы можете заметить, что иногда он просто «зависает», и вам нужно нажать кнопку STOP в блокноте, чтобы прервать его.
Задачи для улучшения учебного процесса
По мере того, как вы лучше знакомитесь с RL, вы можете экспериментировать с различными модификациями, чтобы улучшить процесс обучения:
Задача 1. Измените функцию
walk
, чтобы ограничить максимальную длину пути определенным количеством шагов (например, 100). Наблюдайте, как код время от времени возвращает это значение.
Задача 2. Измените функцию
walk
, чтобы она не возвращалась в те места, где уже была. Это предотвратит зацикливание агента, но он все равно может оказаться в ловушке в месте, из которого не сможет выбраться.
def qpolicy(m): x, y = m.human v = probs(Q[x, y]) a = random.choices(list(actions), weights=v)[0] return a print_statistics(qpolicy)
Исследование процесса обучения
Вы можете построить длину пути для каждой эпохи, чтобы визуализировать, как развивается процесс обучения:
plt.plot(lpath)
Вы завершили этот учебник для начинающих с Петром и Волком. Теперь у вас есть прочная основа для изучения более сложных задач и алгоритмов обучения с подкреплением.
Приятного обучения!