পাঠ ১৪ · ৩২-এর মধ্যে · মডিউল ২

Home / AI Courses / রিইনফোর্সমেন্ট লার্নিং / Replay & Target Net

Experience Replay ও Target Network

Experience replay & target networks — the stability tricks

৭ মিনিট পড়া উচ্চ · Advanced PyTorch

এই পাঠে যা শিখবেন

Replay buffer architecture ও sampling strategies
Prioritized Experience Replay (PER)
Target network — hard vs soft update
Hindsight Experience Replay (HER) — sparse reward-এর সমাধান

১ · Replay buffer-এর architecture

Buffer = circular queue. Capacity $N$ (টিপিকাল 1M for Atari). প্রতি transition $(s, a, r, s', d)$ store.

Sampling — random batch (typically 32-512). Replay age = oldest transition কত step আগের।

Key parameters

Capacity: 1M typical. বড় buffer = stable training, কিন্তু memory cost.
Batch size: 32-512. গ্রেডিয়েন্ট estimate quality.
Min-replay (warmup): training শুরুর আগে কত transition. typically 50K.

২ · কেন uniform replay যথেষ্ট না

Uniform sample — কিছু সমস্যা:

Rare important transition (e.g., terminal reward) sample হার কম।
Already-learned region-এর transition বেশি — wasted compute.
Non-uniform learning progress.

৩ · Prioritized Experience Replay (Schaul et al., 2016)

Idea: TD-error বড় যেখানে — সেখানে শেখার সুযোগ বেশি।

Priority $p_i = |\delta_i| + \epsilon$।

Sampling probability: $P(i) = p_i^\alpha / \sum_k p_k^\alpha$।

$\alpha = 0$ → uniform. $\alpha = 1$ → fully prioritized.

Importance sampling correction: bias avoid করতে weight $w_i = (1/(N \cdot P(i)))^\beta$ — loss-এ multiply.

৪ · Sum-tree data structure

Naive priority sampling — $O(N)$ per draw. Sum-tree — $O(\log N)$।

Binary tree, leaf = priority. internal node = sum of children. sample = random in [0, total]. walk down tree.

Python · Sum-tree (sketch)

import numpy as np

class SumTree:
    def __init__(self, capacity):
        self.cap = capacity
        self.tree = np.zeros(2 * capacity)  # internal + leaves
        self.data = [None] * capacity
        self.write = 0
        self.size = 0

    def _propagate(self, idx, change):
        parent = (idx - 1) // 2
        self.tree[parent] += change
        if parent != 0:
            self._propagate(parent, change)

    def add(self, priority, transition):
        idx = self.write + self.cap - 1
        self.data[self.write] = transition
        self._update(idx, priority)
        self.write = (self.write + 1) % self.cap
        self.size = min(self.size + 1, self.cap)

    def _update(self, idx, priority):
        change = priority - self.tree[idx]
        self.tree[idx] = priority
        self._propagate(idx, change)

    def sample(self, value):
        idx = 0
        while idx < self.cap - 1:
            left = 2 * idx + 1
            if value <= self.tree[left]:
                idx = left
            else:
                value -= self.tree[left]
                idx = left + 1
        data_idx = idx - self.cap + 1
        return data_idx, self.tree[idx], self.data[data_idx]

print("Sum-tree-এ priority sampling — O(log N).")

Sum-tree — efficient priority sample. OpenAI baselines, Stable-Baselines, RLlib — সব এই use করে।

৫ · Target network — soft vs hard update

Hard update (DQN, original):

Every $C$ steps: $\theta^- \leftarrow \theta$।

Soft update (DDPG, SAC, TD3):

Every step: $\theta^- \leftarrow \tau \theta + (1 - \tau) \theta^-$, $\tau \approx 0.005$।

Equivalence: hard $C = 1/\tau$ steps-এর সাথে soft roughly equal.

Empirical:

Hard simpler, OK for discrete (Atari).
Soft smoother, better for continuous (MuJoCo).

Replay buffer + target net pipeline — DQN-এর core stability mechanism.

৬ · Hindsight Experience Replay (HER)

Andrychowicz et al. (2017) — sparse-reward task-এর জন্য brilliant idea.

Problem: "Goal G তে পৌঁছাও" — goal না পৌঁছালে reward 0. random exploration কখনো reward পায় না।

HER: failed episode-এ — actually-reached state-কে "hindsight goal" ধরে replay. প্রতিটি episode useful learning signal দেয়।

Effect: robotic manipulation-এ — pure DDPG fail, DDPG+HER solve.

৭ · Recent variants

Distributed replay (Ape-X): ১০০০ actors parallel, central learner.
Prioritized + recurrent (R2D2): stored sequence — RNN training.
Reverb (DeepMind): production-grade replay framework.
NLE (NetHack): replay with full game memory.

৮ · Replay-এর সমস্যা

Off-policy distribution shift: old data current policy-র নয়। distribution mismatch.
Large memory: 1M Atari frame ~10GB (uint8 এ store).
Stale data: very old transitions wrong policy-এর — bias.
Non-stationary task: environment বদলে গেলে — old data ভুল।

৯ · Modern alternatives

Replay-এর alternative — on-policy (PPO, A3C):

প্রতিটি batch fresh — distribution mismatch নেই।
সরল implementation.
কিন্তু sample inefficient — প্রতি transition একবার ব্যবহার।

Hybrid (PPO + buffer): recent variants — small replay-এর সাথে on-policy update.

ভাবনার প্রশ্ন

প্র ০১Replay buffer-এর capacity choice — large বনাম small trade-off?

Large buffer (10M+):

Pros: more diverse data, decorrelated, stable training.
Cons: stale data (very old policy), memory cost (10s of GB).

Small buffer (10K):

Pros: data current policy-এর কাছে, memory-friendly.
Cons: high correlation, gradient noisy, may overfit recent.

Sweet spot: task-dependent. Atari 1M, MuJoCo 100K-1M, simple Gym 10K-50K.

Diagnostic: if return curve oscillates wildly — buffer too small. if learning slow — too large.

Modern: Reverb-এর "removed sample" tracking — adaptive sizing.

প্র ০২Prioritized replay-এর importance sampling correction কেন দরকার?

Priority sampling — distribution change. যেমন high-error transition ১০x sampled — gradient estimate biased.

$\hat{g} = \frac{1}{N} \sum_i \nabla L_i$ — uniform sample-এ unbiased estimate.

Prioritized sampling-এ — $\hat{g}_{prio} = \frac{1}{B} \sum_{i \sim P} \nabla L_i$ — biased toward high-error.

Correction: importance weight $w_i = (1/(N \cdot P(i)))^\beta$।

$\hat{g}_{corr} = \frac{1}{B} \sum_i w_i \nabla L_i$ — unbiased ($\beta = 1$)।

$\beta$ schedule: training শুরুতে $\beta = 0.4$ (some bias OK), শেষে $\beta = 1$ (fully correct).

কেন বিরাট performance gain: Atari-এ PER → 2-5× sample efficiency. key: rare-but-important transitions (terminal, breakthrough) more visible.

প্র ০৩HER কীভাবে sparse reward solve করে?

Setup: Goal-conditioned RL — state + goal $g$, reward $R(s, g) = \mathbb{1}[s = g]$ (sparse).

Naive: goal $g$ পৌঁছানো ছাড়া কোনো reward — random policy কখনো পৌঁছায় না — কিছু শেখে না।

HER trick: failed episode (goal $g$ achieve হয়নি, কিন্তু other state $s'$ visit হয়েছে) — "what if goal was $s'$?" perspective থেকে relabel.

Replay:

Original: $(s, a, r=0, s', g)$।
HER: $(s, a, r=1, s', g'=s_{\text{achieved}})$।

কেন এটা valid: reward function $R(s, g) = \mathbb{1}[s = g]$ — পুরো $g$-এর space-এ একই formula. তাই different $g$ relabel correct reward দেয়।

Sampling strategies:

Future — episode-এর later state goal হিসেবে।
Final — episode-এর last state.
Episode — random episode state.

Empirical: robot block-stacking — DDPG fail, DDPG+HER works in ~1M samples. OpenAI Robotics suite-এর foundation.

প্র ০৪On-policy (PPO) ও off-policy (DQN) — কেন একই algorithm-এর জগতে coexist?

দু'টি paradigm-এর fundamental trade-off:

On-policy (PPO, A2C):

Pros:
- Stable — distribution match training data.
- Simpler — no replay, no target net.
- Theoretical guarantees stronger.
Cons: sample inefficient — কোটি sample.

Off-policy (DQN, SAC):

Pros:
- Sample efficient — replay reuse.
- Real-world friendly (where samples expensive).
Cons: instability, complex algorithm.

কখন কোনটি:

Cheap simulator (Atari, MuJoCo, parallel envs): PPO simpler, often best.
Expensive real-world: SAC/DQN — sample efficiency critical.
Continuous control with cheap sim: PPO popular.
RLHF (LLM): PPO standard (per-token cost low).

মূল উপলব্ধি: "best algorithm" task-dependent. architecture-এর choice domain-এর economics-এর প্রতিফলন।

অনুশীলন

Memory math: Atari frame 84×84×4 (uint8). 1M buffer-এর memory?

প্রতি transition: 2 frames (s + s') × 84·84·4 = 56448 bytes (~55 KB).

1M × 55 KB ≈ 53 GB. তাই DQN paper "lazy frame" trick ব্যবহার করে — overlapping frames share.
Soft update vs hard: $\tau = 0.001$ — কত step-এ target ~ 50% updated? equivalent hard $C$?

Half-life: $(1-\tau)^k = 0.5 \Rightarrow k \approx \ln 2 / \tau = 693$ steps.

Equivalent hard $C \approx 1/\tau = 1000$ steps.
PER priority: 5 transitions, $|\delta| = [10, 1, 5, 1, 1]$, $\alpha=1$। transition 1-এর sampling probability?

Sum = 10+1+5+1+1 = 18. P(1) = 10/18 ≈ 0.556.