[RL] 강화학습 이론: On-policy & Off-policy

---

강화학습 알고리즘은 on-policy 방식과 off-policy 방식으로 분류될 수 있습니다. On-policy와 Off-policy의 차이는 아래와 같습니다.

 

• On-policy methods: Behavior policy = Target policy
• Off-policy methods: Behavior policy ≠ Target policy

 

여기서 behavior policy와 target policy의 개념이 나오는데 아래와 같습니다.

 

• Behavior policy $b(a|s)$: Action을 선택하고 데이터 샘플을 얻을 때 사용되는 policy
• Target policy $\pi(a|s)$: 평가(evaluate)하고 업데이트(improve)하고자 하는 policy

 

즉 정책 업데이트를 위한 $V(s)$ 또는 $Q(s,a)$를 계산하는데는 target policy $\pi(a|s)$가 사용되며, 실제로 agent가 수행한 action에 의해 획득된 sample들은 behavior policy $b(a|s)$를 따릅니다.

 

$$\{s_1,a_1,r_1,\dots,s_T\}\sim b(a|s)$$

 

대표적으로는 Q-learning이 off-policy 알고리즘이고 SARSA가 on-policy 알고리즘입니다. 예시를 통해 좀더 살펴보도록 하겠습니다.

 

1) Off-Policy Example (Q-learning)

Figure 1. Q-learning 알고리즘

Q-learning은 $\epsilon$-greedy 방식을 통해 action을 선택합니다. 따라서 discrete action space를 $\mathcal{A}$라고 할 때, Q-learning의 behavior policy $b(a|s)$는 아래와 같습니다.

 

$$b(a|s)=\begin{cases} (1-\epsilon)+\frac{\epsilon}{|\mathcal{A}|}~&\text{if}~~~a=\arg\max Q(s,a) \\ \frac{\epsilon}{|\mathcal{A}|}~&\text{otherwise} \end{cases}$$

 

따라서 state $s_t$에서 behavior policy에 따라 $a_t$를 수행하여 $(s_t,a_t,r_t,s_{t+1})$의 sample을 획득할 수 있습니다. 이 때 Q-learning의 update rule은 아래와 같습니다. 

 

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

 

위 식에서 현재 평가된 $(s_t,a_t)$에서의 state-action value가 $Q_\text{old}=Q(s_t,a_t)$일 때, 새로 평가된 state-action value는 $Q_\text{new}=r_t+\gamma \max_a Q(s_{t+1},a)$입니다. 이때 behavior policy에 의해 $a_{t+1}$을 선택하여 $Q_\text{new}$를 계산하는 것이 아니라, $s_{t+1}$에서 가장 높은 Q-value를 가지는 $a_{t+1}$를 선택하여 $Q_\text{new}$를 계산합니다. 다시 말해 Q-learning의 target policy는 greedy poilcy로 아래와 같습니다.

 

$$\pi(a|s)=\begin{cases} 1~&\text{if}~~~a=\arg\max Q(s,a) \\ 0~&\text{otherwise} \end{cases}$$

 

따라서 Q-learning은 behavior policy와 target policy가 다르므로 off-policy 알고리즘입니다.

 

Figure 2. Off-policy 알고리즘의 behavior policy와 target policy 예시

 

2) On-Policy Example (SARSA)

Figure 3. SARSA 알고리즘

SARSA 역시 $\epsilon$-greedy 방식을 통해 action을 선택합니다. 따라서 Q-learning의 behavior policy $b(a|s)$는 Q-learning과 동일합니다. SARSA의 update rule은 아래와 같습니다. 

 

$$Q(s_t,a_t) \leftarrow Q(s_t,a_t)+\alpha\left[r_t+\gamma Q(s_{t+1},a_{t+1})-Q(s_t,a_t) \right]$$

 

SARSA는 Q-learning과 다르게 behavior policy에 따라 $a_{t+1}$를 선택하고 그에 해당하는 $Q(s_{t+1},a_{t+1})$을 이용하여 $Q_\text{new}$를 계산합니다. 따라서 SARSA는 behavior policy와 target policy가 $\epsilon$-greedy로 동일하므로 on-policy 알고리즘입니다.

 

$$b(a|s)=\pi(a|s)=\begin{cases} (1-\epsilon)+\frac{\epsilon}{|\mathcal{A}|}~&\text{if}~~~a=\arg\max Q(s,a) \\ \frac{\epsilon}{|\mathcal{A}|}~&\text{otherwise} \end{cases}$$

 

Figure 4. On-policy 알고리즘의 behavior policy와 target policy 예시

 

3) On-Policy & Off-Policy의 장단점

Off-policy의 장단점

(+) High sample efficiency: 과거의 policy로부터 획득한 sample을 현재 policy를 업데이트할 때 여러번 재사용이 가능하여 environment와의 상호작용을 적게 할 수 있습니다.

(-) High bias error: 과거의 policy와 현재의 policy가 많이 달라진 경우, 과거의 sample은 현재의 policy를 업데이트 하기에 좋은 sample이 아닐 수 있습니다.

 

On-policy의 장단점

(+) Low bias error: Behavior policy와 target policy가 같으므로 일반적으로 bias error를 유발시키지 않아 성능이 안정적입니다.

(-) Low sample efficiency: 획득한 sample을 이용해 policy를 한번 업데이트하고 폐기하므로 environment와의 상호작용이 많이 필요합니다.

 

References

[1] R. S. Sutton et al., "Reinforcement Learning: An Introduction," MIT Press, 2018.

[2] R. Fakoor et al., "P3O: Policy-on Policy-off Policy Optimization," arXiv, 2019.

---

강화학습 스터디의 다른 글 목록

• 강화학습 이론: On-policy & Off-policy
• 강화학습 알고리즘: (1) DQN (Deep Q-Network)
• 강화학습 알고리즘: (2) Double DQN
• 강화학습 알고리즘: (3) Dueling DQN
• 강화학습 알고리즘: (4) DDPG
• 강화학습 알고리즘: (5) PPO

 

---

오타나 잘못된 부분 있으면 댓글 부탁드립니다. 도움이 되셨다면 공감 눌러 주시면 감사하겠습니다 :)