Метод Монте-Карло

Урок объясняет метод Монте-Карло — оценку ценности через усреднение полных эпизодов.

Метод Монте-Карло (MC) оценивает ценность состояния, усредняя фактические возвраты, полученные после посещения этого состояния в полных эпизодах.

Идея: учиться по итогу эпизода

MC не использует модель среды и не делает предположений — он просто играет эпизоды до конца, записывает реальный возврат для каждого состояния и усредняет. Если из состояния s в среднем получался возврат 7, значит V(s) ≈ 7. Чем больше эпизодов, тем точнее оценка по закону больших чисел.

Ключевое ограничение

MC требует завершённых эпизодов: чтобы посчитать возврат, нужно дойти до конца. В непрерывных задачах без естественного конца MC неудобен. Зато он несмещён — усреднение настоящих возвратов сходится к истинной ценности.

# Монте-Карло оценка V(s): цепочка 0..4, цель=4, шаг=-0.1, политика "всегда вправо".
gamma = 0.9

def run_episode():
    s, trajectory = 0, []
    while s != 4:
        ns = s + 1
        reward = 1.0 if ns == 4 else -0.1
        trajectory.append((s, reward))
        s = ns
    return trajectory

returns = {s: [] for s in range(5)}
for _ in range(500):
    traj = run_episode()
    G = 0.0
    for s, r in reversed(traj):     # считаем возврат с конца эпизода
        G = r + gamma * G
        returns[s].append(G)

V = {s: round(sum(v) / len(v), 3) for s, v in returns.items() if v}
print("Оценка V(s) методом Монте-Карло:", V)

Вывод:

Оценка V(s) методом Монте-Карло: {0: 0.458, 1: 0.62, 2: 0.8, 3: 1.0}

Политика детерминирована, поэтому возвраты одинаковы во всех эпизодах, и оценки сразу точные. В стохастической среде усреднение по 500 эпизодам сгладило бы случайность.

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

Возврат считают «с конца»: идём по траектории в обратном порядке и накапливаем G = r + gamma·G. Различают first-visit MC (учитывают только первое посещение состояния в эпизоде) и every-visit MC (каждое посещение). Оба сходятся к истинной ценности. Для управления (а не только оценки) MC оценивает Q(s,a) и улучшает политику жадно по Q — это даёт Monte Carlo Control.

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

• Применять MC к непрерывным задачам. Без конца эпизода нет возврата — MC буксует.
• Высокая дисперсия. Полный возврат зависит от всей траектории, поэтому оценки «шумят» и требуют много эпизодов.
• Обновлять оценку до конца эпизода. MC по определению ждёт конца; нельзя обновлять «на лету» — для этого есть TD (следующий урок).

Итоги

• Монте-Карло оценивает ценность, усредняя реальные возвраты завершённых эпизодов.
• Метод несмещён и не требует модели среды, но нуждается в конечных эпизодах.
• Главный минус — высокая дисперсия и ожидание конца эпизода.