CS234 Assignment 1-4 solution 및 풀이 (코드)

*Assignment 1-3은 본인의 수학적 실력 부족으로 인해 풀이까지 하긴 힘들 것 같습니다..ㅠㅠ

 

코딩 부분은 채워넣어야 하는 부분만 코드를 따로 올릴테니, 다른 추가 코드들은 직접 사이트에서 다운받아 주세요.

http://web.stanford.edu/class/cs234/assignment1/index.html

CS234: Reinforcement Learning

 

(a) (코딩 문제) vi_and_pi.py를 읽고, policy_evaluation, policy_improvement, policy_iteration을 구현하라.

maxₛ |old_V(s) - new_V(s)|로 정의되는 stopping tolerance는 10⁻³이고, γ=0.9이다. optimal value function과 optimal policy를 return하여라. [10점]

def policy_evaluation(P, nS, nA, policy, gamma=0.9, tol=1e-3):
    """Evaluate the value function from a given policy.

    Parameters
    ----------
    P, nS, nA, gamma:
        defined at beginning of file
    policy: np.array[nS]
        The policy to evaluate. Maps states to actions.
    tol: float
        Terminate policy evaluation when
            max |value_function(s) - prev_value_function(s)| < tol
    Returns
    -------
    value_function: np.ndarray[nS]
        The value function of the given policy, where value_function[s] is
        the value of state s
    """

    ############################
    # YOUR IMPLEMENTATION HERE #
    V = np.zeros(nS)
    while True:
        new_V = np.zeros(nS)
        for state in range(nS):
            for (prob, next_state, reward, end) in P[state][policy[state]]:
                new_V[state] += prob * (reward + V[next_state] * gamma)
        if np.all(np.abs(new_V - V) < tol):
            break
        V = new_V.copy()
    ############################

    return new_V
    
    def policy_improvement(P, nS, nA, value_from_policy, policy, gamma=0.9):
    """Given the value function from policy improve the policy.

    Parameters
    ----------
    P, nS, nA, gamma:
        defined at beginning of file
    value_from_policy: np.ndarray
        The value calculated from the policy
    policy: np.array
        The previous policy.

    Returns
    -------
    new_policy: np.ndarray[nS]
        An array of integers. Each integer is the optimal action to take
        in that state according to the environment dynamics and the
        given value function.
    """

    new_policy = np.zeros(nS, dtype='int')
    ############################
    # YOUR IMPLEMENTATION HERE #
    for state in range(nS):
        Q = np.zeros(nA)
        temp = -99
        for action in range(nA):
            for (prob, next_state, reward, end) in P[state][action]:
                Q[action] += prob * (reward + gamma * value_from_policy[next_state])

            if temp < Q[action]:
                temp = Q[action]
                new_policy[state] = action
    ############################

    return new_policy
    
    def policy_iteration(P, nS, nA, gamma=0.9, tol=10e-3):
    """Runs policy iteration.

    You should call the policy_evaluation() and policy_improvement() methods to
    implement this method.

    Parameters
    ----------
    P, nS, nA, gamma:
        defined at beginning of file
    tol: float
        tol parameter used in policy_evaluation()

    Returns:
    ----------
    value_function: np.ndarray[nS]
    policy: np.ndarray[nS]
    """

    value_function = np.zeros(nS)
    policy = np.zeros(nS, dtype=int)

    ############################
    # YOUR IMPLEMENTATION HERE #

    i = 0
    new_policy = np.zeros(nS, dtype=int)

    while i == 0 or np.sum(abs(new_policy - policy)) > 0:
        policy = np.copy(new_policy)
        value_function = policy_evaluation(P, nS, nA, policy, gamma, tol)
        new_policy = policy_improvement(P, nS, nA, value_function, policy, gamma)
        i += 1

    ############################
    return value_function, new_policy

 

그냥 수식을 코드로 옮겼습니다.. 혹시 이 부분 구현이 잘못된 것 같다거나, 궁금한 점이 있으면 따로 댓글로 질문 부탁드립니다.

 

(b) (코딩 문제) vi_and_pi.py에서 value_iteration을 구현하여라. stopping tolerance는 10⁻³이고, γ=0.9이다. optimal value function과 optimal policy를 return하여라. [10점]

 

