Phase 09: Reinforcement Learning

أساليب مونت كارلو تعلم من الحلقات الكاملة

البرمجة الديناميكية تحتاج إلى نموذج. مونت كارلو لا تحتاج سوى الحلقات. تشغيل السياسة، مشاهدة العائدات، متوسطها. الأسهل فكرة في RL والتي تفتح كل شيء أسفل التيار.

Type: Build

Languages: Python

Prerequisites: Phase 9 · 01 (MDPs), Phase 9 · 02 (Dynamic Programming)

Time: ~75 minutes

المشكلة

البرمجة الديناميكية هي جميلة، ولكن يفترض أنه يمكنك استفسارP(s' | s, a)لا يمكن للروبوت تحليلًا لتوزيع بيكسلات الكاميرا بعد محركة مشتركة. لا يمكن ل خوارزمية التسعير أن تتكامل مع كل رد فعل محتمل للعميل. لا يمكن لشركة التسليم المختلف للاستمرار في جميع المواصلات الممكنة بعد رمز.

تحتاج إلى طريقة لا تحتاج إلا إلى القدرة على أخذ عينات من البيئة. تنفيذ السياسة. الحصول على مسارs_0, a_0, r_1, s_1, a_1, r_2, …, s_Tاستخدمها لتقدير القيم هذا مونت كارلو

التحول من DP إلى MC مهم فلسفيا: نقوم بالانتقال من النموذج المعروف + النسخة الاحتياطية الدقيقة إلى التنفيذات المعدنية + العائد المتوسط . يرتفع التباين ، ولكن التطبيق يتفجر. كل خوارزمية RL بعد هذه الدروس TD ، Q-learning ، REINFORCE ، PPO ، GRPO هي تقدير مونت كارلو في قلبها ، في بعض الأحيان مع إطلاق التطبيقات على الطوابق فوق.

المفهوم

!Monte Carlo: rollout, compute returns, average; first-visit vs every-visit

The core idea, in one line: V^π(s) = E_π[G_t | s_t = s] ≈ (1/N) Σ_i G^{(i)}(s)أينG^{(i)}(s)تُلاحظ العوائد بعد زيارات sفي سياسةπ. . .

First-visit vs every-visit MC.نظراً للفصل الذي يزور الولايةsفي العديد من المرات، MC الزيارة الأولى تعتبر فقط العودة من الزيارة الأولى؛ كل زيارة MC تعتبر جميع الزيارات. كلاهما غير متحيز في الحد. الزيارة الأولى أسهل لتحليل (معاكرات iid). كل زيارة تستخدم المزيد من البيانات لكل حلقة وعادة ما تتقارب أسرع في الممارسة.

Incremental mean.بدلاً من تخزين جميع العائدات، قم بتحديث المتوسط التشغيلي:

V_n(s) = V_{n-1}(s) + (1/n) [G_n - V_{n-1}(s)]

إعادة تنظيم: V_new = V_old + α · (target - V_old)معα = 1/n. تغيير1/nلـ (حجم خطوة ثابت)α ∈ (0, 1)و تحصل على مقياس MC غير ثابت الذي يتبع التغيرات فيπهذه الخطوة هي قفزة كاملة من MC إلى TD إلى كل خوارزمية RL الحديثة.

Exploration is now a problem.و"دي بي" لمست كل ولاية من خلال الإحصاءات، و"إم سي" ترى فقط الدول الزيارات السياسية.πإنّها تحديدية، لا يتمّ أخذ عينات على مناطق كاملة من مساحة الدولة، وتقديرات قيمتها تبقى عند الصفر إلى الأبد.

Exploring starts.تبدأ كل حلقة من زوج عشوائي (ات) يضمن تغطية؛ غير واقعي في الممارسة العملية (لا يمكنك "إعادة تعيين" الروبوت إلى حالة تعسفية).
ε-greedy.تصرف طمعية في ق ق الحالي، ولكن مع احتمالεاختر عمل عشوائي جميع أزواج الحالة يتم أخذ عينات بشكل غير متزامن
Off-policy MC.جمع البيانات بموجب سياسة السلوكμ، تعلم عن السياسة المستهدفةπالاختلافات عالية، ولكنها هي الجسر إلى طرق التعبير مثل DQN

Monte Carlo Control.تقييم → تحسين → تقييم، تماما مثل التكرار السياسي، ولكن التقييم يعتمد على أخذ العينات:

أركضπ، احصل على حلقة.
تحديث Q(s, a)من العائدات الملاحظة
- أفعلهاπالـ طمعQ. . .
أكرر

يتحرك إلىQوπمع احتمال 1 في ظروف خفيفة (كل زوج زيارة في كثير من الأحيان ،αيرضي (روبينز مونرو)

بناءها

الخطوة الأولى: الإرسال → قائمة (s، a، r)

pythondef rollout(env, policy, max_steps=200):
    trajectory = []
    s = env.reset()
    for _ in range(max_steps):
        a = policy(s)
        s_next, r, done = env.step(s, a)
        trajectory.append((s, a, r))
        s = s_next
        if done:
            break
    return trajectory

لا نموذج، فقطenv.reset()وenv.step(s, a)نفس الواجهة مثل بيئة رياضية ولكن تم تجريدها

الخطوة الثانية: إرجاع الحساب (التصفية العكسية)

pythondef returns_from(trajectory, gamma):
    returns = []
    G = 0.0
    for _, _, r in reversed(trajectory):
        G = r + gamma * G
        returns.append(G)
    return list(reversed(returns))

مرّة واحدة،O(T)التكرار الراجعG_t = r_{t+1} + γ G_{t+1}يتجنب إعادة جمع.

الخطوة الثالثة: تقييم المملكة العربية المتحدة في الزيارة الأولى

pythondef mc_policy_evaluation(env, policy, episodes, gamma=0.99):
    V = defaultdict(float)
    counts = defaultdict(int)
    for _ in range(episodes):
        trajectory = rollout(env, policy)
        returns = returns_from(trajectory, gamma)
        seen = set()
        for t, ((s, _, _), G) in enumerate(zip(trajectory, returns)):
            if s in seen:
                continue
            seen.add(s)
            counts[s] += 1
            V[s] += (G - V[s]) / counts[s]
    return V

ثلاث خطوط تقوم بالعمل: علامة حالة كما هو مرر على الزيارة الأولى، عدد الزيادة، تحديث متوسط التشغيل.

الخطوة الرابعة: إضفاء الضوابط على المجموعة المتحركة (على السياسة)

pythondef mc_control(env, episodes, gamma=0.99, epsilon=0.1):
    Q = defaultdict(lambda: {a: 0.0 for a in ACTIONS})
    counts = defaultdict(lambda: {a: 0 for a in ACTIONS})

    def policy(s):
        if random() < epsilon:
            return choice(ACTIONS)
        return max(Q[s], key=Q[s].get)

    for _ in range(episodes):
        trajectory = rollout(env, policy)
        returns = returns_from(trajectory, gamma)
        seen = set()
        for (s, a, _), G in zip(trajectory, returns):
            if (s, a) in seen:
                continue
            seen.add((s, a))
            counts[s][a] += 1
            Q[s][a] += (G - Q[s][a]) / counts[s][a]
    return Q, policy

الخطوة 5: مقارنة مع معيار الذهب DP

تقديرات المجلس الوطنيV^πيجب أن توافق مع نتيجة DP من الدروس 02 كحلقات → ∞. في الممارسة العملية: 50,000 حلقة على 4×4 GridWorld يجعلك في غضون ~0.1من إجابة DP.

الفخاخ

Infinite episodes.إن كان سياستك يمكن أن تكون دائمة للأبد، فليكن ذلك صحيحاًmax_stepsواعتبروا أنّه فشل ضمني، وذلك أمر طبيعي، فقط تأكد من احتسابها بشكل صحيح.
Variance.الموسيقى تستخدم العائدات الكاملة في الحلقات الطويلة، الاختلاف هائل مكافأة واحدة غير محظوظة في نهاية النقبات V(s_0)وذلك في نفس المبلغ. أساليب التد (دروس 04) خفض هذا عن طريق إطلاق.
State coverage.الموسيقي الطمأنسي على ق جديد مع العلاقات سوف تجرب فقط عمل واحد يجب عليك استكشاف (ε-طمأنسي، استكشاف بدايات، UCB).
Non-stationary policies.إذاπتغيرات (كما هو الحال في مراقبة MC) ، العائدات القديمة هي من سياسة مختلفة.
Off-policy importance sampling.الوزنπ(a|s)/μ(a|s)يضاعف عبر مسار. ينفجر التباين مع الأفق. القيادة مع IS الموزن لكل قرار أو الانتقال إلى TD.

استخدمها

دور أساليب مونت كارلو لعام 2026:

Use case	Why MC
Short-horizon games (blackjack, poker)	Episodes terminate naturally; returns are clean.
Offline evaluation of a logged policy	Average discounted returns over stored trajectories.
Monte Carlo Tree Search (AlphaZero)	MC rollouts from tree leaves guide selection.
LLM RL evaluation	Compute average reward over sampled completions for a given policy.
Baseline estimation in PPO	The advantage target `A_t = G_t - V(s_t)` uses an MC `G_t`.
Teaching RL	Simplest algorithm that actually works — strip bootstrapping to see the core.

الخوارزميات الحديثة للخلفية العميقة (PPO، SAC) تتقاطع بين MC (العائد الكامل) و TD (الخطوة الواحدة من التشغيل)n-المستويات الخطوة أو GAE. كلا النقاط النهائية هي حالات من نفس المقدرة.

أرسله

إبقواoutputs/skill-mc-evaluator.md:

markdown---
name: mc-evaluator
description: Evaluate a policy via Monte Carlo rollouts and produce a convergence report with DP-comparison if available.
version: 1.0.0
phase: 9
lesson: 3
tags: [rl, monte-carlo, evaluation]
---

Given an environment (episodic, with reset+step API) and a policy, output:

1. Method. First-visit vs every-visit MC. Reason.
2. Episode budget. Target number, variance diagnostic, expected standard error.
3. Exploration plan. ε schedule (if needed) or exploring starts.
4. Gold-standard comparison. DP-optimal V* if tabular; otherwise a bound from a Q-learning / PPO baseline.
5. Termination check. Max-step cap, timeouts, handling of non-terminating trajectories.

Refuse to run MC on non-episodic tasks without a finite horizon cap. Refuse to report V^π estimates from fewer than 100 episodes per state for tabular tasks. Flag any policy with zero-variance actions as an exploration risk.

التمارين

Easy.تنفيذ تقييم الممثلين في الزيارة الأولى لسياسة التعرض العشوائي الموحد على 4 × 4 GridWorld. تشغيل 10،000 حلقة.V(0,0)كعمل على عدد الحلقات مقابل إجابة DP.
Medium.تنفيذ التحكم في الـ " MC " الفطري معε ∈ {0.01, 0.1, 0.3}مقارنة معدل العودة بعد 20000 حلقة كيف يبدو منحنى؟ أين يعيش التداول بين التباينات والتحيزات؟
Hard.تنفيذ خارج السياسة MC مع أخذ العينات المهمة: جمع البيانات في إطار سياسة متساوية متساوية μ، تقدير V^πلسياسة التحديد المثلىπ. مقارنة IS بسيطة مقابل IS لكل قرار مقابل IS الموزن

الشروط الرئيسية

Term	What people say	What it actually means
Monte Carlo	"Random sampling"	Estimate expectations by averaging over iid samples from the distribution.
Return `G_t`	"Future reward"	Sum of discounted rewards from step `t` to episode end: `Σ_{k≥0} γ^k r_{t+k+1}`.
First-visit MC	"Count each state once"	Only the first visit in an episode contributes to the value estimate.
Every-visit MC	"Use all visits"	Every visit contributes; slightly biased but more sample-efficient.
ε-greedy	"Exploration noise"	Pick greedy action with prob `1-ε`; random action with prob `ε`.
Importance sampling	"Correcting for sampling from the wrong distribution"	Reweight returns by `π(a\|s)/μ(a\|s)` products to estimate `V^π` from `μ` data.
On-policy	"Learn from my own data"	Target policy = behavior policy. Vanilla MC, PPO, SARSA.
Off-policy	"Learn from someone else's data"	Target policy ≠ behavior policy. Importance-sampled MC, Q-learning, DQN.