Loading

IIT-M RL-ASSIGNMENT-2-TAXI

Solution for submission 131662

A detailed solution for submission 131662 submitted for challenge IIT-M RL-ASSIGNMENT-2-TAXI

vamsi_krishna_valluru_cs17b045

What is the notebook about?

Problem - Taxi Environment Algorithms

This problem deals with a taxi environment and stochastic actions. The tasks you have to do are:

  • Implement Policy Iteration
  • Implement Modified Policy Iteration
  • Implement Value Iteration
  • Implement Gauss Seidel Value Iteration
  • Visualize the results
  • Explain the results

How to use this notebook? 📝

  • This is a shared template and any edits you make here will not be saved.You should make a copy in your own drive. Click the "File" menu (top-left), then "Save a Copy in Drive". You will be working in your copy however you like.

  • Update the config parameters. You can define the common variables here

Variable Description
AICROWD_DATASET_PATH Path to the file containing test data. This should be an absolute path.
AICROWD_RESULTS_DIR Path to write the output to.
AICROWD_ASSETS_DIR In case your notebook needs additional files (like model weights, etc.,), you can add them to a directory and specify the path to the directory here (please specify relative path). The contents of this directory will be sent to AIcrowd for evaluation.
AICROWD_API_KEY In order to submit your code to AIcrowd, you need to provide your account's API key. This key is available at https://www.aicrowd.com/participants/me

Setup AIcrowd Utilities 🛠

We use this to bundle the files for submission and create a submission on AIcrowd. Do not edit this block.

In [1]:
!pip install aicrowd-cli > /dev/null
ERROR: google-colab 1.0.0 has requirement requests~=2.23.0, but you'll have requests 2.25.1 which is incompatible.
ERROR: datascience 0.10.6 has requirement folium==0.2.1, but you'll have folium 0.8.3 which is incompatible.

AIcrowd Runtime Configuration 🧷

Get login API key from https://www.aicrowd.com/participants/me

In [26]:
import os

AICROWD_DATASET_PATH = os.getenv("DATASET_PATH", os.getcwd()+"/13d77bb0-b325-4e95-a03b-833eb6694acd_a2_taxi_inputs.zip")
AICROWD_RESULTS_DIR = os.getenv("OUTPUTS_DIR", "results")
In [27]:

API Key valid
Saved API Key successfully!
13d77bb0-b325-4e95-a03b-833eb6694acd_a2_taxi_inputs.zip: 100% 31.2k/31.2k [00:00<00:00, 343kB/s]
In [28]:
!unzip $AICROWD_DATASET_PATH
Archive:  /content/13d77bb0-b325-4e95-a03b-833eb6694acd_a2_taxi_inputs.zip
   creating: inputs/
  inflating: inputs/inputs_base.npy  
  inflating: inputs/inputs_1.npy     
  inflating: inputs/inputs_0.npy     
  inflating: inputs/inputs_2.npy     
   creating: targets/
  inflating: targets/targets_2.npy   
  inflating: targets/targets_0.npy   
  inflating: targets/targets_1.npy   
  inflating: targets/targets_base.npy  
In [29]:
DATASET_DIR = 'inputs/'

Taxi Environment

Read the environment to understand the functions, but do not edit anything

In [30]:
import numpy as np

class TaxiEnv_HW2:
    def __init__(self, states, actions, probabilities, rewards, initial_policy):
        self.possible_states = states
        self._possible_actions = {st: ac for st, ac in zip(states, actions)}
        self._ride_probabilities = {st: pr for st, pr in zip(states, probabilities)}
        self._ride_rewards = {st: rw for st, rw in zip(states, rewards)}
        self.initial_policy = initial_policy
        self._verify()

    def _check_state(self, state):
        assert state in self.possible_states, "State %s is not a valid state" % state

    def _verify(self):
        """ 
        Verify that data conditions are met:
        Number of actions matches shape of next state and actions
        Every probability distribution adds up to 1 
        """
        ns = len(self.possible_states)
        for state in self.possible_states:
            ac = self._possible_actions[state]
            na = len(ac)

            rp = self._ride_probabilities[state]
            assert np.all(rp.shape == (na, ns)), "Probabilities shape mismatch"
        
            rr = self._ride_rewards[state]
            assert np.all(rr.shape == (na, ns)), "Rewards shape mismatch"

            assert np.allclose(rp.sum(axis=1), 1), "Probabilities don't add up to 1"

    def possible_actions(self, state):
        """ Return all possible actions from a given state """
        self._check_state(state)
        return self._possible_actions[state]

    def ride_probabilities(self, state, action):
        """ 
        Returns all possible ride probabilities from a state for a given action
        For every action a list with the returned with values in the same order as self.possible_states
        """
        actions = self.possible_actions(state)
        ac_idx = actions.index(action)
        return self._ride_probabilities[state][ac_idx]

    def ride_rewards(self, state, action):
        actions = self.possible_actions(state)
        ac_idx = actions.index(action)
        return self._ride_rewards[state][ac_idx]

