Решение MDP с помощью Q-Learning с нуля - глубокое обучение с подкреплением для хакеров (часть 1)

Решение MDP с помощью Q-Learning с нуля - глубокое обучение с подкреплением для хакеров (часть 1)

Пришло время узнать о функциях ценности, уравнении Беллмана и Q-обучении. Вы будете использовать все эти знания для создания MDP и обучения своего агента использованию Python. Готовы получить это мороженое?

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

Скидка на будущую награду

Зачем нужен коэффициент скидки γ? Общее вознаграждение, которое ваш агент получит с текущего временного шага t до конца задачи, можно определить как:

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

Наш агент будет отлично работать, если выберет действие, которое максимизирует (дисконтированное) будущее вознаграждение на каждом этапе.

Функция значения

Было бы здорово узнать, насколько «хорошо» данное состояние s. Кое-что сказать нам: независимо от того, в каком состоянии вы находитесь, если вы перейдете в состояние s, ваша общая награда будет x, слово! Если вы начнете с s и будете следовать политике π. Это избавило бы нас от повторного посещения одних и тех же состояний снова и снова. Функция значения делает это за нас. Это зависит от состояния, в котором мы находимся s, и политики π, которой придерживается ваш агент. Это дает:

Существует функция оптимального значения, которая имеет наивысшее значение для всех состояний. Выдается:

Q функция

Тем не менее, ваш агент не может напрямую контролировать, в каком состоянии он окажется. Он может повлиять на это, выбрав какое-нибудь действие a. Давайте представим еще одну функцию, которая принимает состояние и действие в качестве параметров и возвращает ожидаемое общее вознаграждение - функцию Q (она представляет «качество» определенного действия при заданном состоянии). Более формально функция Q^π(s, a) дает ожидаемый результат при запуске в s, выполнении aa и следующих за π.

Опять же, мы можем определить оптимальную Q-функцию Q∗(s, a), которая дает ожидаемое общее вознаграждение для вашего агента при запуске с s и выбирает действие a. То есть оптимальная Q-функция сообщает вашему агенту, насколько хорош выбор a в состоянии s.

Между двумя оптимальными функциями V∗ и Q∗ существует взаимосвязь. Это дает:

То есть максимальное ожидаемое общее вознаграждение при запуске с s составляет максимум Q∗(s, a) по всем возможным действиям.

Используя Q∗(s, a), мы можем извлечь оптимальную политику π∗, выбрав действие aa, которое дает максимальное вознаграждение Q∗(s, a) для состояния s. У нас есть:

Между всеми функциями, которые мы определили до сих пор, существует хорошая взаимосвязь. Теперь у вас есть инструменты для определения состояний и пар состояние-действие как хороших или плохих. Что еще более важно, если вы можете идентифицировать V∗ или Q∗, вы сможете создать лучший агент из возможных (для текущей среды). Но как это использовать на практике?

Обучение с помощью Q-Learning

Давайте сосредоточимся на одном состоянии s и действии a. Мы можем выразить Q(s, a) рекурсивно через значение Q следующего состояния s′:

Это уравнение, известное как уравнение Беллмана, говорит нам, что максимальное будущее вознаграждение - это вознаграждение, полученное агентом за переход в текущее состояние s плюс максимальное будущее вознаграждение за следующее состояние _33 _ . Суть Q-обучения в том, что мы можем итеративно аппроксимировать Q∗, используя уравнение Беллмана, описанное выше. Уравнение Q-обучения задается следующим образом:

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

Может ли ваш агент чему-нибудь научиться, используя это? Во-первых - нет, начальные приближения, скорее всего, будут совершенно случайными / неверными. Однако по мере того, как агент исследует все больше и больше окружающей среды, приблизительные значения Q начнут сходиться к Q∗.

Создание окружающей среды

Ладно, пора достать мороженое. Давайте сначала попробуем простой случай:

Исходное состояние выглядит так:

ZOMBIE = "z"
CAR = "c"
ICE_CREAM = "i"
EMPTY = "*"

grid = [
    [ICE_CREAM, EMPTY],
    [ZOMBIE, CAR]
]

for row in grid:
    print(' '.join(row))

>

i *
z c

Мы обернем состояние нашей среды в класс, который содержит текущую сетку и положение машины. Наличие постоянного доступа к положению машины на каждом этапе поможет нам упростить наш код:

class State:
    
    def __init__(self, grid, car_pos):
        self.grid = grid
        self.car_pos = car_pos
        
    def __eq__(self, other):
        return isinstance(other, State) and self.grid == other.grid and self.car_pos == other.car_pos
    
    def __hash__(self):
        return hash(str(self.grid) + str(self.car_pos))
    
    def __str__(self):
        return f"State(grid={self.grid}, car_pos={self.car_pos})"

Все возможные действия:

UP = 0
DOWN = 1
LEFT = 2
RIGHT = 3

ACTIONS = [UP, DOWN, LEFT, RIGHT]

и начальное состояние:

start_state = State(grid=grid, car_pos=[1, 1])

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

from copy import deepcopy

