Bellman equations

5.1.5 · AI-ML › Reinforcement Learning Foundations

WHY they matter: RL mein, ek agent ko ye jaanna hota hai ki "ye state kitni achi hai?" ya "ye action kitna acha hai?". Bellman equations hame in values ko bootstrapping se compute karne ka tarika deti hain—future values ke estimates use karke current estimates ko improve karna. Ye iska core dynamic programming hai.

WHAT they describe: Kisi bhi state ya action pair se expected return (cumulative discounted reward), jo immediate reward aur successor states ki value ke terms mein express hota hai.

HOW they work: Infinite-horizon value ko one-step reward + discounted future value mein decompose karke, hum ek intractable sum ko ek recursive formula mein badal dete hain jise iteratively solve kiya ja sakta hai.

Derivation from First Principles

$V^{\pi }(s)={\mathbb{E}}_{\pi }\left[{\sum }_{t=0}^{\infty }{\gamma }^t{R}_{t+1}\mid S_0=s\right]$

jahan $\gamma \in [0,1)$ discount factor hai, $R_{t+1}$ time $t+1$ par reward hai, aur expectation policy $\pi$ se generate kiye gaye trajectories par hai.

WHY this definition? Hame long-term cumulative reward ki parwah hai, lekin door ke rewards kam matter karte hain (discount factor). Expectation environment aur policy dono mein stochasticity ko account karta hai.

Bellman Equation for $V^{\pi }$ (State Value)

Goal: $V^{\pi }(s)$ ko recursively express karna.

Step 1: Return sum ko expand karo: $V^{\pi }(s)={\mathbb{E}}_{\pi }\left[R_1+\gamma R_2+{\gamma }^2{R}_3+\cdots \mid S_0=s\right]$

Step 2: Pehle reward ko factor out karo: $V^{\pi }(s)={\mathbb{E}}_{\pi }\left[R_1\mid S_0=s\right]+{\mathbb{E}}_{\pi }\left[\gamma (R_2+\gamma R_3+\cdots )\mid S_0=s\right]$

Why this step? Hum immediate reward (jo abhi hota hai) ko future rewards (jo is par depend karte hain ki hum aage kahan jaate hain) se alag kar rahe hain.

Step 3: Recognize karo ki doosra term next state $S_1$ ki discounted value hai: $V^{\pi }(s)={\mathbb{E}}_{\pi }[R_1\mid S_0=s]+\gamma {\mathbb{E}}_{\pi }[V^{\pi }(S_1)\mid S_0=s]$

Step 4: Actions aur transitions par expectation expand karo: Policy hame $\pi (a|s)$ deti hai, dynamics hame $p(s^{\prime },r|s,a)$ dete hain:

$V^{\pi }(s)={\sum }_a\pi (a|s){\sum }_{s^{\prime },r}p(s^{\prime },r|s,a)\left[r+\gamma V^{\pi }(s^{\prime })\right]$

Interpretation: Policy $\pi$ ke under state $s$ ki value, expected immediate reward plus discounted next-state value ka weighted average (un actions par jo $\pi$ choose karta hai) ke barabar hai.

Bellman Equation for $Q^{\pi }$ (Action Value)

$Q^{\pi }(s,a)={\mathbb{E}}_{\pi }\left[{\sum }_{t=0}^{\infty }{\gamma }^t{R}_{t+1}\mid S_0=s,A_0=a\right]$

WHY? Kabhi kabhi hame specific actions evaluate karne hote hain (jaise Q-learning mein). $Q$ hame batata hai ki "state $s$ mein action $a$ kitna acha hai?".

Derivation:

Step 1: Pehle action $a$ lene par condition karo: $Q^{\pi }(s,a)=\mathbb{E}\left[R_1+\gamma V^{\pi }(S_1)\mid S_0=s,A_0=a\right]$

Why? $a$ lene ke baad, hum $S_1$ par transition karte hain aur phir policy $\pi$ follow karte hain, jo hame $V^{\pi }(S_1)$ deta hai.

Step 2: Environment dynamics par expand karo: $Q^{\pi }(s,a)={\sum }_{s^{\prime },r}p(s^{\prime },r|s,a)\left[r+\gamma V^{\pi }(s^{\prime })\right]$