Example of Environment usage

In [31]:
def check_taxienv():
    # These are the values as used in the pdf, but they may be changed during submission, so do not hardcode anything

    states = ['A', 'B', 'C']

    actions = [['1','2','3'], ['1','2'], ['1','2','3']]

    probs = [np.array([[1/2,  1/4,  1/4],
                    [1/16, 3/4,  3/16],
                    [1/4,  1/8,  5/8]]),

            np.array([[1/2,   0,     1/2],
                    [1/16,  7/8,  1/16]]),

            np.array([[1/4,  1/4,  1/2],
                    [1/8,  3/4,  1/8],
                    [3/4,  1/16, 3/16]]),]

    rewards = [np.array([[10,  4,  8],
                        [ 8,  2,  4],
                        [ 4,  6,  4]]),

            np.array([[14,  0, 18],
                        [ 8, 16,  8]]),

            np.array([[10,  2,  8],
                        [6,   4,  2],
                        [4,   0,  8]]),]
    initial_policy = {'A': '1', 'B': '1', 'C': '1'}

    env = TaxiEnv_HW2(states, actions, probs, rewards, initial_policy)
    print("All possible states", env.possible_states)
    print("All possible actions from state B", env.possible_actions('B'))
    print("Ride probabilities from state A with action 2", env.ride_probabilities('A', '2'))
    print("Ride rewards from state C with action 3", env.ride_rewards('C', '3'))

    base_kwargs = {"states": states, "actions": actions, 
                "probabilities": probs, "rewards": rewards,
                "initial_policy": initial_policy}
    return base_kwargs

base_kwargs = check_taxienv()
env = TaxiEnv_HW2(**base_kwargs)
All possible states ['A', 'B', 'C']
All possible actions from state B ['1', '2']
Ride probabilities from state A with action 2 [0.0625 0.75   0.1875]
Ride rewards from state C with action 3 [4 0 8]

Task 1 - Policy Iteration

Run policy iteration on the environment and generate the policy and expected reward

In [32]:
# 1.1 Policy Iteration
def policy_iteration(taxienv, gamma):
    # A list of all the states
    states = taxienv.possible_states
    # Initial values
    values = {s: 0 for s in states}

    # This is a dictionary of states to policies -> e.g {'A': '1', 'B': '2', 'C': '1'}
    policy = taxienv.initial_policy.copy()

    ## Begin code here

    # Hints - 
    # Do not hardcode anything
    # Only the final result is required for the results
    # Put any extra data in "extra_info" dictonary for any plots etc
    # Use the helper functions taxienv.ride_rewards, taxienv.ride_probabilities,  taxienv.possible_actions
    # For terminating condition use the condition exactly mentioned in the pdf

    
    done = False
    while not done:
        # Policy Evaluation:
        delta = 1e200
        while delta >= 1e-8:
            delta = 0
            for state in states:
                action = policy[state]
                old_J = values[state]
                prob = taxienv.ride_probabilities(state, action)
                rew = taxienv.ride_rewards(state, action)
                J = np.array([values[s] for s in states])
                values[state] = np.sum(prob*(rew+gamma*J))
                delta = max(delta, abs(old_J-values[state]))

        # Policy Improvement:
        done = True
        for state in states:
            max_val = -1e200
            arg_max_action = None
            for action in taxienv.possible_actions(state):
                prob = taxienv.ride_probabilities(state, action)
                rew = taxienv.ride_rewards(state, action)
                J = np.array([values[s] for s in states])
                if np.sum(prob*(rew+gamma*J)) > max_val:
                    max_val = np.sum(prob*(rew+gamma*J))
                    arg_max_action = action
            if policy[state] != arg_max_action:
                done = False
            policy[state] = arg_max_action
    
    
    # Put your extra information needed for plots etc in this dictionary
    extra_info = {}

    ## Do not edit below this line

    # Final results
    return {"Expected Reward": values, "Policy": policy}, extra_info

Task 2 - Policy Iteration for multiple values of gamma

Ideally this code should run as is

In [33]:
# 1.2 Policy Iteration with different values of gamma
def run_policy_iteration(env):
    gamma_values = np.arange(5, 100, 5)/100
    results, extra_info = {}, {}
    for gamma in gamma_values:
        results[gamma], extra_info[gamma] = policy_iteration(env, gamma)
    return results, extra_info

