Ма́рковські проце́си вирі́шування (МПВ, ) забезпечують математичну систему для моделювання ухвалення рішень у ситуаціях, в яких наслідки є частково випадковими, а частково контрольованими ухвалювачем рішення. МПВ є корисними для дослідження широкого спектра задач оптимізації, розв'язуваних динамічним програмуванням та навчанням з підкріпленням. МПВ були відомі щонайменше з 1950-х років (пор. ). Основна маса досліджень марковських процесів вирішування стала результатом книги , опублікованої 1960 року, «Динамічне програмування та марковські процеси» (). Їх застосовують у широкій області дисциплін, включно з робототехнікою, автоматизованим керуванням, економікою та виробництвом.
Якщо точніше, то марковський процес вирішування є стохастичним процесом керування дискретного часу. На кожному кроці часу процес перебуває в якомусь стані , і ухвалювач рішення може обрати будь-яку дію , доступну в стані . Процес реагує на наступному кроці часу випадковим переходом до нового стану і наданням ухвалювачеві рішення відповідної винагороди () .
Ймовірність переходу процесу до його нового стану знаходиться під впливом обраної дії. Конкретно, вона задається функцією переходу стану . Таким чином, наступний стан залежить від поточного стану та від дії ухвалювача рішення . Але для заданих та він є умовно незалежним від усіх попередніх станів та дій; іншими словами, переходи станів процесу МПВ задовольняють марковську властивість.
Марковські процеси вирішування є розширенням марковських ланцюгів; різниця полягає в доданні дій (що дає вибір) та винагород (що дає мотивацію). І навпаки, якщо для кожного стану існує лише одна дія (наприклад, «чекати») та всі винагороди є однаковими (наприклад, «нуль»), то марковський процес вирішування зводиться до марковського ланцюга.
Визначення
Марковський процес вирішування є 5-кою , де
є скінченною множиною станів, є скінченною множиною дій (як альтернатива, є скінченною множиною дій, доступних зі стану ), є ймовірністю того, що дія в стані в момент часу призведе до стану в момент часу , є безпосередньою винагородою (або очікуваною безпосередньою винагородою), отримуваною після переходу до стану зі стану , є коефіцієнтом знецінювання (), який представляє відмінність важливості майбутніх та поточних винагород.
(Зауваження: Теорія марковських процесів вирішування не стверджує, що чи є скінченними, але основні алгоритми, наведені нижче, передбачають, що вони є скінченними.)
Задача
Основною задачею МПВ є знайти «стратегію» () для ухвалювача рішень: функцію , яка визначає дію , яку ухвалювач рішення обере в стані . Зауважте, що щойно марковський процес вирішування поєднано таким чином зі стратегією, то це фіксує дію для кожного стану, і отримане в результаті поєднання поводиться як марковський ланцюг.
Метою є обрати таку стратегію , яка максимізуватиме деяку кумулятивну функцію випадкових винагород, зазвичай — очікувану знецінену функцію над потенційно нескінченним горизонтом:
(де ми обираємо )
де є коефіцієнтом знецінювання, і задовольняє . (Наприклад, , де інтенсивністю знецінювання є .) Зазвичай є близьким до 1.
Завдяки марковській властивості, оптимальну стратегію для цієї конкретної задачі насправді може бути записано як функцію лише від , як і передбачалося вище.
Алгоритми
МПВ може бути розв'язувано лінійним програмуванням, або динамічним програмуванням. Далі ми представимо останній підхід.
Припустімо, що ми знаємо функцію переходу стану та функцію винагороди , і хочемо обчислити стратегію, яка максимізує очікувану знецінену винагороду.
Стандартне сімейство алгоритмів для обчислення цієї оптимальної стратегії вимагає зберігання двох масивів, проіндексованих за станом: цінностей () , який містить дійсні значення, та стратегії , який містить дії. По завершенню алгоритму, міститиме розв'язок, а міститиме знецінену суму винагород, яку буде зароблено (в середньому) при слідуванні цим розв'язком зі стану .
Алгоритм має наступні два види кроків, які повторюються в певному порядку для всіх станів, допоки подальших змін вже не відбуватиметься. Вони визначаються рекурсивно наступним чином:
Їхній порядок залежить від варіанту алгоритму; можна робити їх одночасно для всіх станів, або стан за станом, і частіше для одних станів, ніж для інших. Якщо жоден зі станів не виключатиметься назавжди з будь-якого з кроків, то алгоритм зрештою прийде до правильного розв'язку.
Відомі варіанти
Ітерація за цінностями
В ітерації за цінностями (, ), яку також називають зворотною індукцією, функція не використовується; натомість значення обчислюється в межах за потребою. Метод ітерації за цінностями для МПВ увійшов до праці Ллойда Шеплі 1953 року про стохастичні ігри як окремий випадок, але це було визнано лише згодом.
Підставлення обчислення до обчислення дає поєднаний крок:
де є номером ітерації. Ітерація за цінностями починається з та як припущення про функцію цінності. Потім виконується ітерування з повторним обчисленням для всіх станів , поки не збіжиться, коли ліва сторона дорівнюватиме правій (що є «рівнянням Беллмана» для цієї задачі).
Ітерація за стратегіями
В ітерації за стратегіями (, ) перший крок виконується один раз, а потім другий крок повторюється до збіжності. Потім перший крок виконується знову, і так далі.
Замість повторювання другого кроку до збіжності його може бути сформульовано та розв'язано як набір лінійних рівнянь.
Цей варіант має перевагу в тому, що існує чітка умова зупинки: коли масив не змінюється в процесі застосування кроку 1 до всіх станів, алгоритм завершується.
Видозмінена ітерація за стратегіями
У видозміненій ітерації за стратегіями (, , ) перший крок виконується один раз, а потім другий крок повторюється кілька разів. Потім знову перший крок виконується один раз, і так далі.
Пріоритетне підмітання
В цьому варіанті () кроки застосовуються до станів із надаванням переваги тим, які є якимось чином важливими — чи то на основі алгоритму (нещодавно були великі зміни в або навколо цих станів), чи то на основі використання (ці стани знаходяться близько до початкового стану, або іншим чином становлять інтерес для особи або програми, яка застосовує цей алгоритм).
Розширення та узагальнення
Марковський процес вирішування є стохастичною грою з лише одним гравцем.
Часткова спостережуваність
Наведене вище розв'язання передбачає, що в той момент, коли треба вирішувати, яку дію вчинити, стан є відомим; інакше обчислено бути не може. Якщо це припущення не є вірним, задачу називають частково спостережуваним марковським процесом вирішування (ЧСМПВ, ).
Головний поступ у цій області було забезпечено Бурнетасом та Катехакісом в «Оптимальних адаптивних стратегіях для марковських процесів вирішування». В цій праці було побудовано клас адаптивних стратегій, які володіють властивостями рівномірно максимального темпу збіжності для загальної очікуваної винагороди скінченного інтервалу, за припущень скінченних просторів стан-дія та нескоротності закону переходу. Ці стратегії приписують, щоби вибір дій на кожному стані в кожен момент часу ґрунтувався на показниках, які є роздуваннями правої сторони рівнянь оптимальності очікуваної усередненої винагороди.
Навчання з підкріпленням
Якщо ймовірності винагород є невідомими, то задача є задачею навчання з підкріпленням .
Для цього корисно визначити наступну функцію, яка відповідає вчиненню дії з продовженням оптимальним чином (або відповідно до будь-якої наявної в даний момент стратегії):
І хоча ця функція також є невідомою, досвід під час навчання ґрунтується на парах (разом з наслідком ; тобто, «Я був у стані , спробував вчинити , і сталося »). Таким чином, є масив , і досвід використовується для його безпосереднього уточнення. Це відоме як Q-навчання.
Навчання з підкріпленням може розв'язувати марковські процеси вирішування без явного вказання ймовірностей переходів; значення ймовірностей переходів необхідні для ітерації за цінностями та за стратегіями. В навчанні з підкріпленнями замість явного вказання ймовірностей переходів доступ до них отримується через імітатор, який зазвичай багаторазово перезапускається з рівномірного випадкового початкового стану. Навчання з підкріпленням також може поєднуватися з наближенням функцій, щоби можна було братися за задачі з дуже великим числом станів.
Автомати з самонавчанням
Ще одне застосування процесу МПВ в теорії машинного навчання називається автоматами з самонавчанням. Воно також є одним із типів навчання з підкріпленням, якщо середовище має стохастичний характер. Перше детальне дослідження про автомати з самонавчанням () здійснили та Татачар (1974), в якому їх було первісно описано явно як скінченні автомати. Подібно до навчання з підкріпленням, алгоритм автоматів із самонавчанням також має перевагу розв'язання задач, у яких імовірності або винагороди є невідомими. Відмінність автоматів із самонавчанням від Q-навчання полягає в тому, що вони не включають пам'ять Q-значень, а для знаходження результату навчання уточнюють ймовірності дій безпосередньо. Автомати з самонавчанням є однією зі схем навчання з суворим доведенням збіжності.
В теорії автоматів із самонавчанням стохастичний автомат () складається з:
множини можливих входів x, множини можливих внутрішніх станів Φ = { Φ1, …, Φs }, множини можливих виходів, або дій, α = { α1, …, αr }, де r≤s, вектора початкової ймовірності станів p(0) = ≪ p1(0), …, ps(0) ≫, обчислюваної функції A, яка після кожного кроку часу t породжує p(t+1) з p(t), поточного входу та поточного стану, і функції G: Φ → α, яка породжує вихід на кожному кроці часу.
Стани такого автомата відповідають станам «марковського процесу дискретного часу з дискретними параметрами». На кожному кроці часу t=0,1,2,3,… автомат читає вхід зі свого середовища, уточнює P(t) до P(t+1) за допомогою A, випадково обирає наступний стан відповідно до ймовірностей P(t+1) та виводить відповідну дію. Середовище автомата, в свою чергу, читає цю дію, і надсилає автоматові наступний вхід.
Інтерпретація в термінах теорії категорій
Крім як через винагороди, марковський процес вирішування можна розуміти і в термінах теорії категорій. А саме, нехай позначає з породжувальною множиною . Нехай позначає монади Жирі . Тоді функтор кодує як множину станів , так і функцію ймовірностей .
Таким чином, марковський процес вирішування може бути узагальнено з моноїдів (категорій з одним об'єктом) на довільні категорії. Результат можна назвати контекстно-залежним марковським процесом вирішування (), оскільки перехід від одного об'єкта до іншого в змінює множину доступних дій та множину можливих станів.
Марковський процес вирішування безперервного часу
В марковських процесах вирішування дискретного часу рішення здійснюються через дискретні проміжки часу. Проте для марковських процесів вирішування безперервного часу () рішення можуть здійснюватися в будь-який час, який обере ухвалювач рішень. У порівнянні з марковськими процесами вирішування дискретного часу, марковські процеси вирішування безперервного часу можуть краще моделювати процес ухвалювання рішень для системи, яка має безперервну динаміку, тобто системи, динаміка якої визначається диференціальними рівняннями з частинними похідними.
Визначення
Для обговорення марковських процесів вирішування безперервного часу введімо два набори позначень:
Якщо простір станів та простір дій є скінченними,
: простір станів (); : простір дій (); : , функція інтенсивності переходів (); : , функція винагороди ().
Якщо простір станів та простір дій є неперервними,
: простір станів (); : простір можливого керування (); : , функція інтенсивності переходів (); : , функція інтенсивності винагороди (), така, що , де є функцією винагороди, яку ми обговорювали в попередньому випадку.
Задача
Як і в марковських процесах вирішування дискретного часу, в марковському процесі вирішування безперервного часу ми хочемо знаходити оптимальну стратегію () або керування (), яке давало би нам оптимальну очікувану проінтегровану винагороду:
Де
Формулювання лінійного програмування