Перегляд вихідного коду сторінки Марковський процес вирішування

'''Ма́рковські проце́си вирі́шування''' ('''МПВ''', {{lang-en|Markov decision process, MDP}}) забезпечують математичну систему для моделювання [[ухвалення рішень]] у ситуаціях, в яких наслідки є частково [[Випадковість (математика)|випадковими]], а частково контрольованими ухвалювачем рішення. МПВ є корисними для дослідження широкого спектра [[Задача оптимізації|задач оптимізації]], розв'язуваних [[Динамічне програмування|динамічним програмуванням]] та [[Навчання з підкріпленням|навчанням з підкріпленням]]. МПВ були відомі щонайменше з 1950-х років (пор. {{harvnb|Bellman|1957}}). Основна маса досліджень марковських процесів вирішування стала результатом книги {{нп|Рональд Артур Говард|Рональда Говарда||Ronald A. Howard}}, опублікованої 1960 року, «Динамічне програмування та марковські процеси» ({{lang-en|Dynamic Programming and Markov Processes}}).{{sfn|Howard|1960}} Їх застосовують у широкій області дисциплін, включно з [[Робототехніка|робототехнікою]], [[Автоматичне керування|автоматизованим керуванням]], [[Економіка|економікою]] та [[виробництво]]м.

Якщо точніше, то марковський процес вирішування є [[Стохастичність|стохастичним]] процесом [[Теорія оптимального керування|керування]] {{нп|Дискретний час|дискретного часу||Discrete time}}. На кожному кроці часу процес перебуває в якомусь стані <math>s</math>, і ухвалювач рішення може обрати будь-яку дію <math>a</math>, доступну в стані <math>s</math>. Процес реагує на наступному кроці часу випадковим переходом до нового стану <math>s'</math> і наданням ухвалювачеві рішення відповідної винагороди ({{lang-en|reward}}) <math>R_a(s,s')</math>.

Ймовірність переходу процесу до його нового стану <math>s'</math> знаходиться під впливом обраної дії. Конкретно, вона задається функцією переходу стану <math>P_a(s,s')</math>. Таким чином, наступний стан <math>s'</math> залежить від поточного стану <math>s</math> та від дії ухвалювача рішення <math>a</math>. Але для заданих <math>s</math> та <math>a</math> він є умовно незалежним від усіх попередніх станів та дій; іншими словами, переходи станів процесу МПВ задовольняють [[Марковська властивість|''марковську властивість'']].

Марковські процеси вирішування є розширенням [[Марковський ланцюг|марковських ланцюгів]]; різниця полягає в доданні дій (що дає вибір) та винагород (що дає мотивацію). І навпаки, якщо для кожного стану існує лише одна дія (наприклад, «чекати») та всі винагороди є однаковими (наприклад, «нуль»), то марковський процес вирішування зводиться до [[Марковський ланцюг|марковського ланцюга]].

== Визначення ==
[[Файл:Markov Decision Process example.png|400px|right|thumb|Приклад простого МПВ з трьома станами та двома діями.]]

Марковський процес вирішування є [[Кортеж|5-кою]] <math>(S,A,P_\cdot(\cdot,\cdot),R_\cdot(\cdot,\cdot),\gamma)</math>, де

