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

В ітерації за цінностями (англ. value iteration, Bellman, 1957), яку також називають зворотною індукцією, функція ${\displaystyle \pi }$ не використовується; натомість значення ${\displaystyle \pi (s)}$ обчислюється в межах ${\displaystyle V(s)}$ за потребою. Метод ітерації за цінностями для МПВ увійшов до праці Ллойда Шеплі 1953 року про стохастичні ігри[2] як окремий випадок, але це було визнано лише згодом.[3]

Підставлення обчислення ${\displaystyle \pi (s)}$ до обчислення ${\displaystyle V(s)}$ дає поєднаний крок:

${\displaystyle V_{i+1}(s):=\max _{a}\left\{\sum _{s'}P_{a}(s,s')\left(R_{a}(s,s')+\gamma V_{i}(s')\right)\right\},}$

де ${\displaystyle i}$ є номером ітерації. Ітерація за цінностями починається з ${\displaystyle i=0}$ та ${\displaystyle V_{0}}$ як припущення про функцію цінності. Потім виконується ітерування з повторним обчисленням ${\displaystyle V_{i+1}}$ для всіх станів ${\displaystyle s}$, поки ${\displaystyle V}$ не збіжиться, коли ліва сторона дорівнюватиме правій (що є «рівнянням Беллмана» для цієї задачі).

В ітерації за стратегіями (англ. policy iteration, Howard, 1960) перший крок виконується один раз, а потім другий крок повторюється до збіжності. Потім перший крок виконується знову, і так далі.

Замість повторювання другого кроку до збіжності його може бути сформульовано та розв'язано як набір лінійних рівнянь.

Цей варіант має перевагу в тому, що існує чітка умова зупинки: коли масив ${\displaystyle \pi }$ не змінюється в процесі застосування кроку 1 до всіх станів, алгоритм завершується.

У видозміненій ітерації за стратегіями (англ. modified policy iteration, van Nunen, 1976, Puterman & Shin, 1978) перший крок виконується один раз, а потім другий крок повторюється кілька разів. Потім знову перший крок виконується один раз, і так далі.

В цьому варіанті (англ. prioritized sweeping) кроки застосовуються до станів із надаванням переваги тим, які є якимось чином важливими — чи то на основі алгоритму (нещодавно були великі зміни в ${\displaystyle V}$ або ${\displaystyle \pi }$ навколо цих станів), чи то на основі використання (ці стани знаходяться близько до початкового стану, або іншим чином становлять інтерес для особи або програми, яка застосовує цей алгоритм).

Наведене вище розв'язання передбачає, що в той момент, коли треба вирішувати, яку дію вчинити, стан ${\displaystyle s}$ є відомим; інакше ${\displaystyle \pi (s)}$ обчислено бути не може. Якщо це припущення не є вірним, задачу називають частково спостережуваним марковським процесом вирішування (ЧСМПВ, англ. partially observable Markov decision process, POMDP).

Головний поступ у цій області було забезпечено Бурнетасом та Катехакісом в «Оптимальних адаптивних стратегіях для марковських процесів вирішування».[4] В цій праці було побудовано клас адаптивних стратегій, які володіють властивостями рівномірно максимального темпу збіжності для загальної очікуваної винагороди скінченного інтервалу, за припущень скінченних просторів стан-дія та нескоротності закону переходу. Ці стратегії приписують, щоби вибір дій на кожному стані в кожен момент часу ґрунтувався на показниках, які є роздуваннями правої сторони рівнянь оптимальності очікуваної усередненої винагороди.

Якщо ймовірності винагород є невідомими, то задача є задачею навчання з підкріпленням (Sutton та Barto, 1998).

Для цього корисно визначити наступну функцію, яка відповідає вчиненню дії ${\displaystyle a}$ з продовженням оптимальним чином (або відповідно до будь-якої наявної в даний момент стратегії):

${\displaystyle \ Q(s,a)=\sum _{s'}P_{a}(s,s')(R_{a}(s,s')+\gamma V(s')).\ }$

І хоча ця функція також є невідомою, досвід під час навчання ґрунтується на парах ${\displaystyle (s,a)}$ (разом з наслідком ${\displaystyle s'}$; тобто, «Я був у стані ${\displaystyle s}$, спробував вчинити ${\displaystyle a}$, і сталося ${\displaystyle s'}$»). Таким чином, є масив ${\displaystyle Q}$, і досвід використовується для його безпосереднього уточнення. Це відоме як Q-навчання.

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

