Loading

IIT-M RL-ASSIGNMENT-2-TAXI

Solution for submission 132232

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

sundar_raman_p_ee17b069

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 [43]:
!pip install aicrowd-cli > /dev/null

AIcrowd Runtime Configuration ๐Ÿงทยถ

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

In [44]:
import os
from matplotlib import pyplot as plt
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 [45]:

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, 263kB/s]
In [46]:
!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 [47]:
DATASET_DIR = 'inputs/'

Taxi Environmentยถ

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

In [48]:
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 [49]:
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 [50]:
# 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
    actions=taxienv._possible_actions
    ride_probs=taxienv._ride_probabilities
    ride_rewds=taxienv._ride_rewards
    done,time_local,time_global,unequal_policy=0,0,0,0
    extra_info = {}
    extra_info['time_local'],extra_info['time_global'],extra_info['delta'],extra_info['unequal_policy']=[],[],[],[]
    while(done==0):
        time_global+=1
        delta=1e-8
        while(delta>=1e-8):
            time_local+=1
            delta=0
            for state in states:
                j=values[state]
                action=policy[state]
                index=actions[state].index(action)
                ride_prob=ride_probs[state][index]
                ride_rewd=ride_rewds[state][index]
                values_=np.array(list(values.values()))
                values[state]=sum(ride_prob*(ride_rewd+gamma*values_))  #sum(taxienv.ride_probabilities(state,action)*(env.ride_rewards(state,action)+gamma*np.array(list(values.values()))))
                delta=max(delta,abs(j-values[state]))
            extra_info['delta'].append(delta)
        extra_info['time_local'].append(time_local)
        time_local=0
        done=1
        for state in states:
            b=policy[state]
            t_j=[]
            for action in actions[state]:
                index=actions[state].index(action)
                ride_prob=ride_probs[state][index]
                ride_rewd=ride_rewds[state][index]
                values_=np.array(list(values.values()))
                t_j.append(sum(ride_prob*(ride_rewd+gamma*values_)))
            policy[state]=actions[state][np.argmax(np.array(t_j))]
            if b!=policy[state]:
                done=0
                if len(extra_info['unequal_policy'])<time_global:
                    extra_info['unequal_policy'].append(0)
                extra_info['unequal_policy'][time_global-1]+=1
    extra_info['time_global'].append(time_global)
    ## 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 [51]:
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)

Task 3 - Modifed Policy Iterationยถ

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

In [53]:
# 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
    actions=taxienv._possible_actions
    ride_probs=taxienv._ride_probabilities
    ride_rewds=taxienv._ride_rewards
    done,time_local,time_global,unequal_policy=0,0,0,0
    extra_info = {}
    extra_info['time_local'],extra_info['time_global'],extra_info['unequal_policy']=[],[],[]
    while(done==0):
        time_global+=1
        for z in range(m+1):
            time_local+=1
            h={}
            for state in states:
                action=policy[state]
                index=actions[state].index(action)
                ride_prob=ride_probs[state][index]
                ride_rewd=ride_rewds[state][index]
                values_=np.array(list(values.values()))
                h[state]=sum(ride_prob*(ride_rewd+gamma*values_))
            values=h.copy()
        extra_info['time_local'].append(time_local)
        time_local=0
        done=1
        for state in states:
            b=policy[state]
            t_j=[]
            for action in actions[state]:
                index=actions[state].index(action)
                ride_prob=ride_probs[state][index]
                ride_rewd=ride_rewds[state][index]
                values_=np.array(list(values.values()))
                t_j.append(sum(ride_prob*(ride_rewd+gamma*values_)))
            policy[state]=actions[state][np.argmax(np.array(t_j))]
            if b!=policy[state]:
                done=0
                if len(extra_info['unequal_policy'])<time_global:
                    extra_info['unequal_policy'].append(0)
                extra_info['unequal_policy'][time_global-1]+=1
    extra_info['time_global'].append(time_global)
    ## 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 [54]:
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)
#print('modified PI results, extra_info: ',results,extra_info)

