Week9. 강화학습 알고리즘-1

 지금까지 배운 내용들을 통해 강화학습의 수학적 기초를 다졌다. 동적 계획법에 대해 살펴보며 재귀식, 가치 함수, 정책, 상태, 행동이 어떻게 구성되는지를 살펴보았고, 강화학습에서 다루는 환경이 불확실성을 가지고 단계별로 진행되기 때문에 확률과정과 MP, MRP, MDP에 대해 살펴보았다.

 이러한 수학적 기초를 바탕으로 앞으로는 강화학습 알고리즘에 대해서 학습한다. 우선, 강화학습은 agent와 environment 간 상호작용을 통해 agent가 환경에 대한 정보를 취득해 나아가며 학습하는 방법을 말한다. 그래서 아래 그림과 같이 agent는 매 단계마다 환경으로부터 주어지는 상태 정보를 취득하고 이를 바탕으로 특정 행동을 취한다. 행동을 통해서 agent는 환경으로부터 일종의 보상을 받게 되고, 환경은 시스템에 의해 다른 상태로 전이가 이루어진다. 이러한 과정을 반복하며 agent는 보상을 최대화하기 위해 어떤 행동을 취해야할지를 학습한다.

 

강화학습의 구조

 

이번 시간에는 다시 한 번 Infinite-horizon MDP에 대해 복습하고, Infinite-horizon MDP와 강화학습이 가정하고 있는 상황이 어떤 차이가 있는지를 중심으로 살펴보자.

 

1. Infinite-horizon MDP

$$\{S, A_s, p(\cdot|s,a), r(s,a), \gamma : s \in S, a \in A_s \}$$

 

구성 요소

 

1. 상태 공간 (state space) $S$
   • 에이전트가 관찰할 수 있는 상태들의 집합
2. 행동 공간 (action space) $A_s$
   • 환경에 따라 취할 수 있는 행동 후보들의 집합
   • 상태에 따라 행동들의 집합이 달라질 수 있음
3. 상태전이확률 (state transition probabilities) $p(s^\prime|s,a)$ - 시스템 정보(주어진 정보)
   • 특정 상태 $s$ 에서 행동 $a$를 취했을 때 다음 상태 $s^\prime$이 될 확률
4. 보상 (rewards) $r(s,a)$ - 시스템 정보(주어진 정보)
   • 보상의 기대값
   • 강화학습을 정의하는 환경에 따라 변화
     • 행동을 취한 즉시 보상: $r(s,a)$
     • 다음 상태까지 주어졌을 때 보상: $r(s,a) = \sum_{s^\prime}{p(s^\prime|s,a) r(s,a,s^\prime)}$
     • 위 식에서 $p(s^\prime|s,a)$는 시스템에서 주어진 시스템 정보(given)
5. 감가율 (discounting factor) $\gamma$
   • 수식적: 어떤 상태에서 어떤 행동을 취할지 판단 근거가 되는 누적보상의 발산 방지(일정한 값으로 수렴)
   • 의미적: 미래가치를 현재 가치로 환원

 

정책 (policy) $\pi$

 

 정책은 finite-horizon MDP의 경우, 특정 의사결정 시점에서 어떤 상태에서 어떤 행동을 취할지에 대한 의사결정 규칙을 모든 시점에 대해 모아놓은 것을 의미한다. 그러나, Inifitie-horizon MDP의 경우, 모든 시간에 독립적이라는 정상성을 만족하기 때문에 의사결정 규칙이 바로 정책이 된다. 즉 정책은 상태를 행동에 mapping한 함수라고 볼 수 있다. 또한, 정책은 다음과 같이 크게 2가지로 나뉜다.

 

• 확정적 정책(Deterministic policy)
  • $\pi(s) = a$
  • 정책이 주어져 있다 → 모든 상태에 대해 어떤 행동을 취할지 매핑

확정적 정책

 

• 확률적 정책(Stochastic policy)
  • $\pi(a|s) = P(A_t=a|S_t=s)$
  • 확률 분포가 주어져 있다 → 모든 가능한 상태와 행동에 대한 확률이 주어져 있음

확률적 정책

 

추후 학습할 정책을 학습한다는 개념을 가진 정책 기반 강화학습 방법론에서 확률적 정책을 사용하게 된다. 정책을 학습하는 관점에서 어떤 상태에서 어떤 행동을 취했을 때 값이 서서히(gradually) 변하는 것이 유리하기 때문이다.

 

