Task 1 Frozen Lake MDP
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.
1. (coding) Read through vi_and_pi.py and implement policy_evaluation , policy_improvement and policy_iteration . The stopping tolerance (defined as ) is tol = . Use . Return the optimal value function and the optimal policy.
2. (coding) Implement value_iteration in vi_and_pi.py . The stopping tolerance is tol = . Use . Return the optimal value function and the optimal policy.
Task 2 Test Environment
It is crucial to test our code on a test environment. In this problem, you will reason about optimality in the provided test environment by hand; later, to sanity-check your code, you will verify that your implementation is able to achieve this optimality. You should be able to run your models on CPU in no more than a few minutes on the following environment:
4 states: 0, 1, 2, 3
5 actions: 0, 1, 2, 3, 4. Action goes to state , while action 4 makes the agent stay in the same state. Rewards: Going to state from states 0, 1 and 3 gives a reward , where
If we start in state 2, then the rewards defined above are multiplied by -10. See Table 1 for the full transition and reward structure.
One episode lasts 5 time steps (for a total of 5 actions) and always starts in state 0 (no rewards at the initial state).
An example of a trajectory (or episode) in the test environment is shown in Figure 1, and the trajectory can be represented in terms of as:
.
State ( ) Action ( ) Next State ( ) Reward (R)
0 0 0 0.1
01 1 -0.3
0 2 2 0.0
03 3 -0.2
0 4 0 0.1
1 0 0 0.1
11 1 -0.3
1 2 2 0.0
13 3 -0.2
14 1 -0.3
20 0 -1.0
2 1 1 3.0
2 2 2 0.0
2 3 3 2.0
2 4 2 0.0
3 0 0 0.1
31 1 -0.3
3 2 2 0.0
33 3 -0.2
33 3 -0.2
Table 1: Transition table for the Test Environment
Figure 1: Example of a trajectory in the Test Environment
1. (written) What is the maximum sum of rewards that can be achieved in a single trajectory in the test environment, assuming = 1? Show first that this value is attainable in a single trajectory, and then briefly argue why no other trajectory can achieve greater cumulative reward.
Task 3 Tabular Q-Learning
If the state and action spaces are sufficiently small, we can simply maintain a table containing the value of , an estimate of , for every pair. In this tabular setting, given an experience sample , the update rule is
where is the learning rate, the discount factor.
Exploration Strategy For exploration, we use an strategy. This means that with probability , an action is chosen uniformly at random from , and with probability , the greedy action is chosen.
1. (coding) Implement the get_action and update functions in q_table.py . Test your implementation by running python q_table.py .
Task 4 Maze Example
You will implement Sarsa and Q-learning for the Maze environment from OpenAI Gym . We have provided custom versions of this environment. In the scenario, a red rectangle (agent) are initialized at the maze made up of grids and can only observe its location. At each timestep, agent can move to one of four neighboring grids. The reward is +1 if agent is located at the yellow grid, -1 if agent reaches the black grid, otherwise 0.
1.(coding)ImplementSarsa inRL_sarsa.py.
2. (coding) Implement Q_learning in RL_q_learning.py .