Task 5 Value Iterationยถ

Implement value iteration and find the policy and expected rewards

In [55]:
# 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
    actions=taxienv._possible_actions
    ride_probs=taxienv._ride_probabilities
    ride_rewds=taxienv._ride_rewards  
    delta,time_global=1e-8,0
    extra_info = {}
    extra_info['time_global'],extra_info['delta']=[],[]
    while(delta>=1e-8):
        time_global+=1
        delta=0
        h={}
        for state in states:
            t_j=[]
            for action in actions[state]:
                index=actions[state].index(action)
                ride_prob=ride_probs[state][index]
                ride_rewd=ride_rewds[state][index]
                values_=np.array(list(values.values()))
                t_j.append(sum(ride_prob*(ride_rewd+gamma*values_)))
            h[state]=max(t_j)
            policy[state]=actions[state][np.argmax(np.array(t_j))]
            delta=max(delta,abs(values[state]-h[state]))
        extra_info['delta'].append(delta)
        values=h.copy()
    extra_info['time_global'].append(time_global)
    ## 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 [56]:
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)

Task 7 Gauss Seidel Value Iterationยถ

Implement Gauss Seidel Value Iteration

In [57]:
# 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

    actions=taxienv._possible_actions
    ride_probs=taxienv._ride_probabilities
    ride_rewds=taxienv._ride_rewards  
    delta,time_global=1e-8,0
    extra_info = {}
    extra_info['time_global'],extra_info['delta']=[],[]
    while(delta>=1e-8):
        time_global+=1
        delta=0
        h={}
        for state in states:
            j=values[state]
            t_j=[]
            for action in actions[state]:
                index=actions[state].index(action)
                ride_prob=ride_probs[state][index]
                ride_rewd=ride_rewds[state][index]
                values_=np.array(list(values.values()))
                t_j.append(sum(ride_prob*(ride_rewd+gamma*values_)))
            values[state]=max(t_j)
            policy[state]=actions[state][np.argmax(np.array(t_j))]
            delta=max(delta,abs(values[state]-j))
        extra_info['delta'].append(delta)
    extra_info['time_global'].append(time_global)
    ## 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 [58]:
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)
'''
###comparing and contrasting value iterations and gauss seidel value iteration###
gamma_values = np.arange(5, 100, 5)/100
for gamma in gamma_values:
    print('vi: ',results1[gamma],extra_info1[gamma])  #1 stands for VI results, extra_info
    print('gsvi: ',results2[gamma],extra_info2[gamma])  #2 stands for GSVI results, extra_info
'''
Out[58]:
"\n###comparing and contrasting value iterations and gauss seidel value iteration###\ngamma_values = np.arange(5, 100, 5)/100\nfor gamma in gamma_values:\n    print('vi: ',results1[gamma],extra_info1[gamma])  #1 stands for VI results, extra_info\n    print('gsvi: ',results2[gamma],extra_info2[gamma])  #2 stands for GSVI results, extra_info\n"

Generate Results โœ…ยถ