최적 정책 $\pi^*$

 

 MDP에서의 궁극적인 목적은 최적 정책(optimal policy)을 찾는 것이다. 정책은 무수히 많은 수가 존재하기 때문에, 그 중에서 감가율이 반영된 모든 미래 보상합을 최대화하는 최적 정책을 찾아야 한다. 즉, 아래 그림의 좌측처럼 정책 $\pi$를 따르게 되면, 일련의 보상을 얻게 되고, 감가율을 반영한 누적보상합을 최대화하는 정책이 최적 정책이 된다.

 

사실 정책이 주어졌을 때, 감가율을 반영한 누적보상합의 기대값은 상태 가치함수에서 정책이 주어진 형태, 그리고 행동 가치함수의 형태와 동일한 형태임을 쉽게 알 수 있다.

 

정책 평가 (policy evaluation)

 

 정책이 주어졌을 때, 감가율을 반영한 누적보상합의 기대값을 계산하는 것을 정책 평가라고 한다. 즉, 정책이 주어졌을 때 상태 $s$의 가치함수 $v^\pi (s)$는 정책의 형태에 따라 구체적으로 다음과 같이 벨만 기대방정식을 사용해 계산할 수 있다. 

• 확정적 정책
  • $v^\pi(s) = r(s,\pi(s)) + \gamma \sum_{s^\prime}{P(s^\prime|s,\pi(s))v^\pi(s^\prime)}$
• 확률적 정책
  • $v^s = \sum_{a \in A}{\pi(a|s)}[r(s,a) + \gamma \sum_{s^\prime}{P(s^\prime|s,a)v^\pi(s^\prime)}]$

 

벨만 최적 방정식

 

 

 모든 정책 $\pi$에 대해 개별 상태 $s$에 한 가치함수를 계산할 수 있다면, 그 중에서 가장 좋은 정책이 특정 $s$에 대한 최적 정책이 된다. 이를 표현한 식이 벨만 최적 방정식으로 다음과 같다. 즉, $v^*(s)$는 감가율이 보장된 누적 보상합 기대값의 최대치이며, 각 상태에 대해 이 값을 만드는 행동 $a$가 의사결정 규칙이 된다.

 

$$v^*(s) = max_a{[r(s,a) + \gamma \sum_{s^\prime}{P(s^\prime|s,a)v^*(s^\prime)}]}$$

 

이때, 좌변의 $v^*$와 우변의 $v^*$가 동일한 함수이기 때문에 위 식을 풀기 위한 두 가지 방법론에 대해 배웠다. 첫 번째는 가치값을 초기화한 후 가치함수 값 계산을 반복하는 가치 반복 알고리즘, 두 번째는 임의의 정책으로부터 시작해 정책 평가와 정책 개선을 반복하는 정책 반복 알고리즘이다.

 

2. 강화학습

 

Infinite-horizon MDP와 강화학습의 차이점

 

 Infinite-horizon MDP와 강화학습의 주요 차이점은 학습 시 모델(환경)에 대한 정보의 유무다. Infinite-horizon MDP의 구성요소에서 살펴보았듯, 상태전이확률 $p(\cdot|s,a)$과 보상 $r(s,a)$에 대한 정보가 시스템으로부터 주어졌지만, 강화학습은 상태전이확률과 보상에 대한 정보가 부재한 상황에서 agent가 environment와 일련의 상호작용을 통해, 즉 경험을 통해 학습을 진행하게 된다.

 

강화학습 방법론 분류

 

 강화학습은 학습 방법을 기준으로 Model-based methods와 Model-free methods로 나눠볼 수 있으며 Model-free method는 다시 value-based methods와 policy-based methods로 나뉜다.

• Model-based methods: agent가 환경과 상호작용하며 수집한 데이터를 바탕으로 모델 추정. 즉, 상태전이확률과 보상을 추정하며 추정치를 활용해 Infinite-horizon MDP 방법론 등으로 최적 정책 도출
• Model-free methods: 모델을 추정하기보다, 일련의 상호작용을 통해 얻은 데이터로 학습이 이루어짐
  • Value-based methods: 최적 행동 가치함수 추정
  • Policy-based methods: 정책을 개선해 나가며 최적 정책을 직접적으로 검색

 

가장 단순한 model-based 강화학습의 예시

 

 가장 단순한 형태의 모델기반 강화학습을 생각해보자. 에이전트와 환경과의 상호작용을 통해 상태, 행동, 보상의 데이터를 얻고 이를 바탕으로 상태전이확률과 보상의 기대값을 추정해볼 수 있을 것이다.

$$s_1, a_1, r_1, s_2, a_2, r_2, s_3,a_3,r_3,\cdots,s_m,a_m,r_m$$

 

