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

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

\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

Запитати АІ

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

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

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

Дізнайтеся більше