عمليات قرار ماركوف | ML-101

من حلقة إلى نموذج

وصف الدرس 14.1 التفاعل: حالة، ففعل، فمكافأة، فحالة تالية، وهكذا. وهذا الوصف يكفي للحديث عن المشكلة ولا يكفي مطلقًا لحلّها. فلكي تحسب أي شيء عليك أن تقول بدقة ما هي البيئة، والجواب القياسي هو عملية قرار ماركوف — أو MDP. وهي الصياغة التي بُني عليها المجال كله، ويخصّص لها ساتون وبارتو (2018) الفصل الثالث من كتابهما.

وثمرة هذه الصياغة معادلة تكرارية واحدة، تعود إلى بلمان (1957)، تربط قيمة الموضع الذي أنت فيه بقيمة المواضع التي يمكن أن تنتقل إليها. ومتى امتلكت تلك المعادلة استطعت حلّ المشكلات الصغيرة حلًا مضبوطًا، وكل طريقة في الدرسَين 14.3 و14.4 هي سبيل إلى تقريب حلّها عندما لا تكون المشكلة صغيرة.

خاصية ماركوف، وما تُلغيه من الحساب

تتمتع الحالة بـخاصية ماركوف إذا كانت تلخّص الماضي تلخيصًا كافيًا بحيث لا يضيف الماضي شيئًا. وبصيغة رسمية: احتمال الحالة والمكافأة التاليتين يعتمد على الحالة والفعل الحاليين وحدهما — لا على الطريق الذي أوصلك إلى هناك.

خاصية ماركوف

p(s',r \mid s,a) = \Pr\{ S_{t+1} = s',\; R_{t+1} = r \mid S_t = s,\; A_t = a \}

الدالة p ذات الوسائط الأربعة هي دينامية البيئة: بمعلومية أنك كنت في الحالة s واتخذت الفعل a، تعطي احتمال الوصول إلى s′ وجمع المكافأة r. ولا يظهر في الطرف الأيمن أي شيء عن S_t-1 أو A_t-1 أو أي خطوة أسبق. وهذا الغياب هو الافتراض كله.

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

والحل في الغالب الأعم هو إعادة تعريف الحالة لا التخلي عن الإطار: كدّس الإطارات القليلة الأخيرة، أو أضف السرعة، أو أضف الملخص الجاري. وهذه هندسة، ولها ثمن — فكل كمية تضيفها تضاعف حجم فضاء الحالات. وقد سمّى بلمان هذا النمو لعنة الأبعاد، وهي سبب نفاد المساحة أمام الطرائق الجدولية، وسبب انتهاء الدرس 14.3 إلى استبدال الجدول بشبكة عصبية.

حين تكون الحالة مخفية فعلًا

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

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

عملية قرار ماركوف هي خمسة أشياء مجتمعة، وتسميتها هي معظم عمل صياغة المشكلة.

S وA وp وr وγ

الحالات S. مجموعة المواقف التي يمكن أن يكون فيها الوكيل. وبعضها قد يكون نهائيًا، فينهي الحلقة.

الأفعال A. ما يجوز للوكيل فعله. وكثيرًا ما يعتمد هذا على الحالة، فيُكتب A(s).

احتمالات الانتقال p(s′, r | s, a). الدينامية المذكورة أعلاه. والبيئات الحتمية هي الحالة الخاصة التي يستقر فيها الاحتمال كله على نتيجة واحدة.

دالة المكافأة r. المكافأة المتوقعة لانتقال ما، وتُستخرج من p بالمتوسط على r. وهي خاصية البيئة لا خاصية الوكيل، وتحذير الدرس 14.1 من التلاعب بالمكافأة هو تحذير من كيفية كتابة هذا الجزء.

عامل الخصم γ. عدد يحقق 0 ≤ γ ≤ 1 يقول كم تساوي مكافأةٌ متأخرة خطوةً واحدة بالنسبة إلى مكافأة الآن.

العائد، ولماذا يُخصَم المستقبل

الوكيل لا يعظّم المكافأة التالية، بل يعظّم كل ما يأتي بعدها، وهذا المجموع يحتاج إلى اسم وتعريف. العائد G_t هو المجموع المخصوم لكل المكافآت المستقبلية من الزمن t وصاعدًا.

العائد المخصوم

G_t = \sum_{k=0}^{\infty} \gamma^k R_{t+k+1}

