{"cells":[{"cell_type":"markdown","id":"d49ed506-9f31-40eb-8357-da563930a689","metadata":{},"source":"MDP: Frozen Lake\n================\n\n**Author:** Joseph Le Roux\n\n**Date:** 2026-07-19\n\n"},{"cell_type":"markdown","id":"99ba5812-e3cd-476c-9f50-75acfeeee9b4","metadata":{},"source":["- AUTHOR: Joseph Le Roux\n","- DATE: 2026-07-19\n","- DESCRIPTION: MDP Frozen Lake\n"]},{"cell_type":"markdown","id":"30d3c7a8-92b4-43fd-b5bb-c0c93eaac92e","metadata":{},"source":["## Understanding the Problem\n\n"]},{"cell_type":"markdown","id":"d6d4213f-924f-463f-8def-a655d2b94d62","metadata":{},"source":["### Exercise 1\n\n"]},{"cell_type":"markdown","id":"65364a65-6ec0-4541-98d9-e71d4dc94413","metadata":{},"source":["In this exercise, you are asked to provide the probabilities of transitions $T(s,a,s')= P(S_{t+1}=s' | S_t=s, A_t=a)$.\nThe MDP dynamics are described in the lab assignment.\n\n-   The first student in the pair must find:\n    \n    Based on the MDP definition given in the tutorial, provide the following values for the transition function:\n    \n    -   $\\forall s'\\ T(0,0,s')$ , i.e., all transition values from the initial state when performing action 0 (left) for all states (only list non-zero transition values)\n    \n    -   $\\forall s'\\ T(9,a,s')$ , i.e., all transition values from state 9 when performing action $a$ for all states (only list non-zero transition values)\n    \n    -   $\\forall s'\\ T(62,a,s')$ , i.e., all transition values from state 62 when performing action $a$ for all states (only list non-zero transition values)\n\n-   The second student in the pair must find:\n    \n    Based on the MDP definition given in the tutorial, provide the following values for the transition function:\n    \n    -   $\\forall s'\\ T(7,0,s')$ , i.e., all transition values from the top-right state when performing action 0 (left) for all states (only list non-zero transition values)\n    \n    -   $\\forall s'\\ T(11,a,s')$ , i.e., all transition values from state 11 when performing action $a$ for all states (only list non-zero transition values)\n    \n    -   $\\forall s'\\ T(55,a,s')$ , i.e., all transition values from state 55 when performing action $a$ for all states (only list non-zero transition values)\n\n"]},{"cell_type":"markdown","id":"ca968f8e-c540-4e73-8004-fed3f73b4b99","metadata":{},"source":["### Answers\n\n"]},{"cell_type":"markdown","id":"8402a06a-420d-4d48-b75e-b58dd306dcff","metadata":{},"source":["**Write your answers here** (you can verify your answers in the dynamics question later in the assignment)\n\n"]},{"cell_type":"markdown","id":"2fad5d2e-0bfc-4181-a17b-7f71e0f3725a","metadata":{},"source":["## Let Me Code Now!\n\n"]},{"cell_type":"code","execution_count":1,"id":"4fdbd00a-66a9-4e15-9f19-1fd56bec5ecb","metadata":{},"outputs":[],"source":["# gym contains the RL problem interface through environment\nimport gymnasium as gym\n# for vector/matrix/tensor data\nimport torch as t\n\nimport random"]},{"cell_type":"markdown","id":"21266e73-133e-497a-b973-8ac0dad95151","metadata":{},"source":["We create an environment object using the `gym.make` function\n\n"]},{"cell_type":"code","execution_count":1,"id":"2fbbfd14-a489-4a29-99e7-c13ccdb1cc82","metadata":{},"outputs":[],"source":["# load the frozen lake problem\nenv = gym.make('FrozenLake-v1', map_name='8x8', render_mode='ansi')"]},{"cell_type":"markdown","id":"aa8bf623-3ffc-48fe-b696-1d1b26ef86c4","metadata":{},"source":["On the environment object, we can perform several operations. Here we initialize it (via reset) and display it (via render).\n\nNote that the current position is indicated by a different color\n\n"]},{"cell_type":"code","execution_count":1,"id":"bbeeef4b-a59d-414e-86eb-4174fff3c7b3","metadata":{},"outputs":[],"source":["env.reset()\nprint(env) #the environment is wrapped to add more features\nprint(env.unwrapped) # access the real (underlying) environment\nprint(env.render())"]},{"cell_type":"markdown","id":"fc0d0737-f3fa-4654-a2ee-4ae50fb6b744","metadata":{},"source":["The `env` structure has two attributes to define states and actions:\n\n1.  `observation_space`\n2.  `action_space`\n\n"]},{"cell_type":"code","execution_count":1,"id":"210c9d40-e153-4796-bba2-65c4369d4135","metadata":{},"outputs":[],"source":["print(type(env.action_space))\nprint(env.action_space.n)\n\nprint(type(env.observation_space))\nprint(env.observation_space.n)"]},{"cell_type":"markdown","id":"fa424627-eada-40c2-a1e6-3fa652aa043d","metadata":{},"source":["We can choose an action randomly using the **sample** function. To perform an action, we call **step**. In the following example, we randomly choose an action and apply it to the current state of the environment.\n\nNB: the **step** function returns a tuple $(o,r,f,h,i)$ where $o$ is the new state, $r$ is the reward for reaching $o$, $f$ is a boolean indicating if $o$ is terminal, $h$ is a boolean indicating the horizon has been reached, and $i$ is debug information (which we will ignore for these labs).\n\nRun the following block several times and try to understand what happens:\n\n"]},{"cell_type":"code","execution_count":1,"id":"a07492c0-4817-458b-98a9-d20077cc2207","metadata":{},"outputs":[],"source":["action = env.action_space.sample()\nprint(action)\nres = env.step(action)\nprint(\"result:\", res)\nprint(env.render())"]},{"cell_type":"markdown","id":"33eb8fde-29ca-428f-9f2c-738b21db10ed","metadata":{},"source":["### Dynamics and Rewards\n\n"]},{"cell_type":"markdown","id":"555be100-52b1-4f43-8dd2-1c0dd0fb9576","metadata":{},"source":["In this environment, the dynamics are known and stored in a specific data structure `TableTransition`.\n\nA `TableTransition` is a table `State` $\\to$ `TableState` that maps each of the 64 states of the environment to the corresponding outgoing transitions table.\n\nA `TableState` is a table `Action` $\\to$ `List(Arrival)` that associates to each possible action the displacements that can be performed.\n\nWe call `Arrival` tuples of the form $(p,d,r,f)$ where $p$ is a probability, $d$ is an arrival state, $r$ is a reward for reaching $d$, and $f$ is a boolean indicating if state $d$ is terminal.\n\n"]},{"cell_type":"code","execution_count":1,"id":"f7b1bc10-207a-4a79-8ce7-18008403d0a1","metadata":{},"outputs":[],"source":["print(env.unwrapped.P)"]},{"cell_type":"markdown","id":"f0384b5f-6ed9-4359-9e7b-d4d84ed2ca02","metadata":{},"source":["### Exercise 2\n\n"]},{"cell_type":"markdown","id":"30f7207d-6fdf-4c57-a31d-c0ad21672514","metadata":{},"source":["From the structure displayed above, copy the `TableStates` for the transitions in Exercise 1\n\n"]},{"cell_type":"code","execution_count":1,"id":"98d1bd6f-bb5b-4f15-8b67-43236d8c52f5","metadata":{},"outputs":[],"source":["#your answer here"]},{"cell_type":"markdown","id":"99c2dabf-83f8-406b-8f78-a7226207a7da","metadata":{},"source":["## Finding the Optimal Policy\n\n"]},{"cell_type":"markdown","id":"157dcb27-50ad-4d0a-9cec-e83d91eb2661","metadata":{},"source":["### Computing the Optimal Policy\n\n"]},{"cell_type":"markdown","id":"42862273-8888-4cc0-a0d1-08920612698b","metadata":{},"source":["We start by defining an **evaluate** function that takes as input an environment **env**, a policy **policy**, and a number of trials to perform **trials**. It computes **trials** trajectories from the MDP dynamics and the **policy** to choose the action to perform at each time **t**.\n\nIf the **policy** argument is **None**, actions are chosen randomly.\n\n**evaluate** computes the average success rate and average trajectory length for trajectories that end in G.\n\n"]},{"cell_type":"code","execution_count":1,"id":"99df44a6-f3b7-4634-b29c-525b9e27eb2e","metadata":{},"outputs":[],"source":["#set \"render\" to \"True\" to display intermediate boards\n\ndef evaluate(env, policy = None, trials=1000, render=False):\n\n  success = 0\n  lengths = []\n\n  for trial in range(trials):\n    obs,_ = env.reset()\n\n    terminated = False\n    truncated = False\n\n    if render:\n      env.render()\n    length = 0\n\n    while not (terminated or truncated):\n      action = env.action_space.sample() if policy is None else policy[obs]\n      obs,reward, terminated, truncated, _ = env.step(action)\n      if render:\n        print(env.render())\n      length +=1\n\n      if terminated:\n        if reward == 1:\n          success +=1\n          lengths.append(length)\n\n  print('----------------------------------------------')\n  print('You retrieved the frisbee {:.2f}% of the time'.format((success/trials) * 100))\n  print('On average it takes you {:.0f} moves to reach the frisbee'.format(t.mean(t.tensor(lengths, dtype=t.float))))\n  print('----------------------------------------------')"]},{"cell_type":"code","execution_count":1,"id":"36d309c3-8345-48cf-a925-3f539d5d85f9","metadata":{},"outputs":[],"source":["env = gym.make('FrozenLake-v1', map_name='8x8', render_mode='ansi')\nevaluate(env)"]},{"cell_type":"markdown","id":"5b6a634a-eef6-4850-ae1a-5f2d43375b5c","metadata":{},"source":["### Improving the Action Policy\n\n"]},{"cell_type":"markdown","id":"8ce0a5b2-b46a-4676-99f7-485502e8a9a2","metadata":{},"source":["In this section, we will implement the algorithms seen in class: **policy iteration** and **value iteration**.\n\nIn both cases, this implementation will take the form of a Python class with a **get<sub>policy</sub>** method that takes a state number and returns the action to follow according to a deterministic policy.\n\n"]},{"cell_type":"markdown","id":"55900ace-caf5-45cb-b60f-caef0610f47f","metadata":{},"source":["### Policy Iteration Algorithm\n\n"]},{"cell_type":"code","execution_count":1,"id":"ec6b9989-922c-4f19-bc43-0ab732e39178","metadata":{},"outputs":[],"source":["class PolicyIteration:\n  def __init__(self, env):\n\n    self.pi = t.zeros(env.observation_space.n, dtype=t.long)\n    self.values = t.zeros(env.observation_space.n)\n\n    # transition T(s,a,s')\n    self.transitions = t.zeros((env.observation_space.n,env.action_space.n,env.observation_space.n))\n\n    # reward R(s,a,s')\n    self.rewards = t.zeros((env.observation_space.n,env.action_space.n,env.observation_space.n))\n\n    # Init transitions and rewards (ok to loop here)\n    ### your code begins here\n\n    ### your code ends here\n\n  # the python equivalent for C++ [] operator\n  # here we return the policy for the state parameter converted to an integer\n  def __getitem__(self, state):\n    return self.pi[state].item()\n\n  # reset policy and values\n  def reset(self, env):\n    self.pi = t.zeros_like(self.pi)\n    self.values = t.zeros_like(self.values)\n\n    self.transitions = t.zeros_like(self.transitions)\n    self.rewards = t.zeros_like(self.rewards)\n\n    # Re-init transitions and rewards (ok to loop here)\n    ### your code begins here\n\n    ### your code ends here\n\n  # compute V according to a policy\n  def policy_evaluation(self, env, maxit, theta, gamma):\n    done = False\n    i = 0\n\n    ## you can init things here if needed, for instance:\n    transitions = t.zeros((64,64))\n    rewards = t.zeros((64,64))\n\n    while not done:\n      delta = 0.0\n      i += 1\n\n      ### your code begins here\n\n      ### your code ends here\n\n      done = (i >= maxit) or (delta < theta)\n\n  # compute a new (better) policy consistent with V\n  def policy_improvement(self, env, gamma):\n    stable = True\n\n    ### your code begins here\n\n    ### your code ends here\n\n    return stable\n\n  # performs the 2-step loop\n  # 1. compute V from pi iteratively\n  # 2. compute pi from V\n  def compute_policy(self, env, max_iteration=1e20, theta=1e-20, gamma=0.9):\n    self.reset(env)\n    done = False\n    i = 0\n\n    while not done:\n      i += 1\n      self.policy_evaluation(env, max_iteration, theta, gamma)\n\n      done = self.policy_improvement(env, gamma) or i >= max_iteration"]},{"cell_type":"code","execution_count":1,"id":"456e8f37-5426-468a-80c9-0dd880e936e1","metadata":{},"outputs":[],"source":["env = gym.make('FrozenLake-v1', map_name='8x8', is_slippery=False, render_mode='ansi', new_step_api=True) # is_slippery=False => the lake does not slip, the requested direction is the direction obtained\npi = PolicyIteration(env)\nenv.reset()\n\npi.compute_policy(env)\nevaluate(env, pi)\n\nprint(pi.values.view(8,8))\nprint(pi.pi.view(8,8))\n\n# If your implementation is successful, you should achieve over 100% success rate and find the shortest path between S and G"]},{"cell_type":"code","execution_count":1,"id":"b2c165ba-470b-453f-ab96-db18467e12bb","metadata":{},"outputs":[],"source":["env = gym.make('FrozenLake-v1', map_name='8x8', is_slippery=True, render_mode='ansi', new_step_api=True)\npi = PolicyIteration(env)\nenv.reset()\n\npi.compute_policy(env)\nevaluate(env, pi)\n\nprint(pi.values.view(8,8))\nprint(pi.pi.view(8,8))\n\n# If your implementation is successful, you should achieve over 55% success rate"]},{"cell_type":"code","execution_count":1,"id":"21a17ec0-62c7-4bbe-ac7b-d784d033fb0a","metadata":{},"outputs":[],"source":["# To visualize one trial after computing the optimal policy:\nenv.reset()\nevaluate(env, pi, trials=1, render=True)"]},{"cell_type":"markdown","id":"67b47707-dab1-4cf7-a8e2-fdd81eff59eb","metadata":{},"source":["### But Why?\n\n"]},{"cell_type":"markdown","id":"09170647-d348-45be-a054-6041e998ca56","metadata":{},"source":["Your instructor decides to change the discount factor ($\\gamma$) to 1 (no devaluation of future rewards).\nHe relaunches the policy iteration algorithm but the success rate drops from 58% to 0%!\n\nHelp your instructor understand why.\n\n*Your answer here&#x2026;*\n\n"]},{"cell_type":"markdown","id":"eed4b051-2b2a-438f-ae77-693bb529eba1","metadata":{},"source":["## Bonus: Value Iteration\n\n"]},{"cell_type":"markdown","id":"04c5e1d4-ac47-4c9c-b2ab-66f2f3eeef50","metadata":{},"source":["Implement the value iteration algorithm.\nInstead of computing state values with the current policy, we compute them with the greedy policy (taking only the action that yields the most).\nOnly a single policy update is necessary.\n\n"]},{"cell_type":"code","execution_count":1,"id":"4d9f3336-95f0-4d69-b427-58e6a06c9591","metadata":{},"outputs":[],"source":["class ValueIteration:\n  def __init__(self, env):\n\n    self.pi = t.zeros(env.observation_space.n, dtype=t.long)\n    self.values = t.zeros(env.observation_space.n)\n\n    self.transitions = t.zeros((env.observation_space.n,env.action_space.n,env.observation_space.n))\n    self.rewards = t.zeros((env.observation_space.n,env.action_space.n,env.observation_space.n))\n\n    # same init as before\n    # Init transitions and rewards (ok to loop here)\n    ### your code begins here\n\n    ### your code ends here\n\n  def reset(self, env):\n    self.pi = t.zeros_like(self.pi)\n    self.values = t.zeros_like(self.values)\n\n    self.transitions = t.zeros_like(self.transitions)\n    self.rewards = t.zeros_like(self.rewards)\n\n  def __getitem__(self, state):\n    return self.pi[state].item()\n\n  def value_iteration(self, env, maxit, theta, gamma):\n    done = False\n    i = 0\n    while not done:\n      delta = 0.0\n      i += 1\n\n      ### your code begins here\n\n      ### your code ends here\n      done = i >= maxit or delta < theta\n\n  def compute_policy(self, env, max_iteration=100000000, theta=1e-20, gamma=0.9):\n    self.value_iteration(env, max_iteration, theta, gamma)\n\n    # compute pi from V\n    ### your code begins here\n\n    ### your code ends here"]},{"cell_type":"code","execution_count":1,"id":"42578eb2-a281-435c-bbb0-888e4fa8da4b","metadata":{},"outputs":[],"source":["env = gym.make('FrozenLake-v1', map_name='8x8', render_mode='ansi', new_step_api=True)\nvi = ValueIteration(env)\nenv.reset()\nvi.compute_policy(env)\nevaluate(env, vi)\n\nprint(pi.values.view(8,8))\nprint(pi.pi.view(8,8))"]}],"metadata":{"org":{"AUTHOR":"Joseph Le Roux","DATE":"2026-07-19","DESCRIPTION":"MDP Frozen Lake"},"kernelspec":{"display_name":"Python 3","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.5.2"}},"nbformat":4,"nbformat_minor":5}