Обучение с подкреплением (RL) — это область искусственного интеллекта, которая занимается изучением того, как оптимизировать поведение на основе функции вознаграждения. В этой истории у нас есть агент, изучающий задачу лабиринта, интегрированную с флагами и объектами.
Обучение с подкреплением направлено на поиск оптимальной политики, которая максимизирует совокупное вознаграждение с течением времени, уменьшенное за счет скидок. Другими словами, функция вознаграждения, которую агент пытается максимизировать, определяется состоянием агента и действием, которое он решает предпринять. Однако функция политики определяет, какое действие должен предпринять агент, основываясь на его состоянии и предыдущих знаниях о наградах [1].
Reward function: r(s, a) -> r Policy function: δ(s, a) -> s'
Обучение с подкреплением отличается от обучения с учителем тем, что агент обучения не имеет доступа к размеченным данным. Он также отличается от неконтролируемого обучения, которое обычно работает с немаркированными данными. В задачах обучения с подкреплением агент находит скрытые структуры своей среды, совершая действия и получая сигнал вознаграждения. Поэтому RL считается третьей ветвью машинного обучения [1].
Q-обучение
Одним из популярных подходов к RL является Q-learning, метод, основанный на ценностях, который стремится найти наилучшее действие в данном состоянии, оценивая максимальное ожидаемое будущее вознаграждение за каждое действие. В этом подходе агент пытается извлечь уроки из своей среды, передавая свой предыдущий опыт функции вознаграждения. Имея скорость обучения α и скорость дисконтирования γ, предыдущий опыт обновляется за счет новых действий и предписания функции вознаграждения [2].
Q(s, a) <- Q(s, a) + α[r + γ max Q(s’, a’) – Q(s, a)]
a’
Другими словами, таблица создается для каждой пары состояний и действий, а затем каждый регистр инициализируется нулем — пока просто считайте, что функция вознаграждения неположительна — и будет обновляться на протяжении всего этапа обучения реализации алгоритма [3] .
Хотя мы не собираемся предоставлять всестороннее введение в Q-обучение, мы считаем, что текущего обзора достаточно.
Проблема лабиринта
Цель задачи лабиринта — или крысы в лабиринте — найти путь от начальной точки к цели, пока путь не заблокирован никаким препятствием. В изучаемой версии есть некоторые флаги, которые следует собрать перед достижением цели. Кроме того, в лабиринте могут быть объекты, движение к которым приводит к их отталкиванию; некоторые толчки могут привести к блокировке допустимого пути, а некоторые другие толчки могут открыть путь к действительному пути. Следовательно, при разработке функции вознаграждения необходимо тщательное рассмотрение. Задача лабиринта представлена ниже, где агент обозначен синим цветом, цель - зеленым, а флажки - красным; Блоки представлены черными квадратами.
Теперь формализуем задачу.
I. Государства
Состояния этой задачи состоят из любого положения агента в среде лабиринта относительно его накопленных флагов. Это означает, что для n*m лабиринта с p флагами пространство состояний состоит из n*m*p состояний, из которых только одно является целевым состоянием. Обратите внимание, что в этом описании исключены толкаемые объекты (чтобы рассмотреть их, мы можем сосредоточиться на позициях, в которые они могут перемещаться, таким образом, для каждого объекта член, такой как o_i, будет умножен на исходное пространство).
Мы можем уменьшить количество состояний, исключив флаги в пространстве и изменив функцию вознаграждения таким образом, чтобы агент получал вознаграждение за каждый заработанный флаг и не мог выиграть игру, пока не будут заработаны все флаги. При этой попытке размер пространства уменьшится до n*m.
def take_a_step(self):
action_set = {"L":0,"U":0,"R":0,"D":0}
if self.agent[0] == 0: action_set.pop("U", None)
if self.agent[0] == self.env_0-1: action_set.pop("D", None)
if self.agent[1] == 0: action_set.pop("L", None)
if self.agent[1] == self.env_1-1: action_set.pop("R",None)
#...
Еще один способ уменьшить количество состояний — исключить блоки из допустимых позиций агента. Этот подход не считается эффективным, так как агент не сможет узнать о наличии блоков или их позициях. По этой причине данное изменение не было реализовано.
II. Целевое состояние
Как уже отмечалось, целевое пространство с первым определением состояний состояния, в котором агент находится в целевой позиции и является п-1 позицией 3-го измерения; это означает, что все флаги достигнуты.
Следуя второму определению состояний, целевое состояние — это состояние, в котором агент находится в целевой позиции и все флаги заработаны. Обратите внимание, как получение флага удалено от штатов.
Функция вознаграждения
Теперь, когда мы формализовали нашу проблему, мы можем определить функцию вознаграждения, которая позволяет агенту изучить оптимальный путь к целевому состоянию, соблюдая ограничения среды. Пока мы не рассматриваем объекты в окружении — это входит в часть 2.
Функция вознаграждения должна удовлетворять двум требованиям: во-первых, агент достигает цели, когда все флаги достигнуты, и, во-вторых, агент выбирает самый быстрый путь. Таким образом, мы хотим, чтобы наш агент не бродил туда-сюда между парой состояний. Поэтому мы пытаемся наказать агента, когда он посещает посещаемое состояние. Тем не менее, мы не хотим ограничивать агента в исследовании, поэтому повторное посещение состояния только один раз не будет сильно наказываться. Функция вознаграждения представлена ниже. Обратите внимание, что наказание агента при посещении базового состояния пропорционально количеству его предыдущих посещений.
def reward(self,action):
new_agent = self.find_position(action)
if self.visited[new_agent[0]][new_agent[1]]>=2:
return (-0.5*self.visited[new_agent[0]][new_agent[1]])/self.env_size
elif self.visited[new_agent[0]][new_agent[1]]>=1:
return 0.9/self.env_size
Кроме того, когда агент хочет двигаться к блоку, он будет наказан большим значением таким образом, что он проиграет игру, таким образом, агент никогда не посмеет двигаться к блоку ни при каких обстоятельствах.
#...
elif self.env[new_agent[0]][new_agent[1]]=="B":
return 10.0*self.env_lose
Кроме того, функция вознаграждения должна учитывать флаги — точнее, недостигнутые. когда агент входит в состояние, в котором его флаг не достигнут, функция вознаграждения выделяет агенту больше вознаграждений, чем обычно. Таким образом, агент вынужден получать флаги на пути к целевому состоянию. Кроме того, агент использует эти состояния флагов как точки в пространстве, чтобы найти свою цель.
#...
elif self.env[new_agent[0]][new_agent[1]]=="F":
self.achive_flag(new_agent)
Кроме того, агент должен быть вознагражден, когда он выполняет задачу. Следовательно, агент получает огромное вознаграждение, когда цель приближается и все флаги достигаются. Таким образом, мы надеемся, что окончательное вознаграждение будет передано обратно, и самый быстрый путь будет отличен от других.
#...
elif self.env[new_agent[0]][new_agent[1]]=="T" and len(self.flags)==0:
return 1*self.env_size
Кроме того, игра исключается, когда агент приближается к цели или когда агент не может оценить ценную будущую награду — ценная награда устанавливается больше -1.
Это определение функции вознаграждения гарантирует, что агент не войдет в состояние блокировки, потому что, если он войдет, его будущее вознаграждение будет меньше -1, и тогда игра будет исключена. Кроме того, агент вынужден получить все флаги перед входом в целевое состояние, потому что, если все флаги не будут достигнуты, он не выиграет.
Кроме того, обратите внимание, как каждое вознаграждение/наказание пропорционально размеру среды, чтобы иметь однородное распределение значений в Q-таблице любой проблемы.
def reward(self,action):
new_agent = self.find_position(action)
if self.env[new_agent[0]][new_agent[1]]=="B":
return 10.0*self.env_lose
elif self.env[new_agent[0]][new_agent[1]]=="F":
self.achive_flag(new_agent)
return 2*(self.env_size/self.flag_num)
elif self.env[new_agent[0]][new_agent[1]]=="T" and len(self.flags)==0:
return 1*self.env_size
elif self.visited[new_agent[0]][new_agent[1]]>=2:
return (-0.5*self.visited[new_agent[0]][new_agent[1]])/self.env_size
elif self.visited[new_agent[0]][new_agent[1]]>=1:
return 0.9/self.env_size
elif self.env[new_agent[0]][new_agent[1]]=='O':
#...
else:
return 1.0/self.env_size
Выбор действия
Способ, которым агент выбирает свое действие, основан на максимизации дисконтированных будущих вознаграждений; но таким образом, когда агент находит цель, он не будет исследовать окружающую среду в поисках лучших путей. Это означает, что исследование уменьшается, когда агент сосредоточен на эксплуатации. Поэтому для нашего агента мы рассматриваем некоторую степень случайности.
max_reward = max(action_set.values())
random.choice([k for (k, v) in action_set.items()
if v >= 0.8 * max_reward])
Таким образом, агент выбирает действие случайным образом, если оно удовлетворяет ограничению получения не менее 80% наилучшего вознаграждения.
Обучение
Во-первых, мы обучаем агента в легкой среде. Ниже показан лабиринт 9*9 с агентом и целью, расположенными в точках [0,0] и [4,4] соответственно, с шестью флажками, распределенными по доске.
Далее первый лабиринт решается по алгоритму и с помощью введенной функции вознаграждения. Четыре разные переменные для альфа и лямбда выбираются из набора {1, 0,75, 0,5, 0,1} — всего девять. И для каждого лабиринт разгадывается через 1000 эпох
n_epochs = 1000
fig = plt.figure(figsize=(20, 15))
fig.subplots_adjust(hspace=0.3, wspace=0.2)
plot_num = 0
for alpha_ in [1,0.75,0.5,0.1]:
for lambda_ in [1,0.75,0.5,0.1]:
plot_num+=1
tmaze = maze([
["W","W","W","W","B","W","F","W","W"],
["W","W","B","W","W","W","W","W","B"],
["F","W","B","B","F","B","B","W","W"],
["B","W","W","W","W","W","W","W","W"],
["B","W","B","B","W","W","W","W","B"],
["W","W","B","W","B","W","W","W","F"],
["W","F","W","W","B","W","W","B","W"],
["B","W","B","W","W","B","W","W","W"],
["B","B","B","B","B","W","W","W","F"]
],[0,0],[4,4])
tmaze.train(n_epochs,alpha_,lambda_)
ax = fig.add_subplot(4, 4, plot_num)
ax.set_title("alpha: "+str(alpha_)+", lambda: "+str(lambda_))
ax.plot(tmaze.train_curve)
plt.show()
Обобщенный результат обучения показан ниже. Для каждой эпохи выполняется новый алгоритм обучения относительно построенной Q-таблицы. Каждые две печатные строки показывают выбор агента и его вознаграждение в каждом состоянии, а также выбор, сделанный агентом на основе вознаграждения. Следовательно, эпизод каждой эпохи и измененные награды за выполнение действий можно получить из этого печатного вывода.
{'R': 0.004, 'D': 0.004}
>-> D
{'U': 0.0036400000000000004, 'R': 0.004, 'D': 0.004}
>-> R
{'L': 0.0036400000000000004, 'U': 0.004, 'R': -1.0, 'D': 0.004}
>-> U
{'L': 0.0036400000000000004, 'R': 0.004, 'D': 0.0036400000000000004}
>-> R
{'L': 0.0036400000000000004, 'R': 0.004, 'D': -1.0}
>-> R
{'L': 0.0036400000000000004, 'R': -1.0, 'D': 0.004}
>-> D
{'L': -1.0, 'U': 0.0036400000000000004, 'R': 0.004, 'D': -1.0}
>-> R
{'L': 0.0036400000000000004, 'U': -1.0, 'D': 0.004}
>-> D
{'L': -1.0, 'U': 0.0036400000000000004, 'D': 0.004}
>-> D
{'L': 0.004, 'U': 0.0036400000000000004, 'D': 2.5}
>-> D
R , 0.00 |R , 0.00 |R , 0.00 |D , 0.00 |L , 0.00 |
R , 0.00 |U , 0.00 |L , 0.00 |R , 0.00 |D , 0.00 |
U , 0.00 |L , 0.00 |L , 0.00 |L , 0.00 |D , 0.00 |
U , 0.00 |L , 0.00 |L , 0.00 |L , 0.00 |D , 2.50 |
U , 0.00 |L , 0.00 |L , 0.00 |L , 0.00 |L , 0.00 |
------------------------------------------------------------------
.
.
.
------------------------------------------------------------------
R , 0.03 |R , 0.03 |R , 0.03 |D , 0.03 |L , 0.00 |
R , 0.01 |U , 0.01 |L , 0.00 |R , 0.03 |D , 0.03 |
U , 0.00 |L , 0.00 |L , 0.00 |L , 0.00 |D , 0.12 |
U , 0.00 |L , 0.00 |L , 0.00 |L , 0.00 |D , 0.99 |
U , 0.00 |L , 0.00 |L , 0.00 |L , 0.00 |L , 0.00 |
Это обучающие графики для алгоритма для каждых 16 различных переменных для альфа и бета по 1000 итераций каждая. Обратите внимание, что чем больше длина итерации, тем лучше работает алгоритм, и если он не меняется от значения, обучение завершено. Кроме того, если выход равен 0, агент проигрывает игру.
Как видно, модели с лямбда=1 не смогли найти оптимизированный путь, потому что этот параметр используется для управления компромиссом между краткосрочным и долгосрочным вознаграждением при обновлении Q-таблицы. Лямбда = 1 означает, что агент будет считать долгосрочное вознаграждение столь же важным, как и краткосрочное вознаграждение, которое по некоторым причинам может привести к неудаче.
Первая проблема, с которой мы имеем дело, — это завышение значений Q, что приводит к неправильному выбору действий. Другими проблемами, вытекающими из этого выбора, являются медленная сходимость и неэффективное исследование.
Что дальше?
Будет решена еще одна проблема и обсуждены ограничения этого подхода. Кроме того, вводятся объекты, которые агент может перемещать, когда он движется к ним. Эти объекты — две стороны меча; их можно использовать, чтобы открыть путь или полностью его заблокировать. Таким образом, функция вознаграждения должна быть точно определена. Перейдите к части 2 по этой ссылке.
Обновленную версию кода можно найти в связанном репозитории.
Рекомендации
[1] Ричард С. Саттон и Эндрю Г. Барто, Обучение с подкреплением: введение
[2] Т. Митчелл, Машинное обучение.
[3] Сатиш Кумар, Простое обучение с подкреплением с использованием Q-таблиц.
