<jupyter_start><jupyter_text>Define the Environment![image.png](attachment:image.png)Consider a 4*4 GridAbove.    The nonterminal states are S = {1, 2, . . . , 14}.    There are four actions possible in each state, A = {up, down, right, left}, which deterministically cause the corresponding state transitions, except that actions that would take the agent out of the grid in fact leave the state unchanged. Thus, for instance, p(6,−1|5, right) = 1, p(7,−1|7, right) = 1, and p(10, r|5, right) = 0 for all r 2 R.     This is an undiscounted, episodic task.     The reward is −1 on all transitions until the terminal state is reached. The terminal state isshaded in the figure (although it is shown in two places, it is formally one state).     The expected reward function is thus r(s, a, s0) = −1 for all states s, s0 and actions a. The same dynamics of the class are coded in below class<jupyter_code>class GridWorld():
    def __init__(self):
        '''
        Initialize the Gridword
        self.state (list) : How many non-termimal state does this GridWordHave
        self.statePlus : Non terminal + terminal state
        self.posibleStateAction : Possible action for each state
        self.dynamic : Dynamics of this GridWorld
        '''
        self.state = np.arange(1,15)
        self.statePlus = np.arange(1,16)
        self.posibleStateAction = self.defPossibleStateAction()
        self.dynamic = self.defineDynamic() 
        
    def defPossibleStateAction(self):
        #defining Possible action for this GridWorld
        posibleStateAction = dict()
        for s in self.state:
            posibleStateAction[s] = [1,2,3,4]  #Up,down,left,right
        return posibleStateAction
    
    def defineDynamic(self):
        #defining the dynamics of the Environmvent
        dynamic = dict()
        for s in self.state:
            for a in self.posibleStateAction:
                if a == 1: #when action is UP
                    dynamic[(s,a)] = [(s if (s-4) < 0 else s-4,-1,1)]
                elif a == 2: # when action is down
                    dynamic[(s,a)] = [(s if (s+4) > 15 else s+4,-1,1)]
                elif a == 3: #when action is left
                    dynamic[(s,a)] = [(s if s%4 == 0 else s-1,-1,1)]
                elif a == 4: #when action is right
                    dynamic[(s,a)] = [(s if s%4 == 3 else s+1,-1,1)]
        
        dynamic[(1,3)] = [(15,-1,1)]
        dynamic[(4,1)] = [(15,-1,1)]
        return dynamic<jupyter_output><empty_output><jupyter_text>Value Iteration![image.png](attachment:image.png)<jupyter_code>def valuesIteration(env,v,gamma = 1,threshold=0.01):
    '''
    This is the implementation of Policy Iteration
    '''
    hist = []
    while True:
        delta = 0
        for s in env.state:
            vtemp = 0
            actionReward = []
            for action in env.posibleStateAction[s]:
                for sDash,reward,prob in env.dynamic[(s,action)]:
                    actionReward.append(prob * (reward + gamma * v[sDash-1]))
            vtemp = max(actionReward)
            delta = max(delta,abs(vtemp-v[s-1]))
            v[s-1] = vtemp
        #print(v,delta)
        hist.append(cp.deepcopy(v))
        if (delta < threshold):
            break;
    return hist
def oneStepLookAhead(s,env,v,gamma = 1):
    actionReward = []
    for action in env.posibleStateAction[s]:
        for sDash,reward,prob in env.dynamic[(s,action)]:
            actionReward.append(prob * (reward + gamma * v[sDash-1]))
    return actionReward
def findPolicy(env,v):
    newPolicy = dict()
    for s in env.state:
        #get the values from each of values function
        actionRewards = oneStepLookAhead(s,env,v)
        #placing 1 which has the hightest values
        maxReward = [1 if i == max(actionRewards) else 0 for i in actionRewards ]
        #finding the probability
        maxReward = maxReward/np.sum(maxReward)
        #making the new Policy
        newPolicy[s] = [(i+1,j) for i,j in enumerate(maxReward) ]
    return newPolicy
def printPolicy(policy):
    print("state \t [Up,\t       down, \t left, \t    right]")
    for key in policy:
        print(key ,"\t", policy[key])
env = GridWorld() 
v = np.zeros(len(env.statePlus))
hist = valuesIteration(env,v)
policy = findPolicy(env,hist[-1])
print("Final Policy")
printPolicy(policy)
sampleh = []
posi = [0]
sampleh.append(hist[0])
pos =np.random.choice(np.arange(1,len(hist)-1), 1)
sampleh += [hist[i] for i in pos]
posi += list(pos)
sampleh.append(hist[-1])
posi.append(len(hist)-1)
for i,hi in zip(posi,sampleh):
    print("**********Value Iteration",i," iteration values*******")
    hi = np.insert(hi,0,0)
    print(np.round(hi).reshape(4,4))<jupyter_output>**********Value Iteration 0  iteration values*******
[[ 0. -1. -1. -1.]
 [-1. -1. -1. -1.]
 [-1. -1. -1. -1.]
 [-1. -1. -1.  0.]]
**********Value Iteration 1  iteration values*******
[[ 0. -1. -2. -2.]
 [-1. -2. -2. -2.]
 [-2. -2. -2. -1.]
 [-2. -2. -1.  0.]]
**********Value Iteration 3  iteration values*******
[[ 0. -1. -2. -3.]
 [-1. -2. -3. -2.]
 [-2. -3. -2. -1.]
 [-3. -2. -1.  0.]]
{'fraction_non_alphanumeric': 0.14856918855350842, 'fraction_numerical': 0.029008232065856527, 'mean_word_length': 2.4042695130086726, 'pattern_counts': {'":': 0, '<': 10, '<?xml version=': 0, '>': 9, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '2', 'dir': 'jupyter-structured-clean-dedup', 'id': '261276', 'license': 'MIT', 'n_tokens_mistral': 1755, 'n_tokens_neox': 1682, 'n_words': 513, 'path': 'HW2/Code/Question6_ValuesIteration.ipynb', 'repo_name': 'ppthegp/CSE564-Reinforcement-Learning', 'size': '5102'}