Лекція 4

Лекція 4. Алгоритм обчислення функції корисності.

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

Alice … went on “Would you please tell me, please, which way I ought to go from here?” “That depends a good deal on where you want to get to,” said the Cat. “I don’t much care where -” said Alice. “Then it doesn’t matter which way you go,” said the Cat. Lewis Carroll (1832-1898) Alice’s Adventures in Wonderland, 1865

Отже агент приймає рішення на основі трьох елементів:

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

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

\[u_{i}(\cdot): S \rightarrow R \]
Визначення функції корисності для реальних задач може бути складним і вимагає глибокого розуміння проблемної області. Задання функції корисності задає на просторі станів упорядкування, яке має наступні властивості:

• рефлексивність: \(u_{i}(s) \ge u_{i}(s)\);
• транзитивність: Якщо \(u_{i}(a) \ge u_{i}(b)\) і \(u_{i}(b) \ge u_{i}(c)\) то \(u_{i}(a) \ge u_{i}(с)\);
• порівнюваність: для всіх \(a,b\) виконується або \(u_{i}(a) \ge u_{i}(b)\) або \(u_{i}(b) \ge u_{i}(a)\).

Функції корисності можна використовувати для визначення поведінки практично будь-яких агентів. Також вони корисні для врахування різних додаткових обставин, які агент має брати до уваги при планування своїх дій. Наприклад, можна розглянути ситуацію, коли агент отримує певну суму за доставку вантажу але також має враховувати витрати на дорогу (час, ресурси) та можливу втрату через пропуск більш вигідної пропозиції. Якщо перевести всі ці фактори у функцію корисності, ми зможемо дослідити які дії є оптимальними.

Корисність - це не про гроші.

Зауважимо, що корисність представляє переважність агента відносно того або іншого стану, що, очевидно, не завжди дорівнює грошам. Дослідження показали, що відношення корисності і грошей можна оцінити як логарифм. Наприклад, розглянемо двох гравців А та Б. У А є 100 мільйонів у банку, у Б - 0. Кожному надається можливість виграти мільйон доларів. Очевидно, що цінність (корисність) виграшу неоднакова для А і Б. Для Б вона набагато вища. Експерименти демонструють, що для невеликих сум корисність лінійна, зі збільшенням вона стає логарифмічна в тому сенсі, що корисність десятого мільйона доларів меньше ніж в десять раз більша за корисність першого. Деякі експерименти показують, що власне коли справа у грошах люди не мислять раціонально. Проведемо експеримент: Який варіант ви оберете

(а) Отримати 10000 грн і 50/50 шанс ще 10000 грн

(б) Отримати 20000 грн і потім я підкину монетку і якщо випаде герб то заберу у вас 10000 грн.

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

Після визначення функцій корисності потрібно визначити як агенти будуть їх використовувати. Як правило, агенти отримують інформацію про поточний стан та мають певні можливості змінювати його, вибираючи власні дії. Іноді, звичайно ці дії не досконалі - сенсори можуть помилятися, а механізми не завжди працювати яе очікується. Введемо до розгляду функцію переходу \(T(s,a,s_{0})\) яка дорівнює ймовірності переходу зі стану \(s\) в стан \(s_{0}\) за умови виконання дії \(a\). Зрозуміло, що сума \(T(s,a,s_{0})\) за всіма можливими \(s_{0}\), \(a\) має дорівнювати одиниці. Використовуючи функцію корисності агенти можуть обчислити очікувану корисність від здійснення дії \(a\) в стані \(s\):