المكافأة التي تصل بعد خطوة واحدة هي R_t+1 وهي غير مخصومة، لأن k = 0 يعطي γ⁰ = 1؛ والتي تليها موزونة بـγ، ثم γ²، وهكذا. ولاحظ أن اصطلاح الدليل من الدرس 14.1 يعمل هنا فعلًا: الفعل في الزمن t يكسب R_t+1، فيبدأ المجموع من t+1.

وللخصم ثلاثة أسباب، أولها فقط رياضي. إذا لم ينتهِ التفاعل أبدًا، فقد يكون مجموع المكافآت غير المخصوم لا نهائيًا، واللانهايات لا تُقارَن — فسياستان تُحصّلان كلتاهما لا نهاية لا يمكن التمييز بينهما. ومع γ < 1 ومكافآت محدودة تتقارب المتسلسلة الهندسية، فتصبح لكل سياسة درجة منتهية وتصبح المقارنة ذات معنى.

وثانيًا، الأقرب أفضل حقًا في معظم المشكلات الواقعية: المال الآن أفضل من المال لاحقًا، والروبوت الذي يصل إلى الهدف في عشر خطوات أفضل من الذي يصل في ألف. وثالثًا، يرمّز γ عدم اليقين في المستقبل البعيد — فحقٌّ في مكافأة تبعد مئة خطوة يساوي أقل، لأن كثيرًا يمكن أن يعترض الطريق.

والطرفان مفيدان في الفهم. عند γ = 0 يصبح العائد هو R_t+1 فقط ويصبح الوكيل قصير النظر تمامًا: يعظّم الخطوة التالية وسيسير مطمئنًا إلى حافة هاوية في الخطوة التي بعدها. وكلما اقترب γ من 1 صار الوكيل أبعد نظرًا وصارت عوائد السياسات المختلفة أصعب على التمييز، وهذا يبطّئ التعلم. والقيم المعتادة عمليًا بين 0.9 و0.99. وγ = 1 مشروع فقط في المهام الحلقية المضمون انتهاؤها، حيث يكون المجموع منتهيًا لأن له نهاية.

السياسة، وقيمة الحالة، وقيمة الفعل

السياسة π(a | s) هي قاعدة سلوك الوكيل: احتمال اختيار الفعل a في الحالة s. وكل ما يُحاكَم الوكيل عليه ينبع من سياسته، لأن السياسة مع الدينامية p تحددان التوزيع على المسارات، وبالتالي التوزيع على العوائد.

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

دالة قيمة الحالة

V^{\pi}(s) = \mathbb{E}_{\pi}\left[ G_t \mid S_t = s \right]

العائد المتوقع من الحالة s تحت السياسة π. وهو توقع لسببين منفصلين: السياسة قد تختار الأفعال عشوائيًا، والبيئة قد تستجيب عشوائيًا. والدليل العلوي π ليس زخرفة — فلا قيمة للحالة في المجرَّد، بل قيمة تحت طريقة سلوك ما.

أما دالة قيمة الفعل فتسأل سؤالًا مختلفًا قليلًا وأنفع كثيرًا: ماذا لو اتخذتُ فعلًا محددًا هنا أولًا، ثم اتبعت π؟

دالة قيمة الفعل

Q^{\pi}(s,a) = \mathbb{E}_{\pi}\left[ G_t \mid S_t = s, A_t = a \right]

Q هي ما تحتاجه لكي تختار. فمع V وحدها عليك أن تنظر خطوة إلى الأمام عبر النموذج p لتقارن الأفعال؛ ومع Q تقارن ببساطة أرقامًا مفهرسة حسب الفعل أصلًا وتأخذ أكبرها. وهذا بالضبط سبب تعلُّم الدرس 14.3 لـQ بدلًا من V — فهي الصورة التي لا تحتاج نموذجًا.

معادلة بلمان للتوقع

هنا الفكرة التي تقوم عليها الوحدة كلها. العائد من حالة ينقسم إلى المكافأة التالية مباشرة زائد العائد المخصوم من حيث تهبط. خُذ التوقع للطرفين فتصبح دالة القيمة تكرارية: V تظهر في طرفَي تعريفها.

معادلة بلمان للتوقع

