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

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

وعملية القرار الماركوفية هي الصياغة المعيارية لهذا الوضع، وهي الأساس الذي بُني عليه التعلّم المعزّز كله.

أ. المكوّنات

تُحدَّد عملية القرار الماركوفية بأربعة أمور:

• مجموعة حالات $s$؛
• ومجموعة أفعال $A(s)$ متاحة في كل حالة؛
• ونموذج انتقال $P(s' \mid s, a)$، أي احتمال الوصول إلى $s'$ حين يُتّخذ الفعل $a$ في $s$؛
• ودالة مكافأة $R(s)$.

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

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

والسياسة $\pi$ دالةٌ توصي بفعل لكل حالة - لا خطةً لحالة طارئة واحدة، بل قاعدة سلوك كاملة. وحلّ عملية القرار الماركوفية يعني إيجاد سياسة جيدة.

ب. لماذا نخصم

منفعة تنفيذ سياسة $\pi$ انطلاقاً من الحالة $s$ هي مجموع المكافآت المتوقّع على الطريق:

$$U^{\pi}(s) = E\left[\sum_{t=0}^{\infty} \gamma^{t} R(S_t)\right],$$

حيث $S_t$ الحالة المبلوغة عند الزمن $t$، و$\gamma \in [0, 1]$ معامل الخصم. والخصم ليس تفصيلاً تقنياً مضافاً للراحة. فإن جاز ألا يبلغ الوكيل حالةً نهائية أبداً، كانت التواريخ لانهائية الطول وتباعدت المجاميع غير المخصومة عموماً - ومقارنة سياستين تسجّلان $+\infty$ ليست سؤالاً محدّد الصياغة.

ومع $\gamma < 1$ ومكافآت محدودة بـ$R_{\max}$، تحسم المتسلسلة الهندسية الأمر:

$$U([s_0, s_1, s_2, \dots]) = \sum_{t=0}^{\infty} \gamma^{t} R(s_t) \;\le\; \sum_{t=0}^{\infty} \gamma^{t} R_{\max} = \frac{R_{\max}}{1 - \gamma}.$$

فكل منفعة منتهية، ومن ثم كل زوج من السياسات قابل للمقارنة. و$\gamma$ القريبة من $0$ تجعل الوكيل قصير النظر؛ و$\gamma = 1$ تستعيد المكافآت الجمعية الصرفة، وهي آمنة فقط حين يُضمن بلوغ الوكيل حالةً نهائية - وتُسمّى السياسة التي تحمل ذلك الضمان سليمة.

والسياسة المثلى عندئذ $\pi^{*} = \arg\max_{\pi} U^{\pi}(s)$. ومن اللوازم السارّة للمكافآت المخصومة ذات الأفق اللانهائي أن $\pi^{*}$ لا تتوقّف على حالة البداية، فيمكننا الحديث عن السياسة المثلى وكتابة $U(s)$ للمنفعة تحتها.

$U(s)$ و$R(s)$ كميتان مختلفتان. فـ$R(s)$ المكافأة القصيرة الأجل لكونك في $s$؛ و$U(s)$ المجموع الطويل الأجل من $s$ فصاعداً. والخلط بينهما أشيع مصدر التباس في هذه المادة.

ج. معادلة بلمان

وهذه هي الفكرة المركزية. منفعة الحالة هي مكافأتها الفورية زائد المنفعة المتوقّعة المخصومة لحيث يأخذك أفضل فعل:

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

تلك هي معادلة بلمان، نسبةً إلى ريتشارد بلمان (1957). اقرأها ببطء: فـ$\max$ تختار أفضل فعل، و$\sum$ تأخذ المتوسط على حيث قد يوصلك ذلك الفعل فعلاً، و$\gamma$ تخصم المستقبل قياساً بالحاضر.

فإن كانت هناك $n$ حالة، كانت هناك $n$ معادلة كهذه بـ$n$ مجهولاً. وهي ليست خطية، لأن $\max$ ليس مؤثّراً خطياً - فلا نستطيع ببساطة عكس مصفوفة والانتهاء.

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

د. تكرار القيمة، محلولاً حتى التقارب

والعلاج هو التكرار. ابدأ بمنافع اعتباطية، وقيّم الطرف الأيمن، واستخدم الناتج طرفاً أيسر جديداً. وكرّر.

خذ عالماً من أربع حالات. حالتان غير نهائيتين، $s_1$ و$s_2$، لكلٍّ منهما $R(s) = -0.04$ - عقوبة صغيرة لكل خطوة، تشجّع على الإنهاء. وحالتان نهائيتان: GOAL بمنفعة $+1$ وPIT بـ$-1$. ولنضع $\gamma = 0.9$.

ولنهيّئ $U(s_1) = U(s_2) = 0$.

المسحة 1. لـ$s_2$، يعطي Right قيمة $0.8(1) + 0.2(-1) = 0.6$، بينما يعطي Left قيمة $0.8(0) + 0.2(0) = 0$. ومن ثم

$$U(s_2) = -0.04 + 0.9 \times 0.6 = -0.04 + 0.54 = 0.50 .$$

ولـ$s_1$، لا يرى الفعلان بعد إلا أصفاراً، فـ $U(s_1) = -0.04 + 0.9 \times 0 = -0.04$.

المسحة 2. الآن يستطيع $s_1$ رؤية القيمة التي ظهرت في $s_2$. فيعطي Right قيمة $0.8(0.50) + 0.2(-0.04) = 0.400 - 0.008 = 0.392$، متفوّقاً على $-0.04$ الخاصة بـ Stay:

$$U(s_1) = -0.04 + 0.9 \times 0.392 = -0.04 + 0.3528 = 0.3128 .$$

ولا تتحرّك $U(s_2)$، لأن نتيجتيها نهائيتان.

وبالمواصلة:

تتوقّف القيم عن الحركة عند $U(s_1) = 0.3902$ و$U(s_2) = 0.5000$.

ويمكننا تأكيد تلك النقطة الثابتة بالضبط بدل الوثوق بالتكرار. فما إن يُعلم أن Right هو الفعل الأفضل عند $s_1$، تصير معادلة بلمان هناك

$$U(s_1) = -0.04 + 0.9\big(0.8 \times 0.5 + 0.2\,U(s_1)\big) = 0.32 + 0.18\,U(s_1),$$

فـ$U(s_1) = 0.32 / 0.82 = 0.390243\ldots$، مطابقةً الجدول إلى أربع منازل عشرية.

وقراءة السياسة من المنافع المتقاربة تعطي Right في الحالتين، بمنفعتَي خَلَف متوقّعتين $\sum_{s'} P(s' \mid s, a)\,U(s')$ قدرهما $0.478$ مقابل $0.390$ عند $s_1$، و$0.600$ مقابل $0.412$ عند $s_2$. وبإضافة $R(s)$ والخصم تصيران قيمتَي الفعل $Q(s, a)$ في المقالة التالية: $0.3902$ مقابل $0.3112$ عند $s_1$، و$0.5000$ مقابل $0.3310$ عند $s_2$، بالترتيب نفسه.

يعيد تشغيله إنتاج الجدول أعلاه ويطبع Right للحالتين.

هـ. تكرار السياسة

يحسب تكرار القيمة المنافع بدقة عالية ويقرأ السياسة في النهاية. لكن السياسة كثيراً ما تتوقّف عن التغيّر قبل أن تستقرّ الأرقام بوقت طويل - ففي عالمنا كان Right أمثل عند $s_1$ منذ المسحة 2، بينما ظلّت المنزلة العشرية الرابعة تتحرّك عدة مسحات أخرى. ويستثمر تكرار السياسة ذلك بالمناوبة:

1. تقييم السياسة - بمعلومية سياسة ثابتة $\pi_i$، احسب المنافع التي تنتجها.
2. تحسين السياسة - أعد حساب أفضل فعل في كل حالة باستخدام تلك المنافع، فتنتج $\pi_{i+1}$.

كرّر حتى تتوقّف السياسة عن التغيّر. والعائد في الخطوة 1: فمع تثبيت السياسة لفعل كل حالة، لا يبقى $\max$، وتصير معادلة بلمان

$$U_i(s) = R(s) + \gamma \sum_{s'} P(s' \mid s, \pi_i(s))\, U_i(s') .$$

وهذه خطية - $n$ معادلة بـ$n$ مجهولاً، تُحلّ بالضبط بالجبر الخطي المعياري في $O(n^3)$. ولفضاءات الحالات الصغيرة يكون التقييم الدقيق غالباً أسرع المقاربات؛ أما الكبيرة فتعضّها الكلفة التكعيبية، فيُستخدم بدلاً منها تقييم تقريبي (بضع مسحات بدل حلّ دقيق).

و. ماذا يشتري هذا، وماذا يفترض

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

والوكيل المُلقى في بيئة مجهولة لا يملك أياً منهما. بل عليه أن يتصرّف، ويرصد ما يحدث، ويتحسّن - وذلك موضوع التعلّم المعزّز وتعلّم Q.

الخلاصات الأساسية

• عملية القرار الماركوفية هي حالات وأفعال ونموذج انتقال ومكافآت، وخاصية ماركوف تجعل الحالة الحالية ملخّصاً كافياً للماضي.
• السياسة تحدّد فعلاً لكل حالة؛ وحلّ العملية يعني إيجاد سياسة مثلى.
• الخصم يُبقي منافع الأفق اللانهائي منتهية، محدودةً بـ$R_{\max}/(1-\gamma)$، فتبقى السياسات قابلة للمقارنة.
• معادلة بلمان $U(s) = R(s) + \gamma \max_a \sum_{s'} P(s' \mid s,a)U(s')$ غير خطية بسبب $\max$.
• تكرار القيمة يطبّقها تحديثاً حتى تتقارب المنافع؛ واستقرّ عالمنا عند $U(s_1) = 0.3902$، مؤكَّدةً بالضبط بـ$0.32/0.82$.
• تكرار السياسة يناوب بين التقييم والتحسين؛ وتثبيت السياسة يزيل $\max$ ويترك معادلات خطية.
• وكلاهما يتطلّب نموذجاً معلوماً - فهما يخطّطان ولا يتعلّمان.

ما التالي

يُسقط التعلّم المعزّز وتعلّم Q افتراضَ معلومية النموذج ويتعلّم سلوكاً جيداً من التجربة وحدها.