bellman equations

No. think of a ball in space, if you only give that state and not the previous state how would the model know if the ball is going up or down. I know you are thinking you can just give velocity as state too and that’s right.

but now think about poker, in the immediate state, you only have your cards and the cards on table so you do not know what cards your opponent have and that matters a lot so if you had all previous states you would have been able to tell from how the players played what kind of cards do they have.

is a neural network always a deterministic policy?

if we always pick the answer with highest policy then yes it is deterministic but if we sample then it becomes non deterministic

$${\nu }_{\pi }(s)=\mathbb{E}\pi \left[Rt+1+\gamma R_{t+2}+{\gamma }^2{R}_{t+3}+\dots \mid S_t=s\right]$$

$$v(s)=R_s+\gamma \sum _{s^{\prime }\in S}{P}_{s{s}^{\prime }}v(s^{\prime })$$

both of these equations are equivalent

this means all possible combination of sum of these rewards and probability of its coming, sometimes you will not know all possible values, so you have to use Monte-Carlo to get these R values

Concept	Description	Notation	State Value Formula
Expectation	Following a specific policy and finding V values for various state. we can vectorize to solve this all at once	π	$v\pi$ $(s)$ $=$ $\sum \pi [$ $R+$ $\gamma \sum$ $Pv\pi$ $]$
Optimality	Finding the perfect policy but finding the optimum V values because of the max there, it can not be vectorized	*	$v\ast$ $(s)$ $=$ $ma{x}_a$ $[$ $R+$ $\gamma \sum$ $Pv\ast$ $]$

$P[St+1\mid St]=P[St+1\mid S1,\dots ,St]$ is this like always valid?

if we know the values of P for every state then we do not need to do Reinforcement learning, we can just use the equations above.

---

many people confuse what P really is, its not the probablity of choosing an action. it is the probablity that the action will indeed happen after choosing it. it’s the physics not the choice.

there are cases when we exactly know the p value, for example in chess you know when you move a peice from position A to position B it is 100% gonna move that way but when moving a robot the real physics kicks in and we are not sure

---

Grid World Problem

the question setup

world: a 5x5 grid.

start: (1,1). goal: (5,5).

rewards:

• step reward = 0 for all steps.

• goal reward = +100 (when transitioning into the goal).

• discount factor γ = 0.9.

physics (noisy robot):

• intended direction: 80% chance (0.8).

• slip 90° clockwise: 10% chance (0.1).

• slip 90° counter-clockwise: 10% chance (0.1).

• if slip leads into a wall, robot bounces back to current square.

---

initialization (iteration 0)

at the very beginning, the agent knows nothing.

v(s) = 0 for every single square on the board.

iteration 1 (the first update)

We will focus on square (4,5) — the square immediately above the goal.

Step A: Calculate Q-Values

We must calculate the score for every button the robot can press: down, up, left, right.

The Formula:

$$Q(s,a)=R(s,a)+\gamma \sum P(s\prime \mid s,a)V(s\prime )$$

$$R_s=\mathbb{E}\left[R_{t+1}\mid S_t=s\right]$$

$$R(s,a)=\sum P(s\prime \mid s,a)\times R(s,a,s\prime )$$

---

Action: TRY DOWN

• Physics: 0.8 to Goal, 0.1 to Wall (Stay), 0.1 to (4,4).

Step 1: Calculate Expected Reward R(s,a)

R_down = (0.8×100) + (0.1×0) + (0.1×0) = 80

Step 2: Calculate Expected Future ∑PV

∑PV = (0.8×0) + (0.1×0) + (0.1×0) = 0

(Note: All V are currently 0).

Step 3: Combine

Q_down = 80 + 0.9(0) = 80

Q_down = 80

---

Action: TRY LEFT

• Physics: 0.8 to (4,4), 0.1 to (3,5), 0.1 to Goal (Lucky Slip).

Step 1: Calculate Expected Reward R(s,a)

R_left = (0.8×0) + (0.1×0) + (0.1×100) = 10

Step 2: Calculate Expected Future ∑PV

∑PV = (0.8×0) + (0.1×0) + (0.1×0) = 0

Step 3: Combine

Q_left = 10 + 0.9(0) = 10

Q_left = 10

---

Action: TRY UP

• Physics: 0.8 to (3,5), 0.1 to Wall, 0.1 to (4,4).

Step 1: Calculate Expected Reward R(s,a)

R_up = (0.8×0) + (0.1×0) + (0.1×0) = 0

Step 2: Calculate Expected Future ∑PV

∑PV = 0

Step 3: Combine

Q_up = 0 + 0.9(0) = 0

Q_up = 0

---

Action: TRY RIGHT

• Physics: 0.8 to Wall, 0.1 to Goal (Lucky Slip), 0.1 to (3,5).

Step 1: Calculate Expected Reward R(s,a)

R_right = (0.8×0) + (0.1×100) + (0.1×0) = 10

Step 2: Calculate Expected Future ∑PV

∑PV = 0

Step 3: Combine

Q_right = 10 + 0.9(0) = 10

Q_right = 10

---

Step B: Find V (The Max)

The agent looks at the list of q-values: 80, 10, 0, 10.

It picks the winner:

V(4,5) = max(Q_down, Q_left, Q_up, Q_right)

V(4,5) = max(80, 10, 0, 10)

V(4,5) = 80

Update: We erase the 0 on square (4,5) and write 80.

now you can do this same for 4,4 or 5,4 or 3,5

suppose you calculated for 3,5 and all the other remaining state one by one

this was iteration one, now because of the changed V of 3,5 the V of 4,5 will also change so we will do iteration two calculating the V of all the States agian, and then repeat agian

how would we know where to stop?

Convergence Algorithm

• Set a threshold: e.g., θ = 0.001 (your "good enough" stopping criterion)

• Start a sweep: iterate through all 25 squares

• Calculate change: for each square, compute |v_new - v_old|

• Track maximum change (δ):

  • If square (4,5) changed by 0.6, then δ = 0.6

  • If square (3,5) changed by 0.8, then δ = 0.8

• Check convergence: at end of sweep, is δ < θ?

  • If no (e.g., 0.8 < 0.001? no) → repeat the sweep

  • If yes (e.g., sweep 50: δ = 0.00004 < 0.001) → stop

Policy Evaluation Using Vectorized Equation

We are building the equation:

$$V_{\pi }=(I-\gamma P_{\pi }{)}^{-1}{R}_{\pi }$$

We need to build two giant objects:

1. Vector $R_{\pi }$: A column of 25 numbers.

2. Matrix $P_{\pi }$: A 25×25 grid of probabilities.

---

The Setup (Indices)

To make this "Vectorized," we must flatten the grid.

• Row 1 is States 1-5.

• ...

• Row 4 is States 16-20. State 20 is (4,5).

• Row 5 is States 21-25. State 24 is (5,4). State 25 is (5,5) [Goal].

---

Part 1: Calculating Vector $R_{\pi }$ (Expected Reward)

The Formula:

$$R_{\pi }(s)=\sum _a\pi (a|s)\sum _{s^{\prime }}P(s^{\prime }|s,a)\times R(s,a,s^{\prime })$$

We need to calculate this for State 20 (Coordinate 4,5).

Neighbors:

• Down: Goal (State 25).

• Right: Wall (Bounces back to State 20).

• Left: Empty (State 19).

• Up: Empty (State 15).

We sum the expected cash from all 4 buttons (0.25 chance each).

1. Action: TRY DOWN (Intention: Goal)

• Success (0.8): Enters Goal. Reward = 100.

• Slip Right (0.1): Hits Wall (State 20). Reward = 0.

• Slip Left (0.1): Goes Left (State 19). Reward = 0.

$$\text{Contrib}=0.25\times [(0.8\times 100)+(0.1\times 0)+(0.1\times 0)]=20$$

2. Action: TRY RIGHT (Intention: Wall)

• Success (0.8): Hits Wall. Reward = 0.

• Slip "Right" (0.1): Relative right is Down → Enters Goal. Reward = 100.

• Slip "Left" (0.1): Relative left is Up. Reward = 0.

$$\text{Contrib}=0.25\times [(0.8\times 0)+(0.1\times 100)+(0.1\times 0)]=2.5$$

3. Action: TRY LEFT (Intention: Empty)

• Success (0.8): Goes Left. Reward = 0.

• Slip "Right" (0.1): Relative right is Up. Reward = 0.

• Slip "Left" (0.1): Relative left is Down → Enters Goal. Reward = 100.

$$\text{Contrib}=0.25\times [(0.8\times 0)+(0.1\times 0)+(0.1\times 100)]=2.5$$

4. Action: TRY UP (Intention: Empty)

• Success (0.8): Goes Up. Reward = 0.

• Slips (0.1/0.1): Go Left/Right. Reward = 0.

$$\text{Contrib}=0$$

Total Expected Reward for State 20

R(20) = 20 + 2.5 + 2.5 + 0 = 25

(We would repeat this exact math for State 24 (5,4) and get 25. All other states are 0).

The Final Vector R:

$$R=[0,\dots ,0,25_{\text{(index 20)}},0,0,0,25_{\text{(index 24)}},0]$$

---

Part 2: Calculating Matrix P_π (Transitions)

The Formula:

$$P_{\pi }(s_{\text{from}},s_{\text{to}})=\sum _a\pi (a|s_{\text{from}})\times P(s_{\text{to}}|s_{\text{from}},a)$$

We need to fill Row 20 (State 4,5) of the matrix. This row tells us: "If I start at (4,5), what is the probability I land in X?"

We calculate the probability for each possible destination.

Destination A: The Goal (State 25)

Which actions can take us to the Goal (Down)?

1. Try Down (0.25): Success chance is 0.8 → (0.25 × 0.8) = 0.2

2. Try Left (0.25): Slip "Left" (which is Down) chance is 0.1 → (0.25 × 0.1) = 0.025

3. Try Right (0.25): Slip "Right" (which is Down) chance is 0.1 → (0.25 × 0.1) = 0.025

4. Try Up (0.25): Cannot reach Goal.

Total Prob to Goal:

$$P(20\to 25)=0.2+0.025+0.025=0.25$$

Destination B: The Wall/Self (State 20)

Which actions leave us at State 20? (Hitting the wall to the Right).

1. Try Right (0.25): Success (Hit wall) chance is 0.8 → (0.25 × 0.8) = 0.2

2. Try Up (0.25): Slip "Right" (Hit wall) chance is 0.1 → (0.25 × 0.1) = 0.025

3. Try Down (0.25): Slip "Right" (Hit wall) chance is 0.1 → (0.25 × 0.1) = 0.025

4. Try Left (0.25): Cannot hit Right wall.

Total Prob to Self:

$$P(20\to 20)=0.2+0.025+0.025=0.25$$

Destination C: Left (State 19)

Which actions take us Left?

1. Try Left (0.25): Success 0.8 → 0.2

2. Try Up (0.25): Slip Left 0.1 → 0.025

3. Try Down (0.25): Slip Right (relative to Down is Left on map) 0.1 → 0.025

Total Prob to State 19:

$$P(20\to 19)=0.25$$

Destination D: Up (State 15)

(Same logic as above)

Total Prob to State 15:

$$P(20\to 15)=0.25$$

---

Part 3: The Final Matrix Equation

Now we have our ingredients.

1. R: A vector with 25s at indices 20 and 24.

2. P: A matrix where Row 20 has 0.25 at indices [15, 19, 20, 25].

Now we solve:

$$V=(I-0.9P{)}^{-1}R$$

tic-tac-toe with bellman equations

To use the Bellman equation, we must force tic-tac-toe to fit into the tuple $(s,a,p,r,\gamma )$.

In the grid world, this was easy:

• State: Where am I? (square 1–25)

• Physics: The wind

In tic-tac-toe, it is harder. We are player X. The opponent is player O.

1. The State $(s)$

In grid world, a state was a coordinate $(x,y)$.

In tic-tac-toe, a state is the board configuration.

Imagine a list of 9 numbers representing the 3×3 grid:

• 0 = empty

• 1 = X (us)

• 2 = O (opponent)

Example state: $[1,0,2,0,1,0,0,0,0]$.

This is a specific "square" on our massive mental map.

2. The Action $(a)$

Definition: Placing an X in an empty spot.

Constraint: You cannot play in a spot that is already 1 or 2.

3. The Reward $(r)$

We need to define the motivation.

Grid world: step = 0, goal = +100.

Tic-tac-toe:

• We win (3 Xs): $+100$

• We lose (3 Os): $-100$ (this is new; grid world did not have death)

• Draw (full board, no winner): $0$ (or maybe $-10$ to discourage boring games, but we will stick to 0)

• Ongoing game: $0$

4. The Discount Factor $\gamma$

Let $\gamma =0.9$.

Why? If we can win in 1 move, we want that more than winning in 3 moves. Discounting creates urgency.

The Big Logical Hurdle: The Physics $(p)$

This is the most critical concept to understand.

In grid world, when we chose "action down," the environment (physics) calculated the result:

• Agent moves

• Wind blows

• New state

In tic-tac-toe, the environment includes the opponent.

Steps:

1. We choose a move (place X)

2. The environment processes our move, but the state is not "ours" yet. It is not our turn again yet

3. The opponent places an O

4. New state: it is our turn again

Crucial logic:

From the perspective of the Bellman equation, we do not see the opponent moving. The opponent is just a force of nature, like the wind.

We make a move, we close our eyes, the "wind" (opponent) blows, and we open our eyes to see a new board setup with an extra O on it.

Therefore, $p(s^{\prime }\mid s,a)$ depends entirely on how the opponent plays.

We have two choices for designing our "physics":

• The drunk opponent: The opponent plays randomly (environment is stochastic / noisy)

• The god opponent: The opponent plays perfectly (environment is adversarial)

Decision: To learn the logic of MDPs, we will build the AI to crush a random opponent (the drunk opponent).

This fits our previous math perfectly: $p$ is the probability distribution of the opponent's random moves.

---

Module 2: The Map (The State Space)

We need to list every possible situation the agent could ever find itself in.

1. The Coordinate System

In grid world, a state was $(x,y)$.

In tic-tac-toe, a state is a tuple of 9 numbers $(0=\text{empty},1=X,2=O)$.

Start state: $(0,0,0,0,0,0,0,0,0)$.

This is our "state $(1,1)$" equivalent. The journey begins here.

2. The Size of the World

How big is our matrix going to be?

Mathematically: There are 3 options per square and 9 squares.

Calculation: $3^9=19,683$ combinations.

But most of these are impossible:

• You cannot have a board with 9 Xs and 0 Os

• You cannot have a board where both X and O have won simultaneously

The "turn" logic:

Since we defined the transition as "I move, then opponent moves," our agent only gets to make decisions when it is X's turn.

This means we only care about states where $\text{count}(X)=\text{count}(O)$.

(Because X goes first. At the start: 0 vs 0. After round 1: 1 vs 1.)

If we filter out the impossible states, the number of valid states drops to roughly 5,000.

Conclusion: 5,000 is tiny. A computer can solve a $5,000\times 5,000$ matrix in milliseconds. We are safe to use the exact Bellman equations.

3. The Terminal States (The Cliffs and Goals)

In grid world, we had the goal (+100) and the rest were normal.

In tic-tac-toe, the game can end in three ways. We need to identify these terminal states because $v(s)$ for these states is fixed. We do not calculate them; we assign them.

We classify every state into 4 categories:

• X won (e.g., 3 Xs in a row)Value: $+100$Status: terminal, game over

• O won (e.g., 3 Os in a row)Value: $-100$Status: terminal, game over

• Draw (board full, no winner)Value: $0$Status: terminal, game over

• In progress (none of the above)Value: unknown. This is what we need to calculate.

---

Module 3: The Physics (The Opponent)

We need to define a function $\text{get\_transitions}(s,a)$ that returns a list of possible outcomes and their probabilities.

The Inputs

• $s$: the current board (e.g., $[1,0,0,\dots ]$)

• $a$: the index where we place our X (e.g., index 2)

The Logic Flow

Phase 1: My Move (Deterministic)

• Take the board state

• Place a 1 (X) at the action index

• Call this $\text{temp\_board}$

