Сетевой мир

Проблема, похожая на лабиринт:

  • Агент живет в сетке.
  • Стены преграждают путь агенту.

Шумное движение: действия не всегда идут по плану.

  • В 80% случаев действие «Север» берет на себя агент «Север».
  • В 10% случаев Норт берет агента Уэста; В 10% случаев Север берет агента Востока.
  • Если есть стена в том направлении, куда должен был уйти агент, агент остается на месте.

Агент получает вознаграждение за каждый временной шаг:

  • Небольшая «живая» награда за каждый шаг (может быть отрицательной)
  • В конце приходят большие награды (хорошие или плохие)

Цель: максимизировать сумму вознаграждений

MDP определяется -

  • Набор состояний s∈S
  • Набор действий a∈A
  • Функция перехода T (s, a, s ’). Также называется модель или динамика. P (s ’| s, a) = T (s, a, s’)
  • Функция вознаграждения R (s, a, s ’)
  • Начальное состояние
  • Может быть, конечное состояние
  • MDP - это недетерминированные поисковые задачи.
  • «Марковский» обычно означает, что при нынешнем состоянии будущее и прошлое независимы.
  • Это похоже на поиск, где функция-преемник может зависеть только от текущего состояния (а не от истории)
  • В задачах детерминированного поиска с одним агентом нам нужен был оптимальный план или последовательность действий от начала до цели.
  • Для MDP нам нужна оптимальная политика Π *: S ⇒ A
  • Политика Π дает действие для каждого состояния.
  • Оптимальная политика - это политика, которая максимизирует ожидаемую полезность, если следовать ей.
  • Явная политика определяет рефлекторный агент.

Скидка:

  • Разумно максимизировать сумму вознаграждений.
  • Также разумно предпочесть вознаграждения сейчас вознаграждениям позже.
  • Одно решение: размер вознаграждений уменьшается экспоненциально.

Как делать скидки?
Каждый раз спускаемся на уровень. умножаем скидку один раз.

Зачем нужна скидка?
Более ранние вознаграждения, вероятно, действительно полезнее, чем более поздние вознаграждения. Также помогает алгоритму сходиться.

Пример: скидка 0,5
U ([1,2,3]) = 1 * 1 + 2 * 0,5 + 3 * o.25.

Что, если игра будет длиться вечно?
Решение:

  • Конечный горизонт: (аналогично поиску с ограниченной глубиной)
  • Предоставляет нестационарные полисы (Π зависит от оставшегося времени)
  • Дисконтирование: используйте 0 ‹ϒ‹ 1. Меньший ϒ означает меньший «горизонт».

Поглощающее состояние - гарантия того, что для каждой политики в конечном итоге будет достигнуто конечное состояние.

Как решить МДП?

Ценность (полезность) состояния S:

V * (s) = ожидаемая полезность, начиная с S и действуя оптимально.
(говорит нам, насколько хорошо каждое состояние)

Q * (s, a) = ожидаемая полезность, начиная с того, что предприняла действие «a» из состояния «s» и (после этого) действовала оптимально.
(«s» фиксировано, и мы варьируем «a»)

Оптимальная политика:
Π * (s) = оптимальное действие из состояния s = argmax Q * (s, a)
(это действие, которое достигает максимума)

Значения состояний:

Основная операция: вычислить (expectimax) значение состояния.

  • Ожидаемая полезность при оптимальном действии.
  • Средняя сумма вознаграждений (со скидкой)
  • Это именно то, что рассчитал expectimax!

Рекурсивное определение значения:

V * (s) = max Q * (s, a)

Q * (s, a) = max Σ T (s, a, s ’) [R (s, a, s’) + V * (s)] - уравнение Беллмана

Количество:

Политика = карта состояний и действий.
Полезность = сумма дисконтированных вознаграждений.
Значения = ожидаемая будущая полезность от состояния (макс. Узел)
Q-значения = ожидаемая будущая полезность от q- состояние (случайный узел)

Итерация значения и итерация политики вычисляют одно и то же (все оптимальные значения)

В итерации значения -

  • Каждая итерация обновляет как значения, так и (неявно) политику.
  • Мы не отслеживаем политику, но, принимая максимальное значение над действиями, неявно пересчитываем ее.

В итерации политики -

  • Мы выполняем несколько проходов, которые обновляют утилиты с фиксированной политикой (каждый проход выполняется быстро, потому что мы рассматриваем только одно действие, а не все из них)
  • После оценки политики выбирается новая политика (медленная, как итерация значения)
  • Новая политика будет лучше (или все готово)

Хорошо, пока все! Спасибо, что уделили время. Ваше здоровье!