Maze Navigation with Reinforcement Learning

Policy Evaluation, Policy Iteration, Q-Learning, and SARSA in a custom 10 × 10 maze

---

Project Overview

This project explores dynamic programming and tabular reinforcement learning algorithms in a custom 10 × 10 maze environment.

The maze contains three fences and a goal state located in one corner. An agent must learn how to navigate from different starting positions to the goal while avoiding obstacles and minimizing unnecessary movements.

The project compares random and optimized policies using:

• Policy Evaluation
• Local Policy Improvement
• Policy Iteration
• Q-Learning
• SARSA
• Trajectory and reward visualizations

---

Project Objectives

• Create and visualize a custom 10 × 10 maze
• Evaluate a random deterministic policy
• Study the effect of improving actions near the goal
• Find an optimal policy using policy iteration
• Compare random and optimal policy trajectories
• Implement tabular Q-learning
• Implement tabular SARSA
• Analyze accumulated rewards, variance, and convergence

---

Environment

The reinforcement learning environment consists of:

• Grid size: 10 × 10
• Obstacles: Three fences
• Goal state: Located in one corner
• State: Current position of the agent
• Actions: Up, down, left, and right
• Objective: Reach the goal using the shortest efficient path

Moves that cross maze boundaries or fences are restricted by the environment.

---

Implemented Tasks

Task 1: Maze Construction

A custom 10 × 10 maze was created with three fences and a goal state. The maze was visualized using a two-dimensional plot.

The visualization identifies:

• Available states
• Fence locations
• Agent starting positions
• Goal location

---

Task 2: Policy Evaluation

The iterative Policy Evaluation algorithm was implemented for a random deterministic policy.

Each state contains one selected action. The value function estimates the expected return obtained by following the policy from every position in the maze.

The deterministic policy-evaluation update is:

$$ V(s) \leftarrow r(s,\pi(s))+\gamma V(s') $$

where:

• $V(s)$ represents the value of state $s$
• $r$ represents the immediate reward
• $\gamma$ represents the discount factor
• $s'$ represents the next state

---

Task 3: Local Policy Improvement

Optimal actions were manually assigned to states within a two-cell radius of the goal.

The values of states close to the goal increased because the agent could reach the destination with fewer penalized steps.

However, the improvement remained localized. States farther away continued to follow the random policy and demonstrated inefficient behavior.

This experiment shows that improving a policy only near the goal does not produce a globally optimal solution. An effective policy must guide the agent from every reachable state.

---

Task 4: Policy Iteration

Policy Iteration was implemented by repeatedly alternating between:

1. Policy Evaluation: Calculate the value function for the current policy.
2. Policy Improvement: Select better actions using the calculated values.

The improved action for each state is selected using:

$$ \pi(s) \leftarrow \arg\max_a\left[r(s,a)+\gamma V(s')\right] $$

During the first iteration, many states had relatively low values because the initial policy did not guide the agent efficiently.

In later iterations, higher state values spread outward from the goal. The resulting value function created a clearer navigation gradient through the maze.

By the third illustrated iteration, the policy had converged toward an efficient strategy for reaching the goal.

---

Task 5: Random and Optimal Policy Trajectories

A transition function was implemented in the following form:

next_state, reward = step(state, action)

The function receives the current state and action and returns the next state and reward.

Ten trajectories were generated from different initial states using:

• A random policy
• The optimal policy obtained through policy iteration

Random Policy Results

The random-policy trajectories were scattered and inefficient. The agent frequently moved in unnecessary directions and sometimes failed to reach the goal within the maximum number of steps.

Optimal Policy Results

The optimal-policy trajectories were shorter, clearer, and more consistent. The agent reached the goal with fewer unnecessary movements and minimal detours.

The comparison demonstrates the importance of learning a policy that maximizes long-term reward.

---

Task 6: Q-Learning and SARSA

Tabular Q-learning and SARSA were implemented using epsilon-greedy action selection.

Multiple independent runs were performed to evaluate:

• Accumulated reward
• Average reward
• Reward variance
• Learning stability
• Convergence behavior

Q-Learning

Q-learning is an off-policy temporal-difference algorithm. It updates its action values using the best estimated action in the next state.

The Q-learning update is:

$$ Q(s,a) \leftarrow Q(s,a)+ \alpha\left[ r+\gamma\max_{a'}Q(s',a')-Q(s,a) \right] $$

The accumulated reward increased as the agent learned to balance exploration and exploitation.

The variance generally decreased as the policy became more stable and the agent selected efficient actions more consistently.

SARSA

SARSA is an on-policy temporal-difference algorithm. It updates its action values using the next action selected by the current policy.

The SARSA update is:

$$ Q(s,a) \leftarrow Q(s,a)+ \alpha\left[ r+\gamma Q(s',a')-Q(s,a) \right] $$

SARSA also improved its accumulated reward during training. However, it demonstrated slower convergence and greater variability during exploration in these experiments.

Because SARSA learns from the actions actually selected by the current policy, its behavior is generally more cautious than Q-learning.

---

Q-Learning vs. SARSA

Characteristic	Q-Learning	SARSA
Learning method	Off-policy	On-policy
Update target	Best estimated next action	Selected next action
Behavior	More aggressive	More cautious
Observed convergence	Faster	Slower
Observed variance	Lower near convergence	Higher during exploration

---

Technologies Used

• Python
• NumPy
• Matplotlib
• Dynamic programming
• Policy evaluation
• Policy iteration
• Tabular reinforcement learning
• Q-learning
• SARSA

---

Suggested Project Structure

Maze-Navigation-Reinforcement-Learning/
├── main.py
├── maze.py
├── policy_evaluation.py
├── policy_iteration.py
├── q_learning.py
├── sarsa.py
├── requirements.txt
├── README.md
└── results/
    ├── maze_layout.png
    ├── random_policy_values.png
    ├── local_policy_improvement.png
    ├── policy_iteration.png
    ├── trajectory_comparison.png
    └── q_learning_sarsa.png

Adjust the filenames above to match the actual files in the repository.

---

Installation

1. Clone the Repository

git clone https://github.com/saxenap2804/Maze-Navigation-Reinforcement-Learning.git
cd Maze-Navigation-Reinforcement-Learning

2. Create a Virtual Environment

python -m venv venv

3. Activate the Virtual Environment

Windows

venv\Scripts\activate

macOS or Linux

source venv/bin/activate

4. Install the Dependencies

pip install -r requirements.txt

5. Run the Project

python main.py

Update the execution command if the primary script has a different filename.

---

Key Findings

• Random policies produce inefficient and inconsistent navigation.
• Improving actions only near the goal creates localized benefits.
• Policy iteration develops an efficient global navigation strategy.
• Optimal-policy trajectories are shorter than random-policy trajectories.
• Q-learning and SARSA both learn improved policies through experience.
• Q-learning converged faster in the reported experiments.
• SARSA demonstrated more cautious on-policy behavior.
• Reduced variance indicates that the learned behavior is becoming more stable.

---

Future Improvements

• Experiment with larger and more complex mazes
• Add stochastic state transitions
• Add moving obstacles
• Animate agent trajectories
• Implement a decaying epsilon schedule
• Compare different learning rates and discount factors
• Evaluate performance across additional random seeds
• Report confidence intervals
• Compare with Deep Q-Networks

---

Authors

• Priyanka Saxena
• Swapnil Sanjay Pawar

---

License

This project is available for educational and research purposes. Add an appropriate open-source license, such as the MIT License or Apache License 2.0.