import copy #function that returns action_space for a 3x3 grid def getActionSpace(state): a = ["N", "E", "S", "W"] row = state[0] col = state[1] if row == 0: #If at the bottom a.remove("S") #Can't go down if row == 2: a.remove("N") if col == 0: a.remove("W") if col == 2: a.remove("E") return a epsilon = 1 disc_f = 0.9 #recursive function that breaks when difference in value for each state space is less than epsilon def iterate (r, V, itNr): """ Parameters ---------- r : array reward_function. V : array Value function. itNr : int Counter Returns ------- Pi : Array, V : Array The optimal policy and the converging optimal value function """ V_prev = copy.deepcopy(V) #List storing policies for states at their position Pi = [["","",""],["","",""],["","",""]] #Looping through every state space for row in range(3): for col in range(3): s = [row, col] #gets the avaliable actions for state_space s action_space = getActionSpace(s) max_value = 0; curr_pi = "" #if action go direction -> move 1 coordinate up/down/left/right for a in action_space: if a == "N": s_new = [s[0]+1,s[1]] elif a == "E": s_new = [s[0],s[1]+1] elif a == "S": s_new = [s[0]-1,s[1]] elif a == "W": s_new = [s[0],s[1]-1] #reward and value matrix value for s r_old = r[s[0]][s[1]] #r_old = r[1][2] V_s_old = V_prev[s[0]][s[1]] #reward and value matrix value for s_new r_curr = r[s_new[0]][s_new[1]] V_s_new = V_prev[s_new[0]][s_new[1]] #calculates the current expected value for given state and action curr_value = 0.8*(r_curr + disc_f * V_s_new) + 0.2*(r_old + disc_f * V_s_old) #updates what is the highest expected value at this state if (curr_value >= max_value): curr_pi = a max_value = curr_value #update value matrix with highest expected value at this state V[row][col] = round(max_value,2) #updates pi matrix with optimal action / policy at this state Pi[row][col] = curr_pi #prints V and policy for each state print("Iteration nr", itNr, ":") for v in V: print(v) for pi in Pi: print(pi) print("\n") for row in range(3): for col in range (3): s = [row, col] #if difference of old and updated value matrix is higher than epsilon, run another iteration if (abs(V_prev[row][col] - V[row][col]) >= epsilon): itNr += 1 iterate(r, V, itNr) return Pi, V return Pi, V #Reward matrix r = [[0,0,0], [0,10,0], [0,0,0]] #Value matrix V = [[0,0,0], [0,0,0], [0,0,0]] itNr = 1 Pi, V = iterate(r, V, itNr) #Calling the value-function print("Method returns: ", Pi, V)

import gym import gym_toytext import numpy as np import random import math #Creating the environment env = gym.make("NChain-v0") #Setting the parameters num_episodes = 1000 #10000 gamma = 0.95 #given in question learning_rate = 0.1 #given in question epsilon = 0.3 # initialize the Q table Q = np.zeros([5, 2]) #Algorithm for creating the Q-matrix for episode in range(num_episodes): state = env.reset() done = False while done == False: # First we select an action: if random.uniform(0, 1) < epsilon: # Flip a skewed coin action = env.action_space.sample() # Explore action space else: action = np.argmax(Q[state,:]) # Exploit learned values # Then we perform the action and receive the feedback from the environment new_state, reward, done, info = env.step(action) # Finally we learn from the experience by updating the Q-value of the selected action prediction_error = reward + (gamma*np.max(Q[new_state,:])) - Q[state, action] Q[state,action] += learning_rate*prediction_error state = new_state #Printing the first 10 and last 10 iteration to see plateau convergence if episode < 10 or episode > num_episodes - 10: print("Episode:", episode) print(Q) print()

import copy #Defining the MDP S = [0, 1, 2, 3, 4] #State_space A = [0,1] #Same for all states, 0 = forward, 1 = back to start P = 0.8 #Transition probability: 80% probability to get to state s' given action a R = [2, 0, 0, 0, 10] #Reward function V = [0, 0, 0, 0, 0] #Initial value-function, V_0 #Algorithm to calculate the value-function #Changes in number of iterations showed that the value will converge long before 1000 iterations for _ in range(1000): V_prev = copy.deepcopy(V) s_backward = S[0] #Back to start for s in S: max_value = 0 if s <= 3: s_forward = S[s+1] #Moving forward else: s_forward = S[4] #Standin still for a in A: if a == 0: p = 0.8 #Probability to move forward else: p = 0.2 #Probability to move forward #calculates the current expected value for given state and action curr_value = p*(R[s_forward] + gamma*(V_prev[s_forward])) + (1-p)*(R[s_backward] + gamma*(V_prev[s_backward])) if (curr_value >= max_value): curr_pi = a max_value = curr_value #update value matrix with highest expected value at this state V[s] = round(max_value,2) print("Q:", Q) print() print("V:", V)