모델 프리 강화학습

모델 프리 강화학습(model-free reinforcement learning)은 강화학습의 단계 중 마르코프 의사결정 과정에서 모델이 주어지지 않았을 때 최적의 정책 함수를 찾아내는 방법이다. 즉, 모델을 사용하지 않는 강화학습이다.

개요

모델 프리 강화학습은 환경이 어떻게 동작되는지 알지 못한 상태에서 수동적으로 다음 번 상태와 보상을 얻게 되는 강화학습이다. 다시 말해서 주어진 상태에서 어떤 행동을 수행하고, 수동적으로 환경을 알려 주는 다음 번 상태를 얻게 되는 것이다. 게임을 생각하면 이해가 쉬운데, 상태를 모니터 스크린으로, 행동은 키보드 입력에 해당한다고 생각해 보자. 우리가 모니터를 보고 어떤 행동을 하게 되면 어떤 화면이 다음 번에 나타나고, 게임 스코어 등으로 보상을 받을 수 있다. 이러한 모델 프리 강화학습은 모델 기반 강화학습에 비해 몇 가지 구별되는 특징이 있는데, 그 대표적인 것이 바로 탐사(exploration)이다. 모델 프리 강화학습에서, 우리는 더 이상 환경이 어떻게 동작하는지 알지 못한다. 그렇기 때문에 직접 해 보고 그 결과를 통해 정책 함수를 점차 학습시켜야 한다. 현재까지 알고 있는 사실을 좀 더 파고들어서 더 좋은 결과를 얻으려고 하는 것을 개척(exploitation), 새로운 것들을 시도하는 것을 탐사(exploation)라고 하고, 이 둘 사이를 잘 조정하는 것을 개척과 탐사의 트레이드오프(exploitation and exploration tradeoff)라고 한다. 즉, 직접 해 보고 난 후에야 결과를 알 수 있는 것이 모델 프리 강화학습이다.

알고리즘

몬테카를로 예측

몬테카를로 학습은 경험의 에피소드(episode)로부터 직접 가치 기능을 학습한다. 또한 에피소드 끝에만 보상을 받는다.

 에피소드 = S1 A1 R1, S2 A2 R2, S3 A3 R3…… ST (종료 상태까지의 단계 순서)

그래서 마지막 에피소드에서 가치 함수를 알 수 있다. 이를 식으로 나타내면 다음과 같다.

$V_{\pi }(s)\sim {\frac {1}{N(s)}}\sum _{i=1}^{N(s)}G_{i}(s)$

$N(s)$는 에피소드 동안 $s$를 방문한 횟수, $s$는 에피소드 $i$에서 $s$의 리턴 값이다. 이 식을 하나의 상태에 대해서만 생각해 보면, 상태에 대한 표기법을 없애고 n개의 리턴 값을 통해 얻은 가치 함수는 $V_{n+1}$이라고 쓸 수 있다. 그리고 가장 최근 얻은 리턴을 $G_{n}$이라고 한다면, 아래와 같이 분해할 수 있다.

$V_{n+1}={\frac {1}{N}}\sum _{i=1}^{n}G_{i}={\frac {1}{N}}(G_{n}+\sum _{i=1}^{n-1}G_{i})$

그리고 이 식을 고쳐쓰면 다음과 같은 관계를 얻을 수 있다.

 $={\frac {1}{N}}(G_{n}+\sum _{i=1}^{n-1}G_{i})={\frac {1}{N}}(G_{n}+(n-1){\frac {1}{n-1}}\sum _{i=1}^{n-1}G_{i})$
 $={\frac {1}{N}}(G_{n}+(n-1){\frac {1}{n-1}}V_{n})$
 $={\frac {1}{N}}(G_{n}+(n-1)V_{n})$
 $={\frac {1}{N}}(G_{n}+nV_{n}-V_{n})$
 $=V_{n}+{\frac {1}{N}}(G_{n}-V_{n})$

샘플 리턴

마르코프 의사결정 과정의 샘플 리턴으로부터 가치 함수를 배운다. 샘플 리턴은 평균적인 숫자의 집합과 같다.

 ${1,2,3,4}\rightarrow 10/4\rightarrow 2.5$

