IMRL, LAB 2

Original English Version here

It's winter. You're playing frisbee with friends in the park when a bad throw causes the frisbee to land in the middle of the lake. The water is frozen over most of the surface, but there are a few holes where the ice has melted. If you find yourself above one of these holes, you'll fall into the icy water. Currently, there's a global frisbee shortage, so it's essential that you retrieve the frisbee from the lake and bring it back. Be careful, the ice is slippery, and you may not move in the direction you choose.

The lake is modeled as a graph, informally represented by an illustration as below:

SFFFFFFF
FFFFFFFF
FFFHFFFF
FFFFFHFF
FFFHFFFF
FHHFFFHF
FHFFHFHF
FFFHFFFG

Each letter corresponds to a vertex, and there is an edge between a vertex and each of its neighbors (up/down/left/right).

The letters indicate what each state contains:

S

your initial position on the frozen lake (start)

G

the position of the frisbee (goal)

F

the ground is frozen at this vertex (frozen)

H

there is a hole (hole)

The goal is to provide a sequence of actions to reach vertex G from your initial position S, while avoiding holes H. There are 4 possible actions (left/down/right/up) indicating which neighboring vertex you want to move to. Be careful: just because you decide to go in one direction doesn't mean you'll get there—you may slip and randomly end up on another neighboring vertex!

Recall that an MDP is a tuple \((S,A,H,T,R,\gamma)\) with

• \(S\) the set of states,
• \(A\) the set of actions,
• \(H\) the horizon,
• \(T\) the transition function (also called dynamics),
• \(R\) the reward function,
• \(\gamma\) the discount factor.

In our case, there will be:

• 64 states numbered 0 to 63 from left to right and top to bottom,
• 4 actions (requesting movement left/down/right/up) numbered 0 to 3
• \(H\) is infinite. The shortest action sequences from S to G are of length 14, but longer (and infinite) sequences exist.
• For transitions, we assume the dynamics are known and therefore we know the transition probabilities. In the OpenAI Gym implementation, the dynamics are defined as follows:
  • for vertices \(s\) labeled G or H:
    • you stay on \(s\) regardless of action, in other words
    • \(\forall a\in A,\quad T(s,a,s')=1\) if and only if \(s=s'\), \(T(s,a,s')=0\) otherwise;
  • for vertices \(s\) labeled S or F:
    • for any action \(a\), the result can equally likely be moving in direction \(a\) or direction \(a-1 \bmod 4\) or direction \(a+1 \bmod 4\);
    • if an action is "impossible", for example trying to move up from the initial state, it results in staying in the current state;
• the reward is 1 if in the state labeled G, and 0 otherwise.
• the discount factor is arbitrarily set to 0.9.

The Gymnasium site provides environment models for many robotics and reinforcement learning tasks. It is mainly used to test and compare new algorithms. The task of interest today is Frozen Lake.

Through the Python gym module, you can load these environments and create an agent that interacts with them.

The goal of this practical session is to create an agent for this environment and train it to learn a policy \(\pi\) using the two algorithms covered last time (policy iteration, value iteration) that allows the agent to reliably retrieve the frisbee.

1. Download the notebook here (right-click then save link to avoid encoding issues with USPN/LIPN pages)
2. Open a window in your browser on colab
3. Load the notebook (File → Open Notebook …)
4. Read/evaluate/complete the notebook
5. Save the notebook and download it (File → Download .ipynb)
6. Log in to the LMS and navigate to the robotics course page
7. Submit your notebook on the submission interface for the relevant week

You can install Jupyter Notebook on your personal computer and work locally. In that case, you'll need to ensure Jupyter and necessary libraries are installed.