Марковљев процес одлучивања

У математици, Марковљев процес одлучивања (МДП) је стохастички контролни процес са дискретним временом. Он пружа математички оквир за моделовање доношења одлука у ситуацијама у којима су исходи делимично рандомни, а делом под контролом доносиоца одлука. МДП-ови су корисни за проучавање проблема оптимизације решених динамичким програмирањем. МДП-ови су били познати бар још 1950-их;^[1] језгро истраживања о Марковљевим процесима одлучивања је резултат књиге Роналда Хауарда из 1960. Динамичко програмирање и Марковљеви процеси.^[2] Они се користе у многим дисциплинама, укључујући роботику, аутоматску контролу, економију и производњу. Назив МДП-а потиче од руског математичара Андреја Маркова јер су они продужетак Марковљевих ланаца.

У сваком временском кораку, процес је у неком стању $s$ , а доносилац одлуке може изабрати било коју радњу $a$ која је доступна у стању $s$ . Процес реагује у следећем временском кораку тако што се рандомно креће у ново стање $s'$ и даје доносиоцу одлуке одговарајућу награду $R_{a}(s,s')$ .

Изабрана радња утиче на вероватноћу да процес пређе у своје ново стање $s'$ . Конкретно, дата је функцијом прелаза стања $P_{a}(s,s')$ . Дакле, следеће стање $s'$ зависи од тренутног стања $s$ и акције доносиоца одлуке $a$ . Али с обзиром на $s$ и $a$ , условно је независно од свих претходних стања и радњи; другим речима, транзиције стања МДП-а задовољавају Марковљево својство.

Марковљеви процеси одлучивања су продужетак Марковљевих ланаца; разлика је додавање акција (омогућавање избора) и награда (давање мотивације). Супротно томе, ако постоји само једна радња за свако стање (нпр. „чекај“) и све награде су исте (нпр. „нула“), процес Марковљевог одлучивања се своди на Марковљев ланац.

Дефиниција

Пример једноставног МДП-а са три стања (зелени кругови) и две акције (наранџасти кругови), са две награде (наранџасте стрелице)

Марковљев процес одлучивања је 4-орка $(S,A,P_{a},R_{a})$ , где је:

