final-nn-sols

Q2. Deep “Blackjack” To celebrate the end of the semester, you visit Las Vegas and decide to play a good, old fashioned game of “Blackjack”! Recall that the game has states 0,1,. . . ,8, corresponding to dollar amounts, and a Done state where the game ends. The player starts with $ 2, i.e. at state 2. The player has two actions: Stop ( a = 0) and Roll ( a = 1), and is forced to take the Stop action at states 0,1,and 8. When the player takes the Stop action ( a = 0), they transition to the Done state and receive reward equal to the amount of dollars of the state they transitioned from: e.g. taking the stop action at state 3 gives the player $ 3. The game ends when the player transitions to Done . The Roll action ( a = 1) is available from states 2-7. The player rolls a biased 6-sided die. If the player Rolls from state s and the die lands on outcome o , the player transitions to state s + o − 2, as long as s + o − 2 ≤ 8 ( s is the amount of dollars of the current state, o is the amount rolled, and the negative 2 is the price to roll). If s + o − 2 > 8, the player busts, i.e. transitions to Done and does NOT receive reward. As the bias of the dice is unknown , you decided to perform some good-old fashioned reinforcement learning (RL) to solve the game. However, unlike in the midterm, you have decided to flex and solve the game using approximate Q-learning. Not only that, you decided not to design any features - the features for the Q-value at ( s, a ) will simply be the vector [ s a ], where s is the state and a is the action. (a) First, we will investigate how your choice of features impacts whether or not you can learn the optimal policy. Suppose the unique optimal policy in the MDP is the following: State 2 3 4 5 6 7 π ∗ ( s ) Roll Roll Roll Stop Stop Stop For each of the cases below, select “Possible with large neural net” if the policy can be expressed by using a large neural net to represent the Q-function using the features specified as input. (That is, the greedy policy with respect to some Q-function representable with a large neural network is the optimal policy: Q ( s, π ∗ ( s )) > Q ( s, a ) for all states s and actions a ̸ = π ∗ ( s ).) Select “Possible with weighted sum” if the policy can be expressed by using a weighted linear sum to represent the Q-function. Select “Not Possible” if expressing the policy with given features is impossible no matter the function. (i) Suppose we decide to use the state s and action a as the features for Q ( s, a ). ■ Possible with large neural network □ Possible with linear weighted sum of features *$ Not possible A sufficiently large neural network could represent the true optimal Q -function using this feature repre- sentation. The optimal Q -function satisfies the desired property (there are no ties as the optimal policy is unique). Alternatively, a sufficiently large neural network could represent a function that is 1 for the optimal action in each state, and 0 otherwise, which also suffices. No linear weighted sum of features can represent this optimal policy. To see this, let our linear weighted sum be w 0 s + w 1 a + w 3 . We need Q (4 , 1) > Q (4 , 0) and Q (5 , 0) > Q (5 , 1). Plugging in the expression for Q, the former inequality requires that w 1 > 0. The second inequality requires that w 1 < 0, a contradiction. So we cannot represent the policy with a weighted sum of features. (ii) Now suppose we decide to use s + a as the feature for Q ( s, a ). ■ Possible with large neural network □ Possible with linear weighted sum of features *$ Not possible 3

*$ None of the above. Recall from the previous question that no linear function of the features [ s a ] can represent the optimal policy. So network 1, which is linear (as it has no activation function), cannot represent the optimal policy. Network 2 cannot represent the optimal function, as it does not take as input the action. So Q ( s, 0) = Q ( s, 1) for all states s . Network 3 cannot simultaneously satisfy Q (4 , 0) < Q (4 , 1) and Q (5 , 0) > Q (5 , 1). This is because the rectified linear unit is a monotonic function: if x ≥ y , then ReLU ( x ) ≥ ReLU ( y ). Since we cannot represent the optimal policy using a linear function of s, a , we cannot represent it with a ReLU of a linear function of s, a . Network 4 is always 0, so it cannot represent the (unique) optimal policy. Network 5 can represent the optimal policy. For example, w 0 = − 4, w 1 = − 2 represents the optimal policy. (c) As with the linear approximate q-learning, you decide to minimize the squared error of the Bellman resid- ual. Let Q w ( s, a ) be the approximate Q -values of s, a . After taking action a in state s and transitioning to state s ′ with reward r , you first compute the target target = r + γ max a ′ Q w ( s ′ , a ′ ). Then your loss is: loss( w ) = 1 2 ( Q w ( s, a ) − target) 2 You then perform gradient descent to minimize this loss. Note that we will not take the gradient through the target - we treat it as a fixed value. Which of the following updates represents one step of gradient descent on the weight parameter w i with learning rate α ∈ (0 , 1) after taking action a in state s and transitioning to state s ′ with reward r ? [Hint: which of these is equivalent to the normal approximate Q-learning update when Q w , ( s, a ) = w · f ( s, a )?] *$ w i = w i + α ( Q w ( s, a ) − ( r + γ max a ′ Q w ( s ′ , a ′ ))) ∂Q w ( s,a ) ∂w i '! w i = w i − α ( Q w ( s, a ) − ( r + γ max a ′ Q w ( s ′ , a ′ ))) ∂Q w ( s,a ) ∂w i *$ w i = w i + α ( Q w ( s, a ) − ( r + γ max a ′ Q w ( s ′ , a ′ ))) s *$ w i = w i − α ( Q w ( s, a ) − ( r + γ max a ′ Q w ( s ′ , a ′ ))) s *$ None of the above. Note that the gradient of the loss with respect to the parameter, via the chain rule, is: Q w ( s, a ) − r + γ max a ′ Q w ( s ′ , a ′ ) ∂Q w ( s, a ) ∂w i The second option performs gradient descent, the first option is gradient ascent, and the other options compute the gradient incorrectly. (d) While programming the neural network, you’re getting some bizarre errors. To debug these, you decide to calculate the gradients by hand and compare them to the result of your code. Suppose your neural network is the following: That is, Q w ( s, a ) = s + a + w 1 ReLU ( w 0 + s + a ). 6