AI - Reinforcement Learning
본 포스트는 Stuart Russell 과 Peter Norvig의 Artifical Intelligence : A Modern Approach (4th edition) 의 Reinforcement Learning부분을 다룬다.
Reinforcement Learning
강화학습이란?
강화학습의 출발점 : Atari 게임
강화학습의 핵심 구조 : Agent(에이전트)와 Environment(환경)의 상호작용
- Agent : 두뇌 (의사결정자). 현재 상태를 보고 행동을 결정함
- Environment : 아타리 게임기, 에이전트의 행동에 반응하여 다음 상태와 보상을 줌.
핵심 목표 : 에이전트가 기대 보상 (Expected Reward)을 최대화하도록 행동을 배운다.
MDP (Markov Decision Process) 복습
-
Value Iteration : 상태의 최적가치 V*(s) 계산 \(V^*(s) = \max_a \sum_{s'} P(s' \mid s,a) \left( R(s,a,s') + \gamma V^*(s') \right)\)
-
Policy Iteration : 최적 정책 π*(s) 계산
Reinforcement Learning Problem : MDP와 구조는 그대로
New twist : T(전이함수)와 R(보상함수)를 사전에 모른다.
예시 2가지
-
Google DeepMind Atari Agent (2015) : 게임 화면 픽셀만 보고 스스로 Atari 게임을 사람 수준 이상으로 플레이하는 법을 배운다.
-
OpenAI 로봇 손으로 루빅스 큐브 풀기 (2019) : 환경 모델 없이 수백만 번 시행착오로 학습
|  |
강화학습의 2가지 핵심 과제
Agent
↑ ↓
Reward Action
↓ ↑
Environment
State
1. 가치 함수 추정 (Value Estimation)
- 환경 모델 (T, R)을 모르는 상태에서 경험을 통해 V(s) 또는 Q(s,a)를 추정해야 한다.
2. 탐험과 활용의 균형 (Exploration vs Exploitation)
- Exploitation (활용) : 현재 아는 정보에서 최선의 행동을 선택
- Exploration (탐험) : 아직 안 해본 행동도 시도해서 새 정보 획득
개요
| 구분 | Model-Based Learning | Model-Free Learning |
|---|---|---|
| 방법 | T와 R을 먼저 추정하여 MDP 구성 → 풀기 | MDP 만들지 않고 경험에서 직접 가치/정책 학습 |
| 비유 | 설명서를 만들어서 공부 | 설명서 없이 몸으로 부딪혀서 학습 |
| 예시 | T̂, R̂ 추정 → Value Iteration | Monte-Carlo, TD learning |
Model-based Learning
핵심 개념 : 경험을 통해 근사 MDP 모델을 만들고, 이를 기존 알고리즘 (Value/Policy Iteration)으로 풀기
Step1. 경험적 MDP 모델 학습
- 각
(s, a, s')결과를 빈도 기반으로 카운트 - 정규화하여 전이확률 T̂ 로 추정
- 경험할 때마다
R̂(s, a, s')기록
Step 2. 추정된 MDP를 Value Iteration 또는 Policy Iteration으로 풀기 \(E[A] \approx \sum_{a} \hat{P}(a)\, a\)
Model-free Learning
질문 : T와 R을 모를 때, 경험만으로 V(s)를 추정할 수 있을까?
- 샘플 평균
T를 몰라도 샘플 평균만으로 기댓값을 추정할 수 있다.
Monte-Carlo Evaluation
Monte-Carlo(MC) 방법 : 반복적 랜덤 샘플링으로 수치적 양을 근사
대표 예시 : 원의 넓이를 구하는 MC 시뮬레이션
- 정사각형에 점을 무작위로 뿌림
- 원 안에 들어간 점의 비율로 π 추정
- 샘플이 많아질수록 정확해짐
목표 : 정책 π 하에서 각 상태의 가치 계산
방법 : 관찰한 샘플의 평균을 구함
Return G의 정의 : 에피소드 종료까지의 할인된 누적 보상 $$ G_t = r_{t+1}
- \gamma r_{t+2}
- \gamma^2 r_{t+3}
- \cdots
- \gamma^{T-1-t} r_T $$
MC의 핵심 : 가치 = 그 상태에서 출발한 평균 Return
- 정책 π에 따라 행동
- 상태 s를 방문할 때마다 에피소드 끝까지의 G 계산
- G들의 평균 = V(s)
- 기본 구현 방법
중복 평균(Incremental Mean) 버전 $$ V(s) \leftarrow V(s)
- \frac{1}{N(s)} \left( G - V(s) \right) $$
학습률(α) 버전 (실용적으로 더 많이 씀): $$ V(s) \leftarrow V(s)
- \alpha \left( G - V(s) \right) $$
- MC의 장단점
장점 : Model-Free (T,R 불필요), 샘플 에피소드만으로 올바른 값에 수렴
단점 : 완전한 에피소드 필요 (끝까지 가야 G 계산 가능), 상태 간 연결 정보를 낭비, 학습 속도가 느림.
이 단점을 해결하는 방법으로 TD (Temporal Difference)
Temporal Difference Evaluation (TD)
Recap : Policy Evaluation
-
정책 π에 대한 Bellman 기대 방정식:
- 상태 간 연결 구조를 완전히 활용한다.
- DP(Dynamic Programming)는 이걸 정확히 계산하지만 T,R이 필요
$$
\mathbb{E} \left[ R(s,\pi(s),s’) + \gamma V^\pi(s’) \right] $$
핵심 질문 : 샘플링으로 같은 목표를 달성할 수 있을까?
MC vs TD
- MC : V(s) ← V(s) + α(G - V(s))
- 에피소드 끝까지의 실제 누적 보상
- TD : V(s) ← V(s) + α(R(s,a,s’) + γV(s’) - V(s))
- 한 스텝만 가고 V(s’)로 미래 추정
- 장점 : 매 step마다 가능하고, Non-terminate한 상황에서도 가능
- 효율성도 좋고, 상태 연결도 활용한다.
TD의 Target \(R(s,a,s′)+γV(s′)\)
-
TD의 핵심 아이디어
- 기댓값 대신 전이 샘플 하나를 사용해서 업데이트
Bootstrapping vs Sampling
- Bootstrapping : 추정값으로 또 다른 추정을 하는가?
- MC : X, TD / DP(Value/Policy iteration) : O
- Sampling : 샘플 기반으로 업데이트를 하는가?
- MC / TD : O, DP : X
Q-learning
V(s)에서 Q(s,a)로 왜 넘어가는가?
Value Iteration \(V^*(s) = \max_a \sum_{s'} P(s' \mid s,a) \Bigl( R(s,a,s') + \gamma V^*(s') \Bigr)\)
Policy Extraction \(\pi^*(s) = \arg\max_a \sum_{s'} P(s' \mid s,a) \Bigl( R(s,a,s') + \gamma V^*(s') \Bigr)\)
- 이 식을 계산하기 위해서는 **
P(s'|s, a)를 알아야 한다.- 모델이 필요
해결책 : Q-value 사용 \(Q^*(s,a) = \sum_{s'} P(s' \mid s,a) \left( R(s,a,s') + \gamma \max_{a'} Q^*(s',a') \right)\)
\[\pi^*(s) = \arg\max_a Q^*(s,a) \qquad\]- Q를 쓰면 T가 필요 없다.
- Q(s,a)는 상태 s에서 행동 a를 했을 때 얼마나 좋은가?를 선택하는 것으로
- 전이 확률과 보상이 이미 Q 값 안에 녹아있다.
Q-Learning 업데이트 공식 : TD Target에서 max(a’)을 쓰느 것이 특징
- TD의 V(s) 업데이트를 그대로 Q(s,a)에 적용
- TD(V): V(s) ← V(s) + α[R(s,a,s’) + γV(s’) - V(s)]
- Q-learning: Q(s,a) ← Q(s,a) + α[Target - Q(s,a)]
- where Target = R(s,a,s’) + γ max_{a’} Q(s’, a’)
- 공식 전체
Q(s,a) ← Q(s,a) + α [ R(s,a,s') + γ max Q(s',a') - Q(s,a) ]
↑ ↑ ↑ a'↑ ↑
현재 추정값 현재 추정값 지금 받은 다음 상태에서 현재 추정값
(업데이트 후) (업데이트 전) 즉시 보상 가장 좋은 행동의
Q값 (미래 가치)
Exploration vs Exploitation
순수하게 greedy 하게만 행동하면? (탐험-활용 딜레마)
- 처음에 좋아보이는 행동만 계속하고, 더 좋은 행동을 영원히 발견 못 할수도 있음.
해결책 : ε-Greedy 탐험 $$ \pi(a \mid s) = \begin{cases} \frac{\varepsilon}{|A|}
-
(1-\varepsilon), & \text{if } a = \arg\max_{a} Q(s,a) \[6pt] \frac{\varepsilon}{|A|}, & \text{otherwise} \end{cases} $$
- 확률 (1-ε) : 현재 최선의 행동 선택 (Exploitation)
- 확률 ε : 랜덤 행동 선택 (Exploration)
실용적으로는 초기에 ε를 크게 설정하고, 학습이 진행될수록 점점 줄여나간다.
Q-Learning 알고리즘 전체
Q(s,a) 테이블 초기화 (모두 0으로, terminal 상태는 0 고정)
각 에피소드마다 반복:
초기 상태 S 설정
에피소드 각 스텝마다:
ε-greedy 정책으로 Q에서 행동 A 선택
행동 A 실행, 보상 R과 다음 상태 S' 관찰
Q(S,A) ← Q(S,A) + α[R + γ max_a Q(S',a) - Q(S,A)]
S ← S'
until S가 terminal 상태
Q-Learning 수렴 정리
-
정리 (Theorem) : 다음 조건 하에서
Q(s,a) -> Q*(s,a)수렴-
모든 (s,a)가 무한히 자주 방문됨 (ε-greedy가 이를 보장)
-
정책이 greedy 정책에 수렴 \(\lim_{k \to \infty} \pi_k(a \mid s) = \mathbf{1} \left( a = \arg\max_{a'} Q^{\pi_k}(s,a') \right)\)
-
학습률 α가 너무 크지도 작지도 않아야 함 \(\sum_{t=0}^{\infty} \alpha_t(s,a) = \infty \qquad \text{(충분히 학습)}\)
\[\sum_{t=0}^{\infty} \alpha_t^2(s,a) < \infty \qquad \text{(결국 수렴)}\]
-
왜 근사가 필요한가?
- 문제 : 상태공간이 너무 크면 Q-table을 만들 수가 없다.
Approximate Q-Learning
해결책 : Q(s,a)를 함수 근사로 표현
- 선형 Q-함수
예를 들어 팩맨 게임에서:
- 행동 a를 한 후 가장 가까운 음식까지의 거리
- 행동 a를 한 후 가장 가까운 유령까지의 거리
- 배우는 것 : 각 feature들의 가중치
요약 : 세 가지의 Q-Learning의 비교
| Vanilla Q-learning | Approximate Q-learning | DQN | |
|---|---|---|---|
| 표현 방식 | Q-table | 선형 가치 함수 | 심층 신경망 |
| 상태 공간 | 소규모 | 중간 | 대규모 |
| 특징 함수 | 없음 | 사람이 설계 | 자동 학습 |
|  |