2022. 6. 10. 17:29ㆍMajor`/인공지능
Supervised Learning은 인간이 "Labeled Data"를 줌으로써 Agent는 Learning을 통해서 주어진 훈련 데이터를 모두 만족하는 가설함수를 찾아낸다
Unsupervised Learning은 인간이 "input Data"만을 줌으로써 Agent는 Learning을 통해서 주어진 input data들을 "Clustering"한다
Reinforcement Learning은 이전의 Learning과는 완전히 다른 방식이다
왜냐하면 아예 훈련 데이터를 주지 않기 때문이다
그러면 어떻게 Agent는 Learning을 할까??
>> Agent는 아무것도 모르는채로 "환경"에 투입되어서 경험을 통해서 Learning을 한다
일단 Agent가 환경에 놓여지면 1) 먼저 state를 인식하고, 2) 그에 걸맞은 행동을 하게 된다
당연한 말로 "행동"을 하게되면 "환경"은 반드시 변한다
여기서 "강화학습"에서 가장 중요한 개념인 "reward"가 나오게 된다
Agent가 state를 인식하고 행동을 하게 되면 인간은 Agent에게 행동에 따른 "reward"를 제공해준다
Agent는 계속된 학습을 통해서 "reward"를 받게되면 "어떤 상태에서는 어떤 행동을 해야 하는구나"라는 Policy를 깨닫게 된다
>> 강화학습은 결국 Optimal Policy를 알아내는 것이 학습의 목표이다
- Optimal Policy에 의해서 행동을 수행하게 되면 Agent는 "MAX_REWARD"를 얻게 된다
MDP : Markov Decision Process
MDP는 강화학습 모델링의 정형화된 모델이다
1. state를 인식하고 그에 따른 행동을 결정하고 수행
→ 환경이 변한다
2. 이전 행동에 대한 reward 받기 & 변화된 state를 인식하고 그에 따른 행동을 결정하고 수행
→ 환경이 변한다
3. 이전 행동에 대한 reward 받기 & 변화된 state를 인식하고 그에 따른 행동을 결정하고 수행
→ 환경이 변한다
4. 이전 행동에 대한 reward 받기 & 변화된 state를 인식하고 그에 따른 행동을 결정하고 수행
→ 환경이 변한다
....
....
강화학습에서는 이러한 과정이 반복된다
결국 시간(T)에서 어떤 행동을 결정할지는 (1 ~ T-1)때 어떤 행동을 결정한지 : Sequence에 의해 영향을 받게 된다
- 과거에 어떤 식으로 행동을 결정해왔는지에 따라 현재 행동 결정에 영향을 준다
하지만 과거의 모든 Sequence를 고려하는게 너무 오래걸린다고 생각하여서 Markov는 다음과 같은 가정을 하나 세웠다
시간(T)에서의 state는 시간(T-1)때의 state에 의해서만 영향을 받는다
MDP는 <S, A, P, R, λ> : tuple로 표현이 된다
"S"
S는 환경의 가능한 모든 상태들의 집합을 의미한다
"A"
A는 Agent가 수행 가능한 행동들의 집합을 의미한다
"P"
P는 "State Transition Probability Matrix" : 상태 전이 확률 매트릭스를 의미한다
P(s, a, s`)이란 "상태 s에서 행동 a를 하게 되면 상태 s`로 전이될 확률"이다
이러한 P(s, a, s`)은 Nondeterministic State Transition Function이다
만약 P(s, a) = s` : 상태와 행동에 대해서 다음 상태가 정해져 있다면 Deterministic State Transition Function이라고 한다
"R"
R(s, a)는 "상태 s에서 행동 a를 하게되면 얻게 되는 Reward"를 의미한다
"λ"
λ는 "Discount Factor"이고 현재 주어진 보상에 비해 미래에 받게될 보상은 현재에 영향을 덜 줘야 하고, Reward를 수렴시켜야 하기 때문에 [0, 1]범위 안에 존재한다
결국 Agent가 배워야하는 것은 Policy이고 Policy는 2가지로 분류될 수 있다
Deterministic Policy
Deterministic은 어떤 상태 s에서 수행될 행동 a가 확실하게 결정되는 Policy이다
Nondeterministic(Stochastic) Policy
Nondeterministic은 어떤 상태 s에서 각 행동들이 수행될 "확률"이 결정되는 정책이다
Value Functions
시간(T)에서부터 Agent가 받게될 Reward의 합을 G(t)라고 하자
"가치란" {가치가 있다/없다 or 가치가 높다/낮다}로 평가할 수 있다
그리고 "가치"는 {중요도 or 바람직함}의 기준으로도 표현할 수 있다
상태 가치 함수 (State Value Function) : V
상태 가치 함수란 말그대로 "그 상태가 얼마나 가치가 있는 상태인지"를 평가하는 함수이다
파라미터로 들어간 s는 "가치를 평가받을 상태"를 의미한다
아까도 말했듯이 강화학습의 목표는 "Optimal Policy"를 찾는 것이다
위의 식에서 Policy에는 어떠한 Policy도 들어갈 수 있다
그리고 λ는 결국 Value는 수렴이 되어야 하기 때문에 필요한 Discount Factor이다
하지만 최종적으로 학습이 마무리된 시점에서 위의 식에서의 Policy는 "Optimal Policy"가 된다
행동 가치 함수 (Action Value Function) : Q
행동 가치 함수란 말그대로 "그 행동이 얼마나 가치가 있는 행동"인지를 평가하는 함수이다
근데 상태 가치 함수와 달리 "행동 가치 함수"는 행동만 파라미터로 넘겨준다고 해도 아무런 의미가 없다
>> 행동은 어떤 상태에서 수행하느냐에 따라 그 가치가 달라지기 때문이다
따라서 행동 가치함수의 파라미터에는 {상태 - 행동}이 쌍으로 들어가게 된다
QPolicy(s, a)는 다음과 같은 과정으로 수행된다
1. 상태 s에 대해서 행동 a 수행
2. 이후에는 Policy에 의해서 행동이 결정되고 결정된 행동을 수행한다
Bellman Equation
위에 식에서 V(s)와 Q(s, a)간에 상관관계가 있는 것처럼 보인다
V에 Q가 섞여있고, Q에 V가 섞여있기 때문에 이 식들을 일관적으로 바꿔보자
Q Learning
Q Learning은 강화학습의 가장 기초적이고 중요한 Learning 방법이다
Q Learning은 이름 그대로 Learning을 통해서 Q를 update한다는 것이다
그런데 위에서 "강화학습의 목표"는 Optimal Policy를 배운다고 했는데 Q Learning은 약간 목표에서 벗어난 것처럼 보인다
하지만 Q Learning이 곧 Optimal Policy를 배우는 것과 동일하다
"행동 가치 함수"라는것은 어떤 상태에서 어떤 행동을 하는게 가장 바람직한지에 관한 것이다
따라서 Q를 학습함으로써 특정 상태에 대한 최적의 행동을 구하게 되면 어차피 Optimal Policy는 자동적으로 구해지는 것이다
따라서 Q Learning은 간접적으로 Optimal Policy를 배우는 것과 동일하다고 볼 수 있다
Example)
state : s1에서 action : right를 선택했다고 하자
그러면 우리가 Learning을 하는 것은 Q(s1, right)이다
이제 Q(s1, right)를 update해보자
s1에서 action:right를 하게 되면 다음 상태는 s` = s2가 된다
따라서 s2에서 가능한 행동들의 reward중 max값을 고르고 거기에 R(s1, right)를 더한 것이 New_Q(s1, right)가 된다
여기서 또 하나 봐야할것은 현재 {state, action}에 대해서 다음 상태가 정해져있기 때문에 Deterministic이라고 볼 수 있다
따라서 Q(s1, right)는 위와 같이 update된다
Q Tables
Q Learning에서는 {모든 state - 모든 action}쌍을 전부 Table 자료구조에 저장해야 한다
초기에는 당연히 학습이 이루어지지 않았기 때문에 모든 Q(s, a)쌍을 0으로 초기화한 상태에서 학습을 시작한다
그리고 이후에는 학습이 진행됨에 따라 Q(s, a)가 계속 update가 되고 어느 시점에서는 결국 수렴을 한다
모든 Q(s, a)가 수렴이 된다면 Q Learning이 마무리가 된다
이렇게 만들어진 Q-Table이 바로 Optimal Policy이다
이러한 예제에서 현재 자동차가 있는 곳에서 Q(s, a)가 가장 큰 action은 "right"이므로 right로 갔다고 하자
>> Q(s5, right)를 update하자
그러면 "학습 도중에 action 선택"과 "학습 완료 후 action 선택"은 동일한 문제일까 별개의 문제일까
>> 당연히 별개의 문제이다
왜냐하면 학습 도중에 action을 선택한다는 것은 "아직 수렴이 안된 불안정한 Q값"을 판단해서 action을 고르는 것이고, 학습 완료 후 action을 선택한다는 것은 "학습이 완료된 :: 수렴된 Q값"을 판단해서 action을 고르는 것이기 때문에 완전 별개의 문제이다
학습 도중에 action선택하는 것을 학습이 완료된 것처럼 가장 큰 reward인 action을 선택하면 loop에 빠질 수 있다
그리고 학습 도중에 action을 선택할 때는 다음 2가지 상황을 직면할 수 있다
Exploitation
Exploitation은 경험한것만 계속 경험하는 것이다
이러한 상황이 왜 발생하냐면 어쨋든 Local적으로는 reward가 가장 큰 행동을 수행하는 것이 좋다고 생각하기 때문이다
따라서 이렇게 경험한 것만 계속 경험하면 모든 Q를 수렴시킬 수 없고 특정 Q값들만 update loop를 돌 수 있다
Exploration
Exploration은 Exploitation과 다르게 경험하지 않은 것도 경험하는 "탐험"을 하는 것이다
Exploration 1) 확률 기반 선택 방법
이 방법은 Q값이 높을수록 선택될 확률이 높아진다
Exploration 2) t 임의 선택 방법
이 방법은 아예 t / 1-t로 나뉘게 된다
t 확률은 완전 Random Selection으로 행동을 고른다
1-t 확률은 그냥 Q(s, a)가 최대인 행동을 선택한다
- 1-t 확률의 경우 Exploitation과 동일하다
Convergence of Q Learning
Q Learning을 통해서 Q값이 수렴되려면 다음 3가지 조건이 만족되어야 한다
1. 시스템이 MDP를 만족해야 한다
2. Reward Value가 발산하지 않도록 적당한 bound를 설정해주자
3. 모든 {state - action}쌍에 대해서 Q Tables Entry를 거의 무한에 가깝게 고쳐야 한다
- 거의 무한에 가깝게 고치면 시간이 상상이상으로 많이 걸릴 것이다
Off Policy vs On-Policy <RL>
Off-Policy RL
Q Learning이 대표적인 Off-Policy RL Algorithm이다
Off-Policy는 "current Policy"와는 전혀 관계없이 어떤 Policy를 써도 상관없으니까 MAX_REWARD를 위한 Optimal Policy를 찾는 것이다
On-Policy RL
대표적인 On-Policy RL Algorithm은 SARSA이다
On에서는 일단 시작전에 Policy가 결정되기 때문에 "current Policy"를 사용해서 행동을 수행하면서 Learning한다
Value Function Approximation
Q Learning은 Q Table을 이용해서 Learning을 한다
근데 현실세계에서는 사실 Q Table을 사용해서 Learning을 할 수가 없다
왜냐하면 현실세계는 유한집합의 {state/action}이 아니라 거의 무한 집합의 {state/action}이기 때문이다
무한 집합이면 사실상 Q Table을 정의할 수가 없고 정의한다고 해도 무한시간/무한 메모리를 사용하게 된다
>> Q Table대신 Neural Network를 활용하자
Neural Network는 전체가 아닌 일부의 {state/action}쌍만으로도 전체 {state/action}의 Q(state, action)을 예측할 수 있게 된다
여기서 실제로 학습할 경우 action도 주지않고 state만 줌으로써 Learning을 한다
DQN : Deep Q-Network
이전에 Supervised에서는 명확한 output이 존재하기 때문에 Network를 학습시킬 때는 Labeled Data를 부여함으로써 학습한다
하지만 강화학습은 학습 데이터 자체를 주지 않는데 어떻게 Network를 학습할까에 대한 고민에 빠지게 된다
그렇다고해서 인간이 Q(s, a)를 부여해줄 수는 없다.
- state에 대한 행동 Reward를 미리 알 수 없기 때문
>> 따라서 "손실함수"를 정의해보자
결국 Q_Target(s, a)와 Q_Predict(s, a)간의 손실을 최소로 만드는 것이 신경망 학습의 목표가 될 것이다
이전에 Q Learning에서 VFA(Value Function Approximation)을 사용하는 것은 Weight Update 과정에서 샘플들의 상관관계와, Non-Stationary Target으로 인해 Q(s, a)가 수렴하지 않고 발산할 가능성이 존재한다
따라서 이러한 문제를 DQN에서는 {Experience Replay & Fixed Q Targets}로 해결한다
Experience Replay
Experience Replay Buffer에는 DQN의 학습 과정에서 매 Step마다 주어지는 {State / Action / Q(state, action)}값들이 저장된다
이렇게 저장된 경험을 사용해서 Network를 학습시킨다
여기서는 "miniBatch"를 활용해서 update한다
일단 정해진 개수만큼 경험이 저장되었다면 여기서 "Random Sampling"을 통해서 샘플링된 데이터들을 활용해서 신경망을 학습시킨다
{miniBatch + Random-Sampling}을 통해서 독립성을 확보할 수 있고, Q(s, a)가 수렴이 될 가능성이 높아진다
- 이를 무시하고 경험 데이터를 그대로 바로 써버린다면 연속된 경험 데이터들 간의 "과도한 상호 관계성"이 생기게 된다
1. 동일 경험을 weight update에 여러번 재사용 가능
2. 연속된 입력 상태들 간의 상호 관계성 배제
Fixed Q Targets
Loss를 줄이기 위해서 W를 수정하면 Q_Target(s, a)와 Q_Predict(s, a;W)가 동시에 변경되기 때문에 안정적인 Loss 축소 & Q Network 학습이 어려워진다
>> 따라서 Q-Network를 Q_Predict(s, a;W) & Q_Target(s, a;W`) :: 2개로 분리한다
Target Network의 갱신 주기를 Predict(Local) Network의 주기보다 더 느리게 설정함으로써 안정적인 Loss 축소 & Q Network 학습이 가능해진다
DQN의 경우, Q_Predict : Q_Target = 4 : 1 주기로 update한다
Policy Gradient RL
이전까지는 Q-Learning / DQN을 통해서 "Value-Based RL"을 살펴보았다
Value-Based RL은 결국 Optimal Policy를 우회해서 찾는 방식이다
여기서는 Optimal Policy를 직접 찾는 "Policy-Based RL"을 살펴보자
Policy-Based RL은 Policy Network를 통해서 {state}를 input으로 주게되면 그에 따른 output으로 "action"을 도출해낸다
여기서는 state를 input으로 주었을 때 그 state에서 output으로 도출된 action이 과연 가장 최적일까라는 고민에 빠지게 된다
Supervised Learning에서는 명확한 output이 있고 {예측 - 정답}간의 오차를 줄이기 위해서 "기울기 하강 규칙"을 사용해서 weight를 update하였다
Policy-Based RL에서는 명확한 output이 존재하지 않고, 목적은 "reward를 최대로 하는 것"이기 때문에 "기울기 상승 규칙"을 사용해서 Network상의 weight를 update한다
P-RL은 큰 상태/행동 공간에 적용할 수 있지만, 상대적으로 데이터 효율성은 낮은 편이다
