Reinforcement Learning 책 읽고 공부하기(2-5, Exercise)

sutton 교수의 Reinforcement Learning An Introduction을 읽고 공부하기

챕터 2에서 본 연습문제들 풀어보기

Exercise 2.6 Mysterious Spikes 그림 2.3의 결과는 10-armed bandt 문제에서 각각 임의로 선택한 2000개 이상이므로 신뢰할 수 있어야 한다. 왜 진동과 스파이크가 optimistic 방법의 초기에 나타났는가? 다른말로는 왜 이 방법이 average 방법에 비해 초기에 성능이 더 좋거나 나쁜가?

일단 가져와 본 그림 2.3

Optimistic greedy에서는 초기값(initial estimate)에 의해 평향되어 있음. sample-average 방법은 이 편향이 사라지는데 constant average에서는 편향이 영구적인데 시간이 경과함에따라 감소한다고 함. 여기서는 initial estimate를 +5로 설정했고 이 initial estimate에 의해 초기부터 더 많은 exploration을 함. 처음에 action을 선택할 때 action을 선택한 후 받을 reward가 initial estimate보다 작기 때문에 학습을 하며 계속 action을 바꾸면 exploration을 하는 것임.

 따라서 그래프의 변동폭이 학습 초기부터 오락가락하냐면 초기값을 reward의 분포보다 한참 높게(?) 설정해서 계속 exploration을 해서 그런 것으로 보임. exploration 중에서 reward를 많이 주는 optimal action을 찾았다면 그래프는 증가했을 것이고 그렇지 않다면 감소했을 것. 

Exercise 2.7 Unbiased Constant-Step-Size Trick 이 챕터의 대부분에서 action value를 estimate하기 위해 sample average방법을 사용했다. 왜냐하면 스텝사이즈 파라미터를 상수로 했을 때와 달리 initial bias를 만들지 않기 때문이다. 하지만 sample average 방식은 nonstationary 문제에서 성능이 나쁘기 때문에 만족할만한 해결책은 아니다. 상수 스텝사이즈 파라미터에서 nonstationary 문제에 관한 이점을 가진 채, 편향을 피하는게 가능할까? 하나의 해결책은

$$ {\beta}_{n} \doteq \alpha / {\overline{o}}_{n} $$

특정 action의 n번째 reward를 위해 다음과 같은 스텝사이즈 파라미터를 사용하는 것이다. \( \alpha \) > 0인경우 전통적인 스텝 사이즈이고 \( {\overline{o}}_{n} \)은 0에서 시작하는 것의 흔적으로 다음과 같다.(is a trace of one that starts at 0, 그냥 점화식을 말하는 듯)

\( {Q}_{n} \)이 initial bias가 없는 exponential recency-weighted average라는 것을 보여주기 위해 다음과 같이 분석해보자.

스텝사이즈를 위에 나온 베타로 바꿔서 표현해보자

위의 식을 계산을 해보면서 풀어써보면 다음과 같음.

\( {Q}_{2} = {R}_{1} \)를 보면 초기값 \( {Q}_{1} \)이 다음 식에 적용되지 않는 것을 볼 수 있음.

즉 \( {\beta}_{n} \)을 사용하면 initial estimate를 0으로 날려버림. 식을 정리해보니 initial bias가 없어졌다는 것을 알 수 있음.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Exercise 2.8 UCB Spikes. 그림 2.4는 UCB 알고리즘이 11번째 스텝에서 뚜렷한 스파이크 나타남을 보여준다. 왜 이런걸까? 왜 reward가 11번째 스텝에서 오르고 그 밑의 스텝에서 내려갔는지 반드시 설명하시오. Hint c=1이면, 스파이크가 덜 두드러진다.

그림 2.4를 가져왔음

일단 UCB로 action을 선택하는 식은 다음과 같음.

여기서 c가 dgree of exploration 그러니까 탐험의 정도라고 해석할 수 있음. 루트 부분을 앞에서 설명한 것을 다시 생각해보면 uncertainty or variance임. 그리고 c=1에서 스파이크가 덜 두드러진다고 하는 것을 보니 c값이 높으면 높을수록 탐험을 더 많이해서 스파이크는 더 심해질 것임(variance가 더 심해짐). 근데 왜 11번째 스텝에서 오르고 그 밑의 스텝에서 내려갈까.

 앞에서 설명했던 것을 보면 UCB의 경우 처음 k스텝은 아직 시도하지 않은 action을 무작위로 선택하기 때문에 k스텝을 제외한 나머지 부분이 \( \epsilon \)-greedy action보다 우수하다고 했음. bandit 문제에서는 이 k값이 10이였으므로 일단 10번째 스텝까지는 시도하지 않은 모든 action을 수행하기 때문에 더 낮은 성능을 보여줬다고 생각했음. 그래서 11번째에서는 모든 action들 중 제일 나은 action을 선택하므로 아마 가장 높은 값을 주는 actoin을 선택할 것임. 그리고 다음 스텝에서 내려간 것은 exlploration을 해서 내려간 것이라고 추측가능.

  근데... 맞는 답일까 모르겠음.

Exercise 2.9 action이 두개인 경우, soft-max 분포가 인공신경망 및 통계학에서 자주 사용되는 로지스틱 (시그모이드) 함수와 동일하다는 것을 보여줘라.

일단 로지스틱함수가 뭔지 보자.

 

 

Exercise 2.10 타임스텝이 지날 때마다 참 action value가 무작위로 계속 바뀌는 2-armed bandit이 있다고 하자. Case A의 경우 action 1,2의 참 value가 0.1, 0.2(각각 0.5의 확률), Case B의 경우 actoin 1, 2의 참 value가 0.9, 0.8(각각 0.5의 확률)이다. 각 타임스텝마다 어떤 value를 얻을지 모를 때 어떤 action을 선택해야 가장 높은 기대값을 달성할 수 있을까? 이제 각 스텝에서 case A인지 B인지 알고 있다고 가정하면(비록 아직 true action value는 모르지만) associative search다. 이 작업에서 달성할 수 있는 최선의 기대값은 무엇일까? 그리고 어떤 action들을 선택해야할까?

 

 

 

 

 

수정중

 

Reference : Reinforcement Learning : An Introduction