MAS_lecture_3. Формулювання проблеми

Олексій Ігнатенко

Формулювання проблеми

Визначена скалярна функція \( R_t \) - винагорода в момент часу \( t \). Ця функція:

  • показує наскільки успішно агент виконує свою задачу;
  • задача агента: макимізувати сумарну винагороду;
  • Винагорода може задаватись різними способами.

Гіпотеза про винагороду

Будь-яка задача агента (в будь-якій задачі) може бути визначена у вигляді максимізації очікуваної сумарної винагороди

Як функціонує агент у середовищі?

Агент:

  • Отримує спостереження від середовища
  • Вибирає дію для впливу на середовище
  • Отримує (скалярну) винагороду за свою дію

Середовище:

  • отримує дію агента
  • генерує нове спостереження
  • генерує винагороду

Формально

Історія:

\( H_t = O_1 R_1 A_1 O_2 R_2 ... A_{t-1} O_t R_t \)

Стан:

  • Стан визначає дії агента.
    • Стан це будь-яка функція від історії \( S_t = f(H_t) \)

Ми в основному будемо розглядати стан який є у агента (його представлення світу)

Властивість Маркова

Майбутне визначається поточним станом, і не залежить від попередньої історії

Агент, що навчається

Може включати наступні компоненти:

  • Policy: функція поведінки агента
  • Value function: оцінка поточного стану та/або дії
  • Model: представлення середовища агентом

Перші два - функція корисності

Мета: вибирати дії, які максимізують майбутній очікуваний (сумарний) виграш

  • дії можуть мати довгострокові наслідки
  • винагорода може приходити з затримкою
  • іноді краще відмовитись від частини винагороди зараз для того, щоб отримати більше потім

Агент і середовище. Агент приймає рішення на основі трьох елементів

  • можливостей агента. Агент вибирає з рішень, які є у нього в наявності;
  • картини світу агента. Агент сприймає навколишній світ і формує уявлення про нього. Його рішення залежать від цього уявлення;
  • the agent’s preferences. Коли агент має діяти за умов невизначеності, він має зважати не тільки на найбільш ймовірні ситауації але і враховувати можливі, хоча й малоймовірні ситуації. Деякі ситуації можуть призвести до кращих або гірших наслідків. Тому важливо включити в поняття “цілі” агента обчислення очікуваного результату.

Функція корисності

Відношення переважності задає відношення порядку на просторі станів. Ще фон Нейман показав, що якщо виконуються 6 аксіом, то можна ввести функцію корисності, яка описує переваги агента. Раціональний агент намагається діяти найкращим чином для досягнення мети. Це означає, що агент має класифікувати власні дії на ті, що наближують до мети (більш бажані) і ті, що відділяють від мети.

Функція корисності

Поняття мети формалізується за допомогою функції корисності. Ця функція є відображенням з простору станів гри (у які може потрапити агент) у числову вісь

\( u_i(⋅): S → R \)

Визначення функції корисності для реальних задач може бути складним і вимагає глибокого розуміння проблемної області.

Властивості функції корисності

Задання функції корисності задає на просторі станів упорядкування, яке має наступні властивості:

  • рефлексивність: \( u_i(s)≥u_i(s) \)
  • транзитивність: Якщо \( u_i(a)≥u_i(b) \) і \( u_i(b)≥u_i(c) \) то \( u_i(a)≥u_i(с) \)
  • порівнюваність: для всіх \( a,b \) виконується або \( u_i(a)≥u_i(b) \) або \( u_i(b)≥u_i(a) \)

Функції корисності можна використовувати для визначення поведінки практично будь-яких агентів.

Очікувана корисність

Після визначення функцій корисності потрібно визначити як агенти будуть їх використовувати. Як правило, агенти отримують інформацію про поточний стан та мають певні можливості змінювати його, вибираючи власні дії. Іноді, звичайно ці дії не досконалі - сенсори можуть помилятися, а механізми не завжди працювати як очікується.

Очікувана корисність

Введемо до розгляду функцію переходу \( 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

Policy - політика, аналог стратегії в теорії корисності. Політика визначає що має робити агент для будь-якої ситуації. Агент намагається знайти оптимальну політику - ту, що максимізує його очікувану корисність. Дерева рішень (або мережі рішень) описують поведінку агента за умов скінченної та відомої кількості рішень, виграшів та ймовірностей. Як правило, розв’язуються за допомогою зворотної індукції.

Якщо кількість кроків до мети невідома або може бути нескінченною, для моделювання використовують Марковські процеси.

Марковський процес прийняття рішень (MDP)

Поки що ми розглядали ситуацію певного фіксованого стану світу. В реальних задачах агенти існують у середовищі, стан якого змінюється внаслідок дій агента або зовнішних подій. Тобто агент сприймає стан світу, виконує дію, сприймає новий змінений стан. Спрощуючи, можна вважати, що стан світу в момент часу \( t_i \) залежить лише від дії агента у попередній момент часу \( t_{i−1} \) і стану \( s(t_{i−1}) \). Формально ця ідея виражається Марковським процесом прийняття рішень (МППР).

Марковський процес прийняття рішень

Визначення. (Марковського процесу прийняття рішень). МППР визначається початковим станом \( s_1∈S, \) перехідною функцією \( T(s,a,s0) \) і функцією виграшу \( r:S→R \).

Типи

Є два головних типи:

  • В Марковському процесі з повною інормованістю агент знає свій поточний стан при прийнятті рішення;
  • В Марковському процесі з частковою інформованістю (POMDP) агент може отримувати певну інформацію, що залежить від поточного стану та має доступ до історії таких вимірів і власних дій.

Перехідна функція

Перехідна функція \( 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

Go

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

Задачі

  • Як вивести поточний виграш агента?
  • Як додати ймовірності при русі?
  • Як написати програму яка хоч якось знаходить зелену клітинку? (не знаючи поля)