In [59]:
# 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 [60]:
# 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 [61]:
# 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 [63]:
## Visualize policy iteration with multiple values of gamma
#'results', 'extra_info' variables here stand for the outputs from 'policy iteraton' (1.2) and not others (as they also have same variable names)
#So, run the below commented section just after running 'policy iteration' (Task 1) for multiple values of gamma 
'''
gamma_values = np.arange(5, 100, 5)/100
local_time,global_time,delta=[],[],[]
values=[]
twos=[]
for gamma in gamma_values:
    local_time.append(extra_info[gamma]['time_local'][-1])
    global_time.append(extra_info[gamma]['time_global'][-1])
    delta.append(extra_info[gamma]['delta'][-1])
    values.append(list(results[gamma]["Expected Reward"].values()))
    twos.append(list(results[gamma]["Policy"].values()).count('2'))
plt.plot(gamma_values,local_time)
plt.xlabel('gamma values')
plt.ylabel('No. of iterations for inner (delta<1e-8) loop')
plt.title('gamma vs no. of inner loop iterations')
plt.show()

plt.plot(gamma_values,global_time)
plt.xlabel('gamma values')
plt.ylabel('No. of iterations for outer (done) loop')
plt.title('gamma vs no. of outer loop iterations')
plt.show()

for i in range(len(gamma_values)):
    plt.plot(['A','B','C'],values[i],label=gamma_values[i])
plt.xlabel('gamma values')
plt.ylabel('Cummulative values for 3 states: A, B, C')
plt.title('gamma vs expected values')
plt.legend(loc="upper right")
plt.show()


plt.plot(delta)
plt.xlabel('gamma*no. of iterations')
plt.ylabel('delta')
plt.title('delta vs multiple iterations of different gamma')
plt.show()

plt.plot(gamma_values,twos)
plt.xlabel('gamma')
plt.ylabel('no. of states (out of 3) with action 2')
plt.title('no. of states with action 2 vs gamma')
plt.show()
'''
Out[63]:
'\ngamma_values = np.arange(5, 100, 5)/100\nlocal_time,global_time,delta=[],[],[]\nvalues=[]\ntwos=[]\nfor gamma in gamma_values:\n    local_time.append(extra_info[gamma][\'time_local\'][-1])\n    global_time.append(extra_info[gamma][\'time_global\'][-1])\n    delta.append(extra_info[gamma][\'delta\'][-1])\n    values.append(list(results[gamma]["Expected Reward"].values()))\n    twos.append(list(results[gamma]["Policy"].values()).count(\'2\'))\nplt.plot(gamma_values,local_time)\nplt.xlabel(\'gamma values\')\nplt.ylabel(\'No. of iterations for inner (delta<1e-8) loop\')\nplt.title(\'gamma vs no. of inner loop iterations\')\nplt.show()\n\nplt.plot(gamma_values,global_time)\nplt.xlabel(\'gamma values\')\nplt.ylabel(\'No. of iterations for outer (done) loop\')\nplt.title(\'gamma vs no. of outer loop iterations\')\nplt.show()\n\nfor i in range(len(gamma_values)):\n    plt.plot([\'A\',\'B\',\'C\'],values[i],label=gamma_values[i])\nplt.xlabel(\'gamma values\')\nplt.ylabel(\'Cummulative values for 3 states: A, B, C\')\nplt.title(\'gamma vs expected values\')\nplt.legend(loc="upper right")\nplt.show()\n\n\nplt.plot(delta)\nplt.xlabel(\'gamma*no. of iterations\')\nplt.ylabel(\'delta\')\nplt.title(\'delta vs multiple iterations of different gamma\')\nplt.show()\n\nplt.plot(gamma_values,twos)\nplt.xlabel(\'gamma\')\nplt.ylabel(\'no. of states (out of 3) with action 2\')\nplt.title(\'no. of states with action 2 vs gamma\')\nplt.show()\n'

Subjective questionsยถ

1.a How are values of ฮณ affecting results of policy iterationยถ

values.pngtwos.pnglocal_time.pngglobal_time.pngdelta.png As can be observed from the graphs, as gamma increases, number of inner loop iterations (policy improvement step), number of outer loop iterations (policy evaluation and repeating), maximum delta values, expected values for any state ('A','B','C') increases as more and more priority is given to future-transitions/long-term consideration. Also, starting from 0 states which had action 2 as optimal action (when gamma=0) as greedily action 2 is worse as action 1 has more per-stage expected reward from any state, we finally end up with a policy that has all 3 optimal actions (ie. for all 3 states) being 2 as when analysed in long term, action 2 at any state has more probability of ending up at B, which has a good expected reward at B and very high (3/4) transition probability to B again.

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

No considerable improvement is observed if m>10 (value difference for any state is atmost 2) as can be observed from results and 'extra-info' obtained from 1.3. This might be because the policy(/value) improvement step is a contraction step and it converges quickly (which occurs for m<10) in our case!

