cdjs의 코딩 공부방

1. [코딩] q3_nature.py의 get_q_values_op를 작성하여 [mnih2015human] 논문에 나와있는 대로 deep Q-network를 만들어보자.

나머지 코드들은 linear approximation에서 짠 코드 그대로 따라갈 것이다.

python q3_nature.py 명령어로 이를 CPU로 돌려보아라. 대략 1분에서 2분정도 걸릴 것이다. [10점]

sol) nature지 아래에 실린 architecture 란에 보면 : 

The first hidden layer convolves 32 filters of 8 X 8 with stride 4 with the input image and applies a rectifier nonlinearity.
The second hidden layer convolves 64 filters of 4 X 4 with stride 2, again followed by a rectifier nonlinearity
This is followed by a third convolutional layer that convolves 64 filters of 3 X 3 with stride 1 followed by a rectifier.
The final hidden layer is fully-connected and consists of 512 rectifier units.

The output layer is a fully-connected linear layer with a single output for each valid action.

라는 설명이 있습니다.

이를 대충 해석하면,

첫번째 convolutional layer은 32 filters, 8*8 kernel size, stride 4, ReLU

두번째 convolutional layer은 64 filters, 4*4 kernel size, stride 2, ReLU

세번째 convolutional layer은 64 filters, 3*3 kernel size, stride 1, ReLU

마지막 hidden layer은 fully-connected layer로 512개의 output에 ReLU,

output layer은 각각의 action에 대한 single output이 나오는 fully-connected layer이라고 합니다.

이것을 코드로 구현하면 다음과 같은 코드가 나옵니다.

class NatureQN(Linear):
    """
    Implementing DeepMind's Nature paper. Here are the relevant urls.
    https://storage.googleapis.com/deepmind-data/assets/papers/DeepMindNature14236Paper.pdf
    https://www.cs.toronto.edu/~vmnih/docs/dqn.pdf
    """

    def get_q_values_op(self, state, scope, reuse=False):
        """
        Returns Q values for all actions

        Args:
            state: (tf tensor) 
                shape = (batch_size, img height, img width, nchannels)
            scope: (string) scope name, that specifies if target network or not
            reuse: (bool) reuse of variables in the scope

        Returns:
            out: (tf tensor) of shape = (batch_size, num_actions)
        """
        # this information might be useful
        num_actions = self.env.action_space.n

        ##############################################################
        """
        TODO: implement the computation of Q values like in the paper
                https://storage.googleapis.com/deepmind-data/assets/papers/DeepMindNature14236Paper.pdf
                https://www.cs.toronto.edu/~vmnih/docs/dqn.pdf

              you may find the section "model architecture" of the appendix of the 
              nature paper particulary useful.

              store your result in out of shape = (batch_size, num_actions)

        HINT: 
            - You may find the following functions useful:
                - tf.layers.conv2d
                - tf.layers.flatten
                - tf.layers.dense

            - Make sure to also specify the scope and reuse

        """

        """
        The first hidden layer convolves 32 filters of 8 X 8 with stride 4 with the input image and applies a rectifier nonlinearity.
        The second hidden layer convolves 64 filters of 4 X 4 with stride 2, again followed by a rectifier nonlinearity
        This is followed by a third convolutional layer that convolves 64 filters of 3 X 3 with stride 1 followed by a rectifier.
        The final hidden layer is fully-connected and consists of 512 rectifier units.
        The output layer is a fully-connected linear layer with a single output for each valid action.
        """
        ##############################################################
        ################ YOUR CODE HERE - 10-15 lines ################
        input = state
        with tf.variable_scope(scope,reuse=reuse):
            conv1 = tf.layers.conv2d(input, 32, (8, 8), strides=4, activation=tf.nn.relu, name='conv1')
            conv2 = tf.layers.conv2d(conv1, 64, (4, 4), strides=2, activation=tf.nn.relu, name='conv2')
            conv3 = tf.layers.conv2d(conv2, 64, (3, 3), strides=1, activation=tf.nn.relu, name='conv3')
            flat = tf.layers.flatten(conv3, name='flatten')
            fc = tf.layers.dense(flat, 512, activation=tf.nn.relu, name='fully-connected')
            out = tf.layers.dense(fc, num_actions, name='out')


        pass

        ##############################################################
        ######################## END YOUR CODE #######################
        return out

(보기 좋으라고 Class 선언부부터 넣어두지만, 구현한 부분은 가장 아래 10줄 가량입니다. input = state 부터...)

2. (written 5pts) Attach the plot of scores, scores.png, from the directory results/q3 nature to your writeup. Compare this model with linear approximation. How do the final performances compare? How about the training time?

2. results/q3 nature에서 scores.png 사진을 첨부하시오. linear approximation model과 비교하시오.

성능은 어떻게 차이가 나는가? 훈련 시간은 얼마나 차이가 나는가?

일단, DQN보다 Linear Approximation이 더 빠르게 converge 하기 시작하는 모습을 볼 수 있다.

심지어는 DQN을 돌릴 때 가끔씩 reward가 4.0에서 4.1로 가지 못한 채 training이 끝나는 모습도 볼 수 있었다.

