[yongggg's] Basic Contents of Reinforcement Learning

1. 강화학습 원리와 성질

원리

강화 학습은 state, action을 번갈아 수행하며 목표를 달성하는 원리이다.

Environment(환경)은 Agent(행위자)가 행동하는 공간이며, 어떤 State(상태)에서 행위자의 Action(행위)에 따라 새로운 State(상태)로의 변화와 그 행위에 대한 Reward(보상)이 만들어진다. 연속된 행위의 처음과 종료까지를 하나의 Episode(에피소드)라고 하는데, 하나의 에피소드를 통해 얻어진 보상의 합을 G(수익)이라고 한다. 강화학습은 바로 이 수익을 최대화시키기 위한 행위가 선택될 수 있는 Policy(정책)를 강화시키는 것이 목표이다.

아래 [그림 1]을 예제로 알기 쉽게 설명해보자면,

[그림 1] 강화 학습의 핵심 개념인 상태, 행동, 보상

$s_{t}$에서 action(행동) $a_{t}$을 취하면, 새로운 state(상태) $s_{t+1}$로 바뀌고 reward(보상) $r_{t+1}$를 받는다고 생각하면 된다.

마지막 시점을 $T$라고 했을 때, $t=T$([그림 1]의 예시에서는 $T=5$)인 순간에 과업이 성공했으므로, reward 1을 주면된다. 하지만, 중간에 넘어진다면 reward -1을 주고, $r_{1}$ ~ $r_{4}$의 중간 reward은 0으로 설정한다.

이 때, 마지막 순간의 state는 중간 state의 영향을 받아 성립이 되었기 때문에, 최종 순간의 reward를 이전 state에 나눠주어야 할 경우도 생길 수 있다. 이를 credit assignment problem(신뢰 할당 문제)라고 한다.

용어

agent(행위자)와 environment(환경)의 역할은  다음과 같다. agent는 action을 결정하고 environment는 state 전환과 reward 수준을 결정한다. environment 설명에 덧 붙이자면, Markov Decision Process(MDP)는 문제 정의시 주어지는 정보이며, environment는 MDP에 따라 다음 상태와 보상을 결정한다. 강화 학습은 주어진 MDP에서 최적의 action을 결정하는 정책을 찾아야 한다.

 

강화 학습의 목표는 '누적' reward level을 최대화하는 것이다. 즉, 순간 이득을 최대화하는 action이 아니라 긴 시간 동안 누적 보상액이 최대가 되는 action을 선택해야 한다. agent가 action을 선택하는 데 사용하는 규칙을 policy(정책)이라고 하며, 강화 학습 알고리즘은 최적의 policy를 찾아야 한다. 또한  state, action, reward는 연속값일 수도 있지만, 대부분의 application에서는 이산 값을 가진다.

[그림 2] 강화 학습의 계산 모델

[그림 2]는 강화 학습의 계산 모델을 나타내며, state(상태), action(행동), reward(보상)의 표기는 다음과 같이 나타낼 수 있다.

• set of state  : $S = s_{1}, s_{2}, \cdots, s_{n}$
• set of action : $A = a_{1}, a_{2}, \cdots, a_{n}$
• set of reward : $R = r_{1}, r_{2}, \cdots, r_{n}$

source :
http://www.gisdeveloper.co.kr/?p=9016
https://wordbe.tistory.com/entry/RL-%EA%B0%95%ED%99%94%ED%95%99%EC%8A%B5-part1-policy-value-function

policy(정책) 

동, 서, 남, 북으로 이동할 수 있는 action을 가진 로봇이 있다고 가정하자.

이 때, 모든 방향으로 이동하는 확률이 같다면, 다수의 경로의 누적 reward가 같아지는 문제가 발생할 수 있다. 예를 들어, 바둑판에서 더이상 북쪽으로 갈 곳이 없을 경우에는, 북을 제외한 나머지 방향에 똑같이 ${1}\over{3}$의 확률을 부여하며, 북으로 갈 확률을 0으로 부여하는 것이 더 좋을 것이다.

2. 탐험과 탐사

exploration and exploitation(탐험과 탐사)

탐험은 전체 공간을 골고루 찾는 방법이며, 탐사는 특정한 곳 주위를 집중적으로 찾아보는 strategy이다. global 해를 찾을 때, 탐험 방법은 시간이 너무 오래 걸리며, 탐사는 local 해를 찾는 문제가 있을 수 있다.

강화 학습에서는 일반 딥러닝과 다르게, exploitation(탐사) 방법을 사용한다면, 열등 해를 얻는 상황이 많다. 따라서, 탐험과 탐사의 단점을 보완하기 위해, 균형 방식을 사용한다. [그림 3]은 k-손잡이 밴딧 문제를 나타낸다.

[그림 3] K-손잡이 밴딧 문제

사용자가 어느 기계가 몇의 확률로 잭팟이 나오는지 알지 못하는 상황이라고 가정했을 때, 10번의 시도 끝에 2 번째 손잡이에서 잭팟이 나왔다면, 2 번째 슬롯를 당길 확률을 높혀 다시 뽑기를 진행한다. 이 방식은, 똑같이 당기는 탐험 방식도 아니며, 2번 째 손잡이만을 고르는 방식이 아닌, 다른 손잡이를 고를 수 있는 기회를 준다. 이 때, 다른 기계에서 잭팟이 터진다면, 다른 기계의 정보를 고려하여 확률을 배분하고 수정한다. 이 것이 강화 학습에서 사용하는 균형 방식의 예이다.

3. Markov Decision Process(MDP)

마르코브 결정 프로세스의 과정은 현재 state에서  action을 결정할 때, 이전 이력은 중요하게 생각하지 않으며, 현재 state를 중요하게 생각하여, action을 결정하는 성질을 가진다.

$$P(s_{t+1}, r_{t+1} | s_{0}, a_{0}, r_{1}, s_{1}, a_{1}, \cdots, r_{t-1}, s_{t-1}, a_{t-1}, r_{t}, s_{t}, a_{t}) = P(s_{t+1}, r_{t+1} | s_{t}, a_{t})\\P(s_{t+1}, r_{t+1}|s_{t}, a_{t}) = P(s^{'}, r| s, a)$$

하지만, 모든 응용문제가 마르코프 성질을 만족하지 않는다. 예를 들어, 날씨 예측 혹은 바둑 등이 앞 선 상태들 모두가 뒤에 나올 상태를 예측하는 데에 도움이 된다.

 

강화학습은 마르코프 성질을 만족한다는 전제 하에 동작한다. 따라서 Markov property를 근사하게라도 만족하는 문제에 국한하거나, 근사하게 할 수 있도록 상태 표현을 설계하여 적용한다.

$$ S=맑은후맑음, 비온후맑음, 눈온후맑음, \cdots, 눈온후눈$$

과 같이 특징을 섞어 표현하면 마르코프 성질에 근사히 가깝게 표현할 수 있다.

 

먼저 MDP의 확률 분포를 $ P(s^{'},r|s,a) $ 라고 했을 때, MDP의 종류는 다음과 같이 크게 두 가지가 존재한다.

1. 결정론적(Deterministic) MDP : 한 가지 상태와 보상이 있는 경우, 나머지 보상은 전부 0
2. 확률론적(Stochastic) MDP: 다음 상태와 보상이 확률적으로 결정되는 경우

4. 정책과 가치함수

용어 파트에서 설명한 Policy는 agent가 action을 선택하는 데 사용하는 규칙을 policy(정책)이며, 강화 학습의 핵심은 좋은 Policy를 찾아내는 것이다. 좋은 Policy가 있으면, 누적 보상을 최대로 만들 최적 행동을 매 순간 선택할 수 있다.

하지만 Policy Space(정책 공간)은 너무 방대하기 때문에 최적 Policy를 찾는 접근 방법은 무모할 수 있으며, 최적 Policy를 찾아가는 길잡이 역할을 하는 value function(가치함수)를 통해 최적의 Policy를 찾을 수 있다.

다음은 Policy와 가치함수에 대한 설명이다.

Policy

policy는 state $s$에서 action $a$를 취할 확률을 모든 state와 action에 대해 명시한 것이다.  다음은 policy 함수 $\pi$를 나타낸다.

$$ \pi(a|s) = P(a|s), \forall s, \forall a$$

 

$ 4 \times 4 $ 격자 판에서, 파란색 네모에서 출발하여 좌측 상단 혹은 우측 하단까지 도착하는  예시를 살펴보자.

먼저, 각 Cell에서 동, 서, 남, 북으로 이동할 확률이 같은 경우를 생각할 수 있다. 이는 다음과 같은 policy function으로 표현할 수 있다.

$$ \pi_{1} : P(동|i) = P(서|i) = P(남|i) = P(북|i) = {1\over4} , i=2,\cdots,15 $$

[그림 4] 여러 가지 policy($\pi_{4}$는 최적의 정책임)

여기서 남으로만 갈 수 있는 $\pi_{2}$라는 정책을 생각해 보자. $\pi_{2}$는 다음과 같은 식으로 정의되며, 이 정책은 4, 8, 12 중 한 곳에서 시작하지 않는 한 종료 상태에 도달할 수 없다. 따라서 해의 품질을 떠나 아예 채택할 수 없는 정책이라고 할 수 있다.

$$ \pi: P(동|i)=P(서|i)=P(북|i)=0, P(남|i)=1, \quad 상태 i =2, \cdots, 15 $$

마찬가지로 $ \pi_{3}, \pi_{4}$를 구해볼 수 있다.

그림에서 $\pi_{4}$의 경우 가장 짧은 시간에 목표 상태에 도달하여 최고의 누적 보상액을 받았음을 알 수있다. 강화학습은 학습 알고리즘을 통해 MDP에서 이와 같은 최적의 정책을 찾아야 한다.

최적의 정책 찾기

$goodness(\pi)$가 정책 $\pi$의 품질을 측정해주는 함수라고 하자.

$$ \hat{\pi} = argmax_{\pi} goodness(\pi) $$

학습 알고리즘은 위를 만족하는 정책 $\hat{\pi}$를 알아내야 한다. 바둑 같은 상황에서는 상태공간(state space)이 방대하며, 정책 공간(policy space)은 서로 다른 정책 집합을 뜻하고 상태 공간보다 훨씬 방대하다.

따라서 강화학습에서는 정책공간을 하나하나 직접 탐색하는 대신 가치함수를 이용한다. 이 때, 최적의 가치함수를 찾으면, 최적 정책을 찾는 것은 trivial(사소한) 문제가 된다.

가치함수(Value function)

가치함수는 특정 정책의 좋은 정도(상태 s로부터 종료 상태에 이르기까지 누적 보상치의 추정치)를 평가한다. 정책 $\pi$에서 추정하며, 상태 s의 함수이므로 $v_{\pi}(s)$로 표기한다.

즉, 위에서 쓰인 goodness는 가치함수로 바뀌며, 다음과 같이 나타낼 수 있다.

$$ \hat{\pi} = argmax_{\pi}v_{\pi}(s), \forall s \in S$$

$$ v_{\pi}(s) = \sum_{s에서 출발하는 모든 경로 z}P(z)r(z), \; P(z)는 \; 경로 \; z의 \; 발생확률, \; r(z)는 \; 경로 \; z의 \; 누적 \; 보상액이다.$$

에피소드(episode) 과업과 영구(continuing) 과업 

$$ r(z) = r_{t+1} + r_{t+2} + \cdots + r_{T} $$

경로 $z$에 따른 보상액은 누적하여 위처럼 구할 수 있으며, z는 아래와 같이 표현할 수 있다.

$$ 유한 \; 경로(에피소드 \; 과업) \; z:(s_{t},r_{t}) \xrightarrow {a_{t}} (s_{t+1}, r_{t+1}) \xrightarrow{a_{t+1}} (s_{t+2}, r_{t+2}) \xrightarrow{a_{t+2}} \cdots \xrightarrow{a_{r-1}} (s_{r}, r_{r})$$

$$ 무한 \; 경로(영구 \; 과업) \; z: (s_{t}, r_{t}) \xrightarrow {a_{t}} (s_{t+1}, r_{t+1}) \xrightarrow {a_{t+1}} (s_{t+2}, r_{t+2}) \xrightarrow {a_{t+2}} (s_{t+3}, r_{t+3}) \xrightarrow {a_{t+3}} (s_{t+4}, r_{t+4}) \cdots $$

 

강화학습에서 유한 경로를 가진 과업을 에피소드 과업(episode task)이라고 한다. 반면, 무한 경로를 가진 과업을 영구 과업(continuing task)이라고 한다.  

특별히 영구과업은 무한대 보상을 막기 위해, 할인 누적 보상액(discounted accumulating reward)을 사용한다. $\gamma$를 할인율(discounting rate)이라고 하며, $0 \leq \gamma \leq 1 $ 이다. 

$$ r(z)=r_{t+1} + \gamma r_{t+2} + \gamma^{2} r_{t+3} + \cdots = \sum_{k=1}^{\infty} {\gamma^{k-1}r_{t+k}} $$

여기서 $\gamma$ 가 0이면, $r_{t+1}$만 남으므로 순간의 이득을 최대화하는 탐욕 방법인 근시안적 보상액이 되고 $\gamma$가 1이면, 모든 순간을 반영하는 보상액이 된다.

따라서 할인 누적 보상액은 현재에서 멀어질수록 보상을 할인하여 공헌도를 낮추는 전략임을 알 수 있다.

가치함수 추정을 위한 순환식

점화식과 같이, 다음 상태에서의 가치함수를 표현하여 가치함수를 간단하게 표현할 수 있다.

$$ v_{\pi} (s) = \sum_{a \in A(s)} {P(a|s)(r+v_{\pi}(s')), \forall s \in S} $$

스토캐스틱 프로세스에서 가치함수 추정

지금 까지의 수식은 결정론적(deterministic) 프로세스였다.

결정론적  프로세스는 많은 응용을 설명하지 못한다. 현실에서 모든 요인을 상태 변수에 반영하는 대신 주요 요인만을 반영하고 나머지는 무시한 상황에서의 상태, 행동, 보상을 스토캐스틱(stochastic) 프로세스라고 한다.

 

스토캐스틱한 성질은 $P(s', r|s, a)$ 확률로 표현된다. 이는 MDP 확률분포이며, 상태 s에서 행동 a를 취했을 때 상태는 s'로 바뀌며, 보상 r을 받을 확률이다. 스토캐스틱은 이 값이 여러개일 수 있으므로, 모두 더하여 사용한다.

 

가치함수는 MDP 확률분포가 제공하는 정보와 정책 $\pi$가 제공하는 정보를 모두 활용하여 정책을 평가한다.

$$ v_{\pi}(s) = \sum_{a \in A(s)} {P(a|s)} \sum_{s'} \sum_{r} {P(s', r|s, a)(r+v_{\pi}(s')), \forall s \in S} $$

무한 경로를 가진 응용문제에는 할인율을 적용한 식을 사용하면 된다.

$$ v_{\pi}(s) = \sum_{a \in A(s)} {P(a|s)} \sum_{s'} \sum_{r} {P(s', r|s, a)(r+\gamma v_{\pi}(s')), \forall s \in S} $$

 

이 두 식은 상태 가치 함수(State value function)라고 하며, 위 두 식의 순환식을 가치함수를 위한 벨만 수식(Bellman equation)이라고 한다. 현재 상태의 가치는 다음 상태의 가치의 관계를 간결하게 표현할 수 있다.

 

이와 다르게 상태와 행동에 대한 가치함수는 상태-행동 가치함수(state-action value function)라고 하며, 식은 아래와 같다.

$$ q_{\pi}(s,a) = \sum_{s'} \sum_{r} {P(s', r|s, a)(r+ \gamma v_{\pi}(s')), \forall s \in S, \forall a \in A} $$

5. 최적 가치 함수

최적 가치함수를 안다면, 최적의 정책을 쉽게 결정할 수 있다.

$$ \hat{v}(s) = v_{ \hat{\pi}} (s) = \max\limits_{\pi} v_{\pi} (s), \forall s \in S $$

$$ \max\limits_{a \in A(s)} \sum_{s'} \sum_{r} P(s', r|s, a) (r+v_{\pi}(s')), \forall s \in S $$

상태 가치함수는 mean 연산을 통해 구하는 반면, 최적 가치함수는 max 연산을 통해 구하며, 무한 경로를 위해 할인율을 적용한 수식은 다음과 같다.

$$ \hat{v}(s) = \max\limits_{a \in A(s)}  \sum_{s'} \sum_{r} P(s', r|s, a) (r+ \gamma v_{\pi} (s')), \forall s \in S$$

 

위의 과정이 강화학습에서는 어떻게 작용하는 지는 다음과 같이 설명할 수 있다.

1) 초기값은 랜덤 initialization 으로 정책을 설정한 뒤, 출발 함

2) 정책에 따라 가치함수를 계산함 (정책의 품질 평가)

3) 얻은 가치함수로 정책이 더 나아지도록 개선함 (정책의 평가와 개선은 MDP 확률분포를 기초로 이루어짐)

4) 정책 개선 싸이클이 임계점보다 작아질 때까지 반복함 (동적 프로그래밍, 몬테카를로, 시간차 학습 알고리즘은 모두 이 아이디어에 근거하고 있음)

 

이렇게 강화학습이 돌아가는 원리를 기초에 근거하여 리뷰를 해보았습니다.

저도 처음 강화학습에 대한 공부를 하며, 용어 정리부터 어떻게 계산되는 지 명확히 잡히지는 않습니다...ㅠ 

더 공부하여 더 좋은 글 올리겠습니다. 긴 글 읽어주셔서 감사합니다.

해당 내용의 오류나 문제는 댓글로 달아주시면 감사하겠습니다 ^^