Ще одне застосування процесу МПВ в теорії машинного навчання називається автоматами з самонавчанням. Воно також є одним із типів навчання з підкріпленням, якщо середовище має стохастичний характер. Перше детальне дослідження про автомати з самонавчанням (англ. learning automata) здійснили Нарендра та Татачар (1974), в якому їх було первісно описано явно як скінченні автомати.[5] Подібно до навчання з підкріпленням, алгоритм автоматів із самонавчанням також має перевагу розв'язання задач, у яких імовірності або винагороди є невідомими. Відмінність автоматів із самонавчанням від Q-навчання полягає в тому, що вони не включають пам'ять Q-значень, а для знаходження результату навчання уточнюють ймовірності дій безпосередньо. Автомати з самонавчанням є однією зі схем навчання з суворим доведенням збіжності.[6]

В теорії автоматів із самонавчанням стохастичний автомат (англ. stochastic automaton) складається з:

• множини можливих входів x,
• множини можливих внутрішніх станів Φ = { Φ₁, …, Φ_s },
• множини можливих виходів, або дій, α = { α₁, …, α_r }, де r≤s,
• вектора початкової ймовірності станів p(0) = ≪ p₁(0), …, p_s(0) ≫,
• обчислюваної функції A, яка після кожного кроку часу t породжує p(t+1) з p(t), поточного входу та поточного стану, і
• функції G: Φ → α, яка породжує вихід на кожному кроці часу.

Стани такого автомату відповідають станам «марковського процесу дискретного часу з дискретними параметрами».[7] На кожному кроці часу t=0,1,2,3,… автомат читає вхід зі свого середовища, уточнює P(t) до P(t+1) за допомогою A, випадково обирає наступний стан відповідно до ймовірностей P(t+1) та виводить відповідну дію. Середовище автомата, в свою чергу, читає цю дію, і надсилає автоматові наступний вхід.[6]

Крім як через винагороди, марковський процес вирішування ${\displaystyle (S,A,P)}$ можна розуміти і в термінах теорії категорій. А саме, нехай ${\displaystyle {\mathcal {A}}}$ позначає вільний моноїд з породжувальною множиною ${\displaystyle A}$. Нехай ${\displaystyle \mathbf {Dist} }$ позначає категорію Клайслі монади Жирі. Тоді функтор ${\displaystyle {\mathcal {A}}\to \mathbf {Dist} }$ кодує як множину станів ${\displaystyle S}$, так і функцію ймовірностей ${\displaystyle P}$.

Таким чином, марковський процес вирішування може бути узагальнено з моноїдів (категорій з одним об'єктом) на довільні категорії. Результат ${\displaystyle ({\mathcal {C}},F:{\mathcal {C}}\to \mathbf {Dist} )}$ можна назвати контекстно-залежним марковським процесом вирішування (англ. context-dependent Markov decision process), оскільки перехід від одного об'єкту до іншого в ${\displaystyle {\mathcal {C}}}$ змінює множину доступних дій та множину можливих станів.

Для обговорення марковських процесів вирішування безперервного часу введімо два набори позначень:

Якщо простір станів та простір дій є скінченними,

• ${\displaystyle {\mathcal {S}}}$: простір станів (англ. State space);
• ${\displaystyle {\mathcal {A}}}$: простір дій (англ. Action space);
• ${\displaystyle q(i|j,a)}$: ${\displaystyle {\mathcal {S}}\times {\mathcal {A}}\rightarrow \triangle {\mathcal {S}}}$, функція інтенсивності переходів (англ. transition rate function);
• ${\displaystyle R(i,a)}$: ${\displaystyle {\mathcal {S}}\times {\mathcal {A}}\rightarrow \mathbb {R} }$, функція винагороди (англ. reward function).

Якщо простір станів та простір дій є неперервними,

• ${\displaystyle {\mathcal {X}}}$: простір станів (англ. state space);
• ${\displaystyle {\mathcal {U}}}$: простір можливого керування (англ. space of possible control);
• ${\displaystyle f(x,u)}$: ${\displaystyle {\mathcal {X}}\times {\mathcal {U}}\rightarrow \triangle {\mathcal {X}}}$, функція інтенсивності переходів (англ. transition rate function);
• ${\displaystyle r(x,u)}$: ${\displaystyle {\mathcal {X}}\times {\mathcal {U}}\rightarrow \mathbb {R} }$, функція інтенсивності винагороди (англ. reward rate function), така, що ${\displaystyle r(x(t),u(t))dt=dR(x(t),u(t))}$, де ${\displaystyle R(x,u)}$ є функцією винагороди, яку ми обговорювали в попередньому випадку.

Як і в марковських процесах вирішування дискретного часу, в марковському процесі вирішування безперервного часу ми хочемо знаходити оптимальну стратегію (англ. policy) або керування (англ. control), яке давало би нам оптимальну очікувану проінтегровану винагороду:

${\displaystyle \max \quad \mathbb {E} _{u}[\int _{0}^{\infty }\gamma ^{t}r(x(t),u(t)))dt|x_{0}]}$