Step 3: $V^{\pi }(s^{\prime })$ ko $Q^{\pi }$ ke terms mein express karo: $V^{\pi }(s^{\prime })={\sum }_{a^{\prime }}\pi (a^{\prime }|s^{\prime })Q^{\pi }(s^{\prime },a^{\prime })$

Step 4: Wapas substitute karo:

Bellman Optimality Equations

GOAL: Sabse best possible policy ${\pi }^{\ast }$ aur uske value functions $V^{\ast }(s)$ aur $Q^{\ast }(s,a)$ dhundna.

KEY INSIGHT: Optimal policy $V^{\ast }$ ya $Q^{\ast }$ ke respect mein greedy hoti hai: ${\pi }^{\ast }(s)=\arg {\max }_a{Q}^{\ast }(s,a)$

Derivation of Bellman Optimality for $V^{\ast }$:

Step 1: Optimal policy best action choose karti hai: $V^{\ast }(s)={\max }_a{Q}^{\ast }(s,a)$

Step 2: $Q^{\ast }$ definition substitute karo: $V^{\ast }(s)={\max }_a{\sum }_{s^{\prime },r}p(s^{\prime },r|s,a)\left[r+\gamma V^{\ast }(s^{\prime })\right]$

Why the max? Hum ab koi fixed policy follow nahi kar rahe—hum wo action choose kar rahe hain jo har step par value maximize kare.

Derivation of Bellman Optimality for $Q^{\ast }$:

$Q^{\ast }(s,a)={\sum }_{s^{\prime },r}p(s^{\prime },r|s,a)\left[r+\gamma {\max }_{a^{\prime }}{Q}^{\ast }(s^{\prime },a^{\prime })\right]$

Worked Examples

Bellman equation use karke $V^{\pi }(s_1)$ compute karo.

Step 1: $s_1$ ke liye Bellman equation likho: $V^{\pi }(s_1)={\sum }_a\pi (a|s_1){\sum }_{s^{\prime },r}p(s^{\prime },r|s_1,a)\left[r+\gamma V^{\pi }(s^{\prime })\right]$

Step 2: Assume karo ki $s_1$ right move karke $s_2$ ya down move karke $s_3$ ja sakta hai, aur walls se takraane par wahi rehta hai:

• Action "right": $s_2$ par jaata hai, reward $-1$
• Action "down": $s_3$ par jaata hai, reward $-1$
• Actions "left", "up": $s_1$ par hi rehta hai, reward $-1$

Step 3: Substitute karo: $V^{\pi }(s_1)=0.25[(-1)+0.9V^{\pi }(s_2)]+0.25[(-1)+0.9V^{\pi }(s_3)]+0.25[(-1)+0.9V^{\pi }(s_1)]+0.25[(-1)+0.9V^{\pi }(s_1)]$

Why this step? Uniform policy ke under har action ki probability 0.25 hai. Hum saare actions aur unke outcomes par sum karte hain.

Step 4: Simplify karo (symmetry assume karte hue $V^{\pi }(s_2)=V^{\pi }(s_3)=V$): $V^{\pi }(s_1)=-1+0.9[0.25V+0.25V+0.25V^{\pi }(s_1)+0.25V^{\pi }(s_1)]$ $V^{\pi }(s_1)=-1+0.9[0.5V+0.5V^{\pi }(s_1)]$ $V^{\pi }(s_1)=-1+0.45V+0.45V^{\pi }(s_1)$ $0.55V^{\pi }(s_1)=-1+0.45V$

Result: Ye linear equations ka ek system hai. Iteratively ya exactly solve karne par value milti hai. Bellman equation ne ek sequential problem ko ek algebraic problem mein badal diya.

Bellman optimality equation ko update ke roop mein apply karo:

Step 1: Bellman optimality kehti hai: $Q^{\ast }(s,a)=\mathbb{E}[r+\gamma {\max }_{a^{\prime }}{Q}^{\ast }(s^{\prime },a^{\prime })]$

Step 2: Hame ek sample $(s,a,r,s^{\prime })$ mila, toh temporal difference target hai: $\text{target}=r+\gamma {\max }_{a^{\prime }}Q(s^{\prime },a^{\prime })=5+0.9\times 12=5+10.8=15.8$

Why? Ye is experience ke base par "true" $Q^{\ast }(s,a)$ ka hamara bootstrapped estimate hai.

