Проблема обучения с подкреплением

Давайте представим, что вы впервые в новом городе, и ваша цель — найти лучший ресторан. У вас нет карты или интернета. Как бы вы подошли к поиску лучшего ресторана? Вы, вероятно, начнете исследовать город, пробовать разные рестораны и делать мысленные заметки о качестве каждого из них. Со временем вы начнете понимать, где расположены хорошие рестораны.

Это аналогично проблеме обучения с подкреплением, когда агент (в данном случае вы) попадает в неизвестную среду (город) и должен научиться воспринимать >действия (выберите рестораны), которые максимизируют некоторую награду (например, качество еды).

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

Марковские процессы принятия решений

Теперь представьте, что вы находитесь в гигантском лабиринте. Каждый ход приводит вас в другую часть лабиринта, и ваша цель — как можно быстрее найти выход. Лучшее решение на каждом ходу зависит только от вашего текущего местоположения, а не от того, как вы туда попали. Это свойство называется марковским свойством, и проблемы, обладающие этим свойством, можно моделировать как марковские процессы принятия решений (MDP).

В формальном определении MDP определяется набором состояний, набором действий, функцией перехода, которая определяет вероятность попадания в любое состояние при заданном текущем состоянии и предпринятом действии, и функция вознаграждения, которая дает ожидаемое немедленное вознаграждение для каждой пары состояние-действие. Цель состоит в том, чтобы найти политику, которая максимизирует ожидаемую сумму вознаграждений со скидкой, где коэффициент скидки представляет собой число от 0 до 1, представляющее текущую стоимость будущих вознаграждений.

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

Допустим, вы планируете путешествие по нескольким городам. Чтобы свести к минимуму время в пути, вам нужно определить кратчайшее время, чтобы добраться до каждого города из вашего текущего местоположения. Теперь предположим, что вы уже знаете кратчайшее время от каждого города до конечного пункта назначения. Тогда кратчайшее время от вашего текущего города будет равно времени в пути до следующего города плюс кратчайшее время от этого города до пункта назначения.

Этот принцип лежит в основе уравнений Беллмана, которые обеспечивают рекурсивное разложение для функции ценности политики в MDP. Ценность состояния согласно политике — это ожидаемая сумма дисконтированных вознаграждений от этого состояния, а уравнение Беллмана выражает это значение как сумму немедленного вознаграждения. и дисконтированное значение следующего состояния. Уравнение Беллмана формирует теоретическую основу для многих алгоритмов обучения с подкреплением.

1. Агент. Представьте себе собаку, играющую в мяч. Здесь собака является агентом. Это «деятель» или «ученик», тот, кто принимает решения на основе своего понимания мира.

2. Окружающая среда. Парк, в котором собака играет в мяч, — это окружающая среда. Это все, что находится за пределами агента, контекст, в котором агент действует.

3. Состояние. Состояние — это моментальный снимок того, как выглядит мир в данный момент. Например, текущее положение собаки и мяча может представлять состояние.

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

5. Награда. Награда — это то, что агент получает после выполнения действия. Когда собака приносит мяч, ее могут погладить по голове или угостить, что будет ее наградой.

6. Шаги по времени. Шаги по времени — это дискретные «моменты» во времени. Думайте об этом, как о листании комикса, каждая панель представляет собой новый временной шаг.

7. Состояние среды. Состояние среды — это все, что агенту необходимо знать о среде на данном временном шаге. Для собаки это может быть положение мяча, других собак в парке и так далее.

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

9. Сумма вознаграждений. Это общая сумма вознаграждения, которую агент получает за определенный период времени. Если собака берет мяч 10 раз и каждый раз получает лакомство, сумма вознаграждений составит 10 лакомств.

10. Набор состояний. Это все возможные снимки или ситуации, в которых может оказаться агент. Для собаки это может быть где угодно в парке, и мяч тоже может быть где угодно, поэтому множество состояний будет включать все эти возможности.

11. Набор действий. Это все возможные действия, которые может предпринять агент. Для собаки это все различные движения, которые она может совершать, такие как бег, прыжки, сидение и т. д.

12. Функция перехода: описывает, как среда изменяется в ответ на действия агента. Если собака побежит налево, где она окажется? Функция перехода отвечает на такие вопросы.

13. Функция вознаграждения. Определяет, сколько вознаграждения получает агент за каждое действие, которое он совершает в данном состоянии. Если собака принесет мяч, сколько угощения она получит? На это отвечает функция вознаграждения.

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

15. Пара "состояние-действие": это просто состояние и действие вместе. Для собаки парой состояние-действие может быть (собака на дереве, бег к мячу).

16. Функция ценности политики: это мера того, насколько хороша конкретная политика. Это общая сумма вознаграждения, которую агент ожидает получить в будущем, следуя этой политике из данного состояния.

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

18.Немедленное вознаграждение. Это вознаграждение, которое агент получает сразу после совершения действия.

19. Стоимость со скидкой: это стоимость будущих вознаграждений, уменьшенная, чтобы отразить тот факт, что вознаграждение, полученное в будущем, менее ценно, чем вознаграждение, полученное немедленно. Эта концепция похожа на мысль: «Синица в руке стоит двух в кустах». Это способ количественной оценки неопределенности во времени. Например, если собака может получить одно лакомство сейчас или два лакомства в течение часа, стоимость двух лакомств обесценивается на время ожидания собаки. Несмотря на то, что два лакомства лучше, собака может предпочесть одно лакомство сейчас, потому что это немедленно. Это немедленное угощение будет иметь более высокую дисконтированную стоимость, чем два угощения позже.