[Обучение с подкреплением] Метод Монте-Карло

Эта статья была впервые опубликована на:Уокер ИИ

введение

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

1. Оценка стратегии

Мы можем использовать метод Монте-Карло, чтобы узнать функцию ценности состояния, учитывая политику, то есть ожидаемую доходность в начале этого состояния — ожидаемое кумулятивное будущее дисконтированное вознаграждение, формула выглядит следующим образом:

v_\pi(s)=E_\pi[G_t|S_t=s]

То есть мы хотим оценить $v_\pi(s)$ значение, т.е. следовать политике $\pi$ Государство $s$ значение, мы можем рассчитать состояние первого посещения во всех раундах $s$ средняя доходность как $v_\pi(s)$ , этот метод является методом МК первого визита, соответственно другой метод вычисляет состояние каждого визита во всех раундах $s$ Средняя доходность – это метод MC за посещение.

чтобы оценить $v\pi(s)$ Стоимость заключается в оценке $q_\pi(s,a)$ . Поскольку функция значения состояния не может напрямую определять стратегию, когда модель неизвестна, нам нужно передать функцию значения действия состояния. $q_\pi(s,a)$ Чтобы решить. Мы используем эти два метода оценки для оценки $q_\pi(s,a)$ Это запросить доступ ко всем эпизодам $(s,a)$ Среднее значение полученных доходов.

Первое посещение потока алгоритма MC:

Вход: политика для оценки $\pi$

инициализация:

всем $s$ ∈ $S$ любой $V(s)\in R$

$Returns(s)\leftarrow$ пустой список для всех $s$ е $S$

Продолжайте повторять (для каждого хода):

использовать $\pi$ Создать раунд: $S_0,A_0,R_1,S_1,\dots,S_{T-1},A_{T-1},R_T$

$G\leftarrow0$

Для каждого шага петли в раунде, $t=T-1,T-2,\dots,0$ :

$G\leftarrow\gamma G+R_{t+1}$

если только $S_t$ появляться в $S_0,S_1,\dots,S_{t-1}$ середина:

будет $G$ добавить в список $Returns(s)$ середина

$V(s)\leftarrow average(Returns(s))$

2. Контроль политики

2.1 Обсуждение проблемы

После того, как у нас есть функция ценности, следующим шагом будет улучшение, чтобы аппроксимировать функцию оптимальной ценности и оптимальную политику.

Рисунок 1. Процесс управления политикой

Метод повышения политики предназначен для функции текущего значения, даже если политика является жадной. Нам просто нужно для каждого $s\in\S$ Выберите действие, которое максимизирует функцию ценности действия:

\pi(s)=argmax Q(s,a)

Тогда мы для каждого $\pi_{k+1}(s)$ взять все $Q_{\pi k}$ является жадным, поэтому мы получаем:

Q_{\pi k}(s,\pi_{k+1}(s))=Q_{\pi k}(s,argmaxQ_{\pi k}(s,a))\geq Q_{\pi k}(s,\pi_{k}(s))

То есть каждый $\pi_(k+1)$ чем $\pi_k$ Еще лучше, просто пройдите достаточное количество раундов, чтобы прийти к оптимальной политике и функции стоимости. Для сходимости этого процесса необходимо выполнение следующих двух предположений:

(a) У нас есть бесконечное количество раундов для оценки политики.

б) Раунды — это все способы исследования начала.

2.2 Рассмотрение первой гипотезы

Очевидно, невозможно проходить бесконечные эпизоды, и наш лучший способ здесь — это вписаться $q_{\pi k}$ Существует два основных метода укладки:

Метод 1: Сделайте каждую оценку стратегии бесконечно близкой $q_{\pi k}$ . Используя некоторые методы и некоторые предположения, и после достаточного количества шагов, вы можете гарантировать некоторую степень сходимости.

Метод 2. Откажитесь от попыток завершить оценку стратегии, прежде чем переходить к ее продвижению. На каждом шаге оценки мы сдвигаем функцию ценности к $q_{\pi k}$ Двигаться. Крайним примером является итерация значения, то есть один шаг итеративной оценки политики выполняется для каждого шага улучшения политики.

2.3 Обращение ко второй гипотезе

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

2.3.1 политическая стратегия

В частности, мы используем $\epsilon-greedy$ Стратегия, этот алгоритм на самом деле является компромиссом между разработкой и исследованием. т. е. выбирать действие с наибольшей оценочной ценностью действия большую часть времени, но все же $\epsilon$ Вероятность выбора случайного действия.

