KBIA використовують моделі планування та прийняття рішень для ефективного вирішення задач. Ці моделі потрібні агентам, щоб формулювати стратегії та політики, робити обґрунтований вибір та досягати бажаних цілей.
2.4.1 Марківські процеси прийняття рішень.
Марківські процеси прийняття рішень (MDP) та частково спостережувані Марківські процеси прийняття рішень (POMDP) - це моделі, які використовуються в системах KBIA для планування та прийняття рішень у невизначених середовищах та забезпечують структуровану основу для прийняття агентами оптимальних або майже оптимальних рішень, враховуючи невизначеності та ймовірності переходів між станами.
У MDP агент взаємодіє з середовищем протягом послідовних кроків в часі. На кожному кроці агент приймає рішення (вибирає дію) щодо переходу з поточного стану в новий стан. MDP визначаються п’ятьма компонентами [12 p.610].
- Стани (States - S). Скінченна множина можливих станів, у яких може перебувати агент і середовище.
- Дії (Actions - A). Скінченна множина дій, які може виконувати агент.
- Імовірності переходу (Transition probabilities - T). Розподіл ймовірностей переходу з одного стану в інший за певної дії.
- Винагороди (Rewards - R). Негайна винагорода, яку отримує агент за певну дію в певному стані.
- Коефіцієнт знижки (Discount factor - γ). Параметр, який представляє перевагу, яку агент надає негайним винагородам перед майбутніми винагородами.
Агенти прагнуть знайти політику, яка відображає стани в дії (mapping from states to actions) та максимізує очікувану кумулятивну винагороду з врахуванням знижки (expected cumulative discounted reward). Вони можуть використовувати такі алгоритми, як динамічне програмування (dynamic programming), ітерації по значеннях (value iteration) та ітерації політиках (policy iteration).
POMDP розширює MDP на ситуації, коли спостереження агента є невизначеними або неповними. У POMDP агент безпосередньо не спостерігає справжній стан середовища, але отримує спостереження, які ймовірнісно пов’язані з основним станом. POMDP складаються з таких компонентів [12 p.645].
- Стани (States - S). Те саме, що й в MDP - представляють можливі базові стани агента та середовища.
- Дії (Actions - A). Те саме, що й в MDP - представляють доступні дії агента.
- Спостереження (Observations - O). Скінченна множина спостережень, які агент може отримати на основі основного стану та дій агента.
- Імовірності переходу (Transition probabilities - T). Те саме, що й в MDP - розподіл ймовірностей переходу з одного стану в інший за певної дії.
- Імовірності спостереження (Observation probabilities - Z). Розподіл ймовірностей отримання спостереження з урахуванням певного основного стану та дії.
- Винагороди (Rewards - R). Те саме, що й в MDP - негайна винагорода, яку отримує агент за певну дію в певному стані.
- Коефіцієнт знижки (Discount factor - γ). Те саме, що й в MDP - параметр, який представляє перевагу, яку агент надає негайним винагородам перед майбутніми винагородами.
POMDP вводить концепцію станів переконань (belief states), які є розподілами ймовірностей основних станів, враховуючи спостереження агента. Рішення полягає в пошуку політики, яка відображає стан переконань в дії, враховуючи невизначеність спостережень, що вимагає виведення висновків шляхом міркування над станами переконань (reason over belief states). Для отримання наближених до оптимальних рішень використовуються такі підходи, як точкова ітерація по значеннях (point-based value iteration) і фільтри часток (particle filters).
2.4.2 Байєсівські мережі.
Байєсівські мережі (BN), також відомі як байєсівські мережі переконань (Bayesian belief networks) або моделі імовірнісних графів (probabilistic graphical models), є універсальним і широко використовуваним інструментом представлення знань і міркування для планування та прийняття рішень у системах KBIA. BN дозволяють агентам моделювати та міркувати про невизначеність зв’язків та залежності між змінними ймовірнісним способом [12 p.510].
Поняття BN.
- Орієнтований ациклічний граф (DAG). BN представляється як DAG, де вузли відповідають випадковим змінним, а спрямовані ребра відображають імовірнісні залежності.
- Вузли (випадкові змінні) (nodes). Кожен вузол графа представляє випадкову змінну, яка може бути спостережуваною або ні.
- Таблиці умовної ймовірності (conditional probability tables - CPT). CPT кожного вузла визначає умовні ймовірності, заданого його батьками на графі.
- Теорема Байєса (Bayes' theorem). В BN використовується теорема Байєса для оновлення переконань та виведення висновків на основі спостережених свідчень (observed evidence).
- Алгоритми розповсюдження (propagation algorithms). Для виконання ймовірнісного висновку в BN використовуються такі алгоритми, як усунення змінних (variable elimination) і з’єднання дерев (junction tree), що дозволяє ефективно оновлювати переконання (update beliefs).
- Навчання (learning). BN можна навчатися на даних за допомогою таких методів, як оцінка параметрів (parameter estimation) і вивчення структури (structure learning).
BN надають системам KBIA можливість міркувати про невизначеність і приймати обґрунтовані рішення на основі ймовірностей та моделювати причинно-наслідкові зв’язки, допомагаючи агентам зрозуміти вплив різних факторів на результати. Існують ефективні алгоритми розповсюдження для обчислення ймовірнісного висновку навіть у великих мережах. Моделі BN особливо цінні при роботі в ситуаціях, коли ймовірнісні залежності та невизначеність відіграють значну роль у прийнятті рішень.
2.4.3 RL.
RL - це підхід, який може бути застосований в системах KBIA для планування та прийняття рішень у динамічних і невизначених середовищах. RL дозволяє агентам вивчати оптимальні або близькі до оптимальних політики та стратегії через взаємодію з середовищем, максимізуючи кумулятивні винагороди. Цей підхід є важливим в моделях, для яких явних знань або заздалегідь визначених правил недостатньо, і тому агентам необхідно адаптувати свої політики та стратегії на основі зворотного зв’язку з середовищем [12 p.830, 15].
Концепції RL.
- Агент і середовище (Agent and Environment). Агент взаємодіє з середовищем: він виконує дії, а середовище реагує переходом до нових станів і наданням зворотного зв’язку у вигляді винагороди.
- Стани (States). Представляють умови середовища в момент часу. Вони інкапсулюють усю релевантну інформацію, яка потрібна агенту для прийняття рішень.
- Дії (Actions). Вибір, зроблений агентом для впливу на середовище. Мета агента - сформувати політики та стратегії, які визначатимуть найкращі дії в кожному стані.
- Винагороди (Rewards). Числові значення, які вказують на бажаність дії агента в певному стані. Агенти прагнуть максимізувати сукупні винагороди, які вони отримують в часі.
- Політика (Policy). Стратегія, яка відображає стани в дії. Агент формує політики для прийняття рішень, які оптимізують його довгострокову винагороду.
- Функція цінності (Value Function). Оцінює очікувану кумулятивну винагороду, яку агент може отримати від певного стану, дотримуючись певної політики.
- Q-функція (Q-Function). Відома як функція дія-цінність, оцінює очікувану кумулятивну винагороду, яку агент може отримати від певної пари стан-дія, дотримуючись певної політики.
Методи які можуть бути використані агентом в процесі RL.
- Q-навчання (Q-Learning). Безмодельний алгоритм, який формує оптимальну Q-функцію шляхом дослідження (exploration) та використання (exploitation) дій.
- Методи градієнта політики (Policy Gradient Methods). Безпосередньо формують параметризовану політику, яка максимізує очікувану кумулятивну винагороду.
- Методи актора та критика (Actor-Critic Methods). Поєднують підходи на основі політики (policy-based) та на основі значень цінності (value-based), використовуючи актора для оновлення політики (update policies) та критика для оцінки функцій цінності (estimate value functions).
- Глибоке RL (Deep RL). Поєднує алгоритми RL із глибокими нейронними мережами для роботи з просторами станів великої розмірності та складними середовищами.
RL дозволяє системам KBIA адаптуватися до мінливого середовища та формувати оптимальні стратегії не маючи чітких правил та взаємодіючи з середовищем, що робить його придатним для сценаріїв, де бракує детальних знань. Такий підхід дозволяє вирішувати складні завдання прийняття рішень із великим простором станів та невизначеною динамікою.
При моделюванні агентів, які використовують методи RL, потрібно враховувати такі обставини: знаходження балансу між дослідженням (exploration) і використанням (exploitation); використання великої кількості взаємодій із середовищем для формування ефективні політики; розробка відповідних функцій винагороди може мати вирішальне значення для досягнення бажаної поведінки; неоптимальні або небезпечні політики можуть бути сформовані раніше, ніж будуть знайдені оптимальні або наближені до оптимальних, що може бути загрозою у критично важливих для безпеки програмах.