모델을 모를 때 사용할 수 있는 방법
여기서 모델을 모른다는 건, State Transition Matrix / Reward 등을 모른다는 뜻이다.
여기서 몬테카를로 방법은 '큰 수의 법칙' 을 전제로, 에피소드에 대한 경험을 토대로 학습한다.
- 몬테카를로 방법은 Complete Episode 에서 으로부터 배운다.
직접 측정하기 어려운 통계량이 있을 때 여러 번 샘플링하여 그 값을 가늠하는 기법
Transit & Episode
⎣⎢⎢⎢⎡S1S2SnA1A2...AnR1R2Rn⎦⎥⎥⎥⎤
이 행렬의 한 행을 Transit 이라고 하고, Transit 의 시퀀스들을 Episode 라고 한다.
몬테카를로의 경우, SAR 을 한 Transit 으로 본다.
Complete Episode 가 있어야 return 을 계산할 수 있기 때문에, 몬테카를로는 Complete Episode 가 있어야 계산할 수 있다.
Monte-Carlo RL
- Increment Counter : N(s) = N(s) + 1
- Increment Total Return : S(s) = S(s) + Gt
- Value is estimated by mean return = V(s) = S(s)/N(s)
예시
discount factor 가 1일 때
-
S = {1,2,...,10,T}
-
A = {1,2,3,4}
-
Episode : Sequence of transit (s,a,r)
-
Episode 1 : (s1,a1,3) (s3,a2,2) (s9,a3,10) (s2,a1,2) (s4,a4,1)
-
Return : 3+2+10+2+1
-
Increment count of state
N(s1)=N(s1+1),...N(s4)=N(s4)+1
-
Accumulated Reward from the state :
S(s4)=S(s4)+1,S(s2)=S(s2)+3,S(s9)=S(s9)+13,S(s3)=S(s3)+15,S(s1)=S(s1)+18
따라서 결국 Value 는 다음과 같이 나온다.
V(s4)=S(s4)/N(s4),V(s2)=S(s2)/N(s2)...
Incremental Mean
mu : value 의 평균값
x : sequence 번호
k : sample 의 개수 (learning rate)
μk=k1j=1∑kxj=k1(xk+j=1∑k−1xj)=k1(xk+(k−1)μk−1)
(시그마가 저렇게 되는 이유는 평균 x 개수 = sum 이기 때문)
μk=μk−1+k1(xk−μk−1)
예전에는 episode 끝날 때 까지 Sum 에 다 쌓아놓고 number 로 나눠서 Value 를 구했는데,
이렇게 하면 value 값만 계속 업데이트하면 됨. (Forget old episode)
N(St)=N(St)+1
V(St)=V(St)+N(St)1(Gt−V(St))
(Gt: Return)