def value_iteration(P, nS, nA, gamma=0.9, tol=1e-3):
    """
    Learn value function and policy by using value iteration method for a given
    gamma and environment.

    Parameters:
    ----------
    P, nS, nA, gamma:
        defined at beginning of file
    tol: float
        Terminate value iteration when
            max |value_function(s) - prev_value_function(s)| < tol
    Returns:
    ----------
    value_function: np.ndarray[nS]
    policy: np.ndarray[nS]
    """

    policy = np.zeros(nS, dtype=int)
    ############################
    # YOUR IMPLEMENTATION HERE #

    V = np.zeros(nS)
    while True:
        new_V = np.zeros(nS)
        for state in range(nS):
            for action in range(nA):
                temp=0
                for (prob, next_state, reward, end) in P[state][action]:
                    temp += prob * (reward +gamma * V[next_state])

                if temp > new_V[state]:
                    new_V[state] = temp

        if np.all(np.abs(new_V - V) < tol):
            break
        V = new_V.copy()

        policy = policy_improvement(P, nS, nA, V, policy, 0.9)
    ############################
    return V, policy

이것도 마찬가지로 그냥 ppt에 있던 수식을 그대로 코드로 구현했습니다.

처음에 state나 action 둘 중 하나만 for문을 돌렸다가 실패했던 기억이 있습니다.

 

(c) 각각의 방법 (vi와 pi)를 Deterministic-4x4-FrozenLake-v0과 Stochastic-4x4-FrozenLake-v0의 environment에서 실행시켜 보아라. 두 번째 environment에서, world의 dynamics는 무작위적(stochastic)이다. (world가 어떻게 움직이는지 랜덤이라는 뜻이다.) 이 무작위성은 반복의 횟수와 policy의 결과에 어떤 영향을 미치는가? [5점]

 

sol)

다음은 본인의 코드를 돌려 나온 결과값이다. (iter의 횟수를 count하는 코드는 위의 코드에는 없다..)

 

 

 

Deterministic-4x4-FrozenLake-v0

 

PI iter : 7

optimal Value Function
[0.59  0.656 0.729 0.656 0.656 0.    0.81  0.    0.729 0.81  0.9   0.
 0.    0.9   1.    0.   ]
Optimal Policy
[1 2 1 0 1 0 1 0 2 1 1 0 0 2 2 0]

 

VI iter : 7

optimal Value Function
[0.59  0.656 0.729 0.656 0.656 0.    0.81  0.    0.729 0.81  0.9   0.
 0.    0.9   1.    0.   ]
Optimal Policy
[1 2 1 0 1 0 1 0 2 1 1 0 0 2 2 0]

 

 

 

 

Stochastic-4x4-FrozenLake-v0

 

PI iter : 6
optimal Value Function
[0.062 0.056 0.07  0.051 0.086 0.    0.11  0.    0.141 0.244 0.297 0.
 0.    0.377 0.638 0.   ]
Optimal Policy
[0 3 0 3 0 0 0 0 3 1 0 0 0 2 1 0]

 

VI iter : 27
optimal Value Function
[0.062 0.055 0.07  0.051 0.085 0.    0.11  0.    0.14  0.244 0.297 0.
 0.    0.377 0.638 0.   ]
Optimal Policy
[0 3 0 3 0 0 0 0 3 1 0 0 0 2 1 0]

 

 

 

실제로 코드를 돌려 보면, Deterministic의 경우에는 Policy Iteration, Value Iteration 모두 한번에 Goal로 잘 도착한다.

하지만 Stochastic environment에서는 굉장히 머뭇머뭇하며 진행되는 경향이 있는 듯 하다.

 

Iteration 횟수는 Value Iteration같은 경우 증가했으나, Policy Iteration의 경우 1 감소했다.

VI에서 Iteration 횟수가 증가하는 것은 이해가 되지만, PI에서 왜 Iteration 횟수가 감소했는지는 잘 이해가 되지 않는다. (ㅠㅠ)

 

또한, environment의 stochastic하게 되면 Deterministic한 environment와 Optimal Policy도 달라지는 것을 확인했다.

VI와 PI가 동일한 Policy로 Converge한 것을 보면, 학습은 잘 된 것 같다.

 

(혹시 코드가 틀렸다거나... Policy Iteration에서 왜 Iter 횟수가 1 감소했는지 알려주실분 있으면 댓글 부탁드립니다... ㅠㅠ)

 

 

아무튼, 이것으로 CS234 assignment 1 풀이는 마치도록 하겠다.

이젠 assignment 2다!!