Machine Learning

Pac-Man на основе Deep Q Network модели

Время прочтения: 7 мин.

Reinforcement Learning – одно из самых развивающихся и перспективных направлений машинного обучения. С помощью него можно попробовать разные действия исследуемого агента, сделать вывод об их успешности, накопить полученные знания и использовать их при будущем выборе. Такой подход используется, например, в переговорных ботах, где ведутся переговоры с клиентом, и есть цель – совершить самую выгодную сделку среди всех возможных, а также, например, такой алгоритм заложен в беспилотных автомобилях.

Reinforcement Learning также применяется в играх. Pac-Man это игра, в которой главный герой должен съесть как можно большее количество бриллиантов в лабиринте, при этом не попасться на своем пути монстрам, которые гоняются за ним, или не врезаться в стенку.

В RL существует агент и окружение вокруг него, в которой он совершает действия, чтобы максимизировать свое вознаграждение. Агент делает шаг, ему достается вознаграждение, среда вокруг него меняется, он снова ее анализирует и предпринимает следующий шаг. Так происходит до тех пор, пока не завершится среда. Такой цикл принятия решений известен как Markov decision process (MDP). В случае с Pac-Man завершением среды является встреча с монстром, а вознаграждение – это бриллианты. Игра моделируется с помощью объектно-ориентированного программирования, прописывается класс с объектами и методами, которые может совершать агент. Соответственно, state, action, reward вызываются из прописанных условий класса. Код на Python, с помощью которого можно получить текущее состояние представлен ниже.

# get current state as a vector of features
def get_state(obs):
    v = []
    x,y = obs['player']
    v.append(x)
    v.append(y)
    for x, y in obs['monsters']:
        v.append(x)
        v.append(y)
    for x, y in obs['diamonds']:
        v.append(x)
        v.append(y)
    for x, y in obs['walls']:
        v.append(x)
        v.append(y)
    return v

Агент — это алгоритм RL, а окружение – это, например, игра. Окружение отправляет свое начальное состояние агенту, а тот в ответ на это агент предпринимает действия. Далее окружение отправляет агенту новое состояние и награду, агент обновляет свои знания и снова предпринимает шаг.

Алгоритм DQN ищет наилучшую стратегию для совершения действия агента. Для этого рассчитывается значение Q по методу Q-learning, и выбирая его наибольшее значение, алгоритм сообщает агенту в каком направлении необходимо предпринять шаг. Эти значения Q рассчитываются с помощью нейронной сети на основе формулы Беллмана. Таким образом, на вход нейросети подается текущее состояние среды (s), а на выходе выдается значение Q(s, a) – все возможные действия с учетом текущего state и action. Код на Python представлен ниже.

# конструируем DQN
def dqn(shapes, actions):
    model = Sequential()
    model.add(Dense(units=64, input_shape=shapes, activation='relu'))
    model.add(Dense(units=64, activation='relu'))
    model.add(Dense(units=64, activation='relu'))
    model.add(Dense(actions, activation='linear'))
    return model

Архитектура DQN может быть описана в два шага: сначала идут несколько convolutional layers, а далее dense layers. В данной статье подробно описаны dense layers, так как в них указаны параметры, которые использовались для моделирования. Выходные значения нейронной сети являются наилучшим прогнозом агента о вознаграждении, которое он ожидает, если предпримет это действие. Такой подход называется value-based learning, в основе которого лежит функция Q(s, a). Она отражает общую ценность совершения действия a (action) в состоянии s (state), которая является общей суммой будущего вознаграждения r (reward), поправленную на фактор дисконтирования gamma. Уравнение представлено ниже. На каждом этапе агент предпринимает действия, которые приводят к максимальному вознаграждению.

