Skip to content
willjchillPublic

About

Accelerating Q-learning for pathfinding with CUDA.

Resources

Stars

2 stars

Watchers

0 watching

Forks

Repository files navigation

ENG EC 527 Final Project: Q-Learning Maze Solver Accelerator

Project Team: Victor Mercola, William Desueza, Skanda Nadig

This project implements a reinforcement learning tabular Q-learning application targeting path-finding optimization inside a grid-based maze. It investigates and compares a standard sequential CPU algorithm against several parallelization strategies, with a massively parallel CUDA GPU formulation as the primary focus.

Core Q-Learning Mechanics

In this example, we use Q-learning to train an agent to find the shortest path from the top-left corner to the bottom-right corner of a grid-based maze.

Given this environment's definition, we can define its state space $\mathcal{S}$ as the set of all possible grid coordinates, i.e., $\mathcal{S} = \{0, 1, 2, \ldots, \mathtt{GRID\_SIZE} - 1\}^2$.

For every state, the agent can take one of five actions: up, right, down, left, or nothing. We can define the action space $\mathcal{A}(s)$ for a state $s \in \mathcal{S}$ as $\mathcal{A}(s) = \{0, 1, 2, 3, 4\}$, where 0 represents up, 1 represents right, 2 represents down, 3 represents left, and 4 represents nothing.

To train the agent, we reward it or penalize it based on the actions that it takes during a single "episode", and determine whether to terminate the episode based on the following conditions:

Behavior Reward Terminate
Agent reaches the goal +1 true
Agent hits a boundary -1 false
Agent hits a forbidden cell -1 false
Agent moves to empty cell 0 false
Agent takes too long 0 true

The discount factor $\gamma \in (0, 1)$ is used to weight the importance of future rewards. A higher discount factor means that the agent is more likely to take actions that will lead to higher rewards in the future. A lower discount factor means that the agent is more likely to take actions that will lead to higher rewards in the present.

The learning rate $\alpha \in (0, 1]$ is used to control how much the agent learns from each experience. A higher learning rate means that the agent is more likely to learn from each experience. A lower learning rate means that the agent is less likely to learn from each experience. Some implementations use a decaying learning rate, where the learning rate decreases over time. This allows the agent to learn quickly at the beginning and then fine-tune its policy later. However, in this implementation, the learning rate is constant.

Q-Table Initialization

Before the agent can begin learning, it needs a memory structure to store the value of taking specific actions in specific states. This is the Q-table, a state-action matrix $Q(s, a)$. Initially, the agent knows nothing about the environment, so the table is initialized completely to zeroes. As the agent explores, these values will iteratively update.

Exploration vs. Exploitation ($\epsilon$-greedy strategy)

During training, the agent balances discovering new, potentially faster paths (exploration) and using the best path it has found so far (exploitation). We employ an $\epsilon$-greedy strategy:

  • Exploration (Probability $\epsilon$): The agent takes a random action, ignoring current Q-values.
  • Exploitation (Probability $1 - \epsilon$): The agent takes the action with the highest Q-value for the current state.

This strategy ensures the agent thoroughly explores the maze early on, while converging on the optimal path as the Q-values become more accurate.

The Bellman Equation

The core logic of Q-learning relies on the Bellman Optimality Equation. In our tabular implementation, the main memory Q state-action matrix is updated directly using the temporal difference rule derived from this equation:1

$$ q_{t+1} \left( s_t, a_t \right) = q_t \left( s_t, a_t \right) - \alpha_t \left( s_t, a_t \right) \left[ q_t \left(s_t, a_t \right) - \left( r_{t+1} + \gamma \max_{a \in \mathcal{A} \left(s_{t+1}\right)} q_t \left( s_{t+1}, a \right) \right) \right] $$

Symbol Description Values
$t$ Time, $\{0, 1, 2, \ldots\}$
$s_t$ The state (i.e., grid coordinate) at time $t$ $\{0, 1, \ldots, \mathtt{GRID\_SIZE} - 1\}^2$
$a_t$ The action (i.e., direction to move) at time $t$ $\{0, 1, 2, 3, 4\}$
$r_t$ Reward at time $t$ $\{+1, -1, 0\}$
$q \left( s_t, a_t \right)$ Estimate of the optimal action value of the state-action pair $\left(s_t, a_t\right)$ $\mathbb{R}$
$\alpha \left( s_t, a_t \right)$ Learning rate for the current state-action pair $\left(s_t, a_t\right)$ $0.5$
$\gamma$ Discount factor $0.99$

