<jupyter_start><jupyter_text>P1: Solve the OpenAI Gym [Taxi V3](https://gym.openai.com/envs/Taxi-v3/) Environment---  Introduction[OpenAI Gym](https://gym.openai.com/docs/) is a framework that provides RL environments of varying complexity with the same standard API making it easy to develop and benchmark RL algorithms. The [Taxi-V3](https://gym.openai.com/envs/Taxi-v3/) environmnet present a simple, text environment where actions and state (observations) are both discrete.<jupyter_code># Imports
import gym
import pandas as pd
import numpy as np
from IPython.display import clear_output
import time<jupyter_output><empty_output><jupyter_text>The `gym.make()` API can be used to spawn any of the available environments by passing its full name.<jupyter_code>taxi = gym.make('Taxi-v3')<jupyter_output><empty_output><jupyter_text>The Taxi environment has 500 states and 6 possible actions.<jupyter_code>taxi.action_space
taxi.observation_space<jupyter_output><empty_output><jupyter_text>The task and reward structure are described in the [documentation](https://github.com/openai/gym/blob/a5a6ae6bc0a5cfc0ff1ce9be723d59593c165022/gym/envs/toy_text/taxi.pyL25)<jupyter_code>taxi.reset()
render = taxi.render()
state, reward, done, info = taxi.step(taxi.action_space.sample())
taxi.P[state]
state, reward, done, info = taxi.step(2)
state<jupyter_output><empty_output><jupyter_text>1***Describe the methods and variables in the class DiscreteEnv which is the parent class of the Taxi V3 class.*** *Attributes/Variables*: \nS: number of states \nA: number of actions \P: a directory of lists representing transitions/rewards table where keys are the states and value is a dictionry with all actions as keys and their values ares lists with action results. \isd: a list of the initial state distribution of length nS \action_space: the discrete valid actions that the agent can take. \observation_space: discrete valid structure of the observation of the enviroment. \*Methods*: \seed(): set a seed to reproduce the same results.\reset(): reset the enviroment to an initial state.\step(a): returns the current state, reward, if done and probability after taking action a.  2***Describe the methods and variables in the Taxi V3 class.*** *Attributes/Variables*:\desc: The visual structure of the enviorment map stored as a np array. \locs: the indices of the 4 destination locations. \*Methods*:\encode: return the state index given the row, col, destination index and passenger location. \decode: Return the row, col, destination index and passenger location given the state index. \render: Draw the current observation of the taxi envrionment. \  3***Describe the Taxi V3 environment, its actions, states, reward structure and the rationale behind such a reward structure.***There are 4 designated destionation + in the taxi, where the passenger can be.0. R(ed)1. G(reen)2. Y(ellow)3. B(lue)4. Taxi  The taxi can be in one of 25 positionsThe passenger can be in 5 locationsThere are 4 set locationsTherefore, 25x5x4=500 discrete states.The available actions are:move south, move north, move east, move west, pickup passenger, drop-off passenger.Reward of -1 for every step, other than correct drop-off which is +20 and illegal pickup or drop-off which is -10. This reward structure is set such that taking the shortest route while avoiding illegal actions will result in the highest return.   4*Train an algorithm to achieve a 100-episode average reward with a 5th percentile of 7.2 or higher and a 95th percentile of 8.2 or higher on the last 1000 episodes.*  5*The algorithm should be able to perform pick-ups and dropoffs with zero penalties over 1000 episodes.*  6*Document your solution including all hyper parameters and how those hyperparameters were selected.*<jupyter_code># This cell is for experimentation. Exploring ways to print 
# the render and understand enviroment.
# References used in this cell:
# IPython To clear ouptut (using so we can view renders like animations):
#   https://stackoverflow.com/questions/24816237/ipython-notebook-clear-cell-output-in-code
# OpenAI Gym to understand basics:
#   https://gym.openai.com/docs/

steps = 0
taxi.reset()
for i_episode in range(1):
  state = taxi.reset()
  for t in range(1000):
    clear_output(wait=True)
    taxi.render()
    print(state)
    print(steps)
    action = taxi.action_space.sample()
    state, reward, done, info = taxi.step(action)
    steps += 1
    if done:
        print("Episode finished after {} timesteps. Last action: {}".format(t+1, taxi.lastaction))
        break
    time.sleep(0.01)
taxi.close()
#Begin Implementation
# Create Q table
Q = pd.DataFrame.from_dict({s:{a:0 for a in range(taxi.action_space.n)} for s in range(taxi.observation_space.n)}, orient='index')
Q
## Hyperparameters were selected through trial and error
## epsilon 0.7 (no decay) with gamma 0.9 alpha 0.1 seemed to get good results in 3000 episodes
## Potentially because of buggy run ->epsilon 1.001 (0.999 decay) with gamma 0.9 alpha 0.001 did not do as well.
## epsilon 1 (decay 0.999) with gamma 0.9 and alpha 0.1 seemed to get good results but some runs reached cumulative reward of -200 
## issues with 1 epsilone (.999) decay alpah 0.01 and gamma 0.9

## Final hyperparams - using less than 10000 ep did not see convergence
n_episodes = 20000
epsilon = 0.7
min_epsilon = 0.7
epsilon_decay = 1#0.999
gamma = 0.9
alpha = 0.1

# testing with numpy to see if there is any performance gain
Q = np.zeros([taxi.observation_space.n, taxi.action_space.n])

actions = [0, 1, 2, 3, 4, 5]
#default_probs = np.asarray([epsilon/taxi.action_space.n]*taxi.action_space.n,dtype=np.float)

for i in range(n_episodes):
  render_cnt = 0
  epsilon = max(epsilon,min_epsilon)
  epsilon *= epsilon_decay
  done = False
  state_0 = taxi.reset()
  while not done:
    # Find epsilon greedy action
    action_probs = np.asarray([epsilon/taxi.action_space.n]*taxi.action_space.n,dtype=np.float)
    greedy_action_index = np.argmax(Q[state_0])
    action_probs[greedy_action_index] += 1-epsilon
    action_0 = np.random.choice(actions,p=action_probs)

    # Take action_t
    state_1, reward, done, info = taxi.step(action_0)

    # update Q
    curr_q_value = Q[state_0, action_0]
    max_a1 = np.max(Q[state_1])
    Q[state_0, action_0] = curr_q_value + alpha*(reward + (gamma * max_a1) - curr_q_value)

    # update current state
    state_0 = state_1

    if (i+1)%50 == 0:
      clear_output(wait=True)
      print(f"Episode: {i}")


Q
# Visualizing episodes like an animation

actions = ['s', 'n', 'e', 'w', 'pickup', 'drop off']
episodes = 2

for _ in range(episodes):
    state = taxi.reset()
    done = False
    ep_cumul_r = 0

    while not done:
      action = np.argmax(Q[state])
      state, reward, done, info = taxi.step(action)
      clear_output(wait=True)
      taxi.render()
      ep_cumul_r += reward

      print("Prev Action: {}, Curr state: {}, Return: {}, Penalties: {}".format(actions[action], curr_state, ep_cumul_r, penalties))
      time.sleep(0.2)
    
    print("Episode finished with total reward {}".format(ep_cumul_r))
    time.sleep(1)
# Test performance using trained Q table for 1000 episodes

actions = ['s', 'n', 'e', 'w', 'pickup', 'drop off']
total_batches = 10
batch = 100
avg_cumul_reward = [0]*total_batches
penalties = 0

for i in range(total_batches):
  for j in range(batch):
    curr_state = taxi.reset()
    done = False
    ep_cumul_r = 0
    
    while not done:
      action = np.argmax(Q[curr_state])
      curr_state, reward, done, info = taxi.step(action)
      ep_cumul_r += reward

      if reward == -10:
        penalties += 1

    avg_cumul_reward[i] += ep_cumul_r
    if (j%50 == 0):
      print("Episode finished with total reward {}".format(ep_cumul_r))

  avg_cumul_reward[i] /= batch

avg_cumul_reward.sort()
print(avg_cumul_reward)

n_95 = (95/100)*total_batches
n_5 = (5/100)*total_batches

print("95th Percentile: {}\n5th Percentile:{}"\
      .format(avg_cumul_reward[int(n_95)],avg_cumul_reward[int(n_5)] ))
print("Penalties: {}".format(penalties))<jupyter_output>[7.63, 7.63, 7.8, 7.88, 7.98, 7.99, 8.27, 8.34, 8.34, 8.44]
95th Percentile: 8.44
5th Percentile:7.63
Penalties: 0
{'fraction_non_alphanumeric': 0.10435737824972538, 'fraction_numerical': 0.03405346027096302, 'mean_word_length': 4.269453376205788, 'pattern_counts': {'":': 0, '<': 20, '<?xml version=': 0, '>': 21, 'https://': 6, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '5', 'dir': 'jupyter-structured-clean-dedup', 'id': '632926', 'license': 'MIT', 'n_tokens_mistral': 2851, 'n_tokens_neox': 2637, 'n_words': 909, 'path': 'Ali_Raza_Taxi-v3_Sol.ipynb', 'repo_name': 'alisyedraza99/OpenAI_Gym_Projects', 'size': '8193'}