Алгоритм управления алгоритмом первого доступа согласно политике:

инициализация:

$\pi$ любой $\epsilon-soft$ Стратегия

всем $s\in S,a\in A(s)$ , любой $Q(s,a)\in R$

всем $s\in S,a\in A(s)$ , $Returns(s)\leftarrow$ пустой список

продолжайте зацикливаться:

следовать стратегии $\pi$ , сгенерировать раунд: $S_0,A_0,R_1,S_1,\dots,S_{T-1},A_{T-1},R_T$

$G\leftarrow 0$

За каждый шаг в этом раунде $t=T-1,T-2,\dots,0$ :

$G\leftarrow\gamma G+R_{t+1}$

если только $S_t,A_t$ появляется в $S_0,A_0,S_1,A_0,\dots,S_{t-1},A_{t-1}$ В:

будет $G$ Добавить в список $Returns(S_t,A_t)$ Средний

$Q(S_t,A_t)\leftarrow average(Returns(S_t,A_t))$

$A^*\leftarrow argmax Q(S_t,a)$

всем $a\in A(S_t)$ :

$\pi(a|S_t)\leftarrow \begin{cases} 1-\epsilon+\epsilon/|A(S_t)| & if\ a = A^* \\ \epsilon/|A(S_t)| & if\ a \neq A^* \end{cases}$

2.3.2 внеполитическая стратегия

Вне политики используются две стратегии для оценки стратегии и продвижения стратегии, одна из которых - стратегия поведения. $\mu$ : Исследовательская стратегия, предназначенная для создания эпизодов для накопления опыта; другая стратегия является целевой. $\pi$ : о поведенческих стратегиях $\mu$ Полученный опыт изучается, чтобы максимизировать вознаграждение и стать оптимальной политикой.

2.3.2.1 Выборка по важности в неполитических стратегиях

Выборка по важности — это оценка ожидаемого значения случайной величины в одном распределении, но выборка выборок из другого распределения. Метод применения выборки важности к внеполитике заключается в взвешивании вознаграждения в соответствии с отношением вероятностей траектории события, полученным в рамках целевой стратегии и стратегии поведения. Отношение двух вероятностей называется частотой выборки важности. заданное начальное состояние $\S_t$ , то в стратегии $\pi$ , траектория действия следующего состояния $A_t,S_{t+1},A_{t+1},\cdots,S_t$ Вероятность возникновения

\prod_{k=t}^{T-1}{\pi(A_k|S_k)p(S_{k+1}|S_k,A_k)}

в $p$ представляет собой функцию вероятности перехода состояния. Таким образом, частота выборки важности в соответствии с целевой политикой и политикой поведения составляет:

\rho_{t:T-1}=\frac{\prod_{k=t}^{T-1}{\pi(A_k|S_k)p(S_{k+1}|S_k,A_k)}}{\prod_{k=t}^{T-1}{\mu(A_k|S_k)p(S_{k+1}|S_k,A_k)}}=\prod_{k=t}^{T-1}\frac{\pi(A_k|S_k)}{\mu(A_k|S_k)}

Из приведенной выше формулы видно, что частота выборки важности в конечном итоге зависит только от двух стратегий и последовательностей и не имеет ничего общего с MDP. Далее следует формула стратегии оценки вне политики:

(1) Выборка исходной важности

V(s)=\frac{\sum_{t\in\tau(s)}^{}\rho_{t:T(t)-1}G_t}{|\tau(s)|}

(2) Взвешенная выборка важности

V(s)=\frac{\sum_{t\in\tau(s)}^{}\rho_{t:T(t)-1}G_t}{\sum_{t\in\tau(s)}^{}\rho_{t:T(t)-1}}

в $\tau(s)$ : представляет набор моментов, когда все состояния посещаются впервые в эпизоде.

$T(t)$ : от времени t до $T(t)$ с возвращением

$\{G_t\}_{t\in\tau(s)}$ : возврат, принадлежащий состоянию s

$\{\rho_{t:T-1}\}_{t\in\tau(s)}$ : представляет соответствующую частоту дискретизации важности

2.3.2.2 Инкрементальное усреднение

В дополнение к прямому способу вычисления среднего значения мы также можем вычислять среднее значение постепенно. Предположим, мы получаем серию возвратов $G_1,G_2\cdots,G_t-1$ , Для несогласованных с политикой, поскольку мы используем выборку по важности, существует дополнительный весовой коэффициент, и вес каждого возврата устанавливается как $W_k$

