[Part 6] Partial Observability and Deep Recurrent Q-Networks

포스팅에 앞서 Reference의 contents를 review하는 글임을 밝힙니다.

이번 포스팅에서는 강화학습의 Partial observability 문제에 대해 다루겠습니다. 비교적 간단한 환경에서 구현된 agent라면 문제가 되지 않으나 현실 세계와 같은 문제에서는 Partial observability 문제가 발생합니다. 하지만 인간은 시각적으로나 논리적으로, 먼 미래의 현상을 정확하게 예견할 수 없는 환경에서 발생하는 문제를 비교적 정확하게 해결합니다. Partial observability 문제는 어떻게 해결했을까요?

---

The Problem of Partial Observability

앞의 Part 4와 Part 5에서의 gridworld 환경에서 구현했던 agent는 optimal policy를 찾기 위해 environment로부터 모든 정보를 얻을 수 있었습니다. 아래 그림을 보겠습니다.

<Fig1. Fully observability MDP>

해당 환경은 9x9 gridworld로, agent는 파란 박스를 움직여서 50걸음 내에 빨간 박스를 피해 최대한 초록 박스에 도달하는 policy를 찾게 됩니다. 빨간 박스나 초록 박스에 도착하면 gridworld 내에 임의의 위치로 변경되며, 초록 박스는 +1의 reward 그리고 빨간 박스는 -1의 reward를 반환합니다. 해당 환경에서는 모든 조건을 관찰 가능하기때문에, agent가 optimal policy를 찾는 데 알아야할 것들을 그대로 이용할 수 있습니다. 이런 환경을 MDP(Markov Decision Process)라고 하고, 이는 Ch. 2에서 다루었습니다. 

이에 비해 partial observability 문제는 해당 world에서 아래와 같은 3x3 region만 볼 수 있습니다.

<Fig2. Partial observability MDP>

확실히 제한적인 환경입니다. 심지어 끝부분에 가면 관찰가능한 grid는 2x3, 3x2로 줄어듭니다. 당장 주위에 아무것도 없는 환경도 나타나기도 하구요. 이와 같이 state의 observability가 보장되지 못하는 환경을 POMDP(Partial Observability MDP)라고 합니다. 이러한 환경에서 agent를 구성하기 위해서는 어떠한 방법을 사용해야할까요?

Making sense of a limited, changing world

부분적인 정보가 제한된다면, 이 부분부분을 관찰할때마다 정보를 모아서 합치는 것입니다. 아래 그림을 보시면 소녀와 야구선수가 공을 주고 받고 있습니다. 

<Fig3. The baseball going from whom?>

하지만, 조금 헷갈릴 수 있는 여지가 있습니다. 공이 야구선수에게서 소녀로 가는지, 아니면 소녀에게서 야구선수에게로 가는지 이 그림만으로는─물론 글러브가 없는 여자아이에게 공을 던졌겠는가? 하고 의문을 가질수도 있지만, 여전히─ 정보가 부족합니다. 만약, 여기에 다음 과정을 담은 그림을 한 장 더 얻을 수 있다면 어떨까요? 우리는 공이 어디로부터 어디에게로 가는지 확실히 알 수 있습니다. 즉, 부분의 정보가 부족하다면 time step마다 그 정보를 모아 전체의 정보를 얻는 아이디어를 떠올릴 수 있는 것이지요. 

DeepMind의 DQN에서는 Atari simulator로부터 frame을 쌓는 방법으로 이를 해결했습니다. 단순히 하나의 frame을 network에 넣는 것이 아니라 별도의 buffer memory에 game의 마지막 4 frame을 stack으로 쌓아 저장해두고 이를 network에 넣는 것입니다. 하지만, 이것은 game 환경에서만 잘 작동하며 아래와 같은 issue가 발생합니다.

• buffer memory inefficiency, 단순히 하나의 frame을 넘기는 것보다 4 frames block을 넘길 때 보다 많은 memory buffer를 사용하게 됩니다. 다른 환경에서는 이 buffer의 한계를 가늠할 수 없을만큼 많은 data가 저장될 수 있습니다.
  
