<jupyter_start><jupyter_text>MDP Implementations<jupyter_code># Creating MDP representation for the grid world and organizing its functionalities

class ActionResult:
    def __init__ (self, resultState, prob, reward):
        self.resultState = resultState
        self.prob = prob
        self.reward = reward
        
    def __str__(self):
        return "resultstate: {0}\nprobability: {1}\nReward: {2}".format(str(self.resultState), str(self.prob), str(self.reward))

class Action:
    # abstraction for an action. Expects a state on which this action
    # can be taken and a list of ActionResult
    def __init__ (self, state, results, label):
        self.state = state
        self.results = results
        self.label = label
    
    def __str__(self):
        s = "{0} - {1}\n".format(str(self.state), self.label)
        for r in self.results:
            s = s + str(r) + "\n"
            
        return s
#         return str(self.state) + " " + str([str(r) for r in self.results])
     
class State:
    def __init__(self, id, actions, value):
        self.id = id
        self.actions = actions
        self.value = value       

        def __str__(self):
            return str(self.id) + " " + str(self.value) + " " + str(self.actions)

class GridWorldMDP(object):        
    def __init__ (self, rewards, rows, cols, actions):
        self.rows = rows
        self.cols = cols
        self.rewards = rewards
        self.policy = [['u' for j in range(cols)] for i in range(rows)]
        self.value = [[0 for j in range(cols)] for i in range(rows)]
        self.states = [[State((i, j), actions[(i, j)], 0) for j in range(cols)] for i in range(rows)]
    
    def getStateValue(self, state):
        return self.states[state[0]][state[1]].value

    def setStateValue(self, state, v):
        self.states[state[0]][state[1]].value = v
        
    def upadateStateValue(self, state):
        maxV = float("-inf")
        actions = self.states[state[0]][state[1]].actions
        for i in range(len(actions)):
            action = actions[i]
            resultState = action.results[0].resultState
            r = action.results[0].reward
            v = self.getStateValue(resultState)
            if r + v > maxV:
                maxV = r + v
                self.policy[state[0]][state[1]] = action.label
                self.setStateValue(state, v)
    
    def printValues(self):
        for r in self.value:
            print(r)
            
    def getPolicy(self):
        return self.policy
        
        
    def printPolicy(self):
        for r in self.policy:
            print(r)
        print()

    def iterateValues(self):
        for i in range(self.rows):
            for j in range(self.cols):
                self.upadateStateValue((i, j))

    def iterateValuesUntilConverge(self, printSteps=False):
        while True:
            values = self.value
            self.iterateValues()
            if printSteps:
                print()
                self.printPolicy()      
            if values == self.value:
                break
                
    def repeatIterateValues(self, n, printSteps=False):
        for i in range(n):
            self.iterateValues()
            if printSteps:
                print()
                self.printPolicy()        

class DeterministicGridWorldMDP(GridWorldMDP):
    transitions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    nTransitionsPerState = len(transitions)
    # creates a gridworld representation where the reward for every transition
    # is given in the rewards matrix which means the reward the agent gets when achieving that reward
    def __init__ (self, rewards, rows, cols):
        actions = DeterministicGridWorldMDP.getDeterministicGridWorldDefaultActions(rewards, rows, cols)
        super(DeterministicGridWorldMDP, self).__init__(rewards, rows, cols, actions)

    @staticmethod
    def getDeterministicGridWorldDefaultActions(rewards, rows, cols):
        keys = []
        for j in range(cols):
            for i in range(rows):
                keys.append((i, j))
        actions = {key: DeterministicGridWorldMDP.generateActions(key[0], key[1], rewards, rows, cols) for key in keys}
        
        return actions
        
    @staticmethod
    def isValidTransition(dest, rows, cols):
        return  not ((dest[0] < 0 or dest[0] >= rows) or (dest[1] < 0 or dest[1] >= cols))
    
    @staticmethod
    def generateActions(i, j, rewards, rows, cols):
        actions = []
        prettyDirs = ['r', 'l', 'd', 'u']
        for transition in range(DeterministicGridWorldMDP.nTransitionsPerState):
            resultState = (i + DeterministicGridWorldMDP.transitions[transition][0], j + DeterministicGridWorldMDP.transitions[transition][1])
            if DeterministicGridWorldMDP.isValidTransition(resultState, rows, cols):
                actions.append(Action((i, j), [ActionResult(resultState, 1, rewards[resultState[0]][resultState[1]])], prettyDirs[transition]))
         
        return actions<jupyter_output><empty_output><jupyter_text>Auxiliary functions<jupyter_code>def printMatrix(matrix):
    for r in matrix:
        print(r)
    print()

def generateRandomRewards(row, cols, goalReward, notGoalReward):
    goalCoordX, goalCoordY = randint(0, rows - 1), randint(0, cols - 1)
    rewards = [[notGoalReward for j in range(cols)] for i in range(rows)]
    rewards[goalCoordX][goalCoordY] = goalReward
    return rewards, (goalCoordX, goalCoordY)

