{"cells":[{"cell_type":"markdown","id":"f06db25c-558f-4da6-8025-f6ae472d1f3d","metadata":{},"source":"Monte Carlo for Frozen Lake\n===========================\n\n**Author:** Joseph Le Roux\n\n**Date:** 2026-07-19\n\n"},{"cell_type":"markdown","id":"d72b3ee8-39f1-42e2-8208-f1a0947f691d","metadata":{},"source":["- AUTHOR: Joseph Le Roux\n","- DATE: 2026-07-19\n","- DESCRIPTION: Monte Carlo for Frozen Lake\n"]},{"cell_type":"markdown","id":"02bf8695-3416-41b2-94ba-94185bfe57f6","metadata":{},"source":["## Imports\n\n"]},{"cell_type":"code","execution_count":1,"id":"2ebb646e-6b02-4f52-bb77-5716e239e578","metadata":{},"outputs":[],"source":["# gym contains the RL problem interface through environment\nimport gymnasium as gym\n# for math on GPU + autodiff (for neural networks)\nimport torch"]},{"cell_type":"markdown","id":"1944a5bd-6c28-48f5-b31b-a79f47fe344a","metadata":{},"source":["## Computing the Optimal Policy\n\n"]},{"cell_type":"markdown","id":"1799289b-29c5-4905-8ff1-c24e53e3bc42","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**, and that computes **trials** trajectories from the MDP dynamics and the **policy** to choose the action to perform at each time step **t**.\n\n**evaluate** computes the average number of successes and the average length of trajectories that end at G.\n\n"]},{"cell_type":"code","execution_count":1,"id":"947fbe10-0abe-4e08-bf11-5dbdb97de648","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  fails = []\n\n  for trial in range(trials):\n    obs, _ = env.reset()\n\n    terminated, truncated = False, False\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        env.render()\n      length += 1\n\n      if terminated:\n        if reward == 1:\n          success += 1\n          lengths.append(length)\n      if truncated or (terminated and reward == 0):\n          fails.append(length)\n\n  lengths = torch.tensor(lengths if len(lengths) > 0 else [0], dtype=torch.float)\n  fails = torch.tensor(fails, dtype=torch.float)\n\n  print('----------------------------------------------')\n  print('You retrieved the frisbee {:.2f}% of the time'.format((success/trials) * 100))\n\n  print('On average you need {:.0f} moves to reach the frisbee'.format(torch.mean(lengths)))\n  print('The shortest solution found requires {:.0f} moves to reach the frisbee'.format(torch.min(lengths)))\n  print('The longest solution found requires {:.0f} moves to reach the frisbee'.format(torch.max(lengths)))\n\n  print('The shortest failure requires {:.0f} moves'.format(torch.min(fails)))\n  print('The longest failure requires {:.0f} moves'.format(torch.max(fails)))\n\n  print('----------------------------------------------')"]},{"cell_type":"code","execution_count":1,"id":"96d5175d-dcf7-4a82-85ac-00e5e2c2a05b","metadata":{},"outputs":[],"source":["env = gym.make('FrozenLake-v1', map_name='8x8', render_mode='ansi')\nevaluate(env)"]},{"cell_type":"code","execution_count":1,"id":"ebe13189-47e6-4787-8fa1-5b93c731a165","metadata":{},"outputs":[],"source":["# To visualize a trial:\n# evaluate(env, trials=1, render=True)"]},{"cell_type":"markdown","id":"8891f58e-6868-4277-8adf-1b6a186eb1a3","metadata":{},"source":["## Finding the Optimal Policy by Simulation\n\n"]},{"cell_type":"markdown","id":"8430c133-a353-44fb-b643-32a97b4296d5","metadata":{},"source":["In this section, you are asked to implement the Monte-Carlo method to compute the optimal policy via action values $Q$ seen in class\n\n"]},{"cell_type":"code","execution_count":1,"id":"033eb82f-8414-4dca-a3ef-1948cc922960","metadata":{},"outputs":[],"source":["class MonteCarlo:\n  def __init__(self, env):\n    self.reset(env)\n\n  def reset(self, env):\n    # use torch to create\n    # an array (deterministic policy)\n    self.pi = torch.zeros(env.observation_space.n, dtype=torch.long)\n    # a matrix for action values q(state, action)\n    self.Q = torch.ones((env.observation_space.n, env.action_space.n), dtype=torch.float)\n\n  # sample an action according to an epsilon-greedy policy\n  def epsilon_greedy_action(self, env, state, epsilon):\n    # your code here\n    pass  # remove\n\n  def compute_policy(self, env, nb_exp=100000, gamma=0.99, base_epsilon=0.8):\n    final_rewards = 0\n    epsilon = base_epsilon\n\n    # 1/alpha_k for each pair state/action\n    nb_updates = torch.zeros_like(self.Q)\n\n    for m in range(nb_exp):\n      # generate an episode\n      # 0. initialize data\n\n      # your code\n\n      # 1. initial state\n      obs, _ = env.reset()\n\n      # 2. generate and collect trajectory\n      while not (terminated or truncated):\n        pass  # remove\n        # your code\n\n      final_rewards += reward\n      # 3. compute returns for the trajectory\n      # your code\n\n      # 4. update Q according to 'first visit' algorithm\n      # your code\n\n      # 5. update pi: greedy version of Q\n      # for each state, take the highest-scoring action\n      # your code\n\n      # 6. display some information\n      if (m+1) % 1000 == 0:\n        # average all rewards from the beginning\n        avg = final_rewards/(m+1)\n        print(m+1, avg, epsilon)\n\n      # update epsilon\n      if epsilon > 0:\n        epsilon -= base_epsilon / nb_exp\n\n  def __getitem__(self, state):\n    return self.pi[state].item()"]},{"cell_type":"code","execution_count":1,"id":"c5dd9e40-b362-4ba5-b339-649b1e9f8c7c","metadata":{},"outputs":[],"source":["env = gym.make('FrozenLake-v1', map_name='8x8', render_mode='ansi')\nvi = MonteCarlo(env)\nenv.reset()\nvi.compute_policy(env, nb_exp=10000, base_epsilon=0.8)  # increase nb_exp if necessary\nevaluate(env, vi)"]},{"cell_type":"markdown","id":"7f30b066-357f-4ecd-a6d1-251cd3b9894f","metadata":{},"source":["## Bonus\n\n"]},{"cell_type":"markdown","id":"ead895d5-bb39-45d9-95ac-5699398a48ec","metadata":{},"source":["1.  Implement the softmax policy instead of the $&epsilon;$-greedy policy. Modify the parameters of **compute<sub>policy</sub>** to be able to choose the policy during Monte-Carlo simulation. (to sample from the softmax distribution, there are several methods, for example via the **Categorical** class in [https://pytorch.org/docs/stable/distributions.html](https://pytorch.org/docs/stable/distributions.html))\n2.  Implement an $&epsilon;$-softmax-greedy policy:\n    -   randomly draw a real number $r$ between 0 and 1;\n    -   if $r$ is greater than $\\epsilon$ take the highest-scoring action;\n    -   otherwise randomly draw according to the softmax method\n\nThis last method should allow you to recover the success scores from the previous TP (with many examples nonetheless&hellip;)\n\n"]},{"cell_type":"markdown","id":"97a64a21-78bc-4f36-b903-ee4ea0dfa304","metadata":{},"source":["### Bonus within the bonus: temporal difference methods\n\n"]},{"cell_type":"markdown","id":"f9dd1eb9-5a98-4ddc-b18d-d0c3008c7572","metadata":{},"source":["Using the structure of the previous class, implement a **Sarsa** class that defines a **compute<sub>policy</sub>** method that implements the SARSA algorithm seen in class.\n\nWe can go even further and define the classes for **Expected SARSA** and **Q-learning**.\n\n"]}],"metadata":{"org":{"AUTHOR":"Joseph Le Roux","DATE":"2026-07-19","DESCRIPTION":"Monte Carlo for 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}