Як відомо, функцію цінності стану для заданої політики можна визначити, розв’язавши рівняння Беллмана:

Якщо у вас є повна модель середовища (тобто відомі ймовірності переходів і очікувані винагороди для всіх пар стан-дія), єдиними невідомими змінними в рівнянні залишаються значення станів. Тому наведене вище рівняння можна перетворити на систему з $|S|$ лінійних рівнянь з $|S|$ невідомими.

Наприклад, якщо MDP має 2 стани ($s_1$, $s_2$) і 2 дії (перехід до $s_1$, перехід до $s_2$), функцію значення стану можна визначити так:

Цю систему можна розв'язати стандартними методами лінійної алгебри.

Єдиність розв'язку такої лінійної системи гарантується, якщо виконується хоча б одна з наступних умов:

• Коефіцієнт дисконтування задовольняє $γ < 1$;
• Політика $\pi$, якщо її дотримуватися з будь-якого стану $s$, гарантує, що епізод зрештою завершиться.

Ітеративне оцінювання політики

Розв'язок можна обчислити безпосередньо, але ітеративний підхід використовується частіше через простоту реалізації. Цей метод починається з призначення довільних початкових значень для всіх станів, крім термінальних, які встановлюються рівними 0. Далі значення ітеративно оновлюються за допомогою рівняння Беллмана як правила оновлення:

Оцінена функція цінності стану $v_k$ зрештою збігається до істинної функції цінності стану $v_\pi$ при $k \to \infty$, якщо $v_\pi$ існує.

Стратегії резервного копіювання цінності

Під час оновлення оцінок цінності нові оцінки обчислюються на основі попередніх значень. Процес збереження попередніх оцінок називається резервним копіюванням. Існує дві поширені стратегії виконання резервного копіювання:

• Повне резервне копіювання: цей метод передбачає збереження нових оцінок у окремому масиві, відмінному від того, що містить попередні (резервні) значення. Відповідно, потрібні два масиви — один для зберігання попередніх оцінок і ще один для нових обчислених значень;
• Резервне копіювання на місці: цей підхід зберігає всі значення в одному масиві. Кожна нова оцінка одразу замінює попереднє значення. Цей метод зменшує використання пам'яті, оскільки потрібен лише один масив.

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

Коли зупиняти оновлення?

У ітеративній оцінці політики не існує точної точки, в якій алгоритм повинен зупинитися. Хоча збіжність гарантується в межі, продовження обчислень після певного моменту є недоцільним на практиці. Простий та ефективний критерій зупинки — відстежувати абсолютну різницю між послідовними оцінками значення, $|v_{k+1}(s) - v_k(s)|$, і порівнювати її з малим порогом $\theta$. Якщо після повного циклу оновлення (коли значення для всіх станів оновлено) жодна зміна не перевищує $\theta$, процес можна безпечно завершити.

Псевдокод