results, extra_info = run_policy_iteration(env)
In [34]:
PI_res = results.copy()
print(results)
{0.05: {'Expected Reward': {'A': 8.511527294546923, 'B': 16.400259909029575, 'C': 7.4988690667106095}, 'Policy': {'A': '1', 'B': '1', 'C': '1'}}, 0.1: {'Expected Reward': {'A': 9.076506149392834, 'B': 16.85636856362452, 'C': 8.050865123980312}, 'Policy': {'A': '1', 'B': '1', 'C': '1'}}, 0.15: {'Expected Reward': {'A': 9.708121492285777, 'B': 17.464503041460713, 'C': 8.669160453984542}, 'Policy': {'A': '1', 'B': '2', 'C': '1'}}, 0.2: {'Expected Reward': {'A': 10.437030074788021, 'B': 18.482142856612846, 'C': 9.384398496135692}, 'Policy': {'A': '1', 'B': '2', 'C': '1'}}, 0.25: {'Expected Reward': {'A': 11.274074073456447, 'B': 19.629629628834554, 'C': 10.207407407209406}, 'Policy': {'A': '1', 'B': '2', 'C': '1'}}, 0.3: {'Expected Reward': {'A': 12.243837242843748, 'B': 20.934065932820292, 'C': 11.162756162382273}, 'Policy': {'A': '1', 'B': '2', 'C': '1'}}, 0.35: {'Expected Reward': {'A': 13.378714434389575, 'B': 22.43076922849439, 'C': 12.282824024490601}, 'Policy': {'A': '1', 'B': '2', 'C': '1'}}, 0.4: {'Expected Reward': {'A': 14.722222218062745, 'B': 24.16666666169111, 'C': 13.611111109108625}, 'Policy': {'A': '1', 'B': '2', 'C': '1'}}, 0.45: {'Expected Reward': {'A': 16.334131265172196, 'B': 26.205533591380167, 'C': 15.20737070397659}, 'Policy': {'A': '1', 'B': '2', 'C': '1'}}, 0.5: {'Expected Reward': {'A': 18.29870129504681, 'B': 28.636363632167495, 'C': 17.155844153726775}, 'Policy': {'A': '1', 'B': '2', 'C': '1'}}, 0.55: {'Expected Reward': {'A': 20.789988634661945, 'B': 31.607396695666196, 'C': 19.830725213847188}, 'Policy': {'A': '1', 'B': '2', 'C': '2'}}, 0.6: {'Expected Reward': {'A': 24.025686438308284, 'B': 35.32772363825764, 'C': 23.458813102392277}, 'Policy': {'A': '1', 'B': '2', 'C': '2'}}, 0.65: {'Expected Reward': {'A': 28.276692060109887, 'B': 40.096280573890574, 'C': 28.129978785480258}, 'Policy': {'A': '1', 'B': '2', 'C': '2'}}, 0.7: {'Expected Reward': {'A': 34.06193076627213, 'B': 46.43541615340033, 'C': 34.36604101044906}, 'Policy': {'A': '1', 'B': '2', 'C': '2'}}, 0.75: {'Expected Reward': {'A': 42.31741138120016, 'B': 55.28505390685269, 'C': 43.10631739475281}, 'Policy': {'A': '1', 'B': '2', 'C': '2'}}, 0.8: {'Expected Reward': {'A': 55.079365046134924, 'B': 68.55820102458796, 'C': 56.26984124288862}, 'Policy': {'A': '2', 'B': '2', 'C': '2'}}, 0.85: {'Expected Reward': {'A': 77.24651210119615, 'B': 90.81170062152418, 'C': 78.43345572723322}, 'Policy': {'A': '2', 'B': '2', 'C': '2'}}, 0.9: {'Expected Reward': {'A': 121.65347105207364, 'B': 135.30627545205246, 'C': 122.83690301136426}, 'Policy': {'A': '2', 'B': '2', 'C': '2'}}, 0.95: {'Expected Reward': {'A': 255.02290826558783, 'B': 268.7646183427653, 'C': 256.2028492762011}, 'Policy': {'A': '2', 'B': '2', 'C': '2'}}}

Task 3 - Modifed Policy Iteration

Implement modified policy iteration (where Value iteration is done for fixed m number of steps)

In [35]:
# 1.3 Modified Policy Iteration
def modified_policy_iteration(taxienv, gamma, m):
    # A list of all the states
    states = taxienv.possible_states
    # Initial values
    values = {s: 0 for s in states}

    # This is a dictionary of states to policies -> e.g {'A': '1', 'B': '2', 'C': '1'}
    policy = taxienv.initial_policy.copy()

    ## Begin code here

    # Hints - 
    # Do not hardcode anything
    # Only the final result is required for the results
    # Put any extra data in "extra_info" dictonary for any plots etc
    # Use the helper functions taxienv.ride_rewards, taxienv.ride_probabilities,  taxienv.possible_actions
    # For terminating condition use the condition exactly mentioned in the pdf
    
    
    done = False
    while not done:
        # Policy Evaluation:
        for _ in range(m):
            new_values = {s: 0 for s in states}
            for state in states:
                action = policy[state]
                prob = taxienv.ride_probabilities(state, action)
                rew = taxienv.ride_rewards(state, action)
                J = np.array([values[s] for s in states])
                new_values[state] = np.sum(prob*(rew+gamma*J))
            values = new_values.copy()

        # Policy Improvement:
        done = True
        for state in states:
            max_val = -1e200
            arg_max_action = None
            for action in taxienv.possible_actions(state):
                prob = taxienv.ride_probabilities(state, action)
                rew = taxienv.ride_rewards(state, action)
                J = np.array([values[s] for s in states])
                if np.sum(prob*(rew+gamma*J)) > max_val:
                    max_val = np.sum(prob*(rew+gamma*J))
                    arg_max_action = action
            if policy[state] != arg_max_action:
                done = False
            policy[state] = arg_max_action
    

    
    # Put your extra information needed for plots etc in this dictionary
    extra_info = {}

    ## Do not edit below this line


    # Final results
    return {"Expected Reward": values, "Policy": policy}, extra_info