1.c Compare and contrast the behavior of Value Iteration (VI) and Gauss Seidel Value Iteraton (GSVI)ยถ

For all gamma's, both VI and GSVI yield the exact same value and policy. This is because both use the same contraction for evaluating values (but in slightly different ways which brings in other differences as explained below).

Since we do immediate value updates in GSVI (updating J(s), as and when it's new value is evaluated) instead of bulk updates like for VI (calculating all the new values H(s) and then updating J(s)=H(s)), for higher values of gamma which takes more iterations for the contraction to converge (as we have two dominant terms, whose sum we want to converge, which are 'r' (reward) and 'J' (values) in Bellman equation), we observe lesser convergence steps for GVSI as compared to VI (almost a difference of 100 iterations for gamma=1) as infered through 'extra-info' variable.

Submit to AIcrowd ๐Ÿš€ยถ

In [64]:
!DATASET_PATH=$AICROWD_DATASET_PATH aicrowd notebook submit -c iit-m-rl-assignment-2-taxi -a assets
#!DATASET_PATH=$AICROWD_DATASET_PATH aicrowd notebook submit --no-verify -c iit-m-rl-assignment-2-taxi -a assets
No jupyter lab module found. Using jupyter notebook.
Using notebook: /content/Copy%20of%20IITM_Assignment_2_Taxi_Release.ipynb for submission...
Removing existing files from submission directory...
No jupyter lab module found. Using jupyter notebook.
Scrubbing API keys from the notebook...
Collecting notebook...
No jupyter lab module found. Using jupyter notebook.
Validating the submission...
Executing install.ipynb...
[NbConvertApp] Converting notebook /content/submission/install.ipynb to notebook
[NbConvertApp] Executing notebook with kernel: python3
[NbConvertApp] Writing 1056 bytes to /content/submission/install.nbconvert.ipynb
Executing predict.ipynb...
[NbConvertApp] Converting notebook /content/submission/predict.ipynb to notebook
[NbConvertApp] Executing notebook with kernel: python3
[NbConvertApp] ERROR | unhandled iopub msg: colab_request
[NbConvertApp] ERROR | unhandled iopub msg: colab_request
[NbConvertApp] ERROR | unhandled iopub msg: colab_request
[NbConvertApp] ERROR | unhandled iopub msg: colab_request
[NbConvertApp] ERROR | unhandled iopub msg: colab_request
[NbConvertApp] ERROR | unhandled iopub msg: colab_request
[NbConvertApp] ERROR | Error while converting '/content/submission/predict.ipynb'
Traceback (most recent call last):
  File "/usr/local/lib/python2.7/dist-packages/nbconvert/nbconvertapp.py", line 408, in export_single_notebook
    output, resources = self.exporter.from_filename(notebook_filename, resources=resources)
  File "/usr/local/lib/python2.7/dist-packages/nbconvert/exporters/exporter.py", line 179, in from_filename
    return self.from_file(f, resources=resources, **kw)
  File "/usr/local/lib/python2.7/dist-packages/nbconvert/exporters/exporter.py", line 197, in from_file
    return self.from_notebook_node(nbformat.read(file_stream, as_version=4), resources=resources, **kw)
  File "/usr/local/lib/python2.7/dist-packages/nbconvert/exporters/notebook.py", line 32, in from_notebook_node
    nb_copy, resources = super(NotebookExporter, self).from_notebook_node(nb, resources, **kw)
  File "/usr/local/lib/python2.7/dist-packages/nbconvert/exporters/exporter.py", line 139, in from_notebook_node
    nb_copy, resources = self._preprocess(nb_copy, resources)
  File "/usr/local/lib/python2.7/dist-packages/nbconvert/exporters/exporter.py", line 316, in _preprocess
    nbc, resc = preprocessor(nbc, resc)
  File "/usr/local/lib/python2.7/dist-packages/nbconvert/preprocessors/base.py", line 47, in __call__
    return self.preprocess(nb, resources)
  File "/usr/local/lib/python2.7/dist-packages/nbconvert/preprocessors/execute.py", line 381, in preprocess
    nb, resources = super(ExecutePreprocessor, self).preprocess(nb, resources)
  File "/usr/local/lib/python2.7/dist-packages/nbconvert/preprocessors/base.py", line 69, in preprocess
    nb.cells[index], resources = self.preprocess_cell(cell, resources, index)
  File "/usr/local/lib/python2.7/dist-packages/nbconvert/preprocessors/execute.py", line 424, in preprocess_cell
    raise CellExecutionError.from_cell_and_msg(cell, out)
CellExecutionError: An error occurred while executing the following cell:
------------------
## Visualize policy iteration with multiple values of gamma
#'results', 'extra_info' variables here stand for the outputs from 'policy iteraton' (1.2) and not others (as they also have same variable names)
#So, run the below commented section just after running 'policy iteration' (Task 1) for multiple values of gamma 
'''
gamma_values = np.arange(5, 100, 5)/100
local_time,global_time,delta=[],[],[]
values=[]
twos=[]
for gamma in gamma_values:
    local_time.append(extra_info[gamma]['time_local'][-1])
    global_time.append(extra_info[gamma]['time_global'][-1])
    delta.append(extra_info[gamma]['delta'][-1])
    values.append(list(results[gamma]["Expected Reward"].values()))
    twos.append(list(results[gamma]["Policy"].values()).count('2'))
plt.plot(gamma_values,local_time)
plt.xlabel('gamma values')
plt.ylabel('No. of iterations for inner (delta<1e-8) loop')
plt.title('gamma vs no. of inner loop iterations')
plt.show()

plt.plot(gamma_values,global_time)
plt.xlabel('gamma values')
plt.ylabel('No. of iterations for outer (done) loop')
plt.title('gamma vs no. of outer loop iterations')
plt.show()

for i in range(len(gamma_values)):
    plt.plot(['A','B','C'],values[i],label=gamma_values[i])
plt.xlabel('gamma values')
plt.ylabel('Cummulative values for 3 states: A, B, C')
plt.title('gamma vs expected values')
plt.legend(loc="upper right")
plt.show()


plt.plot(delta)
plt.xlabel('gamma*no. of iterations')
plt.ylabel('delta')
plt.title('delta vs multiple iterations of different gamma')
plt.show()

plt.plot(gamma_values,twos)
plt.xlabel('gamma')
plt.ylabel('no. of states (out of 3) with action 2')
plt.title('no. of states with action 2 vs gamma')
plt.show()
''
------------------

  File "<ipython-input-18-06937b380c42>", line 47
    ''
      
^
SyntaxError: EOF while scanning triple-quoted string literal

SyntaxError: EOF while scanning triple-quoted string literal (<ipython-input-18-06937b380c42>, line 47)

โ•ญโ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€ Traceback (most recent call last) โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ•ฎ
โ”‚ /usr/local/bin/aicrowd:8 in <module>                                         โ”‚
โ”‚                                                                              โ”‚
โ”‚   5 from aicrowd.cli import cli                                              โ”‚
โ”‚   6 if __name__ == '__main__':                                               โ”‚
โ”‚   7 โ”‚   sys.argv[0] = re.sub(r'(-script\.pyw|\.exe)?$', '', sys.argv[0])     โ”‚
โ”‚ โฑ 8 โ”‚   sys.exit(cli())                                                      โ”‚
โ”‚                                                                              โ”‚
โ”‚ /usr/local/lib/python3.7/dist-packages/click/core.py:829 in __call__         โ”‚
โ”‚                                                                              โ”‚
โ”‚    826 โ”‚                                                                     โ”‚
โ”‚    827 โ”‚   def __call__(self, *args, **kwargs):                              โ”‚
โ”‚    828 โ”‚   โ”‚   """Alias for :meth:`main`."""                                 โ”‚
โ”‚ โฑ  829 โ”‚   โ”‚   return self.main(*args, **kwargs)                             โ”‚
โ”‚    830                                                                       โ”‚
โ”‚    831                                                                       โ”‚
โ”‚    832 class Command(BaseCommand):                                           โ”‚
โ”‚                                                                              โ”‚
โ”‚ /usr/local/lib/python3.7/dist-packages/click/core.py:782 in main             โ”‚
โ”‚                                                                              โ”‚
โ”‚    779 โ”‚   โ”‚   try:                                                          โ”‚
โ”‚    780 โ”‚   โ”‚   โ”‚   try:                                                      โ”‚
โ”‚    781 โ”‚   โ”‚   โ”‚   โ”‚   with self.make_context(prog_name, args, **extra) as c โ”‚
โ”‚ โฑ  782 โ”‚   โ”‚   โ”‚   โ”‚   โ”‚   rv = self.invoke(ctx)                             โ”‚
โ”‚    783 โ”‚   โ”‚   โ”‚   โ”‚   โ”‚   if not standalone_mode:                           โ”‚
โ”‚    784 โ”‚   โ”‚   โ”‚   โ”‚   โ”‚   โ”‚   return rv                                     โ”‚
โ”‚    785 โ”‚   โ”‚   โ”‚   โ”‚   โ”‚   # it's not safe to `ctx.exit(rv)` here!           โ”‚
โ”‚                                                                              โ”‚
โ”‚ /usr/local/lib/python3.7/dist-packages/click/core.py:1259 in invoke          โ”‚
โ”‚                                                                              โ”‚
โ”‚   1256 โ”‚   โ”‚   โ”‚   โ”‚   Command.invoke(self, ctx)                             โ”‚
โ”‚   1257 โ”‚   โ”‚   โ”‚   โ”‚   sub_ctx = cmd.make_context(cmd_name, args, parent=ctx โ”‚
โ”‚   1258 โ”‚   โ”‚   โ”‚   โ”‚   with sub_ctx:                                         โ”‚
โ”‚ โฑ 1259 โ”‚   โ”‚   โ”‚   โ”‚   โ”‚   return _process_result(sub_ctx.command.invoke(sub โ”‚
โ”‚   1260 โ”‚   โ”‚                                                                 โ”‚
โ”‚   1261 โ”‚   โ”‚   # In chain mode we create the contexts step by step, but afte โ”‚
โ”‚   1262 โ”‚   โ”‚   # base command has been invoked.  Because at that point we do โ”‚
โ”‚                                                                              โ”‚
โ”‚ /usr/local/lib/python3.7/dist-packages/click/core.py:1259 in invoke          โ”‚
โ”‚                                                                              โ”‚
โ”‚   1256 โ”‚   โ”‚   โ”‚   โ”‚   Command.invoke(self, ctx)                             โ”‚
โ”‚   1257 โ”‚   โ”‚   โ”‚   โ”‚   sub_ctx = cmd.make_context(cmd_name, args, parent=ctx โ”‚
โ”‚   1258 โ”‚   โ”‚   โ”‚   โ”‚   with sub_ctx:                                         โ”‚
โ”‚ โฑ 1259 โ”‚   โ”‚   โ”‚   โ”‚   โ”‚   return _process_result(sub_ctx.command.invoke(sub โ”‚
โ”‚   1260 โ”‚   โ”‚                                                                 โ”‚
โ”‚   1261 โ”‚   โ”‚   # In chain mode we create the contexts step by step, but afte โ”‚
โ”‚   1262 โ”‚   โ”‚   # base command has been invoked.  Because at that point we do โ”‚
โ”‚                                                                              โ”‚
โ”‚ /usr/local/lib/python3.7/dist-packages/click/core.py:1066 in invoke          โ”‚
โ”‚                                                                              โ”‚
โ”‚   1063 โ”‚   โ”‚   """                                                           โ”‚
โ”‚   1064 โ”‚   โ”‚   _maybe_show_deprecated_notice(self)                           โ”‚
โ”‚   1065 โ”‚   โ”‚   if self.callback is not None:                                 โ”‚
โ”‚ โฑ 1066 โ”‚   โ”‚   โ”‚   return ctx.invoke(self.callback, **ctx.params)            โ”‚
โ”‚   1067                                                                       โ”‚
โ”‚   1068                                                                       โ”‚
โ”‚   1069 class MultiCommand(Command):                                          โ”‚
โ”‚                                                                              โ”‚
โ”‚ /usr/local/lib/python3.7/dist-packages/click/core.py:610 in invoke           โ”‚
โ”‚                                                                              โ”‚
โ”‚    607 โ”‚   โ”‚   args = args[2:]                                               โ”‚
โ”‚    608 โ”‚   โ”‚   with augment_usage_errors(self):                              โ”‚
โ”‚    609 โ”‚   โ”‚   โ”‚   with ctx:                                                 โ”‚
โ”‚ โฑ  610 โ”‚   โ”‚   โ”‚   โ”‚   return callback(*args, **kwargs)                      โ”‚
โ”‚    611 โ”‚                                                                     โ”‚
โ”‚    612 โ”‚   def forward(*args, **kwargs):  # noqa: B902                       โ”‚
โ”‚    613 โ”‚   โ”‚   """Similar to :meth:`invoke` but fills in default keyword     โ”‚
โ”‚                                                                              โ”‚
โ”‚ /usr/local/lib/python3.7/dist-packages/aicrowd/cmd/notebook.py:92 in         โ”‚
โ”‚ submit_subcommand                                                            โ”‚
โ”‚                                                                              โ”‚
โ”‚    89 โ”‚   โ”‚   output,                                                        โ”‚
โ”‚    90 โ”‚   โ”‚   notebook_name,                                                 โ”‚
โ”‚    91 โ”‚   โ”‚   no_verify,                                                     โ”‚
โ”‚ โฑ  92 โ”‚   โ”‚   dry_run,                                                       โ”‚
โ”‚    93 โ”‚   )                                                                  โ”‚
โ”‚                                                                              โ”‚
โ”‚ /usr/local/lib/python3.7/dist-packages/aicrowd/notebook/submit.py:88 in      โ”‚
โ”‚ create_submission                                                            โ”‚
โ”‚                                                                              โ”‚
โ”‚   85 ):                                                                      โ”‚
โ”‚   86 โ”‚   bundle_submission(assets_dir, submission_zip_path, notebook_name)   โ”‚
โ”‚   87 โ”‚   if not no_verify:                                                   โ”‚
โ”‚ โฑ 88 โ”‚   โ”‚   verify_submission()                                             โ”‚
โ”‚   89 โ”‚   if not dry_run:                                                     โ”‚
โ”‚   90 โ”‚   โ”‚   submit_to_aicrowd(                                              โ”‚
โ”‚   91 โ”‚   โ”‚   โ”‚   challenge=challenge,                                        โ”‚
โ”‚                                                                              โ”‚
โ”‚ /usr/local/lib/python3.7/dist-packages/aicrowd/notebook/submit.py:32 in      โ”‚
โ”‚ verify_submission                                                            โ”‚
โ”‚                                                                              โ”‚
โ”‚   29 โ”‚   for notebook in ["install.ipynb", "predict.ipynb"]:                 โ”‚
โ”‚   30 โ”‚   โ”‚   print(f"Executing {notebook}...")                               โ”‚
โ”‚   31 โ”‚   โ”‚   if execute_command(nbconvert_cmd.format(kernel, SUBMISSION_DIR, โ”‚
โ”‚ โฑ 32 โ”‚   โ”‚   โ”‚   raise RuntimeError(f"{notebook} failed to execute")         โ”‚
โ”‚   33                                                                         โ”‚
โ”‚   34                                                                         โ”‚
โ”‚   35 def bundle_submission(                                                  โ”‚
โ•ฐโ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ•ฏ
RuntimeError: predict.ipynb failed to execute
1682

Comments

You must login before you can post a comment.

Execute