아무래도 DQN이 Linear Approximation보다 더 unstable한 방식이라 그런 것 같다.

또한, training 시간도 DQN쪽이 더 오래 걸린다.

이것을 통해, 이렇게 간단한 test environment 같은 경우는 Linear Approximation이 더 잘 작동할 수도 있다는 것을 알게 되었다.

즉, environment에 따라 서로 다른 최적의 모델이 존재한다는 것을 알 수 있다.

1. x를 다음과 같이 정의할 때, ^q(s, a, w) = wTx(s, a)를 만족한다면 section 2의 (1) 식과 (2) 식이 동일하다는 것을 증명하시오. [3점]

(수식이 너무 많아서 다 쓰긴 좀... 그냥 위에 있는거 대충 보고 합시다...)

sol)

어차피 x(s, a)ₛ',ₐ' 가 0이 되면 w가 뭐든간에 ^q은 0이 되니까,

x(s, a)ₛ,ₐ = 1인 경우를 (2)번 식에 적용하면,

wₛ,ₐ= wₛ,ₐ + α(r + 𝛾max wₛ,ₐ - wₛ,ₐ)∇wₛ,ₐ wₛ,ₐ 

(수식 ㅂㄷㅂㄷ;;; 대충 뭔뜻인지 이해하셨으면 좋겠는데... 그냥 ^q를 w로 바꾸고, w도 wₛ,ₐ로 바꾼 식...)

이 때, ∇wₛ,ₐ wₛ,ₐ = 1이므로 다시 정리하면

wₛ,ₐ= wₛ,ₐ + α(r + 𝛾max wₛ',ₐ' - wₛ,ₐ)

그리고 이를 다시 Q(s, a)로 정리하면 (1)번 식이 나온다.

2. qˆ(s, a, w) = wT x(s, a)이라고 할 때, value function parameter w ∈ Rⁿ에 대한 미분값을 구하고, w의 update rule을 적으시오. [3점]

sol) q^(s, a, w) = wTx(s, a)라고 했으므로,

∇w q^(s, a, w) = ∇w wTx(s, a) = x(s, a) 이다.

그리고 update rule은 아까 section 2 의 (2)번 식에 따라,

w = w + α(r + 𝛾max a0∈A qˆ(s 0 , a0 , w) − qˆ(s, a, w) )x(s, a)

가 된다. (그냥 뒤에 ∇w q^(s, a, w) 부분을 x(s,a)로 바꿈)

3. [코딩] 이제 tensorflow로 linear approximation을 구현할 것이다. 이 문제는 나머지 assignment 문제를 풀기 위한 pipeline을 작성하게 할 것이다. q2linear.py의 함수 중 다음의 함수를 구현할 것이다(q2linear.py를 읽어보라) :

• add_placeholders_op

• get_q_values_op

• add_update_target_op

• add_loss_op

• add_optimizer_op

작성한 코드를 python q2 linear.py 명령어를 사용해서 CPU에서 돌려보아라. 그러면 test environment에서 linear approximation을 실행시킬 것이다. 실행하는데 대략 1분에서 2분 정도 걸릴 것이다.

