Study
RL · Study

4. Model-Free Reinforcement Learning 정리

Unknown MDP에서 MC, TD, Sarsa, Q-Learning, Double Q-Learning이 가치를 추정하는 방식을 정리한다.

reinforcement-learningmonte-carlotemporal-differencesarsaq-learningdouble-q-learning

1. DP와 RL의 차이

DP는 환경 모델을 알고 있을 때 벨만 방정식을 계산으로 푸는 방법이다. 반면 RL은 상태 전이 확률과 보상 함수를 모르는 상태에서 직접 경험한 sample로 가치와 정책을 추정한다.

1.1 Full Backup과 Sample Backup

DP는 가능한 모든 다음 상태를 고려하는 full backup을 사용한다.

Full backup in dynamic programming

RL은 실제로 관찰한 하나의 transition을 이용하는 sample backup을 사용한다.

Sample backup in reinforcement learning

1.2 Solving과 Estimating

모델을 알면 벨만 최적 방정식을 직접 풀 수 있지만, 모델을 모르면 경험을 통해 q*에 가까운 값을 추정해야 한다.

Solving Bellman optimality equation in DP

Estimating optimal action values in RL

2. Generalized Policy Iteration

GPI는 정책 평가와 정책 개선이 서로 영향을 주며 반복되는 구조다. 대부분의 RL 알고리즘은 이 구조를 각자의 방식으로 구현한다.

Generalized policy iteration loop

3. Monte Carlo Method

Monte Carlo 방법은 episode가 끝난 뒤 실제 return을 계산해 가치 함수를 업데이트한다. 모델은 필요 없지만 episode 종료 전에는 업데이트할 수 없고, return의 분산이 클 수 있다.

Monte Carlo method overview

Return equation for Monte Carlo method

Monte Carlo value estimate

모든 return을 저장하지 않기 위해 incremental mean이나 고정 step-size 업데이트를 사용한다.

Incremental mean update

Fixed step size Monte Carlo update

3.1 Exploration과 GLIE

강화학습은 현재 가장 좋아 보이는 행동을 고르는 exploitation과, 더 나은 행동을 찾기 위한 exploration 사이에서 균형을 잡아야 한다.

Epsilon-greedy policy

Epsilon-greedy policy improvement

GLIE는 충분히 오래 모든 행동을 탐험하면서도, 최종적으로는 greedy policy에 가까워지는 조건이다.

GLIE condition

GLIE Monte Carlo control

Monte Carlo method pseudo code

3.2 Off-Policy 평가와 Importance Sampling

target policy와 behavior policy가 다를 때는, behavior policy로 모은 episode를 target policy 기준의 평가에 그대로 사용할 수 없다. 이때 importance sampling ratio로 두 정책의 확률 차이를 보정한다.

Importance sampling summary

Importance sampling distribution comparison

4. Temporal Difference Learning

TD는 MC처럼 sample을 사용하지만 episode가 끝나기 전에도 다음 상태의 추정값으로 바로 업데이트한다. 즉 sample 기반이면서 bootstrapping을 사용한다.

Temporal Difference learning overview

5. Bias와 Variance

MC는 실제 return을 쓰므로 편향은 작지만 분산이 크다. TD는 추정값으로 target을 만들기 때문에 약간의 편향이 생기지만 분산은 낮고 업데이트가 빠르다.

Monte Carlo bias and variance

Temporal Difference bias and variance

구분몬테카를로 (MC)시간차 학습 (TD)
편향/분산높은 분산, 제로 편향낮은 분산, 약간의 편향
업데이트 시점에피소드 종료 후 업데이트매 스텝 업데이트
업데이트 목표실제 반환값 $G_t$TD 타겟
환경 요구사항종료 환경(Episodic)에 적합종료 및 지속(Continuing) 환경 모두 가능
초기값 민감도낮음높음
메모리/계산비교적 많이 필요비교적 적게 필요
수렴 속도느릴 수 있음실전에서는 보통 더 빠름

6. Sarsa와 Q-Learning

Sarsa는 실제로 다음에 선택한 행동을 기준으로 업데이트하는 on-policy 방법이다. 탐험 정책의 영향이 가치에 반영되므로 위험한 환경에서 더 보수적인 경로를 배울 수 있다.

Sarsa overview

Sarsa pseudo code

Q-Learning은 가능한 다음 행동 중 최대 Q값을 target으로 쓰는 off-policy 방법이다. 학습 중 탐험을 하더라도 target은 greedy policy를 기준으로 잡는다.

Q-learning overview

Q-learning pseudo code

구분SarsaQ-Learning
학습 방식On-PolicyOff-Policy
업데이트 기준실제 다음 행동가능한 최적 다음 행동
탐험의 영향가치에 반영됨목표 가치에는 덜 반영됨
경로 성향더 안전한 경로 선호더 빠른 최적 경로 선호

Sarsa vs Q-learning cliff walking comparison

6.1 Expected Sarsa

Expected Sarsa는 실제 다음 행동 하나 대신 정책이 선택할 수 있는 모든 다음 행동의 기대 Q값을 사용한다.

Expected Sarsa update

구분SarsaExpected SarsaQ-Learning
업데이트 목표$Q(S^{\prime}, A^{\prime})$$\mathbb{E}[Q(S^{\prime}, A^{\prime})]$$\max_{a^{\prime}} Q(S^{\prime}, a^{\prime})$
분산높음낮음낮음
학습 방식On-Policy주로 On-PolicyOff-Policy
계산 복잡도낮음높음낮음

7. Double Q-Learning

Q-Learning의 max 연산은 noisy estimate에서 과대평가 편향을 만들 수 있다. Double Q-Learning은 행동 선택과 평가를 두 Q함수로 나누어 이 문제를 줄인다.

Maximization bias in Q-learning

Double Q-learning action selection

Double Q-learning value evaluation

Double Q-learning pseudo code

이번 글의 핵심은 모델을 모르는 환경에서도 경험 sample을 이용해 GPI를 수행할 수 있다는 점이다. MC, TD, Sarsa, Q-Learning은 모두 평가와 개선을 어떤 target으로 섞을지에 대한 서로 다른 선택이다.