Deep Q Network (DQN)

 이번 글에서 리뷰할 강화학습 알고리즘은 Deep Q-Network (DQN)이다. DQN은 AI의 최강자인 Google Deepmind에서 개발한 알고리즘으로, 강화학습에 Deep Learning을 적용하는 방식의 뼈대가되는 논문 [1] [2]이다. 많은 시나리오에서 자주 사용되고, 강화학습 알고리즘의 큰 축 중에 하나기 때문에, 이미 많은 리뷰들이 있다. 이 글에서도, 간단하게 리뷰를 하고, 이를 이용한 여러 논문들도 함께 소개해보고자 한다.

 

DQN 알고리즘

 Deep Q-Network (DQN)은 이름에서 알 수 있듯이, state-action value Q값을 Deep Learning을 통해서 Approximate하는 방식이다. DQN이 나오기 전에는, state-action에 따른 값들을 모두 Table 형태 (Q-Table)로 Update하면서 갖고 있다가, 이를 참고하여 Action을 선택하는 방식으로 Policy가 구성되어 있었다. 이렇게 Episode를 진행하면서, 최종적인 Cumulative Reward를 최대화하도록 Q-Table을 Update해나가는 방식이었다.

 현재 갖고있는 Q-Table을 기반으로 Policy를 정하되, Updating Policy와 Target Policy가 같으면 On-policy인 SARSA, 두 Policy가 다르면 Off-Policy인 Q-Learning이 된다. 어떤 방식이던, Table을 기반으로 하고, State-Action에 대한 모든 값을 갖고 있어야하기 때문에, State가 많아지면, 엄청나게 큰 Table을 가져야 한다. 가장 예로 많이 드는 Atari Game의 경우, State가 Color-Image이기 때문에, State가 엄청 커지고, Memory 소모도 커지고, Training에도 문제가 생긴다. DQN은 이를 보완하기 위해, Table 형태가 아니라, w라는 가중치를 갖고 있는 Deep Learning 모델로 Approximate한다.

 현실에 있는 대부분의 Case는 High-Dimension Data (e.g., Vision)을 대상으로 하고 있기 때문에, DQN은 강화학습 알고리즘을 발전시키는 큰 축 중에 하나로 꼽힌다. 하지만, 단순하게 Deep Learning을 적용하려고 하면 크게 2가지 문제가 생겨난다.

 

Deep Learning (DL) 적용시 문제점과 해결방법

1. Deep Learning은 Label (정답)이 있는 Data를 학습시키는데, Reinforcement Learning은 Label이 없고, 가끔 들어오는 Reward로 학습을 시켜야하기 때문에, 제대로 된 학습이 되기 힘들다.

2. Deep Learning은 Data Sample이 i.i.d (서로 독립적)이라는 가정을 하지만, Reinforcement Learning에서는 다음 State가 현재 State과 연관성 (Correlation)이 크기 때문에 이 가정이 성립하지 않는다.

 이런 문제점 때문에 단순히 Q-Table을 Deep Learning Model로 치환하는 것으로는 제대로된 학습 효과를 보기 힘들다. 따라서, DQN을 제시한 논문[1]에서는 Experience Replay라는 방법을 사용한다. 쉽게 말하면, '강화학습 Episode를 진행하면서, 바로 DL의 Weight를 학습시키는 것이 아니라, Time-Step마다 [S(Current State), A(Action), R (Reward), S'(Next State)] Data set을 모아서 학습하자는 방법'이다. 

 이렇게 모은 Data를 Random하게 뽑으면, 각 Data 간의 Correlation이 줄어들기 때문에 2번 문제를 해결할 수 있다. 추가적으로, Data를 여러 번 재활용할 수 있다는 부수효과도 얻을 수 있다. 이렇게 만든 Experience-Replay Buffer는 N개의 크기를 갖고 있다가, Buffer가 꽉차면 일부 Data를 새로운 Sample로 대체하는 방식을 갖게 된다. DQN 논문 [1]에 실려있는 알고리즘은 다음과 같다.

