[Stanford Univ: CS231n] Lecture 14. Reinforcement Learning

본 포스팅은 Stanford University  School of Engineering의 CS231n: Convolutional Neural Networks for Visual Recognition을 수강하고 공부한 내용을 정리하기 위한 포스팅입니다.

https://youtu.be/lvoHnicueoE?si=IUDiZfS92kmOWib7

 

https://github.com/cs231n/cs231n.github.io

GitHub - cs231n/cs231n.github.io: Public facing notes page

 

1. Reinforcement Learning

 Reinforcement Learning은 에이전트(agent)가 환경(environment)과 상호작용하며, 보상(reward)을 최대화하는 방향으로 의사결정(policy)을 학습하는 학습 패러다임이다.

2. Markov Decision Process(MDP)

Reinforcement Learning은 주로 MDP라는 수학적 모델에 기반하여 이루어진다.

• S: 상태 집합
• A: 행동 집합
• R(s,a): 보상 함수
• P(s′∣s,a): 상태 전이 확률
• γ: 할인율 (0 < γ ≤ 1, 미래 보상에 대한 중요도)

에이전트는 상태 S에서 행동 A를 선택하고, 보상 R을 받고 새로운 상태 S′로 이동한다. 이 과정을 반복하면서 보상의 총합이 최대화되도록 학습한다.

Markov Decision Process가 작동하는 방식은 아래와 같다.

 

1. 초기 time temp인 t = 0에서 환경은 초기 상태 분포인 p(s_0)로부터 s_0을 샘플링한다.

2. 그리고 t = 0에서부터 완료 상태가 될 때 까지 아래 과정을 반복한다.

- 에이전트는 행동 a_t를 선택한다.

- 환경은 s_t와 a_t가 주어졌을 때의 보상을 샘플링한다.

- 환경은 다음 어떤 분포에서 상태인 s_t+1도 샘플링한다.

- 그리고 에이전트는 보상(r_t)와 다음 상태(s_t+1)를 받은 후 다음 단계를 수행한다.

 

 에이전트는 모든 과정이 종료될 때 까지 위의 방식으로 보상과 다음 상태를 받는 과정을 되풀이한다. π(policy)는 각 상태에서 에이전트가 어떤 행동을 취할지를 명시해주는 기능을 수행한다. 즉, 최적의 π를 찾아서 cumulative discounted reward를 최대화시키는 것이 목표이다.

 

 reward에는 미래에 얻을 보상도 포함이 되는데, 이 보상은 discount factor(γ)에 의해 중요도가 조절된다.

-> 에이전트는 최적의 의사결정 π∗을 찾아서 누적 보상(expected return)을 최대화해야 한다.

 아래 슬라이드는 간단한 MDP 예제이다. 격자로 된 Grid World에서 Random Policy와 Optimal Policy의 차이에 대해 알아보자. 격자에서는 상, 하, 좌, 우로 움직이는 행동을 취할 수 있고, 한번 움직일 때 마다 negative reward를 받게 된다. 이 문제에서 최종 목표는 회색으로 칠해진 부분에 최소한의 행동으로 도달하는 것이다.

 

 Random policy는 기본적으로 어떤 방향으로 움직이든 무작위로 방향을 결정한다. 즉, 모든 방향이 동일한 확률을 갖는다. 

 

 반면에 Optimal policy는 점점 더 회색 부분에 가까워 지도록 만드는 적절한 방향을 선택해서 행동을 취하게 된다. 즉, 종료 상태와 먼 곳에 있다고 하더라도, 종료 상태에 가장 가깝게 이동할 수 있는 방향으로 이동한다. 따라서 효율성을 위해 MDP를 정의하고 나면 Optimal Policy를 찾아야 한다. 

Markov Decision Process: optimal policy 

 

 보상의 합이 최대가 되는 π∗를 찾기 위해서는 MDP에서 발생하는 무작위성(randomness)를 다뤄야 한다. 이를 위해서는 보상의 합에 대한 기댓값을 최대화시키면 된다. 

 

 수식적으로 써보면, 최적의 π∗는 π에 대한 미래 보상들의 합 기댓값을 최대화시키는 것이다. 여기에서 초기 상태(s_0)는 어떤 상태 분포를 따르며, 행동은 어떤 상태가 주어졌을 때 π가 가지는 분포로부터 샘플링다. 마지막으로 다음 상태는 전이 확률 분포로부터 샘플링다.

Markov Decision Process: Value function and Q-value function

 

 Value function과 Q-value function은 Optimal policy를 구하기 위해 사용되는 함수이다. 

 

Value function

• 상태 S와  policy π가 주어졌을 때 받을 수 있는 누적 보상의 기댓값

