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

سلام. امروز تصمیم دارم راجع به فرآیندهای تصمیم‌گیری مارکوف بنویسم. این عنوان بارها به گوش من خورده و باهاش سروکار داشتم ولی مدت‌ها بود که از اون دوران گذشته بود و چند روز پیش با شنیدن این عنوان توی یه پادکست گفتم شاید بد نباشه یبار راجع بهش بنویسم که هم برای خودم مرور بشه و هم یه محتوای فارسی نوشته باشم.

معمولا یک MDP به صورت چندتایی $\langle S, A, T, R \rangle$ داده می‌شود. در ادامه این پست هر یک از این اجزاء تعریف خواهد شد.

متغیر $S$ مجموعه‌ای از همه حالت‌های ممکن است. در بازی ساده tic-tac-toe، هر مربع(خانه) می‌تواند یکی از سخ مقدار: خالی، $X$ و یا $O$ را داشته باشد. با این شرایط تعداد حالت‌های ممکن، بیش از $3^9$ نمی‌تواند باشد. با این وجود این مقدار، تعدادی از حالت‌هایی که در بازی tic-tac-toe معتبر نیست را نیز دربر می‌گیرد. برای مثال: یک صفحه هیچ‌گاه فقط با حرف $X$ یا $O$ نمی‌تواند پر شود. پس این نکته مهم است که $S$ را مجموعه‌ای از حالت‌های معتبر در هر محیط در نظر بگیریم.

متغیر $A$ مجموعه‌ای از فعالیت‌هایی است که برای هر عامل در دسترس است. این موضوع می‌تواند از راه‌های مختلفی توضیح داده شود. برای مثال: مسیر یک کاراکتر(شخصیت) در یک بازی ویدیوئی در یک صفحه مشبک(Grid) می‌تواند اعمال: رفتن به بالا، چپ، راست و پایین باشد. به همین صورت، کاراکتر می‌تواند عمل‌هایی مثل: چرخش ۹۰ درجه و رفتن به جلو را برای تولید نتایج یکسان انجام دهد. عامل‌ها در بسیاری از موارد می‌توانند هیچ عملی انجام ندهند (NoOp، non-action).

به دلیل محاسبات سنگین و پیچیده‌ای که حل یک مسئله MDP طلب می‌کند، معمولا یک نفر باید مراقب تعریف کردن مجموعه‌های $S$ و $A$ به صورت جامع و مختصر باشد.

متغیر $T$ تابع گذار است که مشخص می‌کند یک حالت چطور به وجود می‌آید. به عنوان ورودی، حالت فعلی، عملی که روی آن انجام شده و حالت بعدی را دریافت می‌کند و احتمال این‌که چقدر حالت بعدی پیشنهادشده، حالت بعدی مطلوب باشد را به عنوان خروجی برمی‌گرداند. یک صفحه بازی ساده را در نظر بگیرید که در آن بازی‌کن $i$ در‌حال‌حاضر در فضای $s_0$ باشدو باید عمل حرکت رو به جلو را انجام دهد. در این بازی برای حرکت رو به جلو، بازی‌کن یک تاس چهارطرفه را می‌اندازد و به تعداد آن رو به جلو حرکت می‌کند. در این مورد:

$T(s_i, GoForward, s_j)=0.25\: \forall i, j\: s.t.\: i<j<i+4$

و در غیر این صورت $T$ مقدار ۰.۰ را به هنوان خروجی برمی‌گرداند. این مورد هم معمولا به صورت زیر نوشته می‌شود:

$T:s_t \in S, a\in A , s_{t+1} \in S \in S \to [0,1]$

توجه کنید که $T$ به $S_t$ بستگی دارد ولی به $s_{t-1}$ وابسته نیست. چرا تابع گذار فقط به حالت فعلی وابسته است ولی به حالت‌های قبلی وابسته نیست؟ با اغین که از لحاظ ریاضی این کار ممکن است، ولی این کار زمانی که حالت‌ها به صورت مناسبی تعریف شده باشند ضروری نیست. در ساختن یک MDP ما باید سعی کنیم که همه حالت‌ها از نظر آماری به اصطلاح کافی یا مناسب باشند. برای همین دانستن حالت فعلی کافی است.

در بازی tic-tac-toe می‌توان از چندین مسیر به یک حالت بعدی یکسان رسید. برای کنجکاوی ممکن است شما علاقه‌مند باشید که بدانید کدام یک از مسیرها شنا را به یک حالت خاص می‌رساند، ولی این موضوع تأثیری در نتیجه بازی و چگونگی پیدا کردن استراتژی بهینه ندارد.

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

متغیر $R$ تابع تشویق(جایزه) است. این تابع به عنوان ورودی، حالت فعلی و حرکتی که انجام شده‌ را گرفته و امتیازی که عامل با انجام‌دادن آن حرکت به دست می‌آورد را نمایش می‌دهد و معمولا همه مقدارهای گویا را می‌پذیرد و به‌صورت زیر تعریف می‌شود:

$R: s_t \in S,a \in A \to R$