이러한 데이터를 활용해 상태전이확률과 보상은 아래와 같이 sample mean으로 구해볼 수 있을 것이다.

 

$$p(s^\prime|s,a) = \frac{\sum_{i}^{m-1}{I(s_i=s, a_i=a, s_{i+1}=s^\prime)}}{\sum_{i}^{m-1}{I(s_i=s, a_i=a)}}$$

 

$$r(s,a) = \frac{\sum_{i}^{m-1}{I(s_i=s, a_i=a)r_i}}{\sum_{i}^{m-1}{I(s_i=s, a_i=a)}}$$

 

이처럼 일련의 데이터로부터 상태전이확률과 보상을 추정하고, 이를 바탕으로 Infinite-horizon MDP에서 배운 방법론을 통해 최적의 정책을 도출할 수 있게 된다.

 

3. 몬테카를로 학습(Monte-Carlo Learning)

3.1 도입

 몬테카를로 방법에 대해 알아보기 전 먼저 원주율을 추정하는 문제를 살펴보자. 한 변의 길이가 1인 정사각형 안에 한 변을 반지름으로 하는 원의 일부분을 생각해보자. 그럼 정사각형의 넓이는 1, 그리고 정사각형 내 원의 일부분의 넓이는 $\frac{\pi}{4}$이다.

 

 

 

 이와 같은 상황에서 $\pi$의 값은 정사각형 공간에 랜덤하게 점을 뿌린 뒤, 전체 점의 개수 대비 원 안에 들어간 점들의 개수로 원주율을 계산해볼 수 있을 것이다. 예를 들어, 100개의 점들 중 80개가 빨간색 부분에 들어갔다고 가정해보자. 그러면 정사각형의 전체 넓이 1 중 $\frac{80}{100}$이 빨간색에 해당하므로 $\frac{\pi}{4}\approx 1\cdot\frac{80}{100}= 0.8$이 되고, 최종적으로 $\pi \approx 3.2$로 추정해볼 수 있다. 

 이와 같은 방법의 장점은 랜덤하게 점을 뿌려서, 점의 수의 비율로 넓이를 추정한다는 점이다. 예를 들어 특이한 모형의 도형의 넓이도 쉽게 계산할 수 있다. 

 

 

3.2 몬테카를로 방법

 위의 예처럼 몬테카를로 방법은 한마디로 표현하자면 직접 해보는 것이다. 즉, 실제 시도해 얻어진 데이터를 바탕으로 상태 가치함수 값이나 행동 가치함수 값을 추정하는 것이다. 강화학습에서는 에이전트가 초기 상태부터 종결 상태까지 거친 (상태, 행동, 보상)의 시퀀스를 에피소드라고 한다. 따라서, 몬테카를로 방법을 강화학습의 관점에서 본다면, 에이전트가 정책에 따라 환경과 상호작용을 통해 얻은 에피소드들로부터 도출된 반환값들의 평균을 각 상태별 가치 함수로 활용하는 것이다. 즉, 에피소드로부터 직접적으로 가치함수를 학습(가치함수의 추정치를 갱신)해나가는 방법이다.

 

3.3 에피소드

 에이전트와 환경과의 일련의 상호작용은 에피소드 단위로 구분할 수 있다. 각 에피소드는 임의의 특별한 종료상태(terminal state)에서 종료가 일어난다. 따라서, 에이전트와 환경 간 일련의 상호작용이 일어나다 종료상태가 되면 하나의 에피소드가 된다. 그리고 각 에피소드는 독립적(independent)이다.

 

 

또한, 하나의 에피소드에서 동일한 상태가 반복될 수 있다. 틱택토의 경우 과거의 상태가 미래에 나타날 수 없지만, 미로찾기의 경우는 길을 찾는 과정에서 과거의 상테에 다시 위치할 수도 있다.

 

 

정리하면 다음과 같다.

• 에피소드 (episode)
  • 일련의 상호작용은 에피소드 단위로 구분할 수 있다.
  • 각 에피소드는 임의의 특별한 종료상태에서 종료된다.
  • 각 에피소드는 독립적이다.
  • 하나의 에피소드에서 동일한 상태가 여러 번 나타날 수 있다. 

 

• 에피소드의 리턴(return) $G_t$

우리가 관심있는 것은 일관되게 특정 상태로부터 마지막까지 얻을 수 있는 누적 보상합이다. 각 에피소드에 대해서도 이러한 개념의 리턴(return; 반환값)을 정의할 수 있다. 즉, 리턴은 현재 시점 $t$부터 에피소드 종료시까지의 보상들의 합 즉, 누적보상합을 의미한다. 만약 종료상태의 시점을 $T$라고 한다면 하나의 에피소드에 대한 리턴은 다음과 같이 정리할 수 있다. 이때 통상적으로 감가율 $\gamma$는 1을 사용한다.

 