V^{\pi}(s) = \sum_a \pi(a \mid s) \sum_{s',r} p(s',r \mid s,a) \left[ r + \gamma V^{\pi}(s') \right]

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

فقيمة السياسة ليست شيئًا عليك محاكاته ألف حلقة لتكتشفه. إنها حلّ نظام معادلات تستطيع كتابته من النموذج. وهذا مردود هائل لافتراض واحد عن الحالات.

الأمثلية: استبدل المتوسط بحدٍّ أقصى

تقييم سياسة معطاة ليس هو الهدف؛ بل إيجاد أفضلها. والسياسة المثلى π^* هي التي لا تقلّ قيمتها عن قيمة أي سياسة أخرى في كل حالة. ولكل عملية قرار ماركوف منتهية سياسة مثلى واحدة على الأقل، وكل السياسات المثلى تتشارك دالة القيمة V^* نفسها.

وتختلف معادلة بلمان للأمثلية عن معادلة التوقع في موضع واحد بالضبط. فالوكيل الأمثل لا يأخذ متوسط ما قد تفعله سياسته — بل يأخذ أفضل فعل متاح. لذا يصبح المجموع الخارجي على π حدًا أقصى على a.

معادلة بلمان للأمثلية

V^{*}(s) = \max_a \sum_{s',r} p(s',r \mid s,a) \left[ r + \gamma V^{*}(s') \right]

التوقع الداخلي على عشوائية البيئة يبقى — فلا يمكنك أن تعظّم على ما يفعله العالم. والحد الأقصى على ما تفعله أنت فحسب. ولاحظ أن المعادلة لم تبقَ خطية، ولهذا يُوجَد دالة القيمة المثلى بالتكرار لا بحلّ نظام خطي.

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

حلّها عندما يكون النموذج معروفًا

إذا كانت p معروفة، فيمكن حلّ معادلة بلمان للأمثلية بـالبرمجة الدينامية — طريقة بلمان (1957)، وموضوع الفصل الرابع من ساتون وبارتو. والحيلة أن تتوقف عن معاملتها كمعادلة تُحَلّ وتعاملها كإسناد يُكرَّر.

تحديث تكرار القيمة

V_{k+1}(s) \leftarrow \max_a \sum_{s',r} p(s',r \mid s,a) \left[ r + \gamma V_k(s') \right]

معادلة الأمثلية نفسها بسهم بدل علامة المساواة، مُمرَّرة على كل حالة. ابدأ من أي V₀ — الأصفار كلها أمر معتاد — وكرّر. ومن أجل γ < 1 يكون المرور تقلّصًا، فتتقارب التقديرات إلى V^* من أي نقطة انطلاق. وعمليًا تتوقف عندما يهبط أكبر تغيّر في مرور واحد تحت حدّ تحمّل.

اعملها يدويًا على مَمرٍّ من أربع خلايا. الحالات هي 1 و2 و3 وهدف نهائي G، على استقامة واحدة. والفعلان يسارًا ويمينًا، وكلاهما حتمي؛ والارتطام بالحائط الأيسر من الحالة 1 يُبقيك في الحالة 1. والتحرك يمينًا من الحالة 3 يصل إلى G، فيدفع مكافأة 1 وينهي الحلقة. وكل انتقال آخر يدفع 0. اضبط γ = 0.9 وV₀ = 0 في كل مكان.

تكرار القيمة، ثلاث مرورات

المرور 1. الحالة 3: يمينًا تعطي 1 + 0.9 × 0 = 1، ويسارًا تعطي 0 + 0.9 × 0 = 0، فتكون V₁(3) = 1. والحالتان 1 و2 لا تريان إلا أصفارًا في كل اتجاه، فتبقيان عند 0.

المرور 2. الحالة 2: يمينًا تعطي 0 + 0.9 × V₁(3) = 0.9، فتكون V₂(2) = 0.9. والحالة 3 تبقى عند 1. والحالة 1 لا تزال 0.

المرور 3. الحالة 1: يمينًا تعطي 0 + 0.9 × 0.9 = 0.81، فتكون V₃(1) = 0.81. ولا يتغير شيء في المرور التالي، فهذه هي V^*: 0.81 و0.9 و1.

اقرأ الجواب. القيمة تنقص مع البعد عن الهدف بعامل γ لكل خطوة، وهذا بالضبط معنى γ. والتصرف بجَشَع بالنسبة إلى هذه الأرقام يعطي «اتجه يمينًا دائمًا» — وهي السياسة المثلى، مستخرَجة دون أي بحث.

والبديل هو تكرار السياسة، الذي يبادل بين خطوتين بدلًا من دمجهما. تقييم السياسة يحلّ معادلة بلمان للتوقع للسياسة الحالية، فيعطي V^π مضبوطة. ثم تحسين السياسة يجعل السياسة جَشِعة بالنسبة إلى تلك V^π. كرّر حتى لا تغيّر خطوة التحسين شيئًا، فتكون السياسة عندئذٍ محقِّقة لمعادلة الأمثلية ومثلى.

تكرار السياسة على المَمرّ نفسه

ابدأ من السياسة السيئة قصدًا «اتجه يسارًا دائمًا». يعطي التقييم V = 0 في كل حالة، لأن الهدف لا يُبلَغ أبدًا. ويجد التحسين أن الاتجاه يمينًا في الحالة 3 يساوي 1 مقابل 0، فيقلب الحالة 3 إلى يمينًا.

قيّم مرة أخرى: V(3) = 1 وV(2) = 0 وV(1) = 0. ويجد التحسين الآن أن الحالة 2 تساوي 0.9 يمينًا مقابل 0 يسارًا، فيقلبها. قيّم: V(3) = 1 وV(2) = 0.9 وV(1) = 0. ويقلب التحسين الحالة 1، لأن 0.9 × 0.9 = 0.81 تتجاوز 0. قيّم: 0.81 و0.9 و1 — والتحسين التالي لا يغيّر شيئًا، فالسياسة مثلى.

ولاحظ ما حدث: صارت السياسة مثلى بعد ثلاث تحسينات مع أن القيم كانت لا تزال تُصقل. وهذا هو النمط المعتاد، وهو سبب احتياج تكرار السياسة إلى دورات قليلة على نحو مدهش. تكرار القيمة أرخص في المرور الواحد لأنه لا ينتظر انتهاء التقييم؛ وتكرار السياسة يتقارب في دورات أقل لأن كل دورة تستخدم دالة قيمة مضبوطة. وكلاهما برمجة دينامية، وكلاهما يحتاج p.

وهذا يأخذ الدرس إلى حدّه هو. فكل ما سبق يحتاج إلى معرفة احتمالات الانتقال، وهي في معظم المشكلات الواقعية غير معروفة: لا أحد يسلّمك دينامية مستودع أو سوق أو مستخدم. وهذا المكوّن الغائب الواحد هو موضوع الدرس 14.3 — تعلُّم Q من الخبرة وحدها، دون أي نموذج للبيئة على الإطلاق.

أهم النقاط

عملية قرار ماركوف هي الصياغة الرسمية لمشكلة التعلم المعزَّز: حالات، وأفعال، واحتمالات انتقال p(s′, r | s, a)، ودالة مكافأة، وعامل خصم γ يحقق 0 ≤ γ ≤ 1.
تقول خاصية ماركوف إن الحالة والفعل الحاليين يحددان توزيع ما يأتي بعدهما، دون أي اعتماد على التاريخ. والسرعة والاتجاهات وتكديس الإطارات موجودة لتحقيق ذلك.
العائد هو المجموع المخصوم للمكافآت المستقبلية. والخصم يُبقي المهام المستمرة منتهية، ويفضّل المكافأة الأقرب، ويتحوّط للمستقبل البعيد. وγ = 1 آمن فقط عندما تنتهي الحلقات.
V^π(s) هي العائد المتوقع من s تحت π؛ وQ^π(s, a) هي العائد المتوقع بعد الالتزام بـa أولًا. وQ هي الصورة التي تستطيع التصرف بها دون نموذج.
معادلة بلمان للتوقع تجعل V تكرارية: المكافأة الفورية زائد القيمة المخصومة للحالة التالية، بالمتوسط على السياسة وعلى البيئة.
معادلة بلمان للأمثلية تستبدل المتوسط على الأفعال بحدٍّ أقصى. وهي غير خطية، وحلّها V^* يجعل السلوك الأمثل نظرةً خطوةً واحدة إلى الأمام.
تكرار القيمة يمرّ بتحديث الأمثلية حتى التقارب؛ وتكرار السياسة يبادل بين تقييم مضبوط وتحسين جَشِع. وكلاهما برمجة بلمان الدينامية (1957)، وكلاهما يحتاج p.
لعنة الأبعاد عند بلمان هي سبب الثمن الحقيقي لتوسيع الحالة لاستعادة خاصية ماركوف، وسبب تراجع الطرائق الجدولية في النهاية أمام تقريب الدوال.