History

leestott eaff2e5814 🌐 Update translations via Co-op Translator		2 weeks ago
..
solution	🌐 Update translations via Co-op Translator	3 weeks ago
README.md	🌐 Update translations via Co-op Translator	2 weeks ago
assignment.md	🌐 Update translations via Co-op Translator	3 weeks ago
notebook.ipynb	🌐 Update translations via Co-op Translator	3 weeks ago

README.md

Unescape Escape

Введение в обучение с подкреплением и Q-Learning

Скетчноут от Tomomi Imura

Обучение с подкреплением включает три важных понятия: агент, состояния и набор действий для каждого состояния. Выполняя действие в определённом состоянии, агент получает награду. Представьте компьютерную игру Super Mario. Вы — Марио, находитесь на уровне игры, стоите рядом с краем обрыва. Над вами монета. Вы, будучи Марио, находитесь на уровне игры в определённой позиции — это ваше состояние. Шаг вправо (действие) приведёт вас к падению с обрыва, что даст низкий числовой результат. Однако нажатие кнопки прыжка позволит вам заработать очко и остаться в живых. Это положительный исход, который должен принести вам положительный числовой результат.

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

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

Тест перед лекцией

Предварительные требования и настройка

В этом уроке мы будем экспериментировать с кодом на Python. Вы должны иметь возможность запускать код из Jupyter Notebook, либо на своём компьютере, либо в облаке.

Вы можете открыть ноутбук урока и пройти через этот урок, чтобы создать проект.

Примечание: Если вы открываете этот код из облака, вам также нужно получить файл rlboard.py, который используется в коде ноутбука. Добавьте его в ту же директорию, что и ноутбук.

Введение

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

Обучение с подкреплением (RL) — это метод обучения, который позволяет нам изучить оптимальное поведение агента в некоторой среде, проводя множество экспериментов. Агент в этой среде должен иметь цель, определённую с помощью функции награды.

Среда

Для простоты представим мир Пети в виде квадратной доски размером width x height, как показано ниже:

Каждая ячейка на этой доске может быть:

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

Существует отдельный модуль Python, rlboard.py, который содержит код для работы с этой средой. Поскольку этот код не важен для понимания наших концепций, мы импортируем модуль и используем его для создания примерной доски (блок кода 1):

from rlboard import *

width, height = 8,8
m = Board(width,height)
m.randomize(seed=13)
m.plot()

Этот код должен вывести изображение среды, похожее на приведённое выше.

Действия и политика

В нашем примере цель Пети — найти яблоко, избегая волка и других препятствий. Для этого он может ходить по доске, пока не найдёт яблоко.

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

Мы определим эти действия в виде словаря и сопоставим их с парами соответствующих изменений координат. Например, движение вправо (R) будет соответствовать паре (1,0). (блок кода 2):

actions = { "U" : (0,-1), "D" : (0,1), "L" : (-1,0), "R" : (1,0) }
action_idx = { a : i for i,a in enumerate(actions.keys()) }

Итак, стратегия и цель этого сценария следующие:

Стратегия нашего агента (Пети) определяется так называемой политикой. Политика — это функция, которая возвращает действие для любого заданного состояния. В нашем случае состояние задачи представлено доской, включая текущую позицию игрока.
Цель обучения с подкреплением — в конечном итоге изучить хорошую политику, которая позволит нам эффективно решать задачу. Однако для начала рассмотрим самую простую политику, называемую случайной прогулкой.

Случайная прогулка

Сначала решим нашу задачу, реализовав стратегию случайной прогулки. При случайной прогулке мы будем случайным образом выбирать следующее действие из разрешённых действий, пока не достигнем яблока (блок кода 3).

Реализуйте случайную прогулку с помощью кода ниже:

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

walk(m,random_policy)

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

Запустите эксперимент прогулки несколько раз (например, 100) и выведите полученную статистику (блок кода 4):
```
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)
```
Обратите внимание, что средняя длина пути составляет около 30-40 шагов, что довольно много, учитывая, что среднее расстояние до ближайшего яблока составляет около 5-6 шагов.

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

Функция награды

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

Цель может быть определена с помощью функции награды, которая возвращает некоторое числовое значение для каждого состояния. Чем выше число, тем лучше награда. (блок кода 5)

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

Алгоритм, который мы рассмотрим здесь, называется Q-Learning. В этом алгоритме политика определяется функцией (или структурой данных), называемой Q-таблицей. Она фиксирует "качество" каждого действия в заданном состоянии.

