Monte Carlo methods — অভিজ্ঞতা থেকে শেখা

১ · Why MC — DP-এর সীমা

Value iteration, policy iteration — দু'টোই $P, R$ require করে। বাস্তব problem-এ ($P, R$ unknown):

• Robot — physics complete model নেই।
• Game — opponent unknown।
• Recommendation — user behavior model নেই।

MC সমাধান — episode চালিয়ে অভিজ্ঞতা থেকে শেখা।

২ · First-visit MC prediction

Algorithm:

1. Initialize $V(s) = 0$, $Returns(s) = []$ ∀$s$।
2. প্রতি episode generate: $s_0, a_0, r_1, s_1, \ldots, s_T$।
3. প্রতিটি state $s$-এর first occurrence-এ — return $G$ compute, append to $Returns(s)$।
4. $V(s) = \text{mean}(Returns(s))$।

৩ · Every-visit MC

First-visit only first occurrence count করে। Every-visit — প্রতিটি occurrence count। Subtle:

• First-visit: unbiased estimator।
• Every-visit: biased কিন্তু consistent (sample বাড়লে → true)।
• Practical-এ — every-visit সাধারণত more sample-efficient।

৪ · Incremental update

Sample list রাখা memory-costly। Running mean:

$$V_n(s) = V_{n-1}(s) + \frac{1}{n}[G - V_{n-1}(s)]$$

বা constant step:

$$V(s) \leftarrow V(s) + \alpha [G - V(s)]$$

$\alpha$ constant হলে — non-stationary tracking সম্ভব।

৫ · Python — first-visit MC prediction

import numpy as np
from collections import defaultdict

# Toy: 5-state random walk
# s_0 - s_1 - s_2 - s_3 - s_4 (terminal +1)
# random walk policy
n_states = 5
gamma = 1.0  # episodic, terminal +1

def episode():
    s = 2  # start middle
    traj = []
    while s not in [0, 4]:
        a = np.random.choice([-1, 1])
        s_next = s + a
        r = 1.0 if s_next == 4 else 0.0
        traj.append((s, r))
        s = s_next
    return traj

V = np.zeros(n_states)
returns = defaultdict(list)
np.random.seed(0)

for _ in range(5000):
    traj = episode()
    G = 0
    visited = set()
    # backward through trajectory
    for (s, r) in reversed(traj):
        G = r + gamma * G
        if s not in visited:  # first-visit
            returns[s].append(G)
            visited.add(s)

for s in range(1, 4):
    V[s] = np.mean(returns[s])

print("First-visit MC V estimate:")
for s in range(n_states):
    print(f"  V({s}) = {V[s]:.3f}")
# True values: 1/4, 2/4, 3/4 — analytical solution.

৬ · MC control — Q estimation

$V$ থেকে policy বের করা যায় না (model-free)। তাই $Q$ estimate করতে হবে। MC control:

1. Episode generate using current $\pi$।
2. Each (s, a) first-visit-এ — $G$ compute, $Q(s, a)$ update।
3. $\pi$ improve: $\pi(s) = \arg\max_a Q(s, a)$।

সমস্যা: greedy improvement-এ — কিছু (s, a) কখনো sampled হয় না। এই জন্য:

৭ · Exploring starts ও ε-soft policies

Exploring starts (ES): initial state ও action uniformly random। তত্ত্বে কাজ করে কিন্তু practical-এ infeasible।

ε-soft policies: $\pi(a|s) \ge \epsilon/|A|$ ∀$s, a$। সব action positive probability — সব sampled।

ε-greedy ε-soft-এর special case।

৮ · Off-policy MC ও importance sampling

Behavior policy $b$ (data collect) ≠ target policy $\pi$ (evaluate)। Importance sampling ratio:

$$\rho = \prod_t \frac{\pi(a_t | s_t)}{b(a_t | s_t)}$$

$V^\pi(s) \approx \mathbb{E}_b[\rho \cdot G]$।

৯ · MC vs DP — comparison

# DP (Value Iteration):
#   - Model required (P, R)
#   - Bootstrap: V(s) updated from V(s')
#   - Synchronous full sweep
#   - Bias: low, Variance: low

# MC:
#   - Model-free
#   - No bootstrap: G is full return
#   - Episode-based, sample
#   - Bias: zero (first-visit), Variance: high
#   - Continuing task-এ কাজ করে না

# TD (পরের পাঠে):
#   - Model-free
#   - Bootstrap: V(s) updated from V(s')
#   - Online, single transition
#   - Bias: small, Variance: medium
print("MC vs DP — fundamental trade-off in model use ও variance.")