V_n=\frac{\sum_{k=1}^{n-1}W_kG_k}{\sum_{k=1}^{n-1}W_k}

Так что есть

V_{n+1}=V_n+\frac{W_n}{C_n}(G_n-V_n)

C_{n+1}=C_n+W_{n+1}

2.3.2.3 Алгоритм стратегии вне политики

Объединив предыдущую выборку по важности и пошаговое усреднение, мы можем получить алгоритм вне политики. Здесь наша поведенческая стратегия использует $\epsilon-soft$ , целевая политика является жадным алгоритмом.

Неполитический первый доступ к потоку алгоритма управления MC:

инициализация: для всех $s\in S,a\in A(s)$ :

$Q(s,a)\in R$ (случайное значение)

$C(s,a)\leftarrow0$

Продолжайте повторять (для каждого хода):

$b\leftarrow$ любое покрытие $\pi$ стратегия

Используйте стратегию $b$ Создать раунд: $S_0,A_0,R_1,S_1,\dots,S_{T-1},A_{T-1},R_T$

$G\leftarrow 0$

$W\leftarrow 1$

Цикл для каждого шага раунда, $t=T-1,T-2,\dots,0$ ,:

$G\leftarrow\gamma G+R_{t+1}$

$C(S_t,A_t)\leftarrow C(S_t,A_t)+W$

$Q(S_t,A_t)\leftarrow Q(S_t,A_t)+\frac{W}{C(S_t,A_t)}[G-Q(S_t,A_t)]$

$\pi(S_t)\leftarrow argmax Q(S_t,a)$

если $A_t\neq \pi(S_t)$ затем выйти из внутреннего цикла (перейти к следующему кругу)

$W\leftarrow W\frac{1}{b(A_t|S_t)}$

3. Примеры Блэкджек

3.1 Правила игры

Правила игры в блэкджек следующие: в игре участвуют игрок и дилер, и исходом каждого раунда может быть выигрыш игрока, выигрыш дилера или ничья. В начале раунда у игрока и дилера по две карты, и игрок может видеть две карты игрока и одну из карт дилера. Затем игрок может выбрать, хочет ли он больше карт. Если вы решите запросить больше карт (это называется «хит»), игрок может получить еще одну карту, и будет подсчитана сумма очков всех карт в руке игрока. Лицо A представляет 1 точку или 11 точек. Если сумма очков больше 21, говорят, что игрок проигрывает раунд, а выигрывает дилер; если сумма очков меньше 21, то игрок снова может решить, просить ли еще карты, пока не игрок больше не хочет больше карт. Если игрок не хочет больше карт, когда общее количество очков меньше или равно 21, то общее количество очков в руке игрока в этот момент является очком последнего игрока. Затем дилер открывает карту, которую он не открывал, и берет больше карт, если она меньше 17. Если общее количество очков дилера превышает 21 в процессе розыгрыша, дилер проигрывает раунд, а игрок выигрывает; если общее количество очков финального дилера меньше или равно 21, общее количество очков игрока и общее количество очков дилера сравниваются. Если сумма очков игрока больше суммы дилера, игрок выигрывает; если сумма очков игрока и дилера одинакова, это ничья; если сумма очков игрока меньше суммы дилера, выигрывает дилер.

3.2 Реализация кода

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

def obs2state(obs):
    # 将观测信息转换为状态信息
    return (obs[0], obs[1], int(obs[2]))
#策略评估
def evaluate(env, target_policy, behavior_policy, episode_num=500000):
    #初始化
    q = np.zeros_like(target_policy)#q（s,a）
    c = np.zeros_like(target_policy)#前 n 个回报下每个状态的累积权值
    for _ in range(episode_num):
        state_actions = []#状态动作键值对
        observation = env.reset()#获取观测值
        #使用行为策略生成一个回合
        while True:
            state = obs2state(observation)
            action = np.random.choice(env. action_space.n, p=behavior_policy[state])
            state_actions.append((state, action))
            obs, reward, done, _ = env.step(action)
            if done:
                break
        g = 0  # 回报
        rho = 1.  # 重要性采样比率
        for state, action in reversed(state_actions):
            g = gamma*g+reward #G←γG+Rt+1
            c[state][action] += rho #C(St,At)←C(St,At)+W
            q[state][action] += (rho / c[state][action]*(g - q[state][action]))#Q(St,At)←Q(St,At)+W/C(St,At)[G−Q(St,At)]
            rho *= (target_policy[state][action]/ behavior_policy[state][action])
            #W←W*π(At|St)/b(At|St)
            if rho == 0:
                break
    return q