class Linear(DQN):
    """
    Implement Fully Connected with Tensorflow
    """

    def add_placeholders_op(self):
        """
        Adds placeholders to the graph

        These placeholders are used as inputs to the rest of the model and will be fed
        data during training.
        """
        # this information might be useful
        state_shape = list(self.env.observation_space.shape)
        ##############################################################
        """
        TODO: 
            Add placeholders:
            Remember that we stack 4 consecutive frames together.
                - self.s: batch of states, type = uint8
                    shape = (batch_size, img height, img width, nchannels x config.state_history)
                - self.a: batch of actions, type = int32
                    shape = (batch_size)
                - self.r: batch of rewards, type = float32
                    shape = (batch_size)
                - self.sp: batch of next states, type = uint8
                    shape = (batch_size, img height, img width, nchannels x config.state_history)
                - self.done_mask: batch of done, type = bool
                    shape = (batch_size)
                - self.lr: learning rate, type = float32
        
        (Don't change the variable names!)
        
        HINT: 
            Variables from config are accessible with self.config.variable_name.
            Check the use of None in the dimension for tensorflow placeholders.
            You can also use the state_shape computed above.
        """
        ##############################################################
        ################YOUR CODE HERE (6-15 lines) ##################
        batch_size = 5
        img_height = state_shape[0]
        img_width = state_shape[1]
        n_channels = state_shape[2]
        self.s = tf.placeholder(dtype=tf.uint8,
                                shape=[None, img_height, img_width, n_channels * config.state_history],
                                name='state')
        self.a = tf.placeholder(dtype=tf.int32, shape=[None], name='action')
        self.r = tf.placeholder(dtype=tf.float32, shape=[None], name='reward')
        self.sp = tf.placeholder(dtype=tf.uint8,
                                 shape=[None, img_height, img_width, n_channels * config.state_history],
                                 name='next_state')
        self.done_mask = tf.placeholder(dtype=tf.bool, shape=[None], name='done_mask')
        self.lr = tf.placeholder(dtype=tf.float32, shape=(), name='lr')

        ##############################################################
        ######################## END YOUR CODE #######################

    def get_q_values_op(self, state, scope, reuse=False):
        """
        Returns Q values for all actions

        Args:
            state: (tf tensor)
                shape = (batch_size, img height, img width, nchannels x config.state_history)
            scope: (string) scope name, that specifies if target network or not
            reuse: (bool) reuse of variables in the scope

        Returns:
            out: (tf tensor) of shape = (batch_size, num_actions)
        """
        # this information might be useful
        num_actions = self.env.action_space.n

        ##############################################################
        """
        TODO: 
            Implement a fully connected with no hidden layer (linear
            approximation with bias) using tensorflow.

        HINT: 
            - You may find the following functions useful:
                - tf.layers.flatten
                - tf.layers.dense

            - Make sure to also specify the scope and reuse
        """
        ##############################################################
        ################ YOUR CODE HERE - 2-3 lines ##################

        input = tf.layers.flatten(state, name=scope)
        out = tf.layers.dense(input, num_actions, name=scope, reuse=reuse)

        ##############################################################
        ######################## END YOUR CODE #######################

        return out

    def add_update_target_op(self, q_scope, target_q_scope):
        """
        update_target_op will be called periodically
        to copy Q network weights to target Q network

        Remember that in DQN, we maintain two identical Q networks with
        2 different sets of weights. In tensorflow, we distinguish them
        with two different scopes. If you're not familiar with the scope mechanism
        in tensorflow, read the docs
        https://www.tensorflow.org/programmers_guide/variable_scope

        Periodically, we need to update all the weights of the Q network
        and assign them with the values from the regular network.
        Args:
            q_scope: (string) name of the scope of variables for q
            target_q_scope: (string) name of the scope of variables
                        for the target network
        """
        ##############################################################
        """
        TODO: 
            Add an operator self.update_target_op that for each variable in
            tf.GraphKeys.GLOBAL_VARIABLES that is in q_scope, assigns its
            value to the corresponding variable in target_q_scope

        HINT: 
            You may find the following functions useful:
                - tf.get_collection
                - tf.assign
                - tf.group (the * operator can be used to unpack a list)

        (be sure that you set self.update_target_op)
        """
        ##############################################################
        ################### YOUR CODE HERE - 5-10 lines #############

        q = tf.get_collection(tf.GraphKeys.TRAINABLE_VARIABLES, scope=q_scope)
        target_q = tf.get_collection(tf.GraphKeys.TRAINABLE_VARIABLES, scope=target_q_scope)

        assign = [tf.assign(target_q[i], q[i]) for i in range(len(q))]
        self.update_target_op = tf.group(*assign)

        pass

        ##############################################################
        ######################## END YOUR CODE #######################

    def add_loss_op(self, q, target_q):
        """
        Sets the loss of a batch, self.loss is a scalar

        Args:
            q: (tf tensor) shape = (batch_size, num_actions)
            target_q: (tf tensor) shape = (batch_size, num_actions)
        """
        # you may need this variable
        num_actions = self.env.action_space.n
        ##############################################################
        """
        TODO: 
            The loss for an example is defined as:
                Q_samp(s) = r if done
                          = r + gamma * max_a' Q_target(s', a')
                loss = (Q_samp(s) - Q(s, a))^2 
        HINT: 
            - Config variables are accessible through self.config
            - You can access placeholders like self.a (for actions)
                self.r (rewards) or self.done_mask for instance
            - You may find the following functions useful
                - tf.cast
                - tf.reduce_max
                - tf.reduce_sum
                - tf.one_hot
                - tf.squared_difference
                - tf.reduce_mean
        """
        ##############################################################
        ##################### YOUR CODE HERE - 4-5 lines #############

        notdone = 1 - tf.cast(self.done_mask, tf.float32)
        action = tf.one_hot(self.a, num_actions)
        q_samp = self.r + notdone * (self.config.gamma * tf.reduce_max(target_q, axis=1))
        q_s = tf.reduce_sum(q * action, axis=1)
        self.loss = tf.reduce_mean((q_samp - q_s)**2)
        # self.loss = tf.squared_difference(q_samp, q_s)

        ##############################################################
        ######################## END YOUR CODE #######################

    def add_optimizer_op(self, scope):
        """
        Set self.train_op and self.grad_norm
        Args:
            scope: (string) scope name, that specifies if target network or not
        """

        ##############################################################
        """
        TODO: 
            1. get Adam Optimizer
            2. compute grads with respect to variables in scope for self.loss
            3. if self.config.grad_clip is True, then clip the grads
                by norm using self.config.clip_val 
            4. apply the gradients and store the train op in self.train_op
                (sess.run(train_op) must update the variables)
            5. compute the global norm of the gradients (which are not None) and store 
                this scalar in self.grad_norm

        HINT: you may find the following functions useful
            - tf.get_collection
            - optimizer.compute_gradients
            - tf.clip_by_norm
            - optimizer.apply_gradients
            - tf.global_norm
             
             you can access config variables by writing self.config.variable_name
        """
        ##############################################################
        #################### YOUR CODE HERE - 8-12 lines #############

        optimizer = tf.train.AdamOptimizer(learning_rate=self.lr)
        variable = tf.get_collection(tf.GraphKeys.TRAINABLE_VARIABLES, scope=scope)
        gradient = optimizer.compute_gradients(self.loss, variable)
        if self.config.grad_clip is True:
            clip_grad = [(tf.clip_by_norm(i[0], self.config.clip_val), i[1]) for i in gradient]
        self.train_op = optimizer.apply_gradients(clip_grad)

        self.grad_norm = tf.global_norm([i[0] for i in clip_grad])
        pass

        ##############################################################
        ######################## END YOUR CODE #######################

