Reinforcement Learning Memo

A simple memo for learning Reinforcement Learning.（强化学习备忘录）

Terminologies

1. State 状态 $s$, Action 动作 $a$, Reward 奖励 $r$
2. Policy 策略 $\pi: (s,a) \to [0, 1]$

   $$\pi(s | a) = \mathbb{P}(A = a | S = s)$$

3. Trajectory 轨迹: $s_1, a_1, r_1, s_2, a_2, r_2, \dots, s_T, a_T, r_T$
4. Discounted return 折扣回报

   $$U_t = R_t + \gamma R_{t + 1} + \gamma^2 R_{t + 2} + \gamma^3 R_{t + 3} + \cdots$$

5. Action-value function 动作价值函数

   $$Q_\pi(s_t,a_t) = \mathbb{E}[U_t | S = s_t, A = a_t]$$

6. Optimal action-value function 最优动作价值函数

   $$Q^*(s_t,a_t) = \max_\pi Q_\pi(s_t,a_t)$$

7. State-value function 状态价值函数

   $$V_\pi(s_t) = \mathbb{E}_A[Q_\pi(s_t, A)] = \sum_{a \in A} \pi(a|s_t) \cdot Q_\pi(s_t, a)$$

   • $\mathbb{E}_S[V_\pi(S)]$ evaluates how good the policy $\pi$ is.

Value-based Learning

• Goal: Approximate the Q function to maximize the total reward.

Temporal Difference (TD) Learning

$$Q(s_t,a_t;\mathbf{w}) = r_t + \gamma \cdot Q(s_{t+1},a_{t+1};\mathbf{w})$$

• Prediction: $Q(s_t,a_t;\mathbf{w}_t)$
• TD target:

$$y_t = r_t + \gamma \cdot Q(s_{t+1},a_{t+1};\mathbf{w}_t)$$

• Loss:

$$L_t = \frac{1}{2}[Q(s_t,a_t;\mathbf{w}) - y_t]^2$$

• Gradient descent:

$$\mathbf{w}_{t+1} = \mathbf{w}_t - \alpha \cdot \frac{\partial L_t}{\partial \mathbf{w}} \vert_{\mathbf{w} = \mathbf{w}_t}$$

SARSA

• Goal: Learn the action-value function $Q_\pi$.

Tabular Version

• Goal: Directly learn $Q_\pi(s,a)$.
• Algorithm:
  1. Observe a transition $(s_t, a_t, r_t, s_{t+1})$
  2. Sample $a_{t+1} \sim \pi(\cdot|s_{t+1})$
  3. TD target: $y_t = r_t + \gamma \cdot Q_\pi(s_{t+1}, a_{t+1})$
  4. TD error: $\delta_t = Q_\pi(s_t,a_t) - y_t$
  5. Update: $Q_\pi(s_t,a_t) \gets Q_\pi(s_t,a_t) - \alpha \cdot \delta_t$

Neural Network Version

• Goal: Approximate $Q_\pi(s,a)$ by the value network $q(s,a;\mathbf{w})$.
• Algorithm:
  1. Observe a transition $(s_t, a_t, r_t, s_{t+1})$
  2. TD target: $y_t = r_t + \gamma \cdot q(s_{t+1},a_{t+1};\mathbf{w})$
  3. TD error: $\delta_t = q(s_t,a_t;\mathbf{w}) - y_t$
  4. Update: $\mathbf{w} \gets \mathbf{w} - \alpha \cdot \delta_t \cdot \frac{\partial q(s_t,a_t;\mathbf{w})}{\partial \mathbf{w}}$

Q-Learning

• Goal: Learn the optimal action-value function $Q^*$.

Tabular Version

• Goal: Directly learn $Q^*(s,a)$.
• Algorithm:
  1. Observe a transition $(s_t, a_t, r_t, s_{t+1})$
  2. TD target: $y_t = r_t + \gamma \cdot \max_a Q^*(s_{t+1}, a)$
  3. TD error: $\delta_t = Q^*(s_t,a_t) - y_t$
  4. Update: $Q^*(s_t,a_t) \gets Q^*(s_t,a_t) - \alpha \cdot \delta_t$

DQN Version

• Goal: Approximate $Q^*(s,a)$ by the DQN, $Q(s,a;\mathbf{w})$
• Policy: Choose $a_t = \argmax_{a} Q(s_t,a;\mathbf{w})$
• Algorithm:
  1. Observe a transition $(s_t, a_t, r_t, s_{t+1})$
  2. TD target: $y_t = r_t + \gamma \cdot \max_a Q(s_{t+1}, a; \mathbf{w})$
  3. TD error: $\delta_t = Q(s_t,a_t;\mathbf{w}) - y_t$
  4. Update: $\mathbf{w} \gets \mathbf{w} - \alpha \cdot \delta_t \cdot \frac{\partial Q(s_t,a_t;\mathbf{w})}{\partial \mathbf{w}}$

Policy-based Learning