\[E[u_{i},s,a]= \sum_{s' \in S} T(s,a,s')u_{i}(s') \] де \(S\) - множина всіх можливих станів.

Агент може використовувати очікувану корисність для оцінки вартості інформації, що надійшла від іншого агента або сенсора. Вартість інформації визначається формулою: \[ E[u_{i}, t, \pi_{i}(t)] − E[u_{i}, t, \pi_{i}(s)]\]
як різниця між очікуваною корисністю за умови використання найкращої стратегії \(\pi_{i}(t)\) у стані \(t\) та використання найкращої стратегії \(\pi_{i}(s)\) для стану \(s\) за умови перебуванні у стані \(t\).

Policy

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

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

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

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

Визначення. (Марковського процесу прийняття рішень). МППР визначається початковим станом \(s_{1}\in S\), перехідною функцією \(T(s, a, s_{0})\) і функцією виграшу \(r:S\rightarrow R\).

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

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

Перехідна функція \(T(s, a, s_{0})\) дорівнює ймовірності переходу агента зі стану \(s\) в стан \(s_{0}\) при здійсненні дії \(a\). Для чисто детерміністичного світу ця функція буде для кожного фіксованого \(s\) приймати значення \(1\) для одного \(s_{0}\) і \(0\) для всіх інших пар.

Поведінка агента визначається стратегією, яка є відображенням множини станів у множину дій. Будемо позначати її \(\pi\). Мета агента - знайти оптимальну стратегію, тобто ту, що максимізує очікувану корисність (бо егоїстичний агент піклується тільки про свою власну корисність). Отже, оптимальна стратегія агента дорівнює: \[\pi_{i}^{*}(s) = \underset{a\in A}{argmax}\;E[u_{i},s,a]\]

Але для виконання обчислення очікуваного значення потрібно вирішити проблему врахування майбутніх виграшів. Що краще - здійснити 100 дій з 0 виграшем а потім отримати 100, чи виконати 100 дій з виграшем 1 за кожну. Встановлення значень виграшів диктується задачею і може вплинути на роботу алгоритма.

Існує три загальноприйнятих способа інтегрувати поточні виграші у функцію корисності \(V(\cdot)\):

• повна винагорода: \(V = \sum_{i=1}^{\infty}r(s_{i})\). Працює для випадків коли сума точно скінчена, інакше важко порівнювати виграші різних політик. (наприклад ненульова ймовірність переходу у термінальний стан гарантує скінченність)
• середня винагорода: \(V = \lim_{n \rightarrow \infty}(\frac{r(s_{1}) + ... + r(s_{n})}{n})\). В цьому випадку виграші усереднені протягом часу. Тут важлива скінченність виграшів. Якщо виграші скінченні, то ліміт нульовий, отже всі дії агента будуть мати нульову корисність. Однак, якщо додати нескінченну кількість дій, то єдине. що буде важливим - останній стан агента. Тобто неважливо скільки поганих виграшів він отримав на шляху до виграшної ситуації.
• дисконтована винагорода: \(V = \gamma^0 r(s_{1}) + \gamma^1 r(s_{2}) + \gamma^2 r(s_{3}) + ...\). При використанні цього підходу визначається дисконтуюча змінна \(\gamma \in [0,1]\), яка зменшує майбутній очікуваний виграш. Якщо \(\gamma = 1\), то даний виграш співпадає з повною винагородою, Якщо \(\gamma = 0\), то агент ігнорує майбутні винагороди (жадібна стратегія). Для всіх інших значень агент враховує майбутні виграші тою чи іншою мірою. Гарантується також, що функція корисності скінченна для випадку скінченних виграшів.

При цьому ми володіємо інформацією тільки про \(s_{1}\). Всі інші значення залежать від перехідної функції \(T(\cdot)\), наприклад ми знаємо ймовірності переходу зі стану \(s_{1}\) в інші стани для кожної дії \(a\). Вважаючи, що агент максимізує корисність, його стратегія має вибиратись з умови \[\pi^{*}(s) = \underset{a\in A}{argmax}\;T(s,a,s')u(s')\]

Таким чином, агент обчислює виграш від здійснення тієї чи іншою дії використовуючи функцію корисності, корисність для кожного стану визначається рівнянням \[u(s) = r(s) + \gamma max_{a} T(s,a,s')u(s')\]. Це правда означає, що значення функції в одному стані залежать від значень в інших станах, тому для її обчислення потрібний ітераційний розподілений алгоритм.

Спробуємо імплементувати в Netlogo базовий приклад

Отже світ 5-3, є дві клітинки з винагородою. При цьому можливими рухами є:

• праворуч
• ліворуч
• вгору

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

Як додати ймовірності? Як вивести поточні виграші? Як вивести функцію корисності?