DQN의 알고리즘 [1]

 DeepMind는 이 알고리즘을 AI의 3대 학회인 NIPS (2013)에 출판하고 났는데, 조금 더 성능을 향상시킬 수 있는 방식 [2]을 2015년 또 제시하고, 이번에는 Nature (2015)에 실린다.

 Update된 알고리즘은 'Target Network'와 'Update Network'를 분리하자는 내용이 추가되어 있다. [1] 알고리즘 밑에서 3번째 줄을 보면, Gradient Descent를 계산할 때, 모두 동일한 theta가 들어있다. 곰곰히 생각해보면, DL에서 사용되는 label 값에 해당하는 y_i와 우리가 Update하려는 Q값이 theta에 의해 동시에 움직인다는 뜻이 된다. 내가 열심히 달려가는데 목표도 같이 움직이면 어디를 보고 달려야할지 매우 헷갈릴 것이다. 따라서, y_i를 일정 Step동안 Target Value로 고정하고, Q값을 theta에 의해 update하는 방식을 사용한다. 그리고, 주기적으로 Target Value를 Update된 Value로 동기화시켜주는 방법으로 성능을 향상시켰다.

DQN 알고리즘 [2]

 이렇게 DQN 알고리즘을 제안했는데, 이 과정에서 사용하는 Experience-Replay와 Target Network는 Deep Learning을 강화학습에 적용하는 대부분의 논문에 비슷하게 적용된다. 

 

DQN을 적용한 논문들

 통신, 네트워크의 Resource Allocation 논문에 Non-Convex / NP-hard / High Complexity라는 얘기가 나오면, 쉽게 최적화를 하기 힘들다는 뜻이다. 그리고 이 때, 강화학습이 많이 사용된다. Resource Allocation에 강화학습을 적용할 때, State가 Continuous하게 Modeling되면, Deep Reinforcement Learning을 사용해야한다. 이를 위해 대표적으로 사용되는 알고리즘이 DQN, 뒤에서 다룰 Actor-Critic, DDPG다. Resource Allocation에 관한 문제는 대표적으로 Frequency (Channel)과 Power를 할당하는 Issue, Computing Resource를 할당하는 Issue로 나눌 수 있다.

 [3] 논문은 Mobile-Edge Computing (MEC)에 DQN을 적용해서, Computing Resource를 할당하고, Complete Time을 Minimize하는 방법을 Proposal하고 있다. [4] 논문은 Vehicular Network에서 해당 Vehicle을 어떤 Channel에 얼만큼의 Power를 Allocate해야 하는지를 DQN을 적용해서 제안을 하고 있다.

 

Conclusion

 이번 글에서는 DQN에 대한 소개와 핵심적인 아이디어에 대해서 정리했다. 알고리즘을 가져다가 쓰는거는 OpenAI Baseline이나 Keras-rl에 잘 정리되어 있기 때문에, 어렵지 않게 사용할 수 있을 것이다. 단, 모델을 사용하기 위한 환경은 자신의 연구주제에 맞게 자기가 만들어야 한다. 위에 소개한 논문을 비롯해 많은 논문들을 참고하면, 자신에게 맞는 환경을 설계하고, 모델을 사용하는데 도움이 될 것이라고 생각한다.

 

Reference

[1] Mnih, V., Kavukcuoglu, K., Silver, D., Graves, A., Antonoglou, I., Wierstra, D., and Riedmiller, M. (Dec 2013). Playing Atari with deep reinforcement learning. Technical Report arXiv:1312.5602 [cs.LG], Deepmind Technologies.

[2] V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, J. Veness, M. G. Bellemare, A. Graves, M. Riedmiller, A. K. Fidjeland, G. Ostrovski, S. Petersen, C. Beattie, A. Sadik, I. Antonoglou, H. King, D. Kumaran, D. Wierstra, S. Legg, and D. Hassabis. Human-level control through deep reinforcement learning. Nature, 518(7540):529–533, 02 2015. dx.doi.org/10.1038/nature14236.

[3] X. Xiong, K. Zheng, L. Lei and L. Hou, "Resource Allocation Based on Deep Reinforcement Learning in IoT Edge Computing," in IEEE Journal on Selected Areas in Communications, vol. 38, no. 6, pp. 1133-1146, June 2020, doi: 10.1109/JSAC.2020.2986615.

[4] L. Liang, H. Ye, G. Yu, and G. Y. Li, “Deep learning based wireless resource allocation with application to vehicular networks,” Proc. IEEE, vol. 108, no. 2, pp. 341–356, Feb. 2020.