توجه کنید که برخلاف $T$ ، $R$ به حالت‌ بعدی وابسته نیست. آیا این به معنی فقط در نظر گرفتن حالت فعلی و عدم در نظر گرفتن پاداشی که در آینده توسط عامل به‌دست می‌أید است؟ قطعا خیر. یک عامل باید به‌طور مشخص ارزشی که با دادن حالت فعلی و حرکت بعدی به‌دست می‌آورد را در نظر بگیرد. عاملی که این کار را انجام می‌دهد، را عامل «افق صفر(horizon zero)» می‌نامند. اجازه دهید که بیشتر در این مورد زمانی که معنی حل کردن یک MDP را تعریف کردیم بحث کنیم.

یک MDP توصیفی از یک سیستم است. با این که مثال‌های ما بازی‌های ساده هستند، ممکن است کسی یک MDP برای بازی شطرنج، گو(GO)، تجارت سهام، رانندگی و مورد‌های بی‌شمار دیگر ایجاد کند.

معمولا، زمانی که شما یک MDP را تعریف کردید، می‌خواهید که آن را حل کنید. به‌ویژه این که شما علاقه‌مند هستید که استراتژی بهینه‌ای را پیدا کنید که عامل باید با آن منطبق شود تا بیشترین امتیاز را زمان بازی کردن به‌دست آورد. این استراتژی بهینه همچنین سیاست بهینه نیز نامیده می‌شود. یک سیاست،‌ هر فرآیند تصمیم‌گیری است که هر گذشته ممکن را به یک انتخاب درباره حرکت بعدی که انجام می‌شود، نگاشت می‌کند. از این راه، یک MDP به صورت مستقیم به یک مدل عامل نگاشت می‌شود.

پیدا کردن یک راه حل بهینه برای یک MDP روی یک بازی غیرمرسوم از نظر هزینه محاسباتی می‌تواند پرهزینه باشد. همچنین این چارچوب عمیقا تحت تأثیر نفرین ابعاد یا ویژگی‌ها(curse of dimensionality) است. دو رویکرد کلی برای پیدا کردن سیاست بهینه وجود دارد: جست‌وجوی افقی محدود(finite horizon) و جست‌وجوی افقی نامحدود(infinite horizon) با کاهش دادن(تخفیف).

برای جست‌وجوی افقی محدود، یک عامل تعداد گام‌های بعدی برای تعیین حرکت بهینه را محاسبه می‌کند. در نظر بگیرید که هر مسیر ممکن در بازی می‌تواند به دنبال حرکت‌های $h$ بگردد. در میان همه مسیرها، مسیری که بیشترین نفع را برای شما دارد، انتخاب کتید و اولین حرکت‌ را برای آن مسیر اجرا کنید. زمانی که بازی‌کن‌های مقابل باید واکنش نشان دهند،‌ می‌توانند همین فرآیند‌ها را با یک یا چند مشاهده و یک پنجره پیش‌بینی لغزنده(sliding look-ahead window) سایز $h$ تکرار کنند.

برای جست‌وجوی افقی نامحدود یک عامل به دنبال استراتژی‌ای می‌گردد که فرض می‌کند بازی تا ابد ادامه پیدا می‌کند. بازی کردن تا ابد مانند این است که به صورت نامحدود، امکان داشتن امتیازهای محدود(مختلف) را داشته باشیم. بدین ترتیب اول هرکدام سعی می‌کند تا متوسط امتیازها و یا امتیاز با کاهش دادن(تخفیف) را بیشینه کند. امتیاز با کاهش دادن(تخفیف) به صورت نسبت دادن مقدار(وزن) کمتر به امتیاز‌های به‌دست‌آمده بیشتر در آینده، تفسیر می‌شود. برای جست‌وجوی افقی نامحدود، پیاده‌سازی‌های مختلف معمولا جست‌وجو را زمانی که بتواند مطمئن شود بهترین سیاست جاری آن‌ها، حداقل مقدار $\epsilon$ که نزدیک به سیاست بهینه واقعی است، متوقف می‌کنند.

شاد باشید.

پانوشت(ها):

همچنان مشغول مطالعه کتاب «دنیای سوفی» نوشته «یوستین گوردر» هستم و به محض این که تمام شد اینجا راجع بهش می‌نویسم.

اشتراک‌گذاری

4 فکر می‌کنند “فرآیندهای تصمیم‌گیری مارکوف به زبان ساده”

پرتو اکتبر 28, 2019 در 11:11

سلام. ممنونم از توضیحات خوب و مفیدتون. امروز با وب شما آشنا شدم و با توجه به محتوا فک کنم بازم سر بزنم:) موفق باشید

پاسخ دادن ↓
1. پیمان برجوییان نویسندهاکتبر 28, 2019 در 13:31
  
  سلام. خیلی ممنون
  امیدوارم بتونم مطلب‌های جدیدتری بذارم بزودی.
  
  پاسخ دادن ↓
فرخنده می 6, 2023 در 21:55

سلام،
خیلی ممنون بابت توضیح این موضوع. خوشحالم با سایتتون آشنا شدم.

پاسخ دادن ↓
1. پیمان برجوییان نویسندهجولای 22, 2023 در 16:10
  
  سلام.
  خواهش می‌کنم، خوشحالم که براتون مفید بوده و ممنون که نظرتون رو نوشتین.
  موفق باشید.
  
  پاسخ دادن ↓

لایه‌های مخفی یک داده پرت

روزنوشته‌های یک علاقمند به یادگیری انسان، ماشین و علم داده

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

4 فکر می‌کنند “فرآیندهای تصمیم‌گیری مارکوف به زبان ساده”

دیدگاهتان را بنویسید لغو پاسخ