Оценка ценностей без модели: Монте-Карло и TD-обучение

1. Улучшение политики и схема GPI

В конспекте 3 мы научились оценивать политику: итерации оператора Беллмана сходятся к \(V^\pi\) (тренажёр «двигатель»). Осталась вторая половина — как политику улучшать. Ответ даёт одношаговый просмотр вперёд: ценность действия при известном \(V^\pi\) — это \(q^\pi(s, a) = \sum_{s', r} p(s', r|s, a)\,[r + \gamma V^\pi(s')]\) (конспект 3, формула (3.11)).

Теорема (об улучшении политики). Пусть политики \(\pi\) и \(\pi'\) таковы, что

Тогда \(V^{\pi'}(s) \ge V^{\pi}(s)\) во всех состояниях. В частности, жадная политика \(\pi'(s) \in \arg\max_a q^{\pi}(s, a)\) не хуже \(\pi\).

Доказательство. Условие (4.1) означает покомпонентно \(V^{\pi} \le \mathcal{B}^{\pi'} V^{\pi}\), где \(\mathcal{B}^{\pi'}\) — оператор Беллмана политики \(\pi'\) (конспект 3, формула (3.12)). Оператор монотонен (из \(u \le v\) следует \(\mathcal{B}^{\pi'} u \le \mathcal{B}^{\pi'} v\) — все веса под суммами неотрицательны), поэтому, применяя его \(n\) раз:

где сходимость к \(V^{\pi'}\) — теорема Банаха из конспекта 3. Предельный переход сохраняет неравенство. ∎

Так возникает обобщённая итерация политики (англ. generalized policy iteration, GPI) — каркас, в который укладываются почти все алгоритмы траектории:

GPI: чередование оценки и жадного улучшения до стабилизации политики. Разными будут только способы выполнять шаг «оценка».

Числовой пример этой теоремы уже встречался: в разобранном примере конспекта 3 жадный выбор действия поднял ценность состояния с 4,688 до 4,82.

2. On-policy и off-policy

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

• On-policy: траектории генерируются той же политикой \(\pi\), которая оценивается и улучшается. Проще и устойчивее — распределение данных совпадает с целевым.
• Off-policy: агент действует по поведенческой политике \(\mu\) (англ. behavior policy), а оценивается целевая политика \(\pi\) (англ. target policy). Гибче: можно учиться по заранее собранным логам и отделять сбор данных от обучения — но распределения различаются, и это надо корректировать (раздел 5).

3. Монте-Карло: учиться по завершённым эпизодам

Пусть модель неизвестна, задача эпизодическая, политика \(\pi\) фиксирована. Доступны независимые эпизоды \(S_0, A_0, R_1, S_1, \ldots, S_\tau = T\); награды ограничены, эпизод завершается почти наверное. Идея Монте-Карло — прямое использование определения \(V^\pi(s) = \langle G_t | S_t = s\rangle\): наблюдать возвраты и усреднять.

First-visit MC усредняет возвраты после первого появления состояния \(s\) в каждом эпизоде:

Теорема (сходимость first-visit MC). Оценка (4.2) несмещённа и сходится к \(V^\pi(s)\) почти наверное.

Доказательство. Величины \(G^{\mathrm{FV}}_i(s)\) вычисляются по независимым эпизодам — значит, независимы. По марковскому свойству распределение хвоста траектории после момента первого попадания в \(s\) зависит только от \(s\) (и политики), поэтому каждый \(G^{\mathrm{FV}}_i(s)\) распределён как \(G_t \,|\, S_t = s\) и \(\langle G^{\mathrm{FV}}_i(s)\rangle = V^\pi(s)\) — отсюда несмещённость (линейность ожидания, как в конспекте 2, формула (2.9)). Награды ограничены и эпизод конечен почти наверное — дисперсия конечна, и по усиленному закону больших чисел среднее i.i.d.-величин сходится к их ожиданию. ∎

Every-visit MC использует все посещения состояния в эпизоде: если \(K_i(s)\) — число посещений в \(i\)-м эпизоде, а \(X_i(s)\) — сумма возвратов после каждого из них, то

Возвраты внутри одного эпизода зависимы, и аргумент с i.i.d.-выборкой не проходит. Сходимость спасает изящная лемма: \(\langle X_1(s)\rangle = V^\pi(s)\,\langle K_1(s)\rangle\). Действительно, \(\langle \mathbb{1}\{S_t = s\}\, G_t \rangle = V^\pi(s)\, P(S_t = s)\) (внутреннее ожидание возврата при \(S_t = s\) равно \(V^\pi(s)\)), и суммирование по \(t\) даёт слева \(\langle X_1\rangle\), справа — \(V^\pi(s)\sum_t P(S_t = s) = V^\pi(s)\langle K_1\rangle\). Тогда по закону больших чисел числитель и знаменатель (4.3), делённые на \(n\), сходятся к \(\langle X_1\rangle\) и \(\langle K_1\rangle\), а их отношение — к \(V^\pi(s)\). Оба варианта сходятся к одному пределу; first-visit статистически прозрачнее, every-visit выжимает больше из каждого эпизода.

На практике среднее считают инкрементально — в точности схемой из конспекта 2, формула (2.12):

с \(\alpha = 1/n\) для точного среднего или постоянным \(\alpha\) для меняющихся сред. Цель обновления — полный наблюдённый возврат \(G\).

Код из конспекта преподавателя — Монте-Карло для цепочки из конспекта 3 (модель \(P\) здесь используется только средой для генерации переходов; агент её не знает):

states      = np.arange(len(r))             # [0,1,2,3,4,5]
terminals   = [3, 4]                        # терминальные состояния
rews, steps = [], []
s0          = 0                             # стартовое состояние

for _ in range(10000):                      # 10000 эпизодов
    rew, s, discont = 0, s0, 1
    for i in range(100):                    # ограничение длины на всякий случай
        s = np.random.choice(states, p=P[s]) # переход по распределению среды
        rew += r[s] * discont               # накапливаем возврат
        discont *= gamma                    # усиливаем дисконт
        if s in terminals:                  # эпизод окончен
            break
    rews.append(rew)
    steps.append(i + 1)

print("V(%d) = %7.2f ± %5.4f" % (s0, np.mean(rews), np.std(rews)/len(rews)**0.5))
# V(0) = -1.19 ± 0.04   — точное значение из конспекта 3: -1.195

Ошибка убывает как \(\sigma/\sqrt{N}\) (конспект 2, формула (2.10)): оценка честно сошлась к точному значению \(-1{,}195\), полученному решением линейной системы, — но потребовала 10 000 завершённых эпизодов.

4. От оценивания к управлению: ε-мягкие политики

Для GPI нужна не \(V^\pi\), а \(Q^\pi\): улучшение через \(V\) требует одношагового просмотра вперёд по модели \(p(s', r|s, a)\), которой нет. Оценка \(Q^\pi(s, a)\) строится тем же Монте-Карло по парам «состояние–действие». Но возникает проблема: жадная политика перестаёт выбирать «плохие» на вид действия, их оценки замерзают — знакомая по бандитам (конспект 2) ловушка. Теоретический выход — exploring starts (каждый эпизод стартует из случайной пары \((s, a)\)), но практичнее заставить разведывать саму политику.

Политика называется ε-мягкой (англ. ε-soft), если \(\pi(a|s) \ge \varepsilon / |\mathcal{A}(s)|\) для всех \(s, a\). ε-жадная политика по текущей оценке \(Q\) (конспект 2, формула (2.6)) — ε-мягкая. Для них теорема об улучшении сохраняется.

Теорема (ε-мягкое улучшение). Пусть \(\pi\) — ε-мягкая политика, \(\pi'\) — ε-жадная относительно \(q^\pi\). Тогда \(V^{\pi'}(s) \ge V^{\pi}(s)\) для всех \(s\).

Доказательство. Обозначим \(m = |\mathcal{A}(s)|\), \(M = \max_a q^\pi(s, a)\). Раз \(\pi\) ε-мягкая, её можно записать как \(\pi(a|s) = \varepsilon/m + \delta_a\), где \(\delta_a \ge 0\) и \(\sum_a \delta_a = 1 - \varepsilon\). Тогда

поскольку ε-жадная \(\pi'\) кладёт массу \(1-\varepsilon\) именно на максимум \(M\), а обязательную долю \(\varepsilon/m\) — на каждое действие. Левая часть равна \(V^\pi(s)\) (конспект 3, формула (3.7)), и условие (4.1) теоремы об улучшении выполнено. ∎

Итого on-policy Монте-Карло управление: генерировать эпизоды ε-жадной политикой, обновлять \(Q\) по (4.4), после эпизода делать политику ε-жадной по новому \(Q\). Это первый полный алгоритм обучения без модели — сэмплируемый GPI.

5. Off-policy: важностная выборка

Пусть данные собраны политикой \(\mu\), а оценить нужно \(q^\pi\). Обязательное условие покрытия:

— иначе целевой политике нужны действия, которых в данных нет вовсе. Коррекция распределений выполняется важностной выборкой (англ. importance sampling): каждому эпизоду приписывается вес — отношение вероятностей его хвоста при двух политиках:

Теорема (несмещённость). При условии (4.6): \(\bigl\langle \rho\, G \,\big|\, S_0 = s, A_0 = a \bigr\rangle_{\mu} = q^{\pi}(s, a)\).

Доказательство. Вероятность хвоста траектории \(h\) при политике \(\mu\) — это произведение \(\prod_k \mu(a_k|s_k)\, p(s_{k+1}, r_{k+1}|s_k, a_k)\). Умножение на \(\rho(h)\) заменяет каждый множитель \(\mu(a_k|s_k)\) на \(\pi(a_k|s_k)\) — вероятности среды сокращаются и остаётся ровно \(P_\pi(h|s,a)\):

Замечательно, что модель среды в \(\rho\) не входит — только отношения политик. Плата — дисперсия: произведение отношений на длинных эпизодах может взрываться. Поэтому на практике часто берут взвешенную важностную выборку

— она смещена на конечных выборках, но её дисперсия существенно меньше: классический размен смещения на дисперсию, который в этом конспекте встретится ещё раз.

6. TD(0): учиться, не дожидаясь конца

Монте-Карло использует в качестве цели обновления полный возврат \(G_t\). Но по свойству одного перехода (конспект 3, формула (3.9)) ожидание возврата равно ожиданию величины \(R_{t+1} + \gamma V^{\pi}(S_{t+1})\). Заменим в (4.4) цель на её одношаговую версию, подставив вместо неизвестного \(V^\pi\) текущую оценку \(V\):

Это алгоритм TD(0) (англ. temporal difference — «временна́я разность»). Величина в скобках —

— называется TD-ошибкой; обновление записывается как \(V(S_t) \leftarrow V(S_t) + \alpha\, \delta_t\). Знак читается напрямую: \(\delta_t > 0\) — переход оказался позитивно неожиданным (лучше текущего ожидания, оценку поднять), \(\delta_t < 0\) — негативно неожиданным. Запомните эту величину: она вернётся как главный обучающий сигнал в актор-критике (конспект 10).

Использование собственной оценки \(V\) внутри цели обновления называется бутстрапом (англ. bootstrap). У Монте-Карло бутстрапа нет — его цель \(G_t\) от оценки не зависит; у TD(0) — есть, и это источник и силы (обновление на каждом шаге), и смещения (цель опирается на ещё неточную оценку).

Утверждение (TD-ошибка как индикатор Беллмана). Если \(V = V^{\pi}\), то для любого состояния

Доказательство. Подставим \(V^\pi\) в (4.10) и возьмём условное ожидание: \(\langle R_{t+1} + \gamma V^{\pi}(S_{t+1}) | s\rangle_\pi - V^{\pi}(s)\). Первое слагаемое по свойству одного перехода равно \(V^{\pi}(s)\) — разность нулевая. ∎

То есть TD-ошибка измеряет локальное нарушение уравнения Беллмана: у точной функции ценности она в среднем нулевая, и обновления (4.9) прекращают её сдвигать. TD(0) — это стохастическая аппроксимация итераций оператора Беллмана из конспекта 3: вместо точного усреднения по модели — одна наблюдённая реализация перехода. В табличном случае TD(0) сходится к \(V^\pi\) почти наверное, если каждое состояние посещается бесконечно часто, а шаги удовлетворяют условиям Роббинса–Монро:

(первый ряд расходится — алгоритм не перестаёт учиться слишком рано; второй сходится — суммарный вклад шума остаётся конечным; пример: \(\alpha_t = 1/t\)). При постоянном \(\alpha\) сходимость точной нет — оценка колеблется вокруг \(V^\pi\) в полосе, пропорциональной \(\alpha\), — знакомый по бандитам компромисс.

TD(0) для цепочки из конспекта 3 — десять строк numpy (сравните с MC-кодом выше: обновление внутри шага, а не после эпизода):

V = np.zeros(6)                              # оценки ценностей
alpha, gamma = 0.1, 0.9

for _ in range(10000):                      # эпизоды
    s = np.random.randint(3)                # старт из 0, 1 или 2
    while True:
        s2 = np.random.choice(states, p=P[s])
        target = r[s2] + gamma * (0 if s2 in terminals else V[s2])
        V[s] += alpha * (target - V[s])      # TD-обновление (4.9)
        if s2 in terminals:
            break
        s = s2

7. Спектр между TD и Монте-Карло

Одношаговая цель — частный случай. Для любого \(n\) определим n-шаговый возврат: \(n\) реальных наград, а дальше — бутстрап:

При \(n = 1\) формула (4.13) — в точности TD-цель из (4.9). При \(n \ge T - t\) (до конца эпизода) бутстрап-член исчезает — \(V\) терминального состояния равно нулю — и \(G^{(n)}_t\) совпадает с полным возвратом \(G_t\), то есть с целью Монте-Карло. TD и MC — не два разных мира, а края одного спектра:

Рост n уменьшает бутстрап-смещение (цель ближе к реальному возврату), но увеличивает дисперсию (больше случайных наград в цели). Оптимум обычно посередине.

Контрольные вопросы

• Сформулируйте теорему об улучшении политики и объясните роль монотонности оператора Беллмана в её доказательстве.
  Если q^π(s, π'(s)) ≥ V^π(s) всюду, то V^{π'} ≥ V^π (формула (4.1)). Условие означает V^π ≤ B^{π'}V^π; монотонность оператора позволяет применять его многократно, сохраняя неравенство: V^π ≤ (B^{π'})^n V^π → V^{π'} по теореме Банаха.
• Почему для управления без модели нужно оценивать Q, а не V?
  Жадное улучшение через V требует одношагового просмотра вперёд — перебора действий с усреднением r + γV(s') по вероятностям среды, которых агент не знает. Q(s, a) сравнивает действия напрямую, без модели: улучшение — это argmax по строке таблицы.
• Чем first-visit и every-visit Монте-Карло отличаются и почему first-visit оценка несмещённа?
  First-visit усредняет возвраты только после первого посещения состояния в эпизоде, every-visit — после всех. У first-visit возвраты из разных эпизодов независимы и распределены как G_t|S_t=s (марковское свойство), поэтому их среднее — несмещённая оценка V^π, сходящаяся по закону больших чисел. У every-visit возвраты внутри эпизода зависимы, но отношение сумм всё равно сходится к V^π (лемма ⟨X⟩ = V^π⟨K⟩).
• Зачем нужна важностная выборка и почему вес ρ не содержит модели среды?
  Она корректирует несовпадение распределений: данные собраны политикой μ, а оценивается π. Вес ρ — произведение отношений π/μ вдоль эпизода: при умножении на вероятность траектории при μ множители среды p(s',r|s,a) одинаковы в числителе и знаменателе и сокращаются — остаётся вероятность той же траектории при π. Отсюда несмещённость обычной IS-оценки; плата — большая дисперсия на длинных эпизодах.
• Что такое TD-ошибка и бутстрап? Почему при V = V^π средняя TD-ошибка нулевая?
  δ_t = R_{t+1} + γV(S_{t+1}) − V(S_t) — расхождение одношаговой цели с текущей оценкой; бутстрап — использование собственной оценки V внутри цели. При V = V^π ожидание цели по свойству одного перехода равно V^π(s), поэтому ⟨δ_t|s⟩ = 0 (формула (4.11)): TD-ошибка измеряет локальное нарушение уравнения Беллмана.
• Каков смысл условий Роббинса–Монро и что происходит при постоянном шаге α?
  Σα_t = ∞ — суммарная величина шагов неограничена, алгоритм способен добраться до предела из любой точки; Σα_t² < ∞ — влияние шума суммарно конечно и затухает. При постоянном α второй ряд расходится: точной сходимости нет, оценка колеблется вокруг V^π в полосе ширины порядка α — зато метод продолжает адаптироваться к изменениям среды.
• В каком смысле TD(0) и Монте-Карло — края одного спектра?
  n-шаговый возврат (4.13) при n = 1 совпадает с TD-целью, а при n до конца эпизода — с полным возвратом MC. Рост n уменьшает смещение бутстрапа, но увеличивает дисперсию цели: TD — максимальный бутстрап (смещение выше, дисперсия ниже), MC — без бутстрапа (несмещён, но шумен); практический оптимум обычно между ними.