Phase 2: Check for Instant Win

• Did we just make 3 Xs in a row?

• If yes: the transition is complete

  • Outcome: $\text{temp\_board}$

  • Probability: $1.0$

  • Reward: $+100$

  • Stop here. The opponent does not get to move.

Phase 3: Check for Draw

• Is $\text{temp\_board}$ full (and X did not win)?

• If yes: the transition is complete

  • Outcome: $\text{temp\_board}$

  • Probability: $1.0$

  • Reward: $0$

Phase 4: The Opponent's Turn (Probabilistic)

If the game is not over, the opponent moves.

• Identify all 0s (empty spots) remaining on $\text{temp\_board}$

• Suppose there are 4 empty spots left

• Since the opponent is random, they have a $1/4$ chance of picking each spot

Phase 5: Generate Next States $s^{\prime }$

For each of the 4 empty spots:

• Create a copy of $\text{temp\_board}$

• Place a 2 (O) in that spot

• This new board is a possible $s^{\prime }$

Probability: $1/\text{count}(\text{empty})$

Reward:

• If this new board is an "O winner": reward = $-100$

• If not: reward = $0$

Example Trace (The Mental Model)

Current state $s$:

$$\begin{gathered} [1,0,2] \\ [0,1,0] \\ [0,0,0] \end{gathered}$$

We have 2 Xs and 1 O. It is our turn.

My action $a$: place X at top-middle (index 1).

Phase 1 (my move):

Board becomes:

$$\begin{gathered} [1,1,2] \\ [0,1,0] \\ [0,0,0] \end{gathered}$$

Phase 2/3 (check): Did we win? No. Draw? No.

Phase 4 (opponent):

There are 5 empty spots left.

Opponent has $1/5$ chance for each.

Phase 5 (outcomes):

• Outcome 1: opponent plays at position (1, 0) New board $s_1^{\prime }$: $[1,1,2],[2,1,0],[0,0,0]$ Probability: $0.2$. Reward: $0$

• Outcome 2: opponent plays at (1, 2)New board $s_2^{\prime }$: ...Probability: $0.2$. Reward: $0$

• ...

• Outcome 5: opponent plays at (2, 2)Probability: $0.2$. Reward: $0$

Conclusion: For this specific state–action pair $(s,a)$, our physics tells us there are 5 possible futures, each with probability $0.2$.

When we calculate the value $v(s)$, we will average the values of these 5 futures.

---

Module 4: The Solution (Value Iteration Logic)

We need a dictionary called $v$.

• Key: the board state (tuple)

• Value: the score (float)

Step 0: Initialization

• Generate all valid legal states (where $\text{count}(X)=\text{count}(O)$)

• Set $v[s]=0$ for everything

Identify the terminal states inside this list (game-over states) and permanently lock their values:

• If X won: $v[s]=100$

• If O won: $v[s]=-100$

• If draw: $v[s]=0$

Step 1: The Loop (Repeat Until Convergence)

Loop through every non-terminal state $s$ in the list.

Step 2: The "Max" Calculation (Inside the Loop)

For a specific state $s$:

1. Identify all empty spots (possible actions $a$)

2. For each action $a$:

• Call the physics function (Module 3)

• Get the list of futures: $[(p_i,s_i^{\prime },r_i),\dots ]$

• Calculate the Q-value:

$$Q(s,a)=\sum _i{p}_i\cdot [r_i+0.9\cdot v[s_i^{\prime }]]$$

1. Find the best action:$\text{best\_score}=\max (Q(s,a_1),Q(s,a_2),\dots )$

2. Update the dictionary:$v[s]=\text{best\_score}$

Step 3: Check Convergence

• Did any value in the dictionary change by more than $0.001$?

  • Yes: repeat the loop

  • No: done. Tic-tac-toe is solved.

---

The Final Product: The Optimal Policy

Once the loop finishes, we have a dictionary $v$ filled with numbers.

• $v[\text{start}]$ might be roughly 60 (meaning "we can probably win")

• $v[\text{almost\_dead}]$ might be $-90$ (meaning "we are almost doomed")

How to play:

1. Look at the real board $s$

2. Look at every possible move $a$

3. For each move, peek into the future using the physics to see the resulting $s^{\prime }$

4. Check $v[s^{\prime }]$ for those futures

5. Pick the move that leads to the highest value

model based vs model free

if the agent knows the rewards and transition probabilities then it is model based else it is model free. I always get confused in this.

one good example is Atari games. if we only give it the screenshots then it is model free but if we give it the source code of what exactly would happen if it would press the up button then it is model based

sometimes the ps matrix gets too large to fit in computer ram in those cases also we consider model free approaches

montie carlo

The Update Rule

The incremental Monte Carlo (MC) prediction rule is:

$$V(S_t)\leftarrow V(S_t)+\alpha (G_t-V(S_t))$$

This moves the value estimate toward the observed return $G_t$, where $\alpha$ is a step size (often $\alpha =1/N(s)$ to compute a running average).

Episode 1: Every-Visit MC Updates

Initial state:

$V=\{S_1:0,S_2:0,S_3:0\}$, $N=\{S_1:0,S_2:0,S_3:0\}$

Episode trajectory:

$$S_1\to S_2\to S_3\to S_2\to S_4$$

Returns:

$$G_1=-4,G_2=-3,G_3=-2,G_4=-1$$

note : these are G not R.

$$G_t=R_{t+1}+G_{t+1}$$

we visited 5 states but got only 4 rewards why?

time (t) | state (S_t) | return (G_t) | notes t = 1 | S_1 | G_1 = -4 | t = 2 | S_2 | G_2 = -3 | first visit to S_2 t = 3 | S_3 | G_3 = -2 | t = 4 | S_2 | G_4 = -1 | second visit to S_2

