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

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

Псевдокод