Markov Decision Process (MDP)

عملية اتخاذ القرار ماركوفية (MDP) هي النموذج الرياضي لمسألة اتخاذ قرارات متتابعة: يلاحظ الوكيل حالة، ويختار إجراءً، ويتلقى مكافأة، ثم ينتقل إلى حالة تالية تعتمد جزئيًا على اختياره وجزئيًا على الصدفة. وتتكون MDP رسميًا من مجموعة حالات، ومجموعة إجراءات، واحتمالات انتقال P(s′ | s, a)، ودالة مكافأة R(s, a)، وعامل خصم γ بين 0 و1 عادةً. ويعني حلها العثور على سياسة، أي قاعدة تختار إجراءً في كل حالة، لتعظيم المجموع المتوقع للمكافآت المستقبلية المخصومة. نشأت MDPs في بحوث العمليات خلال خمسينيات القرن العشرين، حيث وفّر البرمجة الديناميكية لريتشارد بيلمان أساليب حلها، وهي الصياغة القياسية لمسائل التعلّم المعزز (RL).

خاصية ماركوف#

الافتراض الأساسي هو خاصية ماركوف: تعتمد الحالة والمكافأة التاليتان على الحالة الحالية والإجراء الحالي فقط، لا على المسار الذي أفضى إليهما. وهذا يجعل الحالة ملخصًا كاملًا لكل ما يهم الوكيل. ولا يفي إطار كاميرا واحد بهذا الافتراض عند تتبع جسم متحرك، لأنه يبيّن موضع الجسم لا سرعته؛ لذلك أدخلت شبكة DQN التي طورتها DeepMind للعب Atari آخر أربعة إطارات مكدّسة معًا لتمكينها من رؤية الحركة.

عندما يتعذر على الوكيل رصد الحالة كاملة، كما يحدث مع روبوت تكون مستشعراته مشوشة أو محجوبة، تصبح المسألة عملية اتخاذ قرار ماركوفية جزئية الرصد (POMDP). عندئذٍ يتصرف الوكيل بناءً على اعتقاد بشأن الحالة، يُحدّث باستخدام مرشّح أو شبكة متكررة، بدلًا من التصرف بناءً على الحالة نفسها.

مكوّنات عملية اتخاذ القرار الماركوفية#

• الحالات: الأوضاع التي يمكن أن يكون الوكيل فيها، مثل زوايا مفاصل الروبوت وموضع الجسم الذي يحاول الوصول إليه.
• الإجراءات: الخيارات المتاحة في كل حالة. ويمكن أن يكون فضاء الإجراءات متقطعًا (انعطف يسارًا، انعطف يمينًا) أو مستمرًا (زاوية توجيه بالدرجات).
• احتمالات الانتقال: احتمال الوصول إلى كل حالة تالية بعد إجراء ما، وتشمل هذه الاحتمالات انزلاق العجلات والسائقين الآخرين وكل مصدر آخر للعشوائية.
• المكافآت: التغذية الراجعة الرقمية الفورية للانتقال. ويحدد اختيار المصمم للمكافآت المهمة، وقد يؤدي الاختيار غير المدروس إلى التحايل على المكافآت.
• عامل الخصم: مقدار احتساب المكافآت المستقبلية مقارنةً بالمكافآت الفورية. عند γ = 0.9، تساوي المكافأة التي تأتي بعد عشر خطوات 0.9¹⁰ ≈ 0.35 من قيمة المكافأة نفسها الآن.

يتكرر التفاعل نفسه في كل خطوة زمنية إلى أن تنتهي الحلقة:

حل عملية اتخاذ القرار الماركوفية#

قيمة الحالة هي العائد المتوقع منها وفق سياسة معينة، وتحقق القيم المثلى معادلة بيلمان: تساوي قيمة كل حالة المكافأة الفورية لأفضل إجراء مضافًا إليها القيمة المخصومة والمرجّحة بالاحتمالات للحالات التي يؤدي إليها. وعندما تكون احتمالات الانتقال والمكافآت معلومة، تحل البرمجة الديناميكية هذه المعادلة مباشرةً. تطبّق خوارزمية تكرار القيم (Bellman، 1957) المعادلة مرارًا إلى أن تتوقف القيم عن التغير، بينما تتناوب خوارزمية تكرار السياسات (Howard، 1960) بين تقييم سياسة وتحسينها.

يشغّل مثال NumPy هذا تكرار القيم على روبوت إعادة التدوير الوارد في كتاب التعلّم المعزز: مقدمة لـSutton وBarto؛ إذ يتعين على الروبوت الاختيار بين البحث عن العلب والانتظار وإعادة الشحن عندما تكون البطارية مشحونة أو منخفضة:

