RL from Basics
1. 강화학습이란Permalink
- 1.1 지도학습과 강화학습
- 1.2 순차적 의사결정 문제
- 1.3 보상
- 보상
- 어떻게X, 얼마나O
- 누적 보상
- 스칼라 vs. 벡터
- 희소하고 지연된 보상
- 밸류 네트워크
- 1.4 에이전트와 환경
- 에이전트
- 환경
- 상태
- 상태 변화 (환경의 역할)
- 연속적 vs. 이산적
- 1.5 강화학습의 위력
- 병렬성의 힘
- 자가학습 (Self-Learning)의 매력
2. 마르코프 결정 프로세스 (Markov Decision Process)Permalink
- 2.1 마르코프 프로세스 (Markov Process)
- 마르코프 프로세스 정의
- 미리 정의된 확률 분포를 따라서 상태와 상태사이를 이동해 다니는 여정
MP≡(S,P)
- 미리 정의된 확률 분포를 따라서 상태와 상태사이를 이동해 다니는 여정
- 마르코프 프로세스 구성요소
- 상태의 집합 S
- 전이 확률 행렬 PSS′
- 상태의 집합 S
- 마르코프 성질 : 미래는 오로지 현재에 의해 결정됨
P[St+1∣St]=P[St+1∣S1,S2,⋯,St]
- 마르코프 프로세스 정의
- 2.2 마르코프 리워드 프로세스 (Markov Reward Process)
- 마르코프 리워드 프로세스 정의
- 마르코프 프로세스에 보상의 개념이 추가
MRP≡(S,P,R,γ)
- 마르코프 프로세스에 보상의 개념이 추가
- 마르코프 리워드 프로세스 구성요소
- 상태의 집합 S
- 전이 확률 행렬 PSS′
- 보상함수
R=E[Rt∣St=s] - 감쇠인자 γ
- 상태의 집합 S
- 에피소드
- 리턴 : 감쇠된 보상의 합
Gt=Rt+1+γRt+2+γ2Rt+3+⋯
- 에피소드
- 미래에 받을 보상의 합
- 감쇠인자는 왜 필요할까?
- 수학적 편의성
- 사람의 선호 반영 (즉각적인 보상 선호)
- 미래에 대한 불확실성 반영
- 밸류와 기댓값
- 에피소드 샘플링 (Monte-Carlo 접근법)
- 리턴은 동일 상태에서도 매번 바뀔 수 있음
- 기댓값 사용 필요
- 상태 가치 함수
- 상태 가치 함수
v(s)=E[Gt∣St=s]
- 마르코프 리워드 프로세스 정의
- 2.3 마르코프 결정 프로세스 (Markov Decision Process)
- 마르코프 결정 프로세스 정의
- 마르코프 리워드 프로세스에 에이전트 개념이 추가
MDP≡(S,A,P,R,γ)
- 마르코프 리워드 프로세스에 에이전트 개념이 추가
- 마르코프 결정 프로세스 구성요소
- 상태의 집합 S
- 액션의 집합 A
- 전이 확률 행렬
PaSS′=P[St+1=s′∣St=s,At=a] - 보상함수
Ras=E[Rt+1∣St=s,At=a] - 감쇠인자 γ
- 상태의 집합 S
- 정책함수와 2가지 가치함수
- 정책함수 : 상태 s에서 액션 a를 선택할 확률
π(a∣s)=P[At=a∣St=s] - 상태 가치함수
vπ(s)=Eπ[rt+1+γrt+2+γ2rt+3+⋯∣St=s]=Eπ[Gt∣St=s] - 액션 가치함수
qπ(s,a)=Eπ[Gt∣St=s,At=a]
- 정책함수 : 상태 s에서 액션 a를 선택할 확률
- 마르코프 결정 프로세스 정의
- 2.4 Prediction과 Control
- Prediction : 정책 π가 주어졌을 때 각 상태의 밸류를 평가하는 문제
- Control : 최적 정책 π∗ 를 찾는 문제 (누구를 만나도 다 이기는 정책)
- 최적 가치함수
3. 벨만 방정식Permalink
- 3.1 벨만 기대 방정식
- 모델 프리 : 경험을 통해 학습 (모델을 모르기 때문에 경험을 기반으로 학습해야 함)
- 모델 기반 : Planning (모델을 알고 있으니까 계획만 수립해도 실제 가치를 평가할 수 있음)
- 재귀함수
- 0단계
vπ(st)=Eπ[rt+1+γvπ(st+1)]
qπ(st,at)=Eπ[rt+1+γqπ(st+1,at+1)] - 1단계
vπ(s)=∑a∈Aπ(a∣s)qπ(s,a)
qπ(s,a)=ras+γ∑s′∈SPass′vπ(s′) - 2단계
vπ(s)=∑a∈Aπ(a∣s)(ras+γ∑s′∈SPass′vπ(s′))
qπ(s,a)=ras+γ∑s′∈SPass′∑a′∈Aπ(a′∣s′)qπ(s′,a′)
- 3.2 벨만 최적 방정식
- 최적 밸류와 최적 정책
v∗(s)=maxπvπ(s)
q∗(s,a)=maxπqπ(s,a) - 0단계
v∗(st)=maxaE[rt+1+γv∗(st+1)]
q∗(st,at)=E[rt+1+γmaxa′q∗(st+1,a′)] - 1단계
v∗(s)=maxaq∗(s,a)
q∗(s,a)=ras+γ∑s′∈SPass′v∗(s′) - 2단계
v∗(s)=maxa[ras+γ∑s′∈SPass′v∗(s′)]
q∗(s,a)=ras+γ∑s′∈SPass′maxa′q∗(s′,a′)
- 최적 밸류와 최적 정책
4. MDP를 알 때의 플래닝Permalink
- 4.1 밸류 평가하기 - 반복적 정책 평가
- MDP를 안다는 것
- 보상함수를 알고 있음
- 전이확률행렬을 알고 있음
- S,A,P,R,γ가 주어짐
- 플래닝 : MDP에 대한 모든 정보를 알 때, 이를 이용하여 정책을 개선해나가는 과정
- 테이블 기반 방법론
- MDP를 안다는 것
- 4.2 최고의 정책 찾기 - 정책 이터레이션
- 벨만 기대 방정식 1단계 활용
- 그리디 정책 (Greedy Policy)
- 정책 평가 : 반복적 정책 평가
V→Vπ - 정책 개선 : 그리디 정책 생성
π→πgreedy - Early Stopping
- 4.3 최고의 정책 찾기 - 밸류 이터레이션
- MDP를 모두 아는 상황에서는 최적 밸류를 알면 최적 정책을 얻을 수 있음
- 벨만 최적 방정식 1단계 활용
- 문제와 MDP 조건에 따른 구분
- 문제가 작다
- MDP를 안다
- 4장
- MDP를 모른다
- 5~6장
- MDP를 안다
- 문제가 크다
- 7~9장
- 문제가 작다
5. MDP를 모를 때 밸류 평가하기Permalink
- 5.1 몬테카를로 학습
- 모델 프리
- 모델 : 환경의 모델
- 모델 프리에서의 Prediction
- 몬테카를로
- Temporal Difference
- 가치 함수 : 리턴의 기댓값 (가치 함수의 정의)
- 몬테카를로 방법론 예시 : MCTS (Monte Carlo Tree Search), MCMC (Markov Chain Monte Carlo)
- 대수의 법칙 (Law of large numbers)
- 몬테카를로 학습 알고리즘1 : 테이블 업데이트
- 테이블 초기화, 경험 쌓기, 테이블 업데이트, 밸류 계산 (에피소드 N개가 모두 끝난 뒤 평균 계산)
vπ(st)≅V(st)N(st)
V(st)←V(st)+α(Gt−V(st))
- 테이블 초기화, 경험 쌓기, 테이블 업데이트, 밸류 계산 (에피소드 N개가 모두 끝난 뒤 평균 계산)
- 몬테카를로 학습 알고리즘2 : 조금씩 업데이트
- 에피소드가 한 개 끝날때마다 테이블 업데이트
- 몬테카를로 코드
- 모델 프리
- 5.2 Temporal Difference 학습
- TD 학습
- MC는 반드시 종료하는 MDP에만 사용 가능
- TD는 추측을 추측으로 업데이트 하는 방식 (Bootstrap)
- 리턴은 가치 함수의 불편 추정량 (편향되지 않은 추정량)
- 벨만 기대 방정식의 TD Target 활용
- 실제 TD Target (불편 추정량)과 우리가 사용한 TD Target (편향)은 같지 않음
- 이론적 배경
vπ(st)=Eπ[Gt]
Gt 는 vπ(st) 의 불편 추정량
vπ(st)=Eπ[rt+1+γvπ(st+1)]
TD Target : rt+1+γvπ(st+1) - 알고리즘
MC : V(st)←V(st)+α(Gt−V(st))
TD : V(st)←V(st)+α(rt+1+γV(st+1)−V(st)) - TD 코드
- TD 학습
- 5.3 몬테카를로 vs TD
- 학습 시점
- Episodic MDP : MC, TD 사용 가능
- Non-Episodic MDP : TD만 사용 가능
- 편향성 (Bias)
- MC : 불편 추정량 (가치 함수의 정의로부터 리턴 사용)
- TD : 벨만 기대 방정식으로부터 TD Target 사용, 실제 TD Target (불편 추정량)과 우리가 사용하는 TD Target (편향)은 다른 값
V(st+1)≠vπ(st+1)
- 분산 (Variance)
- MC : 수십 ~ 수백 개의 확률적 결과, 분산이 큼
- TD : 한 Step만 예측, 분산이 작음 (학습에 유리)
- 학습 시점
- 5.4 몬테카를로와 TD의 중간?
- n Step TD
N=n:rt+1+γrt+2+γ2rt+3+⋯+γnV(st+n)
- n Step TD
6. MDP를 모를 때 최고의 정책 찾기Permalink
- 6.1 몬테카를로 컨트롤
- 몬테카를로 컨트롤, SARSA, Q Learning
- 모델 프리에서 정책 이터레이션을 사용할 수 없는 이유 : 1) 보상함수, 전이확률행렬을 모름 (벨만 기대 방정식에서 사용됨), 2) 정책 개선 단계에서 그리디 정책을 만들 수 없음
- MDP를 모르기 때문에 보상과 전이 확률 행렬을 알 수 없음
vπ(s)=∑a∈Aπ(a∣s)(ras+γ∑s′∈SPass′vπ(s′)) - 해결방법
- 평가 자리에 MC 사용
- V 대신 Q 사용
- Greedy 대신 ϵ-Greedy 사용 (Decaying ϵ-Greedy)
- 몬테카를로 컨트롤 구현
- 한 에피소드의 경험 축적
- 경험한 데이터로 q(s,a) 값 업데이트 (정책 평가)
- 업데이트 된 q(s,a) 테이블로 ϵ-Greedy 수행 (정책 개선)
- 모델 프리 MC
- 6.2 TD 컨트롤 1 - SARSA
- MC 대신 TD 사용해서 정책 평가
- 히스토리 전체가 아니라 샘플 트랜지션 하나만 생기면 업데이트 가능
- MC vs. TD
TD로 V 학습 : V(S)←V(S)+α(R+γV(S′)−V(S))
TD로 Q 학습 : Q(S,A)←Q(S,A)+α(R+γQ(S′,A′)−Q(S,A)) - 모델 프리 SARSA
- 6.3 TD 컨트롤 2 - Q러닝
- On-Policy : Target Policy와 Behavior Policy가 같은 경우
- Off-Policy : Target Policy와 Behavior Policy가 다른 경우
- Target Policy : 강화하고자 하는 목표가 되는 정책
- Behavior Policy : 환경과 상호작용하며 경험을 쌓고 있는 정책
- Off-Policy의 장점
- 과거의 경험 재사용 가능
- 사람의 데이터로부터 학습 가능
- 일대다, 다대일 학습 가능
- 이론적 배경
q∗(s,a)=maxπqπ(s,a)
π∗=argmaxaq∗(s,a)
q∗(s,a)=ras+γ∑s′∈SPass′maxa′q∗(s′,a′)
q∗(s,a)=Es′[r+γmaxa′q∗(s′,a′)]
SARSA : Q(S,A)←Q(S,A)+α(R+γQ(S′,A′)−Q(S,A))
Q Learning : Q(S,A)←Q(S,A)+α(R+γmaxA′Q(S′,A′)−Q(S,A)) - SARSA vs. Q Learning
- Behavior Policy : SARSA, Q Learning 모두 ϵ-Greedy 사용
- Target Policy : SARSA는 ϵ-Greedy, Q Learning은 Greedy 사용
SARSA : qπ(st,at)=Eπ[rt+1+γqπ(st+1,at+1)]
Q Learning : q∗(s,a)=Es′[r+γmaxa′q∗(s′,a′)] - Eπ는 정책함수 π를 따라가는 경로에 대해 기댓값 계산
- Es′는 정책함수 π와 전혀 관련없음 (어떠한 정책을 사용해도 무관)
- SARSA
- 벨만 기대 방정식에 기원을 두고 있음
- 2가지 확률적인 요소 포함
- π : 정책에 의한 확률적인 요소
- 전이확률행렬 : 환경에 의한 확률적인 요소
- Q Learning
- 벨만 최적 방정식에 기원을 두고 있음
- π와 관련 없음 : 어떤 정책을 사용해도 상관없음
- 최적 정책은 환경에 의존적임 : 환경이 정해지면 그에 따라 최적 정책도 결정됨
- 모델 프리 Q Learning
7. Deep RL 첫 걸음Permalink
- 7.1 함수를 활용한 근사
- 테이블 방식 접근의 한계
- 저장 용량의 한계 : 이산적 상태 vs. 연속적인 상태 공간
- 무한의 상태 방문 불가 : 학습 불가
- 근사 함수
f(s)=vπ(s) - 최소제곱법
- 평균제곱오차 (Mean Squared Error)
- 피팅
- 다항함수
f(x)=a0+a1x+a2x2+⋯+anxn - 함수의 피팅
- 함수에 데이터를 기록한다.
- 데이터 점들을 가장 가깝게 지나도록 함수를 그려본다.
- 함수의 파라미터 값을 찾는다.
- 함수를 학습한다.
- 차수가 높은게 무조건 유리하지 않은 이유
- 데이터에 노이즈가 섞여 있음
- 데이터에 확률적 요소가 포함되어 있음
- 오버 피팅 : 함수가 노이즈에 피팅해버림
- 언더 피팅 : 함수의 유연성이 부족해 데이터와의 에러가 큼
- 함수의 장점
- 일반화
- 학습의 결과물을 저장하는데 필요한 용량이 적음
- 테이블 방식 접근의 한계
- 7.2 인공 신경망의 도입
- 인공신경망의 구성요소
- Input/Output Layer
- Hidden Layer : Node로 구성
- Node의 동작
- Linear Combination : Input의 선형 결합을 통해 새로운 Feature 생성 (Input보다 한층 더 추상화된 Feature)
- Non-Linear Activation : Input과 Output의 비선형 관계 대응 (ReLU, Sigmoid 등)
- ReLU (Rectified Linear Unit)
- Loss Function
- 인공신경망의 학습 : 손실함수의 값이 줄어들도록 파라미터를 수정하는 것
- w가 L(w)에 미치는 영향력 확인 : 미분 필요
- 편미분 (Partial Derivative)
- Gradient : 편미분의 벡터 모음
- 업데이트 크기 : Learning Rate (Step Size)로 결정
- Gradient
∇wL(w)=(∂L(w)∂w1,∂L(w)∂w2,⋯,∂L(w)∂wn) - Gradient Descent
w′=w−α∗∇wL(w) - 학습 절차
- PyTorch 등에서 자동 미분 라이브러리 활용
- 역전파 (Backpropagation)을 통해 함수의 Gradient를 빠르게 계산
- 미니 배치 활용
- 신경망 구현 사례
- 인공신경망의 구성요소
8. 가치 기반 에이전트Permalink
- 8.1 밸류 네트워크의 학습
- 가치 기반 에이전트
- 정책 기반 에이전트
- Actor-Critic
- 손실함수의 정의에 기댓값 사용 이유 : 존재하는 모든 상태를 방문할 수 없음, 정책에 의해 자주 방문하는 상태의 가중치가 높아짐 (중요한 상태의 밸류를 더 정확하게 계산할 수 있음)
- 정책 π을 이용한 샘플 추출 필요
- 정답에 해당하는 밸류를 모르기 때문에 몬테카를로 방법의 리턴이나 TD의 TD 타깃 학습 필요
- 정답에 해당하는 리턴이나 TD 타깃은 상수임에 주의 : 타깃이 변할 경우 학습이 불안정하게 됨, 실제 구현시에는 TD 타깃에 detach 함수 호출하면 됨
- 밸류 네트워크
L(θ)=Eπ[(vtrue(s)−vθ(s))2]
∇θL(θ)=−Eπ[(vtrue(s)−vθ(s))∇θvθ(s)]
∇θL(θ)≈−(vtrue(s)−vθ(s))∇θvθ(s)
θ′=θ−α∇θL(θ)
θ′=θ+α(vtrue(s)−vθ(s))∇θvθ(s) : vtrue(s) 모름! - 몬테카를로 리턴
θ′=θ+α(Gt−vθ(st))∇θvθ(st) - TD Target
θ′=θ+α(rt+1+γvθ(st+1)−vθ(st))∇θvθ(st)
- 8.2 딥 Q러닝
- 가치 기반 에이전트
- 가치 기반 에이전트에는 명시적 정책이 따로 없음 : 액션 가치 함수 q(s,a) 이용
- 이런 정책 함수를 내재된 정책이라고 함
- 이론적 배경
Q∗(s,a)=Es′[r+γmaxa′Q∗(s′,a′)]
Q(s,a)←Q(s,a)+α(r+γmaxa′Q(s′,a′)−Q(s,a))
L(θ)=E[(r+γmaxa′Qθ(s′,a′)−Qθ(s,a))2]
θ′=θ+α(r+γmaxa′Qθ(s′,a′)−Qθ(s,a))∇θQθ(s,a) - 미니 배치 : 기댓값 연산자를 없애기 위해 여러개의 샘플을 뽑아서 그 평균을 이용해 업데이트
- 미니 배치 사이즈
- 딥 Q러닝 Pseudo Code
- 1) Qθ 의 파라미티 θ 초기화
- 2) 에이전트의 상태 s 를 초기화 (s←s0)
- 3) 에피소드가 끝날때까지 A~E 반복
- A) Qθ 에 대한 ϵ−greedy 를 이용해 액션 a 선택
- B) a 를 실행하여 r 과 s′ 관측
- C) s′ 에서 Qθ 에 대한 Greedy 를 이용해 액션 a′ 선택
- D) θ 업데이트 : θ←θ+α(r+γQθ(s′,a′)−Qθ(s,a))∇θQθ(s,a)
- E) s←s′
- A) Qθ 에 대한 ϵ−greedy 를 이용해 액션 a 선택
- 에피소드가 끝나면 다시 2로 돌아가서 θ 가 수렴할 때까지 반복
- 1) Qθ 의 파라미티 θ 초기화
- Off-Policy 학습 : 실행할 액션을 선택하는 행동 정책은 ϵ-Greedy 정책, 학습 대상인 타깃 정책은 Greedy 정책 사용
- 실제 구현시에는 3-D 대신 L(θ) 를 사용하면 됨 (라이브러리가 미분 수행)
L(θ)=(r+γmaxa′Qθ(s′,a′)−Qθ(s,a))2 - Experience Replay
- 경험 : 여러개의 에피소드로 구성
- 에피소드 : 여러개의 상태 전이 (트랜지션)으로 구성
- 상태 전이 : et=(st,at,rt,st+1)
- 상관성 억제 : 다양한 데이터 섞임 (Shuffle)
- 리플레이 버퍼 : 낱개의 데이터 재사용 (선입선출), 가장 최신 N개의 데이터만 유지, 랜덤하게 미니 배치 구성
- 리플레이 버퍼의 장점 : 여러 데이터가 재사용 될 수 있음 (데이터 효율성 향상), 데이터 사이의 상관성을 낮춤
- Off-Policy 알고리즘에만 사용 가능
- Target Network
L(θi)=E[(R+γmaxA′Qθ−i(S′,A′)−Qθi(S,A))2]
Qθ−i : Target Network
Qθi : Q Network
일정 주기마다 θ−i←θi
- 뉴럴 네트워크를 학습할 때 정답지가 자주 변하는 것은 학습의 안정성을 떨어뜨리기 때문
- 정답을 계산할 때 사용하는 타깃 네트워크와 학습을 받고 있는 Q 네트워크를 구분해서 사용
- 타깃 네트워크의 파라미터를 일정 주기마다 업데이트
- DQN 구현 사례
- 가치 기반 에이전트
9. 정책 기반 에이전트Permalink
- 9.1 Policy Gradient
- 가치 기반 에이전트 : 결정론적 방식으로 액션 결정
- 정책 기반 에이전트 : 확률론적 방식으로 액션 결정 (좀 더 유연한 정책)
- 액션 공간이 연속적일 경우 가치 기반 에이전트 사용 불가
- 환경에 숨겨진 정보가 있거나 환경 자체가 변하는 경우, 정책 기반 에이전트는 유연하게 대처 가능
- 정책 기반 에이전트에서 정책 함수의 정답을 구하는 것은 어려움, 손실함수 사용 불가, 정책을 평가하는 기준인 평가함수 J 필요
- 평가함수는 상태의 확률 분포와 가치함수의 곱으로 정의
- Gradient Ascent
J(θ)=Eπθ[∑trt]=vπθ(s0)
J(θ)=∑s∈Sd(s)∗vπθ(s)
θ′←θ+α∇θJ(θ) - 모델 프리의 한계
- 보상함수와 전이확률행렬을 모름
- 모든 상태에 대해 상태가치함수 합산 불가
- 기댓값 연산자를 이용해 샘플 기반 방법론으로 풀이 가능!
- 1-Step MDP
J(θ)=∑s∈Sd(s)∗vπθ(s)
J(θ)=∑s∈Sd(s)∑a∈Aπθ(s,a)∗Rs,a
∇θJ(θ)=∇θ∑s∈Sd(s)∑a∈Aπθ(s,a)∗Rs,a
∇θJ(θ)=∑s∈Sd(s)∑a∈A∇θπθ(s,a)∗Rs,a
∇θJ(θ)=∑s∈Sd(s)∑a∈Aπθ(s,a)πθ(s,a)∇θπθ(s,a)∗Rs,a
∇θJ(θ)=∑s∈Sd(s)∑a∈Aπθ(s,a)∇θlogπθ(s,a)∗Rs,a
∇θJ(θ)=Eπθ[∇θlogπθ(s,a)∗Rs,a] - MDP
∇θJ(θ)=Eπθ[∇θlogπθ(s,a)∗Qπθ(s,a)]
- 보상함수를 Q로 변경
- 9.2 REINFORCE 알고리즘
- 이론적 배경
∇θJ(θ)=Eπθ[∇θlogπθ(s,a)∗Gt]
Qπθ(s,a)=E[Gt∣st=s,at=a]
- Q대신 샘플인 리턴 사용
- 경험을 통해 리턴이 큰 액션의 확률을 증가시키도록 업데이트
- Gradient ascent vs. Gradient descent
- REINFORCE Pseudo Code
- 1) πθ(s,a) 의 파라미터 θ 를 랜덤으로 초기화
- 2) 에피소드가 끝날때까지 A~C 반복
- A) 에이전트의 상태를 초기화 : s←s0
- B) πθ 를 이용하여 에피소드 끝까지 진행 s0,a0,r0,s1,a1,r1,⋯,sT,aT,rT
- C) t=0∼T 에 대해 다음 반복
- Gt←∑Ti=tri∗γi−t
- θ←θ+α∇θlogπθ(st,at)∗Gt : s 에서 a 를 선택할 확률을 Gt 에 비례하게 업데이트
- Gt←∑Ti=tri∗γi−t
- A) 에이전트의 상태를 초기화 : s←s0
- 1) πθ(s,a) 의 파라미터 θ 를 랜덤으로 초기화
- 참고
∇θJ(θ)≠Eπθ[∇θπθ(s,a)∗Gt]
∇θJ(θ)≈Gt∗∇θlogπθ(st,at)
L(θ)=(r+γmaxa′Qθ(s′,a′)−Qθ(s,a))2
∇θL(θ)≈−(r+γmaxa′Qθ(s′,a′)−Qθ(s,a))∇θQθ(s,a)
J(θ)=Gt∗logπθ(st,at) : Maximize 하고 싶은 값 (Gradient Ascent 사용)
J(θ)=−Gt∗logπθ(st,at) : Minimize 하고 싶은 값 (Gradient Descent 사용)
- 이론적 배경
- 9.3 액터-크리틱
- Q 액터-크리틱
∇θJ(θ)=Eπθ[∇θlogπθ(s,a)∗Qπθ(s,a)] - 리턴 대신 Q 사용
- 액터 : 정책 함수의 가치를 학습하는 방향으로 업데이트, 실행할 액션 a 를 선택하는 πθ
- 크리틱 : Q 평가 결과가 좋으면 강화, 안좋으면 약화하는 방식으로 업데이트, 실행할 액션 a 의 밸류를 평가하는 Qw
- Q Actor-Critic Pseudo Code
- 1) 정책, 액션-밸류 네트워크의 파라미터 θ 와 w 초기화
- 2) 상태 s 초기화
- 3) 액션 a∼πθ(a∣s) 를 샘플링
- 4) 에피소드가 끝날때까지 A~E 반복
- A) a 를 실행하여 보상 r 과 다음 상태 s′ 을 얻음
- B) θ 업데이트 : θ←θ+α∇θlogπθ(s,a)∗Qw(s,a)
- C) 액션 a′∼πθ(a′∣s′) 를 샘플링
- D) w 업데이트 : w←w+β(r+γQw(s′,a′)−Qw(s,a))∇wQw(s,a)
- E) a←a′,s←s′
- A) a 를 실행하여 보상 r 과 다음 상태 s′ 을 얻음
- 1) 정책, 액션-밸류 네트워크의 파라미터 θ 와 w 초기화
- 어드밴티지 액터-크리틱
Aπθ(s,a)≡Qπθ(s,a)−Vπθ(s)
Aπθ(s,a) : Advantage
Vπθ(s) : Baseline (기저)
Eπθ[∇θlogπθ(s,a)∗B(s)]=∑s∈Sdπθ(s)∑a∈Aπθ(s,a)∇θlogπθ(s,a)∗B(s)
∑s∈Sdπθ(s)∑a∈Aπθ(s,a)∇θlogπθ(s,a)∗B(s)=∑s∈Sdπθ(s)∑a∈Aπθ(s,a)∇θπθ(s,a)πθ(s,a)∗B(s)
∑s∈Sdπθ(s)∑a∈Aπθ(s,a)∇θlogπθ(s,a)∗B(s)=∑s∈Sdπθ(s)∑a∈A∇θπθ(s,a)∗B(s)
∑s∈Sdπθ(s)∑a∈Aπθ(s,a)∇θlogπθ(s,a)∗B(s)=∑s∈Sdπθ(s)B(s)∑a∈A∇θπθ(s,a)
∑s∈Sdπθ(s)∑a∈Aπθ(s,a)∇θlogπθ(s,a)∗B(s)=∑s∈Sdπθ(s)B(s)∇θ∑a∈Aπθ(s,a)
∑s∈Sdπθ(s)∑a∈Aπθ(s,a)∇θlogπθ(s,a)∗B(s)=∑s∈Sdπθ(s)B(s)∇θ1=0
∴
\nabla_\theta J(\theta)=E_{\pi_\theta}[\nabla_\theta log \pi_\theta(s,a)*A_{\pi_\theta}(s,a)]
A_{\pi_\theta}(s,a)=Q_{\pi_\theta}(s,a)-V_{\pi_\theta}(s)
Q_{\pi_\theta}\approx Q_w
V_{\pi_\theta}\approx V_\phi
- 정책함수 \pi_\theta(s,a) 의 뉴럴넷 \theta
- 액션-가치함수 Q_w(s,a) 의 뉴럴넷 w
- 가치함수 V_\phi 의 뉴럴넷 \phi
- 정책함수 \pi_\theta(s,a) 의 뉴럴넷 \theta
- 어드밴티지 액터-크리틱 Pseudo Code
- 1) 3쌍의 뉴럴넷 파라미터 \theta,w,\phi 초기화
- 2) 상태 s 초기화
- 3) 액션 a \sim \pi_\theta(a\mid s) 를 샘플링
- 4) 에피소드가 끝날때까지 A~F 반복
- A) a 를 실행하여 보상 r 과 다음 상태 s’ 을 얻음
- B) \theta 업데이트 : \theta\leftarrow \theta+\alpha_1\nabla_\theta log \pi_\theta(s,a)* (Q_w(s,a)-V_\phi(s))
- C) 액션 a’ \sim \pi_\theta(a’\mid s’) 를 샘플링
- D) w 업데이트 : w\leftarrow w+\alpha_2(r+\gamma Q_w(s’,a’)-Q_w(s,a))\nabla_w Q_w(s,a)
- E) \phi 업데이트 : \phi\leftarrow \phi+\alpha_3(r+\gamma V_\phi(s’)-V_\phi(s))\nabla_\phi V_\phi(s)
- F) a\leftarrow a’, s\leftarrow s’
- A) a 를 실행하여 보상 r 과 다음 상태 s’ 을 얻음
- 1) 3쌍의 뉴럴넷 파라미터 \theta,w,\phi 초기화
- TD 액터-크리틱
\delta=r+\gamma V(s’)-V(s)
E_\pi[\delta\mid s,a]=E_\pi[r+\gamma V(s’)-V(s)\mid s,a]
E_\pi[\delta\mid s,a]=E_\pi[r+\gamma V(s’)\mid s,a]-V(s)
E_\pi[\delta\mid s,a]=Q(s,a)-V(s)=A(s,a) : \delta 는 A(s,a) 의 불편추정량
\nabla_\theta J(\theta)=E_{\pi_\theta}[\nabla_\theta log \pi_\theta(s,a)*\delta]
- 어드밴티지와 기저
- 상태 분포 : 정책 \theta를 따라서 움직이는 에이전트가 각 상태에 평균적으로 머무는 비율을 나타내는 분포
- 정책 함수, 액션-가치 함수, 가치 함수 3개 학습 필요
- 그라디언트 추정치의 변동성을 줄여줌으로써 효율적인 학습 가능
- TD Actor-Critic Pseudo Code
- 1) 정책, 밸류 네트워크 파라미터 \theta,\phi 초기화
- 2) 액션 a \sim \pi_\theta(a\mid s) 를 샘플링
- 3) 에피소드가 끝날때까지 A~E 반복
- A) a 를 실행하여 보상 r 과 다음 상태 s’ 을 얻음
- B) \delta 계산 : \delta\leftarrow r+\gamma V_\phi(s’)-V_\phi(s)
- C) \theta 업데이트 : \theta\leftarrow \theta+\alpha_1\nabla_\theta log \pi_\theta(s,a)*\delta
- D) \phi 업데이트 : \phi\leftarrow \phi+\alpha_2\delta\nabla_\phi V_\phi(s)
- E) a\leftarrow a’, s\leftarrow s’
- A) a 를 실행하여 보상 r 과 다음 상태 s’ 을 얻음
- 1) 정책, 밸류 네트워크 파라미터 \theta,\phi 초기화
- TD Error의 기댓값이 어드밴티지 (TD Error는 어드밴티지의 불편 추정량)
- TD Error를 이용함으로써 정책 함수, 가치 함수 2개만 학습하면 됨
- TD Actor-Critic 구현 사례
- loss function 계산시, detach() 함수 반영사실에 주의
loss = -torch.log(pi_a) * delta.detach() + F.smooth_l1_loss(self.v(s), td_target.detach())
- delta.detach()는 \delta 를 상수처리 해서 업데이트 되지 않도록 하기 위함
- td_target.detach()는 TD Target을 상수처리 해서 업데이트 되지 않도록 하기 위함
- 정답은 그 자리에 가만히 있고, 예측치가 변하도록 하기 위함
- Loss는 정책 네트워크의 손실함수와 밸류 네트워크의 손실함수를 더해서 계산
- loss function 계산시, detach() 함수 반영사실에 주의
- Policy Gradient 알고리즘
\nabla_\theta J(\theta)=E_{\pi_\theta}[\nabla_\theta log \pi_\theta(s,a)* Q_{\pi_\theta}(s,a)] : Policy Gradient Theorem
\nabla_\theta J(\theta)=E_{\pi_\theta}[\nabla_\theta log \pi_\theta(s,a)* G_t] : REINFORCE
\nabla_\theta J(\theta)=E_{\pi_\theta}[\nabla_\theta log \pi_\theta(s,a)* Q_w(s,a)] : Q Actor Critic
\nabla_\theta J(\theta)=E_{\pi_\theta}[\nabla_\theta log \pi_\theta(s,a)* A_w(s,a)] : Advantage Actor Critic
\nabla_\theta J(\theta)=E_{\pi_\theta}[\nabla_\theta log \pi_\theta(s,a)* \delta] : TD Actor Critic
- Q 액터-크리틱
10. 알파고와 MCTSPermalink
- 10.1 알파고
- 학습 : 이세돌과 경기전 기보 기반 학습
- 실시간 플래닝 (MCTS) : 이세돌과 경기중 실시간 플래닝
- 학습 단계
- 지도학습 : \pi_{sl}, \pi_{roll}
\pi_{sl} : 컨볼루션 레이어 (13층), Input Feature (19 * 19 * 48), Output (19 * 19)
\pi_{roll} : 선형결합 레이어 (1층), Input Feature (19 * 19 * 48), Output (19 * 19), \pi_{sl} 의 가벼운 버전 - 강화학습 : \pi_{rl}, v
\pi_{rl} : \pi_{sl} 과 동일, 자신의 과거 모델들과 Self-Play 진행
\nabla_\theta J(\theta)=E_{\pi_\theta}[\nabla_\theta log \pi_\theta(s,a)* G_t] : 보상함수에 REINFORCE 사용
v_{\pi_{rl}}(s)=E_{\pi_{rl}}[G_t\mid s_t=s]
- 지도학습 : \pi_{sl}, \pi_{roll}
- MCTS
- 선택 > 확장 > 시뮬레이션 > 백프로파게이션 반복 진행
- 선택 : 루트 노드에서 출발하여 리프 노드까지 가는 단계
a_t=argmax_a(Q(s_t,a)+u(s_t,a)) : 경험이 쌓일수록 Q(s,a) 의 영향력은 커지고, u(s,a) 의 영향력은 작아짐
Q(s_t,a) : 시뮬레이션 실행 후 얼마나 좋은지 판단
상태 s_{78} 에서 액션 a_{33} 을 선택하는 경험을 총 100번 경험했다면 각 경험마다 리프 노드에 도달할 것이고, 해당 리프 노드가 s_L^1,\cdots,s_L^{100} 일 경우
Q(s_{78},a_{33})=\frac{1}{100}\sum_{i=1}^{100}V(s_L^i)
u(s_t,a) : 시뮬레이션 실행 전 얼마나 좋을 것이라 추측하는지 판단(Prior)
u(s_t,a)\varpropto \frac{P(s,a)}{1+N(s,a)}
P(s,a)=\pi_{sl}(s,a) : 사전 확률 (Prior Probability), 시뮬레이션 해보기 전에 각 액션에 확률 부여 - 확장 : 리프 노드를 실제 트리의 노드로 확장하는 단계
P(s,a)\leftarrow \pi_{sl}(s,a)
N(s,a)\leftarrow 0
Q(s,a)\leftarrow 0 - 시뮬레이션 : 정식 노드가 된 리프 노드의 가치를 평가하는 단계
리프 노드 s_L 부터 시작해서 게임이 끝날때까지 빠르게 시뮬레이션 (\pi_{roll} 활용)하고, 그 결과인 z_L 을 s_L 의 밸류로 활용
밸류 네트워크 v_{rl}(s_L) 을 활용
V(s_L)=\frac{v_{rl}(s_L)+z_L}{2} 을 최종 밸류로 결정 - 백프로파게이션 : 리프 노드에 도달하기까지 지나온 모든 엣지에 대해 Q(s,a) 와 N(s,a) 를 업데이트하는 단계
N(s,a)\leftarrow N(s,a)+1
Q(s,a)\leftarrow Q(s,a)+\frac{1}{N(s,a)}(V(s_L)-Q(s,a)) - 가장 좋은 액션을 고르는 기준? N(s,a) 가 가장 큰 액션
- 신뢰도를 함께 고려하기 위함
- 10.2 알파고 제로
- MCTS : 현재 상태를 인풋으로 받아서 그에 특화된 정책을 내놓는 모듈
- 각각의 데이터 : (s_t,\pi_t,z_t) 로 구성
s_t : t 시점의 상태
\pi_t : s_t 에서 진행한 MCTS가 알려주는 정답 정책
z_t : 게임 결과값 - 위 데이터를 이용해 뉴럴넷 f_\theta 학습
MCTS(s)=(\pi,z)
f_\theta(s)=(p,v)
p\approx \pi
v\approx z - 학습 프로세스
- 1) 상태 s_t 를 f_\theta 에 인풋으로 넣어서 정책 네트워크 아웃풋 p_t 와 밸류 네트워크 아웃풋 v_t 를 계산
- 2) p_t 는 MCTS가 알려주는 확률 분포인 \pi_t 와의 차이를 줄이는 방향으로 업데이트
- 3) v_t 는 경기 결과값인 z_t 와의 차이를 줄이는 방향으로 업데이트
- 1) 상태 s_t 를 f_\theta 에 인풋으로 넣어서 정책 네트워크 아웃풋 p_t 와 밸류 네트워크 아웃풋 v_t 를 계산
- 손실함수
L(\theta)=(z_t-v_t)^2-\pi_t log(p_t)
- 각각의 데이터 : (s_t,\pi_t,z_t) 로 구성
- 알파고 제로에서의 MCTS
- 선택 > 확장 및 평가 > 백프로파게이션 반복 진행
\pi_{sl} 대신 p 사용, v_{rl} 대신 v 사용, \pi_{roll} 은 사용하지 않음 - 확장 단계 : f_\theta 아웃풋인 p 이용해 초기화 진행
- 평가 단계 : f_\theta 아웃풋인 v 이용해 s_L 밸류 평가
- 랜덤 정책을 이용해서 MCTS를 해보고, 그 중에서 결과가 좋았던 액션을 선택 (MCTS가 선생님 역할 수행)
- MCTS 덕분에 뉴럴넷 f_\theta 의 아웃풋 p, v 도 점점 더 정확해짐
- 선택 > 확장 및 평가 > 백프로파게이션 반복 진행
- MCTS : 현재 상태를 인풋으로 받아서 그에 특화된 정책을 내놓는 모듈
11. 블레이드 & 소울 비무 AI 만들기Permalink
- 11.1 블레이드 & 소울 비무
- 거대한 문제 공간
- 실시간 게임이 갖는 제약 (cf. 턴제 게임)
- 물고 물리는 스킬 관계
- 상대방에 관계없는 Robust한 성능
- 11.2 비무에 강화학습 적용하기
- MDP 만들기
- 관측치 (o_t) : o_t,o_{t-1},o_{t-2},\cdots,o_1 를 이용해 상태 s_t 정의 (RNN 기법인 LSTM 이용)
- 액션 (a_t) : a_{skill}, a_{move,target} 도입
- 보상 (r_t) : r_t=r_t^{WIN}+r_t^{HP} 정의 (Optimality와 Frequency 고려)
r_t^{HP}=(HP_t^{ag}-HP_{t-1}^{ag})-(HP_t^{op}-HP_{t-1}^{op}) : 나와 적의 체력 차이
- 관측치 (o_t) : o_t,o_{t-1},o_{t-2},\cdots,o_1 를 이용해 상태 s_t 정의 (RNN 기법인 LSTM 이용)
- 학습 시스템과 알고리즘
- ACER (Actor-Critic with Experience Replay) 활용 : A3C의 Off-Policy 버전 알고리즘
- 학습대상 네트워크 : \pi_{skill}, \pi_{move,target}, Q_{skill}, Q_{move,target}
- 여러개의 정책 네트워크를 학습하는 방법
- 1) 번갈아가며 업데이트하는 방법 : \pi_{skill} 업데이트 후 \pi_{move,target} 업데이트
- 2) 서로 독립을 가정하고 곱셈을 이용해 계산하는 방법 : \pi(a_{skill},a_{move,target}\mid s)=\pi_{skill}(a_{skill}\mid s)* \pi_{move,target}(a_{move,target}\mid s)
- 3) 하나씩 순차적으로 선택하는 방법 : \pi(a_{skill},a_{move,target}\mid s)=\pi_{skill}(a_{skill}\mid s)* \pi_{move,target}(a_{move,target}\mid s,a_{skill})
- 1) 번갈아가며 업데이트하는 방법 : \pi_{skill} 업데이트 후 \pi_{move,target} 업데이트
- 이동 정책 네트워크의 학습 : 한 틱 (0.1초) 동안 움직이는 거리가 매우 제한적이라 한 번 이동 방향이 결정되면, 이후 9틱 동안 같은 방향으로 움직이도록 제한
- ACER (Actor-Critic with Experience Replay) 활용 : A3C의 Off-Policy 버전 알고리즘
- MDP 만들기
- 11.3 전투 스타일 유도를 통한 새로운 방식의 Self-Play 학습
- 보상을 통한 전투 스타일 유도 (보상 조절 방법)
- HP 비율, 시간, 거리 패널티 설정을 통해 공격형, 수비형, 밸런스형 스타일 학습
- 새로운 Self-Play 커리큘럼
- 3가지 스타일의 에이전트가 공통의 풀에서 다양한 스타일의 대전 상대를 만날 수 있도록 설정
- 보상을 통한 전투 스타일 유도 (보상 조절 방법)
Comments