Phase 09: Reinforcement Learning

Phương pháp Monte Carlo Học hỏi từ các tập hoàn chỉnh

Type: Build

Languages: Python

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

Time: ~75 minutes

Vấn đề

Quá trình lập trình năng động là thanh lịch, nhưng nó cho rằng bạn có thể truy vấn P(s' | s, a)Một robot không thể tính toán phân phối trên các pixel máy ảnh theo một mô-men xoắn chung. Một thuật toán định giá không thể tích hợp trên mọi phản ứng khách hàng có thể. Một LLM không thể liệt kê tất cả các tiếp tục có thể sau một token.

Bạn cần một phương pháp mà chỉ cần khả năng mặt mẫu từ môi trường.s_0, a_0, r_1, s_1, a_1, r_2, …, s_T- Sử dụng nó để ước tính giá trị.

Sự chuyển đổi từ DP sang MC là triết học quan trọng: chúng ta chuyển từ mô hình được biết + sao lưu chính xác sang triển khai mẫu + lợi nhuận trung bình . Sự khác biệt nhảy vọt, nhưng tính áp dụng nổ. Mỗi thuật toán RL sau bài học này TD, Q-learning, REINFORCE, PPO, GRPO là một ước tính Monte Carlo ở cốt lõi, đôi khi với bootstrapping được layered trên.

Khái niệm

!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)nơi G^{(i)}(s)được quan sát về những lần thăm strong chính sáchπ- Tôi không biết.

First-visit vs every-visit MC.Với một tập phim đến thăm tiểu bang snhiều lần, lần đầu tiên MC chỉ tính toán sự trở lại từ lần đầu tiên; mỗi lần truy cập MC tính tất cả các chuyến thăm. Cả hai đều không thiên vị trong giới hạn. lần đầu tiên dễ phân tích hơn (iid mẫu). Mỗi lần truy cập sử dụng nhiều dữ liệu hơn cho mỗi tập và thường hội tụ nhanh hơn trong thực tế.

Incremental mean.Thay vì lưu trữ tất cả các thông tin trả lại, cập nhật trung bình chạy:

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

Tái tổ chức: V_new = V_old + α · (target - V_old)với α = 1/n- Thay đổi1/ncho một bước kích thước liên tục α ∈ (0, 1)và bạn có một máy ước tính MC không tĩnh mà theo dõi thay đổi trong πChuyển động đó là toàn bộ bước từ MC đến TD đến mọi thuật toán RL hiện đại.

Exploration is now a problem.DP đã chạm vào mọi tiểu bang bằng cách đếm. MC chỉ nhìn thấy các tiểu bang các chuyến thăm chính sách. Nếuπlà xác định, toàn bộ khu vực trong không gian nhà nước không bao giờ được lấy mẫu, và ước tính giá trị của chúng vẫn ở mức không mãi mãi.

1. Exploring starts.Bắt đầu mỗi tập từ một cặp ngẫu nhiên (s, a). Giảm bảo bảo hiểm; không thực tế trong thực tế (bạn không thể "đưa lại" một robot vào trạng thái tùy tiện).
2. ε-greedy.Tạo hành tham lam với Q hiện tại, nhưng với khả năngεchọn một hành động ngẫu nhiên. tất cả các cặp hành động trạng thái được lấy mẫu theo cách không đồng nghĩa.
3. Off-policy MC.Thu thập dữ liệu theo chính sách hành vi μ, tìm hiểu về chính sách mục tiêu πSự khác biệt cao, nhưng nó là cầu nối với các phương pháp buffer như DQN.

Monte Carlo Control.Đánh giá → cải thiện → đánh giá, giống như lặp lại chính sách, nhưng đánh giá dựa trên mẫu:

1. Đi chạyπ, lấy một tập phim.
2. Tới thiệu Q(s, a)từ những kết quả được quan sát.
3. Làm πε-cái tham lam w.r.t. Q- Tôi không biết.
4. Lặp lại.

Tương ứng với Qvà πvới xác suất 1 trong điều kiện nhẹ (mỗi cặp được truy cập vô hạn thường xuyên,αlàm hài lòng Robbins-Monro).

Hãy xây dựng nó

Bước 1: rollout → danh sách (s, a, r)

pythonCopydef 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