Task 4 Modified policy iteration for multiple values of m

Ideally this code should run as is

In [36]:
def run_modified_policy_iteration(env):
    m_values = np.arange(1, 15)
    gamma = 0.9
    results, extra_info = {}, {}
    for m in m_values:
        results[m], extra_info[m] = modified_policy_iteration(env, gamma, m)
    return results, extra_info

results, extra_info = run_modified_policy_iteration(env)
In [37]:
print(results)
{1: {'Expected Reward': {'A': 25.675390625, 'B': 39.27046874999999, 'C': 26.9415625}, 'Policy': {'A': '2', 'B': '2', 'C': '2'}}, 2: {'Expected Reward': {'A': 48.55490468521119, 'B': 62.203121287078865, 'C': 49.737400154724135}, 'Policy': {'A': '2', 'B': '2', 'C': '2'}}, 3: {'Expected Reward': {'A': 66.5070336319201, 'B': 80.16002669080505, 'C': 67.69034691854696}, 'Policy': {'A': '2', 'B': '2', 'C': '2'}}, 4: {'Expected Reward': {'A': 79.80001035898594, 'B': 93.45288211402925, 'C': 80.98345265619488}, 'Policy': {'A': '2', 'B': '2', 'C': '2'}}, 5: {'Expected Reward': {'A': 89.81178760453517, 'B': 103.46459982778873, 'C': 90.99521888644551}, 'Policy': {'A': '2', 'B': '2', 'C': '2'}}, 6: {'Expected Reward': {'A': 97.34789594613352, 'B': 111.0007013724186, 'C': 98.5313279386138}, 'Policy': {'A': '2', 'B': '2', 'C': '2'}}, 7: {'Expected Reward': {'A': 103.04102709136063, 'B': 116.69383160589359, 'C': 104.22445904173425}, 'Policy': {'A': '2', 'B': '2', 'C': '2'}}, 8: {'Expected Reward': {'A': 107.35314857748017, 'B': 121.00595299110296, 'C': 108.53658053027281}, 'Policy': {'A': '2', 'B': '2', 'C': '2'}}, 9: {'Expected Reward': {'A': 110.62884446690502, 'B': 124.28164886875567, 'C': 111.81227641956042}, 'Policy': {'A': '2', 'B': '2', 'C': '2'}}, 10: {'Expected Reward': {'A': 113.12458909097927, 'B': 126.77739349151406, 'C': 114.3080210436424}, 'Policy': {'A': '2', 'B': '2', 'C': '2'}}, 11: {'Expected Reward': {'A': 115.03191631274339, 'B': 128.68472071312897, 'C': 116.2153482654061}, 'Policy': {'A': '2', 'B': '2', 'C': '2'}}, 12: {'Expected Reward': {'A': 116.49414072619648, 'B': 130.1469451265653, 'C': 117.6775726788592}, 'Policy': {'A': '2', 'B': '2', 'C': '2'}}, 13: {'Expected Reward': {'A': 117.61874705064764, 'B': 131.27155145101457, 'C': 118.80217900331036}, 'Policy': {'A': '2', 'B': '2', 'C': '2'}}, 14: {'Expected Reward': {'A': 118.48653594228573, 'B': 132.13934034265242, 'C': 119.66996789494846}, 'Policy': {'A': '2', 'B': '2', 'C': '2'}}}
In [38]:
print(results[5])
print(results[10])
{'Expected Reward': {'A': 89.81178760453517, 'B': 103.46459982778873, 'C': 90.99521888644551}, 'Policy': {'A': '2', 'B': '2', 'C': '2'}}
{'Expected Reward': {'A': 113.12458909097927, 'B': 126.77739349151406, 'C': 114.3080210436424}, 'Policy': {'A': '2', 'B': '2', 'C': '2'}}

Task 5 Value Iteration

Implement value iteration and find the policy and expected rewards

