on-policy Learning vs off-policy Learning

강화학습의 on-policy 와 off-policy update 방식의 차이점을 생각하고 정리합니다.

 

먼저, 직관적인 배경 지식에 대해 먼저 알고 갑니다.

 

on-policy와 off-policy를 나누는 기준은 무엇인가?

• Q-learning (off-policy)

\begin{equation}
Q(a, s) \leftarrow Q(a, s)+\alpha \cdot\left(r_s+\gamma \max _{a^{\prime}} Q\left(a^{\prime}, s^{\prime}\right)-Q(a, s)\right)
\end{equation}

 

• Sarsa (on-policy)

\begin{equation}
Q(a, s) \leftarrow Q(a, s)+\alpha \cdot\left(r_s+\gamma \cdot Q\left(a^{\prime}, s^{\prime}\right)-Q(a, s)\right)
\end{equation}

 

위의 수식과 같이 target이 behavior와 다르면 off-policy고 같으면 on-policy라는 사실은 다들 아실것입니다.

저도 다르다는 차이만을 인지했지만, 이것이 다르면 어떤 차이가 발생하는지 깊게 고민해본것은 이번이 처음입니다.

 

추가로, off-policy 방식에는 잘 알려진 DQN, DDPG, SAC 등이 있습니다.

on-policy에는 Actor-Critic, TRPO, PPO가 있습니다.

 

직관적인 차이점은 무엇일까요?

DQN은 state transition을 replat buffer에 쌓고 그중에 가장 큰 Q value를 가지게하는 action을 target으로 정합니다.

반면 Actor Critic은 따로 buffer는 존재하지 않고, 명시적인 policy를 설정하고 roll-out을 통해 value를 평가하고 그 평가를 바탕으로 policy를 greedy하게 update합니다.

 

이러한 과정이 어디와 가장 유사했는지 생각을 해보니, 바로 value iteration과 policy iteration이었습니다.

한번 더 들어가면, value iteration은 bellman optimality equation을 근간으로하며,

policy iteration은 bellman expectation equation을 근간으로 합니다.

 

Bellman Optimality Equation

\begin{equation}
v_*(s)=\max \sum_{s^{\prime}, r} p\left(s^{\prime}, r \mid s, a\right)\left[r+\gamma v_*\left(s^{\prime}\right)\right]
\end{equation}

 

Bellman Expected Equation

\begin{equation}
v_\pi(s)=\sum_u \pi(a \mid s) \sum_{s^{\prime}, r} p\left(s^{\prime}, r \mid s, a\right)\left[r+\gamma v_\pi\left(s^{\prime}\right)\right]
\end{equation}

 

이제 조금은 더 직관적으로 다가 왔을 것입니다.

 

DQN을 생각해보면 "왜 A3C에는 replay buffer를 사용 안하지?"라는 의문을 가진적이 있을 것입니다.

결국 DQN은 value iteration에서와 같이 현재 쌓아둔 sample안에서 가장 큰 next state의 value가 optimal일 것이다.라는 가정에서 출발한 것이고 또한, value iteration이 기본이 되기 때문에 명확한 policy 없이 학습이 종료된 Q(s,a) approximator에서 나오는 action이 optimal이다.라는 것입니다.

 

결국 sample 안에서 optimal을 근사하기 때문에, sample 내부에 True optimal이 어느 정도는 존재해야 greedy하게 action을 선택하여 학습하였을 때 정확도도 좋을 것입니다.

 

하지만, 다양한 sample에 대해 탐험하지 못한다면, local optimal에 빠질 가능성이 있기에 exploration은 필수입니다.

 

On-policy의 경우 Bellman expected equation이 기본이됩니다. 따라서, policy를 eval하고 improvement하는 과정이 포함되며

결국은 명시적 policy의 update가 발생하기 때문에 이전 policy에 의한 transition들로 policy를 update할 수가 없게 됩니다.

 

이제 어느정도 직관적인 이해가 됐으면, 수렴성이 중요해집니다.

 

그래서 Value Iteration과 Policy Iteration은 수렴을 해?

 

Policy Iteration 수렴 증명

 

Value Iteration 수렴 증명