import numpy as np

import random

# Define the grid world

GRID$\_$SIZE $=(4,5)$

START$\_$STATE $=(0,0)$

GOAL$\_$STATE $=(3,4)$

OBSTACLES $=[(1,1),(2,2),(1,3)]$

# Q$-$learning parameters

LEARNING$\_$RATE $=0\mathrm{.}1$

DISCOUNT$\_$FACTOR $=0\mathrm{.}9$

EPISODES $=500$

# Initialize Q$-$table

q$\_$table $=$ np$.$zeros$(($GRID$\_$SIZE$[0],$ GRID$\_$SIZE$[1],4))$ # $4$ actions: up$,$ down, left, right

# Define actions

ACTIONS $=["$UP$",$ "DOWN", "LEFT", "RIGHT"$]$

# Function to choose an action using epsilon$-$greedy strategy

def choose$\_$action$($state$,$ epsilon$)$:

if random.uniform$(0,1)<$ epsilon:

return random.choice$($range$(4))$ # choose a random action

else:

return np$.$argmax$($q$\_$table$[$state$[0],$ state$[1]])$

# Function to perform Q$-$learning

def q$\_$learning$()$:

for episode in range$($EPISODES$)$:

state $=$ START$\_$STATE

while state $!=$ GOAL$\_$STATE:

action $=$ choose$\_$action$($state$,$ epsilon$=0\mathrm{.}1)$

next$\_$state $=$ take$\_$action$($state$,$ action$)$

reward $=$ calculate$\_$reward$($next$\_$state$)$

update$\_$q$\_$table$($state$,$ action, reward, next$\_$state$)$

state $=$ next$\_$state

# Function to take an action and return the next state

def take$\_$action$($state$,$ action$)$:

if action $==0$: # UP

return $($max$(0,$ state$[0]-1),$ state$[1])$

elif action $==1$: # DOWN

return $($min$($GRID$\_$SIZE$[0]-1,$ state$[0]+1),$ state$[1])$

elif action $==2$: # LEFT

return $($state$[0],$ max$(0,$ state$[1]-1))$

elif action $==3$: # RIGHT

return $($state$[0],$ min$($GRID$\_$SIZE$[1]-1,$ state$[1]+1))$

# Function to calculate the reward for a given state

def calculate$\_$reward$($state$)$:

if state $==$ GOAL$\_$STATE:

return $1$

elif state in OBSTACLES:

return $-1$

else:

return $0$

# Function to update the Q$-$table based on the Q$-$learning update rule

def update$\_$q$\_$table$($state$,$ action, reward, next$\_$state$)$:

best$\_$future$\_$value $=$ np$.$max$($q$\_$table$[$next$\_$state$[0],$ next$\_$state$[1]])$

current$\_$value $=$ q$\_$table$[$state$[0],$ state$[1],$ action$]$

new$\_$value $=(1-$ LEARNING$\_$RATE$)*$ current$\_$value $+$ LEARNING$\_$RATE $*($reward $+$ DISCOUNT$\_$FACTOR $*$ best$\_$future$\_$value$)$

q$\_$table$[$state$[0],$ state$[1],$ action$]=$ new$\_$value

# Run Q$-$learning algorithm

q$\_$learning$()$

# Print the learned Q$-$table

print$("$Learned Q$-$table:"$)$

print$($q$\_$table$)$