MDP Value Iteration and Policy Iteration

Question

# Frozen Lake MDP Assignment

## Introduction

This exercise provides you with a simple Frozen Lake environment that models a Markov Decision Process (MDP).  
Your task is to implement two classical algorithms to solve it:

1. **Value Iteration**
2. **Policy Iteration**

Both algorithms should find the optimal policy and value function that maximize the expected reward for the agent.

---

## The Frozen Lake Environment

The environment is a 4×4 grid world defined as follows:

S F F F  
F H F H  
F F F H  
H F F G

Legend:
- S: Start (safe)
- F: Frozen surface (safe)
- H: Hole (terminal failure)
- G: Goal (terminal success)

Actions: 0 = Left, 1 = Down, 2 = Right, 3 = Up  
Reward: +1 for reaching G, 0 otherwise.  
If `is_slippery=True`, the agent’s intended action may fail with some probability.

---

## Provided Environment Code

Use the following code to create your environment.  
You do **not** need Gym or Gymnasium — this class is standalone.

```python
import numpy as np
import random
from typing import Optional, Tuple, List, Dict

class FrozenLakeEnv:
    """
    A lightweight re-implementation of FrozenLake-v1 supporting:
      • map_name or custom desc
      • is_slippery

Accepted Answer

A detailed reference solution is available to Crack ML Interview members.