따라서 샘플 리턴은 에피소드에서 얻은 평균 리턴을 의미할 수 있다. 마르코프 의사결정 과정에는 두 가지 유형이 있다. 첫 번째 방문하는 경우, 에피소드에서 $s$가 처음 방문되는 경우에만 평균 수익률을 낸다. 매번 방문하는 경우, 에피소드에서 $s$가 방문될 때마다 평균적으로 수익을 얻는다. 예를 들어보자.

 $S1\ A1\ R1,\ S2\ A2\ R3,\ S3\ A3\ R3,S1\ A4\ R4\rightarrow End$

위의 경우 첫 방문일 때는 R3까지 보상을 얻을 수 있고, 매회 방문할 경우 에피소드가 끝날 때까지 보상을 챙긴다. 보통 첫 방문에 초점이 맞춰져야 한다. 예측 작업의 경우 첫 번째 방문의 알고리즘은 다음과 같다.

 $\mathrm {Initialize:}$
     $\pi \leftarrow \mathrm {policy\ to\ be\ evaluated}$
     $V\leftarrow \mathrm {an\ arbitrary\ state-value\ function}$
     $Returns(s)\leftarrow \mathrm {an\ empty\ list,\ for\ all\ s\in S}$
 
 $\mathrm {Repeat\ forever:}$
     $\mathrm {Generate\ an\ episode\ using} \ \pi$
     $\mathrm {For\ each\ state} \ s\ \mathrm {appearing\ in\ the\ episode}$
         $G\leftarrow \mathrm {return\ following\ the\ first\ occurrence\ of} \ s$
         $\mathrm {Append} \ G\ \mathrm {to} \ Returns(s)$
         $V(s)\leftarrow \mathrm {average} (Returns(s))$

$V(S)$는 $G$의 평균이다. 만약 우리가 모든 값을 가지고 있다면 평균을 계산하는 방법을 알고 있지만, 모든 값을 가지고 있지 않다면 평균을 계산할 수 없다. 이럴 때 쓰이는 증분 평균이라는 접근법이 있다. 역학 문제가 아닌 문제에서는, 런닝 평균을 추적하는 것이 유용할 수 있다. 즉, 오래된 에피소드를 잊어버리는 것이다.

$V(St)\leftarrow V(St)+a(Gt-V(St))$

위의 알고리즘이 말하듯이, 먼저 정책을 사용하여 에피소드를 생성하는 것에 초점을 맞추고 평균적인 에피소드를 취한다. 우리는 이것을 영원히 반복하거나 정해진 횟수만큼 반복한다. 다음 조각은 이와 같은 에피소드를 만들어 낸다.

$[(S1,A1,R1),(S2,A2,R2),(S3,A3,R3),\mathrm {so\ on} \cdots ]$

시간차 학습

몬테카를로 예측에서는 에피소드가 끝나야 상태 가치 함수를 갱신할 수 있었다. 그렇기에 학습을 실시간으로 수행하기 어려운 단점이 있다. 시간차 예측(temporal-difference prediction, TD)을 활용하면 매 시간 단계(time step)마다 가치 함수를 업데이트할 수 있다. 시간차 예측은 다음과 같이 가치 함수를 업데이트한다.

$V(St)\leftarrow V(St)+a(R_{(t+1)}+\gamma V(S_{t}+1)-V(S_{t}))$

몬테카를로 예측과 다르게 매 시간 단계 $t$에서 가치 함수를 갱신한다. 이렇게 에피소드 중에 다음 상태의 가치 함수로 현재 상태의 가치 함수를 갱신하므로 시간차 학습은 부트스트랩을 사용한다고 할 수 있다. 동적 계획법에서도 가치 함수를 매 시간 단계마다 갱신했었다. 그러므로 동적 계획법 역시 부트스트랩을 사용한다고 할 수 있다. 시간차 학습에서 제어는 온-폴리시(On-policy)이냐 오프-폴리시(Off-policy)이냐에 따라 그 이름이 달라진다. 온-폴리시 시간차 제어(On-policy temporal-difference control)을 SARSA(state–action–reward–state–action)라고 하고 오프-폴리시 시간차 제어(Off-policy temporal-difference control)을 큐-러닝(Q-learning)이라고 한다.

SARSA

시간차 학습에서 상태-행동 가치 함수를 적용하고 탐험을 추가하여 제어하면 SARSA가 된다. 이름이 SARSA인 이유는 하나의 샘플이 현재 state, action, reward, 다음 state, 다음 action으로 구성되어 있기 때문이다. SARSA는 상태-행동 가치 함수 Q를 사용하는 방법이다. 수식은 다음과 같다.