그냥 Linear class 전부 올리겠습니다. 어차피 저거 처음부터 끝까지 다 짜야되는거라;

파이썬 사용법에 그렇게 익숙치 않고, 텐서플로우를 잘 사용하지 않다 보니까 이것저것 다 찾아보며 하느라 힘들었네요.

4. test environment에서 얻을 수 있는 최적의 reward를 얻었는가? results/q2 linear에 있는 scores.png 파일을 첨부하여라. [5점]

sol...?) section 1에서 봤던 최적의 reward 4.1이 나오는 모습이다.

앞으로 얼마 안남았다.. 달려봅시다!

위에 나온 대부분의 내용들은 전 강의 DQN에 나와있는 내용이므로, 설명은 생략하겠습니다.

사실, 위에 나오는 건 그냥 배웠던 거 다시 설명하는 것 뿐이라...

설명하지 않았던 부분만 간단히 짚고 넘어간다.

실행 중에 (훈련하는 중에?), 버퍼에 (s, a, r, s') transitions을 집어넣는다. 새로 transitions가 들어오면 오래 된 transitions는 삭제된다. 파라미터들을 SGD update를 사용해 파라미터를 update할 때, 버퍼에서 minibatch를 sampling해서 update한다.

훈련 중엔 ε-greedy Exploration policy 를 사용하는데, deepmind의 논문에는 처음에는 ε=1로 시작했다가 백만 번 진행 중에 ε = 0.1까지 줄어든다. test할 때는, ε = 0.05로 두고 test한다.

참고 할 점들:

• 이 assignment에서는 replay 버퍼에서 minibatch를 sampling해서 w를 learning_freq 횟수에 한번 씩 update한다. 

• Deepmind의 Deep Q network는 state s 를 input으로 받고, action의 갯수와 동일한 크기의 벡터를 output으로 낸다.

Pong environment에서는 action 6개가 있으므로, ^q(s, w)도 실수 범위 내에서 6개의 Vector를 가진다. (ℝ^6)

• 이 deep Q network의 input은 연속적인 4개의 step을 합친 것이고, 이를 preprocessing하면 (80 * 80 * 4)의 shape가 나온다.

1. experience replay를 사용할 때의 이점 한 가지를 대시오. [3점]

sol) 게임의 경우 전 프레임과 다음 프레임의 연관관계가 굉장히 끈끈한데, 이러한 연관관계는 SGD에 필요한 I.I.D 가정을 충족시키지 못한다.

이를 충족시키기 위해, experience replay를 사용하면 현재 프레임과 독립적인 프레임의 튜플을 update에 활용하여 SGD에 필요한 I.I.D 가정을 어느 정도 충족시킬 수 있다.

또, history에 저장되는 양을 늘림으로써 놓칠 수 있는 experience들을 다시 활용할 수도 있을 것이다.

(특히 prioritize experience replay를 사용하면 더 좋겠다.)

2. target network를 사용했을 때의 이점을 한 가지 대시오. [3점]

sol) Q-learning을 사용할 경우, update하는 과정에서 지속적으로 optimal한 값이 변화하게 된다. 그러면 w값이 막 미쳐돌아서 infinite로 날라갈 수도 있고, 굉장히 unstable해지는데, w값을 어느 정도 고정시켜주면서 이를 stable하게 잡아준다.

3. Q-Function을 ^q(s, w)∈ℝ^k 과 같이 나타낼 때의 이점을 한 가지를 대시오. [3점]

sol) 저렇게 벡터 형식으로 나타내면, 각각의 action에 대한 scalar값으로 나타내는 것 보다 연산 효율이 좋다.

4. (코딩문제) q1_schedule.py에 있는 get_action 과 update 함수를 구현하고, python q1_schedule.py로 구현한 것을 실행시켜 보시오. [3점]

참고 : http://web.stanford.edu/class/cs234/assignment2/assignment2.zip 에서 assignment2에 필요한 기초 코드를 받을 수 있다.

구현해야 되는 함수의 코드만 작성하겠다.

    def update(self, t):
        """
        Updates epsilon

        Args:
            t: int
                frame number
        """
        ##############################################################
        """
        TODO: modify self.epsilon such that 
			  it is a linear interpolation from self.eps_begin to 
			  self.eps_end as t goes from 0 to self.nsteps
			  For t > self.nsteps self.epsilon remains constant
        """
        ##############################################################
        ################ YOUR CODE HERE - 3-4 lines ##################

        if t < self.nsteps:
            self.epsilon = self.eps_begin - (self.eps_begin - self.eps_end) * t / self.nsteps
        else:
            self.epsilon = self.eps_end

        ##############################################################
        ######################## END YOUR CODE ############## ########