here is the breakdown of your specific trajectory ($S_1\to S_2\to S_3\to S_2\to S_4$): start at S_1 (you haven't done anything yet, so no reward yet). move $S_1\to S_2$: you get reward 1. move $S_2\to S_3$: you get reward 2. move $S_3\to S_2$: you get reward 3. move $S_2\to S_4$: you get reward 4.

The sample-average version uses $\alpha =1/N(s)$ after incrementing the counter:

$$V(s)\leftarrow V(s)+\frac{1}{N(s)}(G-V(s))$$

Backward update loop:

• State $S_2$ (from $t=4$): $N[S_2]=1$ $V[S_2]=0+\frac{1}{1}\cdot (-1-0)=-1$

• State $S_3$ (from $t=3$): $N[S_3]=1$ $V[S_3]=0+\frac{1}{1}\cdot (-2-0)=-2$

• State $S_2$ (from $t=2$): $N[S_2]=2$ $V[S_2]=-1+\frac{1}{2}\cdot (-3-(-1))=-2$

• State $S_1$ (from $t=1$): $N[S_1]=1$ $V[S_1]=0+\frac{1}{1}\cdot (-4-0)=-4$

After episode 1:

$$V=\{S_1:-4,S_2:-2,S_3:-2\}$$

Are These Values Optimal?

No. These are estimates of the value function for the policy being followed, i.e., $v_{\pi }(s)={\mathbb{E}}_{\pi }[G_t\mid S_t=s]$, not the optimal value function $v_{\ast }(s)$.

Monte Carlo policy evaluation answers: "How good is my current strategy $\pi$ on average?" because it only averages returns generated while following $\pi$.

How to Get Optimal Values (MC Control, GPI)

To get $v_{\ast }(s)$ (or more commonly $q_{\ast }(s,a)$ in model-free control), Monte Carlo must be combined with policy improvement inside the Generalized Policy Iteration (GPI) loop: evaluate the current policy, then improve it, then repeat.

Policy improvement is done by moving the policy toward a greedy one with respect to the current value estimates. In practice, this usually means using an $ϵ$ -greedy policy with respect to $Q(s,a)$ to keep exploring.

but you told that in model free we do not get rewards!

no! we do get rewards, but from the environment directly the agent does not have the source code

TD Learning

TD(0) Learning

Update Rule:

$$V(S_t)\leftarrow V(S_t)+\alpha [R_{t+1}+\gamma V(S_{t+1})-V(S_t)]$$

MC Target ($G_t$): $R_{t+1}+\gamma R_{t+2}+{\gamma }^2{R}_{t+3}+\cdots$ (sum of all actual future rewards)

TD Target: $R_{t+1}+\gamma V(S_{t+1})$ (actual reward for next step + estimated value of landing state)

Example Episode

Episode: $S_1\to S_2\to S_3\to S_2\to S_4$ (terminal)

Rewards: -1, -1, -1, -1, 0

Parameters: $\gamma =1$, $\alpha =0.1$

Initial state: $V(S_1)=V(S_2)=V(S_3)=V(S_4)=0$

Step-by-Step Updates

Step 1: Agent in $S_1$, moves to $S_2$

• Reward: -1

• Current estimate: $V(S_2)=0$

• TD target: $-1+1\times 0=-1$

• Update: $V(S_1)\leftarrow 0+0.1[-1-0]=-0.1$

• Note: In MC, nothing would be updated yet!

Step 2: Agent in $S_2$, moves to $S_3$

• Reward: -1

• TD target: $-1+1\times 0=-1$

• Update: $V(S_2)\leftarrow 0+0.1[-1-0]=-0.1$

Step 3: Agent in $S_3$, moves to $S_2$

• Reward: -1

• Current estimate: $V(S_2)=-0.1$ (from previous step!)

• TD target: $-1+1\times (-0.1)=-1.1$

• Update: $V(S_3)\leftarrow 0+0.1[-1.1-0]=-0.11$

Step 4: Agent in $S_2$ (again), moves to $S_4$ (terminal)

• Reward: -1

• TD target: $-1+1\times 0=-1$

• Update: $V(S_2)\leftarrow -0.1+0.1[-1-(-0.1)]=-0.19$

---

2-Step TD Update

Initial state: $V(S_1)=V(S_2)=V(S_3)=V(S_4)=0$

Time t=1: Agent in $S_1$, takes action, receives ($S_2$, $R=-1$)

• Cannot perform 2-step update yet (need to see $R_{t+2}$)

Time t=2: Agent in $S_2$, takes action, receives ($S_3$, $R=-1$)

• Now can perform 2-step update for $S_1$ (state at t=1)

• $R_{t+1}=-1$ (reward $S_1\to S_2$)

• $R_{t+2}=-1$ (reward $S_2\to S_3$)

• $S_{t+2}=S_3$, $V(S_3)=0$

• 2-step return: $G^{(2)}=R_{t+1}+\gamma R_{t+2}+{\gamma }^{2}V(S_{t+2})=-1+1(-1)+1(0)=-2$

• Update: $V(S_1)\leftarrow 0+0.1[-2-0]=-0.2$

Time t=3: Agent in $S_3$, takes action, receives ($S_4$, $R=0$)

• Now can perform 2-step update for $S_2$ (state at t=2)

• $R_{t+1}=-1$ (reward $S_2\to S_3$)

• $R_{t+2}=0$ (reward $S_3\to S_4$)

• $V(S_4)=0$ (terminal state)

• 2-step return: $G^{(2)}=-1+1(0)+1(0)=-1$

• Update: $V(S_2)\leftarrow 0+0.1[-1-0]=-0.1$

End of episode: Episode over, no more 2-step updates

Final V-table:

• $$V(S_1)=-0.2$$

• $$V(S_2)=-0.1$$

• $V(S_3)=0$ (never target of 2-step update)

• $$V(S_4)=0$$

The 2-step update is less biased than 1-step: it correctly learned that $S_1$ is worse than $S_2$ because it's further from the goal.

---

n-Step Returns

$$G_t^{(1)}=R_{t+1}+\gamma V(S_{t+1})$$

$$G_t^{(2)}=R_{t+1}+\gamma R_{t+2}+{\gamma }^{2}V(S_{t+2})$$

$$G_t^{(n)}=R_{t+1}+\gamma R_{t+2}+\cdots +{\gamma }^{n-1}{R}_{t+n}+{\gamma }^{n}V(S_{t+n})$$

$$G_t^{(\infty )}=R_{t+1}+\gamma R_{t+2}+\cdots +{\gamma }^{T-t-1}{R}_T+{\gamma }^{T-t}V(S_T)$$

Since $V(S_T)=0$ for terminal states:

$$G_t^{(\infty )}=R_{t+1}+\gamma R_{t+2}+\cdots =G_t$$

Key Insight: The "infinity-step" return is just the Monte Carlo return! TD(0) and MC are two extremes of the same spectrum of n-step returns.

---

TD(λ) - Weighted Average

$$G_t^{\lambda }=(1-\lambda )\sum _{n=1}^{\infty }{\lambda }^{n-1}{G}_t^{(n)}$$

Example with $\lambda =0.9$:

• Weight for 1-step: $(1-0.9)\times 0.9^0=0.1\times 1=10\%$

• Weight for 2-step: $(1-0.9)\times 0.9^1=0.1\times 0.9=9\%$

• Weight for 3-step: $(1-0.9)\times 0.9^2=0.1\times 0.81=8.1\%$

• ...and so on

The $\lambda$-return is an exponentially decaying average of n-step returns. It says: "I mostly trust short-term returns (1-step, 2-step), but give a little weight to long-term returns in case they have useful information."

But computing this requires the whole episode (like MC). To avoid that, we use the backward view with eligibility traces.

---

Eligibility Traces (Backward View)

TD(λ) Backward View Update Formulas:

${\delta }_t=R_{t+1}+\gamma V(S_{t+1})-V(S_t)$ (TD error)

$E_t(s)=\gamma \lambda E_{t-1}(s)+1(S_t=s)$ (eligibility trace update)

$V(s)\leftarrow V(s)+\alpha {\delta }_t{E}_t(s)$ (value update for all states)

Initial state:

$$V=\{S_0:0,S_1:0,S_2:0\}$$

$E=\{S_0:0,S_1:0,S_2:0\}$ (eligibility traces)

Time t=1: Agent at S₀, moves to S₁

• Trace decay: All traces decay by $\gamma \lambda =0.5$ (still zeros)

• Trace increment: Visiting $S_0$, so $E(S_0)\leftarrow E(S_0)+1=1$

• $$E=\{S_0:1,S_1:0,S_2:0\}$$

• TD error: ${\delta }_0=R_1+\gamma V(S_1)-V(S_0)=1+0-0=1$

• Update all states: $V(s)\leftarrow V(s)+\alpha \delta E(s)$

• $$V(S_0)\leftarrow 0+1\times 1\times 1=1$$

• $V(S_1)\leftarrow 0$, $V(S_2)\leftarrow 0$

After step 1: $V=\{S_0:1,S_1:0,S_2:0\}$, $E=\{S_0:1,S_1:0,S_2:0\}$

Time t=2: Agent at S₁, moves to S₂ (terminal)

• Trace decay: $E(S_0)\leftarrow 1\times 0.5=0.5$

• $$E=\{S_0:0.5,S_1:0,S_2:0\}$$

• Trace increment: Visiting $S_1$, so $E(S_1)\leftarrow 0+1=1$

• $$E=\{S_0:0.5,S_1:1,S_2:0\}$$

• TD error: ${\delta }_1=R_2+\gamma V(S_2)-V(S_1)=1+0-0=1$

• Update all states:

• $$V(S_0)\leftarrow 1+1\times 1\times 0.5=1.5$$

• $$V(S_1)\leftarrow 0+1\times 1\times 1=1$$

• $$V(S_2)\leftarrow 0$$

Final V-table after one episode:

$V(S_0)=1.5$, $V(S_1)=1.0$, $V(S_2)=0.0$

---

Intuition: Credit Flow

At time $t=5$, the agent is surprised: ${\delta }_5=R_6+\gamma V(S_6)-V(S_5)$

This "surprise" needs to propagate backward to update past states.

Eligibility trace $E_t(s)$: Tracks "how responsible" state $s$ is for the current situation.

• When we visit state $s$: $E(s)\leftarrow E(s)+1$

• At every step, all eligibility decay: $E(s)\leftarrow \gamma \lambda E(s)$

Update rule: When surprise ${\delta }_t$ happens at time $t$, update every state according to its eligibility:

$$V(s)\leftarrow V(s)+\alpha {\delta }_t{E}_t(s)$$

Q learning

Why V-Values Need a Model

So far, we've only learned how to evaluate a strategy. But to find the best policy using V-values, you need a model of the environment.

You have to look at your neighboring states and ask: "If I take action 'right', what's the probability I land in that high-value state?" Without the transition probability matrix $P$, you're stuck.

The Hallway Problem

Imagine you're a robot standing in a hallway $s$. There are two doors in front of you: Door 1 and Door 2.

You have a perfect V-table:

• $V(\text{kitchen})=+100$ (delicious cake)

• $V(\text{basement})=-100$ (scary monster)

The Decision:

You want to act greedily—you want to go to the kitchen. Which door do you open?

You don't know.

Knowing that the kitchen is valuable is useless unless you know which action connects the hallway to the kitchen.

• Does Door 1 → kitchen?

• Does Door 2 → kitchen?

You need the transition matrix $P$ to tell you: $P(\text{kitchen}\mid \text{hallway},\text{Door 1})=1.0$

Without that model, having V-values is like having a map of treasure but no compass. You know where you want to be, but not how to move there.

The Q-Value Solution (Model-Free Control)

Now imagine you have a Q-table instead:

• $$Q(\text{hallway},\text{Door 1})=+100$$

• $$Q(\text{hallway},\text{Door 2})=-100$$

The Decision:

Which door do you open? Door 1.

You don't need to know where it leads. You don't need to know it leads to the kitchen. You just need to know that opening Door 1 is worth 100 points.

• V-values: Require a model $P$ to convert state-values into actions

• Q-values: Do not require a model—the value is attached directly to the action

---

Q-Learning Update Rule

$$Q(s_t,a_t)\leftarrow Q(s_t,a_t)+\alpha \left[r_{t+1}+\gamma \underset{a}{\max }Q(s_{t+1},a)-Q(s_t,a_t)\right]$$

Let's break down the target. It's almost identical to the TD(0) target, but with one crucial difference.

TD(0) Target

$$r_{t+1}+\gamma V(s_{t+1})$$

(immediate reward) + (gamma × the value of the state you landed in)

Q-Learning Target

$$r_{t+1}+\gamma \underset{a}{\max }Q(s_{t+1},a)$$

(immediate reward) + (gamma × the value of the best possible action you can take from where you landed)

---

The Q-Learning Algorithm

Initialize

Create a Q-table (dictionary or matrix) with $Q(s,a)=0$ for every state-action pair.

Loop for Many Episodes

1. Start in state $s$

2. Loop for each step of the episode:

• Choose action: Select action $a$ from state $s$ using ε-greedy policy

• Take action: Execute $a$, observe reward $r$ and next state $s^{\prime }$

• Update: Apply the Q-learning update rule

  • Find best Q-value for next state: $\text{max\_q\_next}={\max }_{a}Q(s^{\prime },a)$

  • Calculate TD target: $\text{target}=r+\gamma \times \text{max\_q\_next}$

  • Update Q-value: $Q(s,a)\leftarrow Q(s,a)+\alpha \times (\text{target}-Q(s,a))$

• Move: Update state $s\leftarrow s^{\prime }$

• If $s$ is terminal, end episode

---

SARSA(λ) Algorithm

At each time $t$, the agent does the following:

1. Take action $a_t$, observe $r_{t+1}$ and $s_{t+1}$

2. Choose next action $a_{t+1}$ from $s_{t+1}$ using ε-greedy policy

3. Calculate 1-step TD error: ${\delta }_t=r_{t+1}+\gamma Q(s_{t+1},a_{t+1})-Q(s_t,a_t)$

4. Decay all traces: $E(s,a)\leftarrow \gamma \lambda E(s,a)$

5. Increment trace for action just taken: $E(s_t,a_t)\leftarrow E(s_t,a_t)+1$

6. Update every Q-value: $Q(s,a)\leftarrow Q(s,a)+\alpha {\delta }_{t}E(s,a)$

Value Estimation

The Problem: Dimensionality

In tabular RL, we assumed we could maintain a uniquely addressable memory cell for every state $s\in S$.

v[s] ← ...

This works for tic-tac-toe ($|S|\approx 5\times 10^3$).

This fails for a robotic arm with 7 joints, where each joint angle is a continuous number: $|S|=\infty$

Even if we discretize the angles, if the state space is defined by $n$ variables, the number of states grows exponentially with $n$. This is the curse of dimensionality. We cannot store the value; we must estimate it.

Module 2: Parameterization

We replace the lookup table $V(s)$ with a function approximator $\hat{V}(s,w)$.

• $s$: the input state (vector)

• $w$: a vector of weights (parameters)

• $\hat{V}$: a differentiable function (e.g., linear combination, neural network)

Module 3: The Objective Function (Minimizing Error)

In supervised learning, we minimize the error between a prediction and a known label. In RL, we minimize the error between our approximate value and the true value $V_{\pi }(s)$.

We define the mean squared value error $\overline{VE}$:

$$\overline{VE}(w)=\sum _{s\in S}\mu (s){\left[V_{\pi }(s)-\hat{V}(s,w)\right]}^2$$

• $V_{\pi }(s)$: the true value of state $s$ (the oracle's answer)

• $\hat{V}(s,w)$: our current estimate given weights $w$

• $\mu (s)$: the state distribution. This tells us how often we visit state $s$. We care more about minimizing error in states we visit frequently than in states we never see.

Goal: Find the weight vector $w$ that minimizes this error.

Module 4: Stochastic Gradient Descent (SGD)

Since we cannot know the true $V_{\pi }(s)$ for all states, we cannot solve this analytically. We use gradient descent.

We want to move $w$ in the direction that reduces the error. The gradient of the squared error with respect to weights $w$ is:

$$\nabla \frac{1}{2}{\left[V_{\pi }(s)-\hat{V}(s,w)\right]}^2=-\left[V_{\pi }(s)-\hat{V}(s,w)\right]\nabla \hat{V}(s,w)$$

$\nabla \hat{V}(s,w)$ is the gradient vector of the function approximator. It tells us: "If I increase weight $w_i$, how much does the value prediction for state $s$ increase?"

Module 5: The "Target" Substitution

There is a problem in the equation above: we do not know the true value $V_{\pi }(s)$.

This is where your previous knowledge comes in. We substitute $V_{\pi }(s)$ with the target provided by our RL algorithms (MC or TD).

Case A: Monte Carlo Function Approximation

Substitute $G_t$ (the actual return) for $V_{\pi }(s)$.

$$w\leftarrow w+\alpha \left[G_t-\hat{V}(s_t,w)\right]\nabla \hat{V}(s_t,w)$$

Case B: Temporal-Difference (TD) Function Approximation (Semi-Gradient)

Substitute $r_{t+1}+\gamma \hat{V}(s_{t+1},w)$ for $V_{\pi }(s)$.

$$w\leftarrow w+\alpha \left[\left(r_{t+1}+\gamma \hat{V}(s_{t+1},w)\right)-\hat{V}(s_t,w)\right]\nabla \hat{V}(s_t,w)$$

The Algorithm

1. Initialize weights $w$ arbitrarily (usually random small numbers)

2. Loop for each episode:

• Initialize $s$

• Loop for each step of the episode:

  1. Act: Choose action $a$ according to policy $\pi$ (e.g., random or greedy)

  2. Observe: Take action $a$, observe reward $r$ and next state $s^{\prime }$

  3. Forward pass (prediction): Feed $s$ into the network to get $\hat{V}(s,w)$

  4. Forward pass (target): Feed $s^{\prime }$ into the network to get $\hat{V}(s^{\prime },w)$

  Crucial: We do not calculate gradients for this pass. We treat this value as a fixed number (a constant).

  1. Calculate TD target: $y=r+\gamma \cdot \hat{V}(s^{\prime },w)$ (if $s^{\prime }$ is terminal, $y=r$)

  2. Calculate TD error (delta): $\delta =y-\hat{V}(s,w)$

  3. Backpropagation (the gradient step): Calculate the gradient $\nabla \hat{V}(s,w)$

  4. Update weights: $w\leftarrow w+\alpha \cdot \delta \cdot \nabla \hat{V}(s,w)$

  5. Transition: $s\leftarrow s^{\prime }$

  6. If $s$ is terminal, break loop

Extension to Q-Learning: How to Handle Actions?

Question: This can only be used for policy evaluation right? For policy control we will have to replace $V(s)$ by $Q(s,a)$ but how will we differentiate between $s$ and $a$ as they are both inputs to neural networks?

Architecture 1: The "Naive" Way (State + Action In)

This fits your mental model. We treat the state and the action as two inputs combined together.

• Input: Concatenate the state vector and the action vector (e.g., one-hot encoded). $[s,a]$

• The network: Processes them together

• Output: A single number: $Q(s,a)$

Architecture 2: The "DQN" Way (Only State In)

This is the industry standard for discrete actions (like Atari, grid world, etc).

• Input: Only the state $(s)$

• The network: A "brain" that processes the situation

• Output: A vector of values, one for each possible action Output node 0: $Q(s,{\text{action}}_0)$ Output node 1: $Q(s,{\text{action}}_1)$...

The Benefit:

• You run the network once

• To act: you just take $\text{argmax}(\text{output\_vector})$

• To calculate target: you just take $\max (\text{output\_vector})$

The Modified Algorithm for Control (DQN)

Here is how the update logic works with Architecture 2.

Forward Pass (Prediction):

Feed $s$ into the network.

Output: $[Q_0,Q_1,Q_2,Q_3]$

Select: Since we actually took action 2 ($a=2$), our "prediction" is specifically $Q_2$.

Forward Pass (Target):

Feed $s^{\prime }$ into the network.

Output: $[Q_0^{\prime },Q_1^{\prime },Q_2^{\prime },Q_3^{\prime }]$

Select max: We want the best future. $\text{max\_q}=\max (\text{output})$

The Loss Calculation:

$$\text{target}=r+\gamma \cdot \text{max\_q}$$

$$\text{loss}=(\text{target}-Q_2{)}^2$$

Stabel DQN

Problem 1: Non-IID Data (The Correlation Problem)

The Assumption: Neural networks assume data is i.i.d. (independent and identically distributed).

In supervised learning (e.g., cats vs dogs), the order of images is random. Picture 1 (cat) has nothing to do with picture 2 (dog).

The RL Reality: RL data is sequential.

• State $s_t$ is almost identical to $s_{t+1}$

• If the robot is in the kitchen, the next 100 frames are all in the kitchen

The Crash:

If you train the network on the live stream of data:

1. The robot is in the kitchen. It adjusts all its weights to maximize rewards in the kitchen

2. In doing so, it overwrites the weights that knew how to navigate the living room

3. It enters the living room, fails immediately (catastrophic forgetting), and spirals out of control

The Hero: Experience Replay (The Memory)

We stop the agent from learning from "right now." Instead, we force it to learn from "memories."

The Component: The Replay Buffer $\mathcal{D}$

• This is a massive circular list (usually size 1,000,000)

• It stores "experiences" or "transitions": $e_t=(s_t,a_t,r_{t+1},s_{t+1},\text{done})$

The Logic:

1. Collect: As the agent plays, we do not train. We just push tuples $(s,a,r,s^{\prime })$ into the buffer

2. Sample: When we are ready to train (e.g., every step), we pause. We reach into the buffer and grab a random batch (e.g., 32 scenarios)

• Sample 1: from 5 minutes ago (kitchen)

• Sample 2: from 2 hours ago (bathroom)

• Sample 3: from 10 seconds ago (garden)

1. Train: We calculate the loss on this randomized batch

Problem 2: The Moving Target

The Assumption: Neural networks assume the target (the label) is fixed.

In supervised learning: this image is a cat. That label will never change.

The RL Reality: The target is self-generated.

Recall the Q-learning target:

$$\text{target}=r+\gamma \underset{a^{\prime }}{\max }Q(s^{\prime },a^{\prime };w)$$

Notice that the weights $w$ are inside the target calculation!

The Crash:

1. The network thinks $Q(s)$ should be higher

2. Gradient descent increases the weights $w$

3. Side effect: Increasing $w$ also increases $Q(s^{\prime })$ (because $s$ and $s^{\prime }$ look similar)

4. Result: The target $(r+\gamma Q(s^{\prime }))$ moves up!

The Loop: The network takes a step toward the target, but the target takes a step away. The dog chases its tail forever. The values spiral to infinity.

The Hero: Target Networks (The Anchor)

We split the brain into two parts.

• This is the actor. It selects actions

• It is updated every single step

• This is a clone of the main network

• It is frozen. It is not updated every step

• It is used only to calculate the target number

The Logic:

We modify the loss function to use the frozen weights for the future guess:

$$\text{target}=r+\gamma \underset{a^{\prime }}{\max }\hat{Q}(s^{\prime },a^{\prime };w^{-})$$

The Sync:

• Step 1 to 9,999: We update $w$ (main) constantly. $w^{-}$ (target) stays stone cold. The target stays fixed. The network can finally converge to it

• Step 10,000: Hard update. We copy the weights from main to target: $w^{-}\leftarrow w$. The target jumps to the new, better location, and freezes again

Data Collection: How the Main Network is Used

Phase 1: The "Warm-Up" (Filling the Buffer)

When you first start the script, the replay buffer is empty. You cannot sample a batch of 32 if the buffer has 0 items.

• Logic: We usually run the agent for 1,000 to 10,000 steps without training at all

• Network: We use the main network (or pure random actions) to generate these steps

• Goal: Just fill the tank with diverse data so the first training step isn't biased towards the start state

Phase 2: The "Steady State" (Interleaved)

Once the buffer is full enough (e.g., $>1,000$ items), we enter the main loop.

The standard DQN implementation (like the one DeepMind used for Atari) actually does not do "many steps" in a row before training. It usually follows a 1-to-1 or 4-to-1 ratio.

1. Step 1: main net acts $\to$ store in buffer

2. Step 2: main net acts $\to$ store in buffer

3. Step 3: main net acts $\to$ store in buffer

4. Step 4: main net acts $\to$ store in buffer

5. Train: sample one batch from buffer $\to$ update main net weights one time

Why don't we do 1,000 steps then 1,000 training updates?

If you run the main network for 1,000 steps without updating it, you are collecting data using an old, stale policy. You want the agent to learn from its improving behavior as fast as possible.

Reinforce

Why REINFORCE? The Continuous Action Problem

DQN is great for Atari (joystick: up, down, left, right).

DQN is impossible for a physical robot arm.

The Problem:

A robot arm has 7 motors. Each motor takes a continuous voltage between -1.0 and +1.0.

Action space: a vector of 7 continuous numbers.

Total actions: infinite.

In DQN, to pick an action, we do argmax(Q(s, a)).

You cannot calculate the max of a function over infinite inputs efficiently. You can't check every possible voltage combination.

The Solution:

Instead of learning "how good is this specific voltage?", we act like a human. We learn a probability distribution.

• Input: state (camera feed)

• Output: "mean: 0.5 volts, standard deviation: 0.1"

• Action: sample from that distribution

The REINFORCE Loop:

1. Initialize policy network ${\pi }_{\theta }$ arbitrarily

2. Loop forever:

• Generate episode: run the current policy until the game ends. Store the history: $(s_0,a_0,r_1),(s_1,a_1,r_2),\dots$

• Calculate returns: go backwards from the end. Calculate $G_t$ for every step:

$$G_t=0$$

$$G_{t-1}=r_t$$

$$G_{t-2}=r_{t-1}+r_t$$

• Update weights: for every step $t$ in the episode:

Calculate the "direction": $\nabla \log \pi (a_t|s_t)$

Update: $\theta \leftarrow \theta +\alpha \cdot {\gamma }^t\cdot G_t\cdot \nabla \log \pi (a_t|s_t)$

• Discard episode: throw away the data (this is on-policy; we can't reuse old data because the probabilities change when $\theta$ changes)

What is $\log \pi (a_t|s_t)$?

Discrete Example: Rock, Paper, Scissors

1. The network output (the distribution) The neural network takes the state as input and outputs a softmax probability distribution over the 3 actions.Output: [rock: 0.1, paper: 0.7, scissors: 0.2]

2. The action ($a_t$)The agent samples from this distribution. Let's say, by chance, it picked rock.Action index: 0.

3. The probability $\pi (a_t|s_t)$ We look at the probability the network assigned to the action we actually took. We picked rock. The probability of rock was 0.1. Therefore: $\pi (a_t|s_t)=0.1$

4. The logWe simply take the natural logarithm (ln) of that number.$\log (0.1)=-2.302$

Continuous Example: Gaussian Policy (Robot Force)

1. The network output (the parameters)Input: state (robot sees a target).Network output:

• Mean ($\mu$) = 2.0 (the robot thinks it should apply 2.0 newtons of force)

• Std dev ($\sigma$) = 1.0 (it's exploring with some noise)

1. The action ($a_t$)The agent samples from this bell curve distribution $\mathcal{N}(2.0,1.0)$.Let's say the random sample comes out as action = 2.0 (exactly on the mean).

2. Calculating the "probability" $\pi (a_t|s_t)$ We plug our action (2.0) into the Gaussian probability density function formula: $f(x)=\frac{1}{\sigma \sqrt{2\pi }}{e}^{-\frac{1}{2}{\left(\frac{x-\mu }{\sigma }\right)}^2}$ Plug in $x=2.0$, $\mu =2.0$, $\sigma =1.0$. The exponent part becomes $e^0=1$. The math simplifies to: $\frac{1}{1.0\times 6.28}\approx 0.3989$ So, the single number is 0.3989. This number represents the "likelihood" of picking 2.0 given that specific curve. Likelihood of 2.0: 0.3989 (high, because it's the center).

3. The log probJust like in the discrete case, we take the log of this number.$\log (0.3989)\approx -0.919$

Reinforce Proof

In our study of reinforcement learning, we began with Value-Based Methods (like Q-Learning). The goal was to solve a prediction problem: "What is the expected future reward from this state/action?" We framed this as minimizing a loss function, typically the Mean Squared Error between our prediction and a target.

Minimize Loss: (V_target − V_prediction)²

We now shift to a fundamentally different approach: Policy-Based Methods. Here, we directly parameterize the policy itself with a neural network, π(a|s;θ). We do not have a "target policy" to match. Our goal is simply to find the weights θ that produce the highest possible score.

---

Chapter 1: The Foundation - The Policy Gradient Theorem (REINFORCE)

1.1 The Objective Function

Let $J(\theta )$ be the objective function we want to maximize. It represents the total expected reward for a policy with weights $\theta$.

$$J(\theta )={\mathbb{E}}_{\tau \sim {\pi }_{\theta }}[R(\tau )]$$

Here, $\tau$ represents a single trajectory (or episode), which is a sequence of states and actions: $\tau =(s_0,a_0,s_1,a_1,\dots )$. The notation ${\mathbb{E}}_{\tau \sim {\pi }_{\theta }}$ means "the average score, averaged over all possible trajectories that our policy ${\pi }_{\theta }$ might generate."

1.2 The Goal: Gradient Ascent

To maximize $J(\theta )$, we must calculate its gradient with respect to the weights, $\nabla J(\theta )$, and take a small step in that direction.

$${\theta }_{\text{new}}\leftarrow {\theta }_{\text{old}}+\alpha \nabla J(\theta )$$

The central challenge is calculating this gradient.

1.3 Derivation of the Policy Gradient

Step 1: Express the Expectation as a Sum

The expectation is the sum of the reward for each possible trajectory, weighted by the probability of that trajectory occurring. The probability of a trajectory, $P(\tau ;\theta )$, is the product of the agent's action probabilities and the environment's transition probabilities (physics).

$$P(\tau ;\theta )=p(s_0)\prod _{t=0}^{T-1}\pi (a_t|s_t;\theta )p(s_{t+1}|s_t,a_t)$$

The objective function can thus be written as:

$$\nabla J(\theta )=\nabla \mathbb{E}[R(\tau )]=\nabla \sum _{\tau }P(\tau ;\theta )R(\tau )$$

Step 2: Move the Gradient Inside the Sum

Since the sum is a linear operator, we can move the gradient inside.

$$=\sum _{\tau }\nabla [P(\tau ;\theta )R(\tau )]$$

Step 3: Apply the Product Rule (and a key insight)

A common point of confusion is why the gradient doesn't apply to the reward term, $R(\tau )$. The gradient we are calculating is ${\nabla }_{\theta }$, the rate of change with respect to our policy's weights. The reward function $R(\tau )$ is a property of the environment, not our agent. The rule "you get +1 for winning" is fixed. Therefore, with respect to $\theta$, $R(\tau )$ is a constant, and its derivative is zero.

Applying the product rule for derivatives $\nabla (f\cdot g)=(\nabla f)g+f(\nabla g)$:

$$\nabla [P(\tau ;\theta )R(\tau )]=({\nabla }_{\theta }P(\tau ;\theta ))\cdot R(\tau )+P(\tau ;\theta )\cdot ({\nabla }_{\theta }R(\tau ))=({\nabla }_{\theta }P(\tau ;\theta ))\cdot R(\tau )+P(\tau ;\theta )\cdot 0$$

This simplifies to:

$$=\sum _{\tau }(\nabla P(\tau ;\theta ))R(\tau )$$

Step 4: The Log-Derivative Trick

This is the core mathematical device that makes policy gradients tractable. Recall from calculus that $\frac{d}{dx}\log (f(x))=\frac{f^{\prime }(x)}{f(x)}$. Rearranging gives us $f^{\prime }(x)=f(x)\cdot \frac{d}{dx}\log (f(x))$. Applying this to our gradient:

$$\nabla P(\tau ;\theta )=P(\tau ;\theta )\cdot \nabla \log P(\tau ;\theta )$$

Substituting this back into our equation:

$$=\sum _{\tau }P(\tau ;\theta )\nabla \log P(\tau ;\theta )R(\tau )$$

Step 5: Convert Back to an Expectation

This step can be confusing. Let's be precise. The definition of an expectation is $\mathbb{E}[X]=\sum P(x)\cdot x$. Here, our "outcome" is a trajectory $\tau$.

• The probability of the outcome is $P(\tau ;\theta )$.

• The "value" of that outcome (the random variable we are averaging) is the entire term $\nabla \log P(\tau ;\theta )R(\tau )$.

So, the sum above is, by definition, the expectation of that value:

$$\nabla J(\theta )={\mathbb{E}}_{\tau \sim {\pi }_{\theta }}[\nabla \log P(\tau ;\theta )\cdot R(\tau )]$$

Step 6: Simplify the Log-Probability of a Trajectory

The gradient $\nabla$ only affects terms that depend on $\theta$. Looking at the formula for $P(\tau ;\theta )$, only the policy terms $\pi (a_t|s_t;\theta )$ depend on $\theta$. Since $\log (ab)=\log (a)+\log (b)$, the gradient of the log-probability of the trajectory simplifies to the sum of the gradients of the log-probabilities of the actions:

$$\nabla \log P(\tau ;\theta )=\sum _{t=0}^T\nabla \log \pi (a_t|s_t;\theta )$$

This gives the Policy Gradient Theorem:

$$\nabla J(\theta )=\mathbb{E}\left[\left(\sum _{t=0}^T\nabla \log \pi (a_t|s_t)\right)\cdot R(\tau )\right]$$

1.4 From Theory to a Practical Algorithm (REINFORCE)

The formula above is still theoretical. We now make two practical simplifications.

Simplification 1: Causality (Using $G_t$)

The formula weights every action in an episode by the total reward for the whole episode. This doesn't make sense: an action at time t cannot influence rewards that came before it. It can be proven that in expectation, we can replace the total reward $R(\tau )$ (which is $G_0$ ) with the return from that step onward, $G_t$. This doesn't change the expected gradient but dramatically reduces its variance.

$$\nabla J(\theta )\approx \mathbb{E}\left[\sum _{t=0}^T{G}_t\cdot \nabla \log \pi (a_t|s_t)\right]$$

full explanation

the original theorem says: "sum up all the gradients for the whole game, then multiply that total by the total score."

$$gradient=({\nabla }_0+{\nabla }_1+{\nabla }_2)\cdot (r_0+r_1+r_2)$$

where:

• ${\nabla }_t$ is shorthand for $\nabla log\pi (a_t|s_t)$

• $(r_0+r_1+r_2)$ is the total reward R(τ)

1. the expansion (foil method on steroids) if we multiply everything out (every term times every term), we get:

gradient = ${\nabla }_0\cdot r_0+{\nabla }_0\cdot r_1+{\nabla }_0\cdot r_2$ + ${\nabla }_1\cdot r_0+{\nabla }_1\cdot r_1+{\nabla }_1\cdot r_2+{\nabla }_2\cdot r_0+{\nabla }_2\cdot r_1+{\nabla }_2\cdot r_2$

now apply: actions cannot affect past rewards, so terms of the form ${\nabla }_t\cdot r_k$with k < t have zero expectation.

cross out:

• $${\nabla }_1\cdot r_0\to 0$$

• $${\nabla }_2\cdot r_0\to 0$$

• $${\nabla }_2\cdot r_1\to 0$$

remaining:

gradient ≈ ${\nabla }_0\cdot (r_0+r_1+r_2)$

• ${\nabla }_1\cdot (r_1+r_2)$

• ${\nabla }_2\cdot (r_2)$

the regrouping (finding $G_t$) define return-to-go:

$$G_t=\sum _{k=t}^T{r}_k$$

then:

• $$for{\nabla }_0:(r_0+r_1+r_2)=G_0$$

• $$for{\nabla }_1:(r_1+r_2)=G_1$$

• $$for{\nabla }_2:(r_2)=G_2$$

1. the final formula so we can rewrite:

$$gradient\approx {\nabla }_0\cdot G_0+{\nabla }_1\cdot G_1+{\nabla }_2\cdot G_2$$

or in summation notation:

$$\sum _{t=0}^T(\nabla log\pi (a_t|s_t)\cdot G_t)$$

Simplification 2: Stochastic Approximation (From $\mathbb{E}$ to a single sample)

We cannot average over an infinite number of episodes. Instead, we play one episode and use its result as a noisy but unbiased sample of the gradient. We drop the $\mathbb{E}$.

$$\nabla J(\theta {)}_{\text{sample}}=\sum _{t=0}^T{G}_t\cdot \nabla \log \pi (a_t|s_t)$$

The Final Update Rule and the "On-Policy" Constraint:

This leads to a subtle but important implementation detail. The total update for the episode, $\Delta {\theta }_{\text{total}}$, is a step in the direction of this summed gradient:

$$\Delta {\theta }_{\text{total}}=\alpha \cdot \nabla J(\theta {)}_{\text{sample}}=\alpha \cdot \sum _{t=0}^T(G_t\cdot \nabla \log {\pi }_t)$$

By the distributive property, we can think of this total update as the sum of contributions from each timestep:

$\Delta {\theta }_{\text{total}}={\sum }_{t=0}^T\Delta {\theta }_t$, where $\Delta {\theta }_t\equiv \alpha \cdot G_t\cdot \nabla \log {\pi }_t$.

You are asking: "If I update $\theta$ at step $t=0$, then $\theta$ changes. When I get to step $t=1$, isn't the data now 'old' because it was generated by the previous $\theta$?"

The answer is Yes, technically you are right.

There are two ways to implement REINFORCE. One is mathematically pure, and one is a "lazy" approximation that works because of small step sizes.

If we follow the derivation strictly, the gradient $\nabla J(\theta )$ is the sum over the whole episode.

$$\nabla J(\theta )\approx \sum _{t=0}^T{G}_t\cdot \nabla \log \pi (a_t|s_t)$$

In a pure implementation, you would do this:

1. Play Episode.

2. Initialize total_gradient = 0.

3. Loop t=0 to T:

• Calculate gradient for step t: $g_t=G_t\cdot \nabla \log \pi (a_t|s_t)$.

• Add to total: total_gradient += g_t.

• DO NOT update $\theta$ yet.

1. After the loop finishes:

• Update $\theta$ ONCE: $\theta \leftarrow \theta +\alpha \cdot \text{total\_gradient}$.

Why this satisfies the proof:

Because $\theta$ stays constant during the calculation, every single term in the sum is calculated using the exact same policy ${\pi }_{\theta }$ that generated the data. The "On-Policy" condition is perfectly satisfied.

This is a version very common in practice (e.g., typical SGD implementations).

1. Loop t=0 to T:

• Calculate gradient for step t.

• Update $\theta$ immediately.

Why is this allowed if it violates the math?

It works because of the Learning Rate ($\alpha$).

In RL, $\alpha$ is usually very small (e.g., 0.0003).

• At $t=0$, we update $\theta$. The weights change by a tiny amount.

• At $t=1$, we use the new weights.

• The Assumption: Because the change was so tiny, ${\pi }_{{\theta }_{\text{new}}}$ is roughly 99.99% identical to ${\pi }_{{\theta }_{\text{old}}}$. The error introduced by this slight drift is negligible compared to the noise in the rewards themselves.

Explanation of how summation was removed

we are just moving parentheses

total (end-of-episode) update: ${\theta }_{n}ew={\theta }_{o}ld+{\sum }_{t=0}^{T}gradien{t}_t$

where $gradien{t}_t=\alpha \cdot G_t\cdot \nabla log\pi (a_t|s_t)$

example: 3 steps (t = 0,1,2) ${\theta }_{n}ew={\theta }_{o}ld+(gra{d}_0+gra{d}_1+gra{d}_2)$

incremental (step-by-step) update: $step0:{\theta }_1={\theta }_{o}ld+gra{d}_0$

$$step1:{\theta }_2={\theta }_1+gra{d}_1$$

$$step2:{\theta }_{n}ew={\theta }_2+gra{d}_2$$

Actor Critic

Welcome to Actor-Critic. This is the architecture that runs the modern world of RL.

You identified the problem with REINFORCE: high variance. $G_t$ is a noisy mess.

The Solution:

Instead of waiting until the end of the episode to see how much reward we got ($G_t$), let's train a second neural network to predict how much reward we will get.

We replace the actual return (Monte Carlo) with an estimated return (TD learning).

Module 1: The Two Brains

In Actor-Critic, the agent is split into two distinct neural networks (or two heads on one body):

• Job: Takes the state, outputs action probabilities.

• Goal: Learn to play the game (policy optimization).

• Analogy: The athlete. They perform the moves.

• Job: Takes the state, outputs a scalar value $V(s)$.

• Goal: Learn to guess the score (value estimation).

• Analogy: The coach. They watch the athlete and yell, "that was a good move!" or "that was terrible!"

Module 2: The Math (The Advantage Function)

In REINFORCE, the update was:

$$\theta \leftarrow \theta +\alpha \cdot \nabla \log \pi (a|s)\cdot G_t$$

In Actor-Critic, we don't use $G_t$. We use the advantage ($A_t$).

The advantage asks: "How much better was this action than what I usually expect?"

$$A_t=\text{reality}-\text{expectation}$$

• The expectation: The critic's current prediction for the state, $V(s)$.

• The reality: The immediate reward plus the value of the next state: $r+\gamma V(s^{\prime })$ (this is the TD target!).

So the advantage is simply the TD error ($\delta$):

$$A_t\approx {\delta }_t=(r+\gamma V(s^{\prime }))-V(s)$$

AtA_tAt (Advantage) is not the same number as GtG_tGt (Return).

You can subtract any value from $G_t$ as long as that value does NOT depend on the action you just took. This value is called a Baseline.

Key idea: Subtracting a baseline does not change the expected policy gradient (the direction the weights move). It only changes the variance (how noisy / shaky the learning signal is).

Policy gradient with a baseline: $\nabla J(\theta )\propto E[\nabla log\pi (a|s)\cdot (G_t-b(s))]$

If we choose the baseline b(s) to be the value function V(s) (i.e., the expected return from state s): $b(s)=V(s)$

Then the learning signal becomes: $G_t-V(s)$

So, advantage can be written as: $A_t=G_t-V(s)$

The Updates:

$$w\leftarrow w+\alpha \cdot \delta \cdot \nabla V(s)$$

$$\theta \leftarrow \theta +\alpha \cdot \delta \cdot \nabla \log \pi (a|s)$$

stability issues like in DQN with Actor critic?

REINFORCE (Monte Carlo Policy Gradient)

The Correlation Problem?

Yes, the data is correlated within an episode.

Can we use Experience Replay?

No.

Why: REINFORCE is an on-policy algorithm. The math $\nabla \log \pi (a|s)$ assumes that the data was generated by the current neural network.

If you use a replay buffer, you are training on data generated by an old version of the network (an old policy). The math breaks down immediately. You cannot use old memories to calculate the gradient for a new policy without complex math corrections (importance sampling).

The Moving Target Problem?

No.

Why: REINFORCE uses the Monte Carlo return ($G_t$) as the target.

• $G_t$ is the actual sum of rewards calculated at the end of the episode.

• $G_t$ comes from the environment (ground truth), not from the neural network's own prediction.

Therefore, the target is stable. You do not need a target network for REINFORCE.

---

Actor-Critic (A2C / A3C)

This is where it gets interesting.

The Correlation Problem?

Yes, data is sequential.

Can we use Experience Replay?

No (usually).

Like REINFORCE, standard Actor-Critic is on-policy. It needs fresh data from the current actor.

Instead of a replay buffer, we make 16 agents play the game at the same time in parallel.

• Agent 1 is in the kitchen. Agent 2 is in the garden. Agent 3 is jumping...

We collect the data from all 16 and average the update.

Result: The data is decorrelated because the 16 agents are in different places, but the data is still "fresh" (on-policy).

The Moving Target Problem?

Yes.

The actor is safe (no bootstrapping), but the critic is learning values ($V$).

The critic's target is $r+\gamma V(s^{\prime })$.

$V(s^{\prime })$ comes from the critic itself! The critic is chasing its own tail, just like in DQN.

• In simple A2C: We often ignore it. Because the updates are smoother than DQN, it sometimes just works without a target network.

• In advanced Actor-Critic (DDPG, SAC, PPO): Yes, we use target networks. For the critic to be stable in complex games, we absolutely need to freeze the target weights ($w^{-}$) just like we did in DQN.

PPO

The Problem with Standard Policy Gradients (REINFORCE)

In algorithms like REINFORCE and A2C (standard Actor-Critic), we follow a strict and inefficient cycle:

1. Collect data with the current policy, ${\pi }_{old}$.

2. Perform one gradient update to get a new policy, ${\pi }_{new}$.

3. Throw away the data.

The data becomes "stale" immediately because it was generated by an old, obsolete policy. The mathematical justification for Policy Gradients relies on the expectation being taken over samples from the same policy being optimized. This is incredibly inefficient. We spent 2048 steps collecting data, and we only used it for a single update. It's like reading a textbook chapter for one second and then burning the book.

The Goal

We want to reuse the old data to perform multiple updates on our new policy. This requires a mathematical bridge to justify using data sampled from ${\pi }_{old}$ to calculate the gradient for ${\pi }_{new}$.

---

2. Importance Sampling: The Mathematical Bridge

We cannot simply plug old data into the new policy's gradient.

• The Goal (What we want): Maximize the expected reward under the New Policy. $J({\theta }_{new})={\mathbb{E}}_{\tau \sim {\pi }_{new}}[R(\tau )]$

• The Constraint (What we have): Data (trajectories $\tau$) sampled from the Old Policy. $\tau \sim {\pi }_{old}$

Your Doubt: "I am reading ${\mathbb{E}}_{\tau \sim {\pi }_{new}}$ as 'improve the new policy'. What does this mean?"

Resolution:

• ${\mathbb{E}}_{\tau \sim {\pi }_{new}}$ does not mean "improve". It means "Calculate the Average using data generated by the new policy."

• $\nabla \log P(\tau ;{\theta }_{old})$ does not mean "from the old data." It means "Calculate the gradient direction for the old policy weights."

If we naively estimate the gradient using old samples without correction, we are calculating ${\mathbb{E}}_{\tau \sim {\pi }_{old}}[\dots ]$, which is biased and mathematically incorrect for optimizing ${\pi }_{new}$. It is like driving a Tesla and using data from a Ford Model T to tune it.

Derivation of the Importance Sampling Ratio

To fix this, we use the Importance Sampling Identity: ${\mathbb{E}}_{x\sim P}[f(x)]={\mathbb{E}}_{x\sim Q}\left[\frac{P(x)}{Q(x)}f(x)\right]$

Let's apply this to our RL objective step-by-step.

Step 1: Write the Goal as a Summation

$$J({\theta }_{new})=\sum _{\tau }P(\tau ;{\theta }_{new})\cdot R(\tau )$$

Step 2: The "Multiply by 1" Trick

Multiply and divide the term inside the sum by the Old Probability $P(\tau ;{\theta }_{old})$. This is valid (algebraic identity):

$$J({\theta }_{new})=\sum _{\tau }\frac{P(\tau ;{\theta }_{old})}{P(\tau ;{\theta }_{old})}\cdot P(\tau ;{\theta }_{new})\cdot R(\tau )$$

Step 3: Rearrange terms to match the Old Policy

We want the summation to look like an Expectation over the Old Policy. To do that, we group $P(\tau ;{\theta }_{old})$ to the front:

$$J({\theta }_{new})=\sum _{\tau }\underset{\text{Sampling Dist.}}{P(\tau ;{\theta }_{old})}\cdot \left[\frac{P(\tau ;{\theta }_{new})}{P(\tau ;{\theta }_{old})}\cdot R(\tau )\right]$$

Step 4: Convert back to Expectation

$$J({\theta }_{new})={\mathbb{E}}_{\tau \sim {\pi }_{old}}\left[\frac{P(\tau ;{\theta }_{new})}{P(\tau ;{\theta }_{old})}\cdot R(\tau )\right]$$

We have solved the mismatch. The expectation is over ${\pi }_{old}$ (matching our data), but the term inside allows us to optimize ${\theta }_{new}$. The bridge is the fraction $\frac{P(\tau ;{\theta }_{new})}{P(\tau ;{\theta }_{old})}$, which is the Importance Sampling Ratio.

Simplifying the Ratio (Canceling the Physics)

The ratio looks scary because it involves the probability of the entire trajectory (Agent + Environment).

$$\frac{P(\tau ;{\theta }_{new})}{P(\tau ;{\theta }_{old})}=\frac{p(s_0)\prod \pi (a_t|s_t;{\theta }_{new})p(s_{t+1}|s_t,a_t)}{p(s_0)\prod \pi (a_t|s_t;{\theta }_{old})p(s_{t+1}|s_t,a_t)}$$

• The start state prob $p(s_0)$ cancels out.

• The environment physics $p(s_{t+1}|s_t,a_t)$ cancel out (since physics don't depend on $\theta$).

We are left with just the ratio of the Agent's Policies:

$$r_t(\theta )=\frac{\pi (a_t|s_t;{\theta }_{new})}{\pi (a_t|s_t;{\theta }_{old})}$$

The Surrogate Objective

This leads to the objective function we actually optimize in PPO, using the Advantage $A_t$ instead of raw Reward to reduce variance (proven below):

$$L^{CPI}(\theta )={\mathbb{E}}_{t\sim {\pi }_{old}}[r_t(\theta )A_t]$$

---

3. The Policy Gradient Theorem & Advantage

Why Replace Reward $R(\tau )$ with Advantage $A_t$?

In the derivation above, we swapped $R(\tau )$ for $A_t$. Are they mathematically equal? No.

$$\sum A_t=R(\tau )-V(s_0)$$

However, replacing $R$ with $A$ yields the exact same gradient direction while significantly reducing variance. This is due to the Baseline Property.

Proof:

1. Definition: $A(s,a)=Q(s,a)-V(s)$.

2. Gradient with Advantage: $\nabla J=\mathbb{E}[\nabla \log \pi (a|s)\cdot (Q(s,a)-V(s))]$

3. Split the terms: $\nabla J=\mathbb{E}[\nabla \log \pi \cdot Q]-\mathbb{E}[\nabla \log \pi \cdot V(s)]$

4. Analyze the second term (The Baseline Term). Since $V(s)$ does not depend on action $a$: $\mathbb{E}[\nabla \log \pi \cdot V(s)]=V(s){\sum }_a\pi (a|s)\nabla \log \pi (a|s)$ Using the log-derivative trick ($\pi \nabla \log \pi =\nabla \pi$): $=V(s){\sum }_a\nabla \pi (a|s)=V(s)\nabla \left({\sum }_a\pi (a|s)\right)$ Since probabilities sum to 1, and the derivative of 1 is 0: $=V(s)\cdot 0=0$

The term cancels out. Therefore, optimizing for Advantage is mathematically equivalent to optimizing for Reward, but with lower variance.

Calculating Advantage (Definition vs. Code)

• Mathematical Definition: $A(s,a)=Q(s,a)-V(s)$.

• In Code (Estimation): We don't have $Q$. We use the Bellman estimate $Q\approx R+\gamma V(s^{\prime })$. $A(s,a)\approx (R+\gamma V(s^{\prime }))-V(s)$ This is exactly the TD Error ($\delta$).

---

---

4. Implementing PPO: Algorithm & Memory

The "Old Policy" Dilemma (Do we store 1000 networks?)

To compute the ratio $r_t(\theta )=\frac{{\pi }_{new}}{{\pi }_{old}}$, it looks like we need to keep a copy of the old neural network in memory.

• Your Question: "But to use this we will have to always store the old neural network and after suppose 1000 policy updates will we be storing 1000 neural networks with us?"

• The Answer: No. We absolutely do not store 1000 neural networks. We store one old copy, and we update it frequently.

The Conceptual Cycle:

1. Start: We have our main network, policy_new.

2. Snapshot: At step 0, we make a copy: policy_old = policy_new.clone(). (Now we have 2 networks in memory).

3. Data Collection: Play 2048 steps using policy_old.

4. Training: Train policy_new for 10 epochs. Calculate the ratio using the live network vs the snapshot.

5. Overwrite: Delete policy_old. Overwrite it with policy_new.

The "Log-Prob" Optimization (The Engineering Trick)

• Your Insight: "If you like really really see we do not need to store the whole neural net just the pie ( at , s ) values for those 2048 steps."

• The Optimization: You are absolutely correct. This is the standard optimization used in every professional implementation. We do NOT need to keep a copy of the old network weights in memory.

Since ${\pi }_{old}$ never changes during the training phase (the 10 epochs), its output for the specific states $s_t$ and actions $a_t$ we collected is constant.

The Optimized Algorithm:

1. Rollout (Data Collection):

• Run the current network (policy).

• It outputs an action $a_t$ and a probability calculation.

• We save the number log_prob_old into our data buffer.

• Crucial: We detach this number from the computation graph. It is just a float (e.g., 0.693).

1. Training Loop:

• We load the batch: states, actions, and the saved numbers log_probs_old.

• We run the current network (policy) on states to get log_probs_new.

• We calculate the ratio: ratio = exp(log_probs_new - log_probs_old).

1. Result:

• log_probs_new has a gradient. log_probs_old is just a constant number.

• Memory Cost: We store 2048 floating-point numbers instead of duplicating a 10-Gigabyte Neural Network.

---

Throwing Away Data (The On-Policy Constraint)

• Your Question: "But this means we are throwing away those 2048 examples? If we are deleting the old policy we will never be able to use those examples again?"

• The Answer: YES. You are absolutely correct. We throw them away.

Once we have squeezed the juice out of those 2048 examples (by training on them for roughly 10 epochs), we delete them forever. This is exactly why PPO is still considered an On-Policy algorithm (or "Near On-Policy"), whereas algorithms like DQN and SAC are Off-Policy.

The Logic for Deletion:

1. The Limits of Importance Sampling: The math trick ($r_t=\frac{{\pi }_{new}}{{\pi }_{old}}$) is mathematically valid for any two distributions. However, the Variance of this estimate depends heavily on how different the two distributions are.

• If ${\pi }_{new}$ is close to ${\pi }_{old}$: The ratio is near 1.0 (e.g., 0.9 or 1.1). The variance is low. The update is safe.

• If ${\pi }_{new}$ is far from ${\pi }_{old}$: The ratio becomes wild (e.g., 0.001 or 1000.0). The variance explodes. The gradient becomes garbage.

1. The Timeline of Decay:

• Cycle 1: We collect data with Network_Version_1. We train Network_Version_2 on it. The difference is small. Math works.

• Cycle 2: We create Network_Version_3. If we tried to use the data from Network_Version_1... the difference between Version 3 and Version 1 is now huge. The Trust Region is broken. The math collapses.

1. The Efficiency Trade-off Table:

Algorithm	Data Usage	Sample Efficiency	Stability
REINFORCE	Use once, delete.	Very Low	Low
PPO	Use ~10-80 times, delete.	Medium	High
DQN / SAC	Store in Replay Buffer (1M capacity), reuse forever.	High	Lower (Harder to tune)

Why PPO is popular despite deleting data: It hits the "Sweet Spot." It reuses data enough to be much faster than REINFORCE, but it deletes the data before it becomes "toxic" (too old to be useful), which keeps the training incredibly stable. If you want to keep data forever, you have to leave PPO and study SAC, which uses fancy math to make old data safe again.

but what if the old state is never visited under the new policy

we do not need to visit the state physically to calculate the ratio

data collection (the past):

• the agent was in state s_123 (a specific observation: image / coordinates).

• it took action a_123.

• we saved that exact state tensor s_123 (and action a_123, and usually logπ_old(a_123 | s_123)) into the buffer.

training loop (the present):

• we take the saved state tensor s_123 and feed it into the current policy network π_new.

• we compute the probability (or log-probability) of the same stored action a_123 under the new policy: π_new(a_123 | s_123).

ratio (importance sampling): $r={\pi }_{n}ew(a_{1}23|s_{1}23)/{\pi }_{o}ld(a_{1}23|s_{1}23)$

so the ratio is computed purely from logged (s, a) and policy evaluation

---

5. Variance Reduction: Generalized Advantage Estimation (GAE)

We need to calculate the input to our Objective Function: The Advantage ($A_t$). $A(s_t,a_t)=Q(s_t,a_t)-V(s_t)$

We have a Critic network that gives us $V(s)$. But we don't have $Q(s,a)$. We have to estimate it using the rewards we collected.

The Problem of Estimation

We have two bad options:

Option A: The Monte Carlo Estimate We use the actual full return $G_t$ as our estimate for $Q$. ${\hat{A}}_t=G_t-V(s_t)$

• Pros: Unbiased. It uses real reality.

• Cons: High Variance. If the game is long/random, $G_t$ bounces around wildly. The training will be unstable.

Option B: The TD(0) Estimate We use the one-step lookahead. ${\hat{A}}_t=R_t+\gamma V(s_{t+1})-V(s_t)$

• Pros: Low Variance. Very stable.

• Cons: High Bias. It relies heavily on $V(s_{t+1})$, which is just a guess made by the Critic. If the Critic is dumb (early in training), this estimate is garbage.

The Solution: We need the TD($\lambda$) slider we discussed earlier. We want to mix these two.

Sparse Reward Problem

in text generation, rewards are often sparse/delayed: many steps get 0 reward, and a final outcome (e.g., at ) provides most of the signal. [web:275]

example trajectory (token-by-token): step 1: "The" (reward: 0) step 2: "cat" (reward: 0) step 3: "sat" (reward: 0) ... step 20: "" (reward: +10)

why 1-step advantage can fail here if we use a simple 1-step TD-style advantage:

$$A_t\approx r_t+\gamma V(s_{t+1})-V(s_t)$$

at step 1 ("The"):

• immediate reward $r_t$ = 0

• so the advantage becomes: $A_1\approx 0+\gamma V("Thecat")-V("The")$

this relies entirely on the critic/value function V(·) to predict long-term reward from very early states, via bootstrapping.

if the critic is weak early on (often ~0 everywhere at the start), then: V("The") ≈ 0 and V("The cat") ≈ 0 => $A_1$ ≈ 0

result: the actor gets ~no learning signal for the early token "The" (credit assignment is difficult when rewards are sparse/delayed).

---

The Magic of the TD Error ($\delta$)

Let's define the TD Error for a single step. This is the difference between "What happened + What I expect next" and "What I expected now." ${\delta }_t=R_t+\gamma V(s_{t+1})-V(s_t)$

Now, watch what happens if we sum up these errors over time.

The 1-Step Advantage: $A_t^{(1)}={\delta }_t$ (This is just Option B above).

The 2-Step Advantage: What if we add the next error (${\delta }_{t+1}$) to the current one? $A_t^{(2)}={\delta }_t+\gamma {\delta }_{t+1}$ Let's expand this to prove a point: $=[R_t+\gamma V(s_{t+1})-V(s_t)]+\gamma [R_{t+1}+\gamma V(s_{t+2})-V(s_{t+1})]$ Notice the $\gamma V(s_{t+1})$ terms cancel out! $=R_t+\gamma R_{t+1}+{\gamma }^{2}V(s_{t+2})-V(s_t)$ This is exactly the 2-step return minus the value!

The k-Step Advantage: If we sum $k$ errors, the intermediate Value predictions cancel out telescopically, and we get the k-step return. ${\sum }_{i=0}^{k-1}{\gamma }^i{\delta }_{t+i}=\text{k-Step Return}-V(s_t)$

---

The GAE Formula

Just like in TD($\lambda$), we don't want to pick a specific "k". We want an exponentially weighted average of ALL of them. We introduce the parameter $\lambda$ (Lambda).

• High $\lambda$: Trust the real rewards (Monte Carlo).

• Low $\lambda$: Trust the Critic (TD).

The Generalized Advantage Estimator is defined as the sum of discounted TD errors: ${\hat{A}}_t^{GAE}={\sum }_{l=0}^{\infty }(\gamma \lambda {)}^l{\delta }_{t+l}$ ${\hat{A}}_t^{GAE}={\delta }_t+(\gamma \lambda ){\delta }_{t+1}+(\gamma \lambda {)}^2{\delta }_{t+2}+\dots$

geometric series identity (for |λ| < 1): ${\sum }_{k=0}^{\infty }{\lambda }^k=1/(1-\lambda )$

gae as an exponentially-weighted mixture: A_GAE = (1 − λ) [ A^(1) + λ A^(2) + λ^2 A^(3) + … ]

---

Recursive Calculation (The Backwards Loop)

We do not calculate that infinite sum for every step. That would be $O(N^2)$. We can calculate it in Reverse in $O(N)$.

Look at the relationship between step $t$ and step $t+1$: ${\hat{A}}_t={\delta }_t+(\gamma \lambda )\underset{\text{This is just }{\hat{A}}_{t+1}}{[{\delta }_{t+1}+(\gamma \lambda ){\delta }_{t+2}+\dots ]}$

So the recursive formula is: ${\hat{A}}_t={\delta }_t+(\gamma \lambda ){\hat{A}}_{t+1}$

Your Doubt: "If $A_t={\delta }_t+(\gamma \lambda )A_{t+1}$, where do we get $A_{t+1}$ from? We start from $t=0$, so we need $A_1$, but we don't have it."

The Solution: This is exactly why we loop backwards.

Let's trace it on a short episode of 3 steps ($t=0,1,2$).

Data We Have:

• ${\delta }_0,{\delta }_1,{\delta }_2$. (Calculated from rewards and values).

Goal:

• Calculate $A_0,A_1,A_2$.

Step 1: Start at the End ($t=2$) The episode ends after step 2. What is the "Future Advantage" ($A_3$)? It is 0. There is no future. So, for the last step: $A_2={\delta }_2+(\gamma \lambda )\cdot \underset{0}{A_3}$ ${\mathbf{A}}_2={\delta }_2$ Now we have $A_2$.

Step 2: Step Back ($t=1$) We need $A_1$. The formula requires $A_2$. We just calculated $A_2$ in the previous step! $A_1={\delta }_1+(\gamma \lambda )\cdot {\mathbf{A}}_2$ Now we have $A_1$.

Step 3: Step Back ($t=0$) We need $A_0$. The formula requires $A_1$. We just calculated $A_1$. $A_0={\delta }_0+(\gamma \lambda )\cdot {\mathbf{A}}_1$ Now we have $A_0$. We are done.

6. Continuous Control: Gaussian Heads

In Atari games (DQN/A2C), the output is a Softmax over discrete buttons (Left, Right, Jump). In Robotics (MuJoCo, PyBullet), the action is a Vector of Continuous Numbers (Torque, Voltage, Velocity). We cannot use Softmax. We must use a Probability Distribution Function (PDF).

The Gaussian Policy

We assume that for any state $s$, the optimal action $a$ follows a Gaussian (Normal) Distribution: $a\sim \mathcal{N}(\mu ,\sigma )$

Our Neural Network (Actor) needs to output two things for every motor joint:

1. Mean ($\mu$): The "ideal" action (The center of the bell curve).

2. Standard Deviation ($\sigma$, or "Scale"): How "unsure" or "random" we should be (The width of the bell curve).

The Architecture:

• Input: State Vector (e.g., Robot Joint Angles).

• Hidden Layers: Dense layers with ReLU.

• Output Head 1: A linear layer outputting Mean ($\mu$).

• Output Head 2: A linear layer outputting Log-Std ($\log \sigma$).

---

Why log_std instead of std? (The Optimization Dynamics)

We need to enforce the constraint that Standard Deviation must be positive ($\sigma \ge 0$). Why don't we just use abs(output) or ReLU(output)?

1. The Gradient Scale Problem

• Option A: Absolute Value ($\sigma =|x|$) If the network outputs $x$, and we need to change $\sigma$ from $1.0$ (High Noise) to $0.001$ (High Precision): The network weights must push the output $x$ linearly from $1.0$ down to $0.001$. This requires a massive change in weights relative to the target precision.

• Option B: Log Space ($\sigma =e^x$) If the network outputs $x$, and we need to change $\sigma$ from $1.0$ to $0.001$:

  • To get $\sigma =1$, output $x=0$.

  • To get $\sigma =0.001$, output $x\approx -7$.

  • The Benefit: The neural network can move across massive orders of magnitude (from huge noise to tiny noise) just by moving the output linearly from $0$ to $-7$. This is much easier for an optimizer to handle.

1. The Zero-Crossing Problem

• The Trap of abs(x): Imagine the network outputs $x=-0.5$, so $\sigma =0.5$. The agent realizes it needs less noise. It pushes $x$ toward 0. If it pushes $x$ too far (e.g., from -0.1 to +0.1), the $\sigma$ goes from $0.1\to 0\to 0.1$. The noise collapsed to zero and then bounced back up.

• The Stability of exp(x): $x$ can range from $-\infty$ to $+\infty$. This entire range maps to a valid, strictly positive $\sigma$. There is no "boundary" at zero. You can keep decreasing $x$ forever to get smaller and smaller $\sigma$ without ever hitting a wall or bouncing back.

---

State-Dependent vs. State-Independent Noise

We need to decide how to generate the $\sigma$.

Option A: State-Dependent (The Network Output) In this setup, the Neural Network takes the State $S$ as input and outputs both $\mu$ and $\log \sigma$.

• Meaning: The agent can choose to be precise ($\text{low }\sigma$) in some states and random ($\text{high }\sigma$) in others.

Option B: State-Independent (The Parameter) In this setup, the Neural Network takes the State $S$ and outputs only $\mu$. The $\log \sigma$ is not calculated by the network layers. It is a separate list of trainable numbers (a tensor) that stands alone.

• Math: $\log \sigma =\text{Parameter Vector }{\theta }_{\sigma }$

• Meaning: The agent has a fixed "randomness level" for every state.

Your Doubt: "The optimizer updates this directly? How?" The Explanation:

1. Define Parameter: We create a variable log_sigma_param = 0.0. We tell the optimizer: "Please optimize this number."

2. Forward Pass: Network predicts $\mu$. We grab log_sigma_param. We calculate probability: log_prob = Gaussian(mu, exp(log_sigma_param)).log_prob(action).

3. Backward Pass: When we call loss.backward(), PyTorch sees that log_sigma_param was used in the math. It calculates the derivative $\frac{\partial Loss}{\partial \text{log\_sigma}}$ and updates the number directly, just like a bias term in a neuron.

---

The Entropy Tug-of-War (Auto-Tuning Exploration)

How does the agent decide whether to increase or decrease this noise parameter? It is determined by two forces fighting in the Loss Function:

$$\text{Total Loss}=\underset{\text{Policy Loss}}{-(A_t\cdot \log \pi (a|s))}-\underset{\text{Entropy Bonus}}{c_2\cdot \log (\sigma )}$$

Force 1: The Policy Loss (Exploitation)

• If we found a winning action ($A_t>0$), we want to maximize its probability density.

• In a Gaussian, how do you make the peak higher? You make the bell curve skinnier.

• Result: Maximizing probability pushes $\sigma \to 0$.

Force 2: The Entropy Bonus (Exploration)

• We subtract $c_2\log (\sigma )$. To minimize this, we must maximize $\log (\sigma )$.

• Result: This force constantly pushes $\sigma \to \infty$. It wants the agent to be as random as possible.

The Resulting Behavior:

• Success: If the agent gets huge rewards ($A_t$ is big), Force 1 becomes massive ("I found gold! Be precise!"). It overpowers Force 2. $\sigma$ shrinks.

• Failure: If the agent gets no rewards ($A_t\approx 0$), Force 1 is weak ("I don't know what I'm doing"). Force 2 is still there, pushing constantly. It overpowers Force 1. $\sigma$ grows.

So, when the agent "fails" (doesn't find a strong signal), the Entropy Bonus takes over and inflates the noise to help it search.

---

Calculating Log-Probabilities

In Discrete PPO, the network outputs [0.1, 0.8, 0.1]. If we took action 2, the probability is just the number 0.8. In Continuous PPO, we don't have a list. We have the formula for the Gaussian curve. We need to calculate the Probability Density of the specific action value $a$ that we sampled.

The Gaussian Formula: $P(a)=\frac{1}{\sigma \sqrt{2\pi }}\exp \left(-\frac{(a-\mu {)}^2}{2{\sigma }^2}\right)$

The Log-Prob Formula: $\log P(a)=\underset{\text{Distance from Mean}}{-\frac{(a-\mu {)}^2}{2{\sigma }^2}}-\underset{\text{The Spread}}{\log (\sigma )}-\underset{\text{Constant}}{\log (\sqrt{2\pi })}$

In PyTorch: You do not need to type this formula.

1. You give PyTorch the $\mu$ and $\sigma$ from your network.

2. You give PyTorch the specific action $a$ you took.

3. PyTorch plugs $a$, $\mu$, and $\sigma$ into the equation above and returns the number.

7. The Loss Function & Updates

The Combined Loss Equation

We define a single scalar number that represents everything we want the network to achieve: $L_{total}=-L^{CLIP}(\text{Actor})+0.5L^{VF}(\text{Critic})-0.01S(\text{Entropy})$ (Note: We minimize this total loss).

---

Adding Losses (The "Illegal" Math)

Your Doubt: "I never understood the maths of this. How can you add losses and then propagate gradients? Mathematically aren't you supposed to do them individually and separately?"

The Answer: This relies on the Linearity of Differentiation. It is not a hack; it is valid calculus.

Scenario: Imagine we have two completely separate neural networks:

1. Actor Network (Parameters $\theta$ ): Produces loss $L_{actor}$.

2. Critic Network (Parameters $\varphi$ ): Produces loss $L_{critic}$.

We define a combined loss: $L_{total}=L_{actor}+0.5L_{critic}$.

When we run L_total.backward(), we want PyTorch to calculate the gradients for both $\theta$ and $\varphi$. Let's solve for them manually using partial derivatives.

1. The Actor Gradient ($\frac{\partial L_{total}}{\partial \theta }$) $\frac{\partial L_{total}}{\partial \theta }=\frac{\partial (L_{actor}+0.5L_{critic})}{\partial \theta }$ Using the Sum Rule: $=\frac{\partial L_{actor}}{\partial \theta }+0.5\frac{\partial L_{critic}}{\partial \theta }$ Here is the key: Does the Critic's loss depend on the Actor's weights? No. They are separate networks. Therefore, $\frac{\partial L_{critic}}{\partial \theta }=0$. $=\frac{\partial L_{actor}}{\partial \theta }+0$ Conclusion: Differentiating the Sum with respect to $\theta$ gives exactly the same result as differentiating only the Actor Loss.

2. The Shared Weights Case (The Multi-Head Body) In many implementations, the Actor and Critic share the first few layers (the "Body") to process the image ($W_{shared}$), and then split into two "Heads." $\frac{\partial L_{total}}{\partial W_{shared}}=\frac{\partial L_{actor}}{\partial W_{shared}}+\frac{\partial L_{critic}}{\partial W_{shared}}$ This is exactly what we want. The gradients from both objectives simply add up (accumulate) at the shared weights. The weights are pushed in a direction that satisfies both tasks simultaneously.

---

Batching: How One Number Updates 64 Items

Your Doubt: "We sum the loss for 64 items and do a single backprop. How does that work?"

The Math: Derivative of an Average Let's say we have a batch of 3 items with losses $l_1(w),l_2(w),l_3(w)$. The Total Batch Loss is the average: $L(w)=\frac{1}{3}[l_1(w)+l_2(w)+l_3(w)]$

When we call backward(), we calculate the derivative: $\frac{\partial L}{\partial w}=\frac{1}{3}\left[\frac{\partial l_1}{\partial w}+\frac{\partial l_2}{\partial w}+\frac{\partial l_3}{\partial w}\right]$

The Magic: The Gradient of the Average is the Average of the Gradients. By backpropagating from that single summed number, PyTorch automatically calculates the individual gradient for Sample 1, Sample 2, and Sample 3, and adds them all up inside the weight's .grad attribute.

The Intuition: The "Tug of War" (Compromise) Imagine a single weight $w$ in the network.

• Sample 1 says: "To predict correctly for me, this weight needs to go UP (+1.0)."

• Sample 2 says: "To predict correctly for me, this weight needs to go DOWN (-0.5)."

• Sample 3 says: "I don't care, this weight doesn't affect me (0.0)."

When we do the single backprop on the average, we get: $\text{Total Gradient}=\frac{1+(-0.5)+0}{3}=+0.166$

The Update: The weight moves up slightly.

• This makes Sample 1 happier.

• This makes Sample 2 slightly unhappier.

• But on average, the total error of the batch decreases. The network finds a compromise.

---

Batching vs. Sequential Updates

Your Doubt: "Is averaging the loss for 64 items same as doing 64 sequential updates?" $w_1=w_0+\nabla l_1$ $w_2=w_1+\nabla l_2$

The Answer: NO. They are mathematically different.

1. The Sequential Way (True SGD)

2. Calculate gradient for Sample 1 using weights $w_0$. Update weights to $w_1$.

3. Calculate gradient for Sample 2 using new weights $w_1$.

4. Update weights to $w_2$.

5. The Batch Way (PyTorch Default)

6. Calculate gradient for Sample 1 using weights $w_0$.

7. Calculate gradient for Sample 2 using weights $w_0$ (NOT $w_1$. The weights are "stale").

8. Sum them up and update once.

Why we use Method 2 (Batching) despite the error:

Reason 1: The "Drunk Walk" (Stability) Sequential updates are incredibly noisy.

• Sample 1 says "Go Left". You go Left.

• Sample 2 says "Go Right". You go Right. The weights jitter around wildly. This "drunk walk" makes convergence hard. By averaging 64 samples, the noise cancels out, and the update step moves smoothly in the true downhill direction.

Reason 2: GPU Speed (The Engineering Reality) This is 99% of the reason.

• Sequential: You have to do the math Update -> Write -> Read -> Update 64 times. This is serial processing.

• Batch: You stack the 64 items into a matrix. You do one massive matrix multiplication. The GPU calculates all 64 gradients in parallel instantly.

• Result: Batching is roughly 50x to 100x faster.

Reason 3: The Approximation In Deep Learning, the Learning Rate $\alpha$ is usually very small (e.g., 0.0003). Because $\alpha$ is tiny, $w_1$ is almost identical to $w_0$. Therefore, the gradient at $w_1$ is almost identical to the gradient at $w_0$. The error introduced by batching is negligible.

8. PPO Update Logic & Engineering Details

The Actor Update (Trust Region via "Internal Ratio Clipping")

Our theoretical goal is to constrain the KL Divergence $D_{KL}({\pi }_{old}||{\pi }_{new})$. Calculating KL is computationally expensive. PPO approximates this constraint by Clipping the Probability Ratio. This is often called "Internal Clipping" because it happens inside the mathematical definition of the Loss Function itself.

The Probability Ratio ($r_t$): First, we calculate how much the policy has changed for a specific action: $r_t(\theta )=\frac{{\pi }_{new}(a_t|s_t)}{{\pi }_{old}(a_t|s_t)}$

The Objective Function: $L^{CLIP}=\min \left[r_t{A}_t,\text{clip}(r_t,1-ϵ,1+ϵ)A_t\right]$

Let's trace the logic for a Good Action ($A_t>0$). We want to increase the probability ($r_t>1$).

1. Scenario A: Small Change (Safe). The ratio moves from 1.0 to 1.1. This is inside the safe zone [0.8, 1.2] (assuming $ϵ=0.2$).

• The clip function does nothing.

• The min operator selects the first term ($1.1\times A_t$).

• Result: The gradient flows normally. The optimizer pushes the weights to increase the probability further.

1. Scenario B: Huge Change (Dangerous / Clipped). The optimizer tries to be aggressive. It changes the weights so that ${\pi }_{new}$ is much higher than ${\pi }_{old}$, pushing the ratio to 1.5.

• The clip function activates. It truncates the ratio to the limit: 1.2.

• The min operator sees two values: $(1.5\times A_t)$ and $(1.2\times A_t)$. It chooses the smaller one: $(1.2\times A_t)$.

• The Magic: To the optimizer (differentiation engine), the term $(1.2\times A_t)$ looks like a constant. The derivative of a constant is 0.

• Result: The gradient becomes zero. The update stops for that specific sample. This "Internal Clipping" acts as a logical gate that shuts off learning if the policy strays too far.

---

The Critic Update (Clipped Value Loss)

This is a detail often missed in basic tutorials. Just like the Actor, we don't want the Critic to change too fast, because a jumping Critic destabilizes the Advantage estimate for the Actor.

Definitions:

• $V_{{\varphi }_{old}}(s_t)$: The value predicted by the network before the training epochs started (frozen).

• $V_{\varphi }(s_t)$: The current prediction of the network we are training.

The Logic:

1. Calculate Unclipped Loss: $L_1=(V_{\varphi }-R_t{)}^2$. (Standard MSE).

2. Calculate Clipped Value: We force the new prediction to stay within $ϵ$ of the old prediction. $V_{clipped}=V_{{\varphi }_{old}}+\text{clip}(V_{\varphi }-V_{{\varphi }_{old}},-ϵ,+ϵ)$

3. Calculate Clipped Loss: $L_2=(V_{clipped}-R_t{)}^2$.

4. The Final Loss: We take the Maximum of the two errors. $L^{VF}=\max (L_1,L_2)$

The Update Rule: If the update tries to move $V$ too far (outside the $ϵ$ bound) to chase a noisy return, the gradient becomes 0 (because $L_2$ looks like a constant). This forces the Critic to learn slowly and stably.

---

Engineering Tricks (The "Hidden" Code)

You can have the math 100% correct, but without these engineering details, PPO often fails to learn.

1. Observation Normalization (Running Mean Std)

• The Problem: In games, pixels are 0-255. In robotics, velocity might be 0-5, but position might be -100 to +100. Neural networks hate unscaled data.

• The Fix: We calculate a Running Mean and Variance of every state the agent has ever seen. We normalize inputs: ${\text{State}}_{norm}=\frac{\text{State}-{\mu }_{running}}{\sqrt{{\sigma }_{running}^2+ϵ}}$

• Result: The agent sees a "whitened" world where inputs are roughly Mean 0, Variance 1.

1. Advantage Normalization

• The Problem: In Level 1, rewards might be +10. In Level 10, rewards might be +1000. This messes up the step size. A "good" advantage of +5 becomes irrelevant later.

• The Fix: Inside each training batch (e.g., 2048 items), we normalize the Advantages so they form a standard bell curve. $A_{normalized}=\frac{A-\text{mean}(A)}{\text{std}(A)+1e-8}$

• Result: Roughly half the actions are considered "Good" ($A>0$) and half are "Bad" ($A<0$). This keeps the learning signal consistent regardless of the reward scale.

1. Orthogonal Initialization

• The Problem: Standard weight initialization (Xavier/Glorot) is designed for image classifiers. In RL, bad initialization leads to vanishing gradients immediately.

• The Fix: We initialize weights such that the matrix $W$ is orthogonal ($W{W}^T=I$). This preserves the magnitude of the signal as it passes through deep networks.

• Critical Detail: For the final output layer of the Actor, we initialize weights to be tiny (0.01). This ensures the initial probabilities are almost perfectly random, preventing the agent from starting with a strong bias (e.g., "Always move Left").

1. Gradient Clipping (External / Global Clipping)

• The Distinction: This is NOT the PPO Ratio Clipping we discussed above.

  • PPO Ratio Clipping (Internal): Happens inside the Loss Function math. It sets the gradient to 0 if the policy changes too much.

  • Gradient Clipping (External): Happens after loss.backward() and before optimizer.step().

• The Problem: Even with PPO Clipping, sometimes the data is weird, and the gradient calculation results in massive numbers that crash the floating-point math (NaNs).

• The Fix: We clip the Global Norm of the gradient vector.

torch.nn.utils.clip_grad_norm_(agent.parameters(), max_norm=0.5)

• Meaning: If the gradient vector is too long (length $>0.5$), we shrink it to length 0.5, keeping the direction the same. This is a safety fuse for the optimizer.er.

RLHF

---

Phase 1: Supervised Fine-Tuning (SFT)

The Problem: The "Blank Slate" Model

If we start with a raw, randomly initialized neural network and try to apply PPO, the model will fail. It has no concept of language, grammar, or facts. It would generate random, incoherent noise (e.g., "gaga goo goo").

In a simple RL environment like a Grid World, random exploration is sufficient to eventually stumble upon a reward. In the vast space of language, the probability of a random sequence of tokens forming a coherent, reward-worthy sentence is practically zero. The agent would never receive a learning signal.

Therefore, before we can use RL, the model must first learn to speak a human language and follow basic instructions.

The Goal of SFT

The goal is to teach a pre-trained base model (like LLaMA, GPT-3, etc.) to act like a helpful assistant. We want to refine its behavior to be more aligned with the "instruction-following" style we expect from a chatbot. We are essentially cloning the behavior of expert human labelers.

The Data: High-Quality Demonstrations

The dataset for this phase consists of high-quality (Prompt, Response) pairs curated and written by expert humans. This is a critical and expensive part of the process.

• Example Prompt: "Explain the concept of quantum physics to a five-year-old in simple terms."

• Example Response (written by a human expert): "Imagine a tiny, tiny ball that can be both red and blue at the same exact time, until you look at it. When you look, it has to choose to be just red or just blue. Isn't that silly?"

The Training Method: Standard Supervised Learning

This phase does not involve any reinforcement learning. It is a standard supervised learning task, identical to how models like GPT are trained.

We use Next Token Prediction with a Cross-Entropy Loss (also known as Negative Log-Likelihood).

The Process:

1. We take a (Prompt, Response) pair.

2. We concatenate them into a single sequence.

3. We feed the sequence into the model one token at a time.

4. At each step, we train the model to predict the very next token in the sequence.

Example Trace:

• Input to Model: [<start>, "Explain", "quantum", "physics", ..., "Imagine", "a", "ball", "that", "can", "be"]

• Model's Task: Predict the probability distribution for the next token.

• Correct Answer (Target): The token "red".

• Loss Calculation: The model's loss is the negative logarithm of the probability it assigned to the correct word, "red". We use backpropagation to adjust the weights to make the probability of "red" higher in this context next time.

The Result: The ${\pi }^{SFT}$ Model

After training on thousands of these demonstrations, we get a model we will call ${\pi }^{SFT}$(The Supervised Fine-Tuned Model).

This model is good, but not great.

• It is proficient: It can follow instructions and generate coherent, grammatically correct text.

• It is an "Averager": Its responses are a statistical average of the responses it saw in the training data. It may lack creativity, fail to generalize to novel prompts, or produce safe but unhelpful answers.

• It is the Foundation: This model serves as the crucial starting point for the PPO agent in Phase 3. It also acts as the "Grammarian" or the "Anchor" in the KL Penalty, ensuring our RL agent doesn't forget how to speak English.

---

Chapter 2: The Reward Model (RM)

The Goal: Learn a Scoring Function

The goal of this phase is to train a model, which we'll call $R_{\varphi }$ , that takes a (Prompt, Response) pair and outputs a single scalar number representing its quality (e.g., +5.2 for a good answer, -3.1 for a bad one). This model will act as the "Environment" for our PPO agent in the next phase.

The Data Problem: Human Inconsistency

A naive approach would be to ask human labelers to score responses on a scale of 1 to 10. This fails in practice for two reasons:

1. Noise: What one person considers a "7/10" another might call a "9/10". The scores are not well-calibrated between different people.

2. Difficulty: It is much harder for a human to assign a consistent, absolute score than it is to make a relative judgment.

The Solution: Pairwise Comparison (Ranking)

Instead of asking "How good is this?", we ask "Which one is better?". Humans are exceptionally good at making relative judgments.

The Data Collection Process:

1. Take a Prompt: "Write a short story about a friendly robot."

2. Generate Multiple Responses: Run our SFT model (${\pi }^{SFT}$) several times with the same prompt to get different outputs (e.g., Output A, B, C, D).

3. Human Labeling: Show a human labeler a random pair of these responses (e.g., A and B).

4. Record the Preference: The human chooses which response is better. The data point we save is a triplet: (prompt, chosen_response, rejected_response).

This creates a high-quality dataset of human preferences.

---

The Training Math: The Bradley-Terry Model

We now have a dataset of (prompt, winner, loser). We need a loss function that teaches our Reward Model ( $R_{\varphi }$ ) to assign a higher score to the winner.

The standard approach is based on the Bradley-Terry model, which connects pairwise probabilities to an underlying score.

The Logic: The probability that a human prefers the winning response ( $y_w$ ) over the losing response ( $y_l$) is modeled as a sigmoid of the difference in their scores. $P(y_w>y_l|x)=\sigma (R_{\varphi }(x,y_w)-R_{\varphi }(x,y_l))$

• x is the prompt.

• $R_{\varphi }(x,y)$ is the scalar score our Reward Model gives to a (prompt, response) pair.

• $\sigma$ is the sigmoid function.

Visualizing the Math: Let's trace a single training step to understand how this works.

1. The Setup: We have a winning response Input A and a losing response Input B. We feed both into the same Reward Model network.

2. The Scores: The network, currently with random weights, outputs a random scalar score for each.

• Score(Winner) = 0.5

• Score(Loser) = 0.8 (This is incorrect; the loser has a higher score).

1. The Difference: We calculate the difference in scores.

• Diff = Score(Winner) - Score(Loser) = 0.5 - 0.8 = -0.3.

1. The Probability: We want this difference to be a large positive number. We feed it into a sigmoid to see what the model currently "believes".

• P(Winner is better) = sigmoid(-0.3) ≈ 0.42 (42%).

1. The Loss: We want this probability to be 1.0 (100%). We use the Negative Log-Likelihood as our loss function.

• Loss = -log(0.42) ≈ 0.86. This is a high error, signaling that the model's prediction was very wrong.

1. The Update (Backpropagation): The gradient descent process will now adjust the weights of $R_{\varphi }$ to fix this error. It will simultaneously:

• Push Up: Nudge the weights to increase the score for the winning response.

• Pull Down: Nudge the weights to decrease the score for the losing response.

• The goal is to maximize the gap between the winner's score and the loser's score.

The final loss function we minimize is: $\text{Loss}=-\log \sigma (R_{\varphi }(x,y_w)-R_{\varphi }(x,y_l))$

The Result: The $R_{\varphi }$ Model (The Judge)

After training on hundreds of thousands of human preference pairs, we have a frozen, reliable Reward Model. This model has learned to internalize human preferences. It can now look at a new, unseen response and assign it a high score if it's good (helpful, harmless, well-written) and a low score if it's bad (inaccurate, unsafe, gibberish).

This model is the "Environment" our PPO agent will interact with in the final, most complex phase.

---

Chapter 3: PPO Optimization (Unabridged & Complete)

The Goal: Maximize the Reward Model's Score

The primary objective is to adjust the weights ( $\theta$ ) of our language model, let's call it ${\pi }^{RL}\theta$ , to generate responses that get the highest possible score from our frozen Reward Model, $R\varphi$ .

The "Per-Token" RL Loop

A standard PPO loop involves a sequence: State -> Action -> Reward -> Next State. To apply this to text generation, we treat the process as a multi-step episode.

• The Episode: The entire process of writing one response to one prompt.

• A Timestep ( t ): The generation of a single token (word).

Let's trace the generation for the prompt "Write a poem".

Time t=0:

• State ( $S_0$ ): The initial prompt tokens: ["Write", "a", "poem"].

• Action ( $A_0$ ): The Actor network ( ${\pi }_{\theta }^{RL}$ ) samples the token "Upon".

• Reward ( $R_1$ ): We don't get a score yet. The reward is 0.

• Next State ( $S_1$ ): ["Write", "a", "poem", "Upon"].

...This continues until the model generates an End-of-Sentence <EOS> token.

Final Timestep (e.g., t=20):

• State ( $S_{20}$ ): The full poem generated so far.

• Action ( $A_{20}$ ): The Actor samples <EOS>.

• Reward ( $R_{21}$ ): The episode is now over. We take the complete text and feed it to the Reward Model.

  • $R_{RM}$ = $R_{\varphi }$ ($\text{prompt}$, $\text{full-text}$) = +7.5 .

  • This is the only non-zero reward from the Reward Model. The reward sequence is sparse: [0, 0, ..., +7.5].

---

The Full PPO Loop (LLM Version)

Now, let's look at how all our PPO machinery plugs into this "per-token" view.

1. The Rollout: We generate a batch of, say, 16 prompts. For each prompt, we do a full rollout, collecting data at each token step:

t	State ( S_t )	Action ( A_t )	LogProb (Old)	V(S_t)	Reward ( R_{total} )
0	["Write", "poem"]	"Roses"	-1.2	3.5	-0.002
1	[..., "Roses"]	"are"	-0.8	3.8	-0.004
2	[..., "are"]	"red"	-0.9	4.1	-0.001
3	[..., "red"]	<EOS>	-1.5	4.5	+4.997

• LogProb (Old): The log probability of the action, calculated from the policy_old (the frozen policy that is generating this data).

• V($S_t$): The Critic's prediction of the final score, given the sentence so far. Notice it goes up as the sentence gets better.

• Reward ( $R_{total}$ ): The reward for this token, which is the (usually zero) Reward Model score plus the KL penalty for this step.

1. The GAE Calculation: We now have a sequence of rewards, for example: [-0.002, -0.004, -0.001, +4.997]. We can run our backwards GAE loop exactly as we learned to calculate the Advantage for each token.

• Delta for "red" (t=2): ${\delta }_2=R_{tota{l}_3}+\gamma V(S_3)-V(S_2)=4.997+0.9\times 4.5-4.1\approx +4.947$ .

• Advantage for "red": $A_2={\delta }_2+(\gamma \lambda )A_3=+4.947+0=+4.947$ .

• Delta for "are" (t=1): ${\delta }_1=R_{tota{l}_2}+\gamma V(S_2)-V(S_1)=-0.001+0.9\times 4.1-3.8\approx -0.111$ .

• Advantage for "are": $A_1={\delta }_1+\gamma \lambda A_2=-0.111+(0.9)(0.95)(4.947)\approx +4.11$ .

The GAE math automatically propagates the final reward backwards to credit the earlier words that led to it.

1. The PPO Update: Now we have our (State, Action, LogProb_Old, Advantage) tuples for every single token. We feed these into the PPO Loss function and update the network. The network learns: "When the state was [..., 'are'], picking red had a large positive advantage. I should increase its probability."

obviously we are calculating pie new the updating and then again calculating pie new in loop for 1-4 epoch and yes for the first iteration pie new and old would be the same

---

The Hidden Trap: The "Reward Hack" (Goodhart's Law)

If we let PPO run wild just to maximize the score from $R_{\varphi }$ , it will find and exploit flaws in our Judge.

• Scenario: The Reward Model learned an implicit bias: Longer text = Higher score.

• The Hack: The PPO agent discovers this. It learns to generate rambling, repetitive, nonsensical text because this maximizes its score from the flawed Judge.

• The Result: The model's output becomes unhelpful to a human, even though it is "winning the game." This is Over-Optimization.

---

The Solution: The KL Penalty (The "Anchor")

To prevent the agent from straying too far into "alien" text, we must anchor it to the original, human-like distribution of the SFT model. We modify the reward function.

The Per-Token Reward Function: $R_{tota{l}_t}=R_{R{M}_t}-\beta \cdot D_{KL}({\pi }^{RL}(\cdot |s_t)||{\pi }^{SFT}(\cdot |s_t))$

one doubt I had was how will we calculate this during the rollout phase? because I thought this pie RL is pie RL new no, its pie RL old itself. pie SFT is the OG sft policy we started with

---

The Four Models in Memory

To execute this complex loop, you actually need four separate models loaded into memory simultaneously, which is why RLHF is so resource-intensive.

1. The Actor ( ${\pi }_{\theta }^{RL}$ ): The main LLM we are actively training with PPO.

2. The Critic ($V_{\varphi }$ ): The value function network that predicts the expected score. Often, this shares the "body" of the Actor model but has a separate linear "head" on top.

3. The Reward Model ( $R_{\varphi }$ ): A frozen, separate LLM that acts as the "Judge" and provides the final reward.

4. The SFT Reference Model ( ${\pi }^{SFT}$ ): A frozen, separate copy of the original Supervised Fine-Tuned model. This is used for two things:

• The denominator of the PPO ratio ($r_t$ ): This is the "Old Policy" that collected the data for the current training batch.

• The KL Penalty Anchor: This is the pi_SFT in the KL(pi_RL || pi_SFT) calculation.

GRPO

Deep Reinforcement Learning: Group Relative Policy Optimization (GRPO)

Chapter 1: The Motivation (The Memory Wall)

To understand why GRPO exists, we must look at the computational cost of PPO when applied to massive models (70B+ parameters).

The PPO Memory Bottleneck

In the standard PPO-RLHF setup, we need to load four distinct models into GPU memory:

1. The Actor (${\pi }_{\theta }$ ): The model being trained (e.g., 70B params).

• Memory Cost: Parameters + Gradients + Optimizer States (Adam).

1. The Critic ( $V_{\varphi }$ ): The value function.

• Memory Cost: Parameters + Gradients + Optimizer States.

• Crucial Detail: In PPO, the Critic usually needs to be as large as the Actor to effectively understand the nuance of the text. So, another 70B params.

1. The Reference Model ( ${\pi }_{ref}$ ): Frozen copy for KL penalty.

2. The Reward Model ( R ): Frozen judge.

The Total Cost: The Optimizer States for the Actor and Critic take up massive amounts of VRAM. Having a trainable Critic effectively doubles the training memory requirements compared to just fine-tuning the model.

The GRPO Hypothesis

If we delete the Critic:

1. We save 50% of the training memory (no Critic weights, no Critic optimizer states).

2. We remove the complexity of training a Value Function (no more $L^{VF}$ loss).

3. We remove the need for GAE (Generalized Advantage Estimation).

The Problem: The Critic's job was to provide a Baseline ( V(s) ) to reduce variance ( A = Q - V ). Without V(s) , how do we calculate the Advantage?

The Solution: Instead of learning a neural network to predict the baseline, we can empirically estimate the baseline by sampling a Group of outputs for the same prompt.

---

Chapter 2: The GRPO Mechanism

GRPO modifies Phase 3 (The Optimization Phase). It changes how we collect data and how we calculate the Advantage.

Step 1: Group Sampling

In PPO, we usually sample one output per prompt. In GRPO, for every prompt query q , we sample a Group of G outputs.

$$\{o_1,o_2,\dots ,o_G\}\sim {\pi }_{{\theta }_{old}}(o|q)$$

• G : The group size (e.g., 64).

• q : The input prompt (e.g., "Solve this math problem").

• $o_i$ : The i -th generated output text.

Step 2: Scoring

We run the Reward Model on all G outputs to get a scalar reward for each. $r_1,r_2,\dots ,r_G$

Step 3: The Relative Advantage

This is the core innovation. Instead of asking a Critic "How good is $o_1$ compared to the average?", we compare $o_1$ to the other outputs in the group.

We calculate the Mean and Standard Deviation of the rewards within this specific group.

$$\text{Mean}=\bar{r}=\frac{1}{G}\sum _{i=1}^G{r}_i$$

$$\text{Std}={\sigma }_{group}=\sqrt{\frac{1}{G}\sum _{i=1}^G(r_i-\bar{r}{)}^2+ϵ}$$

The Advantage for output i is its Z-Score within the group:

$$A_i=\frac{r_i-\bar{r}}{{\sigma }_{group}}$$

Why this works (The "Math Test" Analogy):

• Prompt: A very hard calculus question.

• GRPO Approach: The model generates 8 answers. Since the question is hard, all 8 answers are bad. Scores: [0.1, 0.2, 0.1, 0.5, 0.1, 0.2, 0.1, 0.1].

• The Mean is $\approx 0.17$ .

• That answer with score 0.5? It is terrible objectively, but it is amazing compared to the group.

• The Advantage for the 0.5 answer becomes huge positive. The model learns: "Even though I failed, this was the best path."

Using the Group Mean as the baseline automatically adjusts for the difficulty of the prompt.

---

Chapter 3: The Notation and Hierarchy

Before writing the loss function, we must clarify the indices to avoid confusion between "Responses" and "Tokens."

The Hierarchy of Data:

1. The Prompt ( q ): The input question.

2. The Group ( i ): We generate G different responses to that one prompt.

• $i\in \{1,2,\dots ,G\}$ .

• $o_i$ represents the $i-th$ complete response.

1. The Token ( t ): Inside one specific response o_i , there is a sequence of words.

• $t\in \{1,2,\dots ,T\}$ .

• $o_{i,t}$ is the t -th token of the i -th response.

Key Definition: The Advantage ( $A_i$ )

• A_i is a single scalar number calculated for the entire response $o_i$ .

• Crucial Detail: We broadcast this value. Every single token in sentence i ("The", "answer", "is", "4") gets assigned the same advantage $A_i$.

Key Definition: The Probability Ratio ( ${\rho }_{i,t}$ )

• This is calculated per token.

• ${\rho }_{i,t}={\pi }_{new}(toke{n}_t)/{\pi }_{old}(toke{n}_t)$ .

---

Chapter 4: The Objective Function

The GRPO Loss Function (from the DeepSeekMath paper) averages over the Group and sums over the Tokens.

Term A: The Reward Objective (PPO Clip)

$$\min \left({\rho }_{i,t}{A}_i,\text{clip}({\rho }_{i,t},1-ϵ,1+ϵ)A_i\right)$$

• Logic: This is the standard PPO "Trust Region" logic.

• Constraint: It ensures the new policy ( ${\pi }_{\theta }$ ) does not drift too far from the old policy ( ${\pi }_{old}$ ) that generated the data within the current training batch.

Term B: The KL Regularization (Your Doubt)

Your Doubt: "The KL term had to be in the reward, right? What is it doing there in the loss? We are already using clipping."

The Answer:

1. Placement: In Standard PPO, we put KL in the Reward. In GRPO (DeepSeek), they explicitly put it in the Loss. Mathematically, maximizing Reward - KL is similar to minimizing Loss + KL. However, putting it in the loss allows for per-token precise control without messing up the Group Normalization of the rewards.

2. Why do we need it if we have Clipping?

• PPO Clipping (Term A): Constraints pi_new vs pi_old. It ensures Optimization Stability (don't trip while learning). It does not stop long-term drift.

• KL Regularization (Term B): Compares pi_new vs pi_ref (The SFT Model). It ensures Behavioral Stability (don't forget how to speak English). Even after 1,000 updates, this anchors the model to the original SFT distribution.

We need both. One for the math to work (Clip), one for the language to stay coherent (KL).

---

Chapter 5: Update Mechanics (Batch vs. Token)

Your Doubt: "Due to the way loss is calculated weights can only be updated once for a full prompt with many responses, right?"

The Answer: Yes. You are correct. Neither PPO nor GRPO updates weights "per token."

1. The Summation Symbols

The symbols $\sum \sum$ in the loss function mean "Sum up the error." They do not mean "Update weights inside the loop."

The Execution Flow:

1. Loss Calculation: We calculate the GRPO loss for every token in all 64 responses. (e.g., 6,400 individual numbers).

2. Aggregation: We average them all into One Scalar Loss.

3. Update: We run loss.backward() and optimizer.step() ONCE for that entire group/batch.

2. Granularity of the Signal (PPO vs. GRPO)

While the update frequency is the same, the signal is different.

• PPO (Dense Signal): Because of the Critic, Token 5 might have A=+0.8 and Token 6 might have A=-0.2 . The gradient pushes tokens in different directions within the same sentence.

• GRPO (Sparse Signal): Because we use the Group Outcome, the entire sentence gets one score. If A_i = +2.0 , the gradient pushes every single token in that response UP.

3. Engineering Reality (Gradient Accumulation)

With 70B models, we cannot fit 64 sequences in memory to do the sum at once.

• Method: We load 1 sequence, calculate gradients, and accumulate them (add to a bucket). We repeat this 64 times. Then we update the weights once using the bucket. This achieves the mathematical equivalent of the batch update.

DPO

The Current State (RLHF via PPO)

Think about the pipeline we just built for PPO. It is an engineering nightmare.

To align a model, we need:

1. Step 1: Train a Supervised Model ( ${\pi }_{ref}$ ).

2. Step 2: Train a Reward Model ( $R_{\varphi }$ ) on comparison data (Winner, Loser).

3. Step 3: Load 4 Models into memory (Actor, Critic, Ref, Reward).

4. Step 4: Run a complex, unstable loop:

• Generate text (slow).

• Estimate Values.

• Calculate Advantages.

• Clip gradients.

• Hope it doesn't crash.

The DPO Insight

The creators of DPO (Rafael Rafailov et al., 2023) looked at Step 2 (Reward Model training).

• Data: We have pairs (Winner > Loser).

• Standard Way: Train a Reward Model to understand this data, then use RL to teach the Language Model.

• DPO Way: Why the middleman? Can we define a loss function that looks at (Winner, Loser) and updates the Language Model directly?

If this works, we can delete the Reward Model. We can delete the Critic. We can delete the PPO loop. We essentially turn RLHF back into a simple Supervised Learning problem.

---

Chapter 2: The Mathematical Magic Trick

This chapter contains the derivation. It relies on algebra, not calculus.

Step 1: The RLHF Objective

Recall the equation we maximize in PPO (using the KL penalty in the reward):

$$\underset{\pi }{\max }\mathbb{E}\left[R(x,y)-\beta \log \frac{\pi (y|x)}{{\pi }_{ref}(y|x)}\right]$$

• R(x, y) : The true reward for prompt x and response y .

• $\beta$ : The penalty strength.

• ${\pi }_{ref}$ : The reference SFT model.

Step 2: The "Closed Form" Solution

This is the hardest concept to accept intuitively, but it is a proven mathematical fact.

If you have a specific Reward Function R and a Reference ${\pi }_{ref}$ , there is an exact mathematical formula for the Optimal Policy ( ${\pi }^{\ast }$ ) that maximizes that objective. You don't need gradient descent to find the formula, you can just write it down.

The Optimal Policy ${\pi }^{\ast }(y|x)$ is given by:

$${\pi }^{\ast }(y|x)=\frac{1}{Z(x)}{\pi }_{ref}(y|x)e^{\frac{R(x,y)}{\beta }}$$

• Translation: The perfect policy is just the Reference Policy, scaled up by the exponentiated Reward.

• Z(x) : This is a "Partition Function." It’s just a normalization constant (a number) to make sure the probabilities sum to 1. It does not depend on the specific response y .

Step 3: The Algebra (The Inversion)

Now, the magic. We have an equation relating the Optimal Policy to the Reward. ${\pi }^{\ast }=\dots R\dots$

Let's do some algebra to rearrange this equation. We want to solve for R.

1. Take the logarithm of both sides: $\log {\pi }^{\ast }(y|x)=\log \frac{1}{Z(x)}+\log {\pi }_{ref}(y|x)+\frac{R(x,y)}{\beta }$

2. Move terms around to isolate R(x,y) : $\frac{R(x,y)}{\beta }=\log {\pi }^{\ast }(y|x)-\log {\pi }_{ref}(y|x)-\log \frac{1}{Z(x)}$

3. Simplify the logs ( $\log A-\log B=\log \frac{A}{B}$ ): $\frac{R(x,y)}{\beta }=\log \frac{{\pi }^{\ast }(y|x)}{{\pi }_{ref}(y|x)}+\log Z(x)$

4. Multiply by $\beta$ : $R(x,y)=\beta \log \frac{{\pi }^{\ast }(y|x)}{{\pi }_{ref}(y|x)}+\beta \log Z(x)$

What have we done? We have expressed the Reward entirely in terms of the Optimal Policy, the Reference Policy, and a constant Z(x) .

We no longer need a separate Reward Network $R_{\varphi }$ . The policy itself defines the reward.

---

Step 4: The Substitution

Now, recall how we trained the Reward Model in Phase 2 (Bradley-Terry Model). We wanted to maximize the likelihood that the Reward of the Winner ( $y_w$ ) is higher than the Reward of the Loser ( $y_l$).

$$P(Winner>Loser)=\sigma (R(x,y_w)-R(x,y_l))$$

Let's plug in our formula for R from Step 3 into this equation.

$$R(x,y_w)-R(x,y_l)=\left(\beta \log \frac{{\pi }^{(}{y}_w|x)}{{\pi }_{ref}(y_w|x)}+\beta \log Z(x)\right)-\left(\beta \log \frac{{\pi }^{(}{y}_l|x)}{{\pi }_{ref}(y_l|x)}+\beta \log Z(x)\right)$$

Look what happens: The term $\beta \log Z(x)$ appears in both rewards. Since we are subtracting, it cancels out! We don't need to know Z(x) .

The difference becomes: $\beta \log \frac{{\pi }^{(}{y}_w|x)}{{\pi }_{ref}(y_w|x)}-\beta \log \frac{{\pi }^{(}{y}_l|x)}{{\pi }_{ref}(y_l|x)}$

Step 5: The DPO Loss Function

We replace the theoretical "Optimal Policy ${\pi }^{\ast }$ " with our "Trainable Network ${\pi }_{\theta }$ ".

The DPO Loss is just the standard Bradley-Terry loss, but using this "Implied Reward" difference:

$$L_{DPO}(\theta )=-\log \sigma \left(\beta \log \frac{{\pi }_{\theta }(y_w|x)}{{\pi }_{ref}(y_w|x)}-\beta \log \frac{{\pi }_{\theta }(y_l|x)}{{\pi }_{ref}(y_l|x)}\right)$$

Conclusion of the Derivation:

• We started with the RLHF objective (Reward - KL).

• We solved for the optimal policy.

• We inverted it to define Reward in terms of Policy.

• We plugged that into the preference ranking loss.

• Result: A loss function that optimizes the Policy ${\pi }_{\theta }$ using only the reference model ${\pi }_{ref}$ and the data pairs. No Reward Model network required.

This derivation proves that optimizing this loss is mathematically equivalent to optimizing the RLHF objective.

Are you comfortable with this "Inversion" logic? It is the foundation of DPO.

Original Notion page