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

bookРівняння Беллмана

Note
Визначення

Рівняння Беллмана — це функціональне рівняння, яке визначає функцію цінності у рекурсивній формі.

Для уточнення визначення:

  • Функціональне рівняння — це рівняння, розв'язком якого є функція. Для рівняння Беллмана цим розв'язком є функція цінності, для якої й було сформульовано рівняння;
  • Рекурсивна форма означає, що значення у поточному стані виражається через значення у майбутніх станах.

Коротко, розв'язання рівняння Беллмана дає шукану функцію цінності, а виведення цього рівняння вимагає визначення рекурсивного зв'язку між поточними та майбутніми станами.

Функція цінності стану

Для нагадування, ось функція цінності стану у компактній формі:

vπ(s)=E⁡π[Gt∣St=s]\def\E{\operatorname{\mathbb{E}}} v_\pi(s) = \E_\pi[G_t | S_t = s]

Щоб отримати рівняння Беллмана для цієї функції цінності, розкриємо праву частину рівняння та встановимо рекурсивний зв'язок:

vπ(s)=E⁡π[Gt∣St=s]=E⁡π[Rt+1+γRt+2+γ2Rt+3+...∣St=s]=E⁡π[Rt+1+γ∑k=0∞γkRt+k+2∣St=s]=E⁡π[Rt+1+γGt+1∣St=s]=∑aπ(a∣s)∑s′,rp(s′,r∣s,a)(r+γE⁡π[Gt+1∣St+1=s′])=∑aπ(a∣s)∑s′,rp(s′,r∣s,a)(r+γvπ(s′))\def\E{\operatorname{\mathbb{E}}} \begin{aligned} v_\pi(s) &= \E_\pi[G_t | S_t = s]\\ &= \E_\pi[R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + ... | S_t = s]\\ &= \E_\pi[R_{t+1} + \gamma \sum_{k=0}^\infty \gamma^k R_{t+k+2} | S_t = s]\\ &= \E_\pi[R_{t+1} + \gamma G_{t+1} | S_t = s]\\ &= \sum_a \pi(a | s) \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma \E_\pi\Bigl[G_{t+1} | S_{t+1} = s'\Bigr]\Bigr)\\ &= \sum_a \pi(a | s) \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma v_\pi(s')\Bigr) \end{aligned}

Останнє рівняння в цьому ланцюжку є рівнянням Беллмана для функції цінності стану.

Інтуїція

