[RL] 강화학습 part3 - Temporal Difference Learning, RL application

[RL] 강화학습 part3 - Temporal Difference Learning, RL application

5. 시간차 학습

Temporal difference learning

가장 혁신적인 알고리즘입니다.

동적 프로그래밍과 몬테카를로 방법의 장점을 겸비하였습니다.

1) 정책 평가

에피소드 e = $[s_0, r_0]a_0[s_1, r_1]a_1 \cdots [s_T, r_T]$에서 샘플 $z_t$를 처리한다면 몬테카를로 방법은 $Z(s_t)$에 이 샘플을 추가한다음 아래 식으로 가치함수를 갱신합니다.
$$
v_{\pi}(s_t) = \frac{1}{\vert Z(s_t) \vert}\sum_{z \in Z(s_t)} \mathbb{r}(z)
$$

샘플 $z_t$가 k번째로 추가되었다면, 추가된 순서를 고려하여 다음 식을 세울 수 있습니다.
$$
v_{\pi}^{(new)}(s_t) = \frac{v_{\pi}^{(old)}(s_t) * (k-1)}{k} + \frac{\mathbb{r}(z_t)}{k} = v_{\pi}^{(old)}(s_t) + \frac{1}{k}(\mathbb{r}(z_t)-v_{\pi}^{(old)}(s_t))
$$

$v_{\pi}^{(old)}(s_t)$는 직전까지의 가치함숫값, 즉 먼저 추가된 k-1개의 샘플 평균이고,

$\mathbb{r}(z_t)$는 k번째 추가된 샘플의 누적 보상액 입니다.

위 식은 아래와 같은 형식으로 바꿀 수 있습니다. 아래 식은 덧셈 두번과, 곱셈 한번만으로 평균을 갱신하므로 효율적입니다.
$$
v_{\pi}(s_t) = v_{\pi}(s_t) + \rho(\mathbb{r}_{new} - v_{\pi}(s_t))
$$

몬테카를로 방법은 종료 상태 $s_T$에 도달해야 가치함수의 갱신이 일어나지만, 시간차 학습(temporal difference learning)은 다음 상태로 진입할 때 곧바로 갱신이 가능합니다. 이것이 시간차 학습의 핵심 아이디어 입니다.

$$
v_{\pi}(s_t) = v_{\pi}(s_t) + \rho((r_{t+1} + \gamma v_{\pi}(s_{t+1})) - v_{\pi}(s_t))
$$
특별히 시간차 학습에서는 상태 가치함수를 구할 때 위와 같이 새로운 보상을 구하여 식을 재정의 합니다.

$\gamma$는 할인율입니다.

상태-행동 가치함수를 추정하려면 아래의 식을 사용합니다.
$$
q_{\pi}(s_t, a_t) = q_{\pi}(s_t, a_t) + \rho((r_{t+1} + \gamma q_{\pi}(s_{t+1}, a_{t+1})) - q_{\pi}(s_t, a_t))
$$

정책평가

1) 모든 상태에 대해 가치함수 $v_{\pi}(s)$를 0으로 초기화 한다.

2) 에피소드 e를 생성한다.

3) 위 상태 가치함수 식을 이용하여 각 상태별로 (t=0부터 t= T까지) 가치함수를 갱신한다.

4) 2~3을 반복하여, 멈춤조건에서 멈춘다.

다른 상태가치함수의 값을 이용해서 현재의 상태가치함수를 갱신한다는 점에서 부트스트랩과 유사한 점이 있고(즉, 동적프로그래밍와 유사하다.),

에피소드 e를 생성하여 학습한다는 측면에서는 몬테카를로 방법과 유사합니다. 따라서 시간차 학습은 둘의 장점을 취하는 알고리즘으로 평가할 수 있습니다.

2) Sarsa

최적 정책을 찾는 알고리즘

시간차를 이용하여 최적 정책을 탐색하는 알고리즘으로 Sarsa, Q-learning 두가지가 있습니다.

Sarsa는 상태-행동 버전 식을 사용합니다.

알고리즘은 반복할 때마다 $s_t, a_t, r_{t+1}, s_{t+1}, a_{t+1}$ 라는 정보를 처리하므로 앞글자를 따서 Sarsa라고 합니다.

line 7에서 볼 수 있듯이 Sarsa는 다음 행동을 정책에 따라 결정합니다.

line 8에서는 결정된 행동에 따라 가치함수를 갱신합니다.(즉, 정책을 갱신합니다.)

이러한 방식을 on-policy라고 합니다.

3) Q-Learning

Watkins, 1992

Q-learning은 가치함수 갱신을 정책이 아닌 max 연산자로 결정합니다. Q-learning은 off-policy를 사용한다고 말합니다.

