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

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

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

Exercise 2.1 \( \epsilon \)-greedy action 선택에서 두 개의 action을 선택해야 하는데 \( \epsilon \)=0.5인 경우 greedy action을 선택할 확률은 얼마인가?

일단 \( \epsilon \)-greedy action의 경우 \( \epsilon \)만큼의 확률로 greedy하지 않은 action을 선택하는 것임. 그리고 \( \epsilon \)-greedy에서는 optimal action을 선택할 확률이 1-\( \epsilon \)보다 큰 수렴, 즉 거의 확실하게 수렴함을 의미함. 그래서 여기서 greedy한 action을 선택한 확률은 0.5일 것.

-> 'optimal action을 선택할 확률이 1-\( \epsilon \)보다 큰 수렴' 이 부분의 의미가 뭔가 싶어서 고민해봤는데, 처음에는 탐험을 하면서 optimal action이 무엇인지 찾겠지만 학습을 하면 할수록 거의 확실하게 optimal action을 찾아감. 그래서 1-\( \epsilon \) 보다 크게 수렴한다고 쓴게 아닐까 싶음.

Exercise 2.2 Bandit example k=4인 k-armed bandit 문제를 가정해보자. 여기서 \( \epsilon \)-greedy action 선택, sample-average action value 평가(estimate), 초기 평가값(estimate)은 모든 action a에 대해 \( {Q}_{1}\left(a  \right) \)=0이라고 하자. action과 reward의 세트가 \( {A}_{1}=1, {R}_{1}=-1, {A}_{2}=2, {R}_{2}=1, {A}_{3}=2, {R}_{3}=-2, {A}_{4}=2, {R}_{4}=2, {A}_{5}=3, {R}_{5}=0\). 이 타임스텝들 중 \( \epsilon \)이 일어난 경우 임의의 action이 선택될 수 있다. 어떤 타임스텝에서 확실히 임의의 action이 선택됐는가? 어떤 타임스텝에서 이런 경우가 일어날 수 있을까?

어떤 시각에서 greedy하지 않은 action이 선택되었는지를 묻고 있음. 이를 알아내기 위해 챕터 2.2의 action value 계산식을 이용.

초기값은 모두 0으로 초기화한 상태에서 시작.

첫번째 스텝에서는 초기값이 모두 0이므로 아무 action을 선택, 그래서 일단 action 1을 선택하고 reward로 -1을 받음. greedy 방식이라고 할 수 있음.

  두번째 스텝에서는 greedy하게 action 2,3,4 중에서 하나를 선택. 그래서 action 2를 선택하고 reward로 1을 받은 모습.

  세번째 스텝에서도 역시 greedy하게 action 2를 선택. 하지만 reward로 -2를 받아 sample-average action value는 감소했음.

  네번째 스텝에서 action 2를 선택하면 안되지만 action 2를 다시 선택. 그래서 action 2의 action value는 1/3이 되었음. greedy 방식이 아님.

   다섯번째 스텝에서 greedy 방식이라면 action 2를 선택 하지만 action 3을 선택했음. 이 역시 greedy 방식이 아님.

 

결과적으로 4, 5번째 타임스텝에서 greedy하지 않은 임의의 action을 선택.

첫번째 타임스텝을 제외한 모든 타임스텝에서 greedy하지 않은 action을 선택할 수 있음.

 

 

 

Exercise 2.3 그림 2.2에서 보면 누적 reward 및 최상의 행동 선택 가능성 측면에서 장기적으로 가장 우수한 방법은 무엇인가? 얼마나 좋은가?

재등장한 그림 2.2

그냥 딱 봐도 \( \epsilon \)=0.01일 때가 장기적으로 봤을 때 제일 좋아보이긴 하는데 이걸 어떻게 표현해야할까

위의 \( \epsilon \)-greedy action을 생각해보면 이 방법에서 optimal actoin을 선택할 확률은 1-\( \epsilon \)에 거의 확실하게 수렴함. 그렇다면 \( \epsilon \)=0.1일 때 수렴할 optimal action을 선택할 확률은 0.9일 것이고 \( \epsilon \)=0.01일 때는 0.99일 것. 그러므로 \( \epsilon \)=0.01일 때 optimal action을 선택할 확률이 더 높으니까 장기적으로 봤을 때 더 성능이 좋다고 할 수 있음. 얼마나 좋은지는... 0.09%만큼 더 좋은건가?

Exercise 2.4 스텝사이즈 파라미터 \( {\alpha}_{n} \)이 상수가 아니면, \( {Q}_{n} \)은 스텝마다 다른 weight를 적용하는 weighted average다. 일반적인 경우에 각 reward의 weight(스텝사이즈)는 무엇일까?

