CS231n 14강 요약
Reinforcement Learning에 대해서 알아보자!
0. Today’s Goal
- What is Reinforcement Learning?
- Markov Decision Processes
- Q - Learning
- Policy Gradients
1. 강의 및 강의 자료
강의를 들어볼 수 있는 링크와 강의 자료를 pdf형식으로 준비했다.
한글 자막이 필요하신 분은 다음의 링크를 확인해주세요. :)
- 한글 자막을 첨부하고 싶으면 여기를 눌러주세요.
2. What is Reinforcement Learning?
Reinforcement Learning(강화 학습)이란 무엇일까?
Machine Learning의 한 범주로써 어떤 환경 안에서 정의된 에이전트가 현재의 상태를 인식하여, 선택 가능한 행동들 중 보상을 최대화하는 행동 혹은 행동 순서를 선택하는 방법이다. (by Wikipedia)
한 장의 슬라이드로 요약하면 다음과 같다.
우선 용어부터 정리를 해보면,
Agent란 Environment에서 Action을 취할 수 있는 물체를 말한다. Agnet는 어떠한 Action에 의해 Reward를 최대로 받는 것이 목적이다.
Environment란 Agent와 상호작용을 하는 것으로 Agent에게 적절한 state를 부여한다.
순서는 다음과 같다.
- Environmet로 부터 Agent가 State(상태)를 부여받는다.
- 상태를 받은 Agent가 어떠한 Action을 취한다.
- 그 Action에 대해 Agent는 보상을 받는다.
- 그리고 다음 State를 부여받게 된다.
강화 학습을 사용하여 다음과 같은 문제들을 풀 수 있다.
- Cart-Pole Problem (Pole을 Cart위에서 균형을 잡도록 하기)
- Robot Locomotion (로봇을 앞으로 가도록 하기)
- Atari Games (게임을 가장 높은 점수로 끝내기)
- Go (바둑 게임 이기기)
3. Markov Decision Processes
Markov Decision Processes는 강화 학습 방법을 수식화 하는 것을 말한다.
Markov Property는 현재 상태로 전체 상태를 나타내는 것을 말한다.
이러한 문자들에 의해서 정의가 되는데
- S는 가능한 상태 집합을 의미,
- A는 가능한 액션 집합을 의미,
- R은 (상태, 액션)의 쌍이 주어졌을 때 보상에 대한 분포
- P는 (상태, 액션)의 쌍이 주어졌을 때 다음 상태에 대한 분포 (전이 확률)
- R은 보상을 받는 시간에 대해서 얼마나 중요하게 생각하는지를 의미한다.
강화 학습을 수식으로 풀어쓰게 되면
결국 누적 보상을 최대화 하는 $\pi^*$를 찾는 것을 목표로 하게 된다.
예를 들어 한번 살펴보자..
우리가 *쪽으로 가도록 하는 길찾기 문제를 푼다고 할 때,
최적의 정책 $\pi$가 존재한다면 길을 훨씬 수월하게 찾을 것이다.
$\pi$는 우리가 어느 위치에 있더라도 보상을 최대화 할 수 있는
(여기서는 목적지에 가장 빨리 도달할 수 있는) 방법을 알려준다.
보상을 최대화 할 수 있는 방법은
미래 내가 받을 보상들의 합이 최대가 되도록 하면 된다!
수식으로 표현해보면 다음과 같다.
수식을 잘은 모르지만 대략적으로 미래 보상들의 합에 대한 기댓값을
최대화하는 식이라 생각이 든다.
우리가 사용할 정책을 살펴보기 전에
먼저 정의해야 할 몇 가지에 대해서 이야기를 해보자.
- Value function : 어떤 상태 S와 정책 $\pi$가 주어졌을 때,
계산되는 누적 보상의 기댓값
Value function의 수식은 다음과 같다.
- Q-Value funtion : 상태 s에서 어떤 행동을 해야 가장 좋은지 알려주는 함수 - (상태, 행동) 조합이 얼마나 많은 보상을 받을 수 있는가?
Q-Value funtion의 수식은 다음과 같다.
다음으로는 강화학습에서 중요한 요소 중 하나인
Bellman equation에 대해서 이야기 해보자.
Bellman equation이란 현재 state의 value function과 next state의 value function 사이의 관계식을 나타낸 것이다.
우선 어떤 상태 s가 주어졌을 때,
Q-Value funtion에 의해서 $Q^*$를 알게 되었다고 가정하자.
$Q^*$는 어떤 행동을 취했을 때 미래에 받을 보상의 최대치 이기 때문에
이것을 알게 되면 다음 상태 s’에서도
우리는 최적의 경로를 도출 할 수 있게 된다.
직관적으로 생각해보면 우리는 $Q^*$ 덕분에 어느 상태이던 간에 최적의 보상을 받을 경로를 알기 때문에 우리는 s'에서도 최상의 행동을 취할 수 있다.
그렇다면 최적의 정책은 어떻게 구할 수 있을까?
그에 대한 한 가지 방법은 바로 Value iteration algorithm이다.
반복적인 update를 통해서 벨만 방정식을 이용하여
점차적으로 $Q^*$를 최적화 시키는 방법을 말한다.
수학적으로 볼 때 t가 $\infty$ 일 때, $Q$는 최적의 함수로 수렴하게 된다.
하지만 여기에 문제점이 하나 있는데 바로 Scaleable하지 않다는 것이다.
왜나하면 모든 Q(s,a)에 대해서 계산을 진행해야 하기때문에
직관적으로 보더라도 계산량이 어마어마 하다는 것을 알 수 있다.
해결책으로는 Q(s,a)를 계산 가능하도록 근사시키는 방법이 있다!
이러한 복잡한 함수를 근사화 시킬 때에는 Neural Network를 이용하여
근사화를 시킨다. (앞선 강의에서도 그렇게 언급했던 기억이 있다.)
4. Q - Learning
Neural Network를 이용하여 Q(s,a)를 어떻게 근사 시키는지 알아보자!
이러한 방법으로 근사를 시키는 것을 Deep Q - Learning이라고 한다.
위 슬라이드에서 파란색 화살표로 표시된 Parameter는
Neural Network의 weights들과 관련된 parameter $\theta$이다.
현재 Action-value funtion을 추정하는데 사용한 Q - funtion은
Bellman equation을 만족하도록 만들어야 한다.
손실함수(Loss function)는 Q(s,a)가 목적함수($y_i$)랑 얼마나 차이가 나는지 측정한다.
또한 $y_i$는 Bellman equation을 만족하는 정답 방정식이라고 생각하면 된다.
Backward Pass 과정에서는 Loss값에 대하여 $\theta$를 계속 update를 진행한다.
그렇다면 예시를 들어 Q - Learning에 대해서 살펴보자.
앞서 이야기했던 Atrari Game에 대해서 한 번 살펴보자.
- 목표는 이 게임에서 가장 높은 점수를 얻는 것이다.
- 상태는 게임의 픽셀들이 모두 사용되었다.
- 행동은 게임의 방향키를 의미한다.
- 보상은 게임에서 받는 점수이다.
Q - network의 Architecture은 다음과 같다.
입력으로는 여러 전처리 과정을 거쳐 실제 게임 화면을 84 * 84 크기로 만든 다음
4프레임 정도를 누적시켜 넣어준다.
출력은 입력이 들어왔을 때, 각 행동의 Q-value 값이다.
여기서는 위, 아래, 왼쪽, 오른쪽 4방향으로 갈 수 있으므로
출력이 총 4개의 벡터로 출력된다.
이런 네트워크 구조의 장점은 한 번의 forward pass만으로 모든 함수에 대한 Q - value 값을 계산할 수 있다는 것이다.
Q - network를 Training 시킬 때는
Experience Replay에 대해서 알아야 한다.
Experience Replay에서는 Q - network에서 발생할 수 있는
문제들에 대해서 다룬다.
Q - network는 연속적인 시간의 샘플들을 이용하여
Training 시킬 경우 비효율적인데,
그 이유는 연속적인 시간의 샘플들의 경우 모든 샘플들이 서로
상관관계(Correlation)을 가지기 때문이다.
또한 현재 Q - network의 파라미터를 생각해보면,
네트워크가 우리가 어떠한 행동을 해야하는지 정책을 결정한다는 것은
우리가 다음 샘플들도 어떤 것이 나왔으면 좋겠다라고 결정하는 의미가 된다.
우리는 이러한 두 가지 문제점을 해결하는 방법으로
Experience Replay를 사용한다.
Experience Replay에 대해 설명해보자면
Replay Memory라는 테이블을 만들고,
테이블은 (상태, 행동, 보상, 다음행동)으로 구성되어 있다.
그리고 게임을 플레이하면서 이 테이블을 지속적으로 update 시킨다.
따라서 연속적인 시간의 샘플을 사용하는 대신,
Replay Memory에서 임의로 샘플링된 샘플을 이용한다.
이런 방법을 이용하는 또 하나의 이유는 가중치 값을 update하는데
여러번 갱신을 시킬 수 있기 때문이다.
Deep Q - Learning의 pseudo code를 살펴보면 다음과 같다.
5. Policy Gradients
Q - Learning에도 문제점이 존재하는데,
그건 바로 function이 너무나도 복잡하다는 것이다!
모든 state에 대해서 Q - value 값이 존재해야 하는데,
앞서 봤던 예시의 같은 경우 4방향으로 비교적 state의 갯수가 적었지만,
예를 들어 로봇이 어떤 물체를 집는다는 것을 강화학습으로 풀 경우,
state의 차원은 매우 높아진다!
따라서 새로운 방법이 제시되었는데,
상태에 따른 Q - value값들을 학습시키는 것이 아니라 정책(Policy) 자체를 학습시키는 방법이 제시되었다.
그 방법을 Policy Gradients라고 부른다.
$J(\theta)$는 미래에 받을 보상을 누적으로 하여 기댓값을 나타낸 함수이다.
여기서 우리가 하고 싶은 것은 $J(\theta)$를 최대로 하는 $\theta^*$값을 찾아 내는 것이다.
여기서는 Gradient Ascent 방법을 이용하여 Parameter 값들을 update 시켜준다.
조금 더 구체적으로 Reinforce Algorithm에 대해서 살펴보자.
수학적으로 보면 경로에 대한 미래 보상을 기댓값으로 나타낼 수 있다.
이를 위해서 경로를 설정해야 하는데, 어떤 정책에 따라 경로가 결정된다.
Gradient Ascent 방법을 사용하기 위햇 미분을 시켜줘야 하는데,
미분을 하게 되면 슬라이드 두번째 나온 수식처럼
계산 불가능한 식이 나온다.
따라서 약간의 trick을 써서 식을 변형해준다.
맨 아래와 같이 수식을 바꾸면 Monte Carlo sampling에 의해 경로를 샘플링할 수 있게 된다.
(자세한 내용은 좀 더 공부를 하고 포스팅을 진행해야 할 것 같다..)
좀 더 식을 자세히 살펴보자.
우리는 과연 전이 확률을 모르는데 $p(\tau ; \theta)$를 계산할 수 있을까?
정답을 미리 얘기하자면 계산할 수 있다!
우리가 $log$를 이용하게 되면 그에 대한 성질로
곱을 합으로 바꿔주는 성질을 이용할 수 있는데,
미분을 하려고 할 때 정책에 대한 함수만 고려해주면 되므로,
우리는 전이 확률을 구체적으로 몰라도 $J(\theta)$의 미분 값을 계산할 수 있다.
즉, 구체적인 값(Q-value)을 몰라도 정책 자체의 gradient를 구해 최적의 정책을 찾을 수 있다.
직관적으로 어떤 경로에 대해 높게 평가했다면
경로에 해당하는 모든 행동들이 좋았다고 평가하고,
어떤 경로에 대해 낮게 평가한다면
경로에 해당하는 모든 행동들이 나쁘다고 평가하는 것이다.
하지만 기댓값에 의해서 모든 값들이 Average out된다
(평균적으로 맞춰진다).
충분히 많은 샘플링을 거친다면 Gradient를 이용해서
최적의 parameter 값을 찾아 낼 수 있다.
하지만 여기서 고려해야 할 것이 한 가지 존재한다.
바로 분산이 너무 높다는 문제가 발생한다.
우리가 어떤 최적의 정책을 찾았을 때, 그 정책에 포함된 행동들에 대해서 좋았다고 평가를 하는데 Average out때문에 구체적으로 어떤 행동이 좋은 정책을 만들어 내는지는 알지 못한다.
좋은 Estimator를 위해서는 분산을 낮추고, 샘플링을 많이해서
좋은 Estimator가 어떤 것인지 찾아내는 수 밖에 없다.
분산을 줄이는 것은 Policy Gradient에서 가장 중요한 요인 중 하나이다.
분산이 줄어들면 샘플링을 적게해도 좋은 Estimator를 찾을 수 있기 때문이다.
분산을 줄일 수 있는 첫 번째 방법을 소개하자면,
해당 상태로부터 받을 미래 보상만을 고려하여 어떤 행동을 취할 확률을 키워주는 방법이다.
이 방법은 해당 경로에서 얻을 수 있는 전체 보상을 고려하는 대신에, 현재 step에서 종료 시점까지 얻을 수 있는 보상의 합을 고려하는 전략이다.
두 번째 방법을 소개하면,
지연된 보상에 의해서 할인률을 적용하는 것이다.
할인률이 의미하는 것은 바로 받을 보상과 먼 미래에 받을 보상에 대해서 구분해 주는 것을 말한다.
분산을 줄이기 위한 세 번째 방법은 Baseline이라는 방법이다.
경로에서부터 계산한 값을 그대로 사용하는 것은 문제가 있는데,
그 값이 의미있는 값인지 아닌지 모르기 때문이다.
중요한 것은 우리가 얻은 보상이 우리가 얻을 것이라고 예상했던 것 보다 좋은건지 아닌건지 판단하는 것이다.
Baseline funtion은 해당 상태에서 우리가 얼마만큼의 보상을 원하는지 설명해주는 함수이다.
그리고 이것을 기준으로 세워 수식에 적용하면 미래에 얻을 보상의 합을 특정 기준이 되는 값에서 빼주는 형태가 된다.
이를 통해 우리가 예상했던 보상보다 좋은건지 나쁜건지 판단을 할 수 있게 된다.
그렇다면 어떻게 Baseline funtion을 정의할 수 있을까?
가장 간단한 방법은 우리가 지금까지 경험했던 보상들에 대해서 Moving average 값을 취해주는 방법이다.
그렇다면 더 좋은 baseline function은 어떻게 정의할 수 있을까?
우리는 어떤 행동이 그 상태에서의 기댓값보다 좋은 경우에 그 행동을 수행할 확률이 커지는 것을 원한다.
따라서 앞서 우리가 배웠던 Value funtion을 이용하여 baseline에 적용해보자.
현재 행동이 얼마나 좋은 행동이였는지
Q - function과 Value function의 차이를 통해 나타낸다.
그렇다면 우리는 구체적인 Q - function과 Value function이 무엇인지 알아야 할까?
아니다! 우리는 Policy gradient와 Q-learning을 조합해서 Training을 시킬 수 있다.
구체적으로 우리는 이 알고리즘을 Actor-Critic Algorithm이라고 부른다.
Actor는 Policy로 우리가 어떤 상태를 결정할지 정해주는 녀석이고,
Critic은 Q-function으로 그 행동이 얼마나 좋았으며 어떤 식으로 조절해 나가야하는지 알려주는 녀석이다.
기존 Q-function은 모든 (상태, 액션) 조합에 대해서 학습을 진행해야 했지만, 여기서는 정책이 정해준 (상태, 액션) 조합에 대해서만 학습을 진행하면 된다.
내 생각에 마치 GAN을 training 시키는 것과 비슷하다고 생각한다.
슬라이드 맨 아래에 보이는 수식을 Advantage funtion이라고 하고
Q - function - Value function 으로 정의한다.
Advantage funtion은 그 행동이 예상했던 것보다 얼마나 더 큰 보상을 주는지 알려주는 함수이다.
Actor-Critic Algorithm의 pseudo code는 다음과 같다.
- 우선 $\theta, \phi$를 초기화 시킨다.
- 현재의 policy를 기반으로 M개의 경로를 샘플링한다.
- Gradient를 계산한다. 각 경로마다 보상 함수를 계산하고 이용한다.
- 보상함수를 이용해서 gradient estimator를 계산하고 이를 전부 누적시킨다.
- $\phi$를 학습시키기 위해 가치 함수를 학습시킨다. 가치 함수는 보상 함수와 동치이므로, 가치 함수가 벨만 방정식(Bellman equation)에 근접하도록 학습시킨다.
- 앞선 단계를 계속 반복한다.
그렇다면 예제를 통해 reinforcement algorithm을 살펴보자.
RAM(Recurrent Attention Model)은 hard attention과 관련이 있는데,
Hard attention은 Image classification 문제를 푸는데 이미지의 일련의 glimpses(짧은 시간안에 일부분을 보는 것)를 가지고만 예측을 하는 Task이다.
이런 식의 접근 방법은 인간의 안구 운동에 따른 지각 능력으로 부터 영감을 받은 것이다.
또한 지역적인 부분만 보고 전체 이미지를 예측한다면 계산적인 측면에서도 크게 효율적으로 적용할 수 있다.
이미지의 노이즈를 고려하지 않기 때문에 실제로 classification도 더 잘 할 수 있다.
이 문제를 강화학습으로 풀어보자.
- 상태는 지금까지 관찰한 glimpses
- 행동은 다음에 어떤 부분을 볼 것인지 결정한는 것
- 보상은 classification의 성공 유무
이 문제가 강화학습이 필요한 이유는 이미지에서 glimpses를 뽑아내는 것이 미분 불가능하기 때문이다.
그리고 어떻게 glimpses를 얻어 낼 것인지 정책을 통해 학습을 할 수 있다.
상태를 선택하는 것에 있어 RNN을 이용하여 모델링을 한다.
강의에서 알파고에 대한 설명도 나오는데 포스팅이 너무 길어져 그 이야기는 생략하려고 한다.
(사실 핑계이고 너무 어렵다..)
이번에 배운 강화학습을 한 슬라이드로 정리하면 다음과 같다.
15, 16강은 Guest lecture이기 때문에 따로 포스팅은 하지 않을 것이다.
이 강의를 통해 전반적인 Deep learning의 개요를 알 수 있었다.
후반부로 갈 수록 수식도 많이 나오고 개념도 어려웠지만
한 번 훑어보면 분명 도움이 될 것이라 생각한다.
댓글남기기