Введение

Добро пожаловать в увлекательное путешествие в мир 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 с помощью уравнения Беллмана:

  1. Инициализируйте Q-таблицу Q с одинаковыми номерами для всех состояний и действий.
  2. Установите скорость обучения alpha на 1.
  3. Повторите симуляцию много раз: а. Начните со случайной позиции. б. Повторяйте до тех пор, пока не будет выполнено условие конца игры или общая награда не станет слишком маленькой:
  4. Выберите действие a в состоянии s.
  5. Выполните действие, перейдя в новое состояние s'.
  6. Вычислите награду r в новом состоянии.
  7. Обновите Q-функцию в соответствии с уравнением Беллмана: Q(s, a) = (1 - alpha) * Q(s, a) + alpha * (r + gamma * max(Q(s', a'))).
  8. Перейдите в новое состояние s.
  9. Обновите общую награду и уменьшите 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)

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

Приятного обучения!