Доказательство существования оптимальной политики для конечных МДП

В конечном Марковском процессе принятия решений (MDP) оптимальная политика определяется как политика, которая максимизирует ценность всех состояний одновременно ». Другими словами, если существует оптимальная политика, то политика, которая максимизирует значение состояния s, совпадает с политикой, которая максимизирует значение состояния s '. ² Но почему должна существовать такая политика?

Знаменитая вводная книга Саттона и Барто по обучению с подкреплением¹ считает существование оптимальных политик само собой разумеющимся и оставляет этот вопрос без ответа. Мне было трудно поверить им и продолжить чтение!

В этой статье я собираюсь предоставить доказательство существования оптимальной политики в конечных MDP ³.

Обозначения и определения

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

Конечная MDP характеризуется конечным набором состояний (обычно отображается изогнутым S), конечным набором действий для каждого состояния (обычно отображается изогнутым A) и распределение вероятности по значению немедленного вознаграждения r и следующему состоянию s ' с учетом текущего состояния s и текущее выбранное действие a, обозначенное как p (s ', r | s, a).

Учитывая текущее состояние s, политика π представляет собой распределение вероятности возможных действий в состоянии s, обозначаемое как π (a | s). Затем, учитывая политику, агент может перемещаться в среде (т. е. переходить из одного состояния в другое) и получать вознаграждение за каждый переход.

Мы показываем случайные величины заглавными буквами, а их значения - строчными буквами. Время добавляется к каждой переменной с нижним индексом. Затем, учитывая политику и MDP, а также начальное состояние (в момент времени t = 1) s для любого T ›1, совместное распределение состояний, действий и значений вознаграждения

Ценности и уравнение Беллмана

Учитывая политику π и коэффициент дисконтирования 0 ≤ γ ‹1, значение каждого состояния определяется как

и значение каждой пары состояния и действия как

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

Эти системы уравнений известны как уравнения Беллмана.

Позже мы воспользуемся тем фактом, что

Оптимальная политика

Политика π * является оптимальной тогда и только тогда, когда мы имеем

для любого состояния s и любой другой политики π.

Уравнения оптимальности Беллмана

Мы показываем множество всех возможных состояний кривой S, а множество всех возможных действий в состоянии s кривыми A (s). Обозначим символ Кронекера через δ и начнем этот раздел со следующей теоремы.

Подтверждающий комментарий: Мы использовали уравнение. 1 в 1-й строке доказательства, а затем неоднократно использовал тот факт, что значение пары состояние и действие (s *, a *) больше или равно значению состояния s *.

Теорема 1 утверждает, что всякий раз, когда есть пара состояния и действия (s *, a *) со значением больше, чем значение состояния s *, относительно политики π, то существует другая политика π ', которая лучше или равна (в терминах значений состояния) π во всех состояниях. В результате, если существует оптимальная политика π *, ее значения должны удовлетворять для любого состояния s,

где curvy A (s) обозначает множество всех возможных действий в состоянии s -, это утверждение легко доказать от противного . Используя уравнения Беллмана, мы можем разложить уравнение 2 как

Эта система нелинейных уравнений (столько же, сколько и количество состояний) называется «уравнениями оптимальности Беллмана». Итак, если существует оптимальная политика, ее значения должны удовлетворять этой системе уравнений⁴.

Следовательно, чтобы показать, что существует оптимальная политика, необходимо доказать следующие два утверждения:

  1. Система уравнений оптимальности Беллмана имеет решения, и
  2. Одно из его решений имеет значения больше или равные значениям других решений во всех состояниях.

Существование и единственность решения

В этом разделе мы докажем, что система уравнений оптимальности Беллмана имеет единственное решение. Тем самым мы одновременно доказываем два вышеупомянутых утверждения.

Оператор оптимальности Беллмана

Учитывая набор значений по состояниям, мы определяем вектор значений как

который представляет собой просто вектор с действительным значением, элементы которого равны значениям различных состояний. Затем мы определяем «оператор оптимальности Беллмана» T как отображение

