Exploring Grid Worlds: Q‑Learning, UCB & MCTS in Action

Navigating a grid world that changes on the fly is a classic testbed for reinforcement learning and decision‑making research. In this tutorial, we set up a simple dynamic grid environment where an agent must reach a goal while avoiding moving obstacles. The key question is how the agent decides which cells to visit—i.e., how it balances the need to explore uncharted territory with the desire to exploit known good moves. By comparing three well‑known exploration techniques—Q‑Learning with epsilon‑greedy, Upper Confidence Bound (UCB), and Monte Carlo Tree Search (MCTS)—the post offers a side‑by‑side view of their learning curves, convergence speeds, and resilience to environmental changes.

Q‑Learning treats the grid as a Markov decision process and updates a value table using the Bellman equation. The epsilon‑greedy policy injects randomness: with probability ε the agent chooses a random cell, otherwise it follows the current best action. UCB, inspired by bandit theory, selects actions that trade off estimated value with uncertainty, quantified by a confidence term that shrinks as visits increase. MCTS builds a search tree over future steps, sampling random rollouts to estimate the value of unexplored branches and then backing up the results. Together, these methods illustrate a spectrum from value‑based learning to principled exploration and tree‑based planning.

We run each agent for 10,000 episodes, measuring cumulative reward and average steps to goal. Experiments also alter the obstacle dynamics—static versus moving—and tweak key hyperparameters such as ε decay, UCB exploration constant, and MCTS rollout depth. Results show that Q‑Learning converges fastest in static grids but struggles when obstacles shift. UCB remains robust, steadily improving as it refines its confidence estimates, while MCTS excels in highly dynamic settings thanks to its look‑ahead capability. The tutorial ends with a discussion on hybridizing these strategies, for example using UCB‑guided action selection within an MCTS framework, to combine the best of exploration and planning.