$Q(s,a)\leftarrow Q(s,a)+a(Ras+\gamma Q(s',a')-Q(s,a))$

SARSA 에이전트는 환경과 상호 작용하고 취한 조치에 따라 정책을 업데이트하므로 이를 정책 학습 알고리즘이라고 한다. 스테이트 액션의 Q 값은 오류에 의해 업데이트되고 학습 속도 알파에 의해 조정된다. Q 값은 주의 조치를 취하기 위해 다음 시간 단계에서 받을 수 있는 보상과 다음 주의 조치 관찰에서 받은 미래 보상 할인액을 나타낸다. 왓킨(Watkin)의 큐-러닝(Q-Learning)은 사용 가능한 작업의 최대 보상을 기반으로 최적의 상태 동작 값 함수 $Q^{*}$의 추정치를 업데이트한다. SARSA가 스스로 따르는 정책을 취하는 것과 관련된 Q 값을 학습하는 동안 왓킨의 Q-러닝은 탐색/탐색 정책을 따르는 동안 최적의 정책을 취하는 것과 관련된 Q 값을 학습한다. 왓킨의 큐-러닝의 일부 최적화는 SARSA에 적용될 수 있다. 이 방법의 장점으로는, 모든 에피소드를 다 돌지 않아도 금방금방 폴리시 임프로브먼트를 진행할 수 있다는 것이다. 그렇기 때문에 만약 에피소드 하나하나가 매우 길다면 이 방식이 매우 효율적이게 될 것이다. 왜냐하면 그때 그때 (s, a)쌍만 주어진다면 바로바로 폴리시 임프로브먼트가 가능하기 때문이다. 다음은 SARSA의 파이썬 코드이다.

$\mathrm {Initialize} \ Q(s,a),\forall s\in S,\ a\in A(s),\mathrm {arbitrarily,\ and} \ Q(terminal-state)=0$
 $\mathrm {Repeat\ (for\ each\ episode):}$
     $\mathrm {Initialize:} \ S$
     $\mathrm {Choose} \ A\ \mathrm {from} \ S\mathrm {using\ policy\ derived\ from} \ Q\ (e.g,e-greedy)$
     $\mathrm {Repeat\ (for\ each\ step\ of\ episode):}$
         $\mathrm {Take\ action} \ A,\mathrm {observe} \ R,\ S'$
         $\mathrm {Choose} \ A',\mathrm {from} \ S'\mathrm {using\ policy\ derived\ from} Q\ (e.g,e-greedy)$
         $Q(S,A)\leftarrow Q(S,A)+a[R+\gamma Q(S',A')-Q(S,A)]$
         $S\leftarrow S';A\leftarrow A';$
     $\mathrm {until} \ S\ \mathrm {is\ terminal}$

큐-러닝

강화 학습에서 가장 중요한 돌파구 중 하나는 큐-러닝으로 알려진 오프 폴리시 시간차 학습 제어 알고리즘의 개발이었다. 큐-러닝은 가장 높은 가치의 행동을 결정적으로 선택하는 목표 정책에 대한 상태-조치 값 함수를 추정한다. 즉, 큐-러닝은 어떤 상황에서 어떤 조치를 취해야 하는지 에이전트에게 알려주는 정책을 학습하기 위한 알고리즘이다.

알고리즘

상태 $\Delta t$에서 미래로 한 단계 도약하기 위한 가중치는 $\gamma ^{\Delta t}$로 계산된다. 여기서 $\gamma$('할인 요소')는 0과 1($0\leq \gamma \leq 1$) 사이의 숫자로, 나중에 받은 보상보다 더 일찍 받은 보상을 평가하는 효과가 있다. $\gamma$는 또한 모든 $\Delta t$단계에서 성공할 확률로 해석될 수 있다. 따라서 알고리즘에는 상태-작용 조합의 품질을 계산하는 함수가 있다.

$Q:S\times A\to \mathbb {R}$

