Policies and value functions

What Is a Policy?

Why stochastic? In some environments (partially observable, or games with mixed strategies), randomizing actions is optimal. Also helps with exploration during learning.

How does it work?

Agent observes state $s_t$
Policy outputs action: $a_t \sim \pi(\cdot|s_t)$ (sample from the distribution)
Environment responds with reward $r_{t+1}$ and next state $s_{t+1}$
Repeat

State-Value Function: V(s)

Derivation from first principles:

Start with the definition of "expected future return" when you're in state $s$ at time $t$ .

The return (cumulative reward) is: $G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots = \sum_{k=0}^\infty \gamma^k R_{t+k+1}$

Why discount?

Rewards now are more certain than rewards later (uncertainty)
Mathematically ensures convergence when rewards are bounded
Models impatience (economic interpretation)

The value of state $s$ under policy $\pi$ is the expected return: $V^\pi(s) = \mathbb{E}_\pi[G_t | S_t = s]$

Why expectation? The policy might be stochastic, and the environment dynamics $P(s'|s,a)$ are often stochastic, so we average over all possible futures.

Bellman Equation for $V^\pi$ :

We can decompose the return recursively: $G_t = R_{t+1} + \gamma G_{t+1}$

Taking expectation on both sides: $V^\pi(s) = \mathbb{E}_\pi[R_{t+1} + \gamma G_{t+1} | S_t = s]$

Now split the expectation. First, we sample action from policy, then next state from dynamics: $V^\pi(s) = \sum_a \pi(a|s) \sum_{s'} P(s'|s,a) \left[R(s,a,s') + \gamma V^\pi(s')\right]$

Why this step? We marginalize over all possible actions (weighted by policy) and all possible next states (weighted by transition probability).

Compact form: $\boxed{V^\pi(s) = \sum_a \pi(a|s) \sum_{s',r} p(s',r|s,a)\left[r + \gamma V^\pi(s')\right]}$

This is the Bellman expectation equation for $V^\pi$ .

Worked example Computing V(s) by Hand

Setup: 2-state MDP

States: $S = \{s_1, s_2\}$
Actions: $A = \{a_1\}$ (only one action)
Policy: $\pi(a_1|s_1) = 1$ , $\pi(a_1|s_2) = 1$ (deterministic)
Dynamics:
From $s_1$ : take $a_1$ → get reward $+1$ , stay in $s_1$ with prob 0.5, go to $s_2$ with prob 0.5
From $s_2$ : take $a_1$ → get reward $+2$ , stay in $s_2$ forever
Discount: $\gamma = 0.9$

Find: $V^\pi(s_1)$ and $V^\pi(s_2)$

Solution: Write Bellman equations: $V^\pi(s_1) = 1 + 0.9 \left[0.5 \cdot V^\pi(s_1) + 0.5 \cdot V^\pi(s_2)\right]$ $V^\pi(s_2) = 2 + 0.9 \cdot V^\pi(s_2)$

Why this form?

Immediate reward is deterministic here (always +1 from $s_1$ , +2 from $s_2$ )
Future value is the discounted expected value of next state Solve the second equation first: $V^\pi(s_2) = 2 + 0.9 V^\pi(s_2)$ $V^\pi(s_2) - 0.9 V^\pi(s_2) = 2$ $0.1 V^\pi(s_2) = 2$ $V^\pi(s_2) = 20$

Why? In $s_2$ , the agent gets +2 every step forever, so the discounted sum is $2 + 0.9 \cdot 2 + 0.9^2 \cdot 2 + \cdots = \frac{2}{1-0.9} = 20$ .

Plug into first equation: $V^\pi(s_1) = 1 + 0.9 \left[0.5 V^\pi(s_1) + 0.5 \cdot 20\right]$ $V^\pi(s_1) = 1 + 0.45 V^\pi(s_1) + 9$ $V^\pi(s_1) - 0.45 V^\pi(s_1) = 10$ $0.55 V^\pi(s_1) = 10$ $V^\pi(s_1) = \frac{10}{0.55} \approx 18.18$

Interpretation: $s_1$ is slightly worse than $s_2$ because you only get reward +1 immediately, then might stay in $s_1$ (prolonging the lower reward) before eventually reaching $s_2$ .

Action-Value Function: Q(s,a)

Why Q vs V?

$V^\pi(s)$ tells you "how good is state $s$ "
$Q^\pi(s,a)$ tells you "how good is taking action $a$ in state $s$ "
Q is more granular—you can improve the policy by comparing Q-values for different actions.

Relationship between Q and V:

$V^\pi(s) = \sum_a \pi(a|s) Q^\pi(s,a)$

Why? The value of a state is the expected Q-value over actions sampled from the policy.

Bellman Equation for $Q^\pi$ :

Derive from first principles. The return after taking action $a$ in state $s$ : $G_t = R_{t+1} + \gamma G_{t+1}$

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

After taking $a$ , you transition to $s'$ , then follow policy $\pi$ from there: $Q^\pi(s,a) = \sum_{s',r} p(s',r|s,a) \left[r + \gamma \sum_{a'} \pi(a'|s') Q^\pi(s',a')\right]$

Why?

Immediate reward $r$ comes from the transition $(s,a) \to s'$
Future value $\sum_{a'} \pi(a'|s') Q^\pi(s',a')$ is just $V^\pi(s')$

Compact form: $\boxed{Q^\pi(s,a) = \sum_{s',r} p(s',r|s,a)\left[r + \gamma V^\pi(s')\right]}$

Or equivalently: $\boxed{Q^\pi(s,a) = \sum_{s',r} p(s',r|s,a)\left[r + \gamma \sum_{a'} \pi(a'|s') Q^\pi(s',a')\right]}$

Worked example Q-Function Calculation

Setup: Same2-state MDP, but now two actions from $s_1$ :

From $s_1$ :
Action $a_1$ : reward +1, go to $s_2$ deterministically
Action $a_2$ : reward +0.5, stay in $s_1$ deterministically
From $s_2$ : only $a_1$ available, reward +2, stay in $s_2$
Policy: $\pi(a_1|s_1) = 0.8$ , $\pi(a_2|s_1) = 0.2$
Discount: $\gamma = 0.9$

Find: $Q^\pi(s_1, a_1)$ and $Q^\pi(s_1, a_2)$ Solution: First, $V^\pi(s_2) = 20$ (computed earlier).

For $Q^\pi(s_1, a_1)$ : $Q^\pi(s_1, a_1) = + 0.9 \cdot V^\pi(s_2) = 1 + 0.9 \cdot 20 = 1 + 18 = 19$

Why? Taking $a_1$ gives immediate reward +1, then you're in $s_2$ which has value 20.

For $Q^\pi(s_1, a_2)$ : $Q^\pi(s_1, a_2) = 0.5 + 0.9 \cdot V^\pi(s_1)$ But we need $V^\pi(s_1)$ : $V^\pi(s_1) = 0.8 \cdot Q^\pi(s_1,a_1) + 0.2 \cdot Q^\pi(s_1,a_2)$ $V^\pi(s_1) = 0.8 \cdot 19 + 0.2 \cdot Q^\pi(s_1,a_2)$ $V^\pi(s_1) = 15.2 + 0.2 \cdot Q^\pi(s_1,a_2)$ Also: $Q^\pi(s_1, a_2) = 0.5 + 0.9 V^\pi(s_1)$ Substitute: $Q^\pi(s_1,a_2) = 0.5 + 0.9(15.2 + 0.2 Q^\pi(s_1,a_2))$ $Q^\pi(s_1,a_2) = 0.5 + 13.68 + 0.18 Q^\pi(s_1,a_2)$ $0.82 Q^\pi(s_1,a_2) = 14.18$ $Q^\pi(s_1,a_2) \approx 17.29$

Interpretation: Action $a_1$ (Q=19) is better than $a_2$ (Q≈17.29) in state $s_1$ . The policy already prefers $a_1$ (80% probability), which aligns with the Q-values.

Optimal Policy and Optimal Value Functions

Key insight: For any MDP, there exists at least one optimal policy $\pi^*$ (may not be unique). Once you know $Q^*(s,a)$ , the optimal policy is: $\pi^*(s) = \arg\max_a Q^*(s,a)$

Why? If you always pick the action with the highest Q-value, you're being greedy with respect to the optimal Q-function, which is the optimal policy.

Bellman Optimality Equation for $V^*$ :

$V^*(s) = \max_a \sum_{s',r} p(s',r|s,a)\left[r + \gamma V^*(s')\right]$

Derivation:

Optimal value = best possible expected return
"Best possible" means choosing the best action at every step
So: $V^*(s) = \max_a Q^*(s,a)$
Substitute the Bellman equation for $Q^*$

Bellman Optimality Equation for $Q^*$ :

$Q^*(s,a) = \sum_{s',r} p(s',r|s,a)\left[r + \gamma \max_{a'} Q^*(s',a')\right]$

Why the max? After taking action $a$ and reaching $s'$ , you act optimally from $s'$ onward, which means taking the action that maximizes $Q^*(s',a')$ .

Worked example Bellman Optimality in Action

Setup: 3-state chain

States: $\{A, B, C\}$
From $A$ : action "right" → go to $B$ , reward +0
From $B$ : action "right" → go to $C$ , reward +1
From $C$ : terminal state, no actions, reward 0 forever
Discount $\gamma = 1$ (no discounting, for simplicity)

Find: $V^*(A)$ , $V^*(B)$ , $V^*(C)$

Solution:

Work backward from the terminal state: $V^*(C) = 0$ Why? Terminal state, no future rewards.

From $B$ : $V^*(B) = \max_a \left[r + \gamma V^*(s')\right] = 1 + 1 \cdot V^*(C) = 1 + 0 = 1$ Why? Only one action available (go right), immediate reward +1, then reach $C$ which has value 0.

From $A$ : $V^*(A) = \max_a \left[r + \gamma V^*(s')\right] = 0 + 1 \cdot V^*(B) = 0 + 1 = 1$

Why? Go right to $B$ , no immediate reward, but $B$ has value 1.

Interpretation: The optimal policy is "go right" from both $A$ and $B$ . The agent gets a total reward of +1 (when transitioning from $B$ to $C$ ).

Common Mistakes

Active Recall

Recall Explain to a12-year-old

Imagine you're playing a video game. You're trying to get the highest score possible.

A policy is your game plan—like "when I see an enemy, I should jump" or "when I find a coin, I pick it up." It's the rules you follow to decide what to do in each situation.

A value function is like a score predictor. It tells you, "If I'm at this spot in the game, following my game plan, how many points will I get from now until the game ends?"

There are two types:

V(s): "How good is this spot?" (Just based on where you are.)
Q(s,a): "How good is doing this specific action at this spot?" (Like, "If I jump right now, how many points will I get?")

The coolest part? You can use Q to improve your game plan: just always do the action with the highest Q-value!

Connections 5.1.01-Introduction-to-RL — Policies and value functions formalize the RL problem

5.1.02-Markov-Decision-Processes — MDPs provide the mathematical framework for defining policies and computing values
5.1.04-Bellman-Equations — Bellman equations are the recursive relationships for V and Q
5.2.01-Policy-Iteration — Uses value functions to iteratively improve policies
5.2.02-Value-Iteration — Directly computes optimal value function, then extracts optimal policy
5.3.01-Q-Learning — Model-free algorithm that learns Q* directly from experience
5.3.03-PolicyGradient-Methods — Directly optimizes parameterized policies $\pi_\theta$

#flashcards/ai-ml

What is a policy in RL? :: A mapping from states to actions (or distributions over actions). It defines the agent's behavior. Deterministic: $a = \pi(s)$ ; Stochastic: $\pi(a|s)$ .

What is the state-value function

V^\pi(s)

The expected cumulative discounted reward starting from state

s

, following policy

\pi

V^\pi(s) = \mathbb{E}_\pi[\sum_{k=0}^\infty \gamma^k R_{t+k+1} | S_t=s]

What is the action-value function

Q^\pi(s,a)

The expected cumulative discounted reward starting from state

s

, taking action

a

, then following policy

\pi

Q^\pi(s,a) = \mathbb{E}_\pi[\sum_{k=0}^\infty \gamma^k R_{t+k+1} | S_t=s, A_t=a]

How are V and Q related?

V^\pi(s) = \sum_a \pi(a|s) Q^\pi(s,a)

. The value of a state is the expected Q-value over actions sampled from the policy.

What is the Bellman expectation equation for

V^\pi

V^\pi(s) = \sum_a \pi(a|s) \sum_{s',r} p(s',r|s,a)[r + \gamma V^\pi(s')]

. It recursively relates the value of a state to the values of successor states.

What is the Bellman expectation equation for

Q^\pi

Q^\pi(s,a) = \sum_{s',r} p(s',r|s,a)[r + \gamma \sum_{a'} \pi(a'|s') Q^\pi(s',a')]

. It decomposes Q into immediate reward plus discounted future Q-values.

What is an optimal policy

\pi^*

A policy that maximizes the value function for all states:

V^{\pi^*}(s) \geq V^\pi(s)

for all

s

and all policies

\pi

How do you extract the optimal policy from

Q^*(s,a)

\pi^*(s) = \arg\max_a Q^*(s,a)

. Choose the action with the highest optimal Q-value in each state.

What is the Bellman optimality equation for

V^*

V^*(s) = \max_a \sum_{s',r} p(s',r|s,a)[r + \gamma V^*(s')]

. The optimal value is the maximum over actions of the expected immediate reward plus discounted successor value.

What is the Bellman optimality equation for

Q^*

Q^*(s,a) = \sum_{s',r} p(s',r|s,a)[r + \gamma \max_{a'} Q^*(s',a')]

. The optimal Q-value is the expected immediate reward plus the discounted maximum Q-value in the next state.

Why use a discount factor

\gamma < 1

Ensures convergence of infinite sums (geometric series), models uncertainty about the future, and represents time preference. Without it, infinite-horizon problems with positive rewards have infinite value.

What's the difference between

V^\pi(s)

and

V^*(s)

V^\pi(s)

is the value under a specific policy

\pi

(average over actions by

\pi

V^*(s)

is the optimal value (maximum over all policies, or equivalently, max over actions).

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Chalो dost, is note ka core idea bahut simple hai. Do cheezein samajhni hain — policy aur value function. Policy matlab tumhaari strategy — kaunse situation (state) mein kya action lena hai. Jaise chess khelte waqt "opponent meri queen pe attack kare toh main use hata dunga" — yeh tumhara plan hai. Value function alag cheez hai — yeh ek critic ki tarah hai jo batata hai ki "yeh position kitni acchi hai long run mein". Matlab abhi ke reward ke saath saath future ke saare rewards ka andaaza. Policy tumhe act karne mein help karti hai, aur value function us policy ko improve karne mein help karta hai — dono milke agent ko smart banate hain.

Ab value function ke andar ek important concept hai — discount factor gamma. Isse hum future rewards ko thoda kam weight dete hain, kyunki aaj ka reward zyada certain hota hai bajaye future ke reward ke. Aur sabse pyaari baat hai Bellman equation — yeh bolta hai ki kisi state ki value = abhi milne wala reward + gamma times next state ki value. Yani problem ko recursive tod diya, ek badi cheez ko chhoti cheezon mein. Yahi trick puri RL ki backbone hai. Aur jab policy ya environment stochastic (random) ho, tab hum expectation (average) lete hain saare possible futures ka — isliye formulas mein summation aur probabilities aati hain.

Yeh matter kyun karta hai? Kyunki jitne bhi real-world RL systems hain — game-playing AI, self-driving cars, stock trading bots, robots — sab isi foundation pe khade hain. Agent ko decide karna hota hai ki har situation mein kya karna hai (policy) aur kaunsa decision long-term mein faayda dega (value function). Agar tum yeh Bellman recursion aur expectation ka funda ache se pakad loge, toh aage ke advanced topics jaise Q-learning aur policy gradients tumhe bilkul easy lagenge. Isliye is chhoti si example ko haath se solve karna zaroor — practice se hi intuition set hoti hai!

What Is a Policy?

State-Value Function: V(s)

Action-Value Function: Q(s,a)

Optimal Policy and Optimal Value Functions

Common Mistakes

Active Recall

Connections 5.1.01-Introduction-to-RL — Policies and value functions formalize the RL problem

Concept Map

Hinglish (regional understanding)

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Reinforcement Learning Foundations

Connections