فرایندهای تصمیم‌گیری مارکوف

مثال ساده MDP با سه حالت و دو عمل

فرایندهای تصمیم‌گیری مارکوف شامل پنج عنصر ${\displaystyle (S,A,P_{\cdot }(\cdot ,\cdot ),R_{\cdot }(\cdot ,\cdot ),\gamma )}$ است که در ادامه شرح داده می‌شود

• ${\displaystyle S}$ مجموعه متناهی (شمارش پذیر) حالت‌ها است.
• ${\displaystyle A}$ مجموعه متناهی عمل‌ها است. به‌طور جایگزین ${\displaystyle A_{s}}$ مجموعه متناهی از عمل‌ها است که حالت ${\displaystyle s}$
• ${\displaystyle P_{a}(s,s')=\Pr(s_{t+1}=s'\mid s_{t}=s,a_{t}=a)}$ احتمال این که اقدام ${\displaystyle a}$ در حالت ${\displaystyle s}$ و در زمان ${\displaystyle t}$ منجر به حالت ${\displaystyle s'}$ در زمان ${\displaystyle t+1}$
• ${\displaystyle R_{a}(s,s')}$ پاداش فوری (یا انتظار پاداش فوری) است که به علت رفتن از حالت ${\displaystyle s'}$ به حالت ${\displaystyle s}$
• ${\displaystyle \gamma \in [0,1]}$ ضریب کاهش است که نشان دهنده تفاوت ارزش پاداش آتی با پاداش فعلی است.

مسئله اصلی در MDPs پیدا کردن یک «سیاست» برای تصمیم‌گیر است. یافتن یک تابع مشخص عمل ${\displaystyle \pi }$ که تصمیم‌گیر در هنگامی که در حالت s است انتخاب کند ${\displaystyle s}$. توجه داشته باشید که که افزودن یک سیاست ثابت به فرایندهای تصمیم‌گیری مارکوف منجر به یک زنجیره مارکوف می‌شود.

هدف انتخاب یک سیاست ${\displaystyle \pi }$ که جهت به حداکثر رساندن برخی مجموع پاداش تصادفی است.

${\displaystyle \sum _{t=0}^{\infty }{\gamma ^{t}R_{a_{t}}(s_{t},s_{t+1})}}$     (زمانی که ${\displaystyle a_{t}=\pi (s_{t})}$)

که در آن ${\displaystyle \ \gamma \ }$ این ضریب کاهش و ${\displaystyle 0\leq \ \gamma \ <1}$ است. (به عنوان مثال ${\displaystyle \gamma =1/(1+r)}$ زمانی که ضریب کاهش r است) ${\displaystyle \gamma }$ به‌طور معمول نزدیک به ۱ است.

به دلیل خاصیت مارکوف، سیاست بهینه برای یک مسئله خاص را می‌توان به عنوان یک تابع از ${\displaystyle s}$ نوشت

MDPs را می‌توان با برنامه‌ریزی خطی یا برنامه‌نویسی پویا حل کرد.

فرایندهای تصمیم‌گیری مارکوف یک بازی تصادفی با تنها یک بازیکن است.