Уравнение Беллмана

Урок объясняет уравнение Беллмана — рекурсивную основу почти всех методов RL.

Уравнение Беллмана связывает ценность состояния с немедленной наградой и дисконтированной ценностью следующего состояния: V(s) = (награда сейчас) + gamma·V(следующего состояния).

Интуиция: ценность раскладывается на «сейчас» и «потом»

Главная идея Беллмана проста: ценность сегодняшнего шага = что я получу прямо сейчас + сколько будут стоить все будущие шаги. Будущее уже «упаковано» в ценность следующего состояния, поэтому не нужно заглядывать до конца эпизода — достаточно одного шага вперёд. Это превращает длинную сумму будущих наград в короткое рекурсивное правило.

Две формы уравнения

Для фиксированной политики (оценка): V(s) = R(s,a) + gamma·V(s'), где a выбрано политикой. Для оптимальной политики (уравнение оптимальности): берём лучшее действие:

V*(s) = max_a [ R(s,a) + gamma * V*(s') ]
Q*(s,a) =        R(s,a) + gamma * max_a' Q*(s', a')

Интуиция формулы для Q: ценность действия = немедленная награда плюс дисконтированная ценность лучшего действия в том состоянии, куда мы попадём. Именно эту формулу «зашьёт» в себя Q-learning.

Value iteration: решаем уравнение итерациями

Если среда известна, уравнение Беллмана можно решить численно: многократно пересчитывать V по формуле, пока значения не перестанут меняться. Это называется value iteration. Покажем на цепочке из 5 состояний, где цель — состояние 4.

# Цепочка состояний 0..4, цель = 4. Действия: влево/вправо. Награда +1 за вход в цель.
gamma = 0.9
states = [0, 1, 2, 3, 4]

def step(s, a):
    if s == 4:
        return 4, 0.0                       # цель — терминал
    ns = max(0, s - 1) if a == "left" else min(4, s + 1)
    reward = 1.0 if ns == 4 else 0.0
    return ns, reward

V = {s: 0.0 for s in states}
for _ in range(50):                          # итерации Беллмана
    newV = {}
    for s in states:
        if s == 4:
            newV[s] = 0.0
            continue
        newV[s] = max(
            (lambda ns, r: r + gamma * V[ns])(*step(s, a))
            for a in ("left", "right")
        )
    V = newV

for s in states:
    print("V(", s, ") =", round(V[s], 3))

Вывод:

V( 0 ) = 0.729
V( 1 ) = 0.81
V( 2 ) = 0.9
V( 3 ) = 1.0
V( 4 ) = 0.0

Видно: чем ближе к цели, тем выше ценность, и каждый шаг назад «стоит» множителя gamma=0.9 (0.9 → 0.81 → 0.729). Это и есть уравнение Беллмана в действии.

Как работает под капотом

Value iteration сходится, потому что обновление Беллмана — сжимающее отображение: с каждым проходом значения приближаются к истинным. Когда среда (P и R) неизвестна, мы не можем считать «по формуле» — приходится оценивать ожидания по реальным переходам. Так Q-learning и SARSA превращают уравнение Беллмана в обучение на опыте.

Частые ошибки

Забыть про gamma. Без дисконтирования в задачах без явного конца value iteration не сходится.
Путать оценку и оптимальность. Версия с max даёт оптимальную ценность; версия без max — ценность конкретной (возможно, неоптимальной) политики.
Применять value iteration без модели. Оно требует знания P и R. Если их нет — нужны методы из следующего раздела (TD, Q-learning).

Итоги

Уравнение Беллмана раскладывает ценность на «награду сейчас» + «дисконтированную ценность будущего».
Value iteration итеративно решает его, когда среда известна.
Q-learning и SARSA — это способ применять идею Беллмана, когда модель среды неизвестна.