Де ${\displaystyle 0\leq \gamma <1}$

Якщо простори станів та дій є скінченними, то для пошуку оптимальної стратегії ми можемо використовувати лінійне програмування, що було одним із найперших застосованих підходів. Тут ми розглядаємо лише ергодичну модель, яка означає, що наш МПВ безперервного часу стає ергодичним марковським ланцюгом безперервного часу за сталої стратегії. За цього припущення, хоча ухвалювач рішення і може здійснювати рішення в будь-який час у поточному стані, він не може виграти більше, здійснюючи більше ніж одну дію. Для нього краще здійснювати дію лише в той момент часу, коли система переходить з поточного стану до іншого. За деяких умов (детальніше див. Наслідок 3.14 у Continuous-Time Markov Decision Processes), якщо наша функція оптимальної цінності ${\displaystyle V^{*}}$ є незалежною від стану ${\displaystyle i}$, то ми матимемо наступну нерівність:

${\displaystyle g\geq R(i,a)+\sum _{j\in S}q(j|i,a)h(j)\quad \forall i\in S\,\,and\,\,a\in A(i)}$

Якщо існує функція ${\displaystyle h}$, то ${\displaystyle {\bar {V}}^{*}}$ буде найменшим ${\displaystyle g}$, яке задовольняє наведене вище рівняння. Щоби знаходити ${\displaystyle {\bar {V}}^{*}}$, ми можемо застосовувати наступну модель лінійного програмування:

• Пряма лінійна програма (П-ЛП, англ. primal linear program, P-LP)

${\displaystyle {\begin{aligned}{\text{Minimize}}\quad &g\\{\text{s.t}}\quad &g-\sum _{j\in S}q(j|i,a)h(j)\geq R(i,a)\,\,\forall i\in S,\,a\in A(i)\end{aligned}}}$

• Двоїста лінійна програма (Д-ЛП, англ. dual linear program, D-LP)

${\displaystyle {\begin{aligned}{\text{Maximize}}&\sum _{i\in S}\sum _{a\in A(i)}R(i,a)y(i,a)\\{\text{s.t.}}&\sum _{i\in S}\sum _{a\in A(i)}q(j|i,a)y(i,a)=0\quad \forall j\in S,\\&\sum _{i\in S}\sum _{a\in A(i)}y(i,a)=1,\\&y(i,a)\geq 0\qquad \forall a\in A(i)\,\,and\,\,\forall i\in S\end{aligned}}}$

${\displaystyle y(i,a)}$ є придатним розв'язком Д-ЛП, якщо ${\displaystyle y(i,a)}$ є невиродженою, і задовольняє обмеження задачі Д-ЛП. Придатний розв'язок Д-ЛП ${\displaystyle y^{*}(i,a)}$ називають оптимальним розв'язком, якщо

${\displaystyle {\begin{aligned}\sum _{i\in S}\sum _{a\in A(i)}R(i,a)y^{*}(i,a)\geq \sum _{i\in S}\sum _{a\in A(i)}R(i,a)y(i,a)\end{aligned}}}$

для всіх придатних розв'язків Д-ЛП ${\displaystyle y(i,a)}$. Щойно ми знайшли оптимальний розв'язок ${\displaystyle y^{*}(i,a)}$, ми можемо використовувати його для встановлення оптимальних стратегій.

Якщо простір станів та простір дій в МПВ безперервного часу є неперервними, то оптимальний критерій можна знаходити шляхом розв'язання диференціального рівняння Гамільтона — Якобі — Беллмана (ГЯБ, англ. Hamilton–Jacobi–Bellman equation, HJB) в часткових похідних. Для обговорення рівняння ГЯБ нам необхідно переформулювати нашу задачу:

${\displaystyle {\begin{aligned}V(x(0),0)=&{\text{max}}_{u}\int _{0}^{T}r(x(t),u(t))dt+D[x(T)]\\s.t.\quad &{\frac {dx(t)}{dt}}=f[t,x(t),u(t)]\end{aligned}}}$

${\displaystyle D(\cdot )}$ є функцією остаточної винагороди (англ. terminal reward function), ${\displaystyle x(t)}$ є вектором стану системи, ${\displaystyle u(t)}$ є вектором керування системою, який ми намагаємося знайти. ${\displaystyle f(\cdot )}$ показує, як стан системи змінюється з часом. Рівняння Гамільтона — Якобі — Беллмана є таким:

${\displaystyle 0={\text{max}}_{u}(r(t,x,u)+{\frac {\partial V(t,x)}{\partial x}}f(t,x,u))}$

Ми можемо розв'язувати це рівняння, щоби знаходити оптимальне керування ${\displaystyle u(t)}$, яке давало би нам оптимальну цінність ${\displaystyle V^{*}}$

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