Щоб знайти цінність стану ss, потрібно:

  1. Розглянути всі можливі дії aa, які можна виконати з цього стану, кожна з яких зважується відповідно до ймовірності вибору цієї дії згідно з поточною політикою π(a∣s)\pi(a | s);
  2. Для кожної дії aa розглянути всі можливі наступні стани s′s' та винагороди rr, зважені за їх ймовірністю p(s′,r∣s,a)p(s', r | s, a);
  3. Для кожного з цих результатів взяти негайну винагороду rr, яку отримуєте, плюс дисконтовану цінність наступного стану γvπ(s′)\gamma v_\pi(s').

Підсумовуючи всі ці можливості, отримуємо загальне очікуване значення стану ss згідно з поточною політикою.

Функція цінності дії

Ось функція цінності дії у компактній формі:

qπ(s,a)=E⁡π[Gt∣St=s,At=a]\def\E{\operatorname{\mathbb{E}}} q_\pi(s, a) = \E_\pi[G_t | S_t = s, A_t = a]

Виведення рівняння Беллмана для цієї функції дуже схоже на попереднє:

qπ(s,a)=E⁡π[Gt∣St=s,At=a]=E⁡π[Rt+1+γRt+2+γ2Rt+3+...∣St=s,At=a]=E⁡π[Rt+1+γ∑k=0∞γkRt+k+2∣St=s,At=a]=E⁡π[Rt+1+γGt+1∣St=s,At=a]=∑s′,rp(s′,r∣s,a)(r+γE⁡π[Gt+1∣St+1=s′])=∑s′,rp(s′,r∣s,a)(r+γ∑a′π(a′∣s′)(E⁡π[Gt+1∣St+1=s′,At+1=a′]))=∑s′,rp(s′,r∣s,a)(r+γ∑a′π(a′∣s′)q(s′,a′))\def\E{\operatorname{\mathbb{E}}} \begin{aligned} q_\pi(s, a) &= \E_\pi[G_t | S_t = s, A_t = a]\\ &= \E_\pi[R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + ... | S_t = s, A_t = a]\\ &= \E_\pi[R_{t+1} + \gamma \sum_{k=0}^\infty \gamma^k R_{t+k+2} | S_t = s, A_t = a]\\ &= \E_\pi[R_{t+1} + \gamma G_{t+1} | S_t = s, A_t = a]\\ &= \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma \E_\pi\Bigl[G_{t+1} | S_{t+1} = s'\Bigr]\Bigr)\\ &= \sum_{s', r} p(s', r | s, a)\Biggl(r + \gamma \sum_{a'} \pi(a' | s') \Bigl(\E_\pi\Bigl[G_{t+1} | S_{t+1} = s', A_{t+1} = a'\Bigr]\Bigr)\Biggr)\\ &= \sum_{s', r} p(s', r | s, a)\Biggl(r + \gamma \sum_{a'} \pi(a' | s') q(s', a')\Biggr) \end{aligned}

Останнє рівняння в цьому ланцюжку є рівнянням Беллмана для функції цінності дії.

Інтуїція

Щоб знайти значення пари стан-дія (s,a)(s, a), потрібно:

  1. Розглянути всі можливі наступні стани s′s' та винагороди rr, зважені за їх ймовірністю p(s′,r∣s,a)p(s', r | s, a);
  2. Для кожного з цих результатів взяти негайну винагороду rr, яку ви отримуєте, плюс дисконтоване значення наступного стану;
  3. Щоб обчислити значення наступного стану s′s', для всіх дій a′a', можливих зі стану s′s', помножити значення дії q(s′,a′)q(s', a') на ймовірність вибору a′a' у стані s′s' згідно з поточною політикою π(a′∣s′)\pi(a' | s'). Потім підсумувати все, щоб отримати кінцеве значення.

Підсумовуючи всі ці можливості, ви отримуєте загальне очікуване значення пари стан-дія (s,a)(s, a) згідно з вашою поточною політикою.

question mark

Яке з наведеного найкраще описує функцію рівняння Беллмана?

Select the correct answer

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

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

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

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

Запитати АІ

expand

Запитати АІ

ChatGPT

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

Awesome!

Completion rate improved to 2.7

bookРівняння Беллмана

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

Note
Визначення

Рівняння Беллмана — це функціональне рівняння, яке визначає функцію цінності у рекурсивній формі.

Для уточнення визначення:

  • Функціональне рівняння — це рівняння, розв'язком якого є функція. Для рівняння Беллмана цим розв'язком є функція цінності, для якої й було сформульовано рівняння;
  • Рекурсивна форма означає, що значення у поточному стані виражається через значення у майбутніх станах.

Коротко, розв'язання рівняння Беллмана дає шукану функцію цінності, а виведення цього рівняння вимагає визначення рекурсивного зв'язку між поточними та майбутніми станами.

Функція цінності стану

Для нагадування, ось функція цінності стану у компактній формі:

vπ(s)=E⁡π[Gt∣St=s]\def\E{\operatorname{\mathbb{E}}} v_\pi(s) = \E_\pi[G_t | S_t = s]

Щоб отримати рівняння Беллмана для цієї функції цінності, розкриємо праву частину рівняння та встановимо рекурсивний зв'язок:

vπ(s)=E⁡π[Gt∣St=s]=E⁡π[Rt+1+γRt+2+γ2Rt+3+...∣St=s]=E⁡π[Rt+1+γ∑k=0∞γkRt+k+2∣St=s]=E⁡π[Rt+1+γGt+1∣St=s]=∑aπ(a∣s)∑s′,rp(s′,r∣s,a)(r+γE⁡π[Gt+1∣St+1=s′])=∑aπ(a∣s)∑s′,rp(s′,r∣s,a)(r+γvπ(s′))\def\E{\operatorname{\mathbb{E}}} \begin{aligned} v_\pi(s) &= \E_\pi[G_t | S_t = s]\\ &= \E_\pi[R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + ... | S_t = s]\\ &= \E_\pi[R_{t+1} + \gamma \sum_{k=0}^\infty \gamma^k R_{t+k+2} | S_t = s]\\ &= \E_\pi[R_{t+1} + \gamma G_{t+1} | S_t = s]\\ &= \sum_a \pi(a | s) \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma \E_\pi\Bigl[G_{t+1} | S_{t+1} = s'\Bigr]\Bigr)\\ &= \sum_a \pi(a | s) \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma v_\pi(s')\Bigr) \end{aligned}

