State-value and action-value functions

5.1.4 · AI-ML › Reinforcement Learning Foundations

Overview

State-value function aur action-value function core tools hain jo yeh quantify karte hain ki kisi given policy ke under ek state ya action "kitna achha" hai. Yeh abstract goal "maximize future rewards" ko concrete numbers mein convert karte hain jo hum compute aur optimize kar sakte hain.

[!intuition] Hume value functions ki zaroorat kyun hai?

State $s$ mein ek agent jaanna chahta hai: "Kya mujhe rukna chahiye ya jaana chahiye?" Lekin jawab depend karta hai:

• Immediate reward un actions se jo abhi available hain
• Future rewards un states se jo hum baad mein visit karenge
• The policy jo hum follow kar rahe hain (kaun se actions hum usually lete hain)

Value functions infinite future ko compress karke ek single number mein le aate hain: expected cumulative reward is point se aage. Isse hum states aur actions ko numerically compare kar sakte hain.

Key insight yeh hai: Har baar thousands of possible futures simulate karne ki jagah, hum ek function $V(s)$ ya $Q(s,a)$ seekhte hain jo "yeh situation kitni achhi hai?" yeh memorize karta hai.

[!definition] State-value function $V^{\pi }(s)$

State-value function $V^{\pi }(s)$ woh expected return hai jab hum state $s$ se start karke policy $\pi$ follow karte hain:

$V^{\pi }(s)={\mathbb{E}}_{\pi }\left[G_t\mid S_t=s\right]$

jahan $G_t=R_{t+1}+\gamma R_{t+2}+{\gamma }^2{R}_{t+3}+\dots ={\sum }_{k=0}^{\infty }{\gamma }^k{R}_{t+k+1}$ discounted return hai.

Isko tod ke samjhte hain:

• ${\mathbb{E}}_{\pi }$: policy $\pi$ follow karke sample ki gayi trajectories par expectation
• $G_t$: future rewards ka sum, $\gamma \in [0,1]$ se discount kiya gaya
• $S_t=s$: hum state $s$ mein start karne ki condition lagate hain

Yeh hume kya batata hai: $V^{\pi }(s)$ ka jawab hai "Agar main state $s$ mein hoon aur apni current policy $\pi$ follow karta rahoon, toh mera expected total reward kya hoga?"

[!definition] Action-value function $Q^{\pi }(s,a)$

Action-value function (ya Q-function) $Q^{\pi }(s,a)$ woh expected return hai jab hum state $s$ mein start karke action $a$ lete hain aur phir policy $\pi$ follow karte hain:

$Q^{\pi }(s,a)={\mathbb{E}}_{\pi }\left[G_t\mid S_t=s,A_t=a\right]$

$V^{\pi }(s)$ se farq:

• $V^{\pi }(s)$: "Policy $\pi$ ke under yeh state kitni achhi hai?"
• $Q^{\pi }(s,a)$: "State $s$ mein action $a$ lena, phir $\pi$ follow karna, kitna achha hai?"

$Q$ hume action-level granularity deta hai. Hum same state mein alag-alag actions compare kar sakte hain.

[!formula] $V$ aur $Q$ ke beech relationship

$Q$ se $V$ nikalna

Agar hum $Q^{\pi }(s,a)$ sabhi actions ke liye jaante hain, toh hum $V^{\pi }(s)$ policy ke action distribution par average lekar compute kar sakte hain:

$V^{\pi }(s)={\sum }_{a\in \mathcal{A}}\pi (a|s)Q^{\pi }(s,a)$

Yeh kyun kaam karta hai:

1. $V^{\pi }(s)$ woh expected return hai jab state $s$ se $\pi$ follow karo
2. Policy $\pi$ hume actions par ek probability distribution deta hai: $\pi (a|s)$
3. Har action $a$ ke liye, return $Q^{\pi }(s,a)$ hai
4. Actions par expected value: har $Q$ ko uski probability se weight karo

Intuition: $V$ sabhi action-values ka weighted average hai, jahan weights policy ke action probabilities hain.

$V$ se $Q$ nikalna

Hum $Q$ ko $V$ ke terms mein one-step dynamics use karke express kar sakte hain:

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

jahan $p(s^{\prime },r|s,a)$ environment ki transition probability hai.

First principles se derivation:

Definition se shuru karo: $Q^{\pi }(s,a)={\mathbb{E}}_{\pi }[G_t|S_t=s,A_t=a]$

