chapter 4 Dynamic Programming Example 도박사 문제

광고 한 번씩 눌러주세요! 블로그 운영에 큰 힘이 됩니다 :)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2020/05/01 - [관심있는 주제/RL] - 강화학습 - Dynamic Programming 공부

2020/05/05 - [관심있는 주제/RL] - chapter 4 Dynamic Programming Example Grid World

2020/05/05 - [관심있는 주제/RL] - chapter 4 Dynamic Programming Example Car Rental (in-place)

2020/05/05 - [관심있는 주제/RL] - chapter 4 Dynamic Programming Example 도박사 문제

 

 

문제 정의¶

한 도박사가 연속된 동전 던지기의 결과를 맞추는 내기를 할 기회를 얻 게 된다. 동전의 앞면이 나오면 도박사는 자신이 내건 액수만큼의 돈을 따게 되고, 뒷면이 나오 면 그 액수만큼의 돈을 잃는다.

도박사가 자신의 목표 금액인 100달러를 따거나 수중에 있는 돈을 모두 잃으면 게임은 끝난다. 매번의 동전 던지기에서, 도박사는 자신이 보유한 자금 중에서 얼마를 내걸지 결정해야 한다. 이때 금액의 단위는 1달러다 이 문제를 할인되지 않은 에피소딕 유한 MDP로 형식화할 수 있다.

도박사가 자신의 목표에 도달하게끔 하는 행동 에 대한 보상은 +1이고, 이를 제외한 나머지 행동의 보상은 0이다

최적 정책은 도박사가 목 표에 도달할 확률을 최대로 만든다

In [3]:

import matplotlib
import matplotlib.pyplot as plt
import numpy as np

matplotlib.use('Agg')

In [29]:

# goal
GOAL = 100

# all states, including state 0 and state 100
STATES = np.arange(GOAL + 1)

# probability of head
HEAD_PROB = 0.2

 

Value Iteration¶

Bellman Optimality Equation¶

In [30]:

def figure_4_3():
    # state value
    state_value = np.zeros(GOAL + 1)
    """
    100에 도달하면 1점
    """
    state_value[GOAL] = 1.0
    sweeps_history = []

    # value iteration
    while True:
        old_state_value = state_value.copy()
        sweeps_history.append(old_state_value)

        for state in STATES[1:GOAL]:
            # get possilbe actions for current state
            actions = np.arange(min(state, GOAL - state) + 1)
            action_returns = []
            for action in actions:
                action_returns.append(
                    HEAD_PROB * state_value[state + action] + 
                    (1 - HEAD_PROB) * state_value[state - action]
                )
            """
            Policy Iteration 1 STEP + Policy Improvement을 동시에 함
            k 번째 중에서 action 했던 것 중에서 가장 큰 max값만 사용한다.
            """
            new_value = np.max(action_returns)
            state_value[state] = new_value
        delta = abs(state_value - old_state_value).max()
        if delta < 1e-9:
            sweeps_history.append(state_value)
            break

    # compute the optimal policy
    """
    학습된 가치 함수에서 최적의 정책을 계산하기
    가끔식 올인을 하는 경우가 있다.
    """
    policy = np.zeros(GOAL + 1)
    for state in STATES[1:GOAL]:
        actions = np.arange(min(state, GOAL - state) + 1)
        action_returns = []
        for action in actions:
            action_returns.append(
                HEAD_PROB * state_value[state + action] + 
                (1 - HEAD_PROB) * state_value[state - action]
            )

        # round to resemble the figure in the book, see
        # https://github.com/ShangtongZhang/reinforcement-learning-an-introduction/issues/83
        policy[state] = actions[np.argmax(np.round(action_returns[1:], 5)) + 1]

    plt.figure(figsize=(10, 20))

    plt.subplot(2, 1, 1)
    for sweep, state_value in enumerate(sweeps_history):
        plt.plot(state_value, label='sweep {}'.format(sweep))
    plt.xlabel('Capital')
    plt.ylabel('Value estimates')
    plt.legend(loc='best')

    plt.subplot(2, 1, 2)
    plt.scatter(STATES, policy)
    plt.xlabel('Capital')
    plt.ylabel('Final policy (stake)')

    plt.savefig('./images/figure_4_3.png')
    plt.close()

In [31]:

if __name__ == '__main__':
    figure_4_3()

 

2020/05/01 - [관심있는 주제/RL] - 강화학습 - Dynamic Programming 공부

2020/05/05 - [관심있는 주제/RL] - chapter 4 Dynamic Programming Example Grid World

2020/05/05 - [관심있는 주제/RL] - chapter 4 Dynamic Programming Example Car Rental (in-place)

2020/05/05 - [관심있는 주제/RL] - chapter 4 Dynamic Programming Example 도박사 문제