17.2. Итерация значений¶
В этом разделе мы обсудим, как выбрать наилучшее действие для робота в каждом состоянии, чтобы максимизировать возврат траектории. Мы опишем алгоритм, называемый итерацией значений, и реализуем его для смоделированного робота, перемещающегося по замерзшему озеру.
17.2.1. Стохастическая политика¶
Стохастическая политика, обозначаемая как \(\pi(a \mid s)\) (для краткости — политика), представляет собой условное распределение вероятностей действий \(a \in \mathcal{A}\) при заданном состоянии \(s \in \mathcal{S}\), \(\pi(a \mid s) \equiv P(a \mid s)\). В качестве примера рассмотрим робота, имеющего четыре действия \(\mathcal{A}=\) {идти влево, идти вниз, идти вправо, идти вверх}. Политика в состоянии \(s \in \mathcal{S}\) для такого набора действий \(\mathcal{A}\) представляет собой категориальное распределение, в котором вероятности четырёх действий могут быть равны \([0.4, 0.2, 0.1, 0.3]\); в другом состоянии \(s' \in \mathcal{S}\) вероятности \(\pi(a \mid s')\) тех же четырёх действий могут составлять \([0.1, 0.1, 0.2, 0.6]\). Обратите внимание, что для любого состояния \(s\) должно выполняться условие \(\sum_a \pi(a \mid s) = 1\). Детерминированная политика является частным случаем стохастической политики, при котором распределение \(\pi(a \mid s)\) присваивает ненулевую вероятность только одному конкретному действию, например, \([1, 0, 0, 0]\) в нашем примере с четырьмя действиями.
Чтобы сделать обозначения менее громоздкими, мы будем часто записывать \(\pi(s)\) вместо \(\pi(a \mid s)\) в качестве условного распределения.
17.2.2. Функция значения¶
Представим теперь, что робот начинает движение из состояния \(s_0\) и на каждом временном шаге сначала выбирает действие согласно политике \(a_t \sim \pi(s_t)\), после чего выполняет это действие, переходя в следующее состояние \(s_{t+1}\). Траектория \(\tau = (s_0, a_0, r_0, s_1, a_1, r_1, \ldots)\) может различаться в зависимости от того, какое именно действие \(a_t\) было выбрано на промежуточных шагах. Определим среднее возвращение \(R(\tau) = \sum_{t=0}^\infty \gamma^t r(s_t, a_t)\) всех таких траекторий.
где \(s_{t+1} \sim P(s_{t+1} \mid s_t, a_t)\) — это следующее состояние робота, а \(r(s_t, a_t)\) — мгновенное вознаграждение, полученное при выполнении действия \(a_t\) в состоянии \(s_t\) в момент времени \(t\). Это называется функцией значения для политики \(\pi\). Проще говоря, значение состояния \(s_0\) для политики \(\pi\), обозначаемое как \(V^\pi(s_0)\), — это ожидаемое дисконтированное по коэффициенту \(\gamma\) возврат, который получит робот, если начнёт из состояния \(s_0\) и будет выполнять действия в соответствии с политикой \(\pi\) на каждом шаге времени.
Далее мы разбиваем траекторию на два этапа: (i) первый этап, соответствующий \(s_0 \to s_1\) при выполнении действия \(a_0\), и (ii) второй этап, представляющий собой траекторию \(\tau' = (s_1, a_1, r_1, \ldots)\), следующую далее. Ключевая идея, лежащая в основе всех алгоритмов обучения с подкреплением, заключается в том, что значение состояния \(s_0\) можно выразить как сумму среднего вознаграждения, полученного на первом этапе, и функции значения, усреднённой по всем возможным следующим состояниям \(s_1\). Это вполне интуитивно понятно и следует из нашего марковского предположения: среднее вознаграждение из текущего состояния равно сумме среднего вознаграждения из следующего состояния и среднего вознаграждения за переход в следующее состояние. Математически мы записываем два этапа следующим образом:
Это разложение обладает большой силой: оно лежит в основе принципа динамического программирования, на котором базируются все алгоритмы обучения с подкреплением. Обратите внимание, что на втором этапе вычисляются два математических ожидания: одно по выбору действия \(a_0\), совершаемого на первом этапе с использованием стохастической политики, а другое — по возможным состояниям \(s_1\), полученным в результате выбранного действия. Мы можем записать (17.2.2) через вероятности переходов в марковском процессе принятия решений (MDP) следующим образом:
Важно отметить, что приведённое выше тождество верно для всех состояний \(s \in \mathcal{S}\), поскольку любую траекторию, начинающуюся в таком состоянии, можно разбить на два этапа.
17.2.3. Функция значения действия¶
В реализациях часто полезно поддерживать величину, называемую функцией «значения действия», которая тесно связана с функцией значения. Она определяется как среднее возвращение траектории, начинающейся в \(s_0\), при условии, что действие первого этапа фиксировано и равно \(a_0\)
Обратите внимание, что суммирование внутри математического ожидания начинается с \(t=1,\ldots, \infty\), поскольку в данном случае награда первого этапа фиксирована. Мы можем снова разбить траекторию на две части и записать
Эта версия является аналогом (17.2.3) для функции значения действия.
17.2.4. Оптимальная стохастическая политика¶
Как функция значения, так и функция значения действия зависят от политики, которую выбирает робот. Далее мы рассмотрим «оптимальную политику», обеспечивающую максимальное среднее возвращение
Из всех возможных стохастических политик, которые мог бы выбрать робот, оптимальная политика \(\pi^*\) обеспечивает наибольшее среднее дисконтированное возвращение для траекторий, начинающихся из состояния \(s_0\). Обозначим функцию значения и функцию значения действия для оптимальной политики как \(V^* \equiv V^{\pi^*}\) и \(Q^* \equiv Q^{\pi^*}\).
Заметим, что для детерминированной политики в любом состоянии существует только одно возможное действие. Это даёт нам
Хорошая мнемоника для запоминания этого факта заключается в том, что оптимальное действие в состоянии \(s\) (для детерминированной политики) — это действие, которое максимизирует сумму награды \(r(s, a)\) на первом этапе и среднего возврата траекторий, начинающихся со следующего состояния \(s'\), усреднённого по всем возможным следующим состояниям \(s'\) на втором этапе.
17.2.5. Принцип динамического программирования¶
Развитие, представленное в предыдущем разделе в (17.2.2) или (17.2.5), может быть преобразовано в алгоритм для вычисления оптимальной функции значения \(V^*\) или функции значения действия \(Q^*\) соответственно. Заметим, что
Для детерминированной оптимальной политики \(\pi^*\), поскольку в состоянии \(s\) можно выполнить только одно действие, мы также можем записать
для всех состояний \(s \in \mathcal{S}\). Это тождество называется «принципом динамического программирования» (Bellman, 1952, Bellman, 1957). Он был сформулирован Ричардом Беллманом в 1950-х годах, и его можно запомнить как «остаток оптимальной траектории также оптимален».
17.2.6. Итерация значений¶
Мы можем превратить принцип динамического программирования в алгоритм нахождения оптимальной функции значения, называемый итерацией значений. Ключевая идея итерации значений заключается в том, чтобы рассматривать это тождество как набор ограничений, связывающих \(V^*(s)\) в различных состояниях \(s \in \mathcal{S}\). Мы инициализируем функцию значения произвольными значениями \(V_0(s)\) для всех состояний \(s \in \mathcal{S}\). На \(k^{\textrm{th}}\) итерации алгоритм итерации значений обновляет функцию значения следующим образом:
Оказывается, что \(k \to \infty\) функция значений, оценённая алгоритмом Value Iteration, сходится к оптимальной функции значений независимо от начального приближения \(V_0\),
Тот же алгоритм итерации значений может быть эквивалентно записан с использованием функции значения действия как
В этом случае мы инициализируем \(Q_0(s, a)\) произвольными значениями для всех \(s \in \mathcal{S}\) и \(a \in \mathcal{A}\). Аналогично, для всех \(s \in \mathcal{S}\) и \(a \in \mathcal{A}\) выполняется условие \(Q^*(s, a) = \lim_{k \to \infty} Q_k(s, a)\).
17.2.7. Оценка политики¶
Value Iteration позволяет вычислить оптимальную функцию значения, то есть \(V^{\pi^*}\) оптимальной детерминированной политики \(\pi^*\). Мы также можем использовать аналогичные итеративные обновления для вычисления функции значения, связанной с любой другой, потенциально стохастической, политикой \(\pi\). Мы снова инициализируем \(V^\pi_0(s)\) произвольными значениями для всех состояний \(s \in \mathcal{S}\) и на \(k^{\textrm{th}}\) итерации выполняем обновления
Этот алгоритм известен как оценка политики и полезен для вычисления функции значения при заданной политике. Как и ранее, оказывается, что при \(k \to \infty\) эти обновления сходятся к верной функции значения независимо от начальной инициализации \(V_0\),
Алгоритм вычисления функции значения действия \(Q^\pi(s, a)\) политики \(\pi\) аналогичен.
17.2.8. Реализация итерации значений¶
Далее мы покажем, как реализовать итерацию значений для задачи навигации FrozenLake из Open AI Gym. Сначала нам необходимо настроить окружение, как показано в следующем коде.
%matplotlib inline
import random
import numpy as np
from d2l import torch as d2l
seed = 0 # Random number generator seed
gamma = 0.95 # Discount factor
num_iters = 10 # Number of iterations
random.seed(seed) # Set the random seed to ensure results can be reproduced
np.random.seed(seed)
# Now set up the environment
env_info = d2l.make_env('FrozenLake-v1', seed=seed)
В среде FrozenLake робот перемещается по \(4 \times 4\) сетке (это состояния), выполняя действия «вверх» (\(\uparrow\)), «вниз» (\(\rightarrow\)), «влево» (\(\leftarrow\)) и «вправо» (\(\rightarrow\)). В среде присутствуют клетки с ямами (H) и замёрзшей поверхностью (F), а также целевая клетка (G), которые все неизвестны роботу. Чтобы упростить задачу, мы предполагаем, что действия робота надёжны, то есть \(P(s' \mid s, a) = 1\) для всех \(s \in \mathcal{S}, a \in \mathcal{A}\). Если робот достигает цели, испытание завершается, и робот получает вознаграждение \(1\) независимо от выполненного действия; вознаграждение в любом другом состоянии равно \(0\) для всех действий. Цель робота — научиться такой политике, которая позволит достичь целевой локации (G) из заданной начальной локации (S) (это \(s_0\)), максимизируя возврат.
Следующая функция реализует итерацию значений, где env_info содержит
информацию, связанную с MDP и средой, а gamma — коэффициент
дисконтирования:
def value_iteration(env_info, gamma, num_iters):
env_desc = env_info['desc'] # 2D array shows what each item means
prob_idx = env_info['trans_prob_idx']
nextstate_idx = env_info['nextstate_idx']
reward_idx = env_info['reward_idx']
num_states = env_info['num_states']
num_actions = env_info['num_actions']
mdp = env_info['mdp']
V = np.zeros((num_iters + 1, num_states))
Q = np.zeros((num_iters + 1, num_states, num_actions))
pi = np.zeros((num_iters + 1, num_states))
for k in range(1, num_iters + 1):
for s in range(num_states):
for a in range(num_actions):
# Calculate \sum_{s'} p(s'\mid s,a) [r + \gamma v_k(s')]
for pxrds in mdp[(s,a)]:
# mdp(s,a): [(p1,next1,r1,d1),(p2,next2,r2,d2),..]
pr = pxrds[prob_idx] # p(s'\mid s,a)
nextstate = pxrds[nextstate_idx] # Next state
reward = pxrds[reward_idx] # Reward
Q[k,s,a] += pr * (reward + gamma * V[k - 1, nextstate])
# Record max value and max action
V[k,s] = np.max(Q[k,s,:])
pi[k,s] = np.argmax(Q[k,s,:])
d2l.show_value_function_progress(env_desc, V[:-1], pi[:-1])
value_iteration(env_info=env_info, gamma=gamma, num_iters=num_iters)
На приведённых выше рисунках показана политика (стрелка указывает действие) и функция значения (изменение цвета демонстрирует, как функция значения изменяется со временем от начального значения, обозначенного тёмным цветом, до оптимального значения, обозначенного светлыми тонами). Как мы видим, итерация значения находит оптимальную функцию значения после 10 итераций, и целевое состояние (G) может быть достигнуто из любого состояния, если только оно не является клеткой H. Ещё один интересный аспект реализации заключается в том, что помимо нахождения оптимальной функции значения, мы также автоматически нашли оптимальную политику \(\pi^*\), соответствующую этой функции значения.
17.2.9. Резюме¶
Основная идея алгоритма Value Iteration заключается в использовании принципа динамического программирования для нахождения оптимального среднего значения, получаемого из заданного состояния. Обратите внимание, что для реализации алгоритма Value Iteration необходимо полностью знать марковский процесс принятия решений (MDP), например, функции переходов и вознаграждений.
17.2.10. Упражнения¶
Попробуйте увеличить размер сетки до \(8 \times 8\). По сравнению с сеткой \(4 \times 4\), сколько итераций потребуется для нахождения оптимальной функции значения?
Какова вычислительная сложность алгоритма итерации значений?
Ещё раз запустите алгоритм итерации значений (Value Iteration) с \(\gamma\) (т. е. «gamma» в приведённом выше коде), когда он равен \(0\), \(0.5\) и \(1\), и проанализируйте результаты.
Как значение \(\gamma\) влияет на количество итераций, необходимых для сходимости Value Iteration? Что происходит при \(\gamma=1\)?