Return $G_t$ ko expand karo: $Q^{\pi }(s,a)={\mathbb{E}}_{\pi }[R_{t+1}+\gamma G_{t+1}|S_t=s,A_t=a]$

Immediate aur future rewards ko alag karo: $Q^{\pi }(s,a)=\mathbb{E}[R_{t+1}|S_t=s,A_t=a]+\gamma {\mathbb{E}}_{\pi }[G_{t+1}|S_t=s,A_t=a]$

Immediate reward sirf environment se $(s,a{,}^{\prime },r)$ par depend karta hai: $\mathbb{E}[R_{t+1}|S_t=s,A_t=a]={\sum }_{s^{\prime },r}p(s^{\prime },r|s,a)\cdot r$

Future return ${\mathbb{E}}_{\pi }[G_{t+1}|S_t=s,A_t=a]$ depend karta hai ki hum kahan land karte hain. $s^{\prime }$ par condition lagao: ${\mathbb{E}}_{\pi }[G_{t+1}|S_t=s,A_t=a]={\sum }_{s^{\prime },r}p(s^{\prime },r|s,a)\cdot {\mathbb{E}}_{\pi }[G_{t+1}|S_{t+1}=s^{\prime }]$

Lekin ${\mathbb{E}}_{\pi }[G_{t+1}|S_{t+1}=s^{\prime }]=V^{\pi }(s^{\prime })$ definition se!

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

Yeh step kyun? Hum law of iterated expectation aur Markov property use kar rahe hain: $s^{\prime }$ se future return sirf $s^{\prime }$ par depend karta hai, is par nahi ki hum wahan kaise pahunche.

[!formula] Bellman expectation equations

Yeh recursive consistency conditions hain jo value functions ko satisfy karni chahiye.

$V^{\pi }$ ke liye Bellman equation

$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]$

Derivation:

1. $V^{\pi }(s)={\sum }_a\pi (a|s)Q^{\pi }(s,a)$ se shuru karo (actions par averaging)
2. $Q^{\pi }(s,a)={\sum }_{s^{\prime },r}p(s^{\prime },r|s,a)[r+\gamma V^{\pi }(s^{\prime })]$ substitute karo
3. Result: $V^{\pi }(s)$ successor states ke liye $V^{\pi }(s^{\prime })$ ke terms mein

Intuition: State $s$ ki value equals immediate reward plus jahan bhi agle land karo uski discounted value, aapke policy ke action choices par average lekar.

$Q^{\pi }$ ke liye Bellman equation

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

Derivation:

1. $Q^{\pi }(s,a)={\sum }_{s^{\prime },r}p(s^{\prime },r|s,a)[r+\gamma V^{\pi }(s^{\prime })]$ se shuru karo
2. $V^{\pi }(s^{\prime })={\sum }_{a^{\prime }}\pi (a^{\prime }|s^{\prime })Q^{\pi }(s^{\prime },a^{\prime })$ substitute karo
3. Result: $Q^{\pi }(s,a)$ ko $Q^{\pi }(s^{\prime },a^{\prime })$ ke terms mein

Recursive kyun? Dono equations value functions ko successor states par khud ke terms mein express karti hain. Yahi bootstrapping principle hai: hum value functions ko iteratively solve kar sakte hain.

[!example] Example 1: Gridworld state values

Ek $3\times 3$ gridworld consider karo. Agent kahin se bhi start karta hai, goal top-right corner $(0,2)$ hai. Actions: up, down, left, right. Deterministic. Reward: $-1$ per step, $+10$ goal par. $\gamma =0.9$. Policy $\pi$: agar possible ho toh right jao, warna up jao.

Chaliye $V^{\pi }(s)$ compute karte hain state $s=(1,1)$ (center) ke liye.

Step-by-step:

1. Policy action identify karo: $(1,1)$ se, $\pi$ probability 1 ke saath right jaata hai.

2. Next state: $(1,2)$ (goal se ek step door)

3. Immediate reward: $r=-1$

4. Bellman equation: $V^{\pi }(1,1)=1.0\cdot [-1+0.9\cdot V^{\pi }(1,2)]$

5. $V^{\pi }(1,2)$ compute karo: $(1,2)$ se, policy $(0,2)$ (goal) par up jaati hai. $V^{\pi }(1,2)=1.0\cdot [-1+0.9\cdot V^{\pi }(0,2)]$

6. Goal par: $V^{\pi }(0,2)=0$ (terminal state, koi future rewards nahi)