In [39]:
# 1.4 Value Iteration
def value_iteration(taxienv, gamma):
    # A list of all the states
    states = taxienv.possible_states
    # Initial values
    values = {s: 0 for s in states}

    # This is a dictionary of states to policies -> e.g {'A': '1', 'B': '2', 'C': '1'}
    policy = taxienv.initial_policy.copy()

    ## Begin code here

    # Hints - 
    # Do not hardcode anything
    # Only the final result is required for the results
    # Put any extra data in "extra_info" dictonary for any plots etc
    # Use the helper functions taxienv.ride_rewards, taxienv.ride_probabilities,  taxienv.possible_actions
    # For terminating condition use the condition exactly mentioned in the pdf

    epochs = 0
    
    delta = 1e200
    while delta >= 1e-8:
        epochs += 1
        delta = 0
        new_values = {s: 0 for s in states}
        for state in states:
            max_val = -1e200
            arg_max_action = None
            for action in taxienv.possible_actions(state):
                prob = taxienv.ride_probabilities(state, action)
                rew = taxienv.ride_rewards(state, action)
                J = np.array([values[s] for s in states])
                if np.sum(prob*(rew+gamma*J)) > max_val:
                    max_val = np.sum(prob*(rew+gamma*J))
                    arg_max_action = action
            new_values[state] = max_val
            policy[state] = arg_max_action
            delta = max(delta, abs(new_values[state]-values[state]))
        values = new_values.copy()
    

    # Put your extra information needed for plots etc in this dictionary
    extra_info = {'Epochs VI': epochs}

    ## Do not edit below this line

    # Final results
    return {"Expected Reward": values, "Policy": policy}, extra_info

Task 6 Value Iteration with multiple values of gamma

Ideally this code should run as is

In [40]:
def run_value_iteration(env):
    gamma_values = np.arange(5, 100, 5)/100
    results = {}
    results, extra_info = {}, {}
    for gamma in gamma_values:
        results[gamma], extra_info[gamma] = value_iteration(env, gamma)
    return results, extra_info
  
results, extra_info = run_value_iteration(env)
In [41]:
vi_extra_info = extra_info
print(results)
{0.05: {'Expected Reward': {'A': 8.511527294182539, 'B': 16.400259908653545, 'C': 7.498869066334438}, 'Policy': {'A': '1', 'B': '1', 'C': '1'}}, 0.1: {'Expected Reward': {'A': 9.076506148654659, 'B': 16.856368562663413, 'C': 8.050865123013633}, 'Policy': {'A': '1', 'B': '1', 'C': '1'}}, 0.15: {'Expected Reward': {'A': 9.708121491779233, 'B': 17.46450304126533, 'C': 8.669160452818193}, 'Policy': {'A': '1', 'B': '2', 'C': '1'}}, 0.2: {'Expected Reward': {'A': 10.43703007317419, 'B': 18.482142855128945, 'C': 9.384398494226822}, 'Policy': {'A': '1', 'B': '2', 'C': '1'}}, 0.25: {'Expected Reward': {'A': 11.274074070814656, 'B': 19.629629626369894, 'C': 10.207407404147988}, 'Policy': {'A': '1', 'B': '2', 'C': '1'}}, 0.3: {'Expected Reward': {'A': 12.243837242020097, 'B': 20.934065932248725, 'C': 11.162756160939015}, 'Policy': {'A': '1', 'B': '2', 'C': '1'}}, 0.35: {'Expected Reward': {'A': 13.378714431634197, 'B': 22.43076922615468, 'C': 12.282824020675294}, 'Policy': {'A': '1', 'B': '2', 'C': '1'}}, 0.4: {'Expected Reward': {'A': 14.722222216827301, 'B': 24.16666666127172, 'C': 13.611111105716189}, 'Policy': {'A': '1', 'B': '2', 'C': '1'}}, 0.45: {'Expected Reward': {'A': 16.33413126569031, 'B': 26.20553359269582, 'C': 15.207370702310026}, 'Policy': {'A': '1', 'B': '2', 'C': '1'}}, 0.5: {'Expected Reward': {'A': 18.298701293190973, 'B': 28.636363630853307, 'C': 17.15584415033383}, 'Policy': {'A': '1', 'B': '2', 'C': '1'}}, 0.55: {'Expected Reward': {'A': 20.789988627490125, 'B': 31.607396689157056, 'C': 19.830725204761144}, 'Policy': {'A': '1', 'B': '2', 'C': '2'}}, 0.6: {'Expected Reward': {'A': 24.02568643325821, 'B': 35.327723634321096, 'C': 23.45881309401995}, 'Policy': {'A': '1', 'B': '2', 'C': '2'}}, 0.65: {'Expected Reward': {'A': 28.276692058162972, 'B': 40.09628057326413, 'C': 28.12997877946505}, 'Policy': {'A': '1', 'B': '2', 'C': '2'}}, 0.7: {'Expected Reward': {'A': 34.06193076174113, 'B': 46.43541615019445, 'C': 34.36604100170312}, 'Policy': {'A': '1', 'B': '2', 'C': '2'}}, 0.75: {'Expected Reward': {'A': 42.317411373067756, 'B': 55.28505390003232, 'C': 43.106317382312746}, 'Policy': {'A': '1', 'B': '2', 'C': '2'}}, 0.8: {'Expected Reward': {'A': 55.07936504724612, 'B': 68.55820102608209, 'C': 56.26984123772232}, 'Policy': {'A': '2', 'B': '2', 'C': '2'}}, 0.85: {'Expected Reward': {'A': 77.24651209325512, 'B': 90.81170061393325, 'C': 78.43345571343316}, 'Policy': {'A': '2', 'B': '2', 'C': '2'}}, 0.9: {'Expected Reward': {'A': 121.65347103895924, 'B': 135.30627543932593, 'C': 122.83690299162194}, 'Policy': {'A': '2', 'B': '2', 'C': '2'}}, 0.95: {'Expected Reward': {'A': 255.02290824365164, 'B': 268.76461832126836, 'C': 256.2028492466015}, 'Policy': {'A': '2', 'B': '2', 'C': '2'}}}