위 코드는 ε-greedy policy를 더 fancy하게 만들기 위한 코드이다.

처음에는 epsilon값을 크게 잡아뒀다가, 가면 갈수록 점점 더 epsilon값을 작게 만들어 주는 것이다.

참고로 위 네 줄 짜리 코드는 다음의 세 줄짜리 코드로 줄일 수도 있다.

        self.epsilon = self.eps_end
        if t < self.nsteps:
            self.epsilon = self.eps_begin - (self.eps_begin - self.eps_end) * t / self.nsteps

    def get_action(self, best_action):
        """
        Returns a random action with prob epsilon, otherwise returns the best_action

        Args:
            best_action: int 
                best action according some policy
        Returns:
            an action
        """
        ##############################################################
        """
        TODO: with probability self.epsilon, return a random action
                else, return best_action

                you can access the environment via self.env

                you may use env.action_space.sample() to generate 
                a random action        
        """
        ##############################################################
        ################ YOUR CODE HERE - 4-5 lines ##################

        if np.random.random() < self.epsilon:
            return self.env.action_space.sample()
        else:
            return best_action

        ##############################################################
        ######################## END YOUR CODE #######################

위 코드는 그냥 아까 전에 잡아둔 epsilon값을 바탕으로 action을 return하는 함수이다.

* 원래 해석 다 쓰고 쓸려 했는데 해석만 하다 보니깐 답답해 죽겠어서 그냥 풀면서 해석본 올리겠읍니다 ㅎㅎ..

어차피 딱 보니 제가 풀 클라스가 아닌 것들이 있는 것 같아서...

최종 해석본은 Assignment 풀이 끝나면 한번에 올리겠습니다.

1. Test Environment

다음과 같은 environment가 주어진다.

State 4개 : 0, 1, 2, 3

action 4개 : 0, 1, 2, 3, 4

action 0,1,2,3일때는 각각 state 0,1,2,3으로 가고, action 4일 때는 원래 state에 남아있는다.

reward는 위의 표를 참고하라.

한 episode는 time step 5번 (action을 5번 취한다)동안 지속된다.

또한, 언제나 state s0에서 시작한다.

(s, a, r, s')의 형태로 예시를 들면,

(0, 1, -0.2, 1, 2, 0, 2, 4, 0, 2, 3, 1, 3, 0 0.1, 0)

가 한 가지 예시이다. (자세한 것은 위의 그림을 참고하라.)

1. 위 test environment에서, 한 episode에서 얻을 수 있는 최대의 reward는? [5점]

sol) 다른 reward들은 죄다 -1 ~ 0.2 언저리에서 놀고 있지만, s2에서 a1을 취하는 경우는 reward가 2가 나온다.

어떤 경우에도 저 s2로 가서 a1을 취하는 것이 최선이다! (reward 0.2를 time step 5회에 걸쳐 계속 얻더라도 reward 2를 받는게 더욱 효율적이다)

그러므로, s0에서 시작하므로 s2로 우선 가는 것이 최선의 선택이다.

(s0, a2, 0, s2)

그리고 s2에서 a1을 취하면 reward 2를 얻을 수 있으므로,

(s0, a2, 0, s2, a1, 2, s1)

또 뒤에 time step이 3회나 남았으므로 다시 s2에서 a1을 취할 수 있으므로 다시 s2로 가서 a1을 취한다.

(s0, a2, 0, s2, a1, 2, s1, a2, 0, s2, a1, 2, s1)

이러면 time step은 1회가 남고, 이러면 그냥 이 상황에서 reward가 가장 높은 action을 고르는 것이 최선이므로,

s1에서 최선의 reward 0.1을 얻을 수 있는 action 0을 취하는 것이 최선의 선택이다.

(s0, a2, 0, s2, a1, 2, s1, a2, 0, s2, a1, 2, s1, a0, 0.1, s0) 

그리고 이 때 얻는 reward는 0 + 2 + 0 + 2 + 0.1 = 4.1이다.

+추가로, 가장 처음에 s0에서 a0 또는 a4를 취해서 0.1을 먼저 얻은 뒤에 가는 경우도 고려하긴 해야 한다.

하지만, 그렇게 해도 (s0, a0, 0.1, s0, a2, 0, s2, a1, 2, s1, a2, 0, s2, a1, 2, s1)으로, reward가 4.1이 되니 결국 최대의 reward는 4.1이 된다.

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

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

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

(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다!!

해석본은 아래 글에 찾아보시면 될 것 같습니다.

여기서는 풀이만 진행합니다.

(a) time step t=0인 state s0에서 action a1을 취할 때, 최종 discounted return (위 수식 참고)은 무엇인가? [5점]

sol) 처음 얻는 reward r0 = 0이고,

나머지 reward r1, r2, r3, ... , rt = 1이므로, 위 수식을 풀어 쓰면

0 + 𝛾 + 𝛾^2 + 𝛾^3 + .... = 𝛾 / (1-𝛾)

