2024-08-25
These are notes from my study of several online RL tutorials. They are quite disorganized and not suitable as your first RL tutorial. If you want a beginner's RL tutorial, I recommend reading OpenAI's Spinning Up from start to finish.
Here's another similar blog post by yynnyy for reference.
Model-free methods do not model the environment. Of course, for training, the code must model the environment and rewards to some extent, but it does not provide assistance to the model other than defining the reward function. Depending on the learning objectives, the Model-Free category mainly includes policy gradient methods that directly represent policies (including various improvements, such as the PPO algorithm) and Q-Learning type methods that simulate Q functions. Therefore, using PPO's RLHF is a Model-free method.
Model-based methods use the model of the environment for multi-step planning, simulating what will happen after a few steps. This model is either predefined or learned by the algorithm. Model-based RL algorithms are quite diverse without obvious classification. The simplest Model-based RL is MPC Model-predictive control, which looks ahead a fixed time window at each step, calculates an optimal plan based on the model, and then takes the first step of the plan.
The Spinning-up documentation defines Off-policy as data collected at any stage of training can be used to update the model. For example, Q-Learning is an Off-policy algorithm. Can data collected at any stage in Q-Learning be used to update the model? Yes, in Deep Q-Network, there is a replay buffer specifically for collecting all experienced state-action-result-next state tuples $(s_i,a_i,r_i,s_{i+1})$, and each parameter update is done by sampling a mini-batch from the replay buffer and performing gradient descent according to the following Loss, thereby achieving the effect of sampling and reviewing all experiences during the training process.
This loss function is the square of the TD target minus the Q Value Estimation. Note that here the TD target assumes taking the optimal action in the next state: $$ (r_i + \gamma * \max_{a} Q(s_{i+1},a) - Q(s_i,a_i))^2 $$
The Deep RL Course has a slightly different definition of Off-policy, defining it as having different strategies for training and testing (or, the strategy used to update parameters is different from the one used for actual actions). Under this definition, Q-Learning is also Off-policy: it uses an epsilon-greedy strategy to generate training data while using a pure greedy strategy for actions.
A major issue with DQN is that the Q function used to estimate the TD Target is exactly what we need to learn, and it is noisy. When we update the network that defines the Q function, the TD Target also updates, which some consider a "chasing a moving target" problem. An improvement to this is to use a separate network Q' to estimate the TD target and then assign Q' to Q every few rounds. This method is called Double Q-Learning, and its loss is written as
$$ (r_i + \gamma * \max_{a} Q'(s_{i+1},a) - Q(s_i,a_i))^2 $$
The Spinning-up documentation defines On-policy as model updates that can only utilize data collected through interaction with the current policy and environment. The Deep RL Course defines On-policy as using the same policy during training and testing. Policy gradient methods conform to both definitions of On-policy. Let $\pi$ be the policy network, $\theta$ be the parameters of the policy network, and $\tau$ be the trajectory. The expected return can be written as $\Sigma_{\tau} P(\tau, \theta) R(\tau)$. Policy gradient methods use the Monte Carlo method to estimate the gradient of the expected return with respect to $\theta$ using trajectories $\tau$ obtained from several samples—this is a Monte Carlo summation with importance sampling, and the model update only uses data collected at the current step for the latest policy.
$$ \begin{align*} \nabla_{\theta} \Sigma_{\tau} P(\tau;\theta) R(\tau) &= \Sigma_{\tau} \nabla_{\theta} P(\tau;\theta) R(\tau) \\ &= \Sigma_{\tau} P(\tau;\theta) \frac{\nabla_{\theta}P(\tau;\theta)}{P(\tau;\theta)} R(\tau) \\ &= \Sigma_{\tau} P(\tau;\theta) \nabla_{\theta} \log(P(\tau;\theta)) R(\tau) \\ &= \frac{1}{m} \Sigma_{i=1}^m \nabla_{\theta} \log(P(\tau_i;\theta)) R(\tau_i) \end{align*} $$
where $\tau_i$ must be trajectories sampled by acting according to $\pi(\theta)$.
In fact, since policy gradient methods model the probability $p_i(s, a_i)$ of taking each action $a_i$ in state s, the terms in $P(\tau_i, \theta)$ related to $\theta$ are merely the product of each $\pi(s, a_i)$. The above gradient can be further simplified to
$$ \frac{1}{m} * \Sigma_i^m \Sigma_t^T \nabla_{\theta} \log(p_i(s_t^{i}, a_t^{i}, \theta)) R(\tau^{i}) $$
Removing the gradient operator (the operation of finding the "antiderivative" in calculus), we obtain the loss function, whose gradient with respect to the model parameters is exactly equal to the gradient of the expected return with respect to the model parameters
$$ \texttt{Loss} = \frac{1}{m} * \Sigma_i^m \Sigma_t^T \log(p_i(s_t^{i}, a_t^{i}, \theta)) R(\tau^{i}) $$
This algorithm is called Reinforce.
Q: If the return of each trajectory is positive (for example, the score in a game is always positive), does it mean that every action will be encouraged, or that the gradient will be updated to increase its probability?
A: Indeed. Although the probability of each action is increased, since the probabilities of actions taken in each state need to be normalized, increasing the probability of taking one action will decrease the probability of taking other actions. Ultimately, actions associated with high returns will prevail.
Q: Regarding the double summation needed over multiple trajectories and all moments within each trajectory to estimate the gradient, can it be improved?
A: First, try updating the policy using the reward of a single step instead of the return of the entire trajectory. To do this, you can (why?) replace $R(\tau)$ with the advantage of taking a specific action in a single step, i.e., A(s, a) = Q(s, a) - V(s), where V(s) is the expected return of the current policy in state s, and Q(s, a) is the expected return of the current policy in state s when taking action a.
This chapter is mainly notes of Part 3 of the Spinning Up documentation.
The ELGP (Expected Grad-Log-Prob) Lemma is a commonly derived result in the Spinning up documentation. Suppose $P_{\theta}(x)$ is the distribution function of x parameterized by $\theta$, then
$$ \begin{align*} 0 &= \nabla_{\theta} 1 \\ &= \nabla_{\theta} \int_x P_{\theta}(x) \\ &= \int_x \nabla_{\theta} P_{\theta}(x) \\ &= \int_x P_{\theta}(x) \nabla_{\theta} \log(P_{\theta}(x)) \\ &= E_{x\sim P_{\theta}} \nabla_{\theta} \log(P_{\theta}(x)) \\ \end{align*} $$
This is a chapter from the Spinning Up documentation, interestingly titled don't let the past distract you. Take a close look at the gradient expression in the policy gradient algorithm, where the probability of a specific action in a specific state is increased or decreased by the return of the entire trajectory:
$$ \nabla_{\theta} J = E_{\tau \sim \pi_{\theta}} \Sigma_{t=0}^T \nabla_{\theta} \log(\pi_{\theta} (a_t|s_t) R(\tau)) $$
However, intuitively, the probability of taking an action should not be influenced by the rewards obtained before reaching the current state.
Can you prove that these rewards can be excluded? First, change the order of expectation and summation:
$$ \begin{align*} \nabla_{\theta} J &= E_{\tau \sim \pi_{\theta}} \Sigma_{t=0}^T \nabla_{\theta} \log(\pi_{\theta}(a_t|s_t) \Sigma_{t'=0}^T r(s_{t'},a_{t'})) \\ &= \Sigma_{t=0}^T \Sigma_{t'=0}^T E_{\tau} [\nabla_{\theta} \log(\pi_{\theta}(a_t|s_t)) * r(s_{t'},a_{t'})] \\ \texttt{Denote} X(t,t') &:= E_{\tau} [\nabla_{\theta} \log(\pi_{\theta}(a_t|s_t)) * r(s_{t'},a_{t'})] \end{align*} $$
Take a close look at the summation term X(t,t'). Assume t > t', meaning the moment of obtaining the reward is before the current moment, then
$$ \begin{align*} X(t,t') &= E_{\tau=(s_0,a_0,...,s_{t'},a_{t'},...,s_t,a_t,...,s_T,a_T)} [\nabla_{\theta} \log(\pi_{\theta}(a_t|s_t)) * r(s_{t'},a_{t'})] \\ &\texttt{notice that the term does not depend on } s_{t+1}...a_T \\ &= E_{\tau=(s_0,a_0,...,s_{t'},a_{t'},...,s_t,a_t)} [\nabla_{\theta} \log(\pi_{\theta}(a_t|s_t)) * r(s_{t'},a_{t'})] \\ &= E_{\tau=(s_0,a_0,...,s_{t'},a_{t'},...,s_t)} E_{a_t|s_t} [\nabla_{\theta} \log(\pi_{\theta}(a_t|s_t)) * r(s_{t'},a_{t'})] \\ &= E_{\tau=(s_0,a_0,...,s_{t'},a_{t'},...,s_t)} [r(s_{t'},a_{t'}) * E_{a_t|s_t} [\nabla_{\theta} \log(\pi_{\theta}(a_t|s_t))] ] \\ &\texttt{using the ELGP lemma} \\ &= 0 \end{align*} $$
The core idea of this proof is to write the trajectory $\tau$ in the form of alternating (state, action, state, action, ...). When taking expectations, if the expression inside the expectation is independent of the specific states and actions at the tail of the trajectory, it can be eliminated, truncating the trajectory to the part we are interested in (in fact, summing over these uninteresting states and actions equals one). When the action we are interested in reaches the end of the trajectory, according to the expression of $P(\tau)$, it is factored out.
This illustrates that rewards obtained before the "current moment" are not calculated, and the estimated expectation remains unchanged. The advantage of this is that by considering fewer rewards (or having half as many terms to sum), the variance of the Monte Carlo estimate can be reduced.
Continuing along the above line of thought, can we further use the ELGP lemma to algebraically transform the gradient estimate, thereby further reducing the variance of the Monte Carlo estimate?
According to the ELGP lemma, there is actually the following secondary conclusion:
$$ \begin{align*} E_{\tau} \nabla_{\theta} \pi_{\theta} (a_t|s_t) b(s_t) &= E_{\tau=(s_0,a_0,...,s_t,a_t)} \nabla_{\theta} \pi_{\theta} (a_t|s_t) b(s_t) \\ &= E_{\tau=(s_0,a_0,...,s_t)} b(s_t) E_{a_t|s_t} [\nabla_{\theta} \pi_{\theta} (a_t|s_t)] \\ &= 0 \end{align*} $$
So the gradient estimate can be transformed into
$$ \nabla_{\theta} J = E_{\tau} [\Sigma_{t=0}^T \nabla_{\theta} \log(\pi_{\theta}(a_t|s_t)) * (\text{reward to go} - b(s_t)) ] \\ = E_{\tau} [ \Sigma_{t=0}^T \nabla_{\theta} \log(\pi_{\theta} (a_t|s_t)) \Phi_t] $$
The intuitive meaning is that for each chosen action, its probability is increased or decreased by future rewards plus any bias that depends only on the current state. This bias b is called the baseline.
Choosing the baseline as the on-policy value function (definition here) is intuitively a good choice: this way, what affects the action probability is not the absolute future return, but the difference between the actual return associated with a specific action and the expected return without specifying an action.
The $\Phi_t$ in the previous equation can also be taken as the following result without changing the expectation:
(Transformation 1) On-Policy Action Value Function $Q(s_t, a_t)$, definition here, proof here
(Transformation 2) Therefore, using the Value Function $V(s_t)$ as the baseline, $\Phi_t$ can also be the Advantage Function $A(s_t,a_t) = Q(s_t, a_t) - V(s_t)$
The Actor-Critic method is an improvement of the Reinforce algorithm based on the idea from the second Q&A in the previous section. The modification is that it requires modeling both the value function Q(s,a) and the policy $\pi(s, a_i)$; we use the single-step Q(s,a) instead of the return estimated from the entire trajectory to update the policy (based on Transformation 2).
Specifically, we examine the parameter update method of Advantage Actor-Critic: the gradient is
$$ \nabla_{\theta} E[\log(\pi(s_t, a_t, \theta)) A(s_t, a_t)] $$
The loss function is
$$ E[\log(\pi(s_t, a_t, \theta)) A(s_t, a_t)] $$
Replace the log probability with the ratio function between the new policy and the old policy:
$$ r_t(\theta) = \frac{\pi_{\theta}(a_t|s_t)} {\pi_{\theta_{old}}(a_t|s_t)} $$
The loss function then becomes the objective function
$$ E[r_t(\theta) A(s_t, a_t)] $$
Truncate $r_t(\theta)$ in this objective function to avoid excessive policy changes, and the objective function becomes
$$ E[ \min( r_t(\theta) A(s_t,a_t), clip(r_t(\theta),1-\epsilon,1+\epsilon) A(s_t,a_t))] $$
The reason for taking the min is to provide a pessimistic estimate of the objective function. For example, if A>0 and $r<1-\epsilon$, return the smaller $r*A$ instead of $(1-\epsilon)*A$. In this case, even though r is out of range, the policy is still updated to bring it closer to the range of $[1-\epsilon, 1+\epsilon]$.
This section is excerpted from the Spinning Up documentation.
In SL, the loss function typically involves sampling $x \sim P_{data}$ and then defining the loss function on these samples. $P_{data}$ is independent of the model parameters.
In RL, especially in policy gradient algorithms, the data points used to compute the loss function are sampled based on the latest policy and are related to the model parameters.
In SL, the loss function usually reflects the model's performance (whether on testing or training data).
In RL, especially in policy gradient algorithms, the loss function does not attempt to estimate the expected return; it is merely a primitive function whose gradient with respect to the model parameters happens to equal the gradient of the expected return. Therefore, no matter how small the value of this "loss function" drops to, it cannot guarantee any model performance.
In SL, the variance-bias tradeoff generally refers to the reduction in model bias as the model becomes more complex, but the output becomes more susceptible to noise in the training set, increasing variance.
In RL, besides this variance-bias tradeoff related to model complexity, there is another layer of tradeoff related to the training method.
If using Temporal Difference methods like Q-Learning and A2C Advantage Actor Critic algorithms, the estimation of return is given by the Q or V function. We calculate the gradient based on the previous step's Q or V function and then update the parameters (including the Q and V functions), which is a bootstrapping method.
Since the initial Q and V are random, the estimation of return at the start of training is highly biased.
If using Monte Carlo methods, such as policy gradients, the estimation of return is entirely obtained through interaction with the environment (a complete round). This is a Monte Carlo sampling, with no bias, but a small sample size can lead to high variance.