REINFORCE algorithm

5.2.6 · AI-ML › Deep & Advanced RL

HUM kya optimize kar rahe hain?

Policy seedha kyun? Continuous ya bahut bade action spaces mein $\arg {\max }_{a}Q(s,a)$ lena mushkil hai. Ek parameterized policy stochasticity, continuous actions handle karti hai, aur smooth optimization deti hai.

KAISE: Policy Gradient scratch se derive karna

Hum chahte hain ${\nabla }_{\theta }J(\theta )$. Dikkat yeh hai: expectation ek aisi distribution par hai jo $\theta$ par depend karti hai. Hum gradient andar directly nahin daal sakte — isliye hum log-derivative trick use karte hain.

Step 1 — Expectation ko trajectories par ek integral ki tarah likho. $J(\theta )=\int p_{\theta }(\tau )R(\tau )d\tau$ Kyun? Ek expectation bas quantity ka probability-weighted sum/integral hai.

Step 2 — Differentiate karo; gradient integral ke andar jaata hai (linear operator). ${\nabla }_{\theta }J=\int {\nabla }_{\theta }{p}_{\theta }(\tau )R(\tau )d\tau$ Kyun? $R(\tau )$ $\theta$ par depend nahin karta (rewards environment se aate hain), sirf $p_{\theta }(\tau )$ karta hai.

Step 3 — Log-derivative trick. Yeh identity note karo: ${\nabla }_{\theta }{p}_{\theta }(\tau )=p_{\theta }(\tau ){\nabla }_{\theta }\log p_{\theta }(\tau )$ Kyun? Kyunki ${\nabla }_{\theta }\log p=\frac{{\nabla }_{\theta }p}{p}$ — bas $\log$ par chain rule. Dono sides ko $p$ se multiply karo.

Substitute karo: ${\nabla }_{\theta }J=\int p_{\theta }(\tau ){\nabla }_{\theta }\log p_{\theta }(\tau )R(\tau )d\tau ={\mathbb{E}}_{\tau }[{\nabla }_{\theta }\log p_{\theta }(\tau )R(\tau )]$ Yeh kyun important hai: iska matlab ek expectation-ka-gradient ek gradient-ki-expectation mein badal gaya, jise hum trajectories sample karke estimate kar sakte hain (Monte Carlo).

Step 4 — $\log p_{\theta }(\tau )$ expand karo. Trajectory probability hai: $p_{\theta }(\tau )=\rho (s_0){\prod }_{t=0}^T{\pi }_{\theta }(a_t\mid s_t)P(s_{t+1}\mid s_t,a_t)$ Log lo (product → sum): $\log p_{\theta }(\tau )=\log \rho (s_0)+{\sum }_t\log {\pi }_{\theta }(a_t\mid s_t)+{\sum }_t\log P(s_{t+1}\mid s_t,a_t)$ Ab $\theta$ ke w.r.t. differentiate karo. Environment ke terms $\rho$ aur $P$ $\theta$ par depend nahin karte, isliye unke gradients zero ho jaate hain! ${\nabla }_{\theta }\log p_{\theta }(\tau )={\sum }_{t=0}^T{\nabla }_{\theta }\log {\pi }_{\theta }(a_t\mid s_t)$ Yeh kyun badi baat hai: Hum gradient paate hain transition model $P$ jaane bina — REINFORCE model-free hai.

$G_t$ (reward-to-go) kyun, poora $R(\tau )$ kyun nahin? Time $t$ par action sirf future rewards ko affect kar sakta hai. $t$ se pehle mile rewards $a_t$ ke credit ke nazariye se noise hain. Unhe hatane se estimator unbiased rehta hai lekin variance kam hoti hai. Yeh causality hai.

Baseline: variance reduction

${\nabla }_{\theta }J=\mathbb{E}\left[{\sum }_t{\nabla }_{\theta }\log {\pi }_{\theta }(a_t\mid s_t)(G_t-b(s_t))\right]$

Yeh unbiased kyun hai? Kisi bhi baseline ke liye jo action par depend na kare: ${\mathbb{E}}_{a\sim \pi }[{\nabla }_{\theta }\log {\pi }_{\theta }(a\mid s)b(s)]=b(s){\sum }_a{\nabla }_{\theta }{\pi }_{\theta }(a\mid s)=b(s){\nabla }_{\theta }\underset{=1}{\underbrace{\sum _a{\pi }_{\theta }(a\mid s)}}=b(s)\cdot 0=0$ Isliye baseline variance change karta hai lekin zero bias add karta hai. Ek common choice: $b(s_t)=\hat{V}(s_t)$, jo advantage $A_t=G_t-\hat{V}(s_t)$ deta hai.

Algorithm (Monte Carlo, episodic)

Initialize θ (policy network), optional value net for baseline
repeat:
    Sample an episode τ = (s0,a0,r0,...,sT) using π_θ
    for t = 0 ... T:
        G_t = Σ_{k=t..T} γ^{k-t} r_k          # reward-to-go
        A_t = G_t - b(s_t)                     # optional baseline
    Loss  = - Σ_t log π_θ(a_t|s_t) * A_t       # minus: grad ASCENT
    θ ← θ + α ∇_θ ( -Loss )                    # via autograd + optimizer
until converged

Minus sign kyun? Optimizers minimize karte hain. Hum $J$ maximize karna chahte hain, isliye $-J$ minimize karte hain.

Worked Examples

Common Mistakes (Steel-manned)

Active Recall

Flashcards

Connections

• Policy Gradient Methods — REINFORCE iska foundational instance hai.
• Actor-Critic Methods — Monte-Carlo $G_t$ ko ek learned critic se replace karta hai (baseline + bootstrapping).
• Advantage Function — $A_t=G_t-V(s_t)$ weighting ke roop mein use hota hai.
• Value Function V(s) — ek natural baseline choice.
• Monte Carlo Methods — REINFORCE returns full-episode MC estimates hain.
• Log-Derivative Trick — core mathematical identity.
• Softmax Policy / Gaussian Policy — ${\pi }_{\theta }$ ki common parameterizations.
• Variance Reduction in RL — baselines, reward-to-go, control variates.

Concept Map