$S$ је скуп стања који се назива простор стања,
$A$ је скуп радњи које се називају простор радње (алтернативно, $A_{s}$ је скуп акција доступних из стања $s$ ),
$P_{a}(s,s')=\Pr(s_{t+1}=s'\mid s_{t}=s,a_{t}=a)$ је вероватноћа да ће радња $a$ у стању $s$ у време $t$ довести до стања $s'$ у време $t+1$ ,
$R_{a}(s,s')$ је непосредна награда (или очекивана тренутна награда) добијена након преласка из стања $s$ у стање $s'$ , због радње $a$

Простори стања и радње могу бити коначни или бесконачни, на пример скуп реалних бројева. Неки процеси са пребројиво бесконачним просторима стања и деловања могу се свести на оне са коначним просторима стања и деловања.^[3]

Функција политике $\pi$ је (потенцијално пробабилистичко) мапирање из простора стања ( $S$ ) у простор деловања ( $A$ ).

Циљ оптимизације

Циљ у Марковљевом процесу одлучивања је да се пронађе добра „политика“ за доносиоца одлука: функција $\pi$ која одређује радњу $\pi (s)$ коју ће доносилац одлуке изабрати када је у стању $s$ . Након што се Марковљев процес одлучивања комбинује са политиком на овај начин, ово фиксира радњу за свако стање и резултирајућа комбинација се понаша као Марковљев ланац (пошто је радња изабрана у стању $s$ потпуно одређена са $\pi (s)$ и $\Pr(s_{t+1}=s'\mid s_{t}=s,a_{t}=a)$ се своди на $\Pr(s_{t+1}=s'\mid s_{t}=s)$ , Марковљеву прелазну матрицу).

Циљ је одабрати политику $\pi$ која ће максимизовати неку кумулативну функцију рандомних награда, обично очекивану снижену суму у потенцијално бесконачном хоризонту:

E\left[\sum _{t=0}^{\infty }{\gamma ^{t}R_{a_{t}}(s_{t},s_{t+1})}\right]

(где се бира

a_{t}=\pi (s_{t})

, и.е. радње које даје политика). А очекивање се преузима преко

s_{t+1}\sim P_{a_{t}}(s_{t},s_{t+1})

где је $\ \gamma \$ фактор попуста који задовољава $0\leq \ \gamma \ \leq \ 1$ , што је обично близу 1 (на пример, $\gamma =1/(1+r)$ за неку дисконтну стопу р). Нижи дисконтни фактор мотивише доносиоца одлука да фаворизује предузимање радњи рано, уместо да их одлаже на неодређено време.

Политика која максимизира горњу функцију назива се оптимална политика и обично се означава са $\pi ^{*}$ . Одређени МДП може имати више различитих оптималних политика. Због Марковљевог својства, може се показати да је оптимална политика функција тренутног стања, као што је претпостављено горе.

Симулаторски модели

У многим случајевима, тешко је експлицитно представити дистрибуцију вероватноће прелаза, $P_{a}(s,s')$ . У таквим случајевима, симулатор се може користити за имплицитно моделовање МДП-а пружањем узорака из дистрибуција прелаза. Један уобичајени облик имплицитног МДП модела је епизодични симулатор окружења који се може покренути из почетног стања и доноси накнадно стање и награду сваки пут када прими акциони унос. На овај начин се могу произвести путање стања, радњи и награда, које се често називају епизодама.

Други облик симулатора је генеративни модел, симулатор са једним кораком који може да генерише узорке следећег стања и награди за било које стање и радњу.^[4] (Треба имати на уму да је ово другачије значење од термина генеративни модел у контексту статистичке класификације.) У алгоритмима који се изражавају помоћу псеудокода, $G$ се често користи за представљање генеративног модела. На пример, израз $s',r\gets G(s,a)$ може да означи акцију узорковања из генеративног модела где су $s$ и $a$ су тренутно стање и радња, а $s'$ и $r$ су ново стање и награда. У поређењу са епизодним симулатором, генеративни модел има предност у томе што може дати податке из било ког стања, а не само оне на које се наиђе на путањи.

Ове класе модела формирају хијерархију информационог садржаја: експлицитни модел тривијално даје генеративни модел кроз узорковање из дистрибуција, а поновљена примена генеративног модела даје епизодични симулатор. У супротном смеру, могуће је научити само приближне моделе путем регресије. Тип модела који је доступан за одређени МДП игра значајну улогу у одређивању који су алгоритми решења одговарајући. На пример, алгоритми за динамичко програмирање описани у следећем одељку захтевају експлицитан модел, а Монте Карло претрага стабла захтева генеративни модел (или епизодични симулатор који се може копирати у било ком стању), док већина алгоритама подржаног учења захтева само епизодни симулатор.

Референце

^ Беллман, Р. (1957). „А Марковиан Децисион Процесс”. Јоурнал оф Матхематицс анд Мецханицс. 6 (5): 679—684. ЈСТОР 24900506.
^ Хоwард, Роналд А. (1960). Дyнамиц Программинг анд Марков Процессес. Тхе M.I.Т. Пресс.
^ Wробел, А. (1984). „Он Марковиан Децисион Моделс wитх а Фините Скелетон”. Матхематицал Метходс оф Оператионс Ресеарцх. 28 (Фебруарy): 17—27. С2ЦИД 2545336. дои:10.1007/бф01919083.
^ Кеарнс, Мицхаел; Мансоур, Yисхаy; Нг, Андреw (2002). „А Спарсе Самплинг Алгоритхм фор Неар-Оптимал Планнинг ин Ларге Марков Децисион Процессес”. Мацхине Леарнинг. 49 (193–208): 193—208. дои:10.1023/А:1017932429737  .

Литература

Беллман., Р. Е. (2003) [1957]. Дyнамиц Программинг (Довер папербацк изд.). Принцетон, Њ: Принцетон Университy Пресс. ИСБН 978-0-486-42809-3.
Бертсекас, D. (1995). Дyнамиц Программинг анд Оптимал Цонтрол. 2. МА: Атхена.
Дерман, C. (1970). Фините стате Марковиан децисион процессес. Ацадемиц Пресс.
Феинберг, Е.А.; Схwартз, А., ур. (2002). Хандбоок оф Марков Децисион Процессес. Бостон, МА: Клуwер. ИСБН 9781461508052.
Гуо, X.; Хернáндез-Лерма, О. (2009). Цонтинуоус-Тиме Марков Децисион Процессес. Стоцхастиц Моделлинг анд Апплиед Пробабилитy. Спрингер. ИСБН 9783642025464.
Меyн, С. П. (2007). Цонтрол Тецхниqуес фор Цомплеx Нетwоркс. Цамбридге Университy Пресс. ИСБН 978-0-521-88441-9. Архивирано из оригинала 19. 6. 2010. г. Аппендиx цонтаинс абридгед „Меyн & Тwеедие”. Архивирано из оригинала 18. 12. 2012. г.
Путерман., M. L. (1994). Марков Децисион Процессес. Wилеy.
Росс, С. M. (1983). Интродуцтион то стоцхастиц дyнамиц программинг (ПДФ). Ацадемиц пресс.
Суттон, Р. С.; Барто, А. Г. (2017). Реинфорцемент Леарнинг: Ан Интродуцтион. Цамбридге, МА: Тхе МИТ Пресс.
Тијмс., Х.C. (2003). А Фирст Цоурсе ин Стоцхастиц Моделс. Wилеy. ИСБН 9780470864289.

Спољашње везе

Леарнинг то Солве Марковиан Децисион Процессес бy Сатиндер П. Сингх

[1] Беллман, Р. (1957). „А Марковиан Децисион Процесс”. Јоурнал оф Матхематицс анд Мецханицс. 6 (5): 679—684. ЈСТОР 24900506.

[2] Хоwард, Роналд А. (1960). Дyнамиц Программинг анд Марков Процессес. Тхе M.I.Т. Пресс.

[Wrobel_1984-3] Wробел, А. (1984). „Он Марковиан Децисион Моделс wитх а Фините Скелетон”. Матхематицал Метходс оф Оператионс Ресеарцх. 28 (Фебруарy): 17—27. С2ЦИД 2545336. дои:10.1007/бф01919083.

[Kearns_Sparse-4] Кеарнс, Мицхаел; Мансоур, Yисхаy; Нг, Андреw (2002). „А Спарсе Самплинг Алгоритхм фор Неар-Оптимал Планнинг ин Ларге Марков Децисион Процессес”. Мацхине Леарнинг. 49 (193–208): 193—208. дои:10.1023/А:1017932429737  .

[1]

[2]

[3]

[4]