Task 7 Gauss Seidel Value Iteration

Implement Gauss Seidel Value Iteration

In [42]:
# 1.4 Gauss Seidel Value Iteration
def gauss_seidel_value_iteration(taxienv, gamma):
    # A list of all the states
    # For Gauss Seidel Value Iteration - iterate through the values in the same order
    states = taxienv.possible_states

    # Initial values
    values = {s: 0 for s in states}

    # This is a dictionary of states to policies -> e.g {'A': '1', 'B': '2', 'C': '1'}
    policy = taxienv.initial_policy.copy()

    # Hints - 
    # Do not hardcode anything
    # For Gauss Seidel Value Iteration - iterate through the values in the same order as taxienv.possible_states
    # Only the final result is required for the results
    # Put any extra data in "extra_info" dictonary for any plots etc
    # Use the helper functions taxienv.ride_rewards, taxienv.ride_probabilities,  taxienv.possible_actions
    # For terminating condition use the condition exactly mentioned in the pdf

    ## Begin code here
    
    epochs = 0
    
    delta = 1e200
    while delta >= 1e-8:
        epochs += 1
        delta = 0
        for state in states:
            old_val = values[state]
            max_val = -1e200
            arg_max_action = None
            for action in taxienv.possible_actions(state):
                prob = taxienv.ride_probabilities(state, action)
                rew = taxienv.ride_rewards(state, action)
                J = np.array([values[s] for s in states])
                if np.sum(prob*(rew+gamma*J)) > max_val:
                    max_val = np.sum(prob*(rew+gamma*J))
                    arg_max_action = action
            values[state] = max_val
            policy[state] = arg_max_action
            delta = max(delta, abs(old_val-values[state]))
    

    # Put your extra information needed for plots etc in this dictionary
    extra_info = {'Epochs GSVI': epochs}

    ## Do not edit below this line

    # Final results
    return {"Expected Reward": values, "Policy": policy}, extra_info

Task 8 Gauss Seidel Value Iteration with multiple values of gamma

Ideally this code should run as is

In [43]:
def run_gauss_seidel_value_iteration(env):
    gamma_values = np.arange(5, 100, 5)/100
    results = {}
    results, extra_info = {}, {}
    for gamma in gamma_values:
        results[gamma], extra_info[gamma] = gauss_seidel_value_iteration(env, gamma)
    return results, extra_info

results, extra_info = run_gauss_seidel_value_iteration(env)
In [44]:
gsvi_extra_info = extra_info
print(results)
{0.05: {'Expected Reward': {'A': 8.511527294546923, 'B': 16.400259909029575, 'C': 7.4988690667106095}, 'Policy': {'A': '1', 'B': '1', 'C': '1'}}, 0.1: {'Expected Reward': {'A': 9.076506149392834, 'B': 16.85636856362452, 'C': 8.050865123980312}, 'Policy': {'A': '1', 'B': '1', 'C': '1'}}, 0.15: {'Expected Reward': {'A': 9.70812149293256, 'B': 17.464503042356245, 'C': 8.66916045411395}, 'Policy': {'A': '1', 'B': '2', 'C': '1'}}, 0.2: {'Expected Reward': {'A': 10.43703007363936, 'B': 18.48214285510763, 'C': 9.384398495833036}, 'Policy': {'A': '1', 'B': '2', 'C': '1'}}, 0.25: {'Expected Reward': {'A': 11.274074072135488, 'B': 19.62962962714145, 'C': 10.207407406785403}, 'Policy': {'A': '1', 'B': '2', 'C': '1'}}, 0.3: {'Expected Reward': {'A': 12.243837240938772, 'B': 20.934065930435885, 'C': 11.162756161665108}, 'Policy': {'A': '1', 'B': '2', 'C': '1'}}, 0.35: {'Expected Reward': {'A': 13.3787144345583, 'B': 22.43076922870161, 'C': 12.28282402456309}, 'Policy': {'A': '1', 'B': '2', 'C': '1'}}, 0.4: {'Expected Reward': {'A': 14.722222217898851, 'B': 24.166666661495807, 'C': 13.611111109029693}, 'Policy': {'A': '1', 'B': '2', 'C': '1'}}, 0.45: {'Expected Reward': {'A': 16.33413126434644, 'B': 26.20553359041331, 'C': 15.207370703537933}, 'Policy': {'A': '1', 'B': '2', 'C': '1'}}, 0.5: {'Expected Reward': {'A': 18.298701293837997, 'B': 28.63636363077955, 'C': 17.155844153026397}, 'Policy': {'A': '1', 'B': '2', 'C': '1'}}, 0.55: {'Expected Reward': {'A': 20.78998863222275, 'B': 31.60739669290458, 'C': 19.830725212339292}, 'Policy': {'A': '1', 'B': '2', 'C': '2'}}, 0.6: {'Expected Reward': {'A': 24.02568643692515, 'B': 35.32772363671855, 'C': 23.458813101474426}, 'Policy': {'A': '1', 'B': '2', 'C': '2'}}, 0.65: {'Expected Reward': {'A': 28.276692061545695, 'B': 40.09628057546244, 'C': 28.129978786496867}, 'Policy': {'A': '1', 'B': '2', 'C': '2'}}, 0.7: {'Expected Reward': {'A': 34.06193076743594, 'B': 46.43541615465501, 'C': 34.36604101132381}, 'Policy': {'A': '1', 'B': '2', 'C': '2'}}, 0.75: {'Expected Reward': {'A': 42.31741137784243, 'B': 55.28505390328474, 'C': 43.10631739208525}, 'Policy': {'A': '1', 'B': '2', 'C': '2'}}, 0.8: {'Expected Reward': {'A': 55.079365051578144, 'B': 68.5582010300939, 'C': 56.26984124730355}, 'Policy': {'A': '2', 'B': '2', 'C': '2'}}, 0.85: {'Expected Reward': {'A': 77.24651209951202, 'B': 90.81170061982581, 'C': 78.43345572578708}, 'Policy': {'A': '2', 'B': '2', 'C': '2'}}, 0.9: {'Expected Reward': {'A': 121.65347104963263, 'B': 135.30627544959796, 'C': 122.83690300915262}, 'Policy': {'A': '2', 'B': '2', 'C': '2'}}, 0.95: {'Expected Reward': {'A': 255.0229082673451, 'B': 268.7646183445272, 'C': 256.20284927787594}, 'Policy': {'A': '2', 'B': '2', 'C': '2'}}}

