RL-Maze.qmd

---
title: "Solving a Maze using Reinforcement Learning"
author: "Michael Hahsler"
format: 
  html: 
    theme: default
    toc: true
    number-sections: true
    code-line-numbers: true
    embed-resources: true
editor: visual
---

```{r, include = FALSE}
knitr::opts_chunk$set(
  collapse = TRUE,
  comment = "#>",
  warning = TRUE,
  animation.hook = knitr::hook_gifski
)
```

![CC BY-SA 4.0](https://licensebuttons.net/l/by-sa/3.0/88x31.png) This code is provided under [Creative Commons Attribution-ShareAlike 4.0 International (CC BY-SA 4.0) License.](https://creativecommons.org/licenses/by-sa/4.0/)

# Introduction

This report demonstrates how value iteration (model-based RL) and q-learning (model-free RL) solve a maze similar to the mazes we have used for tree search.

## Install and Load Package markovDP

Install the current development version of [markovDP](https://mhahsler.r-universe.dev/markovDP).

```{r}
if (!"markovDP" %in% rownames(installed.packages())) 
  install.packages('markovDP', repos = c(
    'https://mhahsler.r-universe.dev', 
    'https://cloud.r-project.org'))

library(markovDP)
```

## Read the Maze

Mazes are so called *gridworlds* where the agent moves around in a 2d environment composed out of tiles. The markovDP package already comes with the mazes we use in class.

```{r}
maze_dir <- system.file("mazes", package = "markovDP")
dir(maze_dir)

maze <- gw_read_maze(file.path(maze_dir, "L_maze.txt"))
maze
```

```{r}
#| fig-width: 8
#| fig-height: 8
gw_plot(maze)
```

The transition model is stored as a function.

```{r}
#| fig-width: 8
#| fig-height: 8
maze$transition_prob
gw_plot_transition_graph(maze)
```

The reward model

```{r}
maze$reward
```

The reward is a cost of 1 for each transition and a reward of +100 for reaching the goal state. The best solution will be the shortest path to the goal.

Remember that tree search starts with the start state and explores the space till it finds the goal state.

# Solve the Maze MDP as a Planning Agent

We solve the MDP directly using the problem description as a model for the environment. This approach would be used by a **planning agent** similar to the tree search algorithms like A\* search. Since the agent uses a complete model of the environment, we use a **model-based reinforcement learning** algorithm.

Here we use the dynamic programming method called value iteration (VI). The algorithm sweeps in each iteration through all states and updates each state value (called the value function) using the utility of the best state it could get to plus the immediate reward. It stops when the state values do not change anymore (less than a set error threshold).

```{r}
#| fig-width: 8
#| fig-height: 8
system.time(sol <- solve_MDP(maze, method = "DP:VI"))

sol

gw_plot(sol)
gw_path(sol)
```

The color represents the state value. Here are the learned state values and the optimal action for each state (policy).

```{r}
policy(sol)
```

Solve the maze step-by-step.

```{r}
#| fig-width: 8
#| fig-height: 8
gw_animate(maze, "DP:VI", n = 25, zlim = c(70,100))
```

Value iteration looks a lot like the following algorithms:

-   [flood fill](https://en.wikipedia.org/wiki/Flood_fill) algorithm.
-   breath-first search starting at the goal.

While the algorithm exhibits breath-first search behavior, it does not implement an explicit search tree. The search graph is implicitly stored in the transition model and the table representing the utility function. Exploration is replaced by propagating utility values. The tabular version of dynamic programming-based planning algorithms stores the value function as a table with $O(|S|)$ entries, one value for each state. The number of states is typically too large to fit into memory. An option is to use function approximation (e.g., using a machine learning model) to store only a compressed table.

The goal is to find the **optimal state value for each state.** An alternative approach is called policy iteration that searches for the best policy instead of the best value function.

# Reinforcement Learning for Unknown Mazes

An **unknown environment** mean that we do not have a model of the environment. That is, the agent does not know the transition function or the reward structure and has to learn a good policy and at least part of the transition and reward models by trying actions.

Here we assume that the agent has no direct access to the MDP. The agent can only try actions and the environment uses the MDP to simulate how it reacts. Methods to solve this problem are called **model-free reinforcement learning algorithms**.

## Monte Carlo Control

A simple approach is to create (sample) episodes and then update the state value estimates given this information. This approach is similar to Monte Carlo Tree Search that uses playouts. Here is how such an episode looks like.

```{r}
set.seed(1111)
sample_MDP(maze, n = 1, horizon = 50, trajectories = TRUE)$trajectories
```

Monte Carlo methods creates on episode (search from the start to the goal) at a time and then updates the state values in reverse order using the learning parameter $\alpha$. The easiest method is called On-policy Monte Carlo control and uses an exploring $\epsilon$-greedy policy to explore the maze. It is called on-policy because it also learns the same $\epsilon$-greedy policy.

Since we have observed that the simulated episode above was not able to find the goal after 50 steps, we use a much larger horizon for the algorithm.

```{r}
system.time(sol <- solve_MDP(maze, method = "MC:on_policy", 
                 horizon = 1000, n = 10, 
                 epsilon =.2, alpha = 0.3))
```

```{r}
#| fig-width: 8
#| fig-height: 8
gw_plot(sol)
```

We see that it explores a large part of the maze, but then concentrates on the direct path to the goal.

Step-by-step solution.

```{r}
#| fig-width: 8
#| fig-height: 8
sol <- gw_animate(maze, "MC:on_policy", 
                  n = 30, horizon = 1000, 
                  epsilon =.2, alpha = 0.3,
                  ylim = c(70, 100))
```

Initially, the random exploration does not lead to the goal during the horizon, but eventually it finds a path. The behavior can be compared to

-   repeated depth-first search with a depth limited,
-   or Monte Carlo tree search for game trees where the utility is propagated from the end of the game to the current state.

## Q-Learning

Q-learning is the most popular model-free temporal differencing (TD) RL method that does not update with complete episodes, but it updates for each step. The idea is that for each step it makes the value of the current state a little more similar to the value of the next step plus the immediate reward.

```{r}
system.time(sol <- solve_MDP(maze, method ="TD:q_learning", 
                             horizon = 1000, n = 100, 
                             alpha = 0.3))

sol
```

```{r}
#| fig-width: 8
#| fig-height: 8
gw_plot(sol)
```

It is interesting to look at the step-by-step of Q-learning. Q-learning follows an $\epsilon$-greedy policy where it takes the current beat action, but with a probability of $\epsilon$ uses a random action to perform exploration. Initially, the agent has no good policy and essentially performs random walk.

I use 1000 as the horizon with the hope that it will randomly run into the goal. After some experimentation, I settled on an $\epsilon$ of $0.2$ which means every 5th action is chosen randomly and I use a relatively high, fixed learning rate $\alpha$ of $0.3$

```{r}
#| fig-width: 8
#| fig-height: 8
sol <- gw_animate(maze, "TD:q_learning", 
                  n = 100, horizon = 1000, 
                  epsilon = 0.1, alpha = 0.3, 
                  zlim = c(-1,100))
```

# Conclusion

If the environment is known and the number of states and actions is not too large, then model-based methods like value or policy iteration are the best method.

Model-free RL methods are typically horribly data inefficient, but they do not need a model of the environment and do not need to calculate state values for all states.