학습이 시작되기 전에 $Q$는 가능한 프로그래머에 의해 결정된 임의의 고정값으로 초기화된다. 그런 다음, $t$ 에이전트가 조치 $a_{t}$를 선택하고, 보상 $r_{t}$를 관찰하고, 새로운 상태 $s_{t+1}$(이전의 상태 $s_{t}$와 선택된 조치 모두에 따라 달라질 수 있음)를 입력하며, $Q$가 업데이트된다. 알고리즘의 핵심은 단순 값 반복 업데이트로서 벨먼 방정식이며, 이전 값과 새로운 정보의 가중 평균을 사용한다.

$Q^{new}(s_{t},a_{t})\leftarrow \underbrace {Q(s_{t},a_{t})} _{\text{old value}}+\underbrace {\alpha } _{\text{learning rate}}\cdot \overbrace {{\bigg (}\underbrace {\underbrace {r_{t}} _{\text{reward}}+\underbrace {\gamma } _{\text{discount factor}}\cdot \underbrace {\max _{a}Q(s_{t+1},a)} _{\text{estimate of optimal future value}}} _{\text{new value (temporal difference target)}}-\underbrace {Q(s_{t},a_{t})} _{\text{old value}}{\bigg )}} ^{\text{temporal difference}}$

여기서 $r_{t}$는 주 $s_{t}$에서 주 $s_{t+1}$로 이동할 때 받는 보상이며, $\alpha$는 학습률($0<\alpha \leq 1$)이다. 알고리즘의 에피소드는 상태 $s_{t+1}$가 최종 또는 단말 상태일 때 끝난다. 그러나 큐-러닝은 비에피시적 과제에서도 배울 수 있다. 할인율이 1보다 낮으면 문제가 무한루프를 포함할 수 있더라도 작용 값은 유한하다. 모든 최종 상태 $Q(s_{f},a)$에 대해 $r$는 업데이트되지 않지만 상태 E에 대해 관측된 보상 값 $s_{f}$로 설정된다. 대부분의 경우 $Q(s_{f},a)$는 0과 같아질 수 있다.

변수의 영향

• 학습률: 학습 속도 또는 단계 크기는 새로 취득한 정보가 오래된 정보를 얼마나 무시하는지를 결정한다. 인자가 0이면 에이전트가 아무것도 배우지 못하게 되는 반면, 인자가 1이면 대리인은 가장 최근의 정보만 고려하게 된다. 완전한 결정론적 환경에서는 $\alpha _{t}=1$의 학습률이 최적이다. 문제가 확률적일 때 알고리즘은 0으로 감소해야 하는 학습 속도에 대해 어떤 기술적 조건 하에서 수렴한다. 실제로, 모든 $t$에 대해 $\alpha _{t}=0.1$와 같이 일정한 학습 속도를 사용하는 경우가 많다.
• 할인율: 할인 요인 $\gamma$는 미래 보상의 중요성을 결정한다. 요인이 0이면 에이전트 $r_{t}$ 근시적은 현재의 보상만 고려하며, 1에 근접하는 요인은 장기간의 높은 보상을 위해 노력하게 된다. 할인율이 1을 초과하거나 충족하면, 조치값이 갈릴 수 있다. $\gamma =1$의 경우, 터미널 상태가 없거나 에이전트가 한 곳에 도달하지 못할 경우, 모든 환경 이력은 무한히 길어지고, 부가적이고 할인되지 않은 보상이 있는 유틸리티는 일반적으로 무한대가 된다. 1보다 약간 낮은 할인율에도 불구하고 큐-러닝 학습은 가치기능이 인공신경망과 근사치를 했을 때 오류와 불안정성의 전파로 이어진다. 그 경우 낮은 할인율로 시작하여 최종 가치로 증가시키면 학습이 가속된다.
• 초기 조건(Q₀): 큐-러닝은 반복 알고리즘이므로, 첫 번째 업데이트가 발생하기 전에 암시적으로 초기 조건을 가정한다. 최적적 초기 조건이라고도 알려진 높은 초기 값은 탐색을 장려할 수 있다. 어떤 조치를 선택하든 업데이트 규칙은 다른 대안보다 낮은 값을 갖게 하여 선택 확률을 증가시킨다. 첫 번째 보상은 초기 조건을 재설정하는 데 사용될 수 있다. 이 생각에 따르면, 처음으로 조치를 취할 때 보상을 사용하여 $Q$의 가치를 설정한다. 이것은 고정된 결정론적 보상의 경우에 즉각적인 학습을 가능하게 한다. 초기 조건의 재설정(RIC)을 통합한 모델은 임의 초기 조건(AIC)을 가정하는 모델보다 참가자의 행동을 더 잘 예측할 것으로 예상된다.