def act(state, action):
    
    def new_car_pos(state, action):
        p = deepcopy(state.car_pos)
        if action == UP:
            p[0] = max(0, p[0] - 1)
        elif action == DOWN:
            p[0] = min(len(state.grid) - 1, p[0] + 1)
        elif action == LEFT:
            p[1] = max(0, p[1] - 1)
        elif action == RIGHT:
            p[1] = min(len(state.grid[0]) - 1, p[1] + 1)
        else:
            raise ValueError(f"Unknown action {action}")
        return p
            
    p = new_car_pos(state, action)
    grid_item = state.grid[p[0]][p[1]]
    
    new_grid = deepcopy(state.grid)
    
    if grid_item == ZOMBIE:
        reward = -100
        is_done = True
        new_grid[p[0]][p[1]] += CAR
    elif grid_item == ICE_CREAM:
        reward = 1000
        is_done = True
        new_grid[p[0]][p[1]] += CAR
    elif grid_item == EMPTY:
        reward = -1
        is_done = False
        old = state.car_pos
        new_grid[old[0]][old[1]] = EMPTY
        new_grid[p[0]][p[1]] = CAR
    elif grid_item == CAR:
        reward = -1
        is_done = False
    else:
        raise ValueError(f"Unknown grid item {grid_item}")
    
    return State(grid=new_grid, car_pos=p), reward, is_done

В нашем случае одна серия начинается с начального состояния и врезается в зомби или ест мороженое.

Учимся водить

Хорошо, пора реализовать алгоритм Q-Learning и получить мороженое. У нас действительно небольшое пространство состояний, всего 4 состояния. Это позволяет упростить задачу и сохранить вычисленные значения Q в таблице. Начнем с некоторых констант:

import numpy as np
import random

random.seed(42) # for reproducibility

N_STATES = 4
N_EPISODES = 20

MAX_EPISODE_STEPS = 100

MIN_ALPHA = 0.02

alphas = np.linspace(1.0, MIN_ALPHA, N_EPISODES)
gamma = 1.0
eps = 0.2

q_table = dict()

Мы будем снижать скорость обучения, alpha, в каждом эпизоде ​​- по мере того, как ваш агент исследует все больше и больше окружающей среды, он «поверит», что ему осталось не так уж и много учиться. Дополнительно определены ограничения на количество тренировочных эпизодов и шагов.

Dicts в Python могут быть немного неуклюжими, поэтому мы используем вспомогательную функцию q, которая дает значение Q для пары состояние-действие или для всех действий с учетом состояния:

def q(state, action=None):
    
    if state not in q_table:
        q_table[state] = np.zeros(len(ACTIONS))
        
    if action is None:
        return q_table[state]
    
    return q_table[state][action]

Выбрать действие с учетом текущего состояния действительно просто - действуйте случайным образом с некоторой небольшой вероятностью или наилучшим действием, которое мы видели до сих пор (используя наш q_table):

def choose_action(state):
    if random.uniform(0, 1) < eps:
        return random.choice(ACTIONS) 
    else:
        return np.argmax(q(state))

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

Далее обучим вашего агента с помощью алгоритма Q-обучения:

for e in range(N_EPISODES):
    
    state = start_state
    total_reward = 0
    alpha = alphas[e]
    
    for _ in range(MAX_EPISODE_STEPS):
        action = choose_action(state)
        next_state, reward, done = act(state, action)
        total_reward += reward
        
        q(state)[action] = q(state, action) + \
                alpha * (reward + gamma *  np.max(q(next_state)) - q(state, action))
        state = next_state
        if done:
            break
    print(f"Episode {e + 1}: total reward -> {total_reward}")

>

Episode 1: total reward -> 999
Episode 2: total reward -> 998
Episode 3: total reward -> 997
Episode 4: total reward -> 997
Episode 5: total reward -> 999
Episode 6: total reward -> 999
Episode 7: total reward -> 998
Episode 8: total reward -> -100
Episode 9: total reward -> -101
Episode 10: total reward -> 999
Episode 11: total reward -> 999
Episode 12: total reward -> 999
Episode 13: total reward -> 999
Episode 14: total reward -> 999
Episode 15: total reward -> 999
Episode 16: total reward -> 998
Episode 17: total reward -> 999
Episode 18: total reward -> 999
Episode 19: total reward -> 999
Episode 20: total reward -> 999

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

Вы можете ясно заметить, что агент очень быстро учится действовать эффективно. Наш MDP действительно маленький, и это могло быть просто счастливой случайностью. Тем более, что смотрю некоторые эпизоды. вы можете видеть, что агент ударил зомби.

Он чему-то научился?

Давайте извлечем политику, усвоенную вашим агентом, выбирая действие с максимальным значением Q на каждом шаге, мы будем делать это вручную, как босс. Во-первых, start_state:

r = q(start_state)
print(f"up={r[UP]}, down={r[DOWN]}, left={r[LEFT]}, right={r[RIGHT]}")

>

up=998.99, down=225.12, left=-85.10, right=586.19

У UP, кажется, самое высокое значение Q, давайте сделаем следующее:

new_state, reward, done = act(start_state, UP)

Новое состояние выглядит так:

Что лучше всего делать сейчас?

r = q(new_state)
print(f"up={r[UP]}, down={r[DOWN]}, left={r[LEFT]}, right={r[RIGHT]}")

>

up=895.94, down=842.87, left=1000.0, right=967.10

Но, конечно, если вы пойдете налево, вы получите мороженое! Ура! Кажется, ваш агент знает, что здесь что-то не так.

Разве это не потрясающе? Ваш агент ничего не знает о «правилах игры», но ему удается узнать, что зомби - плохие, а мороженое - великолепное! Кроме того, он пытается как можно быстрее добраться до мороженого. Награда кажется окончательным сигналом, который движет процессом обучения.

Мы закончили! Теперь вы можете создавать сложные агенты, которые быстро находят оптимальные политики. За исключением, может быть, нет. Это был очень простой MDP. Далее мы узнаем, как нейронные сети вписываются в структуру обучения с подкреплением.

Первоначально опубликовано на сайте curiousily.com 8 декабря 2017 г.

Нравится то, что вы читаете? Хотите узнать еще больше о машинном обучении?