Введение

Добро пожаловать во вторую статью из серии, посвященной обучению с подкреплением (RL) и его приложениям. Сегодня мы увидим более сложное применение этой техники искусственного интеллекта.

Давайте начнем!

Теоретические основы

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

Этот метод изучает, как люди учатся на собственном опыте, взаимодействуя с окружающей средой. В частности, последний получает в качестве входных данных состояние агента s и выбранное действие a и возвращает вознаграждение a r и новое состояние s '. Более того, на любом этапе агент выбирает действие в соответствии с политикой 𝞹: 𝞹 (a | s) = P (Aₜ = a | Sₜ = s).

Можно выделить три фазы обучения с подкреплением. В первом, называемом предсказанием, мы хотим спрогнозировать функцию значения состояния v (s) = E (Gₜ | Sₜ = s) и функция значения действия q (s, a) = r + v (s '). Здесь r - это награда за действие a, а s ’ - это состояние прибытия. Мы определяем эти два прогноза с помощью метода Монте-Карло и путем выборки опыта в соответствии с политикой 𝞹. На втором этапе улучшения мы хотим найти политику 𝞹 ’ лучше, чем 𝞹. Наконец, в контрольном мы заинтересованы в оптимальной функции значения состояния v * (s) = max v (s) и в функции оптимального значения действия q * (s, a) = max q (s, a), где максимум вычисляется среди всех политик 𝞹. В конце концов, мы можем определить оптимальную политику как политику достижения максимального значения состояния или функции значения действия.

Давайте сосредоточимся на одном приложении.

Как найти кратчайший путь

Первое приложение RL, которое я хочу показать, - это обобщение проблемы выхода из лабиринта, которую мы изучали в предыдущей статье (если вы ее пропустили, посмотрите https://medium.com/betacom/an- Введение в обучение с подкреплением-b749abd1f281 ). В частности, мы заинтересованы в поиске наилучшего пути от начальной точки A до точки прибытия B, и поэтому мы ищем кратчайшую траекторию, которая соединяет две точки. Но, как в лабиринте есть препятствия, создаваемые стенами, так и в этой ситуации есть элементы, неизвестные агенту, которые могут повлиять на его путешествие. Например, мы можем рассмотреть поездку в Италию из Турина в Неаполь, где он может встретить светофор или череду автомобилей, которые замедляют поездку. На дороге также могут быть работы, которые вынуждают его изменить направление, или он может выехать на шоссе с более быстрой траекторией. В другой поездке он также может отправиться на остров, и ему придется сесть на паром и заплатить за него. Как вы понимаете, во время поездки может возникнуть множество неизвестных аспектов, и лучший способ справиться с ними - это многократно повторять одно и то же задание, чтобы научиться избегать самых плохих дорог. Итак, каждый раз, когда агент повторяет путешествие, он начинает понимать, какие улицы оживленные и на каких из них есть работы. Таким образом, он заменяет эти части путешествия другими. В конце концов, он может обнаружить, что лучший путь может быть не более прямым, а более сложным, позволяющим избежать движения и дорожных работ. Давайте возьмем пример, посмотрев на следующий график.

Как вы можете видеть, на изображении связи между итальянскими городами показаны с помощью двусторонних стрелок, таких как стрелка между Турином и Флоренцией, или однонаправленных стрелок, например, между Турином и Миланом, которые допускают наличие улиц с односторонним движением. Кроме того, на некоторых из них есть специальные символы: светофоры, знаки дорожных работ, паромы, шоссе. Посмотрим на их эффекты. Светофор замедляет поездку, дорожные работы вынуждают агента вернуться в город, из которого он приехал, и изменить направление. Шоссе ускоряет путешествие, а паромы, которые используются для прибытия и отъезда из Палермо, дороги. Обратите внимание, что на пути между Палермо и Турином есть красный крест, это означает, что он не уходит.

Прежде чем переходить к примеру, давайте введем определение графа. В этой статье мы используем ориентированный граф G, который определяется набором вершин V, также называемых узлами (в нашем случае городами), и набором ориентированных ребер (строк).

Давайте углубимся в детали этого приложения.

Во-первых, мы определяем агента как водителя, а окружающую среду как дорогу. Состояние агента s - это город, в котором он находится в каждый момент времени t, а действия - это направления, в которых он может двигаться. Чтобы идентифицировать их, мы можем обозначить их названием города прибытия. Глядя на рисунок, мы видим, что доступные действия в мегаполисе различаются. Например, если агент находится в Турине, он может отправиться в Милан, Венецию, Болон или Флоренцию, но не может выбрать направление, которое приведет его в Палермо или любой другой город. Вместо этого, если он во Флоренции, он может поехать в Турин, Флоренцию или Рим.

На этом этапе мы должны определить награды за каждое действие. Предположим, что, если агент следует по дороге без препятствий, он получает награду в размере -2, таким образом он находит кратчайший путь, ведущий к своему конечному пункту назначения. В противном случае, если он встречает светофор, он получает -5, так как ему приходится ждать долго и он хочет их избежать, в то время как, если он едет по шоссе, он получает -1, потому что он может ехать быстрее. Если ведутся дорожные работы или паром недоступен, среда возвращает награду -10, а последующее состояние устанавливается равным исходному. Итак, как мы уже говорили, дорожные работы и неотъезжающий паром имеют тот же эффект, что и стены в лабиринте. Более того, если агент решает сесть на паром, он должен заплатить, и поэтому он получает вознаграждение в размере -3. В конце концов, когда водитель достигает места назначения, он получает +100.

На следующем изображении мы видим награды за каждое действие. Конечно, агент не может получить доступ к этой информации, поскольку окружающая среда ему неизвестна. Теперь предположим, что он идет из Турина в Неаполь по желтому пути: Турин-Милан-Болон (Внимание! Идут дорожные работы, и продавец возвращается в Милан) -Вениция-Болон-Флоренция-Палермо-Рим-Неаполь.

В этом конкретном случае агент выбирает очень плохие действия: он столкнулся с дорожными работами, светофором, и он садится на паром, но он также использует шоссе, поэтому в конечном итоге его возвращение составляет -1 -2 * 3 -3 * 2– 5 -10 +100 = 72. Он маленький, поэтому в следующих итерациях он выберет различные действия, чтобы улучшить его. Если мы посмотрим на график, то легко увидим, что лучший путь - Турин-Флоренция-Рим -Наполь, где доходность +94, очень высокий результат. Таким образом, даже если есть автомагистрали, ускоряющие поездку, лучшим решением будет то, что они не будут использоваться, и вначале агент должен выбрать неоптимальное действие, избегая шоссе.

Давайте посмотрим, как реализовать этот пример.

Прежде чем рассматривать основную функцию, мы должны ввести eps_greedy_action, используемый для определения ε-жадного действия из заданного состояния. Таким образом, с вероятностью ε агент выберет случайное действие, а с вероятностью 1- ε, если мы уже определили жадное действие для этого состояния , жадный.

def eps_greedy_action(proposed_action, eps, actions, state):
    p = np.random.random()
    if p < (1 - eps) and proposed_action is not None:
        return proposed_action
    else:
        return np.random.choice(actions[state])

После этого мы должны определить все состояния, доступные действия для каждого из них и их награды. После этого мы можем выполнить функцию под названием trip, которая определяет эпизод, чтобы мы могли собирать выбранные действия и значение действия для каждой пары (состояния, действия) от Турина до Неаполя.

import numpy as np
def trip(actions,rewards,proposed_action,eps,returns,V,Q):
   state = 'Turin'
   history = []
   while state != 'Naples':
       action = eps_greedy_action(proposed_action[state],epsilon,                                                                              available_actions, state)
       history.append((state,action))
       if rewards[(state,action)]!=-10:
           new_state = action
       else:
           new_state = state
       state = new_state
   G = 0
   for (state,action) in list(reversed(history)):
       G = G + rewards[(state,action)]
       t = history.index((state,action))
       if state not in [h[0] for h in history][:t]:
           returns[state].append(G)
           V[state] = np.average(returns[state])
       
       if rewards[(state,action)]!=-10:
           new_state = action
       else:
           new_state = state
       Q[(state,action)]=V[new_state]+rewards[(state,action)]
return Q

В предыдущей функции мы указываем начальную точку как Турин и инициализируем пустой список с именем history, который будет содержать посещенные состояния. После этого агент входит в цикл while и выбирает следующее действие, пока не достигнет Неаполя. Действие выбирается с помощью функции eps_greedy_action, и в конце цикла мы указываем новое состояние. Теперь мы вычисляем окончательный возврат G и добавляем это инкрементное значение к возврату каждого посещенного состояния. Мы вычисляем значение состояния для всех из них, усредняя их доходность, как показано в псевдокоде в предыдущей статье (https://medium.com/betacom/an-introduction-to-reinforcement-learning-b749abd1f281). Наконец, мы определяем значение действия для состояний, которые мы посетили в этом эпизоде, обновляя значение в словаре Q, и возвращаем его.

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

for t in range(10000):
    Q = trip(available_actions,rewards,proposed_action, 0.7,returns,V,Q)
    for state in states:
        actions_rewards = {}
        for a in available_actions[state]:
            actions_rewards[a] = Q[(state,a)]
        proposed_action[state] = max_dict(actions_rewards)[0]

Благодаря этому циклу for мы можем повторить 10.000 раз функцию trip. F или на каждой итерации мы обновляем значение hibited_action для каждого состояния до действия с наибольшим вознаграждением. Таким образом, на следующей итерации мы выберем это действие (жадное) или случайное. В этом примере мы выбираем жадное действие с вероятностью 0,7, но его можно изменить, чтобы сбалансировать исследование и эксплуатацию, как описано в предыдущей статье. С такими гиперпараметрами последней поездкой может стать Турин-Флоренция-Рим-Неаполь, что, как уже говорилось, является лучшим. Таким образом, путешественник учится избегать дорожных работ и неотходящего парома по своему желанию.

Заключение

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

Увидимся в следующий раз!