(b) time step t=0인 state s0에서 action a2를 취할 때, 최종 discounted return (위 수식 참고)은 무엇인가? optimal action은 무엇인가? [5점]

sol) 처음 얻는 reward r0 = 𝛾^2 / (1-𝛾)이고,

나머지 reward r1, r2, r3, ..., rt = 0이므로, 위 수식을 풀어 쓰면

𝛾^2 / (1-𝛾) + 0 + 0 + ... = 𝛾^2 / (1-𝛾)

그리고 0 < 𝛾 < 1이므로, 𝛾 / (1-𝛾) > 𝛾^2 / (1-𝛾) 이다.

즉, optimal action은 a1이다.

(c) 모든 state의 value를 0으로 초기화 했다고 가정하자. value iteration은 위의 수식 (n* ≥ log(1-ᵞ)/logᵞ ≥ 1/2 * log(1/1-ᵞ) * 1/(1-ᵞ)이 성립할 때 까지 sub-optimal action을 선택하는데, 이를 증명하여라.

따라서, value iteration은 1/(1-ᵞ)보다 빠르게 증가한다. (첫 번째 부등식이 옳다는 것만 보이면 된다.) [10점]

sol)

value iteration은 그때그때 최선의 value를 갖는 action을 고른다.

그렇기 때문에, Q(s0, a1) < Q(s0, a2)인 동안은 Value값이 높은 Q(s0, a2)를 계속 고르게 된다.

우선 action a2를 취할 때, s2에서 모든 Vn(s2) = 0이므로 Q값인 Qn+1(s0, a2)는 𝛾^2 / (1-𝛾)가 된다.

그리고, action a1을 취할 때의 value iteration은 다음과 같이 update된다 : 

Qn+1(s0, a1) = 0 + 𝛾Vn(s1)

Vn+1(s1) = 1 + 𝛾Vn(s1)

즉,

Qn+1(s0, a1) = 0 + 𝛾(1 + 𝛾 + 𝛾^2 + ... + 𝛾^n)

                 = 𝛾 + 𝛾^2 + ... + 𝛾^n

                 = 𝛾 * (1-𝛾^n) / (1-𝛾)

그리고 딱 저 때의 n을 n*라고 두면, action a1을 취했을 때의 Q값이 a2를 취했을 때의 Q값보다 더 크거나 같아져야 하므로,

𝛾 * (1-𝛾^n*) / (1-𝛾) >= 𝛾^2 / (1-𝛾)

이것을 n*에 대해 정리하면 좌변과 우변의 1 / (1-𝛾) 는 사라지고,

𝛾 * (1-𝛾^n*) >= 𝛾^2 에서 양변의 𝛾를 나눠주면

1-𝛾^n* >= 𝛾

𝛾^n* <= 1-𝛾

n* >= log 𝛾 (1-𝛾)  (log 밑이 𝛾, 진수가 1-𝛾) (0 < 𝛾 < 1이므로)

   >= log (1-𝛾) / log(𝛾)  (log 밑은 e)

이로써 첫 번째 부등식을 만족함을 보였다.

두, 세번째 부등식도 그냥 풀어가다 보면 만족함을 보일 수 있겠으나, 문제에서 첫 번째 부등식이 성립함을 보이기만 해도 된다고 했으니 걸러버리겠다.

해석본은 아래 글에 있습니다. 여기서는 풀이만 하도록 하겠습니다.

(a) optimal action은 (최적의 action은) 어떤 state si에서든 G에 도달할 때 까지 오른쪽으로 가는 것이다 (action a0을 취하는 것이다). 이 때, 모든 state si와 goal state G에서의 optimal value function을 구하여라. [5점]

optimal value function V(s) = R(s) + 𝛾Σ s'∈S P(s'|s)V(s') 이다.

이 때, action은 무조건 오른쪽으로 가는 것이고, deterministic한 상황이기 때문에 P(s'|s) = 1이 된다. (s'의 경우의 수는 1개이다.)

이를 정리하면,

V(s) = R(s) + 𝛾Σ s'∈S V(s')

이 때, s'은 s의 바로 오른쪽 (s=G일 때는 G)가 될 것이다.

이를 사용해 goal state G에서의 optimal value function을 구해 보면,

V(G) = R(G) + 𝛾Σ s'∈S V(G)

V(G) = 1 + 𝛾 + 𝛾^2 + 𝛾^3 + ....

       = 1/(1-𝛾)             (등비급수)

V(sₙ₋₁) = R(G) + 𝛾Σ s'∈S V(s')

         = 0 + 𝛾 + 𝛾^2 + 𝛾^3 + ....

         = 𝛾/(1-𝛾)

......

V(s₁) = 0 + 0 + 0 + ... + 𝛾ⁿ + 𝛾ⁿ⁺¹ + ....

       = 𝛾ⁿ / 1-𝛾

(b) optimal policy가 discount factor 𝛾의 영향을 받는지에 대해 서술하시오. [5점]

optimal policy의 경우, 0<𝛾인 모든 상황에서는 위의 '무조건 오른쪽으로 가는' action을 취할 것이다.

