Where is the food? Reinforcement Learning in a Maze World

Nuria Oliver, MIT Media Lab

Overview

I implemented and compared several reinforcement-learning algorithms in a maze world. An agent navigates a configurable grid from a starting position to a goal and receives a reward when it arrives. The task is to learn an optimal policy over time through trial and error. I made the application interactive so the user could design a maze, set the learning parameters, and compare the algorithms.

I chose the maze because it has a stationary environment (fixed transition probabilities and rewards) and an enumerable state space, the two assumptions made by these algorithms. It was still complex enough to show differences in their behavior.

Those assumptions also delimit the result: my comparison concerns a small, fully enumerable grid world, not environments with changing dynamics or continuous, partially observed states.

Algorithms Implemented

• Q-learning: updates state-action values based on the immediate reward plus the estimated value of the best next action.
• DynaQ−: extends Q-learning with an internal world model; for each real experience, k hypothetical experiences are generated and used to update the value function, dramatically improving learning speed.
• DynaQ+: extends DynaQ− to solve the shortcut problem (adapting when a better path to the goal becomes available after the initial policy is learned) using an exploration bonus that encourages re-visiting state-action pairs that have not been tried recently.

Action Selection Policies

• Greedy: always selects the action with the highest estimated value. Prone to suboptimal convergence from early unlucky samples.
• Exploration bonus: greedy selection augmented by an uncertainty term proportional to time elapsed since the action was last tried in that state.
• ε-greedy: greedy with probability 1−ε, uniformly random with probability ε.
• Boltzmann exploration: selects actions probabilistically according to a softmax distribution over estimated values, with temperature decreasing over time to reduce exploration.

Results and Conclusions

Action selection policy: In my experiments, pure greedy selection had a significant risk of converging to a suboptimal path. The other policies reliably found the optimal path, differing mainly in the number of trials and backups required. The system worked across different starting points and maze configurations under all strategies.

Learning strategy: I found that the Dyna architectures learned the optimal policy much faster than pure Q-learning because each real experience generated k additional hypothetical updates. The trade-off was a substantially higher computational load. DynaQ+ also handled environmental changes, at the cost of additional memory to track state-action recency.

Learning parameters: Higher learning rates and larger values of k accelerated convergence but increased the number of backups required. I used a convergence criterion based on the Bellman residual as a stopping rule.

System

I wrote the user interface in Tcl/Tk and the learning algorithms in C++. The user could set the maze walls, start, and goal; choose an action-selection policy; adjust the learning parameters; and watch the paths and learning curves in real time.