Вивчайте Умови Оптимальності | Динамічне програмування

Свайпніть щоб показати меню

У попередньому розділі розглядалися рівняння Беллмана для функцій цінності стану та функцій цінності стану-дії. Ці рівняння описують, як цінності станів можуть рекурсивно визначатися через цінності інших станів, причому ці цінності залежать від заданої політики. Однак не всі політики однаково ефективні. Насправді, функції цінності задають частковий порядок для політик, який можна описати так:

\pi \ge \pi' \iff v_\pi(s) \ge v_{\pi'}(s) \qquad \forall s \in S

Отже, політика $\pi$ краща або рівна політиці $\pi'$ , якщо для всіх можливих станів очікувана винагорода політики $\pi$ не менша за очікувану винагороду політики $\pi'$ .

Додатково до вивчення

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

Оптимальна стратегія

Визначення

Для будь-якого MDP існує принаймні одна стратегія, яка не гірша за всі інші стратегії. Така стратегія називається оптимальною стратегією $\pi_*$ . Хоча може існувати багато оптимальних стратегій, усі вони позначаються як $\pi_*$ .

Чому оптимальна стратегія завжди існує?

Можливо, ви замислювалися, чому оптимальна стратегія завжди існує для будь-якого MDP. Це слушне питання, і інтуїція тут досить проста. Пам'ятайте, що стани в MDP повністю відображають стан середовища. Це означає, що кожен стан є незалежним від інших: дія, обрана в одному стані, не впливає на винагороди чи результати, досяжні в іншому. Тому, обираючи оптимальну дію окремо для кожного стану, ви природно отримуєте загалом найкращу послідовність дій для всього процесу. А ця сукупність оптимальних дій у кожному стані і є оптимальною стратегією.

Крім того, завжди існує принаймні одна стратегія, яка є одночасно оптимальною та детермінованою. Дійсно, якщо для деякого стану $s$ дві дії $a$ і $a'$ дають однакову очікувану винагороду, вибір лише однієї з них не вплине на оптимальність стратегії. Застосування цього принципу до кожного окремого стану зробить стратегію детермінованою, зберігаючи її оптимальність.

Оптимальні функції цінності

Оптимальні політики мають однакові функції цінності — це стає очевидним, коли розглядається порівняння політик. Це означає, що оптимальні політики мають спільні функцію цінності стану та функцію цінності дії.

Крім того, оптимальні функції цінності мають власні рівняння Беллмана, які можна записати без посилання на конкретну політику. Ці рівняння називаються рівняннями оптимальності Беллмана.

Оптимальна функція цінності стану

Визначення

Оптимальна функція цінності стану $V_*$ (або $v_*$ ) позначає максимальне очікуване повернення, якого можна досягти з певного стану, дотримуючись оптимальної політики.

Математичне визначення:

\def\E{\operatorname{\mathbb{E}}} v_*(s) = \max_\pi v_\pi(s) = \E_{\pi_*}[G_t | S_t = s]

Рівняння оптимальності Беллмана для цієї функції цінності можна вивести так:

\begin{aligned} v_*(s) &= \sum_a \pi_*(a | s) \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma v_*(s')\Bigr)\\ &= \max_a \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma v_*(s')\Bigr) \end{aligned}

Інтуїція

Як ви вже знаєте, завжди існує принаймні одна політика, яка є одночасно оптимальною та детермінованою. Така політика для кожного стану послідовно обирає одну конкретну дію, що максимізує очікувану винагороду. Тому ймовірність вибору цієї оптимальної дії завжди дорівнює 1, а ймовірність вибору будь-якої іншої дії — 0. Враховуючи це, у початковому рівнянні Беллмана вже не потрібен оператор суми. Замість цього, оскільки ми завжди обираємо найкращу можливу дію, суму можна замінити на максимум серед усіх доступних дій.

Функція оптимальної цінності дії

Визначення

Функція оптимальної цінності дії $Q_*$ (або $q_*$ ) — це максимальне очікуване значення винагороди, яке можна отримати, виконуючи певну дію в певному стані та дотримуючись оптимальної політики надалі.

Математичне визначення виглядає так:

\def\E{\operatorname{\mathbb{E}}} q_*(s, a) = \max_\pi q_\pi(s, a) = \E_{\pi_*}[G_t | S_t = s, A_t = a]

Рівняння оптимальності Беллмана для цієї функції значення можна вивести так:

\begin{aligned} q_*(s, a) &= \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma \sum_{a'} \pi_*(a' | s')q_*(s', a')\Bigr)\\ &= \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma \max_{a'} q_*(s', a')\Bigr) \end{aligned}

Інтуїція

Аналогічно до функції значення стану, суму можна замінити взяттям максимуму серед усіх доступних дій.

Все було зрозуміло?

Дякуємо за ваш відгук!

Секція 3. Розділ 3

Запитати АІ

Запитайте про що завгодно або спробуйте одне із запропонованих запитань, щоб почати наш чат

Секція 3. Розділ 3