하지만 𝛾=0인 경우엔 0<𝛾인 경우와 비슷하게 무조건 오른쪽으로 가는 action만을 취하겠지만, 그 policy 말고 다른 policy 또한 optimal policy가 될 수 있다.

(오른쪽 왼쪽 오른쪽 오른쪽 오른쪽 .... 도 optimal policy라 할 수 있다.)

(c) 모든 reward 에 상수 c를 더한다고 생각해보자. (즉, G에서는 reward 1+c를, 나머지 state에서는 reward c를 받는다.)

이 때, 모든 si와 G에 대한 새로운 optimal value function을 구하시오. 상수 c를 더한 것이 optimal policy를 바꾸는가? 답을 설명하시오. [5점]

영향을 끼치지 않는다.

직관적으로 보자면, 어떤 상수 c를 더한다고 해도 결국 reward가 가장 큰 것을 G일 것이므로,

optimal policy는 언제나 오른쪽으로 가는 action을 취하는 policy이라는 점은 변하지 않는다.

optimal value function을 구하면,

c를 더한 V(s)를 new_V(s), 원래 V(s)를 old_V(s)라 할때,

new_V(s) = old_V(s) + c + 𝛾c + 𝛾^2c + .... 

            = old_V(s) + c/(1-𝛾)

(d) 모든 reward에 상수 c를 더하고 상수 a를 곱한다고 해보자. (new_r = a * (c + old_r))  이 때 모든 si와 G에 대한 새로운 optimal value function을 구하여라. 이것이 optimal policy에 변화를 주었는가? 답을 설명하고, 만약 '그렇다'고 답했다면 optimal policy를 바꾸는 a와 c의 예시를 드시오. [5점]

우선 위의 방식으로 optimal value function을 구하면,

new_V(s) = a * (old_V(s) + c + 𝛾c + 𝛾^2c + .... )

            = a * old_V(s) + ac/(1-𝛾)

가 된다.

이 때 a>0이라면 optimal policy는 원래와 같이 goal state G로 곧장 가는, 무조건 오른쪽으로만 가는 policy가 될 것이다.

a=0이라면, 모든 reward가 0이 되므로 모든 value function과 policy가 optimal 해 진다. (바람직하진 못하겠지만)

a<0이라면, goal state G가 가장 낮은 reward를 갖게 되므로, goal state G를 거치지 않는 모든 policy는 모두 optimal policy가 될 것이다. (즉, G를 지나는 policy는 optimal 하지 못하다.)

또한, c의 값은 어떻게 변해도 아무런 영향을 끼치지 않는다.

Assignment 1 중에서 가장 쉬운 난이도 문제였습니다.

Value function의 공식을 알고 있는지,

Optimal policy와 Optimal value function의 개념을 알고 있는지,

그리고 value function의 공식을 응용할 수 있는지에 대해 묻는 문제들이었습니다.

사실상 공식에 대입하는 문제였네요 ㅎㅎ

CS234의 Assignment1의 해석입니다.

사실 풀이까지 쓰려고 했는데, 학교에다가 노트를 두고오는 바람에... 풀이는 나중에 사진으로 대체하겠읍니다..

한번 풀어보시기 바랍니다. 재밌음 ㅎㅎ

