[AI] 7. Reinforced Learning

Reinforcement Learning

앞 글에서 Markov Decision Process를 다루었다. 조사해보니 Markov Process(MP), Markov Reward Process(MRP) 등 내가 생각한 것 보다 기술의 범위가 매우 넓었으나 일단은 이정도 지식도 벅차기 때문에 추후에 리뷰하는 것이 좋을 듯 하다.

어쨌든 앞 글을 다시 읽어보면 한 가지 구멍이 있다. 바로 transition function T와 reward function R이 주어져 있다는 가정을 항상 한 것이다. 말 그대로 MDP는 next state의 action에 transition function(확률 함수)가 주어졌을 때 문제를 풀 수 있다.

Reinforcement Learning(이하 RL)은 아래와 같이 MDP의 formalization을 동일하게 따르지만 한가지 가정이 있다. 바로 모델에 해당하는 transition function과 reward function을 모른다는 가정이다. 즉, RL은 model에 해당하는 transition function과 reward function을 알아 내는 것이고, 이렇게 model을 찾는 기술을 Learning이라 분류한다.

• set of state s ∈ S

• set of actions (per state) A

• model T(s, a, s')

• reward function R(s, a, s')

• still looking for a policy π(s)

• New twist : don't know T or R

이런 특징이 있다보니, T, R을 알 고 있는 MDP는 next state에 대해 예상이 가능한 model이 이미 만들어 져 있고 단순히 VI(Value Iteration), PI(Policy Iteration)을 푸는 off-line planning이라 한다. 쉽게 생각하면 지도를 들고 목적지를 찾는 것과 같다.

반면 RL은 경험(sample 혹은 data)이 많이 주어지면 그 안에서 확률(T)과 보상(R)을 계산할 수 있는 함수를 만든다. 그러다 보니 초기에는 Reward가 낮은 행동을 하는 sample을 만들면서 점차 sample(경험)이 많아지면 노픙ㄴ 성능의 모델이 만들어진다 하여 on-line learning이라 부르기도 한다. 물론 on-line learning을 통해 model을 완성시킨 후, 완성된 모델을 활용해 MDP로 문제를 풀면 그건 off-line planning 문제로 넘어간다. 

처음에는 헷갈렸는데 용어정리를 지금 확실해 두어야한다. MDP는 model이 주어졌을 때 value나 policy를 찾는 planning 툴이고, RL은 model을 만들기 위한 learning 툴이다.

1. Model-Based Learning

MDP와 RL을 연계 시킬 수 있는 가장 쉬운 방법이 Model-Based Learning 이며 아래의 절차를 따른다.

• Step 1 : (s, a)로 부터 기인된 empirical(실험적) sample 들로부터 T, R을 배운다.

• Step 2 : VI 혹은 PI를 활용해 value나 policy를 도출한다.

아래 Model-based learning의 간단한 예제를 통해 좀 더 쉽게 이해할 수 있다.

위 예제에서 Episode란 말이 처음 나온다 Episode는 start state에서 terminal state까지 간 sequential policies를 의미한다. 위 예제는 4개의 Episode를 통해서 transition function과 reward function을 learning 한 경우를 보여준다.

Transition function은 확률 함수라고 했다. 즉, T(B, east, C)는 B에서 시작해 동쪽으로 이동하여 C로 이동할 확률이며, 4개 Episode모두 B에서는 항상 C로 이동했음으로 확률은 1.0 이다. 동일한 방법으로 T(C, east, D)는 4회중 3회 이동하였음으로 0.75가 된 것이다.

Reword function도 유사하게 구할 수 있다. R(B, east, C)는 B에서 동쪽으로 C로 갔을 때 얻는 reward 이며, 항상 -1 이었던 것을 확인할 수 있다. 마찬가지로 R(D, exit, x)는 D에서 exit로 갔을 때 +10점이 된 것을 Learning 하였다.

이렇게 T(s, a, s')과 R(s, a, s')을 학습하면 V*(s)는 VI를 통해, π*(s)는 PI를 통해 구할 수 있다.

2. Model-Free Learning

위 그림은 학생의 나이를 예측하는 간단한 사례이며, MDP, RL의 Model based learning, Model free learning을 한눈에 비교할 수 있게 해 준다.

• 만약 나이별로 확률분포(Model)를 알고 있다면 쉽게 평균 나이를 예측 할 수 있다. (MDP)

• 반면 확률분포를 모른다면, num of age를 전체 학생수로 나눠서 확률 분포를 만들 수 있다. (RL : Model based)

• 혹은 매번 sample(a)가 들어올 때 마다 평균을 내서 즉석으로 출력할 수도 있다. (RL : Model Free)

어느 정도 Model free learning에 대해 감이 온다. Model-free는 모델(T, R 함수)을 직접 구현하지 않고 sample이 들어올 때마다 Directly 결과를 출력하며, 통상 많은 sample을 경험할 수록 점점 성능이 좋은 쪽으로 수렴하는 advanced 한 learning 방식이다.

Passive vs. Active Reinforcement Learning

Model-free RL을 풀이하는 방법에는 Passive RL과 Active RL 두 가지 방법이 있다. RL이 value값을 계산하는데 action을 능동적으로 정하지 않고 구하는 것을 passive, action을 결정해 가면서 구하는 것을 active라 한다. 결론적으로 Value값을 학습하면 Passive RL, Q-value를 학습하면 Active RL이라 부른다. 먼저 Passive RL에 대해 알아보자.

Passive Reinforcement Learning

Passive RL은 Policy Evaluation 할 때 fixed policy π(s) 를 지정하고 value를 evaluation 하는데 MDP와 다른 점은 모델(T, R)이 없다는 것이다. 이런 경우 맞든 틀리든 π(s)에 따라 action을 해 sample을 생성하고, 이때 발생한 reward를 모아서 평균을 내는 방식으로 value를 구할 수 있는데, 이런 방식을 Direct Evaluation이라 한다. 쉬운 예제로 다시 알아보자.

• B : 오른쪽으로 출발한 경우의 평균은 8점 (Ep1, Ep2)
• C : D로 나가서 9점 얻은 경우 3번, A로가서 -11점을 얻은 경우가 1번 → 평균 = 4점
• E : 위쪽으로 출발해 8점(Ep.3), -12점(Ep.4)을 얻엇음으로 평균 = 2

위 결과를 앞서 설명한 방법으로 풀어서 살펴보자.

C에서 취할 수 있는 action 중 임의로 우측으로 가는 action (Ep.1)을 π(s)라 하면 이때 V(s)=9이다. (Ep.2)도  π(s) = 우측 이며 V(s) = 9,  (Ep.3)도 V(s) = 9, (Ep.4)는 V(s)=-11 이다. 그럼 앞에서 설명한 대로 이 value(reward)들을 기억해두었다가 평균을 내면 C state에서의 가치(Value 혹은 Reward) = 4 가 도출된다.

확실히 ① 직관적으로 이해할 수 있어 쉽고 ② T, R을 구할 필요가 없으며 ③ sample만 많다면 정답을 찾을 수 있는 장점이 있다.

하지만 ① 각 노드간의 연결성을 전혀 고려하지 않고 ② 각 state를 각각 독립적으로 학습해야 된다는 점에서 합리적이지 않다. 이상하지않은가? B와 E state는 next state의 선택지가 모두 C 뿐이지만 B와 E의 Value값은 다르다. 물론 다양한 sample이 많이 공급 된다면 유사한 값으로 수렴하겠지만 이 역시도 시간이 많이 걸리는 단점이 있다.

다행히 위의 Directly Evaluation의 단점을 보완하기위해, Bellman Equation이라는 훌륭하 툴이 있는데 이것을 좀 활용해보자는 생각을 할 수 있다. 

물론 위의 Original Bellman Equation으로는 풀 수 없다. 왜냐하면 T, R을 모른다고 가정했기 때문이다. 그럼 "T, R을 모른상태에서 Value를 구할 수 없을까?" 라는 것이 Key Question이다. 이 질문은 마치 "weight의 정보 없이 weighted average를 구할 수 없을까?" 라는 질문과 맥락이 비슷하다. 왜냐하면 Σ(확률)*(값) = (확률 분포를 반영한 평균) 과 같은 의미고, 실시간으로 sample이 들어올 때 weighted average를 실시간으로 구하는 것과 유사한 문제이기 때문이다.

그 해답은 Sample-Based Policy Evaluation 이라 불리는 방법이다.

위 식에 Direct evaluation을 대응시켜 보자. 우리는 ① B를 start state로 가지는 Episode Reward의 ② 평균값을 V^π(s=B)에 할당하였다. 이 과정을 Bellman equation에 투영시키면

1. (R(s, π(s), s') + γV^πk(s')) 가 sample의 value 에 해당하고
2. ΣT(s, π(s), s') 이 부분이 sample의 갯수로 평균내는 역할을 한다.

위 투영 결과를 반영하여 Bellman equation을 다시 쓰면 아래와 같다.

위 식을 이용하면 n개 sample들의 평균값으로 V^πk+1(s) (= action π를 따라왔다고 가정했을 때 k+1 step의 value값) 을 구할 수 있다.

위 전개식을 incremental 하게 평균을 구할 수 있게 만든 것이 Temporal Difference Learning 이라고 한다. 즉, 모두 모아서 평균 내는 것이 아니라 매번 sample이 들어올 때 마다 평균을 낼 수 있게 한 것이다. 

앞서 잠깐 언급했는데 이 문제는 running(incremental) average를 구하는 문제와 유사하다고 했었다. 실제로 수학적으로 running average를 구하는 방법이 Exponential Moving Average라는 이름으로 아래의 수식이 존재한다. 수식의 α는 learning rate라 불리는 파라미터이다. 0 < α < 1까지의 값으로 1에 가까울 수록 새로운 값에 가중치를 더 주고, 0에 가까울 수록 기존의 평균값에 converge하는 특징을 가지게 한다. 

이 특성을 Temporal Difference Learning에서 응용하여 아래와 같은 공식을 도출 할 수 있다.

혹시 Neural network를 공부하면서 gradient decent 알고리즘을 공부한 사람이면 이 수식을 이해하는데 크게 어렵지 않을 것이다. machine learning 에서 weight를 update하는 원리와 정확히 같다.

왜 Temporal Difference Learning 일까? 이유는 바로 마지막 식 중 (sample - V^π(s))항의 의미에 있다. action 을 취해서 나온 sample(일종의 미래)과 직전의 value 값의 차가 바로 Temporal(일시적인) Difference 이기 때문이다. 그럼 아래 예제를 마지막으로 Passive RL 학습을 마무리하자.

• 첫 번째 action에서 (1-0.5)(0) + (0.5)(-2 + 1*0) 으로 -1이 도출된다. 

• 두 번째 action에서 C의 직전값인 V^π(s) = 0이고, V^π(s') = 8임으로 3이 계산된다.

정리하면 TD Value Learning은 Policy evaluation과 Bellman equation을 활용해 value를 구하는데 이 때 running sample averages 원리를 활용한 학습법이다.

그런데, 우리가 정말 궁금한 것은 value가 아니라 policy일 경우가 매우 많다. 만약 우리가 policy가 궁금할 경우 value를 구하고, 그 value로 다시 Q-value를 구한다음 argmax 함수를 활용해야 한다. 차라리 value를 구하지말고 Q value를 바로 구하면 더 좋지 않을까? 하는 Idea에서 나온 것이 바로 Active RL 이다. Active RL로 Q를 학습하면 action은 Q에서 선택만 하면 되기 때문에 훨씬 policy를 구하기 수월해진다.

Active Reinforcement Learning

Q-value를 학습한다는 것은 우리가 action에 관심이 있어서 action을 결정해 나가면서 학습한다는 의미다. (여전히 T, R은 모른다.) Passive RL과 결정적으로 다른 것은 π를 고정하는 것이아니라 active하게 선택하고, 그 선택의 기로에서 exploration할 것인지 exploitation할 것인지 learner가 선택하게 한다.

앞서 배운 Value Iteration을 Q버전으로 변형시켜 Q-Value Iteration으로 만들어 보자.

위 식은 V를 대상으로 한 Value Iteration을 위한 Bellman Equation이다. V는 어떤 action을 취해야 할 지 모르기 때문에 max Σ 함수를 사용한다. 하지만 Q는 입력 파라미터에 이미 'a'가 존재하기 때문에 1개의 단일 값을 갖는다. 따라서 모든 action에 대해 Q를 모두 구해야하는 단점이 있지만, max 함수가 필요없어진다. 그리고 Vk(s')은 정의에 따라 Qk(s', a') 들 중 가장 큰 value를 가지는 값임으로 아래와 같이 변환할 수 있다.

이제 이 식을 T와 R 없이 풀어내면 된다. 그리고 그 방법은 Passive RL과 마찬가지로 Temporal Difference Learning을 활용하는 것이고, 이 학습법을 굳이 Temporal Difference Q-Value Learning이라 부르지 않고 Q-Learning 이라 부른다.

여담이지, 지금은 Bellman equation을 활용해서 Q(s, a)를 학습하는 방법을 소개하였지만, 이 Q값을 딥러닝으로 학습하면 그 유명한 Deep-Q Learning이 된다. (알파고가 다음 수를 예측하기 위해서 선택한 알고리즘)

Approximate Q-Learning

Q-learning은 훈련데이터(sample)에서 나오는 모든 상황에 optimal 한 해답을 찾는 것이다. 그런데 실제 환경에서는 훈련데이터와 다른 양상의 예기치 못한 상황이 많이 발생하는게 대부분이다. 극단적으로 표현하면 Q-Learning은 훈련된 상황에만 최적화된, 혹은 Overfitting된 모델을 만드는 경향이 있다. 그래서 나온 개념이 Approximate Q-Learning이다.

Approximate Q-Learning은 Q-Learning이 학습한 모델이 실제 상황에서도 잘 동작할 수 있게 일반화 시킨 것이다. 일반화라는 것은 비유를 하자만 섬세하게 설계된 모델을 뭉퉁하게 만든다(?)의 느낌이다. 

예를 들어 Y를 값을 예측하는 문제가 있다고 하자. 위 그래프 중 어떤 모델이 더 잘 맞는 모델일까? 우측 모델의 경우 훈련 데이터에 대해 100% 만족시키는 성능을 보인다. 그 만큼 모델이 섬세하고 복잡하게 개발됐을 것이다. 그런데 이 모델이 과연 현실에서도 잘 동작할까? 실제로 저런 양상을 보이는 것이 현실이라면 잘 맞겠지만 일반적으로는 좌측의 모델이 더욱 합리적이다고 할 수 있다. 이렇게 우측의 그래프처럼 복잡한 모델을 뭉퉁(?)그려서 좌측의 모델로 만들어서 실제 환경에서 잘 맞게 하는 방법을 일반화 라고 한다. 

위 개념은 사실 Overfitting/Underfitting에 대한 설명이고, Q-Learning이 overfitting 된 모델이란 뜻은 아니다. 잠시 일반화(Generalization)의 개념에 대한 보충 설명정도로 이해하자.

서론이 길었지만, Q-Learning이 모든 state의 optimal action을 배우는 다소 과한 모델링 기법이라면, sample과 다른 양상의 데이터가 입력되어도 잘 맞을 수 있도록 Q-Learning을 일반화 시킨 것이 Approximate Q-Learning 이라 한다.

위 그림은 Q-Learning이 일반화 되어야 할 필요성을 보여주는 사례이다. 

Q-Learning은 모든 sample state를 배운다고 했다. 그래서 가장 왼쪽에 있는 state를 'BAD state'라 학습했다고 가정하자. 그럼 2번째 state도 'BAD'라 예측할 것인가? 같은 위치이지만 먹이가 1개 없는 (우측 상단) 3번째 state는? 희망적으로 Q-Learning으로 모델을 배울 때 2, 3번째 경우의 sample이 있었다면 가능하겠지만, 현실적으로 가능한 모든 상황의 sample을 확보해서 학습시키는 것은 어렵다.

Approximate Q-Learning의 핵심 아이디어는, state과 action을 통채로 배워 all q-value를 table형태로 기억하는 것이 아니라, 중요한 특징만 뽑아서 Q값을 일종의 함수로 표현하는 것이다. (참고로 Q-Learning처럼 모든 상황의 해답을 외우고 있는 기법을 Note Learning이라 부른다. Approximate Q-Learning은 해답을 외우는게 아니라 원리를 배운다고 생각하면 이해가 쉽다.)

위 예제를 예로들면, 

• ghost와 packman간의 거리 : (Xpackman, Ypackman) - (Xghost, Yghost)

• packman과 dot(먹이)간의 거리 : (Xpacman, Ypacman) - (Xdot, Ydot)

• ghost의 수 : 0, 1, ... N

이런 것들을 특징으로 아래와 같이 현재 state를 표현할 수 있는 weighted sum함수로 일반화 하는 것이다.

위와 같은 일반화의 장점은 state를 요약해 표현함으로써 문제를 쉽게 만든다는 장점이 있지만, trade-off state를 대략적으로(approximately) 표현했기 때문에 모델의 정확도를 떨어트릴 수 있다. 특히 정확한 feature를 뽑지 못하면 정확도의 하락은 더욱 커질 것이다.

여하튼, 위와 같이 Q를 feature들로 표현한다면 아래의 기존 Q-Learning 학습 원리가

아래와 같이 각 feature의 weight를 학습하는 수식으로 변경된다.

결국 weight를 정확하게 학습할 수록 Q에 대해 더욱 정확히 인지할 수 있다는 뜻이다. 이제는 복잡하게 Bellman Equation을 재귀적으로 풀며 Q를 도출하는 것이 아니라 feature들로 이루어진 식으로 weight를 학습해 approximate Q를 도출할 수 있게 되었다. (사실 대중적으로 사용하는 Q-learning은 대부분 Approximate Q-Learning 이다.)

[요약]

• Markov Decision Process의 모델은 Transition function (확률)과 Reward function (보상) 이다.  모델을 알고 있다면 MDP는 off-line planning 을 수행할 수 있는 툴이다.
• Reinforce Learning은 MDP 모델(T, R)이 주어지지 않았을 때, sample로부터 모델을 구할 수 있는 on-line learning 기술이다.
• sample을 많이 모아서 각 action의 평균을 취하면 확률분포를 만들 수 있다. 이 확률분포를 모델로 쓰는 방법은 Model-based Learning 이다.
• 반면 sample이 들어올 때 마다 Temporal Difference Learning과 Exponential Moving Average의 원리를 통해 실시간으로 Value를 예측하는 Model-free Learning이 더 진화된 학습 방법이다.
• TD Learning으로 Value를 학습하는 것이 아니라 Q-value를 학습하면 Q-learning이다.
• Q-learning은 모든 sample state로 모델을 생성하기 때문에 sample에만 특화된 모델이 될 수 있다. 이를 일반화 하는 것이 Approximate Q-learning이다. Approximate Q-learning은 state의 중요 feature들로 이루어진 weight sum함수가 Q를 대신하고, weight를 잘 학습하는 것이 목표다.