This equation is used to update the Q-table after each step in the episode. The learning rate determines how much the Q-value is updated, and the discount factor determines how much future rewards are valued.

Deriving the Optimal Policy

Once training finishes and the Q-table has converged, the agent can navigate the maze optimally without any exploration or learning. The extraction of the optimal path (the policy $\pi^*$) is achieved by simply taking the argument maximum of the Q-values for any state the agent finds itself in:

$$ \pi^*(s) = \arg\max_{a \in \mathcal{A}(s)} Q(s, a) $$


Project Structure

All GridWorld implementations live in the src/ directory. The benchmarked implementations (gridworld_serial.c, gridworld_openmp.c, gridworld_gpu.cu, and gridworld_python.py) share the same external interface so src/__main__.py can benchmark them uniformly. The remaining files are exploratory variants used to study vectorization, manual threading, or bottlenecks in isolation.

File Role
src/gridworld_serial.c Serial C — single-threaded reference implementation. This is the baseline against which all parallelization speedups are measured.
src/gridworld_python.py Python / Gymnasium — reference implementation in Python using the gymnasium RL library. Serves as the clean algorithmic reference; only benchmarked on small grids due to interpreter overhead.
src/gridworld_openmp.c OpenMP — distributes episodes across CPU threads with #pragma omp parallel / #pragma omp for, while threads keep private environment state and share one Q-table.
src/gridworld_gpu.cu CUDA — the primary GPU accelerator. Uses inter-episode parallelism: each CUDA worker runs a strided subset of episodes and applies Bellman updates to the shared Q-table with an atomic compare-and-swap loop.
src/pathfinding_q.c Standalone Serial Pathfinding — taken from gridworld_serial.c but has timers to track the Bellman update bottleneck in CPU time vs other time.

Parallelization Methods Comparison

Method Parallelism Model Memory Model Synchronization
Serial C None (1 thread) Stack/heap N/A
Python/Gymnasium None (GIL-bound) Heap (Python objects) N/A
OpenMP CPU thread pool, inter-episode Shared Q-table + thread-local env/RNG Hogwild Q-table writes, atomic epsilon decay
CUDA GPU Massively parallel workers, inter-episode Global Q-table + per-thread registers/RNG Atomic compare-and-swap Bellman update

Inter-episode parallelism: Each parallel unit (thread/lane) runs a full independent episode. This avoids dependencies between timesteps within an episode, making it naturally parallel. The Q-table is shared, so concurrent updates require atomic operations.

Parallel Design Strategy

The project follows the same high-level design pattern across CPU threading, SIMD, and CUDA. The main differences are in how work is cut up, assigned to workers, synchronized, and mapped onto hardware.

Aspect Strategy Used Here
Decomposition We do not split a single episode across workers, because each step depends on the previous state. Instead, we decompose the problem into many independent episodes.
Assignment Serial executes episodes one at a time. OpenMP assigns episodes with an omp for loop. CUDA assigns strided global episode indices to workers so each thread processes episode tid, tid + worker_count, tid + 2 * worker_count, ....
Orchestration Workers share the read-only maze grid and global Q-table, but maintain private transient states (location, RNG). OpenMP updates the Q-table with asynchronous Hogwild writes, while CUDA uses an atomic compare-and-swap loop to ensure stability.
Mapping OpenMP maps software workers to CPU threads. CUDA maps workers to the GPU block hierarchy, automatically capping the thread count on small grids to minimize Q-table contention.

Implementations

Serial CPU (gridworld_serial.c)

The CPU algorithm handles episodic exploration sequentially loop-by-loop. As the agent encounters rewards (or penalties for hitting walls), the Bellman formula is computed in a single thread, recursively updating each state's value step-by-step alongside the exploration trajectory.

OpenMP CPU (gridworld_openmp.c)

The OpenMP version keeps the same Q-learning logic, but changes the outer training loop from "one episode after another" into "many episodes at once across CPU threads."

  • A parallel region creates a pool of worker threads.
  • Each worker gets a private copy of the environment state and a thread-local RNG seed.
  • #pragma omp for assigns episodes to threads, so the decomposition is still inter-episode rather than intra-episode.
  • All threads share the same Q-table, so Q-learning updates happen asynchronously in a Hogwild-style fashion.
  • The global exploration rate is decayed with an atomic update so it still trends downward across the run.