7. Back-substitute karo: $V^{\pi }(1,2)=-1+0.9\cdot 0=-1$ $V^{\pi }(1,1)=-1+0.9\cdot (-1)=-1-0.9=-1.9$

Yeh step kyun? Bellman equation ka har application value ko goal se backward propagate karta hai. Negative values goal tak pahunchne ki cost reflect karti hain (har step par $-1$ incur hota hai).

[!example] Example 2: Two-action state mein action values

State $s$, do actions: $a_1$ (safe), $a_2$ (risky). Stochastic outcomes.

$a_1$ (safe):

• 100% chance: next state $s^{\prime }$, reward $r=1$

$a_2$ (risky):

• 70% chance: next state $s^{\prime \prime }$, reward $r=5$
• 30% chance: next state $s^{\prime \prime \prime }$, reward $r=-3$

Maano $V^{\pi }(s^{\prime })=10$, $V^{\pi }(s^{\prime \prime })=15$, $V^{\pi }(s^{\prime \prime })=2$. $\gamma =1.0$ (undiscounted).

$Q^{\pi }(s,a_1)$ compute karo:

$Q^{\pi }(s,a_1)=.0\cdot [1+1.0\cdot 10]=11$

Kyun? Deterministic transition hai, isliye sum ek single term mein collapse ho jaata hai.

$Q^{\pi }(s,a_2)$ compute karo:

$Q^{\pi }(s,a_2)=0.7\cdot [5+1.0\cdot 15]+0.3\cdot [-3+1.0\cdot 2]$ $=0.7\cdot 20+0.3\cdot (-1)=14-0.3=13.7$

Yeh step kyun? Hum har outcome ko uski probability se weight karte hain. Risky action ka expected value zyada hai despite negative outcome ki possibility ke.

Comparison: $Q^{\pi }(s,a_2)=13.7>Q^{\pi }(s,a_1)=11$. Agar hum policy improve karne ki koshish kar rahe hain, toh hum state $s$ mein $a_2$ prefer karenge.

[!example] Example 3: Stochastic policy ke saath $V$ ko $Q$ se compute karna

State $s$, actions{a_1, a_2, a_3}$. Known Q-values:

• $Q^{\pi }(s,a_1)=5$
• $Q^{\pi }(s,a_2)=8$
• $Q^{\pi }(s,a_3)=3$

Policy $\pi$:

• $\pi (a_1|s)=0.5$
• $\pi (a_2|s)=0.3$
• $\pi (a_3|s)=0.2$

$V^{\pi }(s)$ compute karo:

$V^{\pi }(s)={\sum }_a\pi (a|s)Q^{\pi }(s,a)$ $=0.5\cdot 5+0.3\cdot 8+0.2\cdot 3$ $=2.5+2.4+0.6=5.5$

Yeh step kyun? Policy stochastic hai, isliye hum weighted average lete hain. $a_2$ ka highest Q-value hai lekin sirf 30% probability hai, isliye yeh overall value mein $0.3\times 8=2.4$ contribute karta hai.

Insight: Bhaale $a_2$ best hai, $V^{\pi }(s)=5.5$ hai jo $Q^{\pi }(s,a_2)=8$ se kam hai kyunki policy kabhi kabhi suboptimal actions choose karti hai.

[!mistake] Common mistake: $V$ aur $Q$ ko policy improvement mein confuse karna

Galat reasoning: "Main sabhi states ke liye $V^{\pi }(s)$ compute karoonga, phir woh action choose karoonga jo highest $V$ wale state mein le jaaye."

Kyun sahi lagta hai: Hum valuable states mein jaana chahte hain, isliye woh action choose karna jo highest-value next state mein le jaaye logical lagta hai.

Kyun galat hai:

1. $V^{\pi }(s)$ pehle se policy ke action distribution par average hua hota hai. Yeh nahi batata ki kaun sa action best hai.
2. Ek action high-value state mein le ja sakta hai lekin low immediate reward ho sakta hai, jo isse overall worse banata hai.
3. Transition stochastic ho sakta hai—tum simply next state "choose" nahi kar sakte.

Fix: Action selection ke liye $Q^{\pi }(s,a)$ use karo! Compute karo: $Q^{\pi }(s,a)={\sum }_{s^{\prime },r}p(s^{\prime },r|s,a)[r+\gamma V^{\pi }(s^{\prime })]$ har action ke liye, phir $\arg {\max }_a{Q}^{\pi }(s,a)$ pick karo.

Yeh kyun kaam karta hai: $Q$ pehle se account karta hai:

• Immediate reward $r$
• $s^{\prime }$ par sum ke zariye stochastic transitions
• $V^{\pi }(s^{\prime })$ ke zariye future value

Mistake ko steel-man karo: Confusion isliye hoti hai kyunki deterministic environments mein zero immediate reward ke saath, $V$ aur $Q$ similar meanings mein collapse ho jaate hain. Lekin generally, yeh alag hain!

[!mistake] Common mistake: Value function notation mein policy ko ignore karna

Galat statement: "Value function $V(s)=10$."

Kyun galat hai: Value functions policy-dependent hoti hain! Alag-alag policies same state ke liye alag values lead karti hain.

Fix: Hamesha $V^{\pi }(s)$ likho ya specify karo ki kaun si policy mean kar rahe ho. Optimal policy ${\pi }^{\ast }$ ke liye, $V^{\ast }(s)$ likho.

Example:

• Random policy ${\pi }_{\text{random}}$: $V^{{\pi }_{\text{random}}}(s)=2$
• Optimal policy ${\pi }^{\ast }$: $V^{\ast }(s)=10$

Same state, alag values!

Yeh kyun matter karta hai: Policy evaluation mein, hum ek fixed $\pi$ ke liye $V^{\pi }$ compute karte hain. Policy optimization mein, hum woh $\pi$ dhundte hain jo $V^{\pi }$ maximize kare.

[!recall]- Ek 12 saal ke bachche ko explain karo

Socho tum ek video game khel rahe ho. Tum ek certain level (state) par ho. Tum jaanna chahte ho: "Abhi meri situation kitni achhi hai?"

$V(s)$ teri current level ke liye ek score jaisa hai. Yeh batata hai, "Agar tum waise khelte raho jaise tum usually khelte ho, toh ab se game khatam hone tak shayad kitne total points milenge." Yeh ek single number hai jo tera future summarize karta hai.

$Q(s,a)$ har possible move ke liye ek score jaisa hai. Yeh kehta hai, "Agar tum abhi jump button press karo, toh kitne points milenge." Phir, "Agar tum shoot button press karo, toh kitne points milenge." Yeh alag-alag moves compare karne mein help karta hai.

Key difference: $V$ batata hai ki tera position kitna achha hai agar tum wahi karte raho jo tum usually karte ho. $Q$ batata hai ki har specific choice kitni achhi hai, taaki tum best wala choose kar sako!

Hume dono ki zaroorat kyun hai: Kabhi tum jaanna chahte ho "Kya main overall achhi jagah hoon?" (use $V$). Aur kabhi tum jaanna chahte ho "Kaun sa button press karun?" (use $Q$).

[!mnemonic] V vs Q yaad karo

V = "Value of a Vacation spot"

• Tum Hawaii $(s)$ mein ho. Overall yahan rehna kitna achha hai? Woh $V(s)$ hai.
• Depend karta hai teri plans (policy) par: agar tum beaches pasand karte ho, toh Hawaii great hai. Agar tum sun se nafrat karte ho, toh utna nahi!

Q = "Quality of a Quest"

• Tum Hawaii mein ho aur decide kar rahe ho: swim karo, hike karo, ya surf karo? Har choice ka ek quality score hai: $Q(s,\text{swim})$, $Q(s,\text{hike})$, $Q(s,\text{surf})$.
• Best experience ke liye highest $Q$ choose karo.

V hai jahan tum ho. Q hai jo tum karte ho.

Connections

• 5.1.03-Returns-and-episodes: Value functions expected return $G_t$ compute karti hain
• 5.1.05-Optimal-policiesand-optimal-value-functions: Optimal $V^{\ast }$ aur $Q^{\ast }$ best policy ke liye value functions hain
• 5.2.01-Dynamic-programming-policy-evaluation: Iterative algorithms $V^{\pi }$ ke liye Bellman equations solve karte hain
• 5.2.02-Policy-iteration: Policies improve karne ke liye $V^{\pi }$ aur $Q^{\pi }$ use karta hai
• 5.3.01-Monte-Carlo-prediction: Sampled episodes se $V^{\pi }$ estimate karta hai
• 5.4.01-Temporal-difference-learning: Bellman equations se bootstrapping use karke $V$ aur $Q$ update karta hai

#flashcards/ai-ml

State-value function $V^{\pi }(s)$ kya hai? :: Expected return (cumulative discounted reward) state $s$ se start karke aur phir policy $\pi$ follow karke: $V^{\pi }(s)={\mathbb{E}}_{\pi }[G_t|S_t=s]$

Concept Map