4장. 벨만 방정식부터 강화 학습까지

몬테-카를로 추정법

앞 장에서 살펴본 동적 계획법을 활용한 벨만 방정식의 해를 찾는 방식은 에이전트가 환경에 대한 모든 정보를 파악하고 문제를 해결한다는 점에서 진정한 강화학습으로 볼 수 없다. 

강화 학습이란 위 그림처럼 정확히 파악할 수 없는 환경에 대한 수학적인 정보를 모른 채 에이전트가 환경과 상호 작용하면서 주어진 상태에 대한 최대 가치를 얻어내는 것이다.

몬테-카를로(Monte-Carlo)추정법은 특정 값을 알고 싶으나 해석적으로 정확하게 계산하기 어려울때 대안으로 사용하는 확률을 기반으로 한 근사법이다. 예를 들어, 우리가 원주율 \(\pi\) 값을 정확히 알고 싶다고 할 때, 몬테-카를로 추정법으로 근사해볼 수 있다. 반지름이 1인 사분면의 원의 넓이가 \(\frac{\pi}{4}\)라는 것을 알 때, 임의의 점을 흩뿌린 뒤 데이터의 개수를 세보면 다음의 관계식을 도출 할 수 있다.

원주율 값은 흩뿌린 점의 개수가 많으면 많을수록 값이 정확하게 추산된다. 비록 해석적인 방법은 아니지만 이와 같이 반 복 시행으로 특정 값을 얻어내는 과정을 몬테-카를로 추정법이라고 한다.

앞서 살펴본 벨만 기대 방정식을 몬테-카를로 방식으로 해석할 수 있다. \(V(s)=\mathbb{E}[G_t|S_t=s]\)에서 리턴은 환경이라는 모집단에서 해석적으로 얻은 결과이므로 정확한 값을 알기는 불가능하지만 우리는 에이전트를 무수히 많은 시행 횟수 동안 환경에 대입시켜 샘플링된 리턴값을 얻을 수 있다. n번 수행하여 얻은 n개의 리턴을 산술 평균 내면 이는 리턴의 기대값으로 정의된 가치 함수를 몬테-카를로 방식으로 근사한 결과와 비슷해져 간다. 따라서 가치함수를 다음과 같이 현실적인 방법으로 근사할 수 있다.

$$V(s) \simeq \frac{1}{n} \sum_{i=1}^n G_i(s)$$

(기대값을 여러번 수행을 통한 샘플링으로 대체한다는 이야기!)

애당초 기대값과 산술 평균의 차이는 해당하는 랜덤 변수가 모집단과 샘플의 차이 여부였다. 이제 가치 함수를 전개하여 다른 형태로 작성해보자.

$$ \begin{equation} \begin{split} V_n &\simeq \frac{1}{n}\sum_{i=1}^nG_i \\ &\simeq \frac{1}{n} \sum_{i=1}^n (G_n + \frac{n-1}{n-1}\sum_{i=1}^{n-1}G_i) \\ &\simeq \frac{1}{n} \sum_{i=1}^n (G_n + (n-1)V_{n-1}) \\ &\simeq  V_{n-1} + \frac{1}{n}(G_n - V_{n-1}) \end{split}\end{equation} $$

위 수식은 n회 반복하여 얻은 가치 함수가 n-1회를 반복하여 얻은 가치 함수와 n번째 리턴값을 통해 계산됨을 보여준다. n이 커질수록 산술 평균이 기대값에 가까워진다. 이는 작은 문제에서 사용했던 답을 이용해서 큰 문제를 푸는 동적 계획법의 개념을 이용해서 가치 함수를 업데이트 수식으로 표현할 수 있다.

$$\displaylines{V \gets V + \alpha(G-V) \\ \text{where,} \\ \begin{equation} \begin{split} \text{MC target} &= G \\ \text{MC error} &= \delta \\ &= G-V \end{split}\end{equation} } $$

여기서 \(\alpha\)는 학습률로서 \(\frac{1}{n}\)에 대응되어 0에서 1사이의 양수를 갖는다. 몬테-카를로의 가치 함수 업데이트 식의 목표치는 G이며, 영문으로 MC target으로 부른다. 그리고 목표치와 현재 값의 차이는 Target Error(\(\delta\))로 표기한다.