• Goal: Learn $\mathbf{\theta}$ that maximize $J(\mathbf{\theta}) = \mathbb{E}_S[V(S;\mathbf{\theta})]$.
• Idea: Approximate policy function $\pi(a|s)$ by policy network $\pi(a|s;\mathbf{\theta})$.
  • Learn the policy network by policy gradient.

Policy Gradient

• Policy gradient:

$$\frac{\partial V(s_t;\mathbf{\theta})}{\partial \mathbf{\theta}} = \mathbb{E}_{A_t \sim \pi}\left[\frac{\partial \ln \pi(A_t|s_t;\mathbf{\theta})}{\partial \mathbf{\theta}} \cdot Q_{\pi}(s_t,A_t)\right]$$

• Policy gradient with baseline: Suppose $b$ is independent of $A_t$, then

$$\begin{aligned} \frac{\partial V(s_t;\mathbf{\theta})}{\partial \mathbf{\theta}} =& \, \mathbb{E}_{A_t \sim \pi}\left[\frac{\partial \ln \pi(A_t|s_t;\mathbf{\theta})}{\partial \mathbf{\theta}} \cdot (Q_{\pi}(s_t,A_t) - b)\right] \\ =& \, \mathbb{E}_{A_t \sim \pi}\left[\frac{\partial \ln \pi(A_t|s_t;\mathbf{\theta})}{\partial \mathbf{\theta}} \cdot \left(Q_{\pi}(s_t,A_t) - V_\pi(s_t)\right)\right] \end{aligned}$$

REINFORCE

• Goal: Approximate $Q_{\pi}(s_t,A_t)$ by $u_t$ and $V_\pi(s_t)$ by value network $v(s_t;\mathbf{w})$
• Algorithm:
  1. Play a game to the end and observe the trajectory:

  $$s_1, a_1, r_1, s_2, a_2, r_2, \ldots, s_n, a_n, r_n$$

  2. Compute $u_t = \sum_{i=t}^n \gamma^{r-t}\cdot r_i$ and $\delta_t = v(s_t;\mathbf{w}) - u_t$
  3. Update the policy network by:

  $$\mathbf{\theta} \gets \mathbf{\theta} - \beta \cdot \delta_t \cdot \frac{\partial \ln \pi(a_t|s_t;\mathbf{\theta})}{\partial \mathbf{\theta}}$$

  4. Update the value network by:

  $$\mathbf{w} \gets \mathbf{w} - \alpha \cdot \delta_t \cdot \frac{\partial v(s_t;\mathbf{w})}{\partial \mathbf{w}}$$

  5. Repeat procedure 2 to 4 for $t = 1, \dots, n$

Actor-Critic

• Goal: Approximate policy function $\pi(a|s)$ by policy network $\pi(a|s;\mathbf{\theta})$ and state-value function $V_\pi(s)$ by value network $v(s;\mathbf{w})$.
  • Actor: Update policy network $\pi(a|s;\mathbf{\theta})$ using policy gradient to increase $V(s;\mathbf{\theta}, \mathbf{w})$
  • Critic: Update value network $v(s;\mathbf{w})$ using TD learning to better estimate the return
• Algorithm:
  1. Observe a transition $(s_t,a_t,r_t,s_{t+1})$
  2. TD target: $y_t = r_t + \gamma \cdot v(s_{t+1};\mathbf{w})$
  3. TD error: $\delta_t = v(s_t;\mathbf{w}) - y_t$
  4. Update the policy network (actor) by:

  $$\mathbf{\theta} \gets \mathbf{\theta} - \beta \cdot \delta_t \cdot \frac{\partial \ln \pi(a_t|s_t;\mathbf{\theta})}{\partial \mathbf{\theta}}$$

  5. Update the value network (critic) by:

  $$\mathbf{w} \gets \mathbf{w} - \alpha \cdot \delta_t \cdot \frac{\partial v(s_t;\mathbf{w})}{\partial \mathbf{w}}$$

TRPO (Trust Region Policy Optimization)

• Trust region algorithm: Find $\mathbf{\theta}^* = \argmax_{\mathbf{\theta}} J(\mathbf{\theta})$.
  1. Approximation: Given $\mathbf{\theta}_\text{old}$, construct $L(\mathbf{\theta}|\mathbf{\theta}_\text{old})$, which is an approximation to $J(\mathbf{\theta})$ in $\mathcal{N}(\mathbf{\theta}_\text{old})$
  2. Maximization: In the trust region, find $\mathbf{\theta}_\text{new}$ by:

  $$\mathbf{\theta}_\text{new} \gets \argmax_{\mathbf{\theta} \in \mathcal{N}(\mathbf{\theta}_\text{old})} L(\mathbf{\theta}|\mathbf{\theta}_\text{old})$$

• Object function:

$$J(\mathbf{\theta}) = \mathbb{E}_S[V_\pi(S)] = \mathbb{E}_S\left[\mathbb{E}_{A \sim \pi(\cdot|s;\mathbf{\theta}_\text{old})}\left[\frac{\pi(A|S;\mathbf{\theta})}{\pi(A|S;\mathbf{\theta}_\text{old})} \cdot Q_\pi(S,A)\right]\right]$$

• Algorithm:
  1. Controlled by the policy $\pi(\cdot|s;\mathbf{\theta}_\text{old})$, the agent plays a game to the end and observes a trajectory:

  $$s_1, a_1, r_1, s_2, a_2, r_2, \ldots, s_n, a_n, r_n$$

  2. For $i = 1, 2, \ldots, n$, compute discounted returns: $u_i = \sum_{k=i}^n \gamma^{k-i} \cdot r_k$
  3. Approximation:

  $$\tilde{L}(\mathbf{\theta}|\mathbf{\theta}_\text{old}) = \frac{1}{n} \sum_{i=1}^n \frac{\pi(a_i|s_i;\mathbf{\theta})}{\pi(a_i|s_i;\mathbf{\theta}_\text{old})} \cdot u_i$$

  4. Maximization:

  $$\mathbf{\theta}_\text{new} \gets \argmax_{\mathbf{\theta}} \tilde{L}(\mathbf{\theta}|\mathbf{\theta}_\text{old}); \quad s.t. \, \Vert \mathbf{\theta} - \mathbf{\theta}_\text{old} \Vert < \Delta$$

• Goal:

  $$\begin{aligned} & \argmax_{\mathbf{\theta'}} \mathbb{E}_{s \sim v_{\mathbf{\theta}}, a \sim \pi_{\mathbf{\theta}(\cdot|s)}} \left[\frac{\pi_{\mathbf{\theta'}}(a,s)}{\pi_{\mathbf{\theta}}(a,s)} \cdot A_{\pi_{\mathbf{\theta}}}(s,a)\right] \\ s.t. & \quad D_{KL}(\pi_{\mathbf{\theta}}(\cdot|s) \Vert \pi_{\mathbf{\theta'}}(\cdot|s)) < \Delta \end{aligned}$$

  where $A_{\pi_{\mathbf{\theta}}}(s,a)$ is the advantage function.

PPO (Proximal Policy Optimization)

• PPO-penalty:

  $$\argmax_{\mathbf{\theta'}} \mathbb{E}_{s \sim v_{\mathbf{\theta}}, a \sim \pi_{\mathbf{\theta}(\cdot|s)}} \left[\frac{\pi_{\mathbf{\theta'}}(a,s)}{\pi_{\mathbf{\theta}}(a,s)} \cdot A^{GAE}_{\pi_{\mathbf{\theta}}}(s,a) - \beta \cdot D_{KL}(\pi_{\mathbf{\theta}}(\cdot|s) \Vert \pi_{\mathbf{\theta'}}(\cdot|s))\right]$$

  • $\beta \gets \beta / 2 \quad \text{if } D_{KL} < \delta / 1.5$
  • $\beta \gets \beta \times 2 \quad \text{if } D_{KL} > \delta \times 1.5$
• PPO-clip:

  $$\argmax_{\mathbf{\theta'}} \mathbb{E}_{s \sim v_{\mathbf{\theta}}, a \sim \pi_{\mathbf{\theta}(\cdot|s)}} \left[\min\left(\frac{\pi_{\mathbf{\theta'}}(a,s)}{\pi_{\mathbf{\theta}}(a,s)}A^{GAE}_{\pi_{\mathbf{\theta}}}(s,a), clip\left(\frac{\pi_{\mathbf{\theta'}}(a,s)}{\pi_{\mathbf{\theta}}(a,s)}, 1-\epsilon, 1+\epsilon\right)A^{GAE}_{\pi_{\mathbf{\theta}}}(s,a)\right)\right]$$

GAE (Generalized Advantage Estimation)

$$\begin{aligned} A_t^{(k)} =& \, r_t + \gamma r_{t+1} + \cdots + \gamma^{k-1} r_{t+k-1} + \gamma^k V(s_k) - V(s_t) \\ =& \, \delta_t + \gamma \delta_{t+1} + \cdots \gamma^{k-1} \delta_{t+k-1} \end{aligned}$$

$$A^{GAE}_t = (1-\lambda)(A_t^{(1)} + \lambda A_t^{(2)} + \lambda^2 A_t^{(3)} + \cdots) = \sum_{l=0}^{\infty} (\gamma\lambda)^l \delta_{t+l}$$

GRPO (Group Relative Policy Optimization)

References

1. 王树森,黎或君,张志华.深度强化学习.人民邮电出版社,2022.https://github.com/wangshusen/DRL
2. 张伟楠,沈键,俞勇.动手学强化学习.人民邮电出版社,2022.https://github.com/boyu-ai/Hands-on-RL
3. https://www.bilibili.com/video/BV1rooaYVEk8
4. https://www.bilibili.com/video/BV15cZYYvEhz