1. 강화학습 개요Permalink

• 순차적 행동 결정 문제의 구성요소
  • 상태 (State)
  • 행동 (Action)
  • 보상 (Reward)
  • 정책 (Policy)
• MDP (Markov Decision Process)

2. 강화학습 기초 1: MDP와 벨만 방정식Permalink

• 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: 그리드월드와 다이내믹 프로그래밍Permalink

• 정책 이터레이션
  $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번째 가치함수 계산
  
  • environment
  • policy_iteration
• 다이나믹 프로그래밍의 한계
  • 다이나믹 프로그래밍 : 순차적 행동 결정 문제를 벨만 방정식을 통해 푸는 것
  • 계산 복잡도
  • 차원의 저주
  • 환경에 대한 완벽한 정보 필요

4. 강화학습 기초 3: 그리드월드와 큐러닝Permalink

• 강화학습과 정책 평가 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)
    

$\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: 그리드월드와 근사함수Permalink

• 근사함수
  • 몬테카를로, 살사, 큐러닝의 한계
    • 계산 복잡도
    • 차원의 저주
    • 환경에 대한 완벽한 정보 필요
  • 근사함수를 통한 가치함수의 매개변수화
• 인공신경망
  • 노드와 활성함수
    • 노드의 종류
      • 입력층 (Input Layer)
      • 은닉층 (Hidden Layer)
      • 출력층 (Output Layer)
    • 활성함수의 종류
      • Sigmoid 함수
        $\frac{1}{1+e^{-x}}$
        
      • ReLU 함수
        $f(x)=\cases{x, x \geq 0 \cr 0, x < 0}$
        
  • 딥러닝
    • 특징 추출 (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]$
    

6. 강화학습 심화 2: 카트폴Permalink

• 알고리즘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)

7. 강화학습 심화 3: 아타리Permalink

• 브레이크아웃 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)$ : 가치신경망의 오류함수
      

참고자료Permalink

• https://github.com/rlcode/reinforcement-learning-kr