Step 3: $Q(s,a)$ ko target ki taraf update karo (learning rate $\alpha =0.1$ ke saath): $Q(s,a)\leftarrow Q(s,a)+\alpha [\text{target}-Q(s,a)]$ $Q(s,a)\leftarrow 10+0.1[15.8-10]=10+0.58=10.58$

Interpretation: $Q(s,a)$ ka hamara estimate Bellman optimality equation se predict ki gayi value ki taraf move karke improve hua.

Common Mistakes

Why it feels right: Simple lagta hai—bas rewards add karo.

The problem: Discounting ke bina, infinite-horizon returns diverge ho jaate hain. Agar har state $r=1$ deti hai, toh $V(s)=\infty$. Discount $\gamma$ convergence ensure karta hai aur near-term rewards ko prefer karta hai.

Fix: Recursive term mein hamesha $\gamma$ include karo: $V(s)=r+\gamma V(s^{\prime })$.

Why it feels right: Dono mein actions aur values hain—aasaani se mix up ho jaate hain.

The problem:

• $V^{\pi }$ ek fixed policy $\pi$ se tied hai, isliye hum $\pi$ ke chosen actions par expectation lete hain.
• $V^{\ast }$ optimal value hai, isliye hum saare actions par max lete hain (best choose karte hain).

Fix:

• Bellman expectation ($\pi$ ke liye): ${\sum }_a\pi (a|s)\dots$
• Bellman optimality (${\pi }^{\ast }$ ke liye): ${\max }_a\dots$

Why it feels right: Deterministic environments mein, $(s,a)$ per sirf ek $s^{\prime }$ hota hai.

The problem: Zyaadatar environments stochastic hote hain. Different probabilities $p(s^{\prime }|s,a)$ ke saath kai possible next states ho sakte hain.

Fix: Possible next states par hamesha sum/integrate karo: $V(s)={\sum }_{s^{\prime }}p(s^{\prime }|s,a)[r(s,a,s^{\prime })+\gamma V(s^{\prime })]$

Active Recall Prompts

Bellman equation kehti hai: Tere total points = points jo tujhe abhi milte hain + (thode kam valuable) points jo agli level se milenge.

"Thode kam valuable" kyun? Kyunki baad ke points abhi ke points se thode kam matter karte hain (jaise aaj ₹100 milna ek saal baad ₹100 milne se better hai—yahi discount factor hai).

Toh poore game ke points ek saath add karne ki bajay (jo mushkil hai), tum bas socho: "Mujhe abhi kya milta hai, aur agli level kitni worth hai?" Phir tum agli level ki value ka apna guess use karte ho is level ki value figure out karne ke liye. Ye backward karte raho, aur tum har level ki value figure out kar lete ho!

"Expectation" wala part ka matlab hai: agar game random hai (kabhi kabhi power-up milta hai, kabhi nahi), tum saari possibilities par average karte ho.

Connections

• Dynamic Programming — Bellman equations DP methods enable karte hain (policy iteration, value iteration)
• Temporal Difference Learning — TD learning Bellman equations ko update rules ke roop mein use karta hai
• Q-Learning — $Q^{\ast }$ ke liye Bellman optimality par directly built off-policy algorithm
• Policy Gradient Methods — Contrast: explicit value functions ke bina directly policy optimize karna
• Markov Decision Process — Bellman equations MDPs ki value structure ko formalize karte hain
• Discount Factor — Immediate aur future rewards ke beech tradeoff control karta hai
• Bootstrapping — Key RL concept: value estimates update karne ke liye value estimates use karna

#flashcards/ai-ml

What is the Bellman expectation equation for $V^{\pi }(s)$? :: $V^{\pi }(s)={\sum }_a\pi (a|s){\sum }_{s^{\prime },r}p(s^{\prime },r|s,a)[r+\gamma V^{\pi }(s^{\prime })]$ — policy $\pi$ ke under state $s$ ki value, expected immediate reward plus discounted next-state value ke barabar hai.

What is the recursive structure of the Bellman equation? :: $V(s)=\text{immediate reward}+\gamma \times \text{value of next state}$ — infinite-horizon value ko one-step reward + discounted future mein todta hai, iterative solution enable karta hai.

Concept Map