def generateRandomRewardsWithObstacles(row, cols, goalReward, notGoalReward, obstacleReward, nObstacles):
    
    rewards = [[notGoalReward for j in range(cols)] for i in range(rows)]
    
    goalCoordX, goalCoordY = randint(0, rows - 1), randint(0, cols - 1)
    goal = (goalCoordX, goalCoordY)
    rewards[goalCoordX][goalCoordY] = goalReward
    
    obstacles = []
    while nObstacles > 0:
        obs = randint(0, rows - 1), randint(0, cols - 1)
        if not obs in obstacles and not obs == goal:
            obstacles.append(obs)
            nObstacles = nObstacles - 1
            rewards[obs[0]][obs[1]] = obstacleReward
    
    return rewards, goal, obstacles


def markGoalAndObstaclesOnGrid(grid, goal, obstacles):
    grid[goal[0]][goal[1]] = 'G'
    for o in obstacles:
        grid[o[0]][o[1]] = 'X'
    
    return grid<jupyter_output><empty_output><jupyter_text>Tests with deterministics gridworld environments<jupyter_code># First dummy smoke test to make sure everything is not absurdly wrong

rewards = [
    [-1, -1, -1],
    [-1, 100, -1],
    [-1, -1, -1]
]

rows, cols = 3, 3

mdp = DeterministicGridWorldMDP(rewards, rows, cols)
mdp.printPolicy()
mdp.repeatIterateValues(10)
print ()
printMatrix(markGoalAndObstaclesOnGrid(mdp.getPolicy(), (1,1), []))
# Testing random test case for 10 rows and cols  

rows, cols = 10, 10

rewards, goal = generateRandomRewards(rows, cols, 100, 0)
mdp = DeterministicGridWorldMDP(rewards, rows, cols)
mdp.printPolicy()
mdp.repeatIterateValues(5)
printMatrix(markGoalAndObstaclesOnGrid(mdp.getPolicy(), goal, []))
# Grid world with obstacles (things are getting interesting)

rows, cols = 5, 5

rewards, goal, obs = generateRandomRewardsWithObstacles(rows, cols, 100, 0, -1000, 5)
print ("rewards")
printMatrix(rewards)
print ("goal", goal)
print ("obstacles", obs)
print()

mdp = DeterministicGridWorldMDP(rewards, rows, cols)
mdp.printPolicy()
mdp.repeatIterateValues(10)
print()

printMatrix(markGoalAndObstaclesOnGrid(mdp.getPolicy(), goal, obs))
# This case proves my iterate until converge is not working propperly

rewards = [
    [0, 0, 0, -1000, 0],
    [0, -1000, 0, 0, -1000],
    [-1000, 0, 0, 0, 0],
    [0, -1000, 100, 0, 0],
    [0, 0, 0, 0, 0]
]

goal = (3, 2)
obs = [(1, 4), (3, 1), (2, 0), (1, 1), (0, 3)]
print ("rewards")
printMatrix(rewards)
print ("goal", goal)
print ("obstacles", obs)
print()

mdp = DeterministicGridWorldMDP(rewards, rows, cols)
mdp.iterateValuesUntilConverge()

printMatrix(markGoalAndObstaclesOnGrid(mdp.getPolicy(), goal, obs))

mdp = DeterministicGridWorldMDP(rewards, rows, cols)
mdp.repeatIterateValues(10)
printMatrix(markGoalAndObstaclesOnGrid(mdp.getPolicy(), goal, obs))

# Another case where iterating until converge do not work

rewards = [
    [0,     0,      0,     0, 0],
    [0,     0,     -1000,  0, -1000],
    [0,     0,     0,      0, 0],
    [0,     -1000, -1000,  -1000, -1000],
    [0,     0,     0,    0, 100]
]

rows, cols = 5, 5

goal = (4, 4)
obs = [(3, 1),(3, 2), (3, 3), (3, 4), (1, 2), (1, 4)]
print ("rewards")
printMatrix(rewards)
print ("goal", goal)
print ("obstacles", obs)
print()

mdp = DeterministicGridWorldMDP(rewards, rows, cols)
mdp.iterateValuesUntilConverge()
printMatrix(markGoalAndObstaclesOnGrid(mdp.getPolicy(), goal, obs))

mdp = DeterministicGridWorldMDP(rewards, rows, cols)
mdp.repeatIterateValues(10)
printMatrix(markGoalAndObstaclesOnGrid(mdp.getPolicy(), goal, obs))
# Lets have variable obstacles with variable penalties

rewards = [
    [0,     0,      0,     0, 0],
    [0,     0,     -1000,  0, -1000],
    [0,     0,     0,      0, 0],
    [0,     -250, -500,  -750, -1000],
    [0,     0,     0,    0, 100]
]

rows, cols = 5, 5

goal = (4, 4)
obs = [(3, 1),(3, 2), (3, 3), (3, 4), (1, 2), (1, 4)]
print ("rewards")
printMatrix(rewards)
print ("goal", goal)
print ("obstacles", obs)
print()

mdp = DeterministicGridWorldMDP(rewards, rows, cols)
mdp.iterateValuesUntilConverge()
printMatrix(markGoalAndObstaclesOnGrid(mdp.getPolicy(), goal, obs))

