الوحدة 4 — البرمجة الديناميكية وطرائق مونت كارلو

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

البرمجة الديناميكية: تحسب لأنّها تعرف

عندما يكون MDP معلومًا بالكامل (كما في FrozenLake الذي كشفناه في الوحدة 2 عبر env.unwrapped.P)، تُحلّ معادلات بلمان مباشرة بالتكرار.

تكرار القيمة

نبدأ بتخصيص $V_0(s) = 0$ لكلّ الحالات، ونطبّق تحديث بلمان مرارًا:

$$V_{k+1}(s) \leftarrow \max_{a} \sum_{s', r} P(s', r \mid s, a) \left[ r + \gamma V_{k}(s') \right]$$

تُثبت النظريّة أنّ التتالي $V_k$ يتقارب إلى $V^{*}$ ما دام $\gamma < 1$. ومن $V^{*}$ نستخلص السياسة المُثلى بمرور واحد:

$$\pi^{*}(s) = \arg\max_{a} \sum_{s', r} P(s', r \mid s, a) \left[ r + \gamma V^{*}(s') \right]$$

import numpy as np

def iteration_valeur(env, gamma=0.99, seuil=1e-8):
    S, A = env.observation_space.n, env.action_space.n
    V = np.zeros(S)
    while True:
        V_nouveau = np.zeros(S)
        for s in range(S):
            V_nouveau[s] = max(
                sum(p * (r + gamma * V[s_prime]) for p, s_prime, r, _ in env.unwrapped.P[s][a])
                for a in range(A)
            )
        if np.max(np.abs(V_nouveau - V)) < seuil:
            break
        V = V_nouveau
    politique = np.zeros(S, dtype=int)
    for s in range(S):
        politique[s] = np.argmax([
            sum(p * (r + gamma * V[s_prime]) for p, s_prime, r, _ in env.unwrapped.P[s][a])
            for a in range(A)
        ])
    return V, politique

تكرار السياسة

بديل يتكوّن من مرحلتين متعاقبتين حتّى الاستقرار:

1. تقييم السياسة: احسب $V^{\pi}$ للسياسة الحاليّة بحلّ بلمان للتوقّع (نظام خطّي أو تكرار).
2. تحسين السياسة: كوّن سياسة جديدة جشعة تجاه $V^{\pi}$ الحالي.

تكرار السياسة يتقارب في عدد أصغر من التكرارات عادةً، لكنّ كلّ تكرار أغلى (يشمل تقييمًا كاملًا). في الممارسة يُستخدم تكرار السياسة المُعمَّم الذي يمزج بين قليل من التقييم وقليل من التحسين — كلّ خوارزميّات لاحقة (تعلّم Q، ممثّل-ناقد) هي تجسّدات لهذا المزج.

متى ينهار كلّ ذلك

اثنان من افتراضات البرمجة الديناميكية غير قابلين للتحقّق في العالم الحقيقي:

• نموذج معلوم: نادرًا ما يتوفّر $P$ صراحة. في الروبوتيّات، وألعاب أتاري، والقيادة الذاتيّة، لا نستطيع كتابة $P(s' \mid s, a)$ رياضيًّا.
• جدول قابل للتخزين: FrozenLake 16 حالة. Atari مليار حالة (بكسلات). لا جدول $V$ يسع الملياريّات.

هذان القيدان يفسّران انتقالنا نحو مونت كارلو (بلا نموذج) ثمّ نحو الشبكات العصبيّة (بلا جدول). البرمجة الديناميكية تظلّ مع ذلك مفهومًا مركزيًّا: هي المرجع الذي نُقاس عليه.

مونت كارلو: يتعلّم من الحلقات

عندما لا نعرف $P$، نستبدل التوقّع بالمتوسّط التجريبي على حلقات كاملة. ندع الوكيل يلعب حلقة، ثمّ نحسب العائد الفعلي $G_t$ عند كلّ حالة، ونُعدّل التقدير:

$$V(s) \leftarrow V(s) + \alpha \left[ G_t - V(s) \right]$$

بمعامل تعلّم $\alpha$ ثابت أو متناقص. للـ$Q$:

$$Q(s, a) \leftarrow Q(s, a) + \alpha \left[ G_t - Q(s, a) \right]$$

الفارق الأساسي مع البرمجة الديناميكية: لا نبوت‌سترابنغ. نحسب $G_t$ من الرجعة الفعليّة، ولا نستعمل تقديرًا حاليًّا لحالة أخرى. النتيجة: تقدير غير متحيّز، لكن بتباين ضخم.

تباين العائدات

سبب تباين مونت كارلو الكبير مباشر: $G_t$ يعتمد على كلّ خيار الوكيل وكلّ صدفة البيئة من $t$ إلى نهاية الحلقة. كلّ عشوائيّة إضافيّة في السبيل تضاف إلى تباين $G_t$.

مثال ملموس: على FrozenLake بـis_slippery=True، حتّى مع السياسة المُثلى قد يفقد الوكيل حلقات كاملة بسبب الانزلاق. عائد حلقة قد يكون $0$ (سقط في ثقب) أو $\gamma^{10} \approx 0{,}9$ (وصل بعد 10 خطوات) — تباين هائل من حلقة لأخرى.

النتائج العمليّة:

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

المقارنة الجوهريّة

	البرمجة الديناميكية	مونت كارلو
نموذج $P$	مطلوب	غير مطلوب
بوت‌سترابنغ	نعم	لا
متحيّز؟	حسب التقارب	لا (على الأصل)
تباين	منخفض	مرتفع
مسائل مستمرّة	ممكن	لا (يلزم حلقات)
حجم الحالة	صغير (جداول)	متوسّط

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

فخّ التنفيذ

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

الخلاصة

• البرمجة الديناميكية تحلّ MDP معلومًا بالبوت‌سترابنغ (تكرار القيمة أو تكرار السياسة)؛ سريعة لكن تفترض معرفة $P$ وجدول صغير.
• مونت كارلو لا يفترض نموذجًا؛ يستخدم العائدات الفعلية من حلقات كاملة، وينتج تقديرًا غير متحيّز لكن بتباين مرتفع.
• تباين مونت كارلو يجعل التقارب بطيئًا ويحدّه بالمسائل الحلقيّة.
• المقارنة المفتاحيّة: مع/بلا نموذج، ومع/بلا بوت‌سترابنغ، هما محورا القرار.

الوحدة التالية: الفرق الزمنى وتعلّم Q، الذي يجمع بين لا-نموذج مونت كارلو وبوت‌سترابنغ بلمان، فيولد الخوارزميّة الأشهر في التعلّم المعزّز التبويبي.