Không có mô hình, chỉ là env.reset()và env.step(s, a)- Giống như môi trường tập thể dục nhưng không được trang bị.

Bước 2: trả lại tính toán (tránh ngược)

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

Một lần đi qua.O(T)Sự tái phát ngược lạiG_t = r_{t+1} + γ G_{t+1}tránh tổng hợp lại.

Bước 3: đánh giá MC lần đầu tiên

pythonCopydef 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

Ba dòng làm việc: đánh dấu trạng thái như được nhìn thấy trong chuyến thăm đầu tiên, số lượng tăng, trung bình chạy cập nhật.

Bước 4: kiểm soát MC tham lam (trong chính sách)

pythonCopydef 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

Bước 5: so sánh với tiêu chuẩn vàng DP

Đánh giá của MC của bạn vềV^πnên đồng ý với kết quả DP từ Bài học 02 như các tập → ∞. Trong thực tế: 50.000 tập trên 4×4 GridWorld đưa bạn trong ~0.1của câu trả lời DP.

Những bẫy

• Infinite episodes.MC cần các tập phim để chấm dứt. Nếu chính sách của bạn có thể lặp mãi mãi, cap max_stepsvà coi nắp như thất bại ngầm. GridWorld với một chính sách ngẫu nhiên thường xuyên thời gian ra đó là bình thường, chỉ cần đảm bảo bạn đếm nó đúng.
• Variance.MC sử dụng hoàn toàn trả lại. Trong các tập dài, sự khác biệt là rất lớn một phần thưởng không may ở cuối các phiên V(s_0)Các phương pháp TD (Lớp 04) cắt giảm điều này bằng cách khởi động.
• State coverage.MC tham lam trên một Q mới với dây xích sẽ chỉ thử một hành động.
• Non-stationary policies.Nếuπ(như trong kiểm soát MC), các khoản trả lại cũ là từ một chính sách khác.
• Off-policy importance sampling.Những trọng lượng π(a|s)/μ(a|s)Tăng bằng đường đi, biến động nổ với chân trời, giới hạn với IS/phát quyết hoặc chuyển sang TD.

Sử dụng nó

Vai trò của phương pháp Monte Carlo năm 2026:

Các thuật toán sâu-RL hiện đại (PPO, SAC) liên kết giữa MC tinh khiết (cũng trả lại) và TD tinh khiết (một bước khởi động) thông qua n- bước trở lại hoặc GAE. Cả hai điểm cuối là các trường hợp của ước tính tương tự.

Chuyển nó

Cứ như outputs/skill-mc-evaluator.md- Có thể là:

markdownCopy---
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.

Các bài tập

1. Easy.Thực hiện đánh giá MC lần đầu tiên về chính sách đồng bộ ngẫu nhiên trên 4×4 GridWorld.V(0,0)như một hàm số tập so với câu trả lời DP.
2. Medium.Thực hiện kiểm soát MC tham lam với ε ∈ {0.01, 0.1, 0.3}So sánh mức thu hồi trung bình sau 20.000 tập.
3. Hard.Thực hiện các MC ngoài chính sách với việc lấy mẫu quan trọng: thu thập dữ liệu theo chính sách ngẫu nhiên đồng nhất μ, ước tínhV^πcho chính sách tối ưu định nghĩa πSo sánh IS đơn giản so với IS theo quyết định so với IS trọng lượng.

Các điều khoản chính

Đọc thêm

• Sutton & Barto (2018). Ch. 5 — Monte Carlo Methods điều trị theo luật pháp.
• Singh & Sutton (1996). Reinforcement Learning with Replacing Eligibility Traces lần đầu tiên và mỗi lần thăm.
• Precup, Sutton, Singh (2000). Eligibility Traces for Off-Policy Policy Evaluation MC và kiểm soát biến động ngoài chính sách.
• Mahmood et al. (2014). Weighted Importance Sampling for Off-Policy Learning Máy ước tính IS hiện đại có biến thể thấp.
• Tesauro (1995). TD-Gammon, A Self-Teaching Backgammon Program sự chứng minh thực nghiệm quy mô lớn đầu tiên của MC/TD tự chơi hội tụ với trò chơi siêu nhân; tiền thân khái niệm cho mỗi bài học trong nửa sau của giai đoạn này.

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.