Лекция 2. Уравнения Беллмана для функций ценности. Алгоритмы Policy/Value Iteration.

• Обсуждение кроссотерапийного метода обучения с подкреплением.  

• Задача: максимизация кумулятивной награды, учитывая структуру задачи.  

• Среда: состояния, агент, действия, вероятность перехода, награда.  

• Траектория: кумулятивная награда, вероятность перехода, действие, состояние.  

• Целевая задача: максимизация кумулятивной награды по вероятности перехода.  

• Функция ценности: кумулятивная награда, мат. ожидания по среде.  

• Функция ценности с фиксированным состоянием и действием: кумулятивная награда, мат. ожидания по среде, состояние, действие.  

• Оптимальная функция ценности: максимум по всем распределениям.  

• Рекурентные формулы пересчета: награда, кумулятивная награда, функция ценности, оптимальная функция ценности.  

• В уравнении Беллмана, функция ценности определяется как максимум по всем возможным политикам.  

• Для каждого состояния и действия, функция ценности зависит от ожидаемой награды и вероятности перехода в следующее состояние.  

• Оптимальная функция ценности определяется как максимум по согласованным политикам.  

• Функция ценности зависит от состояния и ожидаемой награды, а также от вероятности перехода в следующее состояние.  

• Оптимальная функция ценности совпадает с функцией ценности для согласованной политики.  

• Задача максимизации заключается в определении оптимальной политики, которая максимизирует функцию ценности.  

• Ограничения на распределение вероятностей и сумма вероятностей по всем действиям должны быть единичными.  

• В видео обсуждается задача условной оптимизации в марковском процессе принятия решений.  

• Оптимальная политика в этой задаче всегда детерминирована, то есть выбирается конкретное действие в каждом состоянии.  

• Это отличается от теории игр, где оптимальная политика может быть смешанной стратегией.  

• Уравнение Белмана для функции ценности в оптимальной политике имеет простой вид, так как максимум достигается на детерминированных политиках.  

• Оптимальная функция ценности зависит от награды, вероятности перехода и функции ценности следующего состояния.  

• Оптимальная политика может быть извлечена из функции ценности, если известна функция в.  

• Если известна функция в, то оптимальная политика может быть извлечена через рекурентное соотношение.  

• Функция ценности и оптимальная политика связаны между собой.  

• В видео обсуждается процедура оценивания качества текущей политики, используя уравнения Белмана.  

• Уравнения Белмана представляют собой систему линейных уравнений, которая может быть решена методом простой итерации.  

• Для сжимаемости отображения, необходимо доказать, что разность между двумя точками в пространстве состояний меньше либо равна некоторой константе меньше единицы.  

• Обсуждается ограничение нормы матрицы, которое должно быть меньше либо равно единице.  

• Это ограничение эквивалентно тому, что модуль каждой компоненты матрицы меньше либо равен единице.  

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

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

• В результате получается свойство сжимаемости, которое позволяет определить, является ли политика оптимальной или нет.  

• Обсуждается стратегия улучшения политики, основанная на максимизации действия в одном состоянии.  

• Если улучшение не удается, то политика считается оптимальной.  

• Если улучшение удается, то новая политика считается лучше старой.  

• Алгоритм улучшения политики состоит из итераций, в которых для каждого состояния выбирается максимальное действие.  

• Если улучшения не происходит, то политика считается оптимальной.  

• В видео объясняется алгоритм улучшения политики, который использует формулу для определения оптимального действия на основе текущей политики и текущей награды.  

• Алгоритм состоит из трех этапов: оценка политики, улучшение политики и оценка политики.  

• В примере рассматривается агент, перемещающийся по полю, и его награда зависит только от текущего положения.  

• Алгоритм применяется к данной среде, и результаты показывают, что оптимальное действие зависит от текущего положения агента.  

• В видео обсуждается сходимость алгоритма, которая зависит от величины отклонения от оптимального действия.  

• В данном примере, алгоритм сходится, так как отклонения от оптимального действия незначительны.  

• В видео обсуждается оптимальная стратегия в игре, где игрок выбирает между различными действиями, и каждое действие имеет свои последствия.  

• Оптимальная стратегия определяется как та, которая максимизирует ожидаемую прибыль.  

• Оптимальная стратегия может быть найдена с помощью алгоритма, который учитывает все возможные действия и их последствия.  

• Алгоритм требует от среды выполнения цикла по всем состояниям и возможности вычисления математического ожидания.  

• Если среда удовлетворяет этим требованиям, алгоритм гарантированно сходится к оптимальной политике.  

• В видео также упоминается другой алгоритм, который может быть более эффективным для некоторых сред, таких как такси.  

• В дальнейшем планируется разработка алгоритмов, которые будут требовать меньше требований к среде.