assignment_3.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<center> <font size=6>Stochastic Optimization</font></center>\n",
    "<center> <font size=4>PW4 Machine Replacement Problem</font></center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Introduction"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this problem, we want to optimize the moment when we are to replace a machinery in a candy factory.  \n",
    "At the end of each production cycle (e.g. seasonal) a candy production line must decide whether to keep a machinery again or replace it with a new one."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 1. Bellman Equation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "_**Write down the Bellman optimality equation of the value function.**_"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The Bellman optimality equation for this problem is given by:\n",
    "\n",
    "$$V*(s) = max[ y(s)m + \\gamma ∑T(s,a,s')V*(s') ]$$\n",
    "\n",
    "where $V*(s)$ is the optimal value function for state $s$, $y(s)$ is the production efficiency of the machinery at state $s$, $m$ is the profit contribution of candy per ton, $\\gamma$ is the discount factor, $T(s,a,s')$ is the state transition probability from state $s$ to state $s'$ under action $a$, and the summation is over all possible next states $s'$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 2. Value Iteration"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "_**What replacement policy maximizes the expected long term cumulative profits?**_   \n",
    "_**Using Value Iteration to solve the problem (you are also encouraged to use the Policy Iteration and Linear Program- ming method). Test the sensitivity of the optimal policies to different problem parameters, e.g., p and c.**_"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We first need to define the **environment** in which the problem takes place as a **Markov Decision Process**."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Markov Decision Process Environment"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Variables**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We have the following variables that are the *core* of our subject:\n",
    "- Actions Set $\\mathcal{A}$\n",
    "- States Set $\\mathcal{S}$\n",
    "- Probability $\\mathcal{p}$\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [],
   "source": [
    "# ============================ VARIABLES ============================ #\n",
    "actions = [\"keep\",\"replace\"]\n",
    "states = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]\n",
    "p = 0.3"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Parameters**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We also need to define all the **hyperparameters** of our MDP problem that will be used when **solving**:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [],
   "source": [
    "# ============================ PARAMETERS ============================ #\n",
    "max_iter = 10000  # Maximum number of iterations\n",
    "delta = 1e-400  # Error tolerance\n",
    "V = [0,0,0,0,0,0,0,0,0,0]  # Initialize values\n",
    "pi = [None,None,None,None,None,None,None,None,None,\"replace\"]  # Initialize policy\n",
    "gamma = 0.9  # discount factor\n",
    "theta = 0.1  # threshold parameter that defines when the change in the value function is negligible (i.e. when we can stop process of Policy Evaluation)\n",
    "m = 150 #PROFIT\n",
    "c = 500 #COST"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Functions**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In order to simulate the ***dynamics*** inside our MDP, some functions are to be defined:\n",
    "- `action_function`: defines the *potential* actions that can be taken when at state $s$\n",
    "- `reward_function`: defines the $reward$ given when action $a$ is taken while in state $s$\n",
    "- `state_transition_function`: in this ***stochastic*** model, defines the **probability** of transitioning from state $s$ to next state $s'$ when taking action $a$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [],
   "source": [
    "# ============================ FUNCTIONS ============================ #\n",
    "\n",
    "# Action Function #\n",
    "def action_function(current_state):\n",
    "    if current_state < 10:\n",
    "        actions = [\"keep\", \"replace\"]\n",
    "        return actions  # Action 'Keep\n",
    "\n",
    "    elif current_state == 10:\n",
    "        actions = [\"replace\"]\n",
    "        return actions  # Action 'Replace'\n",
    "\n",
    "# Reward Function #\n",
    "def reward_function(state, action,s_next,m,c):\n",
    "    if action == \"keep\":\n",
    "        return (\n",
    "            8 + state - 0.15 * state**2\n",
    "        ) * m  # Action 'Keep\n",
    "\n",
    "    elif action == \"replace\":\n",
    "        return (\n",
    "            (8 + state - 0.15 * state**2) * m\n",
    "        ) - c  # Action 'Replace'\n",
    "\n",
    "# State Transition Function #\n",
    "def state_transition_function(current_state, action, probability):\n",
    "    \"\"\"\n",
    "    Return all non-zero probability transitions for this action\n",
    "        from this state, as a list of (state, probability) pairs\n",
    "    \n",
    "    => Pr[s'|s,a] = Pr[S_{t+1} = s_prime | S_t = current_state, A_t = action]\n",
    "    \"\"\"\n",
    "\n",
    "    if (\n",
    "        (action == \"keep\") \n",
    "        and (current_state <= 8)\n",
    "    ):\n",
    "        return [(current_state + 1,probability),(current_state + 2, 1 - probability)]\n",
    "\n",
    "    if (action == \"keep\") and (current_state == 9):\n",
    "        return [(10, 1)]\n",
    "\n",
    "    if (action == \"keep\") and (current_state == 10):\n",
    "        return [(0, 0)]\n",
    "        \n",
    "    if (action == \"replace\"):\n",
    "        return [(1, 1)]\n",
    " "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Value Iteration Algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Start value iteration\n",
    "for i in range(max_iter):\n",
    "    max_diff = 0  # Initialize max difference\n",
    "    V_new = [0,0,0,0,0,0,0,0,0,0]  # Initialize values\n",
    "    for s in states:\n",
    "        max_val = 0\n",
    "        for a in actions:\n",
    "            val = 0.0\n",
    "            # Bellman update\n",
    "            for (s_next, transition_probability) in state_transition_function(s, a, p):\n",
    "                reward = reward_function(s, a, s_next,m,c)  # Get direct reward\n",
    "                val += transition_probability * (reward+ (gamma* V[s_next-1]))\n",
    "                \n",
    "            # Store value best action so far\n",
    "            max_val = max(max_val, val)\n",
    "            \n",
    "            # Update best policy\n",
    "            if V[s-1] < val:\n",
    "                pi[s-1] = a # Store action with highest value\n",
    "\n",
    "        V_new[s-1] = max_val  # Update value with highest value\n",
    "        # Update maximum difference\n",
    "        max_diff = max(max_diff, abs(V[s-1] - V_new[s-1]))\n",
    "\n",
    "    # Update value functions\n",
    "    V = V_new\n",
    "   \n",
    "    # If diff smaller than threshold delta for all states, algorithm terminates\n",
    "    if max_diff < delta:\n",
    "        break"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Optimal Value Function V^* for state 1: 12589.879168355506\n",
      "Optimal Value Function V^* for state 2: 12577.650209007583\n",
      "Optimal Value Function V^* for state 3: 12486.37081257692\n",
      "Optimal Value Function V^* for state 4: 12375.12712636796\n",
      "Optimal Value Function V^* for state 5: 12218.391251519955\n",
      "Optimal Value Function V^* for state 6: 12120.891251519955\n",
      "Optimal Value Function V^* for state 7: 11978.391251519955\n",
      "Optimal Value Function V^* for state 8: 11790.891251519955\n",
      "Optimal Value Function V^* for state 9: 11558.391251519955\n",
      "Optimal Value Function V^* for state 10: 11280.891251519955\n"
     ]
    }
   ],
   "source": [
    "for index, val in enumerate(V):\n",
    "    print(f\"Optimal Value Function V^* for state {index+1}: {val}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Optimal policy 𝜋^* for state 1: keep\n",
      "Optimal policy 𝜋^* for state 2: keep\n",
      "Optimal policy 𝜋^* for state 3: keep\n",
      "Optimal policy 𝜋^* for state 4: keep\n",
      "Optimal policy 𝜋^* for state 5: replace\n",
      "Optimal policy 𝜋^* for state 6: replace\n",
      "Optimal policy 𝜋^* for state 7: replace\n",
      "Optimal policy 𝜋^* for state 8: replace\n",
      "Optimal policy 𝜋^* for state 9: replace\n",
      "Optimal policy 𝜋^* for state 10: replace\n"
     ]
    }
   ],
   "source": [
    "for index, val in enumerate(pi):\n",
    "    print(f\"Optimal policy 𝜋^* for state {index+1}: {val}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Conclusion"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In order to **maximize** profit, the candy factory should consider *replacing* only starting from state 6."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 3. Policy Iteration"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The optimal replacement policy that maximizes the expected long term cumulative profits is to replace the machinery at state 9 (i.e. the last state before becoming too unproductive) and keep it at all other states. This policy is derived by solving the Bellman optimality equation using the policy iteration algorithm."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![image](./val_iter_vs_pol_iter.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Variables, Parameters & Functions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In the following code, we again define the states, actions, and hyperparams for our **Policy Iteration** problem for more consistency."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Define the set of states S\n",
    "S = list(range(1, 11))\n",
    "\n",
    "# Define the problem parameters\n",
    "p = 0.9\n",
    "m = 150\n",
    "c = 500\n",
    "gamma = 0.9\n",
    "epsilon = 1e-6\n",
    "\n",
    "# Initialize the policy\n",
    "pi = {}\n",
    "for s in range(1, 10):\n",
    "    pi[s] = {\"keep\":1,\"replace\":0}\n",
    "    pi[10] = {\"keep\":0,\"replace\":1}\n",
    "\n",
    "#Initialize the value function\n",
    "\n",
    "V = {}\n",
    "for s in range(1, 11):\n",
    "    V[s] = 0\n",
    "\n",
    "# Initialize the previous policy\n",
    "old_pi = {}\n",
    "\n",
    "# Define the production efficiency function\n",
    "def y(s):\n",
    "    return 8 + s - 0.15 * s**2\n",
    "\n",
    "# Define the state transition probability function\n",
    "def state_transition_probability(s, a, s_next):\n",
    "    if a == 'keep':\n",
    "        if s_next == s + 1 and s <= 8:\n",
    "            return p\n",
    "        elif s_next == s + 2 and s <= 8:\n",
    "            return 1 - p\n",
    "        elif s_next == 10 and s == 9:\n",
    "            return 1\n",
    "        else:\n",
    "            return 0\n",
    "    elif a == 'replace':\n",
    "        if s_next == 1:\n",
    "            return 1\n",
    "        else:\n",
    "            return 0\n",
    "\n",
    "# Define the reward function\n",
    "def reward_function(s, a):\n",
    "    if a == 'keep':\n",
    "        return y(s) * m\n",
    "    elif a == 'replace':\n",
    "        return y(s) * m - c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "def improve_policy(pi, current_state, best_actions, p):\n",
    "    \"\"\"\n",
    "    Defines a new policy pi(a|s) given the new best actions (computed by the Policy improvement)\n",
    "\n",
    "    Args:\n",
    "        pi (array): numpy array representing the policy\n",
    "        current_state (int): Current state s_t of agent\n",
    "        best_actions (list): list with best actions\n",
    "        actions (list): list of every possible action (given by board.actions)\n",
    "    \"\"\"\n",
    "\n",
    "    possible_actions = action_function(current_state)\n",
    "\n",
    "    for a in possible_actions:\n",
    "        for (s_next,proba) in state_transition_function(s, a, p):\n",
    "            pi[current_state][a] = proba if a in best_actions else 0\n",
    "\n",
    "    return pi[current_state]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def bellman_update(actions, V, old_v, state, pi, gamma,p):\n",
    "    \"\"\"\n",
    "    Applies the Bellman update rule to the value function.\n",
    "\n",
    "    Args:\n",
    "        - actions (array): array of actions\n",
    "        - V (array): numpy array representing the value function\n",
    "        - old_v (array): numpy array representing the value function on the last iteration\n",
    "        - state (int):  current state\n",
    "        - pi (array):  array of current optimal policy\n",
    "        - gamma (float): gamma parameter (between 0 and 1)\n",
    "    \"\"\"\n",
    "\n",
    "    val = 0\n",
    "    for a in actions:\n",
    "        for (s_next, transition_probability) in state_transition_function(state, a, p):\n",
    "            reward = reward_function(state, a)  # Get direct reward\n",
    "            print(f\"Next state:{s_next} | reward: {reward} | old_v[s_next] {old_v[s_next]}\")\n",
    "            val += pi[state][a] * (reward + (gamma * old_v[s_next]))\n",
    "\n",
    "    # UPDATE OF the VALUE function\n",
    "    V[state] = val\n",
    "    return V"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "def policy_evaluation(states,actions, V, pi, gamma, theta,p):\n",
    "    \"\"\"\n",
    "    Applies the policy evaluation algorithm.\n",
    "\n",
    "    Args:\n",
    "        states (array): array of states\n",
    "        actions (array): array of actions\n",
    "        V (array): numpy array representing the value function\n",
    "        pi (array): numpy array representing the policy\n",
    "        gamma (float): gamma parameter (between 0 and 1)\n",
    "        theta (float): threshold parameter that defines when the change in the value function is negligible\n",
    "    \"\"\"\n",
    "\n",
    "    delta = theta + 1\n",
    "    iter = 0\n",
    "\n",
    "    print(f\"Delta: {delta} | Theta: {theta}\")\n",
    "    \n",
    "    while delta >= theta:\n",
    "        old_v = V.copy()\n",
    "        delta = 0\n",
    "\n",
    "        # Iterate all states\n",
    "        for state in states:  # [1,...,10]\n",
    "            # Run one iteration of the Bellman update rule for the value function\n",
    "            V = bellman_update(actions, V, old_v, state, pi, gamma,p)\n",
    "            # Compute difference for EACH STATE, and take the maximum difference\n",
    "            delta = max(delta, abs(old_v[state] - V[state]))\n",
    "        iter += 1\n",
    "\n",
    "    print(\n",
    "        f\"\\nValue function updated: the Policy Evaluation algorithm converged after {iter} sweeps\"\n",
    "    )\n",
    "\n",
    "    return V"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "def policy_improvement(states,actions,V, pi, gamma,p):\n",
    "    \"\"\"\n",
    "    Applies the Policy Improvement step.\n",
    "\n",
    "    Args:\n",
    "        board (Environment): gridworld environment\n",
    "        v (array): numpy array representing the value function\n",
    "        pi (array): numpy array representing the policy\n",
    "        gamma (float): gamma parameter (between 0 and 1)\n",
    "    \"\"\"\n",
    "    policy_stable = True\n",
    "\n",
    "    # Iterate all states\n",
    "    for s in states:  # [1,...,10]\n",
    "        old_pi = pi[s].copy()\n",
    "\n",
    "        # Instanciate best actions list & best action val\n",
    "        best_actions = []\n",
    "        max_action_val = None\n",
    "\n",
    "        ############ COMPUTE the ACTION-value function Q_𝜋(s,a) for each action ############\n",
    "        for a in actions:\n",
    "            curr_action_value = 0.0\n",
    "            # Bellman update\n",
    "            for (s_next, transition_probability) in state_transition_function(s, a, p):\n",
    "                reward = reward_function(s, a)  # Get direct reward\n",
    "                curr_action_value += transition_probability * (reward+ (gamma* V[s_next]))\n",
    "\n",
    "            if max_action_val is None:  # If no best action, add this one\n",
    "                max_action_val = curr_action_value\n",
    "                best_actions.append(a)\n",
    "            elif (\n",
    "                curr_action_value > max_action_val\n",
    "            ):  # If better than precedent action, replace\n",
    "                max_action_val = curr_action_value\n",
    "                best_actions = [a]\n",
    "            elif (\n",
    "                curr_action_value == max_action_val\n",
    "            ):  # If the Action-value for this specific actions equals another Action-value of another action, both deserve to be taken\n",
    "                best_actions.append(a)\n",
    "\n",
    "        # Define new policy pi(a|s) with the following variables\n",
    "        # - pi: current policy, will be updated by new_policy\n",
    "        # - current_state: state for which the policy should be updated\n",
    "        # - new_policy: best actions to take for this specific state\n",
    "        # - actions: all set of actions\n",
    "        \n",
    "        pi[s] = improve_policy(\n",
    "            pi, s, best_actions, p\n",
    "        )\n",
    "\n",
    "        # Check whether the policy has changed\n",
    "        if (old_pi == pi[s]):\n",
    "            policy_stable = True\n",
    "\n",
    "    if not policy_stable:\n",
    "        print(f\"\\nPolicy improved for all states.\")\n",
    "    else:\n",
    "        # Refresh the display\n",
    "        print(f\"\\nPolicy is now STABLE !\")\n",
    "\n",
    "    return policy_stable"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "def policy_iteration(V,pi,states,actions,gamma,theta,p):\n",
    "    \"\"\"\n",
    "    Runs the Policy Iteration algorithm:\n",
    "        - Policy Evaluation\n",
    "        - Policy Improvement\n",
    "\n",
    "    Args:\n",
    "        env (Environment): Environment class\n",
    "        v0_val (int): initial value for the value function\n",
    "        gamma (float): gamma parameter (between 0 and 1)\n",
    "        theta (float): threshold parameter that defines when the change in the value function is negligible (i.e. when we can stop process)\n",
    "        seed (int): seed (for matter of reproducible results)\n",
    "    \"\"\"\n",
    "    timesteps = 0\n",
    "\n",
    "    # Initialize policy as a NOT STABLE one\n",
    "    policy_stable = False\n",
    "\n",
    "    while True:\n",
    "        if not policy_stable:\n",
    "            timesteps += 1\n",
    "            print(f\"\\nIteration {timesteps} of Policy Iteration algorithm\")\n",
    "\n",
    "            # ============== Policy Evaluation Step ============== #\n",
    "            print(\"# ============== Policy Evaluation Step ============== #\")\n",
    "            V = policy_evaluation(states,actions, V, pi, gamma, theta)\n",
    "\n",
    "            # ============== Policy Improvement Step ============== #\n",
    "            print(\"# ============== Policy Improvement Step ============== #\")\n",
    "            policy_stable = policy_improvement(states,actions,V, pi, gamma,p)\n",
    "\n",
    "            print(\n",
    "                f\"\\The whole Policy Iteration (eval -> improvement -> eval -> ...) algorithm converged after {timesteps} steps\"\n",
    "            )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "policy_iteration(V,pi,S,actions,gamma,theta,p)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Conclusion"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We tried to implement this time the **Policy Iteration Algorithm**, however it seems that our algo runs indefinitely trying to make the *policy evaluation* converge to a treshold it cannot reach..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 4. Varying parameters"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To test the sensitivity of the optimal policies to different problem parameters, we can vary the values of $p$ and $c$ in the **Value Iteration Algorithm** and observe how the resulting policies and value functions change.  \n",
    "- For example, if we increase the probability $p$ of transitioning to a higher efficiency state, we expect the optimal policy to become **more aggressive** (i.e. more likely to replace the machinery) since the machinery will go to higher states and be used **faster**.\n",
    "- Similarly, if we increase the cost $c$ of replacing the machinery, we expect the optimal policy to become **more conservatibe** (i.e. less likely to replace the machinery) since the cost of replacing the machinery will become higher."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- $p = 0.3$ | $c = 500$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "|State| $V^*$| $\\pi^*$  |\n",
    "|---|---|---------------|\n",
    "| 1 |  12589.88 |Optimal policy $\\pi^*$ for state 1: keep  \n",
    "| 2  |  12577.65 |Optimal policy $\\pi^*$ for state 2: keep  \n",
    "| 3  |  12486.37 |Optimal policy $\\pi^*$ for state 3: keep  \n",
    "| 4  |  12375.13 |Optimal policy $\\pi^*$ for state 4: keep  \n",
    "|  5 | 12218.39|Optimal policy $\\pi^*$ for state 5: replace  \n",
    "|  6 |  12120.89  |Optimal policy $\\pi^*$ for state 6: replace  \n",
    "|  7 |  11978.39 |Optimal policy $\\pi^*$ for state 7: replace  \n",
    "|  8 |  11790.89 |Optimal policy $\\pi^*$ for state 8: replace  \n",
    "| 9  |  11558.39 |Optimal policy $\\pi^*$ for state 9: replace   \n",
    "| 10  | 11280.89  |Optimal policy $\\pi^*$ for state 10: replace|\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- $p = 0.9$ | $c = 3000$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "|State| $V^*$| $\\pi^*$  |\n",
    "|---|---|---------------|\n",
    "| 1 |  10390.13 |Optimal policy $\\pi^*$ for state 1: keep  \n",
    "| 2  |  10109.16 |Optimal policy $\\pi^*$ for state 2: keep  \n",
    "| 3  |  9713.43 |Optimal policy $\\pi^*$ for state 3: keep  \n",
    "| 4  |  9236.49 |Optimal policy $\\pi^*$ for state 4: keep  \n",
    "|  5 |  8715.26 |Optimal policy $\\pi^*$ for state 5: keep  \n",
    "|  6 |  8190.33 |Optimal policy $\\pi^*$ for state 6: keep  \n",
    "|  7 |  7706.58 |Optimal policy $\\pi^*$ for state 7: keep  \n",
    "|  8 |  7311.12 |Optimal policy $\\pi^*$ for state 8: replace  \n",
    "| 9  |  7078.62 |Optimal policy $\\pi^*$ for state 9: replace   \n",
    "| 10  | 6801.12  |Optimal policy $\\pi^*$ for state 10: replace|"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3.8.5 64-bit",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.5 (default, Jul 21 2020, 10:48:26) \n[Clang 11.0.3 (clang-1103.0.32.62)]"
  },
  "orig_nbformat": 4,
  "vscode": {
   "interpreter": {
    "hash": "aee8b7b246df8f9039afb4144a1f6fd8d2ca17a180786b69acc140d282b71a49"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}