Марковский процесс принятия решений — введение в обучение с подкреплением… в пиццерии.
Все любят пиццу, верно? Но как выбрать лучшую пиццу для себя? На чужое мнение можно положиться, конечно, но вкус субъективен — не всем нравится пицца с ананасами. На самом деле никто не любит пиццу с ананасами, но вы меня поняли.
В этой статье мы продолжаем наше путешествие о том, как выбрать лучшую пиццу для вас (см. Часть 1 этой серии блогов). Однако на этот раз вы ленивы и просите доставку. Вам также нравится пицца, доставленная как можно скорее. Итак, как пиццерия может добиться этого? Используя, как вы уже догадались, машинное обучение!
Что такое Марковский процесс принятия решений?
Помимо причудливого названия, Марковский процесс принятия решений (MDP) — это структура, в которой определено большинство проблем обучения с подкреплением. В этой структуре агент из данного состояния в среде взаимодействует с ним, совершая действия. Каждое действие приносит вознаграждение агенту и переводит его в новое состояние среды. Цель агента — изучить наиболее оптимальные действия в каждом состоянии, максимизируя его совокупное вознаграждение.
Фу! Это был полный рот. В чем разница между MDP и k-armed bandit, спросите вы? Проще говоря, это количество штатов. В k-armed bandit у нас есть одно состояние, тогда как в MDP у нас есть несколько состояний. Таким образом, вы можете думать о MDP как об обобщении K-вооруженного бандита.
Хватит гиковских штучек. Я проголодался! Вернемся к нашей пиццерии.
В пиццерии
Дин! Новый заказ размещен. Капричоза с добавлением моцареллы. Шеф-повар закатывает рукава и приступает к работе. Прошло двадцать минут, и пицца готова к доставке. Хорошо, что ваш курьер является гуру машинного обучения и может рассчитать оптимальный способ добраться до вашего места. Как он это сделает?
Во-первых, мы начинаем с представления города в виде сетки ячеек. Предположим, что каждая ячейка соответствует 1 квадратному метру поверхности. Некоторые ячейки представляют собой улицу, а другие — здание. Мы также знаем начальную ячейку — магазин пиццы и конечную ячейку — ваш дом.
Во-вторых, курьер должен прибыть к вам как можно быстрее. Он может добиться этого, перемещаясь по как можно меньшему количеству клеток. Чтобы усилить такое поведение, мы вводим награды: перемещение по ячейкам улиц стоит 1 очко, столкновение с клетками зданий стоит 10 очков, выход за пределы сетки также стоит 10 очков, а прибытие на свое место стоит 0 очков. Мы пытаемся минимизировать совокупную сумму баллов (или максимизировать ее, если баллы были отрицательными). Это называется возврат. Почему 10 баллов за неверное направление, спросите вы? Так как мы пытаемся минимизировать общую сумму, ошибка должна стоить больше очков.
В-третьих, каждая из ячеек имеет значение с точки зрения цели, которую мы пытаемся минимизировать (или максимизировать). Некоторые клетки находятся ближе к вашему месту, из которых требуется очень мало движений. Другие могут быть далеко или близко к краю сетки — не буэно! Изначально значение каждой ячейки представляет собой случайное число, которое нам нужно будет изменить. Это функция значения состояния.
Чтобы заполнить функцию значения состояния, нам нужна модель среды. Модель реагирует на наше направление движения, давая нам следующую ячейку и награду. Если направление указывает на ячейку здания, мы остаемся в текущей ячейке и получаем награду 10. Если направление направлено на ячейку улицы, мы двигаемся в новую ячейку и получаем награду 1 (или награду 0, если является конечной ячейкой).
Наконец, в каждой ячейке нам нужно принять решение о направлении движения. Начнем с того, что этот выбор неизвестен, поэтому с равной вероятностью мы можем выбрать любое из направлений. Надеюсь, в конце вычислений мы будем знать оптимальное направление для каждой ячейки. Это политика.
Давайте склеим все вместе. Окончательный алгоритм является итеративным: сначала мы обновляем значение каждой ячейки. Этот шаг называется оценка политики. Затем мы используем обновленные значения, чтобы узнать правильное направление для каждой ячейки. Это называется улучшением политики. Повторите необходимое количество раз — и вуаля! Мы нашли оптимальную политику. Название этого алгоритма — обобщенная итерация политики. Ниже мы увидим, как обновить значение каждой ячейки и как найти правильное направление для каждой ячейки.
Звучит легко? Нет? Давайте посмотрим код.
Код
Во-первых, импорт. Мы напишем все с нуля, поэтому импортируем как можно меньше библиотек. Не забывайте о глобалах.
import numpy as np from matplotlib import pyplot as plt from utils import map_world # GLOBALS m, n = 11, 11 # Size of the world directions = ['up', 'down', 'right', 'left'] # Possible directions gamma = 0.8 # Discounting factor epochs = 100 # The number of epochs evaluation_epochs = 100 # The number of epochs for policy evaluation
Затем мы создаем сетку ячеек и сопоставляем ее с миром с помощью пользовательской функции. Конечно, мы используем простой пример для демонстрации алгоритма, поэтому не ожидайте увидеть «Манхэттен» ниже. Улицы зеленые, а дома серые.
world = np.zeros(shape=(m, n)) world = map_world(world) plt.imshow(world)
Нам нужна модель среды, поэтому мы ее создаем.
# The model of the environment is a two-level dictionary.
# The first key is the cell and the second key is the direction.
# For each cell-direction pair, the dictionary stores the next cell and
# reward as a tuple.
model = {}
def init(cell, direction, next_cell):
'''
Utility function for initializing the next cell and reward
given the current cell and direction.
'''
# If the cell is unreachable, stay in the current cell and pay the price.
if world[next_cell] == 1:
model[cell][direction] = (cell, 10)
# Otherwise, go to the next cell.
else:
model[cell][direction] = (next_cell, 1)
# Iterate over each cell.
for i in range(m):
for j in range(n):
cell = (i, j)
# No need to calculate the value of unreachable cell (building or grid edge).
if world[cell] == 1:
continue
model[cell] = {}
# For each possible direction, initialize the next cell and reward.
init(cell, directions[0], (i-1, j))
init(cell, directions[1], (i+1, j))
init(cell, directions[2], (i, j+1))
init(cell, directions[3], (i, j-1))
Давайте установим значения для конечной ячейки явно.
model[(8, 9)][directions[1]] = ((9, 9), 0) model[(9, 8)][directions[2]] = ((9, 9), 0)
Нам также нужна стартовая политика, поэтому мы создадим и ее.
# The policy is a two-level dictionary.
# The first key is the cell and the second key is the direction.
# For each cell-direction pair, the dictionary stores the probability
# of choosing that direction.
policy = {}
# Iterate over each cell.
for i in range(m):
for j in range(n):
cell = (i, j)
# No need to calculate the value of unreachable cell (building or grid edge).
if world[cell] == 1:
continue
policy[cell] = {}
# Initially, the directions are equiprobable. This will change.
policy[cell][directions[0]] = 0.25
policy[cell][directions[1]] = 0.25
policy[cell][directions[2]] = 0.25
policy[cell][directions[3]] = 0.25
Голый со мной. Код скоро станет понятным.
Существует множество способов обновления значений ячеек. Разработаны различные алгоритмы. Поскольку у нас есть модель мира, мы будем использовать динамическое программирование. Если бы у нас не было модели мира, мы могли бы использовать метод Монте-Карло. Выбранный алгоритм в основном влияет на то, как мы выполняем этап оценки политики.
Давайте немного углубимся в интуицию, стоящую за оценкой и улучшением политики.
Для динамического программирования оценка политики утверждает, что значение каждой ячейки представляет собой средневзвешенное значение значений ячеек, которые могут быть достигнуты напрямую, плюс вознаграждение. Веса — это вероятности выбора этого направления. Мы получим это в следующем разделе.
Улучшение политики одинаково для всех алгоритмов. Он жадно выбирает направление, которое минимизирует (или максимизирует) вознаграждение.
Теперь пришло время увидеть полный алгоритм.
# The state-value function.
# Initilly, the values are random. This will change.
V = np.random.normal(size=(m, n))
# Iterate for several epochs.
for _ in range(epochs):
# --- POLICY EVALUATION ---
for _ in range(evaluation_epochs):
# Iterate over each cell.
for i in range(m):
for j in range(n):
cell = (i, j)
# No need to calculate the value of unreachable cell (building or grid edge).
if world[cell] == 1:
continue
# The value of each cell is a weighted average of the values
# of the cells that can be reached directly plus the reward.
# The weights are the probabilities of choosing that direction.
# These are determined using the policy. Gamma controls the
# ammount of future influence.
value = 0
for direction in directions:
next_cell, reward = model[cell][direction]
value += policy[cell][direction] * (reward + gamma * V[next_cell])
V[cell] = value
# --- POLICY IMPROVEMENT ---
# Iterate over each cell.
for i in range(m):
for j in range(n):
cell = (i, j)
# No need to calculate the value of unreachable cell (building or grid edge).
if world[cell] == 1:
continue
# The direction that minimizes the cumulative reward is the one
# that we choose greedily.
min_value = float('inf')
direction_min_value = None
for direction in directions:
next_cell, reward = model[cell][direction]
value = reward + gamma * V[next_cell]
if value < min_value:
min_value = value
direction_min_value = direction
# We choose this direction by setting its probability
# to 1 and all others to 0.
for direction in directions:
if direction_min_value == direction:
policy[cell][direction] = 1
else:
policy[cell][direction] = 0
После 100 эпох это результат. Стрелки показывают оптимальные направления в каждой ячейке.
Увлекательно, не так ли?
Возможно, доставщику стоит заняться машинным обучением.
Математика
Теперь, когда вы интуитивно поняли, как работает этот алгоритм, давайте выведем уравнения.
Возвращаться
Что делает обучение с подкреплением уникальным, так это то, как оно обеспечивает оптимальное поведение — с помощью вознаграждений. Как мы уже говорили, каждое действие приносит вознаграждение, и цель состоит в том, чтобы максимизировать сумму всех вознаграждений. Это называется возврат.
Параметр гаммы определяет, как будущие вознаграждения влияют на доход. Если гамма равна 0, агент близорук, то есть использует только немедленное вознаграждение. Если гамма равна 1, агент дальновиден, то есть использует все награды.
Мы также можем записать это в красивой рекурсивной форме, как показано ниже.
Нам нужно быть осторожными при назначении вознаграждений, потому что это влияет на обучение.
Функция значения
Функция ценности — это метод количественной оценки того, насколько хорошо для агента находиться в определенном состоянии. Это ожидаемый доход от каждого состояния. Мы также можем учитывать пары состояние-действие. Первая называется функцией значения состояния, а вторая называется функцией значения действия. В разных алгоритмах используются разные функции значений. Мы сосредоточимся на функции значения состояния.
Поскольку функция значения зависит от политики, мы добавляем ее в качестве нижнего индекса к оператору ожидания.
Давайте распакуем выражение выше.
Приведенное выше обновление называется динамическим программированием. Вы можете видеть, как это зависит от модели среды — функции с четырьмя аргументами, p.
Политика
Политика — самая важная часть обучения с подкреплением, которую мы стремимся оптимизировать. Это аппарат принятия решений агентом. Он может быть детерминированным, то есть для каждого состояния существует точное действие, или может быть стохастическим, что означает, что для каждого состояния существует распределение вероятностей по множеству возможных действий.
Изначально политика однородна, то есть все действия равновероятны. Когда мы выполняем обновление политики для данного состояния, мы спрашиваем себя:
Если вместо этого я выберу другое действие, в частности действие, которое максимизирует немедленную отдачу, увеличится ли от этого общая отдача?
Если это жадное действие отличается от выбранного для данного конкретного состояния, то оно увеличит общий доход. Если это жадное действие совпадает с выбранным, то оно не увеличит общую отдачу, а это означает, что мы пришли к оптимальной политике.
Вы можете видеть, как функция значения зависит от политики, а политика зависит от функции значения. Эта взаимная зависимость порождает алгоритм обобщенной итерации политики.
Примечание
Общая проблема исследования и эксплуатации возникает при изучении оптимальной политики. Оптимальная политика медленно сходится к детерминированной политике, так как же можно исследовать действия, отличные от того, которое было изучено как оптимальное?
Решением этой проблемы является так называемый подход вне политики. В этом подходе используются две политики: одна, которая используется в функции значения состояния и является более исследовательской (эта не изменена), а другая, которую мы оптимизируем, является детерминированной политикой (которая изменена).
Обобщенная итерация политики (GPI)
Мы подошли к последней части головоломки: как эффективно выполнять обновления функции значения состояния и политики. Это алгоритм обобщенной итерации политики, который выполняет два прохода за несколько итераций. Первый — это оценка политики, которая обновляет эту функцию значения состояния с помощью ранее обновленной политики. Второе — это улучшение политики, которое обновляет политику с помощью ранее обновленной функции значения состояния. Мы можем показать этот алгоритм визуально.
E означает оценку политики, а I — улучшение политики.
Заключительное замечание
В зависимости от количества состояний существует два решения функции ценности обучения с подкреплением: 1) табличные решения и 2) приближенные решения. Если число состояний разумно, как в приведенной выше задаче, то табличные решения работают лучше всего. Они перечисляют каждое возможное состояние с его соответствующим значением. Однако, если количество состояний комбинаторное, как в игре в шахматы, предпочтительны приближенные решения. Они изучают параметрическую функцию, которая обобщается на несколько состояний (например, нейронная сеть).
В зависимости от того, есть у нас модель среды или нет, существует два метода: 1) методы на основе модели (называемые методами планирования) и 2) модель -бесплатные методы (называемые методами обучения). Если модель среды известна, как в приведенной выше задаче, то используются методы на основе модели, например. динамическое программирование. Они в основном связаны с табличными решениями. С другой стороны, если модель среды неизвестна, опять же, как игра в шахматы, то благоприятны безмодельные методы, напр. Монте-Карло. Они могут быть связаны как с табличными, так и с приближенными решениями.
Конец
Мы подошли к концу нашего путешествия. Я надеюсь, что этой статьей мне удалось пробудить в вас немного любопытства по теме обучения с подкреплением. Несмотря на то, что мы рассмотрели здесь много вопросов, это еще не все. Если вам интересно узнать больше по этой теме, я настоятельно рекомендую вам прочитать книгу «Введение в обучение с подкреплением» Ричарда Саттона и Эндрю Барто.
До скорого.