Оператор T берет вектор значений и сопоставляет его с другим вектором значений. Используя эти новые обозначения, легко увидеть, что уравнения 2 и 3 эквивалентны

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

Для этого нам нужно ввести еще одно понятие и еще одну теорему.

Сжимающее отображение и теорема Банаха о неподвижной точке

Рассмотрим метрическое пространство (M, d), т.е. M - это множество, а d - метрика, определенная на этом множестве. для вычисления расстояния между каждыми двумя элементами M ⁵. Отображение T: M → M является сжатым отображением, если существует 0 ≤ k ‹1 такое, что для любого x и y в M, мы имеем

Интуитивно понятно, что отображение сжатия делает точки ближе друг к другу. На рисунке 1 показана иллюстрация многократного применения карт сжатия к двум точкам.

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

Комментарий к доказательству:. Доказательство теоремы несложно, но я не включаю его в эту статью, потому что теорема хорошо известна, а доказательство можно легко найти в другом месте. , например посмотреть здесь".

Вся идея, лежащая в основе теоремы, представлена ​​на рисунке 1: все точки становятся ближе друг к другу после сопоставления, и, следовательно, при повторении сопоставления все точки сходятся к одной точке, которая является уникальной фиксированной точкой T .

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

Оператор оптимальности Беллмана - это сжимающее отображение в бесконечной норме

Для любой пары векторов значений V и V ' их бесконечная норма определяется как

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

Комментарий к доказательству: Хотя лемма довольно нетривиальна, ее доказательство несложно и требует только элементарных приемов. Я получил удовольствие, доказывая это, и подумал, что было бы неплохо оставить его доказательство в качестве упражнения для заинтересованных читателей ».

Теперь, имея лемму, мы можем наконец перейти к нашей основной теореме.

Комментарий к доказательству: Для перехода со 2-й по 3-ю строку доказательства мы использовали лемму, а для перехода с 4-й на 5-ю строку мы использовали выпуклость функция абсолютного значения. Остальное просто.

В результате оператор оптимальности Беллмана имеет единственную неподвижную точку, а уравнения оптимальности Беллмана имеют единственное решение. Легко показать, что любая жадная политика решения уравнений оптимальности Беллмана имеет значения, равные этому решению. Следовательно, существуют оптимальные правила!

Заключение

Мы показали, что (1) значения оптимальной политики должны удовлетворять уравнениям оптимальности Беллмана. Затем мы показали, что (2) решения уравнений оптимальности Беллмана являются неподвижной точкой оператора оптимальности Беллмана. Показав, что (3) оператор оптимальности Беллмана является сжимающим отображением в бесконечной норме, и используя (4) теорему Банаха о неподвижной точке, мы доказали, что (5 ) оператор оптимальности Беллмана имеет единственную неподвижную точку. В результате (6) существуют политики, максимизирующие значения всех состояний одновременно.

Подтверждение

Я благодарен Johanni Brea и моему научному руководителю Wulfram Gerstner за то, что познакомил меня с этой темой, Мохаммаду Тинати и Киану Калхору за полезные обсуждения и вычитку статьи, а также Berfin Simsek за то, что познакомил меня с этой темой. великая книга Чаба Сепешвари Алгоритмы обучения с подкреплением.

Сноски:

¹ « Обучение с подкреплением: Введение » Саттона и Барто.

² В качестве реального, но немного странного примера, если бы наш мир был конечным MDP и если бы существовала оптимальная политика, то один и тот же способ приготовления обеда сделал бы нас (грубо говоря) самыми счастливыми как во время ужина, так и во время работать в офисе на следующий день.

³ Я впервые прочитал большую часть материалов этой статьи в Алгоритмах обучения с подкреплением Чаба Сепешвари и докторской диссертации Йоханни Бреа.

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

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

⁶ Совет: Без ограничения общности предположим, что максимальное значение f₁ больше, чем максимальное значение f₂. Затем возьмите максимизатор f₁ и назовите его a₁, и…

⁷ Обратите внимание, что для любого конечного n ℝⁿ с бесконечной нормой компактно - см. Здесь для доказательства « Полноты и компактности в R ^ N ».