Sarsa와 다른 점은 $q_{\pi}(s_{t+1}, a_{t+1})$이 $max_q q_{\pi}(s_{t+1}, a)$로 바뀐 것입니다.
$$
q_{\pi}(s_t, a_t) = q_{\pi}(s_t, a_t) + \rho((r_{t+1} + \gamma \ \underset{a}{max} q_{\pi}(s_{t+1}, a) - q_{\pi}(s_t, a_t))
$$

TD Learning 중 Q-learning을 사용하여 최적 정책을 구하는 방식은 강화학습에서 가장 혁신적이라고 평가하고 있습니다.

6. 근사 방법

위에서 언급한 알고리즘의 출력은 $\hat{\pi}$ 또는 최적 가치함수 $\hat{v}$ 또는 $\hat{q}$입니다.

$\hat{\pi}$을 구하기 위해서는 모든 상태와 모든 행동 확률을 표현하기 위해 $\vert \mathcal{S} \vert \mathsf{x} \vert \mathcal{A} \vert$ 크기의 배열이 필요합니다.

$\hat{v}$ 는 $\vert \mathcal{S} \vert$,

$\hat{q}$는 $\vert \mathcal{S} \vert \mathsf{x} \vert \mathcal{A} \vert$ 크기의 배열이 필요합니다.

이 배열을 한 번 구하면, 배열을 참조하여 값을 읽으면 되므로, 배열을 참조표(lookup table)라고 합니다.

그런데 $\vert \mathcal{S} \vert , \vert \mathcal{A} \vert$가 크면 메모리 문제가 발생합니다. 모든 배열 요소의 확률을 구하기도 불가능해집니다. 강화학습은 이러한 종류의 문제를 풀기 위해 lookup table을 버리고, 근사 방법을 이용합니다.

선형방정식을 통해 근사하는 방법이 있습니다.
$$
v(s; \theta) = \sum_{i=1}^k \theta_i \phi_i (s)
$$
가치함수 $v$는 k개의 매개변수 $\theta$로 표현됩니다. 보통 $k << \vert \mathcal{S} \vert$입니다.

$\pi_i(s)$는 기저함수로, 서로다른 기저함수가 매개변수만큼 있습니다. 기저함수는 사람이 설계하여 훈련집합으로 최적의 매개변수를 찾는 일은 학습 알고리즘이 담당합니다.

하지만 현재 강화학습은 위 식보다 신경망을 주로 사용합니다.

입력으로는 상태(state), 출력은 보상(reward)입니다.

훈련집합은 에피소드(episode)를 수집하여 구성하고, 학습시 역전파 알고리즘(backpropagation)을 이용합니다. (Sutton, 2017)

7. Application Example

TD-gammon은 MLP를, DQN은 딥러닝 기술을 사용하여 가치함수를 근사합니다.

1) TD-gammon

Backgammon 게임입니다.

검은 말은 낮은 번호로, 빨간 말은 높은 번호로 이동합니다. 15개의 검은 말이 모두 16번으로 이동한 후 빠져나오면 검은 말이 이기고, 빨간 말이 1924로 이동한 후 먼저 빠져나와면 빨간 말이 이깁니다.

주사위를 굴려 나온 수 만큼 한개의 말을 이동 시킬 수 있습니다. 주사위는 2번 던져 서로 다른 말에 적용시킵니다. 하지만 24번의 검은말 하나가 주사위 5가 나와 빨간말로 꽉찬 19번으로 이동할 수 없습니다. 막는 것이 일종의 전략이 될 수 있습니다.

또한 빨간말이 하나뿐이라면 검은 말이 빨간 말을 잡을 수 있습니다. 잡은 말은 바깥에 두었다가 처음 위치에서 다시 시작해야 합니다.

서로 다른 상태가 $10^{20}$개 이상 있으므로 근사 가치함수를 사용합니다.

은닉층이 하나인 MLP를 사용하였고, 검은 말, 빨간 말이 놓인 위치를 표현하기 위해 24개 위치 각각에 노드를 4개씩 배정하였습니다. 2 * 24 * 4 = 192개의 노드가 사용됩니다.

또한 시간차 알고리즘을 사용해서 TD-gammon이라 불립니다.(Tesauro, 1995)

TD-gammon은 사람의 전략을 가르쳐 주지 않은 채 프로그램 2개가 겨루는 과정에서 학습하는 self-play 방식입니다. 승패의 여부에 따라 상태에 +1, -1 보상을 부여하고 보상이 TDL 알고리즘을 통해 이전상태로 파급됩니다.

TD-gammon은 지도학습을 전혀 이용하지 않고 자가 플레이로 세계 챔피언 수준에 도달하였습니다.

강화학습과 보드게임

틱택토(tic-tac-toe), checkers, 체스, 장기, 바둑입니다.

보드게임을 가장 잘하기 위한 강화학습 연구가 진행되었고 가장 어려운 바둑에서 세계 챔피언 수준의 이세돌을 4:1로 이기는 성과를 기록합니다.

틱택토는 상태의 수가 $3^9=19,683$정도로 근사 가치함수를 사용하지 않더라도 쉽게 최적 정책을 알아낼 수 있습니다.

틱택토는 새로운 프로그램을 테스트하는 용도로 자주 쓰입니다.

checkers는 열약한 하드웨어에서도 체커 게임을 해결하는 시도를 하였습니다.(Samuel, 1959)

체스는 Deepblue라는 프로그램이 세계 챔피언을 이겼습니다.(Campbell, 2002)

당시 VLSI칩은 딥블루라는 슈퍼컴퓨터로 발전하였고, 당시에는 기계 학습 알고리즘 보다 하드웨어 속도를 향상시켜 높은 수준을 달성하였습니다. 장기도 이와 마찬가지입니다.

바둑은 훨씬 탐색 공간이 커서 고성능 하드웨어에도 한계가 있었습니다. alphago는 몬테카를로 트리탐색, 프로기사들의 기보를 활용한 지도학습, self-play를 활용한 강화학습, CNN 적용, 고성능 하드웨어와 결합하여 세계 챔피언을 이길 수 있었습니다.(Silver, 2016)

2) DQN: Atari video game

므니 등은 Atari 2600 게임 49종에서 자동으로 플레이하는 프로그램을 개발하였습니다. (Mnih et al., 2015)

다양한 게임해서 동일한 입력, 신경망 구조, 하이퍼 파라미터를 사용하여 전문 플레이어 수준을 달성하였습니다. 29종에서 좋은 성능을 보였습니다.

CNN과 Q-Learning을 결합한 DQN으로 상태를 입력하고, 게임 종류마다 필요한 만큼 출력노드를 정합니다.