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

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

Псевдокод