Необходимо вычислить эти Q значения, однако агент не может видеть будущее и не может присвоить уникальное значение Q каждому из состояний. Для этого, как было сказано ранее, на помощь приходят нейронные сети, которые будут предсказывать наши Q значения. В RL на начальном этапе нет размеченных данных, и информация об окружении отсутствует. Таким образом, в RL создается свой собственный постоянно меняющийся набор данных, так как выбор действия сети напрямую влияет на то, каких состояний она достигнет, и сеть генерирует свои собственные целевые значения. Чтобы этого достичь, мы дублируем нейронную сеть или ‘target network’, чтобы сгенерировать целевые значения, и используем оригинальную нейронную сеть или ‘online network’, чтобы сгенерировать оценки. Тренируется только online network, но нужно достаточно часто копировать её веса в ‘target network’, чтобы освежить её более оптимизированными параметрами. Также мы используем ‘experience buffer’ – датасет прошлого опыта агента, который характеризуется набором (s, a, r, t, s’), где s (state), a (action), r (reward) – представляет их прошлые значения, t – это булевое значение, которое говорит, завершилась ли игра, s’ – это состояние после s (state), когда агент предпринял действие. Таким образом, агент просто перемещается по экрану на основе своего прошлого опыта и добавляет все свои знания в ‘experience buffer’. Затем можно извлечь опыт из хранилища и предпринять более эффективные действия в будущем.

number_of_steps = 200_000 # количество раз, сколько мы корректируем вес
w = 10_000 # первые итерации после перед началом обучения
interval_of_training = 5 #количество шагов, после которых мы корректируем веса
new_steps = 10_000 # количество шагов, после которых веса online network  копируются в target network
g = 0.99 # ставка дисконтирования
batch = 64 # размер батча
epsilon_maximum = 1.0 # epsilon max
epsilon_minimum = 0.05 # epsilon min
epsilon_decay_steps = int(number_of_steps/2)
learning = 0.001
online = dqn(shapes, actions)
online.compile(optimizer=Adam(learning_rate), loss='mse')
target = clone_model(online)
target.set_weights(online.get_weights())

# тренируем модель
step_first = 0 # our start
iteration = 0
do = True 
while step_first < number_of_steps:
    if do:
        observation = env.reset()
    iter += 1
    q = online.predict(np.array([get_state(observation)]))[0]  
    epsilon_for_training = max(epsilon_minimum, epsilos_maximum - (epsilon_maximum-epilons_minimum) * step_first/epsilon_decay_steps)
    action_go = epsilon_greedy(q, epsilon_for_training, actions)
    next_observation = env.make_action(action_go +1)
    r = next_obs["reward"]
    do = next_obs["end_game"]
    memory.append((observation, action_go , r, next_observation, do))
    observation = next_observation

    if iter >= w and iter % interval_of_training == 0:
        step += 1
        min_batch = random.sample(memory, batch)
        state = np.array([get_state(x[0]) for x in min_batch])
        action = np.array([x[1] for x in min_batch])
        rewards = np.array([x[2] for x in min_batch])
        next_state = np.array([get_state(x[3]) for x in min_batch])
        replay_done = np.array([x[4] for x in min_batch], dtype=int)
        target_for_action = rewards + (1-replay_done) * g * \
                                    np.amax(target.predict(next_state), axis=1)
        target = online.predict(state)  
        target[np.arange(batch), action] = target_for_action  
        online.fit(state, target, epochs=step, verbose=1, initial_epoch=step-1)
        if step_first % new_steps == 0:
            target.set_weights(online.get_weights())

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

Модель DQN решает эту проблему эффективным образом: инициализируется переменная epsilon от 0 до 1. Также для каждого шага генерируется случайное число от 0 до 1. Если это число меньше epsilon, то агент совершает действие совершенно случайным образом вне зависимости от значения Q. В процессе тренировки ставится epsilon до 0.1, чтобы в 90% времени обучения алгоритм действовал согласно значению Q, и в 10% времени совершал случайные движения. Epsilon нельзя ставить на уровне 0, чтобы Pac-Man не застрял в углу на неопределенный срок. Описанный метод называется ‘epsilon greedy’. Код на Python для данного метода представлен ниже:

def epsilon_greedy(q_values, epsilon, n_outputs):
    if random.random() < epsilon:
        return random.randrange(n_outputs)  # random action
    else:
        return np.argmax(q_values)  # q-optimal action

Таким образом, DQN с представленными параметрами дала в результате медиану больше 150 очков, что является хорошим результатом. Для достижения более высокого результата можно использовать более усовершенствованную версию DDQN (Double Deep Q Network).

Советуем почитать