목차

1. Problem definition
2. Double DQN
3. Proof
4. Reference

Problem definition

DQn의 \(\gamma \operatorname{max} Q\)는 overestimate되어있다.
Theorem 1에 의하면 \(V^*(s)\)를 target(optimal Q)라고 했을 시 \(V^*(s) - \underset{a}{\operatorname{max}} Q_t(s,a) \ge \sqrt{\frac{c}{m-1}}\) 이라는 식이 만들어진다. 이 식은 DQN이 항상 \(\sqrt{\frac{c}{m-1}}\)의 error를 가진다는 것을 의미한다. (c는 상수, m은 action 수를 의미)

Double DQN

DDQN에서는 \(\gamma \operatorname{max}Q(s_{t+1},a_{t+1})\) 대신 아래 식을 이용한다.

\[R_t + \gamma Q_{w^-} (s_{t+1}, \underset{a_{t+1}}{\operatorname{argmax}}Q_w(s_{t+1},a_{t+1})\]

Proof

Assumption

1. Given \(s_t\), 모든 action에 대해 optimal \(Q^*\)값이 같다. (\(Q^*(s_t,a_t) = V^*(s_t)\))
2. \(\underset{a}{\sum} \epsilon_a =0\) (\(\epsilon_a \triangleq Q(s_t,a_t) - V^*(s_t)\))
3. \(\frac{1}{m} \underset{a}{\sum} \epsilon^2_a = c\) (\(c>0\))
   \(\to \underset{a}{\operatorname{max}} \epsilon_a \geq \sqrt{\frac{c}{m-1}}\)

n: 양수 action \(\epsilon_a \ge 0\)
m-n: 음수 \(\epsilon_a\)를 만드는 action 수

증명

• \(m-n \geq 1\) 분산이 0보다 크며 합이 0이 되기 위해서 필요(모든 \(\epsilon_a\)가 0일 시 3번 조건 위배)

\(\epsilon^+_a\): 양수 \(\epsilon_a\)
\(\epsilon^-_a\): 음수 \(\epsilon_a\)

\[\underset{a}{\sum} \epsilon^+_a \leq n \underset{a}{\operatorname{max}} \epsilon_a < n\sqrt{\frac{c}{m-1}}\]

위 가정이 모순일 경우 \(n \underset{a}{\operatorname{max}} \epsilon_a \ge n \sqrt{\frac{c}{m-1}}\)이 된다.

• \[\underset{a}{\sum} \vert \epsilon^-_a \vert < n \sqrt{\frac{c}{m-1}}\]
• \[\underset{a}{\operatorname{max}} \vert \epsilon^-_a \vert < \sqrt{\frac{c}{m-1}}\]

\(\underset{a}{\sum} (\epsilon^{-}_a)^2 \leq \underset{a}{\sum} \vert \epsilon^{-}_a \vert \cdot \operatorname{max} \vert \epsilon^{-}_a \vert\)
\(\qquad \leq n \sqrt{\frac{c}{m-1}} \cdot n \sqrt{\frac{c}{m-1}} = n^2 \frac{c}{m-1} \leq (m-1) c \qquad m-n \ge 1\) 이용
\(\underset{a}{\sum} {\epsilon^{+}_a}^2 < n \frac{c}{m-1}\)

\(\underset{a}{\sum} {\epsilon^+_a}^2 + \underset{a}{\sum} {\epsilon^-_a}^2 = \underset{a}{\sum} {\vert \epsilon_a \vert }^2 \leq \underset{a}{\sum} \vert \epsilon^-_a \vert \cdot \operatorname{max} \vert \epsilon^-_a \vert + \underset{a}{\sum} \epsilon^+_a\)
\(< \frac{n^2c}{m-1} + n \frac{c}{m-1} \leq (m-1) c + c = mc\)

\(\underset{a}{\sum} \epsilon^2_a = mc\)라면 위에서 말한 세번째 가정 모순

그러므로 \(\operatorname{max} \epsilon_a \geq \frac{c}{m-1}\)이 된다.

DQN은 max Q로 error가 항상 양수이지만 DDQN은 Q’(argmaxQ)를 사용했기 때문에 lower bound가 0이라고 주장한다.

Reference

1. 혁펜하임 유투브
2. Van Hasselt, Hado, Arthur Guez, and David Silver. “Deep reinforcement learning with double q-learning.” Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 30. No. 1. 2016.