$$G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3}+ \cdots + \gamma^{T-t-1}R_T = \sum_{k=t+1}^{T}\gamma^{k-t-1}R_k$$

 

• 연속 작업(continuing tasks)

 앞서 본 것과같이 종료 조건이 있어 에피소드가 종료되는 경우도 있지만, 상황에 따라서 에피소드가 자연스럽게 분할이 어려운 경우가 있다. 즉, 프로세스가 무한히 반복이 되는 경우가 존재하며 이런 경우를 연속 작업이라고 한다. 대표적인 예로 주가 변동이 있다. 주식 거래는 9시부터 4시까지 이루어지기 때문에 분할이 된다고 볼 수도 있지만, 오늘 장의 종점이 다음 날의 시점과 일치한다. 따라서, 주가 변동 프로세스는 무한히 지속된다고 볼 수 있다. 이러한 연속 작업의 리턴은 보상의 합이 무한대로 발산할 수 있기 때문에 감가율(discounting factor)을 도입한다.

 

• 연속 작업의 리턴 - 감가율 도입

$$G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3}+ \cdots + \gamma^{T-t-1}R_T = \sum_{k=t+1}^{T}\gamma^{k-t-1}R_k$$

 

• 에피소드 단위의 리턴

하나의 에피소드에 대해서 거쳐간 모든 상태에 대한 리턴을 각각 산출해낼 수 있다.

 

 

3.4 몬테카를로 정책평가(MC policy evaluation)

 몬테카를로 방식에 의해서 정책이 주어졌을 때, 정책을 평가하는 방법에 대해 살펴보자. 우선, 연속 작업에서도 몬테카를로 방법 적용은 가능하나, 일반적으로 몬테카를로 방법은 종결 상태까지 완료된 에피소드에 한정하여 사용한다. 

 특정 정책 $\pi$에 따라 임의의 에피소드가 주어진 경우를 생각해보자. 어떤 상태에서 특정 행동을 취하면 보상을 얻게되고, 시스템에 대한 정보가 없기 때문에 상태가 어떻게 전이되는지는 모르지만 환경은 다음 상태로 전이가 이루어진다. 전이된 상태에서 또 다시 정책에 의해 행동을 취하고 보상을 받고 다시 상태전이가 일어나는 과정을 반복하게 된다. 이 과정은 $T$시점에서 종료된다. 이때, $s$라는 상태에 대한 리턴은 아래와 같이 계산할 수 있다.

 

 

  이번에는 에피소드들을 무한히 반복을 한다고 가정해보자. 그러면 각 에피소드에 대해서 상태 $s$에 대한 리턴들을 계산할 수 있다. 여기서, 상태 가치함수를 상기해보자. 상태 가치함수 $V_\pi (s)$는 정책 $\pi$가 주어졌을 때, 리턴의 기대값이다. 따라서, $G_t$를 다양한 에피소드들에 대해 계산 후 산술평균한다면 약한 대수의 법칙(WLLN)에 의해 $V_\pi(s)$로 수렴하므로 해당 $G_t$로 $V_\pi(s)$로 추정할 수 있다. 

 

몬테카를로 정책 평가 방법

 

 앞서 말했듯 하나의 에피소드에는 동일한 상태가 여러 번 등장할 수 있기 때문에 리턴을 어떻게 계산할 것인지에 따라 몬테카를로 방법은 크게 두 가지로 구분할 수 있다.

 

• First-visit MC
  • 최초 방문 몬테카를로 방법
  • 단일 에피소드 내, 특정 상태를 여러 번 방문하여도 해당 상태를 처음 방문한 시점부터 종결 상태까지의 누적 보상합을 해당 에피소드의 해당 상태에 대한 리턴값으로 사용
  • 뒤에 동일한 상태는 무시하므로, 하나의 에피소드가 주어졌을 때 해당 상태에 대한 리턴값은 하나가 존재하거나, 존재하지 않거나의 경우만 존재
• Every-visit MC
  • 모든 방문 몬테카를로 방법
  • 단일 에피소드 내, 특정 상태를 여러 번 방문한 경우, 해당 상태를 방문한 각각의 시점에 대해 누적보상합을 계산하고 가치함수 값 추정에 사용

 