Generate Results ✅

In [45]:
# Do not edit this cell
def get_results(kwargs):

    taxienv = TaxiEnv_HW2(**kwargs)

    policy_iteration_results = run_policy_iteration(taxienv)[0]
    modified_policy_iteration_results = run_modified_policy_iteration(taxienv)[0]
    value_iteration_results = run_value_iteration(taxienv)[0]
    gs_vi_results = run_gauss_seidel_value_iteration(taxienv)[0]

    final_results = {}
    final_results["policy_iteration"] = policy_iteration_results
    final_results["modifed_policy_iteration"] = modified_policy_iteration_results
    final_results["value_iteration"] = value_iteration_results
    final_results["gauss_seidel_iteration"] = gs_vi_results

    return final_results
In [46]:
# Do not edit this cell, generate results with it as is
if not os.path.exists(AICROWD_RESULTS_DIR):
    os.mkdir(AICROWD_RESULTS_DIR)

for params_file in os.listdir(DATASET_DIR):
  kwargs = np.load(os.path.join(DATASET_DIR, params_file), allow_pickle=True).item()
  results = get_results(kwargs)
  idx = params_file.split('_')[-1][:-4]
  np.save(os.path.join(AICROWD_RESULTS_DIR, 'results_' + idx), results)

Check your local score

This score is not your final score, and it doesn't use the marks weightages. This is only for your reference of how arrays are matched and with what tolerance.

In [47]:
# Check your score on the given test cases (There are more private test cases not provided)
target_folder = 'targets'
result_folder = AICROWD_RESULTS_DIR

def check_algo_match(results, targets):
    param_matches = []
    for k in results:
        param_results = results[k]
        param_targets = targets[k]
        policy_match = param_results['Policy'] == param_targets['Policy']
        rv = [v for k, v in param_results['Expected Reward'].items()]
        tv = [v for k, v in param_targets['Expected Reward'].items()]
        rewards_match = np.allclose(rv, tv, rtol=3)
        equal = rewards_match and policy_match
        param_matches.append(equal)
    return np.mean(param_matches)

def check_score(target_folder, result_folder):
    match = []
    for out_file in os.listdir(result_folder):
        res_file = os.path.join(result_folder, out_file)
        results = np.load(res_file, allow_pickle=True).item()
        idx = out_file.split('_')[-1][:-4]  # Extract the file number
        target_file = os.path.join(target_folder, f"targets_{idx}.npy")
        targets = np.load(target_file, allow_pickle=True).item()
        algo_match = []
        for k in targets:
            algo_results = results[k]
            algo_targets = targets[k]
            algo_match.append(check_algo_match(algo_results, algo_targets))
        match.append(np.mean(algo_match))
    return np.mean(match)

if os.path.exists(target_folder):
    print("Shared data Score (normalized to 1):", check_score(target_folder, result_folder))
Shared data Score (normalized to 1): 1.0

Visualize results of Policy Iteration with multiple values of gamma

Add code to visualize the results

In [48]:
## Visualize policy iteration with multiple values of gamma

