basics

reinforce grpo dapo

history is past actions state is current env state env is action space actions are actions rewards are rewards you give the model to update itself agent is who does actions expectation is a parallel to averages except for probabilities.

two main things

1. agent: the model that performs the actual tasks
   • it’s goal is to maximize reward over the entire horizon (not just in that temp place)
   • it has a set of actions it can perform in that environment
2. environment: the place where the agent actually performs the actions
   • also provides the next state after each action
   • provides rewards

policies: policies decide how do models decide which action to perform usually denoted by $\pi$ . there are generally two types of policies 1. deterministic policies : policy directly specifies what specific action the agent will take for each state $a=\pi (s)$ for every possible state s in the env there is a specific action according to the policy. 2. stochastic policies : this gives (as the name suggests) a probability distribution over the action space. $\pi (a|s)=P[A_t=a|S_t=s]$

value function: from a given state $s$ what’s the total rewards from here on out. it’s a learned function instead of preset like reward used in value based learning where it tries to first learn this and then maximize it.

the goal of reinforcement learning is to find the “optimal policy” or ${\pi }^{\ast }$ which maximizes the reward over the long run on any starting state. since i don’t wanna learn everything from scratch right now i will just jump to REINFORCE which is the most basic implementation of policy gradients. the main difference between this and the basic other ones is they try to first approximate the value function then get the model to make the best policy according to that since i’m not exactly using classical RL i will revisit these techniques later.

policy gradients

this is for continuous actions. instead of discrete defined actions. instead of trying to learn the value functions it tries to directly find the most optimal policy. we try to learn a policy network $\pi (a|s)$ such that it maximizes the reward by doing a grad over this. how do we do the grad? just decide an algo where you mix it with the probability distribution of the outputs of the policy model. oh yeah policy gradients mean they are outputting probability distributions. where we get a sort of loss that we use to then update the policy model…

where for each output probability distribution that we get. we try to use rewards in junction to that distribution as a psuedo loss to define our total loss and do grad over it.

which is why we get the policy gradient theorem

$$\begin{array}{rl}{\nabla }_{\theta }J(\theta )& \propto {\mathbb{E}}_{{\pi }_{\theta }}\left[{\nabla }_{\theta }\log {\pi }_{\theta }(a|s)\cdot G_t\right]\\ \text{where:}& \\ & {\nabla }_{\theta }J(\theta )\text{- Gradient of objective function}\\ & {\mathbb{E}}_{{\pi }_{\theta }}[\cdot ]\text{- Expectation under policy }{\pi }_{\theta }\\ & {\nabla }_{\theta }\log {\pi }_{\theta }(a|s)\text{- Score function}\\ & G_t\text{- Return from time }t\end{array}$$

there’s a long derivation but my intuition is we want to maximize $J(\theta )$ which is the sum of all rewards over time t so that’s an integration for all states performing an action with maximal reward we can move this to an update where the $G_t$ comes in which is the rewards for that trajectory after that specific action from that point on (sort of like a monte carlo tree yk) multiplied by the log of the policy reward probability. which gives us the entire map of the action state space and we get an average score of whcih using $E_{{\pi }_{\theta }}$ and doing a gradient ascent over this to maximize $J$ function…

the most basic version of policy gradients is REINFORCE

reinforce

it is also known as a monte carlo policy gradient, why? well it takes the policy gradient theorem way too seriously, only updating the parameters after an entire episode has been run with the same parameters (an episode is an entire run of the environment start through finish). calculating the $G_t$ obtained from each state $S_t$ and then update parameters in that direction.

the reinforce update rule

the entire episode is needed to run before doing an update and there’s two ways you can go about it. first is you do it full episode 1 update

$$\theta \leftarrow \theta +\alpha \cdot \sum _{t=0}^{T-1}{\nabla }_{\theta }\log {\pi }_{\theta }(a_t|s_t)\cdot G_t$$

this is a big update although it’s still an average and doesn’t make that discrete an update i think so there’s sequential update where you

$$\text{For each time step }t:\theta \leftarrow \theta +\alpha \cdot {\nabla }_{\theta }\log {\pi }_{\theta }(a_t|s_t)\cdot G_t$$

since you already know all the $G_t$ for each step.

this seems extremely fucking slow like per episode update is insane plus such mixed averages feels like exploding gradients. also next time the agent will just choose a different direction and it’s equally useless if it does…

baseline

ok so turns out the genius researchers thought of the same thing and discovered the problem of high varience. so they got a new term, $b(s_t)$ which they subtract from the total $G_t$.