Q-value function

• 상태 S, 행동 a, policy π가 주어졌을 때 받을 수 있는 누적 보상의 기댓값

Optimal Q-value function

•  어떤 상태 s에서 행동 a를 했을 때, 모든 policy 중 가장 높은 누적 보상 기대값을 반환하는 함수이다.

Markov Decision Process: Bellman equation

 Bellman Equation은 MDP에서 Q-value function를 재귀적으로 정의하여 Optimal policy 탐색의 기초를 제공하는 핵심 수식이다.

 우선 optimal policy으로부터 나온 Q-value function인 Q*가 있다고 가정해보면, Q*는 Bellman equation을 만족할 것이다. 이것이 의미하는 바는 어떤 (s, a)가 주어지던 간에 현재 (s, a)에서 받을 수 있는 보상(r)과 다음 상태(s', a')까지의 보상을 더한 값이다. 

 

 즉, 현재 상태 s에서 행동 a를 했을 때 얻는 보상 r을 받고, 다음 상태 s'에서 최적 행동 a'를 선택했을 때의 Q*값을 더한 것이다. 다시 말하면 Q*는 다음 상태에서도 가장 좋은 선택을 했다고 가정할 때의 기대 보상을 나타낸다.

 (s', a')에서의 Q* 값은 현재 상태(s, a)에서 취할 수 있는 모든 행동들 중에 Q*을 최대화시키는 값이 된다. 이를 통해서 최적의 Q 값을 얻을 수 있다.

 

 만약 다음 상태 s′에서 가능한 행동들 중 가장 큰 Q*(s′,a′) 값을 알고 있다면, 지금 상태에서는 이 기대값을 최대화하는 행동 a를 선택하면 된다.

 

 Optimal policy를 구할 수 있는 방법으로 value iteration algorithm이 있다. Bellman equation을 통해 각 step마다 Q*를 최적화시키면 된다. 수학적으로는 Q_i의 i가 무한대일때 최적의 Q*로 수렴하게 된다.

 

 하지만 scalable하지 않다는 문제가 있다. 반복적으로 Q*을 업데이트하기 위해서는 모든 (상태, 행동)마다 Q(s, a)를 계산해야 하는데, 상태 공간이 큰 경우에는 전체에 해당하는 Q(s, a)을 계산하는 것이 불가능하다. 따라서 신경망을 사용하여 Q(s, a)를 근사시키는 방법을 사용한다.

3. Q-Learning

 

 Q-Learning은 각 상태 s에서 가능한 모든 행동 a에 대해 Optimal Q*(s, a)를 근사하여 Optimal policy를 도출하는 알고리즘이다. 여기에서는 함수 파라미터 theta가 있다. theta는 신경망의 가중치이다.

Q-learning Forward Pass: Loss function

 

• θi​: Q-function의 현재 파라미터
• yi​: target value (정답처럼 여김), 아래와 같이 정의됨:

 

 Loss function은 Q(s, a)가 목적 함수와 얼마나 멀리 떨어져있는지를 측정한다. 즉, y_i에 가까워지도록 Q(s, a)를 학습시킨다. 이 과정에서 Loss가 최소가 되는것을 목표로 한다.

 

Q-learning Backward Pass

 Backward Pass에서는 계산한 loss를 기반으로 weight theta를 업데이트한다. 이런식의 반복적인 업데이트를 통해서 Q-function이 target과 가까워지도록 학습시킨다.

 Q-function에 사용한 네트워크는 다음과 같이 생겼다. Q-network는 가중치인 theta를 가지고 있다. 네트워크의 입력은 상태 s이다. 이 예시에서는 현재 게임 스크린의 픽셀들이다. 

 

 입력은 RGB->grayscale변환, downsampling, cropping 등 전처리 과정을 거친다. 전처리를 거친 입력은 84 x 84 x 4의 형태가 된다. FC 레이어의 출력 벡터는 네트워크의 입력인, "상태"가 주어졌을 때 각 행동의 Q-value 이다. 만약 네 가지 행동이 존재한다면 출력도 4차원이된다. 이는 현재 상태 s_t와 여기에 존재하는 행동들 a_1, a_2, a_3, a_4에 관한 Q값들이다.

 

 각 행동들 마다 하나의 스칼라 값을 얻고, 행동의 수는 task 종류에 따라서 다양한 값(4~18)으로 변할 수도 있다. 이런 방식의 네트워크 구조의 장점은 한 번의 forward pass 만으로 현재 상태에 해당하는 모든 함수에 대한 Q-value를 계산할 수 있다는 점이다.

 

 현재 상태의 각 행동들에 각각 Q-value가 존재할텐데, 현재 상태를 네트워크의 입력으로 넣어주기만 하면, 모든 Q-value를 한 번의 forward pass로 계산할 수 있으므로 아주 효율적인 방법이다.

 

 

 Q-network를 학습시키기 위해서는 앞서 구한 loss function이 필요하다. 네트워크로 근사시킨 함수도 Bellman equation을 만족해야 한다. 따라서 네트워크의 출력인 Q-value가 target(y_i)과 가까워지도록 학습시켜야 한다. backward pass에서는 손실함수를 기반으로 gradient를 계산하고 이를 바탕으로 네트워크를 학습시킨다.

