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मानों का अनुमान लगाने के लिए इसका उपयोग करें।

डीपी से एमसी में बदलाव दार्शनिक रूप से महत्वपूर्ण हैः हम ज्ञात मॉडल + सटीक बैकअप से सैंपल रोलआउट + औसत रिटर्न तक जाते हैं। भिन्नता कूदती है, लेकिन प्रयोज्यता विस्फोट होती है। इस पाठ के बाद प्रत्येक आरएल एल्गोरिथ्म टीडी, क्यू-लर्निंग, रीइनफोर्स, पीपीओ, जीआरपीओ एक मोन्टे कार्लो अनुमानक है, कभी-कभी ऊपर परतों पर बूटस्ट्रैपिंग के साथ।

अवधारणा

!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कई बार, पहली यात्रा एमसी केवल पहली यात्रा से वापसी की गणना करता है; प्रत्येक यात्रा एमसी सभी यात्राओं की गणना करता है। दोनों सीमा में निष्पक्ष हैं। पहली यात्रा का विश्लेषण करना आसान है (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.वर्तमान Q के साथ काम लोभी W.R.T. लेकिन संभावना के साथ εसभी राज्य-कार्य जोड़े असंबद्ध रूप से नमूना लिया जाता है।
Off-policy MC.व्यवहार नीति के अंतर्गत डेटा एकत्र करें μ, लक्ष्य नीति के बारे में जानें πमहत्व नमूनाकरण के माध्यम से। उच्च भिन्नता, लेकिन यह DQN की तरह रीप्ले-बफर तरीकों के लिए पुल है।

Monte Carlo Control.मूल्यांकन → सुधार → मूल्यांकन, नीति पुनरावृत्ति की तरह, लेकिन मूल्यांकन नमूना-आधारित हैः

दौड़ेंπ, एक एपिसोड प्राप्त करें.
अद्यतन Q(s, a)देखे गए रिटर्न से।
बनाओπ लालची w.r.t.Q. .
दोहराएँ।

Qऔर πहल्के परिस्थितियों में संभावना 1 के साथ (प्रत्येक जोड़ी अनंत बार दौरा किया,αरॉबिन्स-मोंरो को संतुष्ट करता है) ।

इसे बनाओ

चरण 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)जिम वातावरण के समान इंटरफ़ेस लेकिन नीचे उतार दिया गया।

चरण 2: गणना रिटर्न (रिवर्स स्वीप)

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}पुनः योग करने से बचता है।

चरण 3: पहली यात्रा के लिए एमसी मूल्यांकन

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

तीन पंक्तियाँ काम करती हैंः पहली यात्रा पर देखा गया राज्य चिह्नित करें, वृद्धि संख्या, अद्यतन चल रही औसत।

चरण 4: ई-लाभिचारी एमसी नियंत्रण (नीति पर)

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: डीपी स्वर्ण मानक की तुलना करें

आपके एमसी अनुमान V^πअभ्यास में: 4×4 ग्रिडवर्ल्ड पर 50,000 एपिसोड आपको अंदर ले जाता है ~0.1डीपी उत्तर का।

फंदे

Infinite episodes.MC एपिसोड की आवश्यकता है * समाप्त करने के लिए।max_stepsग्रिडवर्ल्ड के साथ एक यादृच्छिक नीति नियमित रूप से समय बाहर है, जो सामान्य है, बस सुनिश्चित करें कि आप इसे सही ढंग से गिनती.
Variance.MC पूर्ण रिटर्न का उपयोग करता है। लंबे एपिसोड पर, भिन्नता बहुत बड़ी है एक दुर्भाग्यपूर्ण पुरस्कार अंत शिफ्ट पर V(s_0)टीडी विधि (लर्सन 04) बूटस्ट्रेपिंग द्वारा इसे कम किया।
State coverage.एक ताजा Q के साथ लालची MC केवल एक ही कार्रवाई की कोशिश करेगा. आप must अन्वेषण (ε- लालची, अन्वेषण शुरू, UCB) ।
Non-stationary policies.यदिπएक बार जब एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक बार एक
Off-policy importance sampling.वजन π(a|s)/μ(a|s)एक पटरियों के पार गुणा करें। क्षितिज के साथ भिन्नता विस्फोट करती है। प्रति निर्णय भारित आईएस के साथ कैप या टीडी पर स्विच करें।

इसका प्रयोग करें

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.

आधुनिक गहरे आरएल एल्गोरिदम (पीपीओ, एसएसी) शुद्ध एमसी (पूर्ण रिटर्न) और शुद्ध टीडी (एक-चरण बूटस्ट्रैप) के बीच अंतर करते हैं।nदोनों अंत बिंदु एक ही अनुमानक के उदाहरण हैं।

इसे भेजें

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 ग्रिडवर्ल्ड पर वर्दी-एडजस्ट नीति के MC मूल्यांकन को पहली बार लागू करें। 10,000 एपिसोड चलाएं।V(0,0)डीपी उत्तर के खिलाफ एपिसोड गिनती के कार्य के रूप में।
Medium. के साथ ε-गामी MC नियंत्रण लागू करेंε ∈ {0.01, 0.1, 0.3}20,000 एपिसोड के बाद औसत रिटर्न की तुलना करें. वक्र कैसा दिखता है? पूर्वाग्रह-वियरिएंस ट्रेडऑफ कहां रहता है?
Hard.गैर-नीति MC को लागू करना महत्वपूर्ण नमूनाकरण के साथः एक समान-संदिग्ध नीति के तहत डेटा एकत्र करना μ, अनुमान V^πनिर्धारात्मक अनुकूल नीति के लिए π. सादे आईएस बनाम प्रति निर्णय आईएस बनाम वजन आईएस की तुलना करें. किसमें सबसे कम भिन्नता है?

प्रमुख शर्तें

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.

आगे पढ़ना

Sutton & Barto (2018). Ch. 5 — Monte Carlo Methods कैनोनिक उपचार।
Singh & Sutton (1996). Reinforcement Learning with Replacing Eligibility Traces पहली यात्रा बनाम हर यात्रा विश्लेषण।
Precup, Sutton, Singh (2000). Eligibility Traces for Off-Policy Policy Evaluation नीतिगत MC और भिन्नता नियंत्रण।
Mahmood et al. (2014). Weighted Importance Sampling for Off-Policy Learning आधुनिक कम-विविधता वाले आईएस अनुमानक।
Tesauro (1995). TD-Gammon, A Self-Teaching Backgammon Program MC/TD स्व-खेल का पहला बड़े पैमाने पर अनुभवजन्य प्रदर्शन सुपरमनुष्य खेल के लिए अभिसरण; इस चरण के दूसरे भाग में प्रत्येक पाठ के लिए अवधारणात्मक अग्रदूत।

This free lesson is part of the AI Engineering from Scratch curriculum. Read the full explanation, run the lesson code, and verify the result in the interactive reader or from the repository source.

Browse the complete course catalog or open this lesson on GitHub.