'''
Depicts the variation of values for each state wrt gamma
'''

import seaborn as sns;
sns.set_theme()
lis = []
for key in PI_res.keys():
    lis.append([PI_res[key]['Expected Reward']['A'], PI_res[key]['Expected Reward']['B'], PI_res[key]['Expected Reward']['C']])
lis = np.log(np.array(lis))
ax = sns.heatmap(lis, linewidths=0.2, cmap="YlGnBu")
ax.set_xlabel('State')
ax.set_ylabel('Gamma')
ax.set_xticklabels(['A', 'B', 'C'])
Out[48]:
[Text(0.5, 0, 'A'), Text(1.5, 0, 'B'), Text(2.5, 0, 'C')]

Subjective questions

1.a How are values of $\gamma$ affecting results of policy iteration

As $\gamma$ increases, the total expected reward for the taxi driver also increases. Also when there is a smaller $\gamma$, there is more incentive to take action that give high reward early, but not the action that gives the highest average reward in the long run - this is because there is a high probability that the car breaks down at an early time step.

1.b For modified policy itetaration, do you find any improvement if you choose m=10.

The output when m = 5:

{'Expected Reward': {'A': 89.81178760453517, 'B': 103.46459982778873, 'C': 90.99521888644551}, 'Policy': {'A': '2', 'B': '2', 'C': '2'}}

The output when m = 10

{'Expected Reward': {'A': 113.12458909097927, 'B': 126.77739349151406, 'C': 114.3080210436424}, 'Policy': {'A': '2', 'B': '2', 'C': '2'}}

Notice that when we increase m from 5 to 10, the policy remains the same, but the Expected Reward becomes closer to the converged value for $\gamma$ = 0.9. This means that we are arriving at the policy quickly enough using this approximated policy iteration algorithm, but the more the value of m is, the closer the Expected reward is to the actual value. Notice that as $m \rightarrow \infty$, this modified policy iteration becomes the same as the normal policy iteration.

1.c Compare and contrast the behavior of Value Iteration and Gauss Seidel Value Iteraton

The difference between Value Iteration and Gauss Seidel Value Iteration is that in Value Iteration we store a copy of the old $J$ in $H$ and use $H(s')$ to calculate $J(s)$ whereas in Gauss Seidel Value Iteration, we use the $J(s')$ as it is to calculate the new $J(s)$. This means we are using the $J$ matrix that is partially updated directly in Gauss Seidel. It turns out that theoretically we can show the number of iterations/epochs it takes for convergence in Value Iteration is more than that of Gauss Seidel. We can verify this claim in the graph generated below showing how for different $\gamma$, the Value Iteration epochs are consistently lower than that of Gauss Seidel epochs.

In [49]:
vi_epoch = []
for gamma in vi_extra_info.keys():
    vi_epoch.append(vi_extra_info[gamma]['Epochs VI'])
gsvi_epoch = []
for gamma in gsvi_extra_info.keys():
    gsvi_epoch.append(gsvi_extra_info[gamma]['Epochs GSVI'])
x = list(vi_extra_info.keys())

import matplotlib.pyplot as plt
plt.plot(x, vi_epoch, label = 'Epochs Value Iteration')
plt.plot(x, gsvi_epoch, label = 'Epochs Gauss Seidel')
plt.xlabel('Gamma')
plt.ylabel('Epochs')
plt.title('Comparing Iterations of VI and GSVI')
plt.legend()
plt.show()

Submit to AIcrowd 🚀

In [ ]:
!DATASET_PATH=$AICROWD_DATASET_PATH aicrowd notebook submit -c iit-m-rl-assignment-2-taxi -a assets
WARNING: No assets directory at assets... Creating one...
No jupyter lab module found. Using jupyter notebook.
Using notebook: /content/Copy%20of%20IITM_Assignment_2_Taxi_Release.ipynb for submission...
Mounting Google Drive 💾
Your Google Drive will be mounted to access the colab notebook
Go to this URL in a browser: https://accounts.google.com/o/oauth2/auth?client_id=947318989803-6bn6qk8qdgf4n4g3pfee6491hc0brc4i.apps.googleusercontent.com&redirect_uri=urn%3aietf%3awg%3aoauth%3a2.0%3aoob&scope=email%20https%3a%2f%2fwww.googleapis.com%2fauth%2fdocs.test%20https%3a%2f%2fwww.googleapis.com%2fauth%2fdrive%20https%3a%2f%2fwww.googleapis.com%2fauth%2fdrive.photos.readonly%20https%3a%2f%2fwww.googleapis.com%2fauth%2fpeopleapi.readonly%20https%3a%2f%2fwww.googleapis.com%2fauth%2fdrive.activity.readonly%20https%3a%2f%2fwww.googleapis.com%2fauth%2fexperimentsandconfigs%20https%3a%2f%2fwww.googleapis.com%2fauth%2fphotos.native&response_type=code

Enter your authorization code:
695

Comments

You must login before you can post a comment.

Execute