Олексій Ігнатенко
Визначена скалярна функція \( R_t \) - винагорода в момент часу \( t \). Ця функція:
Агент:
Середовище:
Історія:
\( H_t = O_1 R_1 A_1 O_2 R_2 ... A_{t-1} O_t R_t \)
Стан:
Ми в основному будемо розглядати стан який є у агента (його представлення світу)
Може включати наступні компоненти:
Мета: вибирати дії, які максимізують майбутній очікуваний (сумарний) виграш
Відношення переважності задає відношення порядку на просторі станів. Ще фон Нейман показав, що якщо виконуються 6 аксіом, то можна ввести функцію корисності, яка описує переваги агента. Раціональний агент намагається діяти найкращим чином для досягнення мети. Це означає, що агент має класифікувати власні дії на ті, що наближують до мети (більш бажані) і ті, що відділяють від мети.
Поняття мети формалізується за допомогою функції корисності. Ця функція є відображенням з простору станів гри (у які може потрапити агент) у числову вісь
\( u_i(⋅): S → R \)
Визначення функції корисності для реальних задач може бути складним і вимагає глибокого розуміння проблемної області.
Задання функції корисності задає на просторі станів упорядкування, яке має наступні властивості:
Функції корисності можна використовувати для визначення поведінки практично будь-яких агентів.
Після визначення функцій корисності потрібно визначити як агенти будуть їх використовувати. Як правило, агенти отримують інформацію про поточний стан та мають певні можливості змінювати його, вибираючи власні дії. Іноді, звичайно ці дії не досконалі - сенсори можуть помилятися, а механізми не завжди працювати як очікується.
Введемо до розгляду функцію переходу \( T(s,a,s0) \) яка дорівнює ймовірності переходу зі стану \( s \) в стан \( s0 \) за умови виконання дії \( a \). Зрозуміло, що сума \( T(s,a,s0) \) за всіма можливими \( s0 \), a має дорівнювати одиниці. Використовуючи функцію корисності агенти можуть обчислити очікувану корисність від здійснення дії \( a \) в стані \( s \)
\( E[u_i,s,a]=∑_{s′∈S}T(s,a,s′)u_i(s′) \)
де \( S \) - множина всіх можливих станів.
Policy - політика, аналог стратегії в теорії корисності. Політика визначає що має робити агент для будь-якої ситуації. Агент намагається знайти оптимальну політику - ту, що максимізує його очікувану корисність. Дерева рішень (або мережі рішень) описують поведінку агента за умов скінченної та відомої кількості рішень, виграшів та ймовірностей. Як правило, розв’язуються за допомогою зворотної індукції.
Якщо кількість кроків до мети невідома або може бути нескінченною, для моделювання використовують Марковські процеси.
Поки що ми розглядали ситуацію певного фіксованого стану світу. В реальних задачах агенти існують у середовищі, стан якого змінюється внаслідок дій агента або зовнішних подій. Тобто агент сприймає стан світу, виконує дію, сприймає новий змінений стан. Спрощуючи, можна вважати, що стан світу в момент часу \( t_i \) залежить лише від дії агента у попередній момент часу \( t_{i−1} \) і стану \( s(t_{i−1}) \). Формально ця ідея виражається Марковським процесом прийняття рішень (МППР).
Визначення. (Марковського процесу прийняття рішень). МППР визначається початковим станом \( s_1∈S, \) перехідною функцією \( T(s,a,s0) \) і функцією виграшу \( r:S→R \).
Є два головних типи:
Перехідна функція \( T(s,a,s0) \) дорівнює ймовірності переходу агента зі стану \( s \) в стан \( s0 \) при здійсненні дії \( a \). Для чисто детерміністичного світу ця функція буде для кожного фіксованого \( s \) приймати значення 1 для одного \( s0 \) і 0 для всіх інших пар.
Поведінка агента визначається стратегією, яка є відображенням множини станів у множину дій. Будемо позначати її \( \pi \). Мета агента - знайти оптимальну стратегію, тобто ту, що максимізує очікувану корисність (бо егоїстичний агент піклується тільки про свою власну корисність).
Отже, оптимальна стратегія агента дорівнює:
\( \pi^∗_i(s)=argmax_{a∈A}E[u_i,s,a] \)
Але для виконання обчислення очікуваного значення потрібно вирішити проблему врахування майбутніх виграшів. Що краще - здійснити 100 дій з 0 виграшем а потім отримати 100, чи виконати 100 дій з виграшем 1 за кожну. Встановлення значень виграшів диктується задачею і може вплинути на роботу алгоритма.
Існує три загальноприйнятих способа інтегрувати поточні виграші у функцію корисності \( V(⋅) \)
повна винагорода: \( V=∑^∞_{i=1}r(s_i) \)
Працює для випадків коли сума точно скінчена, інакше важко порівнювати виграші різних політик. (наприклад ненульова ймовірність переходу у термінальний стан гарантує скінченність)
середня винагорода: \( V=lim_{n→∞}(\frac{r(s_1)+...+r(s_n)}{n}) \)
В цьому випадку виграші усереднені протягом часу. Тут важлива скінченність виграшів. Якщо виграші скінченні, то ліміт нульовий, отже всі дії агента будуть мати нульову корисність. Однак, якщо додати нескінченну кількість дій, то єдине. що буде важливим - останній стан агента. Тобто неважливо скільки поганих виграшів він отримав на шляху до виграшної ситуації.
дисконтована винагорода: \( V = γ^0 r(s_1)+γ^1 r(s_2)+γ^2 r(s_3)+... \)
При використанні цього підходу визначається дисконтуюча змінна \( γ∈[0,1] \), яка зменшує майбутній очікуваний виграш. Якщо \( γ=1 \), то даний виграш співпадає з повною винагородою, Якщо \( γ=0 \), то агент ігнорує майбутні винагороди (жадібна стратегія). Для всіх інших значень агент враховує майбутні виграші тою чи іншою мірою. Гарантується також, що функція корисності скінченна для випадку скінченних виграшів.
При цьому ми володіємо інформацією тільки про \( s_1 \). Всі інші значення залежать від перехідної функції \( T(⋅) \), наприклад ми знаємо ймовірності переходу зі стану \( s_1 \) в інші стани для кожної дії \( a \). Вважаючи, що агент максимізує корисність, його стратегія має вибиратись з умови
\( \pi^∗(s)=argmax_{a∈A}T(s,a,s′)u(s′) \)
globals [current-action r current-utility]
to setup
clear-all
reset-ticks
ask patch -1 0 [set pcolor white
set plabel "wall "
set plabel-color black]
ask patch 1 1 [set pcolor green
set plabel "+ 1 "
set plabel-color black]
ask patch 1 0 [set pcolor red
set plabel " - 1 "
set plabel-color black]
create-turtles 1 [
set color blue
set size 0.7
set shape "person"
setxy -2 -1]
end
to go
tick
perform-action
calculate-reward
end
to to-left
set current-action "left"
go
end
to to-right
set current-action "right"
go
end
to to-up
set current-action "up"
go
end
to perform-action
ask turtles [
if ((current-action = "left") and (check-constraints (pxcor - 1) pycor) = true)
[
setxy pxcor - 1 pycor
]
if ((current-action = "right") and (check-constraints (pxcor + 1) pycor))
[
setxy pxcor + 1 pycor
]
if ((current-action = "up") and (check-constraints pxcor (pycor + 1)))
[
setxy pxcor pycor + 1
]
]
end
to calculate-reward
ask turtles [
let my-patch patch-here
if (([pcolor] of my-patch) = green) [
set current-utility current-utility + green-reward
]
if (([pcolor] of my-patch) = red) [
set current-utility current-utility + red-reward
]
if (([pcolor] of my-patch) = black) [
set current-utility current-utility + black-reward
]
]
end
to-report check-constraints [x y]
let f false
if (x <= max-pxcor) and (x >= min-pxcor) and (y <= max-pycor) and (y >= min-pycor)
[
set f true
]
let p patch x y
if (p != nobody) [
if ([pcolor] of patch x y = white)
[
set f false
]
]
report f
end