강화학습은 에이전트가 환경과 상호작용하며 누적 보상을 최대화하는 정책을 학습하는
기계학습의 한 분야다. 지도학습과 결정적으로 다른 점은 명시적 레이블이 없다는 것이다.
정답 대신 보상 신호 만 주어지고, 에이전트는 시행착오로 배운다.
구성 요소 에이전트 학습하고 행동하는 주체 환경 행동에 따라 상태와 보상을 제공 상태 S S S 환경의 현재 상황 행동 A A A 취할 수 있는 선택 보상 R R R 행동에 대한 피드백 정책 π \pi π 상태에서 행동을 선택하는 규칙 π ( a ∣ s ) \pi(a\lvert s) π ( a ∣ s ) 가치 함수 상태 또는 상태-행동 쌍의 기대 보상 V π ( s ) V^\pi(s) V π ( s ) Q π ( s , a ) Q^\pi(s,a) Q π ( s , a )
목표는 최적 정책 π ∗ \pi^* π ∗
J ( π ) = E π [ ∑ t = 0 ∞ γ t R t + 1 ] J(\pi) = \mathbb{E}_\pi\left[\sum_{t=0}^{\infty} \gamma^t R_{t+1}\right] J ( π ) = E π [ ∑ t = 0 ∞ γ t R t + 1 ]
γ ∈ [ 0 , 1 ) \gamma \in [0, 1) γ ∈ [ 0 , 1 ) 할인율 이다. 미래의 보상을 현재만큼 값지게 치지 않겠다는 뜻이고,
동시에 무한 합이 발산하지 않게 하는 수학적 장치이기도 하다.
전체를 관통하는 두 축이 있다. On-Policy vs Off-Policy , 그리고
Model-Based vs Model-Free 다. 아래 알고리즘들은 결국 이 두 축 위의 좌표다.
밴딧 문제
다중 팔 밴딧(Multi-Armed Bandit) — 여러 옵션(팔) 중에서 보상을 최대화하기 위해
선택하는 가장 단순한 RL 문제다. 각 팔은 알려지지 않은 보상 분포를 가진다.
상태가 없다. 오직 탐험과 활용의 트레이드오프만 남긴 문제 라서 강화학습의 첫 관문이 된다.
활용 Exploitation알려진 고보상 행동을 고른다. greedy 탐험 Exploration새로운 행동을 시도한다. random
알고리즘
Epsilon-Greedy — 확률 ϵ \epsilon ϵ 1 − ϵ 1-\epsilon 1 − ϵ
π ( a ) = { arg max a Q ( a ) 확률 1 − ϵ 무작위 행동 확률 ϵ \pi(a) = \begin{cases} \arg\max_a Q(a) & \text{확률 } 1-\epsilon \\ \text{무작위 행동} & \text{확률 } \epsilon \end{cases} π ( a ) = { arg max a Q ( a ) 무작위 행동 확률 1 − ϵ 확률 ϵ
UCB (Upper Confidence Bound) — 불확실한 쪽에 가산점을 준다.
a t = arg max a [ Q ( a ) + c ln t N ( a ) ] a_t = \arg\max_a \left[ Q(a) + c\sqrt{\frac{\ln t}{N(a)}} \right] a t = arg max a [ Q ( a ) + c N ( a ) l n t ]
N ( a ) N(a) N ( a ) 적게 뽑아 본 팔일수록 두 번째 항이 커진다.
ϵ \epsilon ϵ
Thompson Sampling — 각 팔의 보상 분포에서 샘플링해 고른다.
보상 가중치는 상황에 따라 나뉜다 — 정상(Stationary) 이면 단순 평균으로 충분하지만,
비정상(Non-stationary) 이면 최근 데이터에 더 큰 가중치를 줘야 한다. 환경이 변하는데
과거 전부를 평균 내면 변화를 따라가지 못한다.
실제 응용은 온라인 광고, 추천 시스템, 임상 시험이다.
마르코프 결정 과정 (MDP)
강화학습의 수학적 기반이다. 마르코프 성질 — 다음 상태는 현재 상태와 행동에만 의존한다.
과거 이력 전체가 아니라 지금 상태 하나에 모든 정보가 압축돼 있다고 보는 것이다.
구성 상태 집합 S S S 행동 집합 A A A 전이 확률 P ( s ′ ∣ s , a ) P(s'\lvert s, a) P ( s ′ ∣ s , a ) 보상 함수 R ( s , a , s ′ ) R(s, a, s') R ( s , a , s ′ ) 할인율 γ ∈ [ 0 , 1 ) \gamma \in [0,1) γ ∈ [ 0 , 1 )
가치 함수
V π ( s ) = E π [ ∑ t = 0 ∞ γ t R t + 1 ∣ S 0 = s ] V^\pi(s) = \mathbb{E}_\pi\left[\sum_{t=0}^{\infty}\gamma^t R_{t+1} \,\Big\lvert\, S_0 = s\right] V π ( s ) = E π [ ∑ t = 0 ∞ γ t R t + 1 S 0 = s ]
Q π ( s , a ) = E π [ ∑ t = 0 ∞ γ t R t + 1 ∣ S 0 = s , A 0 = a ] Q^\pi(s,a) = \mathbb{E}_\pi\left[\sum_{t=0}^{\infty}\gamma^t R_{t+1} \,\Big\lvert\, S_0 = s, A_0 = a\right] Q π ( s , a ) = E π [ ∑ t = 0 ∞ γ t R t + 1 S 0 = s , A 0 = a ]
V V V Q Q Q 제어를 하려면 Q Q Q — V V V
벨만 방정식
V π ( s ) = ∑ a π ( a ∣ s ) ∑ s ′ P ( s ′ ∣ s , a ) [ R ( s , a , s ′ ) + γ V π ( s ′ ) ] V^\pi(s) = \sum_a \pi(a\lvert s)\sum_{s'} P(s'\lvert s,a)\left[R(s,a,s') + \gamma V^\pi(s')\right] V π ( s ) = ∑ a π ( a ∣ s ) ∑ s ′ P ( s ′ ∣ s , a ) [ R ( s , a , s ′ ) + γ V π ( s ′ ) ]
Q π ( s , a ) = ∑ s ′ P ( s ′ ∣ s , a ) [ R ( s , a , s ′ ) + γ ∑ a ′ π ( a ′ ∣ s ′ ) Q π ( s ′ , a ′ ) ] Q^\pi(s,a) = \sum_{s'} P(s'\lvert s,a)\left[R(s,a,s') + \gamma \sum_{a'} \pi(a'\lvert s')Q^\pi(s',a')\right] Q π ( s , a ) = ∑ s ′ P ( s ′ ∣ s , a ) [ R ( s , a , s ′ ) + γ ∑ a ′ π ( a ′ ∣ s ′ ) Q π ( s ′ , a ′ ) ]
최적 벨만 방정식 은 정책에 대한 기댓값 자리에 max \max max
V ∗ ( s ) = max a ∑ s ′ P ( s ′ ∣ s , a ) [ R ( s , a , s ′ ) + γ V ∗ ( s ′ ) ] V^*(s) = \max_a \sum_{s'} P(s'\lvert s,a)\left[R(s,a,s') + \gamma V^*(s')\right] V ∗ ( s ) = max a ∑ s ′ P ( s ′ ∣ s , a ) [ R ( s , a , s ′ ) + γ V ∗ ( s ′ ) ]
유도는 마르코프 성질에서 곧장 나온다. 상태 s s s 당장의 보상 + 다음 상태 가치의
기댓값 으로 쓸 수 있다.
V π ( s ) = E π [ R t + 1 + γ V π ( S t + 1 ) ∣ S t = s ] V^\pi(s) = \mathbb{E}_\pi[R_{t+1} + \gamma V^\pi(S_{t+1}) \lvert S_t = s] V π ( s ) = E π [ R t + 1 + γ V π ( S t + 1 ) ∣ S t = s ]
이걸 펼치면 위의 벨만 방정식이 된다. 재귀적으로 정의된다 는 것이 핵심이고, 이 재귀 구조
덕분에 반복 계산으로 풀 수 있게 된다.
동적 프로그래밍
환경 모델이 알려진 경우 MDP 를 푸는 방법이다. 전이 확률 P P P R R R
정책 평가
V k + 1 ( s ) = ∑ a π ( a ∣ s ) ∑ s ′ P ( s ′ ∣ s , a ) [ R ( s , a , s ′ ) + γ V k ( s ′ ) ] V_{k+1}(s) = \sum_a \pi(a\lvert s)\sum_{s'}P(s'\lvert s,a)[R(s,a,s') + \gamma V_k(s')] V k + 1 ( s ) = ∑ a π ( a ∣ s ) ∑ s ′ P ( s ′ ∣ s , a ) [ R ( s , a , s ′ ) + γ V k ( s ′ )]
정책 개선 — greedy 하게 고른다.
π ′ ( s ) = arg max a ∑ s ′ P ( s ′ ∣ s , a ) [ R ( s , a , s ′ ) + γ V π ( s ′ ) ] \pi'(s) = \arg\max_a \sum_{s'}P(s'\lvert s,a)[R(s,a,s') + \gamma V^\pi(s')] π ′ ( s ) = arg max a ∑ s ′ P ( s ′ ∣ s , a ) [ R ( s , a , s ′ ) + γ V π ( s ′ )]
방법 정책 반복 Policy Iteration평가와 개선을 번갈아 반복 → 최적 정책 으로 수렴 가치 반복 Value Iterationmax \max max 가치 함수 로 수렴
V k + 1 ( s ) = max a ∑ s ′ P ( s ′ ∣ s , a ) [ R ( s , a , s ′ ) + γ V k ( s ′ ) ] V_{k+1}(s) = \max_a \sum_{s'}P(s'\lvert s,a)[R(s,a,s') + \gamma V_k(s')] V k + 1 ( s ) = max a ∑ s ′ P ( s ′ ∣ s , a ) [ R ( s , a , s ′ ) + γ V k ( s ′ )]
수렴하는 이유
가치 반복은 수축 매핑(contraction mapping) 이라 고정점 정리로 수렴이 보장된다.
∥ V k + 1 − V ∗ ∥ ≤ γ ∥ V k − V ∗ ∥ \lVert V_{k+1} - V^* \rVert \le \gamma \lVert V_k - V^* \rVert ∥ V k + 1 − V ∗ ∥ ≤ γ ∥ V k − V ∗ ∥
γ < 1 \gamma < 1 γ < 1 γ \gamma γ V k → V ∗ V_k \to V^* V k → V ∗ 할인율이 1 보다 작아야 하는 이유가 여기서도 나온다.
단점은 명확하다 — 환경 모델이 필요하고 계산 비용이 높다. 상태 공간을 전부 훑어야 한다.
몬테카를로 방법
반복적인 무작위 샘플링에 의존하는 계산 알고리즘 이다. 환경 모델 없이 완전한 에피소드에서
학습한다.
V ( S t ) ← V ( S t ) + α [ G t − V ( S t ) ] V(S_t) \leftarrow V(S_t) + \alpha[G_t - V(S_t)] V ( S t ) ← V ( S t ) + α [ G t − V ( S t )]
G t G_t G t
V ( s ) ← V ( s ) + α π ( a ∣ s ) β ( a ∣ s ) [ G t − V ( s ) ] V(s) \leftarrow V(s) + \alpha\frac{\pi(a\lvert s)}{\beta(a\lvert s)}[G_t - V(s)] V ( s ) ← V ( s ) + α β ( a ∣ s ) π ( a ∣ s ) [ G t − V ( s )]
수렴하는 근거는 대수의 법칙 이다. 리턴의 평균이 기댓값으로 간다.
V ( s ) ≈ 1 N ∑ i = 1 N G i ⟶ E [ G ∣ s ] V(s) \approx \frac{1}{N}\sum_{i=1}^{N} G_i \;\longrightarrow\; \mathbb{E}[G\lvert s] V ( s ) ≈ N 1 ∑ i = 1 N G i ⟶ E [ G ∣ s ]
장점 단점 환경 모델이 필요 없다 에피소드가 끝나야 평가할 수 있다편향이 없다 분산이 크다 .
에피소드가 끝나야 한다는 제약이 실용적으로 크다. 일회성 과제에는 되지만 지속성 과제에는
적용하기 어렵다. 끝나지 않는 일에는 G t G_t G t
First-Visit 과 Every-Visit 의 차이도 정리해 둔다 — 한 에피소드에서 같은 상태를 여러 번
방문했을 때 첫 방문만 세느냐, 전부 세느냐다.
시간차 학습 (TD)
몬테카를로의 제약을 푸는 방법이다. 에피소드가 끝날 때까지 기다리지 않고 일정 시간마다
정책을 평가하고 갱신한다. 그래서 일회성 과제와 지속성 과제 모두에 쓸 수 있다.
TD = MC + DP \text{TD} = \text{MC} + \text{DP} TD = MC + DP
MC 의 샘플링과 DP 의 부트스트래핑 (다음 상태의 추정값을 그대로 가져다 쓰기)을 결합했다.
TD(0)
V ( S t ) ← V ( S t ) + α [ R t + 1 + γ V ( S t + 1 ) − V ( S t ) ] V(S_t) \leftarrow V(S_t) + \alpha[R_{t+1} + \gamma V(S_{t+1}) - V(S_t)] V ( S t ) ← V ( S t ) + α [ R t + 1 + γ V ( S t + 1 ) − V ( S t )]
대괄호 안이 TD 오차 다. MC 가 실제 리턴 G t G_t G t R t + 1 + γ V ( S t + 1 ) R_{t+1} + \gamma V(S_{t+1}) R t + 1 + γ V ( S t + 1 ) 한 스텝 뒤의 추정값 을 넣은 것이다.
Q-Learning 과 SARSA
Q-Learning : Q ( S t , A t ) ← Q ( S t , A t ) + α [ R t + 1 + γ max a Q ( S t + 1 , a ) − Q ( S t , A t ) ] \text{Q-Learning}:\; Q(S_t,A_t) \leftarrow Q(S_t,A_t) + \alpha\left[R_{t+1} + \gamma \max_a Q(S_{t+1},a) - Q(S_t,A_t)\right] Q-Learning : Q ( S t , A t ) ← Q ( S t , A t ) + α [ R t + 1 + γ max a Q ( S t + 1 , a ) − Q ( S t , A t ) ]
SARSA : Q ( S t , A t ) ← Q ( S t , A t ) + α [ R t + 1 + γ Q ( S t + 1 , A t + 1 ) − Q ( S t , A t ) ] \text{SARSA}:\; Q(S_t,A_t) \leftarrow Q(S_t,A_t) + \alpha\left[R_{t+1} + \gamma Q(S_{t+1},A_{t+1}) - Q(S_t,A_t)\right] SARSA : Q ( S t , A t ) ← Q ( S t , A t ) + α [ R t + 1 + γ Q ( S t + 1 , A t + 1 ) − Q ( S t , A t ) ]
두 식의 차이는 딱 한 곳, max a Q \max_a Q max a Q Q ( S t + 1 , A t + 1 ) Q(S_{t+1}, A_{t+1}) Q ( S t + 1 , A t + 1 ) 여기서 On-Policy 와
Off-Policy 가 갈린다.
정책 뜻 On-Policy (SARSA)대상 정책 = 행동 정책 스스로 쌓은 경험으로 자신의 정책을 개선 Off-Policy (Q-Learning)대상 정책 ≠ 행동 정책 다른 정책으로 쌓은 경험 으로 자신의 정책을 개선
Q-Learning 은 실제로 어떤 행동을 했든 상관없이 “최선을 골랐다면” 을 가정하고 갱신한다.
그래서 탐험을 하면서도 최적 정책을 배울 수 있다. SARSA 는 실제로 고른 행동
A t + 1 A_{t+1} A t + 1
Q-Learning 의 수렴 역시 수축 매핑이다.
Q n e w ( s , a ) = ( 1 − α ) Q ( s , a ) + α [ R ( s , a , s ′ ) + γ max a ′ Q ( s ′ , a ′ ) ] Q_{new}(s,a) = (1-\alpha)Q(s,a) + \alpha\left[R(s,a,s') + \gamma\max_{a'}Q(s',a')\right] Q n e w ( s , a ) = ( 1 − α ) Q ( s , a ) + α [ R ( s , a , s ′ ) + γ max a ′ Q ( s ′ , a ′ ) ]
α \alpha α Q → Q ∗ Q \to Q^* Q → Q ∗
신경망으로 근사하기
상태 공간이 커지면 표(table)로 Q Q Q
층 입력층 상태를 나타낸다 (FrozenLake 라면 16개 노드) 은닉층 ReLU 로 비선형성 제공 출력층 Q 값 또는 정책 확률. 선형 활성화
출력층에 활성화 함수를 두지 않는 이유는 Q 값이 범위 제한 없는 실수이기 때문이다.
선형 함수 근사와 그 TD 업데이트는 이렇게 된다.
V ( s ) = w T ϕ ( s ) , w ← w + α δ t ϕ ( S t ) V(s) = w^T\phi(s), \qquad w \leftarrow w + \alpha\delta_t\phi(S_t) V ( s ) = w T ϕ ( s ) , w ← w + α δ t ϕ ( S t ) δ t = R t + 1 + γ w T ϕ ( S t + 1 ) − w T ϕ ( S t ) \delta_t = R_{t+1} + \gamma w^T\phi(S_{t+1}) - w^T\phi(S_t) δ t = R t + 1 + γ w T ϕ ( S t + 1 ) − w T ϕ ( S t )
신경망 자체의 기초 — 단층 퍼셉트론은 선형 분류만 가능하고 XOR 같은 비선형 문제를 풀지
못한다. 은닉층이 하나 이상인 MLP 라야 비선형 분류가 된다. 손실 함수는 회귀에 MSE,
분류에 교차 엔트로피(CEE)를 쓰고, 미니배치로 학습하며, 경사하강법과 오차 역전파로
가중치를 갱신한다.
Q-Network 와 DQN
Q-Network 는 Q 함수를 신경망으로 근사한 것이다. Q-Learning + 신경망 회귀라고 보면 된다.
Q ( s , a ; θ ) ← Q ( s , a ; θ ) + α [ R + γ max a ′ Q ( s ′ , a ′ ; θ − ) − Q ( s , a ; θ ) ] Q(s,a;\theta) \leftarrow Q(s,a;\theta) + \alpha\left[R + \gamma\max_{a'}Q(s',a';\theta^-) - Q(s,a;\theta)\right] Q ( s , a ; θ ) ← Q ( s , a ; θ ) + α [ R + γ max a ′ Q ( s ′ , a ′ ; θ − ) − Q ( s , a ; θ ) ]
θ − \theta^- θ − 타깃 네트워크 의 가중치다. DQN 은 여기에 두 가지 장치를 얹어 학습을
안정시킨다.
경험 재생 (Experience Replay)
에이전트가 행동할 때마다 경험 ( s , a , r , s ′ ) (s, a, r, s') ( s , a , r , s ′ ) 무작위로 뽑아
미니배치 를 만들어 학습한다.
연속된 경험은 서로 강하게 상관돼 있다. 그대로 순서대로 학습하면 신경망이 최근 몇 스텝에
과하게 맞춰진다. 무작위 추출이 그 상관관계를 끊어 분산을 줄인다.
타깃 네트워크
Q 값이 갱신될 때마다 정답 레이블도 같이 움직인다. 쫓아가야 할 과녁이 계속 움직이는
셈 이라 학습이 불안정해진다.
그래서 원본 신경망(qnet)과 구조가 같은 신경망(qnet_target)을 하나 더 두고, 목표값은
이 고정된 쪽에서 가져온다. 일정 주기마다 가중치를 복사해 준다.
L ( θ ) = E [ ( r + γ max a ′ Q ( s ′ , a ′ ; θ − ) − Q ( s , a ; θ ) ) 2 ] L(\theta) = \mathbb{E}\left[\left(r + \gamma\max_{a'}Q(s',a';\theta^-) - Q(s,a;\theta)\right)^2\right] L ( θ ) = E [ ( r + γ max a ′ Q ( s ′ , a ′ ; θ − ) − Q ( s , a ; θ ) ) 2 ]
경험 재생은 상관관계를 줄이고, 타깃 네트워크는 이동 타깃 문제를 완화한다. 이 두 문장이
DQN 을 요약한다. DQN 은 Atari 게임에서 인간 수준 성능을 달성했고, 이후
Double DQN , Dueling DQN 같은 변형이 나왔다.
정책 그라디언트
가치 함수를 거치지 않고 정책 매개변수 θ \theta θ 한다.
∇ θ J ( θ ) = E π [ ∇ θ log π θ ( a ∣ s ) Q π ( s , a ) ] \nabla_\theta J(\theta) = \mathbb{E}_\pi\left[\nabla_\theta\log\pi_\theta(a\lvert s)\,Q^\pi(s,a)\right] ∇ θ J ( θ ) = E π [ ∇ θ log π θ ( a ∣ s ) Q π ( s , a ) ]
REINFORCE
θ ← θ + α G t ∇ θ log π θ ( A t ∣ S t ) \theta \leftarrow \theta + \alpha G_t\nabla_\theta\log\pi_\theta(A_t\lvert S_t) θ ← θ + α G t ∇ θ log π θ ( A t ∣ S t )
Actor-Critic
θ ← θ + α δ t ∇ θ log π θ ( A t ∣ S t ) , δ t = R t + 1 + γ V ( S t + 1 ) − V ( S t ) \theta \leftarrow \theta + \alpha\delta_t\nabla_\theta\log\pi_\theta(A_t\lvert S_t), \qquad \delta_t = R_{t+1} + \gamma V(S_{t+1}) - V(S_t) θ ← θ + α δ t ∇ θ log π θ ( A t ∣ S t ) , δ t = R t + 1 + γ V ( S t + 1 ) − V ( S t )
Actor 가 정책을, Critic 이 가치 함수를 동시에 학습한다. REINFORCE 의 G t G_t G t δ t \delta_t δ t
특징 장점 연속 행동 공간에 적합 하다. Q 러닝은 max a \max_a max a 단점 분산이 크다 베이스라인(V ( s ) V(s) V ( s )
고급 방법
알고리즘 DDPG 연속 행동 공간을 위해 Q-Learning 과 정책 그라디언트를 결합 SAC 엔트로피를 최대화 해 탐험을 촉진PPO 안정적이고 샘플 효율적인 정책 그라디언트 Model-Based RL 환경 모델을 학습해 계획한다 Hierarchical RL 복잡한 작업을 하위 작업으로 분해
성공 사례는 AlphaGo 와 AlphaZero 다.
공식 한 장 요약
알고리즘 공식 특징 정책 평가 V k + 1 ( s ) = ∑ a π ( a ∣ s ) ∑ s ′ P [ R + γ V k ( s ′ ) ] V_{k+1}(s) = \sum_a \pi(a\lvert s)\sum_{s'}P[R + \gamma V_k(s')] V k + 1 ( s ) = ∑ a π ( a ∣ s ) ∑ s ′ P [ R + γ V k ( s ′ )] 환경 모델 필요 가치 반복 V k + 1 ( s ) = max a ∑ s ′ P [ R + γ V k ( s ′ ) ] V_{k+1}(s) = \max_a \sum_{s'}P[R + \gamma V_k(s')] V k + 1 ( s ) = max a ∑ s ′ P [ R + γ V k ( s ′ )] 최적 가치 함수로 수렴 TD(0) V ( S t ) ← V ( S t ) + α [ R t + 1 + γ V ( S t + 1 ) − V ( S t ) ] V(S_t) \leftarrow V(S_t) + \alpha[R_{t+1} + \gamma V(S_{t+1}) - V(S_t)] V ( S t ) ← V ( S t ) + α [ R t + 1 + γ V ( S t + 1 ) − V ( S t )] 부트스트래핑 Q-Learning Q ← Q + α [ R + γ max a Q ( S t + 1 , a ) − Q ] Q \leftarrow Q + \alpha[R + \gamma\max_a Q(S_{t+1},a) - Q] Q ← Q + α [ R + γ max a Q ( S t + 1 , a ) − Q ] Off-Policy SARSA Q ← Q + α [ R + γ Q ( S t + 1 , A t + 1 ) − Q ] Q \leftarrow Q + \alpha[R + \gamma Q(S_{t+1},A_{t+1}) - Q] Q ← Q + α [ R + γ Q ( S t + 1 , A t + 1 ) − Q ] On-Policy REINFORCE θ ← θ + α G t ∇ θ log π θ \theta \leftarrow \theta + \alpha G_t\nabla_\theta\log\pi_\theta θ ← θ + α G t ∇ θ log π θ 정책 직접 최적화