MC example

 

 아래와 같이 5개의 상태가 주어지고, 좌측과 우측으로 이동하는 행동만이 존재하는 프로세스에서 상태 3에 대한 가치함수를 first-visit MC와 every-visit MC 방법으로 구해보자. 좌측으로 이동했을 시의 보상은 -1, 우측으로 이동했을 시의 보상은 +1이며, 감가율 $\gamma$는 1이라고 하자.

 

 

• First-visit MC

빨간 네모 상자로 표시한 상태를 시작점으로 하는 누적 보상합을 각 에피소드마다 계산하게 된다.

 

 

EP1: $G^1(3) = 1+( -1)+1+1+1=3$

EP2: $G^2(3) = 1 +1+1=3$

EP3: $G^3(3) = 1+(-1)+1+1+1=3$

 

따라서, First-visit MC를 사용했을 때 가치함수 값의 추정치는 다음과 같다.

$$v^\pi(3)=\frac{3+3+3}{3}=3$$

 

• Every-visit MC

EP1(1): $G^1_{(1)}(3) = 1+( -1)+1+1+1=3$

EP1(2): $G^1_{(2)}(3) = 1+1+1=3$

  EP2:  $G^2(3) = 1 +1+1=3$

EP3(1): $G^3_{(1)}(3) = 1+( -1)+1+1+1=3$

EP3(2): $G^3_{(2)}(3) = 1+1+1=3$

 

따라서, First-visit MC를 사용했을 때 가치함수 값의 추정치는 다음과 같다.

$$v^\pi(3)=\frac{3+3+3+3+3}{5}=3$$

 

따라서, 몬테카를로 정책 평가를 정리하면 다음과 같다.

 

 

3.5 점진적 몬테카를로 정책평가(Incremental MC policy evaluation)

 만약 100개의 에피소드로부터 가치함수를 추정했다고 가정하자. 101개의 에피소드를 활용해 가치 함수의 추정을 하고 싶을 때, 만약 101개 에피소드들로부터 다시 계산을 한 뒤, 가치함수를 추정하는 방법을 사용한다면 비효율적이다. 따라서, 기존까지 계산된 가치함수를 기반으로 추정값을 업데이트하는 것이 모든 에피소드 값을 가지고 있을 필요가 없어 정보 관리 차원 및 계산 효율성 면에서 합리적이다.

 

 

 $V_{n+1}$을 $n$개의 리턴을 통해 평균을 취한 가치함수 값이라고 하자.

 

$$V_{n+1} = \frac{1}{n}\sum_{i=1}^{n}{G_i} = \frac{1}{n}(G_n + (n-1)\frac{1}{n-1}\sum_{i=1}^{n-1}{G_i})$$

$=\frac{1}{n}(G_n + (n-1)V_n) = V_n + \frac{1}{n}(G_n - V_n)$

 

 

• 몬테카를로 방법에 따른 가치함수 업데이트 방법

$V(S_t)$ ← $V(S_t) + \alpha (G_t - V(S_t))$

 

몬테카를로 방법에 따른 가치함수 업데이트 방법에서 달라진 점은 $\frac{1}{n}$이 $\alpha$로 변경되었다는 점뿐이다. 즉, $\alpha$는 새로운 정보를 얼마만큼 반영할 것인가를 조절하는 모수로 learning rate라고 부른다. 

 

 

3.6 MC 기반 정책 반복

 지금까지는 정책이 주어진 상황에서 가치함수 값을 추정하는 방법에 대해서 살펴봤다면, 좀 더 나아가 정책을 개선하는 방법에 대해 알아보자. 정책 개선을 하기 위해서는 가치함수 값 추정만이 아니라, 행동 가치함수가 필요하게 된다. 만약 행동 가치함수를 추정할 수 있게 된다면, 이를 통해 특정 상태에 대해서 가장 좋은 여러 가지 행동들 중 가장 좋은 행동을 선택할 수 있다. 즉, 아래와 같이 어떤 상태 $s$에 대해서 $Q(s,a)$의 추정치를 최대화하는 행동 $a$를 구할 수 있다면 정책을 개선할 수 있게 된다.

 

$$\pi(s) = \arg\max_a {\tilde{Q}(s,a)}$$

 

• Q함수에 대한 추정치 계산 방법

예를 들어 에피소드1에서 상태가 4일 때 우측으로 이동할 때의 Q함수를 추정하고자 한다고 하자.

 

 

 

EP1: $G^1 = 1+1=2$

EP2: $G^2 = 1+1=2$

EP3: $G^3 = 1+1=2$

 

따라서, First-visit의 경우 (상태4, 우측 이동)에 대해서 총 3개의 반환값을 사용하고 다음과 같이 Q함수를 추정할 수 있다.

$$Q^\pi(4,우측)=\frac{2+2+2}{3}=2$$