위 그림에서처럼 각각의 에피소드 종료 시점 T의 상태로 도달할 수 있는 경우의 수는 매우 많다. 바로 한 번의 시점 진행으로 상황이 종료될 수 있거나, 많은 시간이 지나고 여러 상태를 거쳐서 환경이 종료되는 경우 등 매우 다양하게 리턴이 계산된다. 하지만 이런 모든 리턴들을 평균 내면 적절한 리턴, 기대되는 가치 함수를 계산할 수 있다.

시간차 학습

몬테-카를로 방식은 에피소드가 종료될 때까지 기다려야 하는 부분에서 단점이 있다. 시간차 학습(Temporal difference learning)은 그 단점을 보완하는 방식이다.

TD(0)

$$V \gets V + \alpha(G-V)$$

위 수식에서 리턴을 한 스텝 앞선 시점의 가치(V')로 바꿔서 표현해보자.

$$\displaylines{V \gets V + \alpha(R+ \gamma V'-V) \\ \text{where,} \\ \begin{equation} \begin{split} \text{TD target} &= R+\gamma V' \\ \text{TD error} &= \delta \\ &= R+ \gamma V'-V \end{split}\end{equation}} $$

위 수식은 가중치가 없는 시간차 학습 방식을 이용한 가치 함수 업데이트 수식이다. 시간차 학습 방식은 단 한 번의 시점이 이동된 상태에서 보상과 가치 함수와 현재 가치 함수와의 차이를 이용해 가치 함수를 업데이트하는 방식이므로 몬테-카를로 방식과 차이점이 명확히 드러난다. 쉽게 말해 몬테-카를로 방식은 현재의 가치를 알고자 먼 미래까지 결과를 보는 방식이라면, TD(0)는 현재의 가치를 알고자 바로 다음 미래의 예상되는 결과를 이용하는 전략이다.

몬테-카를로(MC) vs 시간차 학습(TD) 방식

MC는 모든 상태를 다 탐색하므로 현재 가치를 올바르게 평가하는 장점이 있지만 무수히 많은 에피소드를 경험해야 올바른 값을 구할 수 있다. 반면 TD(0)는 바로 다음 상태만을 탐색하므로 MC보다 경우의 수가 적으므로 유리하지만 공정하게 가치 함수를 평가했다고 이야기하기에는 MC보다 근거가 부족하다.

우리가 맞혀야 할 가치 함수가 과녁의 중앙이라고 고려하면 MC 학습 방식은 전체적인 추정이 과녁의 중앙을 향해 분포하지만 분포가 넓게 형성되어 있다. 반면 TD는 전체적인 추정이 과녁의 중앙에는 벗어나 있지만 분포가 한 곳을 향해 집중적으로 모여있다. 그래서 MC는 "High-variance, Low-bias", TD는 "Low-variance, High-bias" 특성을 보인다고 할 수 있다. 과녁의 중앙을 맞히는 문제와 분산을 줄이는 문제는 동시에 풀면 이상적이지만, 하나를 포기해야 하는 트레이드 오프 딜레마에 놓여있다. 이런 트레이드-오프 관계를 정략적으로 분석하고자 우리는 가중치가 첨가된 일반화된 시간차 학습 방식을 살펴보아야 한다.

TD(\(\lambda\))

이 부분에서 책 설명이 이해가 안되서 데이비드 실버 선생님 강의자료 참고함..

Monte-Carlo vs Temporal Difference

Eligibility traces

한글로 적격성 추적이라고 해석되는 본 개념은 어떤 사건이 일어났을 때 해당하는 원인 분석법을 1) 발생 빈도 초점(Frequency heuristic), 2) 최신 발생 초점(Recency heuristic)을 두는 관점을 모두 아울러 추적하는 분석 방법이다.

(거의 책 내용이 데이비드 실버 강의를 한글로 풀이해놓은 느낌.. 그래서 오히려 설명이 강의보다 불명확한 부분이 중간중간 있다..)

shock이 발생하기 전 종이 울리는 상태와 전등이 들어오는 상태를 겪었다고 할 때, 자주 울렸던 종이 주요한 역할을 했는지를 추정하는 것이 발생 빈도 초점 방식이며, 전등이 들어온 상태를 주요 역할로 추정하는 것이 최신 발생 초점 방식이다.

위 수식은 시작 지점에서 그 값이 0부터 시작해서 t 시점의 상태 \(S_t\)가 보고자 하는 상태 s인 경우에만 신호를 첨가하고 이전의 신호들을 시간에 따라 할인하며 누적합을 하는 것을 보여준다.

위 그림은 상태 s에 따른 eligibility trace이다. 특정 시점마다 에이전트는 상태 s를 겪으면서 그때마다 신호가 강해짐을 보여준다. 신호가 들어오지 않으면 시간이 점차 지남에 따라 신호가 약해지는데 그 정도는 할인율 \(\gamma\)와 TD 가중치 \(\lambda\)에 의존하게 된다.

TD Error

Eligibility trace를 접목한 가치 함수 업데이트 식을 새롭게 정의할 수 있다. 먼저 TD-error를 수식으로 표현하면 다음과 같다.

$$\delta_t=G_t^\lambda - V(S_t)$$

Eligibility trace 수식과 TD-error 수식을 이용해 가치 함수의 업데이트 수식을 다시 표현할 수 있다.

$$V(S_t) \gets V(S_t) + \alpha \delta_t E_t(s)$$

(원래는, \(V(S_t) \gets V(S_t) + \alpha \delta_t\))

여기서 가중치 \(\lambda\)를 0부터 1까지 변화시켜 가면서 TD(0)에서 Monte-Carlo 업데이트 식으로 이어지는지 확인해보자.

Case 1. \(\lambda = 0\)

시간이 흘러도 eligibility traces 값은 1로 고정된다.

$$\begin{equation}\begin{split} E_t(s) &= 1(S_t=s) \\ V(S_t) &\gets V(S_t) + \alpha \delta_t 1(S_t=s) \\ V(S_t) &\gets V(S_t) + \alpha \{ R_{t+1} + \gamma V(S_{t+1}) - V(S_t)\} \end{split}\end{equation} $$

따라서 해당 경우의 가중치 업데이트 수식은 TD(0)의 방식과 같다.

Case 2. \(\lambda = 1\)

Eligibility trace 값은 더 이상 1로 고정되지 않으므로 점화식으로 매 시점의 가치 함수 업데이트 식을 고려야 한다. 특점 시점 k에서 상태 s를 겪었을 때 Eligibility trace를 수식으로 표현하면 다음과 같다.

$$E_t(s) = \begin{cases} 0, &\text{t < k} \\ \gamma^{t-k}, &\text{if t >= k} \end{cases}$$

우리의 논의 대상 시점 t가 k보다 앞서 발생했다면 상태 s에 대한 신호를 겪어 보지 않았으므로 eligibility trace의 값은 0이며, 반대로 시점 t가 k보다 미래라면 그 신호는 시간이 지날수록 할인된다. 추가로 가중치는 \(\lambda\)는 1이므로 eligibility trace는 할인율만 고려한다.

TD-error는 에피소드의 최초 시점부터 종료까지 상태 s에 대한 모든 eligibility trace를 고려한다.

$$\sum_{t=1}^T \alpha \delta_t E_t(s)$$

이제 위 두 식을 합하여 TD-error를 작성해보자

$$\begin{equation} \begin{split} \sum_{t=1}^T \alpha \delta_{t}E_{t}(s)&=\sum_{t=k}^T \alpha \gamma^{t-k}\delta_{t} \\ &= \alpha (\delta_k + \gamma \delta_{k+1} + \cdots +  \gamma^{T-k-1}\delta_{T-1} + \gamma^{T-k}\delta_{T}) \end{split}\end{equation}$$

오른쪽 항의 괄호 안 요소들을 상세히 전개하면 다음과 같다.

$$\begin{equation}\begin{split} \delta_k &= R_{k+1} + \gamma V(S_{k+1})-V(S_k) \\ \gamma \delta_{k+1} &= \gamma R_{k+2} + \gamma^2 V(S_{k+2})- \gamma V(S_{k+1}) \\ \vdots \\ \gamma^{T-k-1} \delta_{T-1} &= \gamma^{T-k-1} R_{T} + \gamma^{T-k} V(S_{T})- \gamma^{T-k-1} V(S_{T-1}) \\ \gamma^{T-k} \delta_{T} &= -\gamma^{T-k} V(S_{T-1}) \end{split}\end{equation}$$

(마지막 항에서 갑자기 몇 개 항이 사라지는 이유는 T시점 이후의 Reward는 0이기 때문으로 추측... 책에 설명이 없다;)

$$\therefore \alpha(\delta_k + \gamma_{k+1} + \cdots + \gamma^{T-k-1} \delta_{T-1} + \gamma^{T-k}\delta_T) = \sum_{n=k}^T\gamma^{n-k} R_{n+1} - V(S_k) = G_k - V(S_k)$$

더해서 정리하면 위와 같다. 따라서 가중치 업데이트 수식은 몬테 카를로 방식과 동일하다.

경우 3. 0 < \(\lambda\) < 1

시점 k에서 상태 s를 처음 마주햇으면 Eligibility trace는 가중치 \(\lambda\)를 반영한 것 이외에 다르지 않다

(책의 수식에 오타가 있는 것 같은 의심이 들어서 강의 자료로 대체)

어쨌든 eligibility trace를 통해 TD-Erorr를 도출할 수있다.

차후 배울 알고리즘과 구현하기 쉬운 eligibility trace 개념을 합하여 MC와 TD 사이의 적절한 학습 전략을 찾아낼 수 있다.

에이전트 학습

가치 함수를 최적화 시키리면 정책도 같이 최적화시켜야 한다. 따라서 최적 정책을 가치 함수를 구성하는 요소까지 포함시켜 적어보면 다음과 같다

$$\pi_*(a|s) = \text{argmax}_{a \in A}\{R_s^a + \gamma P_{ss'}^aV(s')\}$$

그러나 우리가 살펴보는 에이전트는 모델(환경)에 대한 정보가 없기에 상태 변환 확률 행렬도 알 수 없으며, 행동이 첨부된 보상도 구체적으로 알 수 없다. 그래서 강화학습에서 정책을 업데이트하고자 가치 함수를 바로 사용하기는 매우 어렵다. 그 대신에 앞서 배웠던 Q-함수를 통해 정책 업데이트를 시행한다. 

$$\pi_*(a|s) = \text{argmax}_{a \in A} Q(s,a)$$

하지만 Q-함수를 업데이트 하는 과정에서 '경사 하강법'을 쓰는 경우 그 초기값에 굉장히 민감하게 반응하여 모든 상태 공간에서 최적값이 아닌 국부 최소값에 머무를 가능성이 높다.

\(\epsilon\)-greedy

따라서 우리는 최적 정책을 학습하는 과정마다 다른 최적점이 있지 않을까 하는 의문을 계속 가져야 한다. 이렇게 다른 최적 지점을 탐구하는 생각을 'Exploration'이라고 하며, 반복법을 통해 초기의 학습 방향대로 최적 정책을 꾸준히 찾아가는 생각을 'Exploitation'이라고 한다. 에이전트는 모델(환경)을 완전히 알고 있지 못하므로 스스로 학습하고 있는 와중에도 다른 학습 경로에 대한 탐험을 부여하는 전략이 필요하다.

\(\epsilon\)-greedy 방법은 Q-함수를 기반으로 한 학습 방식에서 가장 많이 이용하는 행동 선택 전략이다. 1보다 작은 \(\epsilon\)을 이용해 Q-함수값 중 최대값을 반환하지 않는 행동을 취할 수 있는 확률을 보장해준다.(m=행동 개수)

$$\pi_*(a|s) = \begin{cases} \frac{\epsilon}{m} + 1 - \epsilon &\text{if } a = \text{argmax}_{a \in A} Q(s,a), \\ \frac{\epsilon}{m}, &\text{otherise} \frac{\epsilon}{m} \end{cases}$$

\(\epsilon\)-greedy 방법으로 행동을 추출할 때, 주사위를 굴리듯이 임의로 생성한 확률값이 \(\epsilon\)보다 작으면 Exploration을, \(\epsilon\)보다 크면 Exploitation을 수행하도록 코드를 작성한다.

\(\epsilon\)-greedy 방식의 학습 전략은 초기에는 상대적으로 큰 \(\epsilon\)을 취하지만 점차 작은 값으로 수렴하도록 조정하는 Epsilon-decay방식을 사용한다.

SARSA

시간차 학습의 가치 함수 업데이트 수식에 가치 함수 대신 행동을 고려한 보상인 Q-함수를 부여하여 새로운 형태의 수식으로 전개해보자

$$Q(s,a) \gets Q(s,a) + \alpha \{R+\gamma Q(s',a') - Q(s,a)\}$$

가치 함수만으로는 행동에 대해 생각할 수 없으니 Q-함수를 도입해서 최적 정책을 찾는다. 현재 상태에서 에이전트의 정책에 \(\epsilon\)-greedy와 같은 방식을 이용해 최적의 행동을 선택, 다음 시점에서도 에이전트가 가진 정책에 \(\epsilon\)-greedy 방식을 이요해 다음 시점에서의 상태 s'와 그에 맞는 행동 a'를 도입한 Q-함수값으로 현재 Q-함수값을 업데이트 한다. 

위 알고리즘은 Q-함수값을 알고자 필요한 요소 (\(s,a,R,s',a'\))를 모아서 SARSA 알고리즘이라고 부른다. SARSA는 현재 시점에서 행동을 구하고자 정책을 이용하며, 다음 시점에서도 다음 시점의 행동을 구하고자 정책을 그대로 사용한다. 이렇게 강화 학습 정책을 이용하는 방식을 통틀어 정책 기반(on-policy)학습이라고 부른다.

Q-learning

SARSA 알고리즘에서 다음 시점에서 행동 a'을 구하는 데 현재 시점에서의 정책을 이용하는 것이 다소 직관적으로 이해가 되지 않을 수 있다. 그래서 a'를 구하는 데 현재 시점의 정책을 이용하지 않고 Q-함수값을 가능한 모든 행동에 대해서 평가하는 방법을 이용하는 다른 방식의 학습법을 생각할 수 있다.

$$a' = \text{argmax}_{a \in A} Q(s', a)$$