Останнє рівняння в цьому ланцюжку є рівнянням Беллмана для функції цінності стану.

Інтуїція

Щоб знайти цінність стану ss, потрібно:

  1. Розглянути всі можливі дії aa, які можна виконати з цього стану, кожна з яких зважується відповідно до ймовірності вибору цієї дії згідно з поточною політикою π(a∣s)\pi(a | s);
  2. Для кожної дії aa розглянути всі можливі наступні стани s′s' та винагороди rr, зважені за їх ймовірністю p(s′,r∣s,a)p(s', r | s, a);
  3. Для кожного з цих результатів взяти негайну винагороду rr, яку отримуєте, плюс дисконтовану цінність наступного стану γvπ(s′)\gamma v_\pi(s').

Підсумовуючи всі ці можливості, отримуємо загальне очікуване значення стану ss згідно з поточною політикою.

Функція цінності дії

Ось функція цінності дії у компактній формі:

qπ(s,a)=E⁡π[Gt∣St=s,At=a]\def\E{\operatorname{\mathbb{E}}} q_\pi(s, a) = \E_\pi[G_t | S_t = s, A_t = a]

Виведення рівняння Беллмана для цієї функції дуже схоже на попереднє:

qπ(s,a)=E⁡π[Gt∣St=s,At=a]=E⁡π[Rt+1+γRt+2+γ2Rt+3+...∣St=s,At=a]=E⁡π[Rt+1+γ∑k=0∞γkRt+k+2∣St=s,At=a]=E⁡π[Rt+1+γGt+1∣St=s,At=a]=∑s′,rp(s′,r∣s,a)(r+γE⁡π[Gt+1∣St+1=s′])=∑s′,rp(s′,r∣s,a)(r+γ∑a′π(a′∣s′)(E⁡π[Gt+1∣St+1=s′,At+1=a′]))=∑s′,rp(s′,r∣s,a)(r+γ∑a′π(a′∣s′)q(s′,a′))\def\E{\operatorname{\mathbb{E}}} \begin{aligned} q_\pi(s, a) &= \E_\pi[G_t | S_t = s, A_t = a]\\ &= \E_\pi[R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + ... | S_t = s, A_t = a]\\ &= \E_\pi[R_{t+1} + \gamma \sum_{k=0}^\infty \gamma^k R_{t+k+2} | S_t = s, A_t = a]\\ &= \E_\pi[R_{t+1} + \gamma G_{t+1} | S_t = s, A_t = a]\\ &= \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma \E_\pi\Bigl[G_{t+1} | S_{t+1} = s'\Bigr]\Bigr)\\ &= \sum_{s', r} p(s', r | s, a)\Biggl(r + \gamma \sum_{a'} \pi(a' | s') \Bigl(\E_\pi\Bigl[G_{t+1} | S_{t+1} = s', A_{t+1} = a'\Bigr]\Bigr)\Biggr)\\ &= \sum_{s', r} p(s', r | s, a)\Biggl(r + \gamma \sum_{a'} \pi(a' | s') q(s', a')\Biggr) \end{aligned}

Останнє рівняння в цьому ланцюжку є рівнянням Беллмана для функції цінності дії.

Інтуїція

Щоб знайти значення пари стан-дія (s,a)(s, a), потрібно:

  1. Розглянути всі можливі наступні стани s′s' та винагороди rr, зважені за їх ймовірністю p(s′,r∣s,a)p(s', r | s, a);
  2. Для кожного з цих результатів взяти негайну винагороду rr, яку ви отримуєте, плюс дисконтоване значення наступного стану;
  3. Щоб обчислити значення наступного стану s′s', для всіх дій a′a', можливих зі стану s′s', помножити значення дії q(s′,a′)q(s', a') на ймовірність вибору a′a' у стані s′s' згідно з поточною політикою π(a′∣s′)\pi(a' | s'). Потім підсумувати все, щоб отримати кінцеве значення.

Підсумовуючи всі ці можливості, ви отримуєте загальне очікуване значення пари стан-дія (s,a)(s, a) згідно з вашою поточною політикою.

question mark

Яке з наведеного найкраще описує функцію рівняння Беллмана?

Select the correct answer

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

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

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

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