• loss of information, 이렇듯 buffer memory에 한계가 있다보니 FIFO방식으로 data를 저장하는데, 정작 필요한 data를 쓰려고보니 새로운 data에 밀려 없어져있는 경우도 생길 수 있습니다. 즉, 이 4 frames도 정보가 부족할 수 있습니다.

위와 같은 issue들을 해결하기 위해서 RNN의 장점을 이용합니다.

 DRQN(Deep Recurrent Q-Networks)

 먼저, 우리가 agent를 구성하게 될 환경, POMDP에 대해서 다시한번 짚고 넘어가겠습니다. DRQN이 소개된 논문에서는 POMDP에 대해 다음과 같이 말하고 있습니다.

 In real world environments it’s rare that the full state of the system can be provided to the agent or even determined. In other words, the Markov property rarely holds in real world environment. (...) 

Formally a POMDP can be described as a 6-tuple (S, A, P, R, Ω, O). S, A, P, R are the states, actions, transitions, and rewards as before, except now the agent is no longer privy to the true system state and instead receives an observation o ∈ Ω. This observation is generated from the underlying system state according to the probability distribution o ∼ O(s).

 Vanilla Deep Q-Learning has no explicit mechanisms for deciphering the underlying state of the POMDP and is only effective if the observations are reflective of underlying system states. In the general case, estimating a Q-value from an observation can be arbitrarily bad since Q(o, a|θ) ≠ Q(s, a|θ).

 Our experiments show that adding recurrency to Deep Q-Learning allows the Q-network network to better estimate the underlying system state, narrowing the gap between Q(o, a|θ) and Q(s, a|θ).

중요하다고 생각하는 부분만 발취한 것인데, 요점은 아래와 같습니다.

• real world에서 fully observable한 경우는 없으며, MDP는 매우 이상적인 환경이므로 현실과 맞지 않다.
• POMDP 환경에서 agent는 whole state에 대한 정보가 없이, 오직 observation o(~O(s))에 의해서만 정보를 얻을 수 있다.(underlying state)
• Vanilla Deep Q-Learning(standard Deep Q-learning)은 온전한 state 정보를 이용해야하는데, observation에 의존해서 estimate한 Q value는 이와 같지 않으므로 POMDP의 환경에서는 맞지 않는다.(Q(o, a|θ) ≠ Q(s, a|θ))

그래서 POMDP환경에서 recurrency를 이용해서 이 두 가지 Q-value, Q(o, a|θ)와 Q(s, a|θ)의 gap을 줄여보자는 것이 목적입니다.

본 논문에서, DQN에 recurrency를 얹기 위해서 CNN구조에서 fully-connected layer를 같은 size의 recurrent LSTM layer로 교체한 것입니다. 아래는 논문에 나온 그림을 눈에 보기 쉽게 편집한 것 입니다. 논문에 있는 그림과 구조는 같습니다.

<Fig4. DRQN architecture>

Part 4의 DQN에서 DRQN을 구현하기 위해 아래와 같은 사항을 추가합니다.

• Double Q network의 value와 advantage stream을 나누는 부분에서 LSTM cell을 추가한다.
• Experience buffer에서 random sample을 취하는 것이 아니라 sequential하게 이용하기 위해서 episode마다 experience 전체를 저장하고, 이 저장된 episode에서 8 step의 experience를 random sampling한다.
• Agent가 training할 시에 모든 gradient가 아닌 끝에서 절반만큼의 gradient를 보낸다(카네기 멜론에서 DRQN을 이용해서 Doom game을 플레이할 수 있는 agent를 개발할 시에 사용한 기법을 이용한다-뒤에서 Doom game을 플레이할 수 있는 agent를 구현할 때, 관련 논문을 리뷰하면서 자세히 다루겠습니다).

아래는 이를 반영하여 9x9 gridworld 환경에서 구현한 agent입니다.

마치며

다음 포스팅은 agent의 action을 선택하는 데 사용하는 몇 가지 탐색(exploration) 방법에 대해 소개하고, 각 방법의 장단점 및 구현해보도록 하겠습니다. 

오탈자나 잘못 언급된 부분이 있으면 댓글로 지적해 주세요 :)

Reference

[1] https://medium.com/emergent-future/simple-reinforcement-learning-with-tensorflow-part-6-partial-observability-and-deep-recurrent-q-68463e9aeefc

[2] http://ishuca.tistory.com/398