عمليات القرار الماركوفية ومعادلة بلمان

افترض البحث أن أفعالك تفعل ما تقصده. أسقِط ذلك الافتراض - ودَع الفعل ينجح في معظم الأوقات وينزلق أحياناً - فتكفّ سلسلة النقلات الثابتة عن كونها جواباً نافعاً. وما تحتاجه بدلاً منها قاعدةٌ تخبرك بما تفعل من حيث تنتهي فعلاً.

الأجزاء الخمسة

عملية القرار الماركوفية مسألةُ قرار متتابع في بيئة تامّة الرصد عشوائية. وتُحدَّد بـ:

واثنان منها يحملان ثقلاً أكبر مما يبدو أول الأمر.

نموذج الانتقال هو حيث يسكن اللايقين. فـ$P(s' \mid s, a)$ توزيع لا نتيجة. فمحاولة التحرّك يميناً قد تأخذك يميناً باحتمال $0.8$ وتتركك مكانك باحتمال $0.2$. والوكيل لا يختار $s'$؛ بل يختار $a$ فقط.

وخاصية ماركوف هي الافتراض الذي يجعل هذا قابلاً للمعالجة. فالحالة التالية تتوقّف على الحالة والفعل الحاليين وحدهما - لا على كيفية وصولك. وهذا تقييد حقيقي، وهو ما يتيح إلحاق عدد واحد بكل حالة بدل إلحاقه بكل تاريخ ممكن.

المكافأة على الحالة. يتبع هذا المساق راسل ونورفيغ، حيث تُلحَق المكافأة بالحالة التي أنت فيها، وتُكتب $R(s)$. وكثير من الأدبيات يلحقها بالانتقال بدلاً من ذلك، $R(s,a,s')$. والنظرية واحدة في الحالين، لكن المعادلات تبدو مختلفة، فتوقّع هذا التباين عند مقارنة المصادر.

لماذا يكون الجواب سياسة

لأن النتائج عشوائية، تكون خطةٌ مثل «يمين، يمين، أعلى» بلا قيمة: فأول انزلاق يضعك في موضع لم تعد بقية السلسلة تخاطبه.

والجواب سياسة $\pi(s)$ - فعلٌ موصى به لـكل حالة. ولا تنفد قابليتها للتطبيق أبداً، لأنك مهما حدث تكون في حالة ما ولدى السياسة جواب لها. والسياسة المثلى $\pi^*$ هي التي تعظّم المنفعة المتوقّعة.

علامَ تتوقّف أفضل سياسة. الشكل أدناه هو عالم 4x3 عند راسل ونورفيغ: أربعة مربّعات في ثلاثة، أحدها يسدّه جدار، ومخرجان قيمتاهما $+1$ و$-1$. ونموذج انتقاله أغنى قليلاً من المذكور أعلاه: كل حركة تمضي في الاتجاه المقصود باحتمال $0.8$ وإلى كل جانب باحتمال $0.1$، ولا خصم فيه. والشيء الوحيد الذي تحرّكه هو مكافأة البقاء R، أي $R(s)$ التي يدفعها كل مربّع غير نهائي، والسياسة المثلى دالة سُلّمية فيها: عند ثماني عتبات ينقلب سهم مربّع واحد. ويعيدها زر قيمة الكتب -0.04 إلى القيمة التي يستخدمها راسل ونورفيغ.

معادلة بلمان

لنفترض أنك تعرف سلفاً $U(s)$، منفعة كل حالة. عندئذ تتفكّك قيمة كونك في $s$ إلى ما تجنيه الآن وما تستطيع توقّعه بعد ذلك:

$$U(s) = R(s) + \gamma \max_{a \in A(s)} \sum_{s'} P(s' \mid s,a)\, U(s')$$

اقرأها ببطء، فكل قطعة تؤدّي عملاً:

• $R(s)$ - تُجنى لكونك في $s$، مهما فعلت تالياً.
• $\max_a$ - أنت تختار الفعل، فتأخذ أفضل المتاح.
• $\sum_{s'} P(s' \mid s,a) U(s')$ - أنت لا تختار النتيجة، فالمستقبل متوسط مرجّح بنموذج الانتقال.
• $\gamma$ - تخصم ذلك المستقبل قياساً بالحاضر.

والترتيب مهم: عظِّم على ما تتحكّم فيه، وتوسّط على ما لا تتحكّم فيه.

وهذا شرط لا وصفة. فهو لا يقول شيئاً عن كيفية إيجاد $U$؛ بل يقول فقط إن $U$ الحقيقية يجب أن تحقّقه عند كل حالة في آنٍ واحد. ومع $n$ حالة تحصل على $n$ معادلة بـ$n$ مجهولاً - لكنها غير خطية، لأن $\max$ ليس مؤثّراً خطياً، فلا تستطيع حلّها بالجبر الخطي ببساطة. والانتقال من هذا الشرط إلى أرقام فعلية هو موضوع الدرس التالي.

ترتيب العمليات هو ما لا تُظهره الصيغة، ولذلك يفكّكه الشكل أدناه. فلكل فعل سطره، وفيه متوسّطه على النتائج التي لا يتحكّم فيها، ويُؤخذ الحدّ الأقصى ظاهرًا بين السطرين لا داخل رمز. وحرّك معامل الخصم لترى حدّ المستقبل ينشأ من العدم: فعند الصفر لا يرى الوكيل إلا كلفة البقاء، وقرب الواحد تغلب عليه مكافأة تبعد عدّة خطوات.

لماذا الخصم

مع $\gamma < 1$، تساوي مكافأةٌ على بُعد $k$ خطوة $\gamma^k$ من قيمتها الاسمية. ولذلك سببان مهمّان:

1. يحدّ المجموع. إذ كان سلسلة لانهائية من مكافآت محدودة ستجمع إلى ما لا نهاية، واللانهايات لا تُقارَن.
2. يعبّر عن تفضيل حقيقي. فالأقرب أفضل عادةً.

وعند $\gamma = 0$ يكون الوكيل قصير النظر، لا يعبأ إلا بـ$R(s)$. وحين $\gamma \to 1$ يصير بعيد النظر، مستعدّاً لقبول مسافة طويلة بلا مكافأة مقابل عائد كبير في النهاية.

جرّبه مباشرةً. راقب احتمالات الإشغال وهي تتطوّر من معدّلات الانتقال وحدها، بلا سياسة بعد. وهذه سلسلة بزمن متّصل فيها حالة عطل ماصّة، فهي لا تستقرّ أبداً: فعلى الأفق المطبوع تنصرف الكتلة باطّراد إلى failed.

قبل الاختبار

كن قادراً على سرد الأجزاء الخمسة، وصوغ ما تحظره خاصية ماركوف، وتفسير لماذا تتفوّق السياسة على الخطة تحت اللايقين، والإشارة إلى أي حدّ في معادلة بلمان تعظيمٌ وأيّها توقّع - ولماذا لا يتبادلان. وتشتقّ المقالة المرافقة عمليات القرار الماركوفية المادةَ نفسها بإسهاب أكبر.