Q-Learning: Experience Replay

 experience replay는 Q-Learning에서 과거의 transition들을 저장해두고, 무작위로 샘플링하여 학습에 사용하는 기법이다. Q-learning은 환경과 상호작용하면서 경험한 transition을 즉시 사용해 Q값을 업데이트한다. 하지만 Q-network를 학습시킬 때 하나의 배치에서 시간적으로 연속적인 샘플들로 학습을 진행하게 되면, 모든 샘플들이 상관 관계를 갖게 돼서 학습이 비효율적이게 된다.

 

 또한 현재 Q-network의 parameter는 다음 샘플들에 대한 policy를 결정하게 되기 때문에 학습에 좋지 않은 영향을 미치게 된다.(ex. 현재 상태에서 왼쪽으로 이동하는 것이 보상을 최대화하는 행동이라면 다음 샘플들도 모두 왼쪽에서 발생할 수 있는 것들로만 편향된다.)

 

 여기에서는 replay memory에서의 임의의 미니 배치를 이용하여 Q-network를 학습시킨다. 연속적인 샘플을 사용하는 대신 전이 테이블에서 임의로 샘플링된 샘플을 사용하는 것이다. 이 방식을 통해서 앞서 상관관계(correlation)로 발생하는 문제를 해결할 수 있다. 추가적으로 각각의 전이가 가중치 업데이트에 여러 차례 기여할 수 있게 된다. 이를 통해 데이터 효율이 훨씬 더 증가한다.

Deep Q-learning 전체 알고리즘

 

0. 초기화

• Replay memory D:
  최대 용량 N을 가진 버퍼로, 경험 (s,a,r,s′)을 저장
• Q-function Q(s,a;θ):
  랜덤한 가중치로 초기화된 딥러닝 모델

1. 초기 상태 설정

• 환경의 초기 상태 s_1​을 관찰하고, CNN 입력용 전처리된 상태 ϕ_1 = ϕ(s_1)를 생성

2-1. 행동 선택 (Exploration/Exploitation)

• 확률 ϵ로 랜덤한 행동 a_t 선택 (exploration) -> 다양한 상태 공간을 샘플링하는 효과
• 그렇지 않으면 아래 수식으로 a_t 선택 (exploitation)

2-2. 환경에 행동 적용

• 행동 a_t​를 수행하고,
• 다음 상태 s_t+1, 보상 r_t​, 화면 이미지 x_t+1​를 얻음

2-3. 전처리 및 저장

• 다음 상태 s_t+1​을 전처리하여 ϕ_t+1​ 생성
• transition(ϕ_t, a_t, r_t, ϕ_t+1)을 replay memory D에 저장

3. 미니배치 샘플링

• 매 학습 스텝마다, replay memory D에서 무작위로 Batch size개의 transition들을 샘플링 (ϕ_j, a_j, r_j, ϕ_j+1)한다.
• 이 Batch size개의 transition을 이용하여 각각의 target y_j를 계산하고, 전체 loss를 평균내어 계산한다.

4. Target y_j​ 계산

 

5. Gradient descent으로 θ 업데이트

• 이 평균 loss에 대해 gradient를 계산하고, weight theta를 업데이트한다.
• 즉, 미니배치 내 모든 transition을 동시에 사용하여 weight를 한 번 업데이트한다.

4. Policy Gradients

 Policy Gradient는 강화학습에서 Policy 자체를 직접 학습하는 방식이다. Q-learning에서는 모든 (state, action) 쌍들을 학습해야만 한다. 때문에 Q-learning은 고차원의 상태 공간이 존재하는 문제를 해결하는 것이 불가능에 가깝다. 

 

 Policy Gradient는 Q-Learning처럼 value function을 먼저 추정하는 것이 아니라, 확률적으로 행동을 선택하는 policy π(a∣s;θ)를 직접 파라미터화하고, 이 정책이 기대 보상을 최대화하도록 경사 상승(gradient ascent) 방식으로 업데이트한다.

 Policy Gradients의 목표는 optimal policy θ*를 찾아서, 에이전트가 받을 수 있는 expected return J(θ)을 최대화하는 것이 목적이다. 이때 J(θ)는 미래에 받을 보상들의 누적 합의 기댓값으로 나타낸다.