import numpy as np

# ⁨عملية اتخاذ القرار الماركوفية لروبوت إعادة التدوير: الحالات 0 = بطارية مشحونة، 1 = بطارية منخفضة؛ الإجراءات 0 = بحث، 1 = انتظار، 2 = إعادة شحن⁩
gamma = 0.9  # ⁨عامل الخصم⁩
P = np.zeros((2, 3, 2))  # ⁨P[s, a, s'] = احتمال الوصول إلى s' بعد تنفيذ a في s⁩
P[0, 0] = [0.7, 0.3]  # ⁨قد يؤدي البحث مع بطارية مشحونة إلى انخفاض شحنها⁩
P[1, 0] = [0.4, 0.6]  # ⁨قد يؤدي البحث مع بطارية منخفضة إلى نفاد شحنها (يُنتشل الروبوت ويُعاد شحنه)⁩
P[:, 1] = np.eye(2)  # ⁨يحافظ الانتظار على مستوى البطارية دون تغيير⁩
P[:, 2] = [1.0, 0.0]  # ⁨تعيد إعادة الشحن البطارية دائمًا إلى مستوى الشحن الكامل⁩
R = np.array([[2.0, 1.0, 0.0], [0.0, 1.0, 0.0]])  # ⁨القيمة المتوقعة لـ R[s, a]؛ البحث ببطارية منخفضة: 0.6 * 2 + 0.4 * -3 = 0⁩

# ⁨تكرار القيم: تطبيق تحديث أمثلية بيلمان إلى أن تتوقف القيم عن التغير⁩
V = np.zeros(2)
for _ in range(500):
    Q = R + gamma * P @ V  # ⁨قيمة كل إجراء في كل حالة⁩
    V = Q.max(axis=1)

actions = ["search", "wait", "recharge"]
print("Optimal values:", V.round(2))
print("Optimal policy:", {s: actions[a] for s, a in zip(["high", "low"], Q.argmax(axis=1))})

يطبع البرنامج قيمًا تبلغ 15.75 للبطارية المشحونة و14.17 للبطارية المنخفضة، وسياسةً تقضي بالبحث عند شحن البطارية وإعادة شحنها عندما ينخفض مستواها: فاحتمال 40% لفرض غرامة إنقاذ قدرها −3 يجعل البحث ببطارية منخفضة أقل جدوى من إعادة الشحن.

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

عمليات اتخاذ القرار الماركوفية مقارنةً بالنماذج المرتبطة بها#

• سلسلة ماركوف: سلسلة من الحالات العشوائية دون إجراءات أو مكافآت. وتضيف عملية اتخاذ القرار الماركوفية الخيارات والهدف.
• نموذج ماركوف المخفي (HMM): سلسلة ماركوف لا تُرصد حالاتها إلا عبر إشارات مشوشة. وترتبط عملية اتخاذ القرار الماركوفية جزئية الرصد بعملية اتخاذ القرار الماركوفية على النحو نفسه.
• مسألة الأذرع المتعددة: عملية اتخاذ قرار ماركوفية ذات حالة واحدة، حيث يحقق كل إجراء عائدًا مستقلًا عن الماضي.
• التعلّم المعزز: مجموعة الأساليب التي تتعلم التصرف بفعالية في عملية اتخاذ قرار ماركوفية من خلال التفاعل، دون تزويدها باحتمالات الانتقال.

التطبيقات#

• الروبوتات والتحكم: تُصاغ مهام الإمساك والمشي والتنقل على هيئة عمليات اتخاذ قرار ماركوفية، وغالبًا ما تُدرّب سياساتها في المحاكاة. وفي التحكم المعتمد على الكاميرا، يستطيع كاشف مثل Ultralytics YOLO26 توفير الحالة، محولًا كل إطار إلى قائمة قصيرة من فئات الأجسام وإحداثيات الصناديق، وهي مدخلات أصغر بكثير للسياسة من وحدات البكسل الخام.
• تدريب النماذج اللغوية: يتعامل RLHF وRLVR مع توليد النص بوصفه عملية اتخاذ قرار ماركوفية تكون حالتها هي الموجّه مضافًا إليه الرموز المُنتجة حتى الآن، وإجراؤها هو الرمز التالي، ومكافأتها تصل عند اكتمال الاستجابة.
• بحوث العمليات: تُعد إعادة طلب المخزون وصيانة المعدات والتسعير الديناميكي مسائل كلاسيكية لعمليات اتخاذ القرار الماركوفية، وقد طوّر رونالد هوارد تكرار السياسات أثناء تحسين إرسال كتالوجات Sears بالبريد.