RL with Python and Keras
1. 강화학습 개요
- 순차적 행동 결정 문제의 구성요소
- 상태 (State)
- 행동 (Action)
- 보상 (Reward)
- 정책 (Policy)
- MDP (Markov Decision Process)
2. 강화학습 기초 1: MDP와 벨만 방정식
- MDP의 구성요소
- 상태
$S_t = s$ : 시간 t에서의 상태 - 행동
$A_t = a$ : 시간 t에서의 행동 - 보상 함수
$R^a_s = E[R_{t+1} | S_t=s,A_t=a]$ : 시간 t에서 상태가 s이고 행동이 a일때 에이전트가 받을 보상 - 상태 변환 확률 (State Transition Probability)
$P^a_{ss’} = P[S_{t+1}=s’ | S_t=s,A_t=a]$ : 상태 s에서 행동 a를 취했을 때 다른 상태 s’에 도달할 확률 - 감가율 (Discount Factor)
$\gamma\in[0,1]$
$\gamma^{k-1}R_{t+k}$ : 현재 시간 t로부터 k가 지난후의 보상 - 정책
$\pi(a|s)=P[A_t=a|S_t=s]$ : 시간 t, 상태 s의 에이전트가 있을 때 가능한 행동 중에서 행동 a를 할 확률
- 상태
-
가치함수
$R_{t+1}+R_{t+2}+R_{t+3}+R_{t+4}+R_{t+5}+\cdots$ : 시간 t로부터 에이전트가 행동을 하면서 받을 보상들의 합
$G_t=R_{t+1}+\gamma R_{t+2}+\gamma^2 R_{t+3}+\gamma^3 R_{t+4}+\gamma^4 R_{t+5}+\cdots$ : 시간 t로부터 에이전트가 행동을 하면서 받을 보상들의 반환값
ex) 에피소드를 t=1 ~ 5까지 진행했을 경우, 아래와 같은 5개의 반환값이 생김
$G_1=R_2+\gamma R_3+\gamma^2 R_4+\gamma^3 R_5+\gamma^4 R_6$
$G_2=R_3+\gamma R_4+\gamma^2 R_5+\gamma^3 R_6$
$G_3=R_4+\gamma R_5+\gamma^2 R_6$
$G_4=R_5+\gamma R_6$
$G_5=R_6$
$v(s)=E[G_t|S_t=s]$ : 반환값의 기대값으로 표현된 가치함수
$v(s)=E[R_{t+1}+\gamma R_{t+2}+\gamma^2 R_{t+3}+\gamma^3 R_{t+4}+\gamma^4 R_{t+5}+\cdots|S_t=s]$
$v(s)=E[R_{t+1}+\gamma (R_{t+2}+\gamma R_{t+3}+\gamma^2 R_{t+4}+\gamma^3 R_{t+5}+\cdots)|S_t=s]$
$v(s)=E[R_{t+1}+\gamma G_{t+1}|S_t=s]$
$v(s)=E[R_{t+1}+\gamma v(S_{t+1})|S_t=s]$ : $G_{t+1}$ 은 앞으로 받을 보상에 대한 기대값이기 때문에 가치함수로 표현 가능
$v_\pi(s)=E_\pi[R_{t+1}+\gamma v_\pi(S_{t+1})|S_t=s]$ : 정책을 고려한 가치함수의 표현 (벨만 기대 방정식) - 큐함수
- 행동 가치함수 (큐함수) : 어떤 상태에서 어떤 행동이 얼마나 좋은지 알려주는 함수
$v_\pi(s)=\Sigma_{a\in A}\pi(a|s)q_\pi(s,a)$
$q_\pi(s,a)=E_\pi[R_{t+1}+\gamma q_\pi(S_{t+1},A_{t+1})|S_t=s,A_t=a]$
- 행동 가치함수 (큐함수) : 어떤 상태에서 어떤 행동이 얼마나 좋은지 알려주는 함수
-
벨만 기대 방정식
$v_\pi(s)=E_\pi[R_{t+1}+\gamma v_\pi(S_{t+1})|S_t=s]$ : 벨만 기대 방정식
$v_\pi(s)=\Sigma_{a\in A}\pi(a|s)(R_{t+1}+\gamma \Sigma_{s’\in S}P^a_{ss’}v_\pi(s’))$ : 계산 가능한 벨만 기대 방정식
$v_\pi(s)=\Sigma_{a\in A}\pi(a|s)(R_{t+1}+\gamma v_\pi(s’))$ : 상태 변환 확률이 1인 벨만 기대 방정식 - 벨만 최적 방정식
$v_{k+1}(s)=\Sigma_{a\in A}\pi(a|s)(R^a_s+\gamma v_k(s’))$ : 계산 가능한 형태의 벨만 기대 방정식
$v_\ast(s)=\max_\pi[v_\pi(s)]$ : 최적의 가치함수
$q_\ast(s,a)=\max_\pi[q_\pi(s,a)]$ : 최적의 큐함수
$\pi_\ast(s,a)=\cases{1\space \text{if}\space a=argmax_{a\in A} q_\ast(s,a)\cr 0\space \text{otherwise}}$ : 최적 정책
$v_\ast(s)=\max_a[q_\ast(s,a)|S_t=s,A_t=a]$ : 큐함수 중 최대를 선택하는 최적 가치함수
$v_\ast(s)=\max_a E[R_{t+1}+\gamma v_\ast(S_{t+1})|S_t=s,A_t=a]$ : 벨만 최적 방정식
$q_\ast(s,a)=E[R_{t+1}+\gamma \max_{a’} q_\ast(S_{t+1},a’)|S_t=s,A_t=a]$ : 큐함수에 대한 벨만 최적 방정식
3. 강화학습 기초 2: 그리드월드와 다이내믹 프로그래밍
- 정책 이터레이션
$v_\pi(s)=E_\pi[R_{t+1}+\gamma v_\pi(S_{t+1})|S_t=s]$ : 벨만 기대 방정식을 통한 효율적인 가치함수 계산
$v_\pi(s)=\Sigma_{a\in A}\pi(a|s)(R_{t+1}+\gamma v_\pi(s’))$ : 합의 형태로 표현한 벨만 기대 방정식
$v_{k+1}(s)=\Sigma_{a\in A}\pi(a|s)(R_s^a+\gamma v_k(s’))$ : k번째 가치함수를 통해 k+1번째 가치함수 계산
- 다이나믹 프로그래밍의 한계
- 다이나믹 프로그래밍 : 순차적 행동 결정 문제를 벨만 방정식을 통해 푸는 것
- 계산 복잡도
- 차원의 저주
- 환경에 대한 완벽한 정보 필요
4. 강화학습 기초 3: 그리드월드와 큐러닝
- 강화학습과 정책 평가 1: 몬테카를로 예측
$v_\pi(s)\thicksim \frac {1}{N(s)}\Sigma_{i=1}^{N(s)}G_i(s)$ : 반환값($G$)의 평균으로 가치함수($v$)를 추정
$V_{n+1}=\frac {1}{n}\Sigma_{i=1}^{n}G_i=\frac {1}{n}(G_n+\Sigma_{i=1}^{n-1}G_i)$
$=\frac {1}{n}(G_n+(n-1)\frac {1}{n-1}\Sigma_{i=1}^{n-1}G_i)$
$=\frac {1}{n}(G_n+(n-1)V_n)$
$=V_n+\frac {1}{n}(G_n-V_n)$
$V(s)\gets V(s)+\frac {1}{n}(G(s)-V(s))$
$V(s)\gets V(s)+\alpha(G(s)-V(s))$ - 강화학습과 정책 평가 2: 시간차 예측
$v_\pi(s)=E_\pi[R_{t+1}+\gamma v_\pi(S_{t+1})|S_t=s]$ : 정책을 고려한 가치함수의 표현 (벨만 기대 방정식)
$V(S_t)\gets V(S_t)+\alpha(R+\gamma V(S_{t+1})-V(S_t))$ : 시간차 예측에서 가치함수 업데이트
$R+\gamma V(S_{t+1})$ : 업데이트의 목표
$\alpha(R+\gamma V(S_{t+1})-V(S_t))$ : 업데이트의 크기 - 강화학습과 알고리즘 1: 살사
- 정책 이터레이션 (GPI : Generalized Policy Iteration)
- 정책 이터레이션 (GPI : Generalized Policy Iteration)
$\pi’(s)=argmax_{a \in A} [R_s^a+\gamma P^a_{ss’}V(s’)]$ : GPI의 탐욕 정책 발전
$\pi(s)=argmax_{a \in A} Q(s,a)$ : 큐함수를 사용한 탐욕 정책
$Q(S_t,A_t)\gets Q(S_t,A_t)+\alpha(R+\gamma Q(S_{t+1},A_{t+1})-Q(S_t,A_t))$ : 시간차 예측에서 큐함수 업데이트
$[S_t,A_t,R_{t+1},S_{t+1},A_{t+1}]$ : 시간차 제어에서 사용하는 샘플
- 탐욕정책 : 초기의 에이전트는 탐욕 정책으로 잘못된 학습을 하게 될 가능성이 큼
$\pi(s)=\cases{a^\ast=argmax_{a\in A} Q(s,a), 1-\varepsilon \cr a \ne a^\ast, \varepsilon}$ : $\varepsilon$-탐욕 정책
- 살사 코드
- 에이전트 작동 방식
- 현재 상태에서 $\varepsilon$-탐욕 정책에 따라 행동 선택
- 선택한 행동으로 환경에서 한 타임스텝 진행
- 환경으로부터 보상과 다음 상태 받음
- 다음 상태에서 $\varepsilon$-탐욕 정책에 따라 다음 행동 선택
- $(s,a,r,s’,a’)$을 통해 큐함수 업데이트
- 강화학습과 알고리즘 2: 큐러닝
- 살사
온폴리시시간차 제어 (On-Policy Temporal-Difference Control) 때문에 자신이 행동하는대로 학습- 탐험을 위해 선택한 $\varepsilon$-탐욕 정책때문에 에이전트가 최적 정책을 학습하지 못하는 문제 발생
- 큐러닝
오프폴리시시간차 제어 (Off-Policy Temporal-Difference Control), 또는 큐러닝으로 해결 가능
- 살사
$Q(S_t,A_t)\gets Q(S_t,A_t)+\alpha(R_{t+1}+\gamma max_{a’}Q(S_{t+1},a’)-Q(S_t,A_t))$ : 큐러닝을 통한 큐함수 업데이트
$q^\ast(s,a)=E[R_{t+1}+\gamma max_{a’}q^\ast(S_{t+1},a’)|S_t=s,A_t=a]$ : 큐함수에 대한 벨만 최적 방정식
비슷한 수식들이 여러개 있어 확실한 이해&개념정리 필요!
5. 강화학습 심화 1: 그리드월드와 근사함수
- 근사함수
- 몬테카를로, 살사, 큐러닝의 한계
- 계산 복잡도
- 차원의 저주
- 환경에 대한 완벽한 정보 필요
- 근사함수를 통한 가치함수의 매개변수화
- 몬테카를로, 살사, 큐러닝의 한계
- 인공신경망
- 노드와 활성함수
- 노드의 종류
- 입력층 (Input Layer)
- 은닉층 (Hidden Layer)
- 출력층 (Output Layer)
- 활성함수의 종류
- Sigmoid 함수
$\frac{1}{1+e^{-x}}$ - ReLU 함수
$f(x)=\cases{x, x \geq 0 \cr 0, x < 0}$
- Sigmoid 함수
- 노드의 종류
- 딥러닝
- 특징 추출 (Feature Extraction)
- 신경망의 학습
$오차 = (타깃 - 예측)^2$
$업데이트 값 \varpropto 오차 * 오차 기여도$
- 경사하강법의 종류
- SGD
- RMSprop
- Adam
- 경사하강법의 종류
- 노드와 활성함수
- 케라스
- 딥살사
- 살사의 큐함수 업데이트 식
$Q(S_t,A_t)\gets Q(S_t,A_t)+\alpha(R_{t+1}+\gamma Q(S_{t+1},A_{t+1})-Q(S_t,A_t))$ - 살사의 큐함수 업데이트 식에서 정답
$R_{t+1}+\gamma Q(S_{t+1},A_{t+1})$ - 살사의 큐함수 업데이트 식에서 예측
$Q(S_t,A_t)$ - 딥살사의 오차함수
$MSE = (정답 - 예측)^2 = (R_{t+1}+\gamma Q(S_{t+1},A_{t+1}) - Q(S_t,A_t))^2$ - 딥살사의 활성함수 : 선형함수
- 딥살사 코드
- 살사의 큐함수 업데이트 식
- 정책신경망 (Policy Gradient)
- 정책신경망의 활성함수 : Softmax
$s(y_i)=\frac{e^{y_i}} {\Sigma_j e^{y_j}}$ - 정책의 표현
$정책 = \pi_\theta (a|s) : \theta = 가중치$ - 정책 기반 강화학습의 목표
$maximize J(\theta)$ - 목표함수의 경사에 따라 정책신경망 업데이트
$\theta_{t+1} = \theta_t + \alpha \nabla_\theta J(\theta)$ - 가치함수로 표현한 목표함수의 정의
$J(\theta) = v_{\pi_\theta} (s_0)$ - 목표함수의 미분
$\nabla_\theta J(\theta) = \nabla_\theta v_{\pi_\theta} (s_0)$ - Policy Gradient
$\nabla_\theta J(\theta) = \sum_s d_{\pi_\theta}(s) \sum_a \nabla_\theta \pi_\theta (a|s) q_\pi (s,a)$
$\nabla_\theta J(\theta) = \sum_s d_{\pi_\theta}(s) \sum_a \pi_\theta(a|s) \frac {\nabla_\theta \pi_\theta (a|s)} {\pi_\theta (a|s)} q_\pi (s,a)$
$\nabla_\theta J(\theta) = \sum_s d_{\pi_\theta}(s) \sum_a \pi_\theta(a|s) \nabla_\theta log \pi_\theta (a|s) q_\pi (s,a)$ - 기댓값의 형태로 표현한 목표함수의 미분
$\nabla_\theta J(\theta) = E_{\pi_\theta} [\nabla_\theta log \pi_\theta (a|s) q_\pi (s,a)]$ - Policy Gradient의 업데이트 식
$\theta_{t+1} = \theta_t + \alpha \nabla_\theta J(\theta) \approx \theta_t + \alpha[\nabla_\theta log \pi_\theta (a|s) q_\pi (s,a)]$ - 강화학습의 업데이트 식
$\theta_{t+1} \approx \theta_t + \alpha[\nabla_\theta log \pi_\theta (a|s) G_t]$ - 강화학습 코드
- 에이전트가 환경과 상호작용하는 방법
- 상태에 따른 행동 선택
- 선택한 행동으로 환경에서 한 타임스텝 진행
- 환경으로부터 다음 상태와 보상 받음
- 다음 상태에 대한 행동 선택 (에피소드가 끝날 때까지 반복)
- 환경으로부터 받은 정보를 토대로 에피소드마다 학습 진행
- 보상들의 정산 (반환값)
$G_1=R_2+\gamma R_3+\gamma^2 R_4+\gamma^3 R_5+\gamma^4 R_6$
$G_2=R_3+\gamma R_4+\gamma^2 R_5+\gamma^3 R_6$
$G_3=R_4+\gamma R_5+\gamma^2 R_6$
$G_4=R_5+\gamma R_6$
$G_5=R_6$ - 효율적인 반환값 계산
$G_5=R_6$
$G_4=R_5+\gamma R_5$
$G_3=R_4+\gamma R_4$
$G_2=R_3+\gamma R_3$
$G_1=R_2+\gamma R_2$ - 네트워크 업데이트를 위한 오류함수
$\nabla_\theta log \pi_\theta (a|s) G_t$
$\nabla_\theta [log \pi_\theta (a|s) G_t]$ - 엔트로피
$엔트로피 = -\sum_i p_i log p_i$ - 크로스 엔트로피
$크로스 엔트로피 = -\sum_i y_i log p_i : y_i = 정답$ - Policy Gradient의 크로스 엔트로피
$크로스 엔트로피 = -\sum_i y_i log p_i = -log~p_{action}$ - 강화학습의 업데이트 식
$\theta_{t+1} \approx \theta_t + \alpha[\nabla_\theta log \pi_\theta (a|s) G_t] = \theta_t - \alpha[\nabla_\theta -log \pi_\theta (a|s) G_t]$
- 정책신경망의 활성함수 : Softmax
6. 강화학습 심화 2: 카트폴
- 알고리즘1: DQN
- Playing Atari with Deep Reinforcement Learning
- 경험 리플레이 : 에이전트가 환경에서 탐험하며 얻은 샘플 $(s, a, r, s’)$ 을 메모리에 저장
- 리플레이 메모리 : (과거) 샘플을 저장하는 메모리 → 오프폴리시 알고리즘
- 타깃 신경망
$Q(S_t,A_t)\gets Q(S_t,A_t)+\alpha(R_{t+1}+\gamma max_{a’}Q(S_{t+1},a’)-Q(S_t,A_t))$ : 큐러닝의 큐함수 업데이트 식
$MSE = (정답 - 예측)^2 = (R_{t+1}+\gamma max_{a’}Q(s’,a’,\theta) - Q(s,a,\theta))^2$ : DQN의 오류함수
$MSE = (정답 - 예측)^2 = (R_{t+1}+\gamma max_{a’}Q(S_{t+1},a’,\theta^-) - Q(S_t,A_t,\theta))^2$ : 타깃 네트워크를 이용한 DQN 오류함수 - DQN 코드
- 에이전트가 환경과 상호작용하는 방법
- 상태에 따른 행동 선택
- 선택한 행동으로 환경에서 한 타임스텝 진행
- 환경으로부터 다음 상태와 보상 받음
- 샘플 $(s, a, r, s’)$ 을 리플레이 메모리에 저장
- 리플레이 메모리에서 무작위 추출한 샘플로 학습
- 에피소드마다 타깃 모델 업데이트
- 알고리즘2: 액터-크리틱
- Reinforcement Learning: Introduction
$\theta_{t+1} = \theta_t + \alpha \nabla_\theta J(\theta) \approx \theta_t + \alpha[\nabla_\theta log \pi_\theta (a|s) q_\pi (s,a)]$ : 폴리시 그레디언트의 정책신경망 업데이트 식
$\theta_{t+1} \approx \theta_t + \alpha[\nabla_\theta log \pi_\theta (a|s) G_t]$ : Reinforce 알고리즘의 업데이트 식
$\theta_{t+1} \approx \theta_t + \alpha[\nabla_\theta log \pi_\theta (a|s) Q_w(s,a)]$ : 액터-크리틱 업데이트 식
$오류함수 = 정책\ 신경망\ 출력의\ 크로스\ 엔트로피 * 큐함수(가치신경망\ 출력)$
$A(S_t,A_t)=Q_w(S_t,A_t)-V_v(S_t)$ : 어드밴티지 함수의 정의
$\delta_v=R_{t+1}+\gamma V_v(S_{t+1})-V_v(S_t)$ : 어드밴티지 함수의 정의
$\theta_{t+1} \approx \theta_t + \alpha[\nabla_\theta log \pi_\theta (a|s) \delta_v]$ : 액터-크리틱 업데이트 식
$MSE = (정답 - 예측)^2 = (R_{t+1}+\gamma V_v(S_{t+1})-V_v(S_t))^2$ : 가치신경망의 업데이트를 위한 오류함수 - A2C (Advantage Actor-Critic)
- 액터-크리틱 코드
- 에이전트가 환경과 상호작용하는 방법
- 정책신경망을 통해 확률적으로 행동을 선택
- 선택한 행동으로 환경에서 한 타임스텝 진행
- 환경으로부터 다음 상태와 보상 받음
- 샘플 $(s, a, r, s’)$ 을 통해 시간차 에러를 구하고 어드밴티지 함수 구함
- 시간차 에러로 가치신경망을, 어드밴티지 함수로 정책신경망을 업데이트
$\theta_{t+1} \approx \theta_t + \alpha[\nabla_\theta log \pi_\theta (a|s) \delta_v]$ : 액터 업데이트 식
$\theta_{t+1} \approx \theta_t + \alpha \nabla_\theta [log \pi_\theta (a|s) \delta_v]$ : 액터 업데이트 식 변형
$MSE = (정답 - 예측)^2 = (R_{t+1}+\gamma V_v(S_{t+1})-V_v(S_t))^2$ : 크리틱 오류함수
- A3C (Asynchronous Advantage Actor-Critic)
- Reinforcement Learning: Introduction
7. 강화학습 심화 3: 아타리
- 브레이크아웃 DQN
- 브레이크아웃의 컨볼루션 신경망
- 필터의 개수
- 필터의 크기
- 컨볼루션 연산시 필터가 이동하는 폭 (Strides)
- 활성함수
- DQN 학습 전 준비사항
- Preprocessing
- Frame Skip
- DQN 코드
- 에이전트가 환경과 상호작용하는 방법
- 상태에 따른 행동 선택
- 선택한 행동으로 환경에서 한 타임스텝 진행
- 환경으로부터 다음 상태와 보상 받음
- 샘플 $(s, a, r, s’)$ 을 리플레이 메모리에 저장
- 리플레이 메모리에서 무작위로 추출한 32개의 샘플로 학습
- 50,000 타임스텝마다 타깃 네트워크 업데이트
$MSE = (정답 - 예측)^2 = (R_{t+1}+\gamma max_{a’}Q(S_{t+1},a’,\theta^-) - Q(S_t,A_t,\theta))^2$ : DQN의 오류함수 식
- 후버로스 오류함수
- 텐서보드 사용방법
- 브레이크아웃의 컨볼루션 신경망
- 브레이크아웃 A3C
- DQN의 한계
- 학습에 사용된 샘플끼리의 연관성에 영향을 받음 (경험 리플레이 기반 한계)
- 메모리 사용량 높음 (느린 학습속도 유발)
- A3C (Asynchronous Advantage Actor-Critic) 학습 과정
- 글로벌신경망의 생성과 여러개의 (환경 + 액터러너) 생성
- 각 액터러너는 일정 타임스텝 동안 환경에서 자신의 모델로 샘플 수집
- 일정 타임스텝이 끝나면 각 액터러너는 수집한 샘플로 글로벌 네트워크 업데이트
- 글로벌 네트워크를 업데이트 한 액터러너는 다시 글로벌 네트워크로 자신을 업데이트
- 멀티스레딩
- 하나의 프로그램에서 여러개의 프로세스 생성 : 멀티 프로세싱
- 하나의 프로세스에서 여러개의 스레드 생성 : 멀티 스레딩
- 파이썬에서는 GIL (Global Interpreter Lock) 장치 사용
- A3C 코드
- 액터러너의 Run 함수 순서
- 액터러너의 로컬 네트워크에 따라 액션 선택
- 환경으로부터 다음 상태와 보상 받음
- 샘플 저장
- 에이전트가 목숨을 잃거나 t_max 타임스텝 동안 반복
- 저장한 샘플을 글로벌 네트워크로 보냄
- 글로벌 네트워크는 로컬 네트워크로부터 받은 샘플로 자신을 업데이트
- 업데이트 된 글로벌 네트워크로 액터러너 업데이트
$Advantage = R_{t+1}+\gamma V_v (S_{t+1})-V_v (S_t)$ : 액터-크리틱에서의 어드밴티지 함수
$Advantage = R_{t+1}+\gamma R_{t+2}+\cdots+\gamma^k V_v(S_{t+k})-V_v (S_t)$ : k-타임스텝 어드밴티지 함수
$엔트로피 = -\Sigma_i p_i log(p_i)$
$오류함수 = R_{t+1}+\gamma R_{t+2}+\cdots+\gamma^k V_v(S_{t+k})-V_v (S_t)$ : 가치신경망의 오류함수
- DQN의 한계
Comments