​ 따라서 optimal policy θ*은 아래와 같이 나타낼 수 있다.

 이제 보상의 기댓값을 최대로 하는 optimal policy θ*를 찾기만하면 된다.

Policy Gradients: REINFORCE algorithm

  REINFORCE 알고리즘은 policy parameter에 대해서 gradient ascent를 수행하여 parameters를 연속적으로 업데이트한다. 수학적으로 보면, trajectory에 대한 미래 보상의 기댓값으로 나타낼 수 있다. 

 

 이를 위해서 trajectory를 샘플링해야 하는데, 하나의 trajectory τ는 에이전트가 한 번의 에피소드 동안 환경과 상호작용한 모든 상태, 행동, 보상, 다음 상태의 연속을 의미하며, 일반적으로 다음과 같이 구성된다:

 이 trajectory들은 어떤 policy π_θ​를 따라 결정될 것이다. 

 그러면 각 경로에 대해서 보상을 계산할 수 있다. 이 보상은 어떤 trajectory를 따라 얻을 수 있는 누적 보상이 될 것이다. 

 

 gradient ascent를 위해 J(θ)를 미분한다. 미분을 진행한 뒤 이 값들을 gradient step으로 취하면 될 것이다. 하지만 여기서 p(τ; θ)를 계산할 수가 없다.(intractable) p가 θ에 종속되어 있는 상황에서 기댓값 안에 gradient가 있으면 문제가 될 수 있다.

 

 하지만 여기서 기댓값의 gradient를 score function trick(likelihood ratio trick)을 통해 바깥으로 뺄 수 있다.

 이 수식을 앞에 있던 gradient 식에 대입하게 되면, 이제는 log(p)에 대한 gradient를 모든 trajectory에 대한 확률로 곱하는 꼴이 된다.

 그러면 다시 trajectory에 대한 기댓값의 형식으로 바꿀 수 있다.

 처음에는 기댓값에 대한 gradient를 계산했지만,

이제는 gradient에 대한 기댓값으로 바꾼 셈이다.

이로 인해 gradient를 추정하기 위해서 trajectory를 샘플링하여 사용할 수 있다.

 그럼 이제 전이 확률을 모르는 채로 계산을 진행해보자. 아래 식은 trajectory τ가 발생할 전체 확률을 나타낸다. "정책이 특정 행동을 선택할 확률 × 환경이 그에 따라 특정 상태로 전이될 확률"을 모든 타임스텝에 대해 곱한 값이다.

 이 식을 로그 변환하면:

  이 되고, 이제 gradient를 계산하면:

 여기서 전이 확률 p는 policy θ와 무관하므로 gradient 계산에서 사라지게 된다. 따라서 policy gradient는 transition probability를 몰라도 계산 가능해지게 된다. 

 

 이제 하나의 trajectory를 샘플링해서 다음과 같이 근사할 수 있다.

 

• 한 trajectory에서 얻은 누적 보상 r(τ)
• 그 안의 각 시간 step에서의 행동 확률의 로그 gradient

 

 gradient 계산을 하기 위해서 지금까지 유도한 것을 해석해보면 아래와 같다.

 

- 만약 어떤 경로로부터 얻은 보상이 크다면, 그 경로에 속한 모든 행동의 확률을 증가시키는 방향으로 파라미터를 업데이트한다.

- 반면에 만약 어떤 경로에 대한 보상이 낮다면, 해당 행동들의 확률을 줄이는 방향으로 업데이트한다.

 

 "좋은 경로였다면 모든 행동도 좋았을 것이다."라는 가정은 단순해 보이지만, 많은 경로를 평균적으로 보면, 올바른 방향으로 수렴하게 된다. 즉, 개별 trajectory에선 완벽하지 않지만 기댓값 측면에서 unbiased하므로, 충분히 많은 샘플을 모으면 평균적으로 좋은 방향으로 학습이 진행된다는 이론적 보장이 있다.

 

 그러나  r(τ)는 trajectory 전체의 보상이므로, 각 행동 a_t​ 에 대해 정확히 얼마나 기여했는지를 판단하기 어렵다. 예를 들어 어떤 행동 하나가 성공의 핵심이었을 수도 있고, 아닐 수도 있는데 r(τ)는 trajectory 전체의 보상만 제공하므로 개별 행동에 대한 책임을 나누기 어려워 학습에 분산(variance)이 생긴다.

 

