def value_iteration(states, actions, transition, reward, discount=0.9, iv=0, epsilon=0.1):
    """
    Updates state values according to the bellman update, explained above. Repeat until convergence,
    defined as maximum change in value for a state over an iteration being less than epsilon
    :param states: a List of valid states in the MDP
    :param actions: a Dict mappings states to lists of possible actions from that state. Null values should be empty lists
    :param transition: a nested Dict of the form transition[s][a] = {s1: 0.5, s2: 0.2, s3: 0.3}
    :param reward: a function accepting a state and returning the reward for that state
    :param discount: Optional, a hyperparameter for the bellman equation governing speed of contraction.
    :param iv: Optional, initial values for the Bellman equation. Used only for visualization, update will converge regardless
    :param epsilon: Optional, convergence threshold
    :return: values, history: Dict mapping states to computed values, List of all values Dicts across iterations
    """
    # intialize values
    values = {
        state: iv for state in states
    }

    delta = 0
    history = [values]
    
    while True:
        new_values = {}
        for state in states:

            action_values = []
            for action in actions(state):
                action_value = 0
                for s_prime, prob in transition[state][action].items():
                    action_value += prob * values[s_prime]
                action_values.append(action_value)

            if len(action_values) > 0:
                optimal_action_value = max(action_values)
            else:
                optimal_action_value = 0

            new_value = reward(state) + discount * optimal_action_value
            abs_diff = abs(new_value - values[state])
            if abs_diff > delta:
                delta = abs_diff

            new_values[state] = new_value

        values = new_values
        history.append(values)
        if delta < epsilon:
            break
        delta = 0

    return values, history