mdp = DeterministicGridWorldMDP(rewards, rows, cols)
mdp.repeatIterateValues(10)
printMatrix(markGoalAndObstaclesOnGrid(mdp.getPolicy(), goal, obs))
# Lets now give negative reward for moving

rewards = [
    [-100,     -100,      -100,     -100, -10],
    [-100,     -100,     -1000,  -100, -1000],
    [-100,     -100,     -100,      -100, -10],
    [-100,     -250, -500,  -750, -1000],
    [-100,     -100,     -100,    -100, 100]
]

rows, cols = 5, 5

goal = (4, 4)
obs = [(3, 1),(3, 2), (3, 3), (3, 4), (1, 2), (1, 4)]
print ("rewards")
printMatrix(rewards)
print ("goal", goal)
print ("obstacles", obs)
print()

mdp = DeterministicGridWorldMDP(rewards, rows, cols)
mdp.iterateValuesUntilConverge()
printMatrix(markGoalAndObstaclesOnGrid(mdp.getPolicy(), goal, obs))

mdp = DeterministicGridWorldMDP(rewards, rows, cols)
mdp.repeatIterateValues(20)
printMatrix(markGoalAndObstaclesOnGrid(mdp.getPolicy(), goal, obs))
# how long it takes to converge

rows, cols = 100, 100

rewards, goal, obs = generateRandomRewardsWithObstacles(rows, cols, 100, 0, -1000, 100)
print ("rewards")
# printMatrix(rewards)
print ("goal", goal)
print ("obstacles", obs)
print()

mdp = DeterministicGridWorldMDP(rewards, rows, cols)
mdp.iterateValuesUntilConverge()
policy1 = mdp.getPolicy()
# printMatrix(markGoalAndObstaclesOnGrid(mdp.getPolicy(), goal, obs))

mdp = DeterministicGridWorldMDP(rewards, rows, cols)
mdp.repeatIterateValues(10)
policy2 = mdp.getPolicy()
# printMatrix(markGoalAndObstaclesOnGrid(mdp.getPolicy(), goal, obs))

mdp = DeterministicGridWorldMDP(rewards, rows, cols)
mdp.repeatIterateValues(50)
policy3 = mdp.getPolicy()

mdp = DeterministicGridWorldMDP(rewards, rows, cols)
mdp.repeatIterateValues(100)
policy4 = mdp.getPolicy()

print(policy1 == policy2)
print(policy2 == policy3)
print(policy3 == policy4)

# First dummy smoke test to make sure everything is not absurdly wrong

rewards = [
    [-1, -1, -1],
    [-1, 100, -1],
    [-1, -1, -1]
]

rows, cols = 3, 3

stateActions = DeterministicGridWorldMDP.getDeterministicGridWorldDefaultActions(rewards, rows, cols)
for s in stateActions:
    for a in stateActions[s]:
        print(str(a))

# print(stateActions.__dict__)
# s = json.dumps(stateActions)
# print(s)<jupyter_output>(0, 0) - r
resultstate: (0, 1)
probability: 1
Reward: -1

(0, 0) - d
resultstate: (1, 0)
probability: 1
Reward: -1

(1, 0) - r
resultstate: (1, 1)
probability: 1
Reward: 100

(1, 0) - d
resultstate: (2, 0)
probability: 1
Reward: -1

(1, 0) - u
resultstate: (0, 0)
probability: 1
Reward: -1

(2, 0) - r
resultstate: (2, 1)
probability: 1
Reward: -1

(2, 0) - u
resultstate: (1, 0)
probability: 1
Reward: -1

(0, 1) - r
resultstate: (0, 2)
probability: 1
Reward: -1

(0, 1) - l
resultstate: (0, 0)
probability: 1
Reward: -1

(0, 1) - d
resultstate: (1, 1)
probability: 1
Reward: 100

(1, 1) - r
resultstate: (1, 2)
probability: 1
Reward: -1

(1, 1) - l
resultstate: (1, 0)
probability: 1
Reward: -1

(1, 1) - d
resultstate: (2, 1)
probability: 1
Reward: -1

(1, 1) - u
resultstate: (0, 1)
probability: 1
Reward: -1

(2, 1) - r
resultstate: (2, 2)
probability: 1
Reward: -1

(2, 1) - l
resultstate: (2, 0)
probability: 1
Reward: -1

(2, 1) - u
resultstate: (1, 1)
probability: 1
Reward: 100

(0, 2) - l
[...]
{'fraction_non_alphanumeric': 0.13776591569196955, 'fraction_numerical': 0.041526022450741815, 'mean_word_length': 3.0547422024188413, 'pattern_counts': {'":': 0, '<': 14, '<?xml version=': 0, '>': 16, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 8, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '3', 'dir': 'jupyter-structured-clean-dedup', 'id': '506280', 'license': 'MIT', 'n_tokens_mistral': 4908, 'n_tokens_neox': 4521, 'n_words': 1212, 'path': 'Implementations/RLValueAndPolicyIterationGridWorld.ipynb', 'repo_name': 'RenatoGeh/ReinforcementLearning-knowledgeBase', 'size': '12739'}