Она называется Q-таблицей, потому что её удобно представлять в виде таблицы или многомерного массива. Поскольку наша доска имеет размеры width x height, мы можем представить Q-таблицу с помощью массива numpy формы width x height x len(actions): (блок кода 6)

Q = np.ones((width,height,len(actions)),dtype=np.float)*1.0/len(actions)

Обратите внимание, что мы инициализируем все значения Q-таблицы одинаковым числом, в нашем случае — 0.25. Это соответствует политике "случайной прогулки", так как все шаги в каждом состоянии одинаково хороши. Мы можем передать Q-таблицу в функцию plot, чтобы визуализировать таблицу на доске: m.plot(Q).

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

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

Суть Q-Learning: уравнение Беллмана

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

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

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

Предположим, что мы сейчас находимся в состоянии s и хотим перейти в следующее состояние s'. При этом мы получим немедленную награду r(s,a), определённую функцией награды, плюс некоторую будущую награду. Если предположить, что наша Q-таблица правильно отражает "привлекательность" каждого действия, то в состоянии s' мы выберем действие a, соответствующее максимальному значению Q(s',a'). Таким образом, лучшая возможная будущая награда, которую мы могли бы получить в состоянии s, будет определена как max

Проверка политики

Поскольку Q-Table содержит "привлекательность" каждого действия в каждом состоянии, использовать её для определения эффективной навигации в нашем мире довольно просто. В самом простом случае мы можем выбрать действие, соответствующее наибольшему значению в Q-Table: (код блок 9)

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 в ноутбуке, чтобы прервать выполнение. Это происходит потому, что могут возникнуть ситуации, когда два состояния "указывают" друг на друга с точки зрения оптимального значения Q-Value, в результате чего агент бесконечно перемещается между этими состояниями.

🚀Задача

Задача 1: Измените функцию walk, чтобы ограничить максимальную длину пути определённым количеством шагов (например, 100), и посмотрите, как код выше возвращает это значение время от времени.

Задача 2: Измените функцию walk, чтобы она не возвращалась в места, где уже была ранее. Это предотвратит зацикливание walk, однако агент всё равно может оказаться "запертым" в месте, из которого не сможет выбраться.

Более эффективной политикой навигации будет та, которую мы использовали во время обучения, объединяющая использование накопленных знаний и исследование. В рамках этой политики каждое действие выбирается с определённой вероятностью, пропорциональной значениям в Q-Table. Эта стратегия всё ещё может привести к тому, что агент вернётся в уже исследованное место, но, как видно из кода ниже, она обеспечивает очень короткий средний путь к желаемой цели (помните, что print_statistics запускает симуляцию 100 раз): (код блок 10)

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)

После выполнения этого кода вы должны получить значительно меньшую среднюю длину пути, в диапазоне от 3 до 6.

Исследование процесса обучения

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

Выводы из обучения:

Средняя длина пути увеличивается. На начальном этапе средняя длина пути увеличивается. Это, вероятно, связано с тем, что, не зная ничего о среде, мы склонны попадать в плохие состояния, такие как вода или волк. По мере того как мы узнаём больше и начинаем использовать эти знания, мы можем исследовать среду дольше, но всё ещё плохо знаем, где находятся яблоки.
Длина пути уменьшается по мере обучения. Когда мы узнаём достаточно, агенту становится легче достигать цели, и длина пути начинает уменьшаться. Однако мы всё ещё открыты для исследования, поэтому часто отклоняемся от оптимального пути и пробуем новые варианты, что делает путь длиннее, чем оптимальный.
Резкое увеличение длины. На графике также видно, что в какой-то момент длина пути резко увеличивается. Это указывает на стохастическую природу процесса, и на то, что мы можем "испортить" коэффициенты Q-Table, перезаписав их новыми значениями. Это желательно минимизировать, уменьшая скорость обучения (например, ближе к концу обучения мы корректируем значения Q-Table только на небольшую величину).

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

Тест после лекции

Задание

Более реалистичный мир

Отказ от ответственности:
Этот документ был переведен с помощью сервиса автоматического перевода Co-op Translator. Несмотря на наши усилия обеспечить точность, имейте в виду, что автоматические переводы могут содержать ошибки или неточности. Оригинальный документ на его родном языке следует считать авторитетным источником. Для получения критически важной информации рекомендуется профессиональный перевод человеком. Мы не несем ответственности за любые недоразумения или неправильные интерпретации, возникшие в результате использования данного перевода.

README.md Unescape Escape