8. MonteCarlo(3/3) - off-policy ~ importance sampling
Off - policy
실제 play, optimize policy가 다름
behavior policy b - random policy
target policy π - optimize policy
policy를 이용해서 Q값을 업데이트하는 policy는 pi,
내가 직접 플레이를 하면서 개션하는가
다른 사람들의 플레이(tv에서 잘하는 사람을 참고) 보면서 내 policy를 improve하는가,
Off policy 장점
내 policy를 계속해서 변화시켜나기 때문에 내 policy에 벗어나기 쉽다 그렇기 때문에
혁신적이고 스타일이 다른 diverse한 탐험을 할 수 있다
하지만 당연히 단점도 있지
실제 에피소드 만드는 policy와 참고하는 policy의 행동이 너무 다르면 어떤 상황에서의 Q값을 계산하면 정확하지 않음
기본적으로 어떤 행동을 취했을 때, 다음 행동들이 연결돼서 끝까지 갔을 때 행동이 내 policy와 많이 벌어져
내 policy와 가치가 안 맞는다.
1번 줄만 차이있음(on-policy와)
behavior policy (random하게)쓰면서 π update
장점 : epsilon greedy 이런거 필요없음 남을 보면서 하면돼서 배울점이 있음
문제점 : 행동에 distribution이 다름 쟤 행동과 내 행동이 다름
어떤 state에서의 가치를 찾고싶다 !
그 뒤에 어떤 식으로 action을 취하는데에 그 가치가 결정된다
이걸 해결하는 방법은 importance sampling
importance sampling
b policy가 엉망으로 행동할 때 참고해서 내가 어떤 state의 가치를 정하면 문제가 생김
그것을 해결하기 위해선 보정이 필요한데, 그 방법이 importance sampling
내가 알고싶은 주사위의 분포가 원래 알고 있는 주사위의 distribution(주사위의 눈이 나올 각각의 확률)이 다를 경우,
sampling을 통해서(주사위 1000번, 10000번) 분포를 알아낼 수 있다.
추정을 할 수 있게 어떻게 하느냐...
x: 주사위 눈
p(x) : 특정 눈이 나올 확률
f(x) : 상금
x가 p(x)라는 분포를 따를 때의 기대값
A주사위를 굴려 분포를 알아낸다고 한대도 내가 알고자하는 B분포가 아님
A, B의 분포의 비율을 알 수 있다면 A분포를 샘플링 한 다음 B 분포를 알아냄 importance sampling ratio 사용
f(x) 주사위 1이 나오면 100원, 2나오면 200원... 등등
p(x)f(x) = 확률x 상금
x가 p(x)라는 분포를 따를 때, 분포가 다른 q(x)를 가져와보면 아래와 같이 생각해볼 수 있음
( p라는 분포를 가지는 주사위/q라는 분포를 가지는 주사위 ) 비율을 알아야한다 p(x)/q(x)
Importance sampling ratio : p(x)/q(x)
(p(x)/q(x))*f(x) 새로운 확률(분포) reward
q(x)를 적용해줌으로 새로운 분포를 사용할 수 있음
ex ) p주사위에서 1이나올 확률 / q주사위에서 1이 나올 확률
Importance sampling ratio의 개념을 쉽게 풀어 쓰자면
어떤 state에서 어떤 action이 쟤는 25%확률로 취함 하지만 나는 70%의 확률로 취한다면
쟤가 25% 확률로 action을 취했을 때 얻는 reward값의 weight를 높여준다.
b와 π의 distribution이 다르기 때문에 가중치를 곱해준다. 즉, 비율대로 반영해준다.
q 분포를 통해 p의 분포를 파악한다.
starting에서 어떤 policy를 썼을 때, 특정 tragactory를 고르게 될 확률은?
특정 tragactory를 가질(골라질) 확률은 아래와 같다.
p(St+1|St, At)는 stochastic environmnet이기 때문에 있음 (next state가 여러가지가 있을 수 있기 때문에)
(Sk에서 Ak로 가는 확률) x (Sk에서 Ak일 때 next state가 Sk+1일 확률) 곱하고 k 에 대해서 다 곱함
=> 그 trajactory가 골라질 확률
Importance sampling
분모 : b라는 policy를 썼을 때, 나오는 trajactory
분자 : pi라는 policy를 썼을 때, 나오는 trajactory
b라는 policy를 쓸 땐 아래, 위는 pi를 쓸 때 trajectory
어떤 state에서 특정 액션을 취할 확률을 계산할 수 있다면 추정할 수 있다면 importance sampling ratio로 쓸 수 있다.
return에 importance sampling 곱하면 pi라는 policy의 v(s)임
어떤 state의 V,Q값을 구할 때, 출발 state(s)로 부터 ~ episode 가 끝났을 때, 나에게 주어진 reward의 합 G(t) return
stochasic일때는 기대값으로
Vb(s) behavior policy를 썼을 때의 가치
pi policy에서의 V(s)값은 Vb(s) * (importance sampling ratio)
importance sampling ratio 개념
쟤가 10일 때 내가 50이라면, 0.1인데 운좋게 취했을 때 나는 그걸 250점으로 간주하겠다
나는 별로 취하지 않을 행동인데, 쟤는 엄청 취하면 나는 줄이겠다.
Ordinary importance sampling
각 iteration에서 11번째 값을 모아서 각각 importance sampling ratio를 곱해주고 전체 iteration값으로 나눠줌
G(t)는 각각의 reward의 합
10번의 V값들을 계산하고 싶으면 각 ep의 10번째 각 S의 Reward 합을 계산하면 G(t)
시그마 Impartance sampling ratio x G(t) / 60 -> ordinary Import sampling ratio
weighted 와의 차이, 밑이 타우가 S의 합이냐 , 또는 weight들의 합이냐
Weighted importance sampling
분모 : weighted 들의 합
각각 return 값이 100, 200, 300 일 때,
축구를 생각해 봤을 때, 같은 100점을 땄을 때, 아시안컵에서 우승 가중치와 월드컵의 가중치는 분명 다름
동일하게 각 3건에 대해서 나누면 ordinary / 똑같은 경기 1판이지만 가중치에 따라 4, 3, 2번한 거처럼 치겠다. weighted
둘다 Importance sampling 이지만 weighted 를 많이 쓰긴 함.
weighted importance sampling에서는 각각의 가중치를 4,3,2 부여
| ordinary importance sampling | Weighted importance sampling |
| 1600 / 3 | 1600/4+3+2 |
bias : True분포에서 조금 틀어져서 샘플링 됨(치우침)
variance : sampling을 할 때마다, variance가 크다(뭔말일까? 내가 적었지만 잘 모르겠다)
tade-off 관계
장단점이 있기 때문에 뭐가 좋다 말하긴 어렵다.
Weighted importance sampling using Incremental Mean
Wk : Importance sampling
using incremental mean
Wn : Importance sampling Ratio
Gn : return 값,
Cn : 기존의 importance sampling 계속 더해가면서 분모를 넣음
한 case가 나올 때 마다 update
W = W*(1/b(at|st)) = W*(pi(at|st) /b(at|st))
target policy가 deterministic 하므로, 역계산을 통해 update
항상 behavior가 최적의 목적지로 가기위해서 분자는 1이 된다.
1. R 0, W 1으로 세팅
2. reverse order
하나의 episode가 끝나면 맨 뒤에서 부터 C 0으로 세팅, W 를 구함 초기값은 1, Incremental mean을 계산
Q의 초기값은 random
importance sampling ratio를 곱해줌
뒤에서부터 action을 보는데, 그 다음것을 보는데 어떤 스테이트에서 액션을 취할 때, optimize하는 policy가 그 액션을 취할 수도 안 취할 수도 / 취한 액션이 취하는 것일 수도 있고 안 취한 것일 수도 있는데, 만약 그 액션이 (내가 취하는 것과 쟤가)서로 다르면 분자를 버림
만약 같은 액션이라면 1 (100프로 그 action을 취하기 때문에 )
내가 취할 액션과 달랐다 -> 분자는 0
0이 되는 순간 뭘 곱한다 한들, 계속 0이기 때문에 episode를 버림. 한 데까지만 한다.
결론적으로 내가 어떤 episode에서 state를 10번째 할 때, 9번째 state에서 B,Q 값을 구함
8번 일때 9번, 10번의 ratio 곱해줘야함
ep 가 길거나 복잡하면 직접 계산할 수 없다. 그 때 TD사용 (continuous tasks의 경우)