아래 Assignment의 pdf와 코딩 문제의 파일은 CS234 assignment 페이지 (http://web.stanford.edu/class/cs234/assignment1/index.html) 에서 다운로드 받을 수 있습니다.

1. Figure 1에 있는 간단한 n-state MDP를 보자. State s1에서 시작하는 Agent는 어떤 state si에서도 오른쪽 (a0) 또는 왼쪽 (a1)으로 가는 action을 취할 수 있다. 모든 Action은 deterministic(결정론적)이고, 언제나 성공한다. (가령 s2에서 왼쪽으로 가면 s1으로 가고, s1에서 왼쪽으로 또 가면 s1 자신으로 돌아온다.) State에서 Action을 취함으로써 Reward를 취할 수 있다.  goal state G에서 취한 모든 Action은 r(reward) += 1 을 얻고, G에 머무른다. 그 외의 나머지 행위는 reward 0을 얻는다. discount factor ᵞ < 1 이라고 가정한다.

(a) optimal action은 (최적의 action은) 어떤 state si에서든 G에 도달할 때 까지 오른쪽으로 가는 것이다 (action a0을 취하는 것이다). 이 때, 모든 state si와 goal state G에서의 optimal value function을 구하여라. [5점]

(b) optimal policy가 discount factor ᵞ의 영향을 받는지에 대해 서술하시오. [5점]

(c) 모든 reward 에 상수 c를 더한다고 생각해보자. (즉, G에서는 reward 1+c를, 나머지 state에서는 reward c를 받는다.)

이 때, 모든 si와 G에 대한 새로운 optimal value function을 구하시오. 상수 c를 더한 것이 optimal policy를 바꾸는가? 답을 설명하시오. [5점]

(d) 모든 reward에 상수 c를 더하고 상수 a를 곱한다고 해보자. (new_r = a * (c + old_r))  이 때 모든 si와 G에 대한 새로운 optimal value function을 구하여라. 이것이 optimal policy에 변화를 주었는가? 답을 설명하고, 만약 '그렇다'고 답했다면 optimal policy를 바꾸는 a와 c의 예시를 드시오. [5점]

이번 문제에서는 value iteration을 사용하여 optimal policy를 찾을 때 사용할 steps의 갯수를 제한하는 예시를 들 것이다. Figure 2에 나오는 discount factor ᵞ < 1 인 infinite MDP를 보자. 이 MDP는 state 3개로 구성되어 있고, state에서 action을 취할 때 reward를 얻는다. state s0에서 a1의 Action을 취하면 0의 reward를 얻은 뒤 s1으로 이동하고, 그 이후의 모든 action에 대해 r = +1을 얻는다. state s0에서 a2의 Action을 취하면 s2로 이동하고 즉시 ᵞ^2 / (1-ᵞ) 의 reward를 얻지만, s2는 그 이후의 모든 action에 대해 r = +0을 얻는다.

(a) time step t=0인 state s0에서 action a1을 취할 때, 최종 discounted return (위 수식 참고)은 무엇인가? [5점]

(b) time step t=0인 state s0에서 action a2를 취할 때, 최종 discounted return (위 수식 참고)은 무엇인가? optimal action은 무엇인가? [5점]

(c) 모든 state의 value를 0으로 초기화 했다고 가정하자. value iteration은 위의 수식 (n* ≥ log(1-ᵞ)/logᵞ ≥ 1/2 * log(1/1-ᵞ) * 1/(1-ᵞ)이 성립할 때 까지 sub-optimal action을 선택하는데, 이를 증명하여라.

따라서, value iteration은 1/(1-ᵞ)보다 빠르게 증가한다. (첫 번째 부등식이 옳다는 것만 보이면 된다.) [10점]

finite MDP M = <S, A, T, R, ᵞ> 가 있다고 생각해보자. (S = state space, A = action space, T = transition probability, R = reward function, ᵞ = discount factor이다.)

Q* 을 optimal state-action function인 Q*(s, a) = Qπ*(s, a) (이 때, π*는 optimal policy이다.) 라고 정의하자.

또, ||x||∞ = max(|x(s, a)| 일 때 Q* 의 예측값인 Q˜을 가지고 있다고 가정하자. (이 때 Q˜는 l∞ norm ||Q˜ - Q*||∞ ≤ ε으로 제한되어 있다.)

만약 Q˜에 대한 greedy policy, π(s) = argmaxₐ∈AQ˜(s, a)를 따른다고 가정하자. 이 때, 우리는 다음을 보이고 싶다: Vπ(s) ≥ V*(s) − 2ε / (1 − γ)

(이 때 Vπ(s)는 π에 대한 greedy policy를 따르는 value function이고,  V*(s) = maxₐ∈AQ*(s, a)는 optimal value function이다.)

이것은 만약 우리가 거의 optimal한 state-action value function을 계산하여 그 대략의(approximate한) state-action value function에서 greedy policy를 뽑아낸다면, 그 policy는 실제 MDP에서도 잘 작동한다는 것을 보여준다.

(a) π*가 optimal policy이고 V*이 oprimal value function이라고 하고, 위에서 정의했듯 π(s) = argmaxₐ∈AQ˜(s, a)라고 하자. 모든 state s∈S에서 다음의 부등식, V*(s) − Q*(s, π(s)) ≤ 2ε을 만족함을 보여라. [10점]

(b) part 1의 결과를 사용하여, Vπ(s) ≥ V*(s) − 2ε/(1−γ)임을 증명하라. [10점]

이렇게, 위의 범위가 성립함을 보였다. figure 3에 나온 2-state MDP를 고려하자. 이 MDP의 state1은 두 가지 action이 가능하다. 첫 번째 action은 reward 0을 얻고 다시 자기 자신의 state s1으로 돌아로는 action이고, 두 번째 action은 reward 2ε를 얻고 state s2로 가는 action이다. state s2는 추후의 모든 time step에 대하여 reward 2ε를 얻으며 자기 자신으로만 갈 수 있다. (어떤 action을 취해도 reward 2ε를 얻고 state s2로 돌아온다.)

(c) 모든 state에 대하여, optimal value function V*(s)를 구하고, state s1와 각각의 action에 대한 optimal state-action value function Q*(s, a)를 구하여라. [5점]

(d) π(s) = argmaxₐ∈AQ˜(s, a)일 때, Vπ(s1) − V*(s1) = −2ε/(1−γ)를 만족시키는, (l∞ norm으로 측정된) ε error를 갖는 대략적의 state-action value function Q˜이 존재함을 보여라. (일관적인 tie break rule을 정의해야 할 수도 있다.) [10점]

이제 OoenAI Gym을 사용하여 Frozen Lake environment에 대한 value iteration과 policy iteration을 구현할 것이다.

starter code 에 이 environment의 custom version을 제공하였다. (최상단의 링크에서 다운로드 가능)

(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점]

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

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

이해가 잘 되지 않는 부분이 있거나, 혹시라도 제가 잘못 해석한 부분이 있다면 댓글로 시정 요청 부탁드립니다.

(풀이는 나중에 올리도록 하겠습니다!)