• 다음 내용은 [CS-188] Introduction to Aritificial Intelligence, UC Berkeley, Fall 2018의 Readings-Note5을 정리하였음을 밝힙니다.
• 스스로 이해하기에 영문 용어가 이해하기 직관적이면 그대로 사용했습니다.

Model-Free Learning

Q-Learning

DE와 TD 학습이 정책을 통해 각 상태 값 $V$를 얻어낸다면, Q 학습은 $Q$ 상태를 직접 계산한다.

에이전트가 최적의 정책 $\pi^*$를 따른다는 건 곧 각 상태별 q 값을 알고 있다는 뜻이다.
벨만 방정식을 통해 트랜지션/보상 함수를 얻고, 이를 통해 우리가 가지고 있는 값에서 q 값을 계산해보자.

• $Q^*(s,a)=\sum\limits_{s'}T(s,a,s')[R(s,a,s')+\gamma V^*(s')]$

DE와 TD 학습이 에이전트가 따르는 정책을 업데이트하기 위해 어느 정도 트랜지션 함수 $T$와 보상 함수 $R$을 필요로 하는 모델 기반 학습과 연관되는 반면, Q 학습은 전적으로 모델에서 자유롭다는 게 특징이다.

Q 학습은 Q값을 반복적으로 업데이트하면서 다음 단계의 q값을 얻어낸다.

• $Q_{k+1}(s,a) \leftarrow \sum \limits_{s'}T(s,a,s')[R(s,a,s')+\gamma max_{a'}Q_k(s',a')]$

에이전트가 q 상태에 있을 때 다음 q 값을 최댓값으로 만들어주는 행동 $a'$를 찾는 게 이 q값 반복의 목적이다.

이 업데이트 규칙을 통해 Q 학습은 샘플을 얻을 수 있다.

• $sample = R(s,a,s')+\gamma max_{a'}Q(s',a')$

TD 학습에서 학습률(learning rate) $\alpha$를 사용해 에이전트가 여태까지 학습해놓은 q 상태와 새로 얻은 샘플 간 어떤 비중을 두고 새로운 q 값을 학습할지 정할 수 있다.

• $Q(s,a) \leftarrow (1-\alpha)Q(s,a)+\alpha * sample$

탐색 시간이 충분하다면 학습률 $\alpha$는 충분한 속도로 줄어들고, Q 학습 또한 모든 q 상태의 최적 q 값을 얻을 수 있다. $V$를 계산하는 모델 프리 학습(DE, TD 학습 등)이 지금 에이전트가 따르는 정책이 최적인지 결정하기 전에 정책을 택해야 하는 반면, Q 학습은 최적이 아닌 행동을 하더라도 직접 최적의 정책 $\pi^*$를 학습할 수 있다.

• off-policy learning: suboptimal action을 통해 궁극적으로 optimal policy를 학습할 수 있는 $Q$를 계산해 학습하는 모델 프리 학습의 특징

Approximate Q-Learning

Q학습은 각 상태에 대한 모든 q 값을 저장해야 하는데, 상태가 많아질수록 효율이 낮다. 학습하는 동안 모든 상태를 방문하지 못할 뿐더러, 메모리에 모든 q 값을 저장할 수도 없기 때문이다.

근사 Q 학습(approximate Q-learning)은 Q 학습을 실행하지만 모든 경우의 q 값이 아니라, 일반적인 경우만을 저장한다.

이때 일반적(general)인 학습은 문제의 특징 벡터(feature vector)로 각 상태를 표현(feature-based representation)한 값을 저장하는 것이다. 이는 그대로 표현할 때 크기가 큰 상태를 중요한 정보만 남기고 압축하는 방법이다.

예를 들어 팩맨 문제에서 특징 벡터는 (1) 팩맨과 가장 가까운 고스트까지 거리 (2) 팩맨과 가장 가까운 음식까지 거리 (3) 고스트의 수 (4) 지금 좌표가 함정인지 여부 등이 존재할 것이다.

특징 벡터를 통해 상태 및 q 상태의 값을 선형 함수로 표현해보자.

• $V(s)=w_1\cdot f_1(s) +w_2\cdot f_2(s)+...+w_n\cdot f_n(s)=\vec{w}\cdot \vec{f}(s)$

• $Q(s,a)=w_1\cdot f_1(s,a) +w_2\cdot f_2(s,a)+...+w_n\cdot f_n(s,a)=\vec{w}\cdot \vec{f}(s,a)$

이를 사용해 q 값의 차(difference)를 표현하자.

• $difference=[R(s,a,s')+\gamma max_{a'}Q(s',a')]-Q(s,a)$

근사 Q 학습은 이 차와 $f_i(s,a)$를 곱한 값을 사용해 가중치 $w$를 업데이트한다.

• $w_i \leftarrow w_i+\alpha \cdot difference\cdot f_i(s,a)$

필요할 때에만 근사 Q 학습이 이 $w$ 벡터를 사용해 다음 q 상태를 업데이트한다는 데 주목하자. 즉 이전의 Q 학습에서 모든 q 값을 저장해둔 것과 다르게 메모리 효율적으로 업데이트할 수 있다.

• $Q(s,a,) \leftarrow Q(s,a,)+\alpha \cdot difference$

이 업데이트 규칙을 통해 보다 정확한 q 값을 얻어낼 수 있다. 현재 q 상태값과 샘플 값의 차(difference)를 원하는 학습률 $\alpha$에 곱해 적용하는 게 특징이다.

Exploration and Exploitation

에이전트가 상태 $s$에서 $a$를 통해 다음 상태 $s'$를 얻어내는데, 이 확률에 따라 강화학습의 학습 소요 시간이 달라질 수 있다. 보다 효율적으로 학습을 하기 위해 어떤 방법을 실행할 수 있을까?

가장 간단한 무작위 선택을 사용한 방법부터 알아보자.

$\epsilon$-Greedy Policies

$0\leq \epsilon \leq 1$인 확률 $\epsilon$을 따르는 $\epsilon$ 그리디 정책에서 에이전트는 랜덤하게 이 확률 $\epsilon$을 따라 탐색한다. 만일 이 확률이 적정 값보다 크다면, 최적의 정책 $\pi^*$를 학습하고도 애이전트는 계속해서 학습할 것이다. 반대로 적정 값보다 작다면 에이전트의 Q 학습이 매우 느린 속도로 진행된다는 것을 뜻한다.

Exploration Functions

$\epsilon$을 직접 튜닝해주어야 하는 앞의 그리디 정책과는 달리, 탐험 함수(exploration functions)는 q 값 반복 업데이트를 수정해 적게 방문한 상태를 더 많이 방문할 수 있는 알고리즘이다.

• $Q(s,a) \leftarrow (1-\alpha)Q(s,a)+\alpha \cdot[R(s,a,s')+\gamma max_{a'}f(s',a')]$

탐험 함수 $f$를 통해 각 상태를 어느 정도로 많이 방문할지 설정할 수 있다.

• $f(s,a)=Q(s,a)+\frac{k}{N(s,a)}$

$N(s,a)$는 q 상태 $(s,a)$를 지금까지 방문한 횟수이고 $k$는 사정에 정한 값이다. $s$ 상태에 있는 에이전트는 언제나 가장 $f(s,a)$ 값이 큰 길, 다시 말해 여태까지 가장 적게 방문한 상태를 방문할 수 있다. 더 많이 방문할 수록 이 $f$는 0에 수렴하기 때문에 전체적으로 골고루 방문 가능하다.