* <math>S</math> є скінченною множиною станів,
* <math>A</math> є скінченною множиною дій (як альтернатива, <math>A_s</math> є скінченною множиною дій, доступних зі стану <math>s</math>),
* <math>P_a(s,s') = \Pr(s_{t+1}=s' \mid s_t = s, a_t=a)</math> є ймовірністю того, що дія <math>a</math> в стані <math>s</math> в момент часу <math>t</math> призведе до стану <math>s'</math> в момент часу <math>t+1</math>,
* <math>R_a(s,s')</math> є безпосередньою винагородою (або очікуваною безпосередньою винагородою), отримуваною після переходу до стану <math>s'</math> зі стану <math>s</math>,
* <math>\gamma \in [0,1]</math> є [[Q-навчання#Коефіцієнт знецінювання|коефіцієнтом знецінювання]] ({{lang-en|discount factor}}), який представляє відмінність важливості майбутніх та поточних винагород.

(Зауваження: Теорія марковських процесів вирішування не стверджує, що <math>S</math> чи <math>A</math> є скінченними, але основні алгоритми, наведені нижче, передбачають, що вони є скінченними.)

== Задача ==

Основною задачею МПВ є знайти «стратегію» ({{lang-en|policy}}) для ухвалювача рішень: функцію <math>\pi</math>, яка визначає дію <math>\pi(s)</math>, яку ухвалювач рішення обере в стані <math>s</math>. Зауважте, що щойно марковський процес вирішування поєднано таким чином зі стратегією, то це фіксує дію для кожного стану, і отримане в результаті поєднання поводиться як [[марковський ланцюг]].

Метою є обрати таку стратегію <math>\pi</math>, яка максимізуватиме деяку кумулятивну функцію випадкових винагород, зазвичай&nbsp;— очікувану знецінену функцію над потенційно нескінченним горизонтом:

: <math>\sum^{\infty}_{t=0} {\gamma^t R_{a_t} (s_t, s_{t+1})} </math> &nbsp;&nbsp;&nbsp;(де ми обираємо <math>a_t = \pi(s_t)</math>)

де <math>\ \gamma \ </math> є [[Q-навчання#Коефіцієнт знецінювання|коефіцієнтом знецінювання]], і задовольняє <math>0 \le\ \gamma\ < 1</math>. (Наприклад, <math> \gamma = 1/(1+r) </math>, де інтенсивністю знецінювання є <math>r</math>.) Зазвичай <math> \gamma </math> є близьким до 1.

Завдяки марковській властивості, оптимальну стратегію для цієї конкретної задачі насправді може бути записано як функцію лише від <math>s</math>, як і передбачалося вище.

== Алгоритми ==

МПВ може бути розв'язувано [[Лінійне програмування|лінійним програмуванням]], або [[Динамічне програмування|динамічним програмуванням]]. Далі ми представимо останній підхід.

Припустімо, що ми ''знаємо'' функцію переходу стану <math>P</math> та функцію винагороди <math>R</math>, і хочемо обчислити стратегію, яка максимізує очікувану знецінену винагороду.

Стандартне сімейство алгоритмів для обчислення цієї оптимальної стратегії вимагає зберігання двох масивів, проіндексованих за станом: ''цінностей'' ({{lang-en|value}}) <math>V</math>, який містить дійсні значення, та ''стратегії'' <math>\pi</math>, який містить дії. По завершенню алгоритму, <math>\pi</math> міститиме розв'язок, а <math>V(s)</math> міститиме знецінену суму винагород, яку буде зароблено (в середньому) при слідуванні цим розв'язком зі стану <math>s</math>.

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

: <math> \pi(s) := \arg \max_a \left\{ \sum_{s'} P_a(s,s') \left( R_a(s,s') + \gamma V(s') \right) \right\} </math>

: <math> V(s) := \sum_{s'} P_{\pi(s)} (s,s') \left( R_{\pi(s)} (s,s') + \gamma V(s') \right) </math>

Їхній порядок залежить від варіанту алгоритму; можна робити їх одночасно для всіх станів, або стан за станом, і частіше для одних станів, ніж для інших. Якщо жоден зі станів не виключатиметься назавжди з будь-якого з кроків, то алгоритм зрештою прийде до правильного розв'язку.

=== Відомі варіанти ===

==== Ітерація за цінностями ====

В ітерації за цінностями ({{lang-en|value iteration}}, {{harvnb|Bellman|1957}}), яку також називають [[Зворотна індукція|зворотною індукцією]], функція <math>\pi</math> не використовується; натомість значення <math>\pi(s)</math> обчислюється в межах <math>V(s)</math> за потребою. Метод ітерації за цінностями для МПВ увійшов до праці [[Ллойд Ставелл Шеплі|Ллойда Шеплі]] 1953 року про [[Стохастична гра|стохастичні ігри]]{{sfn|Shapley|1953}} як окремий випадок, але це було визнано лише згодом.{{sfn|Kallenberg|2002}}

Підставлення обчислення <math>\pi(s)</math> до обчислення <math>V(s)</math> дає поєднаний крок:

: <math> V_{i+1}(s) := \max_a \left\{ \sum_{s'} P_a(s,s') \left( R_a(s,s') + \gamma V_i(s') \right) \right\}, </math>

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

==== Ітерація за стратегіями ====

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

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

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

==== Видозмінена ітерація за стратегіями ====

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

==== Пріоритетне підмітання ====

В цьому варіанті ({{lang-en|prioritized sweeping}}) кроки застосовуються до станів із надаванням переваги тим, які є якимось чином важливими&nbsp;— чи то на основі алгоритму (нещодавно були великі зміни в <math>V</math> або <math>\pi</math> навколо цих станів), чи то на основі використання (ці стани знаходяться близько до початкового стану, або іншим чином становлять інтерес для особи або програми, яка застосовує цей алгоритм).

== Розширення та узагальнення ==

Марковський процес вирішування є [[Стохастична гра|стохастичною грою]] з лише одним гравцем.

=== Часткова спостережуваність ===
{{Докладніше1|{{нп|Частково спостережуваний марковський процес вирішування|||Partially observable Markov decision process}}}}

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

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

=== Навчання з підкріпленням ===
{{main|Навчання з підкріпленням}}

Якщо ймовірності винагород є невідомими, то задача є задачею [[навчання з підкріпленням]] {{harv|Sutton|Barto|1998}}.

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

: <math>\ Q(s,a) = \sum_{s'} P_a(s,s') (R_a(s,s') + \gamma V(s')).\ </math>

І хоча ця функція також є невідомою, досвід під час навчання ґрунтується на парах <math>(s, a)</math> (разом з наслідком <math>s'</math>; тобто, «Я був у стані <math>s</math>, спробував вчинити <math>a</math>, і сталося <math>s'</math>»). Таким чином, є масив <math>Q</math>, і досвід використовується для його безпосереднього уточнення. Це відоме як [[Q-навчання|''Q''-навчання]].

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

=== Автомати з самонавчанням ===
{{Докладніше1|{{нп|Автомати з самонавчанням|||Learning automata}}}}

Ще одне застосування процесу МПВ в теорії [[Машинне навчання|машинного навчання]] називається автоматами з самонавчанням. Воно також є одним із типів навчання з підкріпленням, якщо середовище має стохастичний характер. Перше детальне дослідження про '''автомати з самонавчанням''' ({{lang-en|learning automata}}) здійснили {{нп|Кумпаті Нарендра|Нарендра||Kumpati S. Narendra}} та Татачар (1974), в якому їх було первісно описано явно як [[Скінченний автомат|скінченні автомати]].{{sfn|Narendra|Thathachar|1974}} Подібно до навчання з підкріпленням, алгоритм автоматів із самонавчанням також має перевагу розв'язання задач, у яких імовірності або винагороди є невідомими. Відмінність автоматів із самонавчанням від ''Q''-навчання полягає в тому, що вони не включають пам'ять ''Q''-значень, а для знаходження результату навчання уточнюють ймовірності дій безпосередньо. Автомати з самонавчанням є однією зі схем навчання з суворим доведенням збіжності.{{sfn|Narendra|Thathachar|1989}}

В теорії автоматів із самонавчанням '''стохастичний автомат''' ({{lang-en|stochastic automaton}}) складається з:

* множини можливих входів ''x'',
* множини можливих внутрішніх станів Φ = { Φ<sub>1</sub>, …, Φ<sub>''s''</sub> },
* множини можливих виходів, або дій, α = { α<sub>1</sub>, …, α<sub>''r''</sub> }, де ''r''≤''s'',
* вектора початкової ймовірності станів ''p(0)'' = ≪ ''p''<sub>1</sub>(0), …, ''p<sub>s</sub>''(0) ≫,
* [[Обчислювана функція|обчислюваної функції]] ''A'', яка після кожного кроку часу ''t'' породжує ''p''(''t''+1) з ''p''(''t''), поточного входу та поточного стану, і
* функції ''G'': Φ → α, яка породжує вихід на кожному кроці часу.

Стани такого автомату відповідають станам «[[Марковський процес|марковського процесу]] дискретного часу з дискретними параметрами».{{sfn|Narendra|Thathachar|1974|loc=с. 325 ліворуч}} На кожному кроці часу ''t''=0,1,2,3,… автомат читає вхід зі свого середовища, уточнює P(''t'') до P(''t''+1) за допомогою ''A'', випадково обирає наступний стан відповідно до ймовірностей P(''t''+1) та виводить відповідну дію. Середовище автомата, в свою чергу, читає цю дію, і надсилає автоматові наступний вхід.{{sfn|Narendra|Thathachar|1989}}

=== Інтерпретація в термінах теорії категорій ===

Крім як через винагороди, марковський процес вирішування <math>(S,A,P)</math> можна розуміти і в термінах [[Теорія категорій|теорії категорій]]. А саме, нехай <math>\mathcal{A}</math> позначає {{нп|вільний моноїд|||Free monoid}} з породжувальною множиною <math>A</math>. Нехай <math>\mathbf{Dist}</math> позначає {{нп|Категорія Клайслі|категорію Клайслі||Kleisli category}} [http://ncatlab.org/nlab/show/Giry+monad монади Жирі] {{Webarchive|url=https://web.archive.org/web/20160506132151/https://ncatlab.org/nlab/show/Giry+monad |date=6 травня 2016 }}. Тоді [[функтор]] <math>\mathcal{A}\to\mathbf{Dist}</math> кодує як множину станів <math>S</math>, так і функцію ймовірностей <math>P</math>.

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

== Марковський процес вирішування безперервного часу ==

В марковських процесах вирішування дискретного часу рішення здійснюються через дискретні проміжки часу. Проте для '''марковських процесів вирішування безперервного часу''' ({{lang-en|Continuous-time Markov Decision Processes}}) рішення можуть здійснюватися в будь-який час, який обере ухвалювач рішень. У порівнянні з марковськими процесами вирішування дискретного часу, марковські процеси вирішування безперервного часу можуть краще моделювати процес ухвалювання рішень для системи, яка має {{нп|Безперервний час|безперервну динаміку||Continuous time}}, тобто системи, динаміка якої визначається [[Диференціальне рівняння з частинними похідними|диференціальними рівняннями з частинними похідними]].

=== Визначення ===

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

Якщо [[Простір станів (теорія керування)|простір станів]] та простір дій є скінченними,

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

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

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

=== Задача ===

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

: <math>\max \quad \mathbb{E}_u[\int_0^{\infty}\gamma^t r(x(t),u(t)))dt|x_0]</math>

Де <math>0\leq\gamma< 1</math>

=== Формулювання лінійного програмування ===

Якщо простори станів та дій є скінченними, то для пошуку оптимальної стратегії ми можемо використовувати лінійне програмування, що було одним із найперших застосованих підходів. Тут ми розглядаємо лише ергодичну модель, яка означає, що наш МПВ безперервного часу стає [[Ергодичність|ергодичним]] марковським ланцюгом безперервного часу за сталої [[Політика (в управлінні)|стратегії]]. За цього припущення, хоча ухвалювач рішення і може здійснювати рішення в будь-який час у поточному стані, він не може виграти більше, здійснюючи більше ніж одну дію. Для нього краще здійснювати дію лише в той момент часу, коли система переходить з поточного стану до іншого. За деяких умов (детальніше див. Наслідок 3.14 у [http://www.springer.com/mathematics/applications/book/978-3-642-02546-4 ''Continuous-Time Markov Decision Processes''] {{Webarchive|url=https://web.archive.org/web/20120202023334/http://www.springer.com/mathematics/applications/book/978-3-642-02546-4 |date=2 лютого 2012 }}), якщо наша функція оптимальної цінності <math>V^*</math> є незалежною від стану <math>i</math>, то ми матимемо наступну нерівність:

: <math>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)</math>

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

* Пряма лінійна програма (П-ЛП, {{lang-en|primal linear program, P-LP}})

: <math>
\begin{align}
\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{align}
</math>

* Двоїста лінійна програма (Д-ЛП, {{lang-en|dual linear program, D-LP}})

: <math>
\begin{align}
\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{align}
</math>

<math>y(i,a)</math> є придатним <!-- feasible --> розв'язком Д-ЛП, якщо <math>y(i,a)</math> є невиродженою, <!-- ?
nonnative --> і задовольняє обмеження задачі Д-ЛП. Придатний <!-- feasible --> розв'язок Д-ЛП <math>y^*(i,a)</math> називають оптимальним розв'язком, якщо

: <math>
\begin{align}
\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{align}
</math>

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

=== Рівняння Гамільтона&nbsp;— Якобі&nbsp;— Беллмана ===

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

: <math>\begin{align} 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{align}
</math>

<math>D(\cdot)</math> є функцією остаточної винагороди ({{lang-en|terminal reward function}}), <math>x(t)</math> є вектором стану системи, <math>u(t)</math> є вектором керування системою, який ми намагаємося знайти. <math>f(\cdot)</math> показує, як стан системи змінюється з часом. Рівняння Гамільтона&nbsp;— Якобі&nbsp;— Беллмана є таким:

: <math>0=\text{max}_u ( r(t,x,u) +\frac{\partial V(t,x)}{\partial x}f(t,x,u)) </math>

Ми можемо розв'язувати це рівняння, щоби знаходити оптимальне керування <math>u(t)</math>, яке давало би нам оптимальну цінність <math>V^*</math>

=== Застосування ===

Марковські процеси вирішування безперервного часу мають застосування в [[Система масового обслуговування|системах масового обслуговування]], процесах епідемії та {{нп|Процес населення|процесах населення||Population process}}.

== Альтернативні позначення ==

Термінологія та позначення МПВ не є остаточно узгодженими. Є дві основні течії&nbsp;— одна зосереджується на задачах максимізації з контекстів на кшталт економіки, застосовуючи терміни дія ({{lang-en|action}}), винагорода ({{lang-en|reward}}), цінність ({{lang-en|value}}), та називаючи коефіцієнт знецінювання ({{lang-en|discount factor}}) <math>\beta</math> або <math>\gamma</math>, в той час як інша зосереджується на задачах мінімізації з техніки та навігації, застосовуючи терміни керування ({{lang-en|control}}), витрати ({{lang-en|cost}}), остаточні витрати ({{lang-en|cost-to-go}}), і називаючи коефіцієнт знецінювання ({{lang-en|discount factor}}) <math>\alpha</math>. На додачу, різниться й позначення ймовірності переходу.

{| class="wikitable"
! в цій статті !! альтернативне !! коментар
|-
| дія <math>a</math> || керування <math>u</math> ||
|-
| винагорода <math>R</math> || витрати <math>g</math>
| <math>g</math> є від'ємною <math>R</math>
|-
| цінність <math>V</math> || остаточні витрати <math>J</math>
| <math>J</math> є від'ємною <math>V</math>
|-
| стратегія <math>\pi</math> || стратегія <math>\mu</math> ||
|-
| коефіцієнт знецінювання <math>\ \gamma \ </math> || коефіцієнт знецінювання <math>\alpha</math> ||
|-
| ймовірність переходу <math>P_a(s,s')</math> || ймовірність переходу <math>p_{ss'}(a)</math> ||
|}

На додачу, ймовірність переходу іноді записують як <math>Pr(s,a,s')</math>, <math>Pr(s'|s,a)</math> або, рідше, як <math>p_{s's}(a)</math>.

== Обмежені марковські процеси вирішування ==

Обмежені марковські процеси вирішування (ОМПВ, {{lang-en|Constrained Markov Decision Process, CMDP}}) є розширеннями марковських процесів вирішування (МПВ). Між МПВ та ОМПВ є три докорінні відмінності.{{sfn|Altman|1999}}

* Після застосування дії замість однієї витрати несуться декілька витрат.
* ОМПВ розв'язуються лише за допомогою [[Лінійне програмування|лінійних програм]], а [[динамічне програмування]] не працює.
* Остаточна стратегія залежить від початкового стану.

Існує ряд застосувань ОМПВ. Нещодавно їх було застосовано в сценаріях [[планування руху]] в робототехніці.{{sfn|Feyzabadi|Carpin|2014}}

== Див. також ==

* {{нп|Ймовірнісні автомати|||Probabilistic automata}}
* {{нп|Квантові скінченні автомати|||Quantum finite automata}}
* {{нп|Частково спостережуваний марковський процес вирішування|||Partially observable Markov decision process}}
* [[Динамічне програмування]]
* [[Рівняння Беллмана]] для застосувань в економіці.
* [[Рівняння Гамільтона — Якобі — Беллмана|Рівняння Гамільтона&nbsp;— Якобі&nbsp;— Беллмана]]
* [[Оптимальне керування]]
* {{нп|Рекурсивна економіка|||Recursive economics}}
* {{нп|Задача про мабіногіонських овець|||Mabinogion sheep problem}}
* [[Стохастична гра|Стохастичні ігри]]
* [[Q-навчання|''Q''-навчання]]

== Примітки ==
{{Примітки}}

== Джерела ==

{{refbegin}}
* {{cite journal|first=R.|last=Bellman|url=http://www.iumj.indiana.edu/IUMJ/FULLTEXT/1957/6/56038|title=A Markovian Decision Process|journal=Journal of Mathematics and Mechanics|volume=6|year=1957|ref=harv|accessdate=8 вересня 2016|archive-date=30 квітня 2021|archive-url=https://web.archive.org/web/20210430065537/http://www.iumj.indiana.edu/IUMJ/FULLTEXT/1957/6/56038}} {{ref-en}}
* {{cite book|first=R. E.|last=Bellman.|title=Dynamic Programming|url=https://archive.org/details/dynamicprogrammi0000bell|publisher=Princeton University Press|location=Princeton, NJ|orig-year=1957|edition=Dover paperback edition|year=2003|ISBN=0-486-42809-5|ref=harv}} {{ref-en}}
* {{cite book|first=Ronald A.|last=Howard|title=Dynamic Programming and Markov Processes|publisher=The M.I.T. Press|year=1960|url=http://web.mit.edu/dimitrib/www/dpchapter.pdf|ref=harv|accessdate=8 вересня 2016|archive-date=9 жовтня 2011|archive-url=https://web.archive.org/web/20111009101353/http://web.mit.edu/dimitrib/www/dpchapter.pdf}} {{ref-en}}
* {{cite journal|last=Shapley|first=Lloyd|authorlink=Ллойд Ставелл Шеплі|title=Stochastic Games|year=1953|journal=Proceedings of National Academy of Science|volume=39|pages=1095–1100|ref=harv}} {{ref-en}}
* {{cite book|first=Lodewijk|last=Kallenberg|chapter=Finite state and action MDPs|editor-first1=Eugene A.|editor-last1=Feinberg|editor-first2=Adam|editor-last2=Shwartz|title=Handbook of Markov decision processes: methods and applications|publisher=Springer|year=2002|ISBN=0-7923-7459-2|ref=harv}} {{ref-en}}
* {{cite book|first=D.|last=Bertsekas|title=Dynamic Programming and Optimal Control|volume=2|publisher=Athena|location=MA|year=1995|ref=harv}} {{ref-en}}
* {{cite journal|last1=Burnetas|first1=A.N.|first2=M. N.|last2=Katehakis|title=Optimal Adaptive Policies for Markov Decision Processes|url=https://archive.org/details/sim_mathematics-of-operations-research_1997-02_22_1/page/222|journal=Mathematics of Operations Research|volume=22|issue=1|year=1997|doi = 10.1287/moor.22.1.222|pages=222|ref=harv}} {{ref-en}}
* {{cite book|editor1-first=E.A.|editor1-last=Feinberg|editor2-first=A.|editor2-last=Shwartz|title=Handbook of Markov Decision Processes|publisher=Kluwer|location=Boston, MA|year=2002|ref=harv}} {{ref-en}}
* {{cite book|first=C.|last=Derman|title=Finite state Markovian decision processes|publisher=Academic Press|year=1970|ref=harv}} {{ref-en}}
* {{cite book|first=M. L.|last=Puterman.|title=Markov Decision Processes|publisher=Wiley|year=1994|ref=harv}} {{ref-en}}
* {{cite book|first=H.C.|last=Tijms.|title=A First Course in Stochastic Models|publisher=Wiley|year=2003|ref=harv}} {{ref-en}}
* {{cite book|last1=Sutton|first1=R. S.|last2=Barto|first2=A. G.|title=Reinforcement Learning: An Introduction|publisher=The MIT Press|location=Cambridge, MA|year=1998|url=http://webdocs.cs.ualberta.ca/~sutton/book/the-book.html|ref=harv|accessdate=8 вересня 2016|archiveurl=https://web.archive.org/web/20131211192714/http://webdocs.cs.ualberta.ca/~sutton/book/the-book.html|archivedate=11 грудня 2013|deadurl=yes}} {{ref-en}}
* {{cite journal|first=J.A. E. E|last=van Nunen|title=A set of successive approximation methods for discounted Markovian decision problems. Z|journal=Operations Research|volume=20|pages=203-208|year=1976|ref=harv}} {{ref-en}}
* {{Cite journal|last=Narendra|first=K. S.|authorlink=Кумпаті Нарендра|last2=Thathachar|first2=M. A. L.|date=1974-07-01|title=Learning Automata - A Survey|url=http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=5408453|journal=IEEE Transactions on Systems, Man, and Cybernetics|volume=SMC-4|issue=4|pages=323–334|doi=10.1109/TSMC.1974.5408453|issn=0018-9472|ref=harv}} {{ref-en}}
* {{Cite book|url=https://books.google.com/books?id=hHVQAAAAMAAJ|title=Learning automata: An introduction|last=Narendra|first=Kumpati S.|authorlink=Кумпаті Нарендра|last2=Thathachar|first2=Mandayam A. L.|year=1989|publisher=Prentice Hall|isbn=9780134855585|language=en|ref=harv|accessdate=8 вересня 2016|archive-date=16 березня 2017|archive-url=https://web.archive.org/web/20170316105941/https://books.google.com/books?id=hHVQAAAAMAAJ}} {{ref-en}}
* {{cite book|first=S. P.|last=Meyn|year=2007|url=https://netfiles.uiuc.edu/meyn/www/spm_files/CTCN/CTCN.html|archive-url=https://web.archive.org/web/20100619011046/https://netfiles.uiuc.edu/meyn/www/spm_files/CTCN/CTCN.html|archive-date=19 червня 2010|title=Control Techniques for Complex Networks|publisher=Cambridge University Press|year=2007|ISBN=978-0-521-88441-9|ref=harv}} Додаток містить скорочену {{cite web|url=https://netfiles.uiuc.edu/meyn/www/spm_files/book.html|archive-url=https://web.archive.org/web/20121218173202/https://netfiles.uiuc.edu/meyn/www/spm_files/book.html|archive-date=18 грудня 2012|title=Meyn & Tweedie}} {{ref-en}}
* {{cite book|first=S. M.|last=Ross|year=1983|title=Introduction to stochastic dynamic programming|url=https://archive.org/details/introductiontost0000ross|publisher=Academic press|ref=harv}} {{ref-en}}
* {{cite book|first1=X.|last1=Guo|first2=O.|last2=Hernández-Lerma|url=http://www.springer.com/mathematics/applications/book/978-3-642-02546-4|title=Continuous-Time Markov Decision Processes|publisher=Springer|year=2009|ref=harv|accessdate=8 вересня 2016|archive-date=2 лютого 2012|archive-url=https://web.archive.org/web/20120202023334/http://www.springer.com/mathematics/applications/book/978-3-642-02546-4}} {{ref-en}}
* {{cite journal|first1=M. L.|last1=Puterman|last2=Shin|first2=M. C.|title=Modified Policy Iteration Algorithms for Discounted Markov Decision Problems|journal=Management Science|volume=24|year=1978|ref=harv}} {{ref-en}}
* {{cite book|last=Altman|first=Eitan|title=Constrained Markov decision processes|volume=7|publisher=CRC Press|year=1999|ref=harv}} {{ref-en}}
* {{cite conference|last1=Feyzabadi|first1=S.|last2=Carpin|first2=S.|title=Risk-aware path planning using hierarchical constrained Markov Decision Processes|booktitle=Automation Science and Engineering (CASE)|year=2014|conference=IEEE International Conference|pages=297,303|date=18-22 Aug 2014|ref=harv}} {{ref-en}}
{{refend}}

== Посилання ==

* [http://www7.inra.fr/mia/T/MDPtoolbox/ MDP Toolbox для MATLAB, GNU Octave, Scilab та R] {{Webarchive|url=https://web.archive.org/web/20160713101050/http://www7.inra.fr/mia/T/MDPtoolbox/ |date=13 липня 2016 }} Інструментарій марковських процесів вирішування (МПВ).
* [https://web.archive.org/web/20041012205238/http://www.ai.mit.edu/%7Emurphyk/Software/MDP/mdp.html MDP Toolbox для Matlab]&nbsp;— Чудовий навчальний посібник та інструментарій [[Matlab]] для роботи з МПВ. {{ref-en}}
* [https://pypi.python.org/pypi/pymdptoolbox Інструментарій МПВ для Python] {{Webarchive|url=https://web.archive.org/web/20161002192149/https://pypi.python.org/pypi/pymdptoolbox |date=2 жовтня 2016 }} Пакет для розв'язання МПВ
* [http://www.cs.ualberta.ca/~sutton/book/ebook Reinforcement Learning]{{Недоступне посилання|date=квітень 2019 |bot=InternetArchiveBot }} Введення від Річарда Саттона та Ендрю Барто {{ref-en}}
* [http://www.cs.uwaterloo.ca/~jhoey/research/spudd/index.php SPUDD] {{Webarchive|url=https://web.archive.org/web/20160424034835/https://cs.uwaterloo.ca/~jhoey/research/spudd/index.php |date=24 квітня 2016 }} Структурований розв'язувач МПВ для завантаження від Jesse Hoey
* [http://www.eecs.umich.edu/~baveja/Papers/Thesis.ps.gz Learning to Solve Markovian Decision Processes] {{Webarchive|url=https://web.archive.org/web/20120129223359/http://www.eecs.umich.edu/%7Ebaveja/Papers/Thesis.ps.gz |date=29 січня 2012 }} від [http://www.eecs.umich.edu/~baveja/ Satinder P. Singh] {{Webarchive|url=https://web.archive.org/web/20120222182453/http://www.eecs.umich.edu/~baveja/ |date=22 лютого 2012 }} {{ref-en}}
* [http://www.jstor.org/stable/3690147 Optimal Adaptive Policies for Markov Decision Processes] від Burnetas та Katehakis (1997). {{ref-en}}

{{Перекласти|en|дата=листопад 2023}}

[[Категорія:Оптимальні рішення]]
[[Категорія:Динамічне програмування]]
[[Категорія:Марковські процеси|Вирішування]]
[[Категорія:Стохастичне керування]]