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

فرایندهای تصمیم‌گیری مارکوف الگو:به انگلیسی (به اختصار: MDPs) یک چارچوب ریاضی است برای مدل‌سازی تصمیم‌گیری در شرایطی که نتایج تا حدودی تصادفی و تا حدودی تحت کنترل یک تصمیم‌گیر است. MDPs برای مطالعه طیف گسترده‌ای از مسائل بهینه سازی که از طریق برنامه‌نویسی پویا و یادگیری تقویتی حل می‌شوند مفید است. حداقل از اوایل ۱۹۵۰ میلادی MDPs شناخته شده‌است (cf. الگو:Harvard citation no brackets). هسته اصلی پژوهش در فرایندهای تصمیم‌گیری مارکوف حاصل کتاب رونالد هوارد است که در سال ۱۹۶۰ تحت عنوان «برنامه‌نویسی پویا و فرایندهای مارکف» منتشر شد.الگو:Sfn فرایندهای تصمیم‌گیری مارکوف در طیف گسترده‌ای از رشته‌ها از جمله رباتیک، اقتصاد و تولید استفاده می‌شود.

به‌طور دقیق تر، فرایندهای تصمیم‌گیری مارکوف، فرایندهای کنترل تصادفی زمان گسسته است. در هر گام، فرایند در حالت $s$ است و تصمیم‌گیر اقدام (عمل) $a$ را انتخاب می‌کند. پاسخ فرایند، رفتن به حالت جدید $s$ (در گام بعدی) به‌طور تصادفی و همچنین دادن پاداش R_a(s,s') به تصمیم‌گیر است $R_a(s,s^{\prime })$.

تعریف

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

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

• $S$ مجموعه متناهی (شمارش پذیر) حالت‌ها است.
• $A$ مجموعه متناهی عمل‌ها است. به‌طور جایگزین $A_s$ مجموعه متناهی از عمل‌ها است که در حالت $s$ قرار دارند.
• $P_a(s,s^{\prime })=\mathrm{Pr}(s_{t+1}=s^{\prime }\mid s_t=s,a_t=a)$ احتمال این که اقدام $a$ در حالت $s$ و در زمان $t$ منجر به حالت $s^{\prime }$ در زمان $t+1$ شود.
• $R_a(s,s^{\prime })$ پاداش فوری (یا انتظار پاداش فوری) است که به علت رفتن از حالت $s^{\prime }$ به حالت $s$ رخ می دهد.
• $\gamma \in [0,1]$ ضریب کاهش است که نشان دهنده تفاوت ارزش پاداش آتی با پاداش فعلی است.

مسئله

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

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

$\sum _{t=0}^{\mathrm{\infty }}{\gamma }^t{R}_{a_t}(s_t,s_{t+1})$     (زمانی که $a_t=\pi (s_t)$)

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

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

الگوریتم

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

تعمیم و گسترش

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

مشاهده پذیری جزئی

در راه حل بالا فرض می‌شود که وقتی عمل انتخاب می‌شود که حالت $s$ شناخته شده باشد؛ در غیر این صورت $\pi (s)$ را نمی‌توان حساب کرد. زمانی که این فرض درست نیست مسئله فرایندهای تصمیم‌گیری مارکوف با مشاهده پذیری جزئی یا POMDP نامیده می‌شود.

یادگیری تقویتی

اگر احتمالات یا پاداش مشخص نباشد مسئله به عنوان یادگیری تقویتی شناخته می‌شود الگو:Harvard citation.

یادگیری اتوماتا

یکی دیگر از کاربردهای MDP یادگیری ماشین با نام یادگیری اوتوماتا شناخته می‌شود. این هم یک نوع از یادگیری تقویتی است البته در صورتی که محیط به شیوه تصادفی باشد. الگو:Sfn

تفسیر نظریه رده‌ها

غیر از پاداش، فرایندهای تصمیم‌گیری مارکوف $(S,A,P)$ را می‌توان به عنوان نظریه رده‌ها درک کرد.

در این روش پردازش‌های تصمیم‌گیری مارکوف می‌تواند تعمیم از monoids (دسته‌ها با یک شی) را به دلخواه دسته‌بندی کنید. یکی می‌توانید تماس بگیرید و نتیجه $(𝒞,F:𝒞\to 𝐃𝐢𝐬𝐭)$ یک متن وابسته به پردازش‌های تصمیم‌گیری مارکوف روندچرا که در حال حرکت از یک شیء به دیگری در $𝒞$ تغییرات در این مجموعه موجود اقدامات و مجموعه‌ای از امکان متحده است.

فرایندهای تصمیم‌گیری مارکوف فازی (FDMPs)

در فرایندهای تصمیم‌گیری مارکوف سیاست بهینه سیاستی است که مجموع پاداش‌های آتی را به حداکثرمی‌رساند؛ بنابراین سیاست بهینه شامل چندین عمل است که متعلق به مجموعه متناهی از اعمال است. در فرایندهای تصمیم‌گیری مارکوف فازی (FDMPs) ابتدا تابع ارزش با فرض غیر فازی بودن محاسبه می‌شود؛ سپس توسط یک سیستم استنتاج فازی سیاست مطلوب استخراج می‌شود. به عبارت دیگر تابع ارزش تابع به عنوان یک ورودی برای سیستم استنتاج فازی استفاده شده‌است و سیاست مطلوب، خروجی سیستم استنتاج فازی است.