$$Q(s,a) \gets Q(s,a) + \alpha \{R+\gamma Q(s', \text{argmax}_{a \in A}Q(s',a')) - Q(s,a)\}$$

$$Q(s,a) \gets Q(s,a) + \alpha \{R+\gamma \text{max}_aQ(s',a') - Q(s,a)\}$$

Q-learning에서는 다음 행동을 선택하는 과정에서 \(\pi(a|s')\)를 사용하지 않고 에이전트 스스로 평가하는 Q-함수값에 의존하게 된다. 정책을 이용하지 않으므로 비정책 기반 학습(off-policy)로 분류된다.

Q-learing은 본인이 가진 Q-함수값을 통해 학습한다. 강화 학습에서는 에이전트는 모델(환경)을 모른다는 전제를 가지므로 본인이 가진 Q-함수값도 완전하지 못하다는 것을 인지해야 한다. 실습에서 살펴볼 수 있듯이, Q-학습은 모델에 대한 불완전한 지식을 인정하지 않으므로 Exploitation과 Exploration의 적절한 조화가 이루어지지 못하여 상대적으로 SARSA 방식보다 저조한 결과를 보여준다.

(뭔 소리지..? Q-함수의 Q 값이 불완전하다는 건 이해가는데 그럼 SARSA에서 사용하는 정책은 불완전하지 않다는 건가...)

Q함수와 SARSA비교

• 공통점
  • 둘 다 다음 Action을 고를 때 Epsilon Action을 통해 Action을 선택한다.
• 차이점
  • Q함수를 업데이트 할 때, SARSA는 다음 상태 S'에서 현재 정책을 통해서 A'을 선택해서 Q(S',A')을 계산 한 뒤 활용해서 업데이트(현재 정책과 유관)
  • 반면 Q-learning은 Q 함수를 업데이트 할 때 다음 상태 S'에서 가장 높은 max Q(S',A')를 활용해서 그대로 업데이트(현재 정책과 무관)

# Q-Learning
next_q = self.max_Q(next_state) # 정책이 아니라 Q 함수에 의존
rhs = (1-self.alpha)*self.get_qvalue(state,action)+self.alpha*(reward+self.gamma*next_q)

# SARSA
next_action = self.epsilon_action(next_state) # 정책에 의존
next_q = self.get_qvalue(next_state,next_action)
rhs = (1-self.alpha)*self.get_qvalue(state,action)+self.alpha*(reward+self.gamma*next_q)

실습

https://colab.research.google.com/drive/1Tr93_bWYC7gOQ5TQ3eEVdwtgxNC3dwIH#scrollTo=0a4e3979

Google Colab Notebook