일단 \( {Q}_{n}\)의 식은 다음과 같았음.

$$ {Q}_{n+1} \doteq {Q}_{n} + \alpha \left[ {R}_{n} - {Q}_{n} \right] $$

여기서 스텝사이즈를 상수 \( \alpha \)로 고정시켜놓은 것이고 스텝사이즈가 1/n이라면 sample-average가 됨. 단순하게 생각해서 스텝사이즈 파라미터를 일반화시키는 것은 스텝사이즈를 \( {\alpha}_{n} \left( a \right) \), 이렇게 쓰면 될 것 같음. 그래서 정리해서 쓰자면 아래와 같이

Exercise 2.5 (programming) 실험을 설계하고 수행해 nonstationary 문제에서 sample-average방법의 어려움을 증명하라. 10-armed testbed의 수정된 버전을 사용, 모든 \( {q}_{*}\left( a \right) \)는 동일하게 시작하고 각 스텝마다  독립적임(각 단계의 모든 \( {q}_{*} \left( a \right) \)에 평균 0, 표준편차 0.01인 정규분포 증분을 추가, 이 부분이 그냥 각 단계마다 독립적으로 정퓨분포를 따른다는 뜻인지 잘 모르겠음 일단은 각 단계마다 정규분포로 수행). action-value를 계산하는데 sample average방법과 constant step-size사용하는 방법 두가지 사용, inremental 계산, 스텝사이즈 파라미터=0.1, \( \epsilon \)=0.1, 10000스텝까지 진행

그래서 다음과 같이 나옴, 맞게 계산했는지 모르겠네

아래는 작성한 코드

선언부분

import numpy as np
import matplotlib.pyplot as plt

ACTION = 10
ALPHA = 0.1
EPSILON = 0.1
ACTION_LIST = [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0]
C_ACTION_LIST= [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0]
sample_n=[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

 

sample average를 계산하는 부분

def sample_average(p_action_value, n):
    n+=1
    reward_dist = np.random.normal(0, 0.01, 1000)
    reward = np.random.choice(reward_dist, 1)
    
    return p_action_value + n*(reward - p_action_value)

 

constant_average로 계산하는 부분

def constant_average(p_action_value):
    reward_dist = np.random.normal(0, 0.01, 1000)
    reward = np.random.choice(reward_dist, 1)
    
    return p_action_value + ALPHA*(reward - p_action_value)

 

sample average로 평균 reward를 계산하는 부분, 확률적으로 선택하는 것을 어떻게 해야하나 처음에는 고민 좀 했음

def avg_reward():
    reward_list= []
    
    for idx in range(10000):
        action_idx = np.argmax(ACTION_LIST)
        nprand = np.random.rand(1)

        if nprand > EPSILON:
            # greedy하게 선택
            ACTION_LIST[action_idx] = sample_average(ACTION_LIST[action_idx], sample_n[action_idx])
        else:
            index = np.random.randint(10, size=1)[0]
        
            while ACTION_LIST[index] == ACTION_LIST[action_idx]:
                index+=1
                if index == 10:
                    index = 0
        
            ACTION_LIST[index] = sample_average(ACTION_LIST[index], sample_n[index])
            
        reward_list.append(sum(ACTION_LIST) / (idx+1))        
        
    return reward_list

 

constant average로 평균 reward를 계산하는 부분, 위의 코드를 거의 그대로 복사했다

def avg_reward2():
    reward_list=[]
    
    for idx in range(10000):
        action_idx = np.argmax(ACTION_LIST)
        nprand = np.random.rand(1)
    
        if nprand > EPSILON:
            # greedy하게 선택
            C_ACTION_LIST[action_idx] = constant_average(C_ACTION_LIST[action_idx])
        else:
            index = np.random.randint(10, size=1)[0]
        
            while C_ACTION_LIST[index] == C_ACTION_LIST[action_idx]:
                index+=1
                if index == 10:
                    index = 0
        
            C_ACTION_LIST[index] = constant_average(C_ACTION_LIST[index])
            
        reward_list.append(sum(C_ACTION_LIST) / (idx+1))
        
    return reward_list

 

matplotlib로 시각화

def visualize(sample, const):
    plt.plot(sample, label='sample')
    plt.plot(const, label='const')
    
    plt.ylim(-0.0005, 0.0001)
    plt.xlabel('steps')
    plt.ylabel('avg reward')
    plt.legend()
    
    plt.show()

 

이것들을 합해서 다음과 같이

sample_reward=avg_reward()
const_reward = avg_reward2()
visualize(sample_reward, const_reward)

 

 

Reference : Reinforcement Learning : An Introduction