This is a natural fit for multicore CPUs because episodes are coarse enough to amortize thread overhead, while the shared table allows useful information discovered by one thread to propagate to the others.

CUDA GPU (gridworld_gpu.cu)

Rather than distributing a single episode search (intra-episode parallelism), this accelerator performs inter-episode parallelism natively on the host GPU. Episodes are chunked across hardware streaming multiprocessors.

  • Each CUDA worker owns a strided subset of the global episode indices, which keeps the assignment simple and avoids any centralized scheduler.
  • Each worker initializes its own curand RNG state so epsilon-greedy action selection is independent.
  • The world grid is copied once into device memory and treated as read-only during training.
  • The Q-table lives in global memory and is shared by every worker.
  • Bellman updates are now applied through an atomic compare-and-swap update loop, not a raw atomicAdd of a stale delta. In effect, each worker repeatedly tries to perform:
q = q + alpha * (target - q)

against the latest value currently stored in memory.

  • The launcher also caps the active worker count to the smaller of the episode count, the Q-table size, and the default hardware-sized launch. This reduces useless contention on small grids where thousands of GPU threads would otherwise fight over a tiny table.

This design keeps the decomposition embarrassingly parallel at the episode level while making the shared Q-table stable enough to converge on the GPU.

Experimentation and Execution

Environment Setup

This project uses uv for Python environment management. All Python commands should be run through uv run to ensure the correct virtual environment is used:

# One-time setup (creates .venv/ automatically)
uv sync

Running the Full Benchmark Suite (__main__.py)

The primary driver script src/__main__.py automates the full benchmark pipeline:

  1. Generates random maze grids at multiple sizes and obstacle densities
  2. Builds each implementation (serial_c, gpu_impl, openmp_impl, python_impl)
  3. Runs all combinations of (grid_size, forbidden_prob, implementation, seed)
  4. Saves per-run training/test/Q-table/policy data as .parquet files in data/
  5. Generates per-run SVG plots in data/
# Run from the project root
uv run src/__main__.py

Key parameters (edit at top of __main__.py):

Variable Default Description
GRID_SIZES [8, 16, 32, 64, 128, 256] Grid dimensions to test
SEEDS [123, 456, 789, 101112] Random seeds (averaged over in plots)
FORBIDDEN_PROBABILITIES [0.0, 0.05, 0.1, 0.15, 0.2] Wall density
omp_threads [1, 2, 4, 8, 16, 32, 64] Evaluated dynamically inside openmp_impls
threads_per_block & num_blocks Powers of 2 up to 128 Evaluated dynamically inside gpu_impls
IMPLEMENTATIONS all four Which implementations to benchmark

Note: The python_impl is automatically skipped for grids larger than 32×32 due to interpreter overhead.

Generating Comparison Plots

After collecting data with src/__main__.py, generate aggregate comparison plots:

# General comparison plots (output to data/plot/)
uv run python visualize_results.py

# Execution time, throughput, and speedup scaling plots (output to plots/)
uv run python src/overall_plots.py

Bottleneck Analysis

The standalone src/pathfinding_q.c is used for bottleneck profiling. It is taken from gridworld_serial.c but has timers to track Bellman update bottlenecks, separating Q-table update latency from the rest of the CPU execution time:

bash generate_output.sh

Results are deposited into data/csv_outputs/results.csv. The visualize_results.py script uses this CSV to generate a stacked bar plot showing the fraction of CPU time spent on Q-table updates vs all other work.

Debug Tracing Animations

If you'd like to trace and compare the actual policy convergence paths of CPU vs GPU inside the terminal visually, use the -DPRINT_EPISODE compilation flag. We provide a debug make target:

make debug
./build/maze_debug

(Visual Key: S = Starting Pos, G = Goal Pos, O = Current Object Pos, . = Empty block)

Footnotes

  1. "Mathematical Foundations of Reinforcement Learning", Shiyu Zhao, §7.4 ↩

About

Accelerating Q-learning for pathfinding with CUDA.

Resources

Stars

2 stars

Watchers

0 watching

Forks

Releases

Packages

Contributors

Languages