<jupyter_start><jupyter_text>Policy Iteration AlgorithmTable of contents  * [Abstract](abstract)   * [The environment](the-environment)  * [Imports](imports)  * [Measuring execution time](measuring-execution-time)  * [The Policy Evaluation Function](the-policy-evaluation-function)  * [The Policy Improvement Function](the-policy-improvement-function)  * [Interpreting the Output](interpreting-the-output)     Abstract 1. Generate random policy2. Generate random value function3. ???4. ProfitPolicy iteration is a technique for finding an optimal* policy in a given, fully known environment. It is neither fast nor efficient, and the practical applications are therefore limited. However, it is guaranteed to find an optimal policy in finite time, and serves as an important starting point for many reinforcement learning algorithms.The algorithm generates a random policy and evaluates it by calculating the value function (with the help of a policy evaluation algorithm).It then improves the random policy by changing its guidelines according to the newly obtainted value function (choosing actions which lead to the states with the maximum values). This does not yield an optimal policy yet, since the value function is based on a random, (probably**) suboptimal policy.  It then again submits the new, improved policy for review to the evaluation algorithm, receiving the new value function. Again, the policy is updated based on the value function. This process is repeated (iteration!) until there's nothing left to improve - optimality is achieved!In this example, we will try to find the optimal policy for navigating Jack's car rental problem, an excercise provided in the standard reference of Reinforcement Learning, ["Reinforcement Learning: An Introduction"](http://incompleteideas.net/book/bookdraft2017nov5.pdf) by Sutton and Barto.The policy iteration code was copied (and slightly modified) from [<NAME>' GitHub](https://github.com/dennybritz/reinforcement-learning/blob/master/DP/Policy%20Iteration%20Solution.ipynb), but is applied to another problem in this tutorial. _________*why not THE optimal policy? Because technically, there could be several different policies that yield the same reward, and if there's no *better* policy, then multiple optimal policies exist.  **you could, by chance, have guessed an optimal policy. <NAME>'s policy iteration algorithm ends here.  The environment You don't need to know the details of the environment in order to understand policy iteration. You can find the full description [here](http://incompleteideas.net/book/bookdraft2017nov5.pdf).    In brief, Jack runs two car rentals. He earns money (reward) when someone requests a car, and the location is able to provide a car. If he perceives an imbalance between the two locations, he has the possibility to move cars from one spot to another at a minor cost while the business is closed at night.But because the requests are randomly and unequally distributed over both locations, it is not obvious how this balancing should be done.  This is where reinforcement learning comes in; if we see earned money as reward, and expenditures as punishment (or negative reward), we are able to calculate guidelines for balancing the count of cars that maximize expected reward (which in this case equals maximizing expected income).  Imports First, we need to import some libraries.  `time` is imported to measure run times.  `numpy` makes some numerical operations easier.  `CarRentalEnvironment` provides the environment to which we want to apply our policy iteration algorithm.  `matplotlib.pyplot` will be used to visualize our purely numerical results.    This page is a Jupyter Notebook that allows you to run and also modify the code that's written in code cells. Go ahead and execute the imports below by either clicking on the "Run this cell"-button, or by clicking in the cell and pressing shift + enter. As I said, you are able to modify the code, but I recommend not messing with the imports. You will get to play later!<jupyter_code>import time
import sys
!{sys.executable} -m pip install numpy
!{sys.executable} -m pip install matplotlib
import numpy as np
import CarRentalEnvironment as jack
import matplotlib.pyplot as plt<jupyter_output><empty_output><jupyter_text>Measuring execution time Let us begin by storing the time at the start to keep track of the time it takes to execute the code.Next, we initialize the environment. This might take a while, since a transition list of all possible transitions is generated. Because in our example - Jack's Car Rental - there is at least a tiny chance to land in almost any state, regardless of the action we take, the transition list is huge (relative to the number of states). It contains every possible combination of starting state, target state, reward and action.  When this is done, we measure the time again to find out how long this step took. This is relevant if we want to optimize our algorithms, because we need to know how long it took to generate the transition list.jack.env() sets up the environment and return an object of the environment class.  Let's have a look at the environment class as defined in the imported CarRentalEnvironment. Pay special attention to the attributes; they will be of key importance in the next steps!    class environment:        """        Complete information environment class with attributes that fully define the        environment. The environment is a Markov decision process.                env() should be used to initialize an environment object according to the        Jack's Car Rental excercise.                Attributes:            P[s][a] is a list of transition tuples (prob, next_state, reward, done).            nS is a number of states in the environment.             nA is a number of actions in the environment.            shape[] is optional for visualization purposes. It is a list of             integers representing the edge lengths of a matrix that contains the             states. E.g. if the states are best mapped on a 21x21 matrix, the list             should state [21, 21]        """        def __init__(self, P, nS, nA):            self.P = P            self.nS = nS            self.nA = nA            self.shape = [nrOfStates, nrOfStates]<jupyter_code>start_time = time.time()
print("start!")


#env = GridworldEnv()
env = jack.env()

env_time = time.time()
iterationCount = 1
print("Run time of transition list generation = {}s".format(env_time-start_time))<jupyter_output><empty_output><jupyter_text>The Policy Evaluation Function Now we can start writing our algorithm. At first we need to implement a policy evaluation function, which is a necessary tool for a policy iteration algorithm.The policy evaluation function is supposed to evaluate a policy that it is given (as an argument), by producing a value function (or utility function). The value function has the form of a vector, with values corresponding to every state. Since the values represent the expected reward (utility) of a state, not of a transition, the vector is relatively small, containing "only" as many values as there are states. This is in contrast to the number of state-action-reward-state combinations, which is much higher. Initializing the Value FunctionAt first we initialize a value function filled with zeros, whose values are iteratively improved until they become the true values. It doesn't matter with which values you start, they will always converge to the correct solution. In theory, you can speed up the process if you know how the final values roughly look like - by starting with values which are close to that.For example, if you know the final values will mostly be around 20, you could initialize the value function with 20s at each point to achieve fewer iterations. It will make almost no difference in execution time though, because the final value is approximated quadratically.But go ahead and try it out yourself by changing the `0` in `V = np.full(env.nS, 0, float)`!You might need to pick extreme values to get a noticable difference in speed. Note that the same code will have slight variations in execution time when run several times.<jupyter_code># Taken from Policy Evaluation Exercise!

def policy_eval(policy, env, discount_factor, theta=0.00001): #original theta value theta=0.00001
    """
    Evaluate a policy given an environment and a full description of the environment's dynamics.
    
    Args:
        policy: [S, A] shaped matrix representing the policy.
        env: OpenAI env. env.P represents the transition probabilities of the environment.
            env.P[s][a] is a list of transition tuples (prob, next_state, reward, done).
            env.nS is a number of states in the environment. 
            env.nA is a number of actions in the environment.
        theta: We stop evaluation once our value function change is less than theta for all states.
        discount_factor: Gamma discount factor.
    
    Returns:
        Vector of length env.nS representing the value function.
    """
    
    # Some visualization of the policy iteration steps
    global iterationCount
    print("evaluating policy iteration " + str(iterationCount) + ", discount factor = " + str(discount_factor) + ", theta = " + str(theta))
    print("Policy:")    
    visualizePretty(np.reshape(np.argmax(policy, axis=1)-5, env.shape), "policy " + str(iterationCount))
    print("")
    iterationCount += 1
    ##
    
    # Start with a random (all 0) value function
    V = np.full(env.nS, 0, float) # was originally: V = np.zeros(env.nS)
    while True:
        delta = 0
        for s in range(env.nS):
            v = 0
            # Look at the possible next actions
            for a, action_prob in enumerate(policy[s]):
                # For each action, look at the possible next states...
                #for tupel in env.P[s][a]:
                for  prob, next_state, reward, done in env.P[s][a]:
                        #for  prob, next_state, reward, done in tupel:
                        # Calculate the expected value
                        v += action_prob * prob * (reward + discount_factor * V[next_state])
            # How much our value function changed (across any states)
            delta = max(delta, np.abs(v - V[s]))
            V[s] = v
        # Stop evaluating once our value function change is below a threshold
        if delta < theta:
            break
    return np.array(V)<jupyter_output><empty_output><jupyter_text>The For-Each Loop Over `env.P``env.P[s][a]` is a list of all possible transitions from state $s$, under the condition that action $a$ is selected. The list contains target states (possible next states) with their respective rewards and probabilities.This for-each loop calculates the value (expected future reward) of a state under the current policy by summing up the possible rewards which are discounted by the probability of  * the transition itself  * choosing the action under the given policy  and adding the value of the next state, discounted by the discount factor.                     for  prob, next_state, reward, done in tupel:                         Calculate the expected value                        v += action_prob * prob * (reward + discount_factor * V[next_state])  Exit Condition For The Outer LoopSo why is there a `while True:` loop? Shouldn't the loop end once the for-each loop has iterated through every element and has therefore considered all transitions?  The answer to why the latter doesn't work is that when we calculate the value of a state, we need to take into account the value of the next states. We do that by simply adding the value that is given by our value function. But the values of our value function are arbitrary and very likely not correct - we initialized them to be 0 or another guessed value. This means after our first loop through all transitions, the values are all based on a (probably) wrong value function.  We did, however, add some truth to our value function: we considered the (correct) rewards and transition probabilities. This means our value function is not completely arbitrary anymore, it gained some "knowledge" about the true values. By circling through this process often enough, we get closer and closer to the correct values in our value function. This is why we have the "while" loop in the beginning.  We know that we have the correct values in our value function when an update cycle completes without any changes.1______1. For proof that convergence is guaranteed with any starting values, see Theorem 3.6 in ["From ants to safe Artificial Intelligence: Reinforcement Learning" (Lang, 2018)](https://github.com/Favodar/Reinforcement-Learning/blob/master/Reinforcement%20Learning%2C%20Part%201.pdf)↩  The Policy Improvement Function We will now get to the core of the policy iteration algorithm: the policy_improvement function improves a policy until it becomes an optimal policy for maximizing utility in a given environment. Initializing the policyAs a first step, we generate a random policy, similar to  what we did earlier when we set up a random value function `policy = np.ones([env.nS, env.nA]) / env.nA`   Evaluating the policyNext, we let our evaluation function do the job of evaluating this policy. How *value*able are the states if we act according to this policy (in terms of long term expected reward)? This doesn't tell us yet how good our policy is. If we have a utility of, say, 914 in one state, is that good? We don't know, because it's all relative. But we do have a reference now. Future versions of our policy can be measured against this, and that's exactly what we're gonna do!   One step lookaheadWhat we'll do next to improve our policy is to calculate the values of the available actions. So instead of just looking at the state value (which we already did), we look at a state-action pair and calculate the long-term expected reward of this pair. We can do this by looking at where the action could potentially bring us, and summing up the values of those states, multiplied (meaning discounted) by the probability of getting there.    For example, let's say we are in state $s_2$ and if we take action $a_3$, there's a 20% chance to get to state $s_8$, and $s_8$ has a value of $v(s_8)=10$. Then we start by multiplying $v(s_8)$ with the 20% chance:  $v(s_8)*p(s_8|s_2, a_3) = 10*0.2 = 2$      for a in range(env.nA):            for prob, next_state, reward, done in env.P[state][a]:                A[a] += prob * (reward + discount_factor * V[next_state])     return ASo $2$ is the first value we have to keep in mind. But let's say action 3 also yields a 10% chance to arrive in state 20, and state 20 has an astounding value of 360. Then we need to add $360*0.1 = 36$ to what we already got, which is 2. If we keep doing this with every state that action 3 could bring us to, and add up all these values, then we have the value of the state action pair "state 2 - action 3" (under our current policy). Now if we do this for **all** the actions that are available in state 2 (you probably realize by now that this is a lot of calculations), we can chose the one with the highest value and put *this* has our action-recommendation in our policy. [I think some magic happens here before the next step]  Since our policy has now changed (improved!), we need to re-evaluate it to get our value-function up to date as well, and then we can rinse and repeat.  If we do this often enough, we will eventually get an optimal policy. How do we know we have an optimal policy? Same as with the policy evaluation function - if the update cycle completes without changes, we know we're done!<jupyter_code>def policy_improvement(env, discount_factor, theta=0.00001, policy_eval_fn=policy_eval):
    """
    Policy Improvement Algorithm. Iteratively evaluates and improves a policy
    until an optimal policy is found.
    
    Args:
        env: The OpenAI environment.
        policy_eval_fn: Policy Evaluation function that takes 3 arguments:
            policy, env, discount_factor.
        discount_factor: gamma discount factor.
        
    Returns:
        A tuple (policy, V). 
        policy is the optimal policy, a matrix of shape [S, A] where each state s
        contains a valid probability distribution over actions.
        V is the value function for the optimal policy.
        
    """

    def one_step_lookahead(state, V):
        """
        Helper function to calculate the value for all action in a given state.
        
        Args:
            state: The state to consider (int)
            V: The value to use as an estimator, Vector of length env.nS
        
        Returns:
            A vector of length env.nA containing the expected value of each action.
        """
        A = np.zeros(env.nA)
        for a in range(env.nA):
            for prob, next_state, reward, done in env.P[state][a]:
                A[a] += prob * (reward + discount_factor * V[next_state])
        return A
    
    # Start with a random policy
    policy = np.ones([env.nS, env.nA]) / env.nA
    
    while True:
        # Evaluate the current policy
        V = policy_eval_fn(policy, env, discount_factor, theta)
        
        # Will be set to false if we make any changes to the policy
        policy_stable = True
        
        # For each state...
        for s in range(env.nS):
            # The best action we would take under the currect policy
            chosen_a = np.argmax(policy[s])
            
            # Find the best action by one-step lookahead
            # Ties are resolved arbitarily
            action_values = one_step_lookahead(s, V)
            best_a = np.argmax(action_values)
            
            # Greedily update the policy
            if chosen_a != best_a:
                policy_stable = False
            policy[s] = np.eye(env.nA)[best_a]
        
        # If the policy is stable we've found an optimal policy. Return it
        if policy_stable:
            return policy, V<jupyter_output><empty_output><jupyter_text>Interpreting the Output  Policy Probability DistributionEach row of the policy probability distribution represents a state, while the columns represent the actions.The numbers signify the probability of taking the action in that state under the policy, with a value between 0 and 1.  For example, a `1` in position $(2,6)$ means a 100% percent chance to take the 6th action in the 2nd state (which is the state where c1 = 0 and c2 = 1). The 6th action is the action "0" or "move no cars". Reshaped PolicyThe reshaped policy shapes the policy into a matrix where the x-axis represents the number of cars at c1 and the _inverted_ y-axis signifies c2.The numbers in the matrix are the action with the highest probability at that state, under the final policy. Value FunctionThe value function matrix has the same structure as the reshaped policy, but the numbers signify the value (expected future reward, or utility) of that state, if the final policy is followed. The value function is not a policy as it doesn't contain instructions. It tells you how valuable a state is *if* you choose optimal actions from there on, but it doesn't tell you what those actions are (assuming it is the value function of the optimal policy, as it is the case here).<jupyter_code>def visualizePretty(array, title="title goes here"):
    ## 
    dim_1, dim_2 = array.shape
    fig, ax = plt.subplots(figsize=(7,7))
    im = ax.imshow(array)
    
    # Loop over data dimensions and create text annotations.
    for i in range(dim_1):
        for j in range(dim_2):
            text = ax.text(j, i, array[i, j],
                           ha="center", va="center", color="w")
    
    ax.set_title(title)
    fig.tight_layout()
    plt.show()
    ##
plt.rcParams.update({'font.size': 22}) #this just sets the font size for the visualizing plots

policy, v = policy_improvement(env, 0.9, 0.00001)

iteration_time = time.time()
print("Run time of policy iteration = {} sec".format(iteration_time-env_time))

print("Policy Probability Distribution:")
print(policy)
print("")

print("Reshaped Policy (-5 = move 5 cars from B to A, 0 = move no cars, 5 = move 5 cars from A to B):")
#print("(not implemented)")
print(np.reshape(np.argmax(policy, axis=1)-5, env.shape))
print("")

print("visualizePretty:")
visualizePretty(np.reshape(np.argmax(policy, axis=1)-5, env.shape), "final policy")

print("Value Function:")
print(v)
print("")

print("Reshaped Grid Value Function:")
#print("(not implemented)")
list3 = []
for number in v:    
    list3.append(round(number, 3))
#print("(not implemented)")
print(str(np.reshape(list3, env.shape)).replace("'", ""))
print("")

plt.rcParams.update({'font.size': 5})

print("visualizePretty:")
visualizePretty(np.reshape(v, env.shape), "value function")

end_time = time.time()

print("Run time total = {} sec".format(end_time - start_time))
print("Run time of transition list generation = {} sec".format(env_time-start_time))
print("Run time of policy iteration = {} sec".format(iteration_time-env_time))<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.06535514991014849, 'fraction_numerical': 0.008086635770358461, 'mean_word_length': 3.4840966921119594, 'pattern_counts': {'":': 0, '<': 24, '<?xml version=': 0, '>': 23, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 1, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '5', 'dir': 'jupyter-structured-clean-dedup', 'id': '51172', 'license': 'MIT', 'n_tokens_mistral': 5525, 'n_tokens_neox': 5234, 'n_words': 2852, 'path': 'Jacks-Car-Rental/.ipynb_checkpoints/PolicyIterationNotebook-checkpoint.ipynb', 'repo_name': 'Favodar/Reinforcement-Learning', 'size': '21161'}