[Solved] CS234 Assignment1-Gridworld

GridworldConsider the following grid environment. Starting from any unshaded square, you can move up, down, left, or right. Actions are deterministic and always succeed (e.g. going left from state 16 goes to state 15) unless they will cause the agent to run into a wall. The thicker edges indicate walls, and attempting to move in the direction of a wall results in staying in the same square (e.g. going in any direction other than left from state 16 stays in 16). Taking any action from the green target square (no. 12) earns a reward of rg (so r(12,a) = rg a) and ends the episode . Taking any action from the red square of death (no. 5) earns a reward of rr (so r(5,a) = rr a) and ends the episode. Otherwise, from every other square, taking any action is associated with a reward rs {1,0,+1}(even if the action results in the agent staying in the same square). Assume the discount factor = 1, rg = +5, and rr = 5 unless otherwise specified.

(a) Define the value of rs that would cause the optimal policy to return the shortest path to the green target square (no. 12). Using this rs, find the optimal value for each square.(b) Lets refer to the value function derived in (a) as and the policy as g. Suppose we are now in a new gridworld where all the rewards (rs, rg, and rr) have +2 added to them. Consider still following g of the original gridworld, what will the new values be in this second gridworld?(c) Consider a general MDP with rewards, and transitions. Consider a discount factor of . For this case assume that the horizon is infinite (so there is no termination). A policy in this MDP induces a value function V (lets refer to this as ). Now suppose we have a new MDP where the only difference is that all rewards have a constant c added to them. Can you come up with an expression for the new value function induced by in this second MDP in terms of Vold , c, and ?(d) Lets go back to our gridworld from (a) with the default values for rg, rr, and with the value you specified for rs. Suppose we now derived a second gridworld by adding a constant c to all rewards (rs, rg, and rr) such that rs = +2. How does the optimal policy change (Just give a one or two sentence description)? What do the values of the unshaded squares become?(e) Now take the second gridworld from part (d) and change such that 0 < < 1. Can the optimal policy change and does it depend on your choice of gamma? (A brief description is sufficient, no formal proof or mathematical analysis required).(f) Lets go back to our gridworld from (a) with the default values for rg, rr, and with the value you specified for rs. In this gridworld, our optimal policy from any unshaded square never terminates in the red square. Now suppose rs can take on any real, non-infinite value and is not restricted to {+1,0,1} anymore. Give a value of rs such that there are unshaded squares starting from which following the optimal policy results in termination in the red square.2 Value of Different Policies [35 pts]In many situations such as healthcare or education, we cannot run any arbitrary policy and collect data from running those policies for evaluation. In these cases, we may need to take data collected from following one policy and use it to evaluate the value of a different policy. The equality proved in the following exercise can be an important tool for achieving this. The purpose of this exercise is to get familiar on how to compare the value of different policies, 1 and 2, on a fixed horizon MDP. A fixed horizon MDP is an MDP where the agents state is reset after H timesteps; H is called the horizon of the MDP. There is no discount (i.e., = 1) and policies are allowed to be non-stationary, i.e., the action identified by a policy depends on the timestep in addition to the state. Let xt denote the distribution over states at timestep t (for 1 t H) upon following policy and Vt(xt) denote the value function of policy in state xt and timestep t, and Qt (xt,a) denote the corresponding Q value associated to action a. As a clarifying example, we denote Ext1V (xt) to represent the average value of the value function V () over the states at timestep t encountered upon following policy 1. Please show the following:

Intuition: The above expression can be interpreted in the following way. For concreteness, assume that 1 is the better policy, i.e., achieving . Suppose youre following policy 2 and you are at timestep t in state xt. You have the option to follow 1 (the better policy) until the end of the episode, totalling Qt 1(xt,1(xt,t)) return from the current state-timestep; or you have the option to follow 2 for one timestep and then follow 1 instead until the end of the episode (you can follow many other policies of course). This would you give you a loss of that originates from following the worse policy 2 instead of 1in that timestep. Then the equation above means that the value difference of the two policies is the sum of all the losses induced by following the suboptimal policy for every timestep, weighted by the expected trajectory of the policy youre following.3 Fixed PointIn this exercise we will use Cauchy sequences to prove that value iteration will converge to a unique fixed point (in this case, a value function V ) regardless of the starting point. An element V is a fixed point for an operator B (in this case the Bellman operator) if performance of B on V returns V , i.e., BV = V . Recall that the Bellman backup operator B is defined as (in lecture 2):.Additionally, in lecture 2, we proved that this Bellman backup is a contraction for < 1 on the infinity norm kBV 0 BV 00k kV 0 V 00k for any two value functions V 0 and V 00, meaning if we apply it to two different value functions, the distance between value functions (in the norm) shrinks after application of the operator to each element. (a) (5pts) Prove by induction that kVn+1 Vnk nkV1 V0k (b) (10pts) Prove that for any A Cauchy sequence is a sequence whose elements become arbitrarily close to each other as the sequence progresses. Formally a sequence {an} in metric space X with distance metric d is a Cauchy sequence if given an > 0 there exists k such that if m, n > k then d(am,an) < . Real Cauchy sequences are convergent.(c) (2pts) Using this information about Cauchy sequences, argue that the sequence V0,V1, is a Cauchy sequence and is therefore convergent and must converge to some element V and this V is a fixed point(d) (8pts) Show that this fixed point is unique.4 Frozen Lake MDP [25 pts]Now you will implement value iteration and policy iteration for the Frozen Lake environment from OpenAI Gym. We have provided custom versions of this environment in the starter code.(a) (coding) (10 pts) Read through vi_and_pi.py and implement policy_evaluation, policy_improvement and policy_iteration. The stopping tolerance (defined as maxs |Vold(s) Vnew(s)|) is tol = 103 . Use = 0.9. Return the optimal value function and the optimal policy.(b) (coding) Implement value_iteration in vi_and_pi.py. The stopping tolerance is tol = 103 . Use = 0.9. Return the optimal value function and the optimal policy.(c) (written) (5 pts) Run both methods on the Deterministic-44-FrozenLake-v0 and Stochastic4x4-FrozenLake-v0 environments. In the second environment, the dynamics of the world are stochastic. How does stochasticity affect the number of iterations required, and the resulting policy?