$$\theta \leftarrow \theta +\alpha \cdot {\nabla }_{\theta }\log {\pi }_{\theta }(a_t|s_t)\cdot (G_t-b(s_t))$$

there are many ways to get a baseline like

• average $b(s)=E[G_t]$
• moving average of recent returns
• value function (this is later though)

and they say apparently it doesn’t add bias… oh wait yeah if we get the probability enough times it’s basically computing the avearage only since expectation is just a long term average

why do we use log here ?

state value functions

since we need a dynamic baselines we use value functions to get a baseline over the state (no idea how they train it). they train an approximation model $v(s_t,w)$ where w is the weights to get the baseline. there are different techniques to learn the approximation. i’ll just focus on the actor critic method…

the actor critic method

instead of pure reinforce now we have two components.

actor: this is what learns the policy and outputs the probability distribution over our actions (can do both continous and discrete actions). it’s basically a parametrized policy ${\pi }_{\theta }(a|s)$ that maximizes the reward.

critic: this component tries to estimate the value fucntion $V(s)$ or the action-value function $Q(s,a)$. takes in state information and outputs.

how is this used for grad and updates?

the actor gives action $A_t$ for the state $S_t$ with it’s policy. environment changes it’s states $S_{t+1}$ and reward $R_{t+1}$ then the critic evaluates the actions (by using something like temporal difference error) temporal difference error: measures the difference between estimated value and observed reward plus the discounted value of the next state.

which brings us to more sophisticated archs, i don’t wanna read everything i will however revisit TRPO later but for now just jump in PPO

proximal policy optimization

stuff used before had some problems

1. episodic learning : it takes too long to do updates
2. exploding variance: the update can be crazy big or crazy small and that’s tiring to look and there’s a catastrophic sub problem there.
   • here if it makes a big wrong change (that it does very often) it causes good actions to ahve way less probabilities and bad actions to big probabilities. and once this policy has been updated we can never updated so that particular action will never be performed again (or remote) and cause even worse updates.

PPO tries to solve this.

1. fixing sample efficiency

they do something called importance sampling i also wrote a note abt it in ^aa2580
so they use that equation to use the previous episode policy using importance sampling so the new equation becomes

$${\nabla }_{\theta }J(\theta )={\mathbb{E}}_{s,a\sim {\pi }_{\text{old}}}\left[\frac{{\pi }_{\theta }(a|s)}{{\pi }_{\text{old}}(a|s)}{\nabla }_{\theta }\log {\pi }_{\theta }(a|s)A(s,a)\right]$$

so the importance formula is

$$E_{x\sim p}[f(x)]\approx \frac{1}{N}\sum _{i=1}^{N}f(x)\frac{p(x)}{q(x)}$$

so the mapping is $p(x)$ is the new policy ${\pi }_{\theta }(a|s)$ $q(x)$ is the old policy ${\pi }_{old}(a|s)$ and $f(x)$ is $A(s,a)$

hence we can now reuse the same episodes over and over again for better performance. so they keep updating the same trajectory with these new policies… but this must create some additonal problems

• overfitting
• also if you are doing it again and again the episodes are the same it’s just the update is much faster it’s still episodic but updates are faster and gradual ig so apparently they solve it using clipping

2. fixing exploding variance

they clip by how much changes can a policy have relative to the previous policy. helps with catastrophic updates

$$L^{\text{PPO}}(\theta )={\mathbb{E}}_t\left[\min (r_t(\theta )A_t,\text{clip}(r_t(\theta ),1-ϵ,1+ϵ)A_t)\right]$$

we clip the objective where $ϵ$ how much the policy can change. and $r_t$ is the ratio between the new and old policy. and $A_t$ is the advantage or how much more reward you got over baseline.

GRPO

since critic PPO takes a lot of computation then deepseek geniuses came up with grpo, stands for group relative policy optimsation . in the previous equation $A_t=G_t-V(s_t)$ and value model is too much computation. so we remove that part and instead of absolute advantage we have relative advatage where we sample n outputs and judge relatively which one has the best actions and move in that direction. so the new advantage equations look like.

$$A_i=\frac{r_i-\frac{1}{k}{\sum }_{j=1}^k{r}_j}{\sigma (r_1,r_2\dots ,r_k)}$$

this is essentially each reward subtracted by the mean and divided by the standard deviation ($\sigma$)

$$A_i=\frac{r_i-mean}{std}$$

and we put this as is in the equation instead of the previous advantage. helps with computation efficiency.

but this pure grpo often drifts too far from base model since a stupid policy can keep getting pushed to hell. so we add a KL divergence penalty.