참고자료

• State–action–reward–state–action Wikipedia - https://en.wikipedia.org/wiki/State%E2%80%93action%E2%80%93reward%E2%80%93state%E2%80%93action
• Q-learning Wikipedia - https://en.wikipedia.org/wiki/Q-learning#Learning_Rate
• 카카오 정책사업 연구, 〈(카카오AI리포트)알파고를 탄생시킨 강화학습의 비밀〉, 《브런치》, 2017-06-23
• 숨니야, 〈Ch.5 Monte-Calro Methods〉, 《티스토리》, 2018-01-01
• Madhu Sanjeevi, 〈Ch 12.1:Model Free Reinforcement learning algorithms (Monte Carlo, SARSA, Q-learning)〉, 《medium》, 2018-06-29
• cdjs의 코딩 공부방, 〈강화학습 강의 (CS234) 4강 - MC / SARSA / Q-learning〉, 《티스토리》, 2019-05-08
• 〈강화학습(reinforcement learning)이란?)〉, 《퀀티랩》, 2020-02-13

같이 보기

• 강화학습
• 모델 기반 강화학습

이 모델 프리 강화학습 문서는 인공지능 기술에 관한 글로서 검토가 필요합니다. 위키 문서는 누구든지 자유롭게 편집할 수 있습니다. [편집]을 눌러 문서 내용을 검토·수정해 주세요.

인공지능 : 인공지능 기술 □■⊕, 인공지능 활용, 인공지능 개발업체, 인공지능 인물 인간적 행위 로봇공학 • 로봇기술 • 인지과학 • 자동추론 • 자연어 처리 • 지식표현 • 컴퓨터 비전 • 튜링 테스트 합리적 사고 결정이론 • 논리학 • 논리주의자 • 삼단논법 • 선호도 • 최대기대효용 • 효용이론 강화학습 ADP • DDPG • DQN • SARSA • 결정이론적 메타추론 • 계통적 강화학습 • 동적 계획법 • 모델 기반 강화학습 • 모델 프리 강화학습 • 반영식 아키텍처 • 수시 알고리즘 • 심층믿음망 • 어니 • 에이전트 • 확률적 경사하강법 인공지능 프로그램 A2I • 어니 • 알파고 • 왓슨 • 카페 • 텐서플로 • 토치 • 한돌 인공지능 알고리즘 AGI • 관계형 네트워크(RN) • 다층퍼셉트론 • 데이터마이닝 • 딥러닝 • 딥큐러닝 • 머신러닝(기계학습) • 방사신경망 • 분산 샌드박스 • 비지도학습 • 생성대립신경망(GAN) • 생성형 AI • 수퍼 얼라인먼트 • 순전파 • 순환신경망(RNN) • 시그노이드 함수 • 신경망 구조 • 심층신경망(DNN) • 심층신뢰신경망(DBN) • 양방향 비고정값 암호 체계(TSID) • 역전파 • 인공신경망(ANN) • 인공지능(AI) • 제한 볼츠만 머신(RBM) • 전방전달신경망 • 지도학습 • 코헨 자기조직 신경망 • 텍스트마이닝 • 파이 • 퍼셉트론 • 합성곱 신경망(CNN) 문자인식 ICR • OCR • OMR • 문자인식 인공지능 특징 계산상의 합리성 • 분산성 • 불확실성 • 예측곤란성 • 완벽한 합리성 • 유계 합리성 • 이유 불충분의 원리 • 자율성 • 할루시네이션 계산 복잡도 NP • NP-완전 • 공간복잡도 • 시간복잡도 • 여 NP • 여 NP-완전 인공지능 기술 BCI • 멀티모달 • 모달 • 모달리티 • 모달창 • 텔레파시 인공지능 법적 지위 권리주체성 • 전자대리인 • 전자적 인간 • 책임법 • 코파일럿 인공지능 업무 데이터라벨러 • 데이터라벨링 • 크라우드워커 위키 : 자동차, 교통, 지역, 산업, 기업, 단체, 업무, 쇼핑, 블록체인, 암호화폐, 인공지능, 개발, 인물, 행사, 일반