#策略控制
def off_policy(env,target_policy,behavior_policy,espisode_num=500):
    q=np.zeros_like(target_policy)
    c=np.zeros_like(target_policy)
    for i in range(espisode_num):
        state_action=[]
        obs=env.reset()
        while True:
            state = obs2state(obs)
            action = np.random.choice(env.action_space.n,p=behavior_policy[state])
            state_action.append((state,action))
            observation, reward, done, _ = env.step(action)
            if done:
                break
            #完成了一个episode
        g=0 # 回报
        rho=1#重要性采样比率
        for state,action in reversed(state_action):
            g = gamma*g+reward #G←γG+Rt+1
            c[state][action]+=rho#C(St,At)←C(St,At)+W
            q[state][action]+=(rho / c[state][action]*(g - q[state][action]))#Q(St,At)←Q(St,At)+W/C(St,At)[G−Q(St,At)]
            #策略提升 π(St)←argmaxaQ(St,a)
            a =q[state].argmax()
            target_policy[state]=0
            target_policy[state][a]=1
            if a!=action:
                break
        rho /= behavior_policy[state][action]
    return target_policy,q

3.3 Экспериментальные результаты

Рисунок 2. Эпизод

Один из эпизодов показан на рисунке.В начале игрок получил карту [1,4], дилер показал 5, и стратегия решила попросить карту (действие 1). , карта игрока [1,4,9], а награда 0, стратегия продолжает решать запросить карту В итоге наблюдение за следующим раундом показывает, что сумма карт игрока равна 23 очков, что превышает 21 очко, поэтому игра заканчивается, вознаграждение равно -1, и побеждает дилер.

График оптимальной стратегии выглядит следующим образом:

Рисунок 3. График оптимальной стратегии

с тузом: используется туз, т. е. a равно 1. без туза: туз не используется, т. е. a равно 11. Видно, что на графике оптимальной стратегии без туза: в большинстве случаев предпочитают не повышать , с тузом: в Когда общее количество игроков меньше 18, велика вероятность того, что они продолжат добавлять карты.

4 Резюме

(a) Метод Монте-Карло — это метод обучения для оценки функции ценности и поиска оптимальной политики. В отличие от DP, нам не нужно полное знание окружающей среды. Методы Монте-Карло требуют только последовательности эмпирических выборок состояний, действий и вознаграждений за фактические или смоделированные взаимодействия с окружающей средой.

(b) Методы Монте-Карло выбирают и усредняют вознаграждения для каждой пары состояние-действие.

(c) Оценка политики оценивает функцию ценности действий государства через среднюю доходность. Повышение политики использует жадную политику $\pi(s)=argmax q(s,a)$

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

5 ссылок

[1]Reinforcement Learning

Обратите внимание на общедоступную учетную запись WeChat [Potential Technology], чтобы узнать актуальную информацию.

Уокер ИИ (Chengdu Potential Artificial Intelligence Technology Co., Ltd., xingzhe.ai)Стремление использовать искусственный интеллект и технологии машинного обучения для повышения производительности индустрии игр и развлечений и продолжать улучшать пользовательский опыт в отрасли. У нас есть команда по безопасности контента, команда игровых ботов, команда платформы данных, умная музыкальная команда и команда автоматического тестирования. > >Если у вас есть сильное любопытство к миру, вы не боитесь сложных проблем; вы можете мириться со всеми видами неопределенности в процессе исследования и настойчивы; вы можете находить новаторские способы решения проблем, и в то же время время иметь все детали Подотчетность для обеспечения эффективной реализации решений. Тогда, пожалуйста, отправьте нам свое резюме, соответствующие достижения в работе и позиции, которые вас интересуют. Мы приглашаем людей, которые принимают вызовы и мыслят новаторски, присоединиться к нашей команде. пожалуйста, свяжитесь с:hr@xingzhe.ai

Если у вас есть какие-либо потребности, связанные с безопасностью контента, игровыми ботами, платформами данных, умной музыкой и автоматическим тестированием, мы также будем рады вам помочь. Вы можете связаться:contact@xingzhe.ai