Policy Gradients: Variance reduction

 Variance을 줄이는 것은 policy gradient에서 아주 중요한 분야이다. 샘플링을 더 적게 하면서도 estimator의 성능을 높일 수 있는 방법이기 때문이다.

 

 첫 번째 아이디어는 전체 보상이 아닌, 해당 시점 t 이후의 누적 보상만을 사용하는 것이다.

•  이 방법은 해당 경로에서 얻을 수 있는 전체 보상을 고려하는 것 대신에 맨 처음부터가 아닌, 현재의 time step에서부터 종료 시점까지 얻을 수 있는 보상의 합을 고려한다.
• 이 방법이 의도하는 바는 어떤 행동이 발생시키는 미래의 보상이 얼마나 큰지를 고려하겠다는 것이다.

 두 번째 아이디어는 지연된 보상에 덜 민감하도록 discount factor를 사용하는 것이다.

• discount factor γ ∈ [0,1] 이므로, 먼 미래의 보상은 덜 중요하게 반영한다.

Policy Gradients: Variance reduction: Baseline

 세 번째 아이디어는 Baseline이라는 방법이다. 경로에서부터 계산한 값을 그대로 사용하는 것이 아닌, 경로로부터 얻은 보상이 예상했던 것보다 더 좋은지, 아닌지를 판단하는 과정을 추가한다.

• b(s_t): 상태 s_t​에서의 보상 기대값에 해당하는 기준점

 Baseline을 선택하는 간단한 방법으로는 지금까지의 모든 경로로부터 얻은 보상의 평균을 사용하는 것이다.

 Baseline을 더 정교하게 선택하는 아이디어로, value function과 Q-function을 활용하는 방법도 있다.

 

• Advantage는 "행동 a가 평균보다 얼마나 더 좋은가?"를 측정하는 값이다.
• A > 0이면 좋은 행동 → 확률 증가
  A < 0이면 나쁜 행동 → 확률 감소

 

5. Actor-Critic Algorithm

 지금까지의 REINFORCE 알고리즘에서는 Q-function과 Value-function을 구하지 않았다. Actor-Critic Algorithm에서는 Q-learning을 통해서 Policy와 Q-function을 학습시키면서 Policy Gradient 방식과 Q-learning 방식을 조합한다.

 

 여기에서는 actor가 policy이고, critic이 Q-function이다. 이들은 어떤 상태가 얼마나 좋은지, 그리고 상태에서의 어떤 행동이 얼마나 좋았는지를 의미힌다.

 

 Actor-Critic 알고리즘에서 actor는 어떤 행동을 취할지를 결정한다. 그리고 critic (Q-function)은 그 행동이 얼마나 좋았으며, 어떤 식으로 조절해 나가야하는지를 알려준다. 그리고 critic의 Q-learning에서는 모든 (상태, 행동)이 아닌, policy가 만들어낸 (상태, 행동) 쌍에 대해서만 학습을 시키면 된다.

Actor Critic Algorithms 

 

0. 초기화

• policy parameter θ
• critic parameter ϕ

1. 현재 policy로 m개의 trajectory 샘플링

• 각 trajectory에서 (상태, 행동, 보상)을 수집한다.
• i = 1, ... , m은 각 에피소드
• t = 1, ... , T은 각 에피소드 내의 time step

2. Advantage 계산 A_t

• ​첫 항: 해당 상태 이후의 discounted reward 합
• 두 번째 항: critic이 예측한 상태의 가치
• 이 값이 클수록 policy는 그 행동의 확률을 높여야 한다.

3. Actor 업데이트(gradient ascent)

• advantage에 따라 확률을 더 높이거나 낮춘다. 

4. Critic 업데이트(value function 학습)

• advantage의 제곱을 줄이는 방향으로 V(s)를 학습한다. 이를 통해 가치 함수가 벨만 방정식에 근사하도록 학습다.
• 즉, discounted reward의 합과 value의 차이를 줄이도록 학습한다.

5. parameter 갱신

 

• α, β: learning rate
• 둘 다 동시에 업데이트 → policy와 value 동시 개선

 

 

Reccurent Attention Model(RAM, 2014)

 Recurrent Attention Model은 강화학습 기반의 시각적 주의(attention) 메커니즘으로, 사람이 이미지를 전체적으로 보지 않고, 중요한 부분만 순차적으로 살펴보며 인식하는 방식에서 영감을 받은 모델이다.

 

 전체 이미지를 한 번에 처리하지 않고, glimpse라고 불리는 작은 시각 영역들만 반복적으로 관찰하여 정보를 축적하고, 마지막에 결정을 내리는 모델이다.