Цей підхід особливо корисний у навчанні з підкріпленням (RL) для ефективного розв'язання марковських процесів прийняття рішень (MDP), коли доступна повна модель середовища.

Умови застосування динамічного програмування

Не кожну задачу можна розв’язати за допомогою динамічного програмування. Існують дві ключові властивості, якими повинна володіти задача, щоб DP була застосовною:

• Оптимальна підструктура: оптимальне розв’язання задачі отримується з оптимальних розв’язань її підзадач. У MDP це означає, що оптимальна стратегія в будь-якому стані залежить від оптимальних стратегій у наступних станах. Оскільки рішення в MDP приймаються послідовно, розв’язання менших підзадач (визначення найкращої дії для майбутніх станів) приводить до розв’язання загальної задачі (визначення найкращої дії для поточного стану);
• Перекривання підзадач: розв’язання підзадач повторно використовуються для розв’язання більших задач. У MDP це проявляється в тому, що значення стану багаторазово обчислюється в різних послідовностях прийняття рішень. Оскільки стани часто відвідуються повторно, раніше обчислені значення можна зберігати та використовувати повторно, що зменшує надлишкові обчислення та підвищує ефективність.

Кожна вершина на зображенні представляє рекурсивний виклик для обчислення Fib(n), а деревоподібна структура показує, як ці виклики розбиваються на менші підзадачі. Зверніть увагу, що підзадачі на кшталт Fib(2) та Fib(1) з’являються кілька разів, що демонструє перекривання підзадач, а розв’язання Fib(5) будується з оптимальних розв’язань її підзадач, що демонструє оптимальну підструктуру. Саме цю надмірність динамічне програмування прагне усунути шляхом збереження та повторного використання результатів.

Оскільки MDP мають як оптимальну підструктуру, так і перекривання підзадач, вони добре підходять для розв’язання методами динамічного програмування.

Чому використовувати ДП у навчанні з підкріпленням?

• Гарантії оптимальності: методи динамічного програмування гарантують збіжність до оптимальної стратегії, якщо відома повна модель;
• Ефективність для загальних рішень: за допомогою ДП можна ефективно отримати загальні рішення, тобто отримана стратегія буде оптимальною для кожного окремого стану;
• Базис для інших методів: концепції ДП є основою для інших методів навчання з підкріпленням, таких як Монте-Карло та навчання з часовою різницею.

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

Виклики та обмеження динамічного програмування

Хоча методи динамічного програмування (ДП) забезпечують елегантну структуру для розв'язання задач навчання з підкріпленням, вони мають суттєві обмеження, які ускладнюють їх застосування в реальних умовах:

• Обчислювальна складність: методи ДП вимагають виконання обчислень для кожного окремого стану в середовищі. Зі зростанням простору станів кількість необхідних обчислень значно збільшується, що робить ДП непрактичним для складних задач;
• Необхідність відомої моделі: ДП передбачає, що ймовірності переходів і винагороди в середовищі відомі заздалегідь. Однак у багатьох реальних задачах навчання з підкріпленням ця інформація недоступна, тому більш доцільними є безмодельні підходи.