Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.
Вивчайте Умови Оптимальності | Динамічне Програмування
Вступ до навчання з підкріпленням
course content

Зміст курсу

Вступ до навчання з підкріпленням

Вступ до навчання з підкріпленням

1. Основна Теорія Навчання з Підкріпленням
2. Проблема Багаторукого Бандита
3. Динамічне Програмування
4. Методи Монте-Карло
5. Навчання з часовою різницею

book
Умови Оптимальності

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

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

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

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

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

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

Note
Визначення

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

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

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

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

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

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

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

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

Note
Визначення

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

Це можна математично визначити так:

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

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

v(s)=aπ(as)s,rp(s,rs,a)(r+γv(s))=maxas,rp(s,rs,a)(r+γv(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. Враховуючи це, у початковому рівнянні Беллмана вже не потрібен оператор суми. Замість цього, оскільки ми завжди обираємо найкращу можливу дію, суму можна замінити на максимум по всіх доступних діях.

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

Note
Визначення

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

Математично це можна визначити так:

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

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

q(s,a)=s,rp(s,rs,a)(r+γaπ(as)q(s,a))=s,rp(s,rs,a)(r+γmaxaq(s,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}

Інтуїція

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

question mark

Чому оптимальна стратегія завжди існує для будь-якого марковського процесу прийняття рішень?

Select the correct answer

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

Як ми можемо покращити це?

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

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

Запитати АІ

expand

Запитати АІ

ChatGPT

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

course content

Зміст курсу

Вступ до навчання з підкріпленням

Вступ до навчання з підкріпленням

1. Основна Теорія Навчання з Підкріпленням
2. Проблема Багаторукого Бандита
3. Динамічне Програмування
4. Методи Монте-Карло
5. Навчання з часовою різницею

book
Умови Оптимальності

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

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

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

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

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

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

Note
Визначення

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

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

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

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

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

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

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

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

Note
Визначення

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

Це можна математично визначити так:

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

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

v(s)=aπ(as)s,rp(s,rs,a)(r+γv(s))=maxas,rp(s,rs,a)(r+γv(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. Враховуючи це, у початковому рівнянні Беллмана вже не потрібен оператор суми. Замість цього, оскільки ми завжди обираємо найкращу можливу дію, суму можна замінити на максимум по всіх доступних діях.

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

Note
Визначення

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

Математично це можна визначити так:

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

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

q(s,a)=s,rp(s,rs,a)(r+γaπ(as)q(s,a))=s,rp(s,rs,a)(r+γmaxaq(s,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}

Інтуїція

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

question mark

Чому оптимальна стратегія завжди існує для будь-якого марковського процесу прийняття рішень?

Select the correct answer

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

Як ми можемо покращити це?

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

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