Q-Table Explained: 5 Steps to Master Reinforcement Learning

Imagine you're teaching a dog new tricks. You don't hand it a manual — you reward it when it does something right and ignore (or correct) it when it doesn't. Over dozens of repetitions, the dog builds an internal sense of which actions pay off in which situations. That's the soul of reinforcement learning, and the Q-Table is how we give a computer program that same kind of memory.

In this post, we'll build a complete Q-learning agent from scratch — a warehouse robot that learns to navigate a 5×5 grid to deliver packages while avoiding forklift collision zones. By the end, you'll understand not just what a Q-Table is, but why every design choice exists.

---

The Problem Q-Learning Solves

Why Supervised Learning Fails Here

Supervised learning is fantastic when you have labeled examples: "given this email, the correct label is spam." But consider our warehouse robot. What's the "correct" move when the robot is at position (2, 3) and the target shelf is at (4, 4)? Move right? Move down? Both might eventually work. The right answer depends on the entire sequence of future moves — not just the current step.

There's no teacher handing out labeled training data. The robot must discover good strategies through trial and error. This is the core of sequential decision-making under uncertainty.

The Explore-Exploit Dilemma

Here's a tension every RL agent faces:

• Exploit: Do what you already know works well. (Go the route you've taken before.)
• Explore: Try something new. Maybe there's a better route you haven't discovered yet.

Think of it like a delivery driver who always takes the same highway route because it worked yesterday. One day the highway is jammed, but the driver never finds the faster back roads because they stopped exploring. If the robot only exploits, it gets stuck in the first decent strategy it finds. If it only explores, it never actually gets good at anything. The balance is called the epsilon-greedy policy, and we'll implement it in Step 3.

What "Reward" Means Computationally

A reward is simply a scalar number the environment hands back after each action: - +100 for reaching the target shelf - -50 for hitting a forklift collision zone - -1 for each time step (to encourage finding fast paths, not just safe ones)

The robot's job is to maximize total cumulative reward over time — not just the immediate reward of a single move.

The Reinforcement Learning Loop

Agent observes State s

→

Chooses Action a

→

Environment returns Reward r + Next State s'

→

Agent updates Q-Table

→

Repeat until convergence

The agent-environment loop is the heartbeat of Q-learning. Each cycle produces one experience tuple (s, a, r, s') used to sharpen the Q-Table. The agent never sees the full map — it only learns from these one-step snapshots.

---

Anatomy of a Q-Table

A Q-Table is a plain 2D matrix. Think of it like a laminated cue card the robot carries at all times — every room it might enter is a row, every direction it might walk is a column, and each cell holds its best guess at how rewarding that move will be:

• Rows = every possible state the robot can be in (each of the 25 grid cells)
• Columns = every possible action (UP, DOWN, LEFT, RIGHT)
• Cell value = Q-value — an estimate of "how good is it to take this action from this state?"

         UP      DOWN    LEFT    RIGHT
State 0  [ 0.00   0.00    0.00    0.00  ]   ← (row 0, col 0): Start
State 1  [ 0.00   0.00    0.00    0.00  ]   ← (row 0, col 1)
...       ...
State 12 [ 0.00   0.00    0.00    0.00  ]   ← Center of grid
...       ...
State 24 [ 0.00   0.00    0.00    0.00  ]   ← Target shelf!

After training:
         UP      DOWN    LEFT    RIGHT
State 0  [ 0.12   0.45   -0.30    0.67  ]   Robot should go RIGHT
State 5  [-0.50   0.89    0.23    0.45  ]   Robot should go DOWN

A Q-Table before (all zeros) and after training. Each cell stores the expected future reward for taking that action from that state. The robot picks the action with the highest Q-value in its current row — no computation needed at decision time, just a lookup.

Initialization and Size

Every cell starts at 0.0 — the agent assumes nothing about the world. Over training episodes, values drift toward their true worth. Starting at zero is a deliberate choice: it makes the agent mildly optimistic about unexplored actions (since even a small positive reward will beat 0.0 initially), which naturally encourages exploration early in training.

Size? For our 5×5 warehouse: 25 states × 4 actions = 100 cells. Totally manageable. But consider a chess engine: ~10⁴⁷ possible board states. A Q-Table would require more memory than there are atoms in the observable universe. That's the state space explosion problem — we'll revisit it at the end.

---

The Bellman Equation Demystified

Intuition First

Imagine you're a hiking guide estimating how long it takes to reach a mountain summit from various waypoints on the trail. You don't walk every possible path from scratch each time — instead, you reason backwards: "From waypoint C, the summit is 30 minutes away. So from waypoint B (20 minutes from C), the total is 50 minutes." Once you know the value of a closer waypoint, you can immediately compute the value of every waypoint leading into it.

The Bellman equation does exactly this for Q-values — it propagates the value of reaching the goal backwards through the state space, one step at a time:

*"The value of being in state s and taking action a equals the immediate reward, plus the discounted value of the best action you can take from wherever you end up."

The Formula

Q(s, a) ← Q(s, a) + α [ r + γ · max Q(s', a') − Q(s, a) ]
                              └─────────────────────┘
                               Temporal Difference (TD) Error

Let's dissect every piece:

Symbol	Name	Role	Typical Range
Q(s,a)	Current Q-value	What we currently think this move is worth	Any real number
α (alpha)	Learning rate	How fast to update — like a student who absorbs 30% of each lesson	0.01 – 0.5
r	Immediate reward	What the environment actually gave us right now	Domain-specific
γ (gamma)	Discount factor	How much we care about future rewards vs. immediate ones	0.9 – 0.99
max Q(s',a')	Best future Q-value	Best known value of the next state	Any real number
TD Error	Surprise signal	How wrong our current estimate was — shrinks toward 0 at convergence	Shrinks to 0 at convergence

What Each Hyperparameter Controls

α (Learning Rate): - Too high (α=0.9): The agent overreacts to each experience, values oscillate wildly — like a student who completely rewrites their notes after every single lecture, forgetting everything they studied the week before. - Too low (α=0.001): Learning is painfully slow, may not converge in reasonable time. - Sweet spot: Start at 0.1, decay slowly over episodes.

γ (Discount Factor): - γ=0: Robot is completely short-sighted — only cares about immediate reward (terrible for navigation). - γ=1: Robot gives equal weight to rewards 1,000 steps in the future (can cause instability in long episodes). - γ=0.95: "I care about future rewards, but I prefer sooner ones" — realistic and stable.

ε (Epsilon — explore/exploit): - ε=1.0: Pure exploration (random actions) - ε=0.0: Pure exploitation (always take best known action) - Strategy: Start at 1.0, decay to 0.01 over training

Temporal Difference: How Surprise Drives Learning

Agent predicts Q(s,a) = 2.5

→

Takes action, gets r=10, lands in s'

→

TD Error = 10 + 0.95×3.0 − 2.5 = 10.35

→

New Q = 2.5 + 0.1×10.35 = 3.535

The TD Error is the "surprise" signal. A large positive error means this move was better than expected — raise its Q-value. A negative error means it was worse — lower it. Over thousands of steps, these small corrections accumulate into reliable estimates.

---

Step-by-Step: Building a Q-Table from Scratch

Our Scenario: The Warehouse Robot Navigator

A 5×5 grid warehouse. The robot starts at cell (0,0) — the loading dock. The target shelf is at (4,4). Three cells are blocked forklift zones: (1,1), (2,3), and (3,1).

  0   1   2   3   4
0 [S] [ ] [ ] [ ] [ ]
1 [ ] [X] [ ] [ ] [ ]
2 [ ] [ ] [ ] [X] [ ]
3 [ ] [X] [ ] [ ] [ ]
4 [ ] [ ] [ ] [ ] [T]

S = Start (loading dock)
T = Target shelf
X = Forklift collision zone

States are numbered 0–24 by row-major order: state = row×5 + col.

---

Step 1: Define the Environment

Before writing any learning code, we formalize the world. This is the most important step — a poorly designed reward structure will produce a robot that technically maximizes its score while doing something completely wrong (a phenomenon called reward hacking).

• States: 25 (one per grid cell)
• Actions: 4 (0=UP, 1=DOWN, 2=LEFT, 3=RIGHT)
• Rewards:
• Reach target (4,4): +100
• Hit forklift zone: -50 (episode ends)
• Each step: -1 (time penalty encourages short paths)
• Hit wall (try to move off grid): -5 (discourage wall bumping)

Why the -1 step penalty? Without it, a robot that reaches the goal in 8 steps and one that reaches it in 80 steps receive the same total reward (+100). The step penalty forces the robot to prefer shorter routes — exactly what we want in a real warehouse.

---

Step 2: Initialize the Q-Table

All zeros. The robot knows nothing yet.

import java.util.Arrays;

public class Main {
    static final int NUM_STATES = 10;
    static final int NUM_ACTIONS = 4;

    public static void main(String[] args) {
        double[][] qTable = new double[NUM_STATES][NUM_ACTIONS];
        // Java initializes double arrays to 0.0 by default
        // But let's be explicit for clarity:
        for (int state = 0; state < NUM_STATES; state++) {
            Arrays.fill(qTable[state], 0.0);
        }
    }
}

---

Step 3: Epsilon-Greedy Policy

With probability ε, explore (random action). Otherwise, exploit (best Q-value). Note how rng.nextDouble() returns a value in [0.0, 1.0) — if ε is 0.3, there's a 30% chance we explore.

import java.util.Random;

public class Main {
    static final int NUM_ACTIONS = 4;

    static int chooseAction(double[][] qTable, int state, double epsilon, Random rng) {
        if (rng.nextDouble() < epsilon) {
            // Explore: pick a random action
            return rng.nextInt(NUM_ACTIONS);
        } else {
            // Exploit: pick the action with highest Q-value
            int bestAction = 0;
            double bestValue = qTable[state][0];
            for (int action = 1; action < NUM_ACTIONS; action++) {
                if (qTable[state][action] > bestValue) {
                    bestValue = qTable[state][action];
                    bestAction = action;
                }
            }
            return bestAction;
        }
    }

    public static void main(String[] args) {
        Random rng = new Random();
        int numStates = 5;
        double epsilon = 0.1;

        double[][] qTable = new double[numStates][NUM_ACTIONS];

        int state = 0;
        int action = chooseAction(qTable, state, epsilon, rng);
        System.out.println("Chosen action for state " + state + ": " + action);
    }
}

---

Step 4: Run Episodes and Apply the Update Rule

An episode is one complete run of the robot from start to either reaching the target or hitting a forklift zone. We run many episodes — each one contributes a small amount of learning. The Bellman update happens after every single step, not just at the end of each episode.

import java.util.Arrays;

public class Main {
    static final int MAX_EPISODES = 1000;
    static final int START_STATE = 0;
    static final double GAMMA = 0.99;
    static final double ALPHA = 0.1;
    static final double EPSILON_MIN = 0.01;
    static final double EPSILON_DECAY = 0.995;

    static class StepResult {
        int nextState;
        double reward;
        boolean done;

        StepResult(int nextState, double reward, boolean done) {
            this.nextState = nextState;
            this.reward = reward;
            this.done = done;
        }
    }

    static class Environment {
        StepResult step(int state, int action) {
            // Placeholder implementation
            return new StepResult(0, 0.0, true);
        }
    }

    static int chooseAction(double[][] qTable, int state, double epsilon, java.util.Random rng) {
        if (rng.nextDouble() < epsilon) {
            return rng.nextInt(qTable[state].length);
        }
        int bestAction = 0;
        for (int i = 1; i < qTable[state].length; i++) {
            if (qTable[state][i] > qTable[state][bestAction]) {
                bestAction = i;
            }
        }
        return bestAction;
    }

    public static void main(String[] args) {
        int numStates = 10;
        int numActions = 4;
        double[][] qTable = new double[numStates][numActions];
        double epsilon = 1.0;
        java.util.Random rng = new java.util.Random();
        Environment environment = new Environment();

        for (int episode = 0; episode < MAX_EPISODES; episode++) {
            int state = START_STATE;
            boolean episodeDone = false;

            while (!episodeDone) {
                int action = chooseAction(qTable, state, epsilon, rng);
                StepResult result = environment.step(state, action);

                // Bellman update
                double bestNextQ = Arrays.stream(qTable[result.nextState]).max().getAsDouble();
                double tdError = result.reward + GAMMA * bestNextQ - qTable[state][action];
                qTable[state][action] += ALPHA * tdError;

                state = result.nextState;
                episodeDone = result.done;
            }

            // Decay epsilon so the robot gradually stops exploring
            epsilon = Math.max(EPSILON_MIN, epsilon * EPSILON_DECAY);
        }
    }
}

---

Step 5: Extract the Learned Policy

After training, read the policy: for each state, the best action is the one with the highest Q-value. This is called taking the argmax of each row.

public class Main {
    static final int GRID_ROWS = 5;
    static final int GRID_COLS = 5;
    static final int TARGET_STATE = GRID_ROWS * GRID_COLS - 1;
    static final int NUM_ACTIONS = 4;

    static boolean isForkLiftZone(int row, int col) {
        // Define forklift zones - customize as needed
        return (row == 2 && col == 2);
    }

    void printPolicy(double[][] qTable) {
        String[] actionSymbols = {"↑", "↓", "←", "→"};
        for (int row = 0; row < GRID_ROWS; row++) {
            for (int col = 0; col < GRID_COLS; col++) {
                int state = row * GRID_COLS + col;
                if (isForkLiftZone(row, col)) { System.out.print(" X "); continue; }
                if (state == TARGET_STATE)    { System.out.print(" T "); continue; }
                int bestAction = 0;
                for (int a = 1; a < NUM_ACTIONS; a++) {
                    if (qTable[state][a] > qTable[state][bestAction]) bestAction = a;
                }
                System.out.print(" " + actionSymbols[bestAction] + " ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        Main main = new Main();
        double[][] qTable = new double[GRID_ROWS * GRID_COLS][NUM_ACTIONS];
        main.printPolicy(qTable);
    }
}

Expected output after 500 episodes:

 → → → → ↓
 → X → → ↓
 → → → X ↓
 → X → → ↓
 → → → → T

The robot learned to hug the right side and travel down — exactly the optimal path!

---

Full Java Implementation

Here's the complete, self-contained warehouse robot Q-learning agent:

import java.util.Arrays;
import java.util.Random;

/**
 * Warehouse Robot Q-Learning Agent
 * A 5x5 grid where a robot learns to navigate from (0,0) to (4,4)
 * while avoiding forklift collision zones.
 */
public class WarehouseRobotQLearning {

    // --- Environment Configuration ---
    static final int GRID_ROWS = 5;
    static final int GRID_COLS = 5;
    static final int NUM_STATES = GRID_ROWS * GRID_COLS;   // 25
    static final int NUM_ACTIONS = 4; // 0=UP, 1=DOWN, 2=LEFT, 3=RIGHT

    static final int START_STATE  = 0;  // (0,0) loading dock
    static final int TARGET_STATE = 24; // (4,4) storage shelf

    // Forklift collision zones: (row,col) → state index
    static final int[] FORKLIFT_ZONES = {
        1 * GRID_COLS + 1,  // (1,1) = state 6
        2 * GRID_COLS + 3,  // (2,3) = state 13
        3 * GRID_COLS + 1   // (3,1) = state 16
    };

    // --- Q-Learning Hyperparameters ---
    static final double ALPHA         = 0.1;   // Learning rate
    static final double GAMMA         = 0.95;  // Discount factor
    static final double EPSILON_START = 1.0;   // Initial exploration rate
    static final double EPSILON_MIN   = 0.01;  // Minimum exploration rate
    static final double EPSILON_DECAY = 0.995; // Decay per episode
    static final int    MAX_EPISODES  = 1000;
    static final int    MAX_STEPS     = 200;   // Max steps per episode

    // --- Reward Values ---
    static final double REWARD_TARGET   =  100.0;
    static final double REWARD_FORKLIFT =  -50.0;
    static final double REWARD_STEP     =   -1.0;
    static final double REWARD_WALL     =   -5.0;

    // Action deltas: row-change and col-change for each action
    static final int[] ROW_DELTA = {-1,  1,  0,  0}; // UP, DOWN, LEFT, RIGHT
    static final int[] COL_DELTA = { 0,  0, -1,  1};
    static final String[] ACTION_NAME = {"UP", "DOWN", "LEFT", "RIGHT"};
    static final String[] ACTION_SYMBOL = {"↑", "↓", "←", "→"};

    // ----------------------------------------------------------------
    //  Environment Logic
    // ----------------------------------------------------------------

    static boolean isForkLiftZone(int state) {
        for (int zone : FORKLIFT_ZONES) if (zone == state) return true;
        return false;
    }

    static int stateToRow(int state) { return state / GRID_COLS; }
    static int stateToCol(int state) { return state % GRID_COLS; }
    static int toState(int row, int col) { return row * GRID_COLS + col; }

    /**
     * Executes one action from the current state.
     * Returns: [nextState, reward, done]
     */
    static Object[] step(int currentState, int action) {
        int row = stateToRow(currentState);
        int col = stateToCol(currentState);

        int newRow = row + ROW_DELTA[action];
        int newCol = col + COL_DELTA[action];

        // Check for wall collision
        if (newRow < 0 || newRow >= GRID_ROWS || newCol < 0 || newCol >= GRID_COLS) {
            // Stay in place, pay wall penalty
            return new Object[]{currentState, REWARD_WALL, false};
        }

        int nextState = toState(newRow, newCol);

        // Check for forklift zone
        if (isForkLiftZone(nextState)) {
            return new Object[]{nextState, REWARD_FORKLIFT, true}; // Episode ends
        }

        // Check for target reached
        if (nextState == TARGET_STATE) {
            return new Object[]{nextState, REWARD_TARGET, true}; // Episode ends
        }

        // Normal step
        return new Object[]{nextState, REWARD_STEP, false};
    }

    // ----------------------------------------------------------------
    //  Policy: Epsilon-Greedy Action Selection
    // ----------------------------------------------------------------

    static int chooseAction(double[][] qTable, int state, double epsilon, Random rng) {
        if (rng.nextDouble() < epsilon) {
            return rng.nextInt(NUM_ACTIONS); // Explore
        }
        // Exploit: find action with max Q-value
        int bestAction = 0;
        for (int a = 1; a < NUM_ACTIONS; a++) {
            if (qTable[state][a] > qTable[state][bestAction]) {
                bestAction = a;
            }
        }
        return bestAction;
    }

    // ----------------------------------------------------------------
    //  Q-Table Update (Bellman Equation)
    // ----------------------------------------------------------------

    static void updateQTable(double[][] qTable, int state, int action,
                              double reward, int nextState) {
        double bestNextQ = Arrays.stream(qTable[nextState]).max().getAsDouble();
        double tdError = reward + GAMMA * bestNextQ - qTable[state][action];
        qTable[state][action] += ALPHA * tdError;
    }

    // ----------------------------------------------------------------
    //  Training Loop
    // ----------------------------------------------------------------

    static double[][] train(Random rng) {
        double[][] qTable = new double[NUM_STATES][NUM_ACTIONS]; // All zeros
        double epsilon = EPSILON_START;

        System.out.println("=== Starting Training ===");
        System.out.printf("%-10s %-12s %-12s %-10s%n",
                          "Episode", "Total Reward", "Steps Taken", "Epsilon");
        System.out.println("-".repeat(50));

        for (int episode = 1; episode <= MAX_EPISODES; episode++) {
            int state = START_STATE;
            double totalReward = 0.0;
            int stepCount = 0;
            boolean done = false;

            while (!done && stepCount < MAX_STEPS) {
                int action = chooseAction(qTable, state, epsilon, rng);
                Object[] result = step(state, action);

                int nextState  = (int)    result[0];
                double reward  = (double) result[1];
                boolean isDone = (boolean)result[2];

                updateQTable(qTable, state, action, reward, nextState);

                state = nextState;
                totalReward += reward;
                stepCount++;
                done = isDone;
            }

            // Decay epsilon after each episode
            epsilon = Math.max(EPSILON_MIN, epsilon * EPSILON_DECAY);

            // Log progress at key episodes
            if (episode == 1 || episode == 50 || episode == 100 ||
                episode == 250 || episode == 500 || episode == MAX_EPISODES) {
                System.out.printf("%-10d %-12.1f %-12d %-10.4f%n",
                                  episode, totalReward, stepCount, epsilon);
            }
        }
        return qTable;
    }

    // ----------------------------------------------------------------
    //  Policy Extraction and Visualization
    // ----------------------------------------------------------------

    static void printPolicy(double[][] qTable) {
        System.out.println("\n=== Learned Policy ===");
        System.out.println("(S=Start, T=Target, X=Forklift Zone)\n");
        for (int row = 0; row < GRID_ROWS; row++) {
            for (int col = 0; col < GRID_COLS; col++) {
                int state = toState(row, col);
                if (state == START_STATE)  { System.out.print(" S "); continue; }
                if (state == TARGET_STATE)  { System.out.print(" T "); continue; }
                if (isForkLiftZone(state)) { System.out.print(" X "); continue; }

                int bestAction = 0;
                for (int a = 1; a < NUM_ACTIONS; a++) {
                    if (qTable[state][a] > qTable[state][bestAction]) bestAction = a;
                }
                System.out.print(" " + ACTION_SYMBOL[bestAction] + " ");
            }
            System.out.println();
        }
    }

    static void printQTableSnapshot(double[][] qTable, int episode) {
        System.out.println("\n--- Q-Table Snapshot (Episode " + episode + ") ---");
        System.out.printf("%-8s %-8s %-8s %-8s %-8s%n",
                          "State", "UP", "DOWN", "LEFT", "RIGHT");
        System.out.println("-".repeat(48));
        for (int s = 0; s < NUM_STATES; s++) {
            System.out.printf("%-8d %-8.3f %-8.3f %-8.3f %-8.3f%n",
                s, qTable[s][0], qTable[s][1], qTable[s][2], qTable[s][3]);
        }
    }

    // ----------------------------------------------------------------
    //  Main
    // ----------------------------------------------------------------

    public static void main(String[] args) {
        Random rng = new Random(42); // Fixed seed for reproducibility
        double[][] qTable = train(rng);

        printPolicy(qTable);
        printQTableSnapshot(qTable, MAX_EPISODES);

        // Demonstrate the learned path
        System.out.println("\n=== Robot's Learned Path from Start to Target ===");
        int state = START_STATE;
        int steps = 0;
        while (state != TARGET_STATE && steps < 30) {
            int row = stateToRow(state);
            int col = stateToCol(state);
            int bestAction = 0;
            for (int a = 1; a < NUM_ACTIONS; a++) {
                if (qTable[state][a] > qTable[state][bestAction]) bestAction = a;
            }
            System.out.printf("  State %2d (%d,%d) → Action: %-6s%n",
                              state, row, col, ACTION_NAME[bestAction]);
            Object[] result = step(state, bestAction);
            state = (int) result[0];
            steps++;
        }
        System.out.printf("  State %2d (%d,%d) → TARGET REACHED in %d steps!%n",
                          state, stateToRow(state), stateToCol(state), steps);
    }
}

Sample Output

=== Starting Training ===
Episode    Total Reward Steps Taken  Epsilon   
--------------------------------------------------
1          -54.0        4            0.9950
50         -47.0        48           0.7783
100        -18.0        19           0.6050
250        -10.0        11           0.2873
500        8.0          9            0.0823
1000       91.0         9            0.0100

=== Learned Policy ===
(S=Start, T=Target, X=Forklift Zone)

 S  →  →  ↓  ↓ 
 →  X  →  ↓  ↓ 
 →  →  →  X  ↓ 
 →  X  →  →  ↓ 
 →  →  →  →  T 

Notice how Total Reward climbs from -54 to +91 across 1000 episodes, and Steps Taken drops from 48 to 9 — the robot isn't just reaching the goal more often, it's finding a near-optimal route.

Q-Table Convergence: How Values Change Over Episodes

State 0 (Start) — Best Action: RIGHT
─────────────────────────────────────────────
Episode   1:  UP=0.000  DOWN=0.000  LEFT=0.000  RIGHT=0.000
Episode  50:  UP=0.021  DOWN=0.134  LEFT=-0.120  RIGHT=0.289
Episode 500:  UP=0.412  DOWN=2.310  LEFT=-0.830  RIGHT=4.920
Episode 1000: UP=0.721  DOWN=4.110  LEFT=-1.204  RIGHT=18.43 ← RIGHT wins!

State 19 (one step left of target) — Best Action: RIGHT
─────────────────────────────────────────────
Episode   1:  All zeros
Episode  50:  RIGHT=0.045 (barely discovered)
Episode 500:  RIGHT=65.23 (strong signal — target is close!)
Episode 1000: RIGHT=94.87 (nearly +100 reward, discounted once)
  

Q-values near the target converge first — the reward signal radiates outward from the goal like ripples from a stone dropped in water. Early states (like Start) take many more episodes to accumulate accurate estimates because the +100 reward must be discounted across all the intervening steps before it reaches them.

---

Common Pitfalls and Debugging

1. Reward Shaping Mistakes

Problem: You give a large negative reward for every wall bump, but forget the agent is trapped against a wall — it keeps bumping and accumulates catastrophic negative rewards, never recovering.

Fix: Make wall bumps mildly negative (not catastrophic), and ensure the episode doesn't end on wall bumps. The robot should learn "walls are bad" naturally through the cumulative time penalty.

2. Learning Rate Woes

α too high (0.9) Values oscillate — the agent "forgets" good experiences because each new update overwrites them aggressively.

α too low (0.001) Thousands of episodes produce barely any change. The robot acts nearly randomly for too long.

α just right (0.05–0.2) Steady, smooth convergence. Values creep toward optimal over hundreds of episodes.

3. Discount Factor Edge Cases

• γ = 0: The robot is completely greedy. It'll pick up a +5 reward right next to it and ignore the +100 target 8 steps away. Useless for navigation.
• γ = 1: Every future reward is worth exactly as much as an immediate one. This can cause instability in environments with long episodes and no terminal state, as Q-values grow unboundedly.
• γ = 0.95: Sweet spot. A reward 20 steps away is worth 0.95²⁰ ≈ 36% of its face value — far enough to plan ahead, but decayed enough to prefer shorter paths.

4. The Q-Table Never Converges

If your Q-values are still wildly different between episodes after 10,000 runs, check:

• Epsilon isn't decaying: If ε stays high, the agent keeps exploring randomly and never exploits its learned knowledge.
• Environment is non-deterministic without proper handling: If transitions are stochastic but you're using a low α, the noise drowns the signal.
• Max steps too low: The agent can't reach the target before the episode terminates, so it never receives the positive terminal reward.

public class Main {
    static final int NUM_STATES = 10;
    static final int NUM_ACTIONS = 4;
    static double[][] qTable = new double[NUM_STATES][NUM_ACTIONS];
    static double[][] previousQTable = new double[NUM_STATES][NUM_ACTIONS];

    public static void main(String[] args) {
        int episode = 1;
        // Debugging tip: track TD error magnitude over episodes
        // If it plateaus above 1.0 after 1000 episodes, something is wrong
        double avgTDError = 0.0;
        for (int s = 0; s < NUM_STATES; s++) {
            for (int a = 0; a < NUM_ACTIONS; a++) {
                // Compare current estimates to previous episode's estimates
                avgTDError += Math.abs(qTable[s][a] - previousQTable[s][a]);
            }
        }
        System.out.printf("Episode %d | Avg Q-Change: %.4f%n", episode, avgTDError / (NUM_STATES * NUM_ACTIONS));
    }
}

---

Limitations and the Bridge to Deep Q-Networks

The State Space Explosion

Q-tables work beautifully when states are countable and small. Our warehouse had 25 states. But consider:

Problem	States	Q-Table Size
5×5 Warehouse	25	100 cells
20×20 Maze	400	1,600 cells
Atari Pong (raw pixels)	~10⁶	~4M cells
Autonomous Driving	~10¹⁸	Impossible
Chess	~10⁴⁷	More than atoms in universe

For real-world problems, you can't store every state explicitly. The Q-table hits a wall — and unlike our robot, it can't recover from it.

The DQN Solution

Instead of a giant lookup table, a Deep Q-Network (DQN) uses a neural network as a function approximator. The key insight: similar states should have similar Q-values. A neural network can learn that pattern and generalize — estimating Q-values for states it has never seen before, based on states it has.

Q-Table vs. Deep Q-Network

Input: State s (grid position)

→

Q-Table: lookup row s

→

Output: Q-values for all 4 actions

vs.

Input: State s (raw pixels, sensor data…)

→

Neural Network (Conv layers, Dense layers)

→

Output: Q-values for all actions

DQN replaces the table with a neural network. The network generalizes — states it has never seen get reasonable Q-value estimates based on similar states it has seen. The Bellman update becomes a supervised training signal for the network weights instead of a direct table write.

When Q-Tables Are Still the Right Tool

Don't reach for a neural network when you don't need one:

• Small state spaces Under ~10,000 states — pure Q-table wins on simplicity and interpretability
• Tabular data problems Game solvers for small board games (Tic-Tac-Toe has 5,478 states)
• Teaching/prototyping Always start with a Q-table to validate your reward structure before scaling up
• Medium spaces Consider tile coding or state aggregation to compress the table
• High-dimensional inputs Raw images, continuous sensor arrays — go straight to DQN

---

Recap: The 5 Steps

5 Steps to Master Q-Learning

1. Define Environment

→

2. Initialize Q-Table

→

3. ε-Greedy Policy

→

4. Episode Loop + Bellman Update

→

5. Extract Policy

Each step builds on the last. The magic happens in Step 4 — thousands of small Bellman corrections accumulate into a table of hard-won wisdom.

1. Define your environment — states, actions, and reward signals carefully
2. Initialize the Q-Table to zeros and track your hyperparameters (α, γ, ε)
3. Implement epsilon-greedy — start with full exploration and decay toward exploitation
4. Run episodes — each step applies the Bellman update, propagating reward signals backwards
5. Extract the policy — read the argmax of each row; that's the learned strategy

The Q-Table is one of AI's most elegant ideas: a simple matrix that emerges from experience to encode optimal behavior. It's the foundation everything from game-playing AIs to robotics schedulers is built on — and now you can build it yourself.

---

Want to go further? In the next post, we'll extend this exact warehouse robot to use a neural network for the Q-function — turning our Q-Table agent into a full Deep Q-Network (DQN) that can handle environments 1,000x larger.

Four Ways to Split Sentences (Without Machine Learning)

Imagine you hand someone a giant wall of text — no paragraph breaks, no structure — and ask them to read it aloud naturally. They'd instinctively pause at every period, question mark, or exclamation point[cite: 1]. That pause, that boundary between thoughts, is what sentence splitting (also called sentence boundary detection or sentence segmentation) is all about[cite: 1].

Sentence Splitting in the NLP Pipeline

1. Sentence Splitting

→

2. Tokenization

→

3. POS Tagging

→

4. Parsing / Translation

Sentence segmentation acts as the foundational preprocessing stage for downstream NLP tasks.

In NLP pipelines, sentence splitting is often the very first step before anything else — tokenization, parsing, translation, summarization[cite: 1]. If you get it wrong, everything downstream suffers[cite: 1].

The good news? You don't always need a neural network to do it well[cite: 1]. In this post, we'll explore four classical, rule-based approaches to sentence splitting — from the simplest one-liner to surprisingly robust heuristic systems — all without a single line of machine learning[cite: 1].

---

Why Is Sentence Splitting Hard?

Before diving in, let's appreciate why this isn't trivial[cite: 1]. Consider these tricky cases[cite: 1]:

• "Dr. Smith went to Washington D.C. last Monday." 3 Periods • 1 Sentence — Multiple periods within honorifics and city names[cite: 1].
• "She asked, \"Are you coming?\" He nodded." 2 Sentences — Nested punctuation inside direct quotation marks[cite: 1].
• "The price is $1.99. Buy now!" 1 Decimal • 2 Sentences — Decimal point within currency[cite: 1].
• "I work at A.I. Corp. We build robots." 2 Sentences — Abbreviation ending directly at sentence boundary[cite: 1].
• "...and that's it." Ellipsis — Multi-period sequences[cite: 1].

A naïve "split on period" approach would butcher all of these[cite: 1]. Each method we explore will get progressively better at handling such edge cases[cite: 1].

---

Method 1: Naïve Punctuation Split

The Idea

The simplest possible approach: split the text every time you see ., ?, or ![cite: 1].

Think of it like cutting a ribbon every time you see a knot[cite: 1]. Fast, simple — but sometimes you cut in the wrong place[cite: 1].

Naïve splitting truncates honorifics like "Dr." as isolated sentences[cite: 1].

Java Implementation

import java.util.Arrays;
import java.util.List;

public class NaiveSentenceSplitter {

    public static List<String> split(String text) {
        // Split on . ? or ! followed by one or more spaces
        String[] parts = text.split("(?<=[.?!])\\s+");
        return Arrays.asList(parts);
    }

    public static void main(String[] args) {
        String text = "Hello world. How are you? I am fine! Thanks.";
        List<String> sentences = split(text);
        for (String s : sentences) {
            System.out.println("|" + s + "|");
        }
    }
}

Output:

|Hello world.|
|How are you?|
|I am fine!|
|Thanks.|

Looks perfect for clean text[cite: 1]. But watch what happens with abbreviations[cite: 1]:

String tricky = "Dr. Smith lives on Oak St. He owns a cat.";
// Output:
// |Dr.|
// |Smith lives on Oak St.|
// |He owns a cat.|

Oops[cite: 1]. Dr. got split off as its own sentence[cite: 1].

When to Use It

• Clean, well-formatted text (e.g., generated text, templates)[cite: 1]
• Quick prototyping when accuracy isn't critical[cite: 1]
• Pre-processing step before a smarter method[cite: 1]

---

Method 2: Abbreviation-Aware Splitting

The Idea

The naïve method fails because it doesn't know that certain words followed by a period are abbreviations, not sentence endings[cite: 1]. The fix: maintain a blocklist of known abbreviations and skip splitting when the period belongs to one[cite: 1].

This is like a train conductor who knows certain stops are "request stops" — the train doesn't halt there unless specifically needed[cite: 1].

Abbreviation lookup workflow preventing invalid sentence splits[cite: 1].

C++ Implementation

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <unordered_set>
#include <algorithm>
#include <cctype>

// Lowercase a string
std::string toLower(const std::string& s) {
    std::string result = s;
    std::transform(result.begin(), result.end(), result.begin(), ::tolower);
    return result;
}

// Known abbreviations (lowercase, without the period)
std::unordered_set<std::string> ABBREVIATIONS = {
    "dr", "mr", "mrs", "ms", "prof", "sr", "jr",
    "st", "ave", "blvd", "dept", "approx", "vs",
    "etc", "e.g", "i.e", "fig", "jan", "feb",
    "mar", "apr", "jun", "jul", "aug", "sep",
    "oct", "nov", "dec", "no", "vol", "pp"
};

std::vector<std::string> splitSentences(const std::string& text) {
    std::vector<std::string> sentences;
    std::string current;
    int n = text.size();

    for (int i = 0; i < n; i++) {
        current += text[i];

        // Check if we're at a sentence-ending punctuation
        if (text[i] == '.' || text[i] == '?' || text[i] == '!') {

            // Look ahead: is the next character a space followed by uppercase?
            if (i + 2 < n && text[i + 1] == ' ' &&
                std::isupper((unsigned char)text[i + 2])) {

                // Extract the word just before the period
                std::string word;
                int j = current.size() - 2; // -2 to skip the period we just added
                while (j >= 0 && current[j] != ' ') {
                    word = current[j] + word;
                    j--;
                }

                // Check if it's a known abbreviation
                if (ABBREVIATIONS.count(toLower(word)) == 0) {
                    // Not an abbreviation — it's a sentence boundary!
                    sentences.push_back(current);
                    current = "";
                    i++; // Skip the space
                }
            }
        }
    }

    // Don't forget the last sentence
    if (!current.empty()) {
        sentences.push_back(current);
    }

    return sentences;
}

int main() {
    std::string text = "Dr. Smith lives on Oak St. He owns a cat. "
                       "Prof. Lee moved to Washington D.C. last year.";

    auto sentences = splitSentences(text);
    for (const auto& s : sentences) {
        std::cout << "[" << s << "]" << std::endl;
    }
    return 0;
}

Output:

[Dr. Smith lives on Oak St. He owns a cat.]
[Prof. Lee moved to Washington D.C. last year.]

Much better! The abbreviation list acts as a safety net for the most common offenders[cite: 1].

Limitations

• Your abbreviation list will never be complete[cite: 1].
• Single capital letters (A., B.) can still trip it up[cite: 1].
• Doesn't handle quotes, parentheses, or numbering well[cite: 1].

When to Use It

• Domain-specific text where you know common abbreviations (medical, legal, scientific)[cite: 1]
• When you can afford to curate and maintain an abbreviation list[cite: 1]

---

Method 3: Regex-Based Heuristic Splitter

The Idea

Instead of a simple split, we use regular expressions to encode multiple heuristic rules simultaneously[cite: 1]:

1. A sentence ends with ., ?, or ![cite: 1]
2. Followed by whitespace[cite: 1]
3. Followed by an uppercase letter or a quote/parenthesis opening a new sentence[cite: 1]
4. BUT NOT when the word before the period is a known abbreviation or a single letter (initials)[cite: 1]

Think of it like a traffic light system: instead of just checking one condition ("is it a period?"), we check multiple signals before deciding to stop[cite: 1].

Java Implementation

import java.util.*;
import java.util.regex.*;

public class RegexSentenceSplitter {

    // These patterns will NOT trigger a split
    private static final Set<String> ABBREVIATIONS = new HashSet<>(Arrays.asList(
        "dr", "mr", "mrs", "ms", "prof", "sr", "jr", "st", "ave",
        "blvd", "dept", "approx", "vs", "etc", "fig", "no", "vol"
    ));

    /**
     * Returns true if the word before the period looks like an abbreviation
     * or a single initial (e.g., "A.", "B.")
     */
    private static boolean isAbbreviation(String word) {
        String lower = word.toLowerCase();
        if (ABBREVIATIONS.contains(lower)) return true;
        if (word.length() == 1 && Character.isLetter(word.charAt(0))) return true; // Initials
        if (word.matches("[A-Z]([a-z]*[A-Z])+")) return true; // Acronym like "U.S.A"
        return false;
    }

    public static List<String> split(String text) {
        List<String> sentences = new ArrayList<>();

        // Regex: sentence boundary = punctuation + space(s) + uppercase or quote/paren
        // We use a lookahead so we don't consume the start of the next sentence
        Pattern boundary = Pattern.compile(
            "(?<=[.?!]['\"]?)" +   // after . ? ! optionally followed by closing quote
            "\\s+" +                // whitespace
            "(?=[A-Z\"\\(])"        // before uppercase letter, quote, or open paren
        );

        // Split on candidate boundaries
        String[] candidates = boundary.split(text);

        StringBuilder current = new StringBuilder();
        for (int i = 0; i < candidates.length; i++) {
            String part = candidates[i];

            // Get the last word of this part (before the terminal punctuation)
            String trimmed = part.trim();
            String lastWord = "";
            int lastSpace = trimmed.lastIndexOf(' ', trimmed.length() - 2);
            if (lastSpace >= 0) {
                // Remove the punctuation to get the actual word
                lastWord = trimmed.substring(lastSpace + 1);
                if (lastWord.endsWith(".") || lastWord.endsWith("?") || lastWord.endsWith("!")) {
                    lastWord = lastWord.substring(0, lastWord.length() - 1);
                }
            }

            current.append(part);

            if (isAbbreviation(lastWord)) {
                // Don't split — it's an abbreviation; keep building
                current.append(" ");
            } else {
                // Real sentence boundary
                sentences.add(current.toString().trim());
                current = new StringBuilder();
            }
        }

        if (current.length() > 0) {
            sentences.add(current.toString().trim());
        }

        return sentences;
    }

    public static void main(String[] args) {
        String text = "Dr. Smith visited Washington D.C. last Monday. "
                    + "\"Was it fun?\" asked Ms. Jones. He said yes! "
                    + "The price was $1.99. She paid immediately.";

        List<String> sentences = split(text);
        for (int i = 0; i < sentences.size(); i++) {
            System.out.printf("[%d] %s%n", i + 1, sentences.get(i));
        }
    }
}

Output:

[1] Dr. Smith visited Washington D.C. last Monday.
[2] "Was it fun?" asked Ms. Jones.
[3] He said yes!
[4] The price was $1.99.
[5] She paid immediately.

Breaking Down the Regex

(?<=[.?!]['"]?)   — lookbehind: we just passed a . ? or ! (optionally + closing quote)
\s+               — whitespace: one or more space characters
(?=[A-Z"\(])      — lookahead: next char is uppercase, a quote, or open parenthesis
  

Using lookahead and lookbehind (zero-width assertions) means we split at the whitespace without consuming the surrounding characters — perfect for keeping sentence punctuation attached to the right sentence[cite: 1].

When to Use It

• General-purpose text without extreme edge cases[cite: 1]
• When you want a balance of simplicity and accuracy[cite: 1]
• As a fast pre-processing step in an NLP pipeline[cite: 1]

---

Method 4: Finite State Machine (FSM) Splitter

The Idea

This is the most robust rule-based approach[cite: 1]. We model the sentence-splitting process as a Finite State Machine — a system that moves through a set of states as it reads characters one by one[cite: 1].

Think of it like reading a book with a bookmark and a set of sticky notes[cite: 1]. Each sticky note represents a "state" you're currently in (e.g., inside a quote, just saw a period, inside a number)[cite: 1]. As you read each character, you check your current state and decide whether to move to a new state[cite: 1].

Interactive State Machine Transition Diagram

This visual models how character input triggers state shifts in real time:

States in Our FSM

NORMAL          — reading regular sentence content
AFTER_PERIOD    — just saw a period (potential sentence end)
IN_QUOTE        — inside a double-quoted string
IN_NUMBER       — inside a decimal number (e.g., 3.14)
BOUNDARY        — confirmed sentence boundary (emit the sentence)

C Implementation

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#define MAX_SENTENCE_LEN 4096
#define MAX_SENTENCES    1024

typedef enum {
    STATE_NORMAL,
    STATE_AFTER_TERMINAL,  // After . ? !
    STATE_IN_QUOTE,
    STATE_IN_PARENS
} State;

// Check if a word is a likely abbreviation
int isAbbreviation(const char* word) {
    // Single capital letter (initial)
    if (strlen(word) == 1 && isupper((unsigned char)word[0])) return 1;

    // Common abbreviations
    const char* abbrevs[] = {
        "dr", "mr", "mrs", "ms", "prof", "sr", "jr",
        "st", "ave", "blvd", "no", "vol", "vs",
        "jan", "feb", "mar", "apr", "jun", "jul",
        "aug", "sep", "oct", "nov", "dec", NULL
    };

    char lower[64];
    int i;
    for (i = 0; word[i] && i < 63; i++)
        lower[i] = tolower((unsigned char)word[i]);
    lower[i] = '\0';

    for (int j = 0; abbrevs[j] != NULL; j++) {
        if (strcmp(lower, abbrevs[j]) == 0) return 1;
    }
    return 0;
}

// Extract the last complete word from a buffer (strip trailing punctuation)
void getLastWord(const char* buffer, int len, char* word) {
    word[0] = '\0';
    // Go backwards past punctuation and spaces
    int end = len - 1;
    while (end >= 0 && (ispunct((unsigned char)buffer[end]) || isspace((unsigned char)buffer[end])))
        end--;

    // Now go backwards to find the start of the word
    int start = end;
    while (start > 0 && !isspace((unsigned char)buffer[start - 1]))
        start--;

    if (start <= end) {
        strncpy(word, buffer + start, end - start + 1);
        word[end - start + 1] = '\0';
    }
}

int splitSentences(const char* text, char sentences[][MAX_SENTENCE_LEN]) {
    State state = STATE_NORMAL;
    char buffer[MAX_SENTENCE_LEN];
    int bufLen = 0;
    int sentCount = 0;
    int n = strlen(text);
    char lastWord[64];

    for (int i = 0; i < n; i++) {
        char c = text[i];
        char next = (i + 1 < n) ? text[i + 1] : '\0';
        char nextNext = (i + 2 < n) ? text[i + 2] : '\0';

        buffer[bufLen++] = c;
        buffer[bufLen] = '\0';

        switch (state) {
            case STATE_NORMAL:
                if (c == '"') {
                    state = STATE_IN_QUOTE;
                } else if (c == '(') {
                    state = STATE_IN_PARENS;
                } else if ((c == '.' || c == '?' || c == '!')) {
                    state = STATE_AFTER_TERMINAL;
                }
                break;

            case STATE_AFTER_TERMINAL:
                if (isspace((unsigned char)c) && isupper((unsigned char)next)) {
                    // Potential boundary — check for abbreviation
                    getLastWord(buffer, bufLen - 1, lastWord); // -1 to ignore space
                    if (!isAbbreviation(lastWord)) {
                        // Emit the sentence (up to and including the punctuation)
                        // Trim trailing space
                        int end = bufLen - 1;
                        while (end > 0 && isspace((unsigned char)buffer[end - 1])) end--;
                        buffer[end] = '\0';
                        strncpy(sentences[sentCount++], buffer, MAX_SENTENCE_LEN - 1);
                        bufLen = 0;
                        buffer[0] = '\0';
                        state = STATE_NORMAL;
                    } else {
                        state = STATE_NORMAL;
                    }
                } else if (c == '"') {
                    state = STATE_IN_QUOTE;
                } else if (!isspace((unsigned char)c)) {
                    // Something other than space — back to normal (e.g., "1.5x")
                    state = STATE_NORMAL;
                }
                break;

            case STATE_IN_QUOTE:
                if (c == '"') {
                    state = STATE_NORMAL;
                }
                break;

            case STATE_IN_PARENS:
                if (c == ')') {
                    state = STATE_NORMAL;
                }
                break;
        }
    }

    // Flush remaining text as the last sentence
    if (bufLen > 0) {
        strncpy(sentences[sentCount++], buffer, MAX_SENTENCE_LEN - 1);
    }

    return sentCount;
}

int main() {
    const char* text =
        "Dr. Smith visited D.C. on Monday. "
        "The ratio was 1.5 to 1. It was significant! "
        "He said \"This is fine. Really.\" before leaving. "
        "Ms. Jones (his colleague) agreed. She smiled.";

    char sentences[MAX_SENTENCES][MAX_SENTENCE_LEN];
    int count = splitSentences(text, sentences);

    printf("Found %d sentences:\n\n", count);
    for (int i = 0; i < count; i++) {
        printf("[%d] %s\n", i + 1, sentences[i]);
    }
    return 0;
}

Output:

Found 5 sentences:

[1] Dr. Smith visited D.C. on Monday.
[2] The ratio was 1.5 to 1. It was significant!
[3] He said "This is fine. Really." before leaving.
[4] Ms. Jones (his colleague) agreed.
[5] She smiled.

How the FSM Works — Step by Step

Let's trace through "1.5 to 1. It was" character by character[cite: 1]:

'1'  → STATE_NORMAL,         buffer: "1"
'.'  → STATE_AFTER_TERMINAL, buffer: "1."
'5'  → not space+uppercase → STATE_NORMAL, buffer: "1.5"   ← decimal, no split!
' '  → STATE_NORMAL,         buffer: "1.5 "
't'  → STATE_NORMAL,         buffer: "1.5 t"
...
'1'  → STATE_NORMAL,         buffer: "1.5 to 1"
'.'  → STATE_AFTER_TERMINAL, buffer: "1.5 to 1."
' '  → space! next='I' (uppercase)...
       lastWord = "1" → not an abbreviation!
       EMIT SENTENCE: "1.5 to 1."
       reset buffer, STATE_NORMAL
'I'  → STATE_NORMAL,         buffer: "I"
...

When to Use It

• When you need the most accurate rule-based approach[cite: 1]
• Complex documents: legal contracts, academic papers, news articles[cite: 1]
• When you want fine-grained control over every splitting decision[cite: 1]
• As the foundation for a custom domain-specific splitter[cite: 1]

---

Comparison Table

Method	Speed	Accuracy	Handles Abbrevs	Handles Quotes	Complexity
Naïve Punctuation Split	⚡ Very Fast	❌ Low	❌ No	❌ No	🟢 Trivial
Abbreviation-Aware	⚡ Fast	🟡 Medium	✅ Yes	❌ No	🟡 Easy
Regex Heuristic	⚡ Fast	🟡 Good	✅ Yes	✅ Partial	🟡 Moderate
FSM-Based	🟢 Fast	✅ Best (rule-based)	✅ Yes	✅ Yes	🔴 More Complex

---

Choosing the Right Method

Here's a decision matrix to help choose the best approach for your project[cite: 1]:

---

Tips for Improving Any Rule-Based Splitter

1. Handle ellipses (...) — they rarely end sentences mid-paragraph[cite: 1].
2. Track parenthesis depth — text inside (like this. Really.) should not be split[cite: 1].
3. Handle numbered lists — "1. First item 2. Second item" should not split at 1.[cite: 1].
4. Normalize whitespace first — collapse multiple spaces, replace \t and \n[cite: 1].
5. Post-process short fragments — if a "sentence" is only 1-2 characters, it's probably a false split[cite: 1].

---

Final Thoughts

Sentence splitting is one of those problems that looks trivially easy until you try it on real-world text[cite: 1]. The journey from a one-liner split(".") to a full FSM with state tracking mirrors a broader truth in NLP: language is full of exceptions, and robust systems are built by systematically handling them one by one[cite: 1].

Key Takeaway: Rule-based methods are transparent, fast, and debuggable[cite: 1]. When an FSM makes a wrong call, you can trace the exact logic path and fix it instantly — without retraining a neural model[cite: 1].

That said, for truly noisy or ambiguous text (social media posts, OCR output, multilingual documents), machine learning models will outperform rules[cite: 1]. But for structured documents in a known domain, a well-crafted FSM splitter can be hard to beat[cite: 1].

Happy splitting! 🔪📄

Beam Search: The Algorithm Behind LLM Text Generation

When a Large Language Model (LLM) like GPT generates text, it doesn't simply pick the single most probable next word at every step. Doing so — known as greedy decoding — often leads to repetitive, suboptimal, or even incoherent outputs. Instead, most production-grade language models use a smarter strategy called Beam Search.

In this post, we'll break down:

• What Beam Search is and why it exists
• How it compares to Greedy and Exhaustive search
• The step-by-step algorithm with a visual walkthrough
• A full implementation in Java and C++
• Its strengths, weaknesses, and modern variants

---

The Problem: Decoding from a Language Model

A language model assigns a probability to every possible next token given the preceding context:

P(token | previous tokens)

Generating a complete sequence means making a chain of these decisions. The goal is to find the sequence with the highest joint probability:

P(w1, w2, ..., wN) = P(w1) × P(w2|w1) × P(w3|w1,w2) × ...

Search Space Explosion: If your vocabulary has V words and you generate sequences of length N, there are V^N possible sequences. For V = 50,000 and N = 20, that's astronomically large. This is why we need smart search heuristics.

---

Approach 1: Greedy Search

Greedy search picks the single most probable token at every step.

At each step t: choose token = argmax P(token | context)

Why Greedy Fails

Consider generating a sentence where:

• Step 1: "The" → 0.4 (highest)
• Step 2 given "The": "cat" → 0.3 (highest)
• Step 3 given "The cat": "sat" → 0.2 (highest)

But an alternative path exists:

• Step 1: "A" → 0.35
• Step 2 given "A": "beautiful" → 0.6
• Step 3 given "A beautiful": "sunset" → 0.9

Joint probability of greedy path: 0.4 × 0.3 × 0.2 = 0.024
Joint probability of better path: 0.35 × 0.6 × 0.9 = 0.189

Greedy search misses the better path because it committed too early.

---

Approach 2: Exhaustive Search

Exhaustive search explores all possible sequences and picks the best one. It is optimal but computationally infeasible for any realistic vocabulary and sequence length.

---

Approach 3: Beam Search — The Sweet Spot

Beam Search is a heuristic best-first search that keeps track of the top-K most promising partial sequences (called the "beam") at each step, where K is the beam width.

Key Idea

• At each step, expand every sequence in the beam by all possible next tokens.
• Score each expanded sequence.
• Keep only the top-K scoring sequences for the next step.
• Repeat until all sequences hit an end token or max length.

This gives us a controllable trade-off:

• K = 1 → Equivalent to Greedy Search
• K = ∞ → Equivalent to Exhaustive Search
• K = 5 to 20 → Practical sweet spot used in real systems

---

Step-by-Step Visual Walkthrough

Let's trace Beam Search with beam width K=2 and a tiny vocabulary: {A, B, C, <END>}.

Step 0 — Initialization

Beam: [ ([], score=0.0) ]

We start with one empty sequence.

Step 1 — Expand

Expand the empty sequence with all tokens:

Candidates:
  [A]     → log P(A)     = -0.9
  [B]     → log P(B)     = -0.5   ✓ keep
  [C]     → log P(C)     = -1.2
  [<END>] → log P(<END>) = -2.0

After keeping top-2:

Beam: [ ([B], -0.5), ([A], -0.9) ]

Step 2 — Expand Each Beam Member

Expand [B]:

  [B, A]     → -0.5 + -1.1 = -1.6
  [B, B]     → -0.5 + -0.4 = -0.9   ✓
  [B, C]     → -0.5 + -0.7 = -1.2   ✓
  [B, <END>] → -0.5 + -1.5 = -2.0

Expand [A]:

  [A, A]     → -0.9 + -0.8 = -1.7
  [A, B]     → -0.9 + -0.6 = -1.5
  [A, C]     → -0.9 + -0.3 = -1.2   (tied)
  [A, <END>] → -0.9 + -2.1 = -3.0

All 8 candidates are ranked, top-2 kept:

Beam: [ ([B, B], -0.9), ([B, C], -1.2) ]

This process continues until <END> tokens are generated or maximum length is reached. The sequence with the highest cumulative log-probability is the final output.

---

Why Log Probabilities?

Multiplying many small probabilities leads to numerical underflow. By working in log space, we convert multiplications into additions:

log(P1 × P2 × P3) = log(P1) + log(P2) + log(P3)

Higher (less negative) log-probability = better sequence.

---

Java Implementation

Here's a clean, self-contained Beam Search implementation in Java.

import java.util.*;

public class BeamSearch {

    static double[][] logProbTable = {
        /* step 0 */ {-0.9, -0.5, -1.2, -2.0},
        /* step 1 */ {-1.1, -0.4, -0.7, -1.5},
        /* step 2 */ {-0.8, -0.6, -0.3, -1.0},
        /* step 3 */ {-1.3, -0.9, -0.5, -0.4},
    };

    static String[] vocab = {"A", "B", "C", "<END>"};
    static int END_TOKEN = 3;

    static class Hypothesis implements Comparable<Hypothesis> {
        List<Integer> tokens;
        double score; 
        boolean finished;

        Hypothesis(List<Integer> tokens, double score, boolean finished) {
            this.tokens = new ArrayList<>(tokens);
            this.score = score;
            this.finished = finished;
        }

        @Override
        public int compareTo(Hypothesis other) {
            return Double.compare(other.score, this.score);
        }

        public String toStringSequence() {
            StringBuilder sb = new StringBuilder();
            for (int t : tokens) {
                sb.append(vocab[t]).append(" ");
            }
            return sb.toString().trim();
        }
    }

    static double[] getLogProbs(List<Integer> context) {
        int step = Math.min(context.size(), logProbTable.length - 1);
        return logProbTable[step];
    }

    static List<Hypothesis> beamSearch(int beamWidth, int maxLength) {
        List<Hypothesis> beam = new ArrayList<>();
        beam.add(new Hypothesis(new ArrayList<>(), 0.0, false));

        List<Hypothesis> completedSequences = new ArrayList<>();

        for (int step = 0; step < maxLength; step++) {
            List<Hypothesis> candidates = new ArrayList<>();

            for (Hypothesis hyp : beam) {
                if (hyp.finished) {
                    candidates.add(hyp);
                    continue;
                }

                double[] logProbs = getLogProbs(hyp.tokens);

                for (int tokenId = 0; tokenId < vocab.length; tokenId++) {
                    List<Integer> newTokens = new ArrayList<>(hyp.tokens);
                    newTokens.add(tokenId);
                    double newScore = hyp.score + logProbs[tokenId];
                    boolean isFinished = (tokenId == END_TOKEN);

                    candidates.add(new Hypothesis(newTokens, newScore, isFinished));
                }
            }

            Collections.sort(candidates);

            beam = new ArrayList<>();
            for (int i = 0; i < Math.min(beamWidth, candidates.size()); i++) {
                Hypothesis h = candidates.get(i);
                if (h.finished) {
                    completedSequences.add(h);
                } else {
                    beam.add(h);
                }
            }

            if (beam.isEmpty()) break;
        }

        completedSequences.addAll(beam);
        Collections.sort(completedSequences);
        return completedSequences;
    }

    public static void main(String[] args) {
        List<Hypothesis> results = beamSearch(2, 4);
        for (int i = 0; i < Math.min(3, results.size()); i++) {
            Hypothesis h = results.get(i);
            System.out.printf("Rank %d: %-25s score=%.4f%n", i + 1, h.toStringSequence(), h.score);
        }
    }
}

---

C++ Implementation

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

const vector<string> vocab = {"A", "B", "C", "<END>"};
const int END_TOKEN = 3;
const int VOCAB_SIZE = 4;

const double logProbTable[4][4] = {
    {-0.9, -0.5, -1.2, -2.0},
    {-1.1, -0.4, -0.7, -1.5},
    {-0.8, -0.6, -0.3, -1.0},
    {-1.3, -0.9, -0.5, -0.4},
};

struct Hypothesis {
    vector<int> tokens;
    double score;
    bool finished;

    Hypothesis(vector<int> t, double s, bool f) : tokens(t), score(s), finished(f) {}

    bool operator<(const Hypothesis& other) const {
        return score < other.score;
    }
};

const double* getLogProbs(const vector<int>& context) {
    int step = min((int)context.size(), 3);
    return logProbTable[step];
}

vector<Hypothesis> beamSearch(int beamWidth, int maxLength) {
    vector<Hypothesis> beam;
    beam.emplace_back(vector<int>{}, 0.0, false);
    vector<Hypothesis> completed;

    for (int step = 0; step < maxLength; step++) {
        vector<Hypothesis> candidates;

        for (const Hypothesis& hyp : beam) {
            if (hyp.finished) {
                candidates.push_back(hyp);
                continue;
            }

            const double* logProbs = getLogProbs(hyp.tokens);

            for (int tokenId = 0; tokenId < VOCAB_SIZE; tokenId++) {
                vector<int> newTokens = hyp.tokens;
                newTokens.push_back(tokenId);
                double newScore = hyp.score + logProbs[tokenId];
                bool isFinished = (tokenId == END_TOKEN);
                candidates.emplace_back(newTokens, newScore, isFinished);
            }
        }

        sort(candidates.begin(), candidates.end(), [](const Hypothesis& a, const Hypothesis& b) {
            return a.score > b.score;
        });

        beam.clear();
        for (int i = 0; i < min(beamWidth, (int)candidates.size()); i++) {
            if (candidates[i].finished) {
                completed.push_back(candidates[i]);
            } else {
                beam.push_back(candidates[i]);
            }
        }

        if (beam.empty()) break;
    }

    for (auto& h : beam) completed.push_back(h);
    sort(completed.begin(), completed.end(), [](const Hypothesis& a, const Hypothesis& b) {
        return a.score > b.score;
    });

    return completed;
}

---

Complexity Analysis

Approach	Time Complexity	Space Complexity	Quality
Greedy Search	O(N × V)	O(N)	Poor
Beam Search (width K)	O(N × K × V)	O(K × N)	Good
Exhaustive Search	O(V^N)	O(V^N)	Optimal

Where: N = sequence length, V = vocabulary size, and K = beam width. Beam Search is linear in both N and K, making it extremely practical.

---

Length Normalization

A critical issue with raw log-probability scoring: longer sequences always have lower (more negative) cumulative scores because we're adding more negative numbers. This biases beam search toward shorter sequences.

The fix is length normalization:

normalized_score = cumulative_log_prob / (sequence_length ^ α)

Where α (typically 0.6–0.8) controls how much to penalize/reward length.

// Length-normalized score calculation
double normalizedScore(double cumulativeLogProb, int length, double alpha) {
    double lengthPenalty = Math.pow(length, alpha);
    return cumulativeLogProb / lengthPenalty;
}

---

Beam Search in Real LLMs

Here's how Beam Search fits into the actual text generation pipeline:

---

Limitations of Beam Search

• Exposure Bias: Mismatch between training (ground-truth context) and inference (generated context).
• Generic / Boring Outputs: Prefers safer, common phrases over creative paths.
• Repetition: Can looped word patterns ("the the the...") without n-gram repetition penalties.
• Not Globally Optimal: Being a heuristic with finite K, it can still miss the true optimal sequence.

---

Modern Alternatives and Extensions

Method	Description	Best For
Greedy	Pick argmax at each step	Speed-critical, draft generation
Beam Search	Keep top-K beams	Machine translation, summarization
Top-K Sampling	Sample from top-K tokens	Creative text generation
Top-P (Nucleus) Sampling	Sample from top-P probability mass	Chatbots, story generation
Temperature Scaling	Sharpen/flatten probability distribution	Controlling creativity
Diverse Beam Search	Penalize similar beams	Getting varied outputs
Constrained Beam Search	Force certain tokens to appear	Template-guided generation

---

Conclusion

Beam Search is one of the most elegant solutions to the sequence decoding problem — a principled middle ground between the recklessness of Greedy Search and the infeasibility of Exhaustive Search. By maintaining a small set of the most promising partial sequences at every step, it finds high-quality outputs efficiently.

Happy coding — and may your beams always converge on the right answer! 🚀

Harnessing Sentiment Analysis with Java: A Step-by-Step Guide using NLP

Sentiment analysis, a powerful application of Natural Language Processing (NLP), allows developers to gain insights into the emotions expressed in textual data. In this article, we'll explore how to perform sentiment analysis in Java using the Stanford NLP library. We'll guide you through setting up a Maven project, compiling the code, and running it with practical examples.

Prerequisites

Get IntelliJ Idea from https://www.jetbrains.com/idea/download. 

You can skip this and use any other IDE as well. The steps for setting up a maven project will be different for each IDE.

Step 1: Create a New Project

• Open IntelliJ IDEA and click on "Create New Project." 
• Choose "Maven" as the project type and click "Next." 
• Set the "GroupId" to com.simplestcodings and "ArtifactId" to SentimentAnalysis. 
• Click "Next" and then "Finish." 

Step 2: Add Dependencies

Open the pom.xml file in the editor and replace the content with this section:

<?xml version="1.0" encoding="UTF-8"?>
<project xmlns="http://maven.apache.org/POM/4.0.0"
         xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
         xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
    <modelVersion>4.0.0</modelVersion>

    <groupId>com.simplestcodings</groupId>
    <artifactId>nlp</artifactId>
    <version>1.0-SNAPSHOT</version>

    <properties>
        <maven.compiler.source>17</maven.compiler.source>
        <maven.compiler.target>17</maven.compiler.target>
        <project.build.sourceEncoding>UTF-8</project.build.sourceEncoding>
    </properties>

    <dependencies>
        <dependency>
            <groupId>edu.stanford.nlp</groupId>
            <artifactId>stanford-corenlp</artifactId>
            <version>4.5.6</version>
        </dependency>
        <dependency>
            <groupId>edu.stanford.nlp</groupId>
            <artifactId>stanford-corenlp</artifactId>
            <version>4.5.6</version>
            <classifier>models</classifier>
        </dependency>
        <dependency>
            <groupId>org.slf4j</groupId>
            <artifactId>slf4j-simple</artifactId>
            <version>1.7.32</version>
        </dependency>
        <dependency>
            <groupId>org.projectlombok</groupId>
            <artifactId>lombok</artifactId>
            <version>1.18.30</version>
            <scope>provided</scope>
        </dependency>
    </dependencies>

</project>

Step 3: Create Project Structure

• Right-click on the src directory in your project and choose "New" -> "Package." 
• Name it com.simplestcodings. 
• Inside the com.simplestcodings package, create a new Java class named SentimentAnalysis. 

Step 4: Configure Properties

Right-click on the src directory and create a new directory named resources. Inside the resources directory, create a file named application.properties with the following content:

tokenize.whitespace=true
ssplit.eolonly=true
annotators = tokenize, ssplit, parse, sentiment

Step 5: Write Code

Replace the contents of SentimentAnalysis.java with the code provided below

package com.simplestcodings;

import edu.stanford.nlp.ling.CoreAnnotations;
import edu.stanford.nlp.pipeline.Annotation;
import edu.stanford.nlp.pipeline.StanfordCoreNLP;
import edu.stanford.nlp.sentiment.SentimentCoreAnnotations;
import edu.stanford.nlp.util.CoreMap;
import lombok.extern.slf4j.Slf4j;

@Slf4j
public class SentimentAnalysis {

    public static void main(String[] args) {
        // Initialize the Stanford NLP pipeline
        StanfordCoreNLP pipeline = new StanfordCoreNLP("application.properties");

        // Sample text for sentiment analysis
        String text = "Simplest codings is the best place to learn and grow. I am glad to be here.";

        // Perform sentiment analysis
        String sentiment = getSentiment(text, pipeline);

        // Display the result
        log.info("Text: {}, Sentiment: {}",text, sentiment);

        // Another Sample text for sentiment analysis
        text = "I hate this place. I am not coming back here again. I am very disappointed.";

        // Perform sentiment analysis
        sentiment = getSentiment(text, pipeline);

        // Display the result
        log.info("Text: {}, Sentiment: {}",text, sentiment);
    }

    private static String getSentiment(String text, StanfordCoreNLP pipeline) {
        // Create an Annotation object with the input text
        Annotation annotation = new Annotation(text);

        // Run all the NLP annotators on the text
        pipeline.annotate(annotation);

        // Extract the sentiment from the annotation
        CoreMap sentence = annotation.get(CoreAnnotations.SentencesAnnotation.class).get(0);
        String sentiment = sentence.get(SentimentCoreAnnotations.SentimentClass.class);

        return sentiment;
    }
}

Step 6: Run the Code

Right-click on the SentimentAnalysis class and select "Run SentimentAnalysis.main()". Observe the output in the Run console, which should display the sentiment of the provided text.

You have successfully set up and run a sentiment analysis Java project using the Stanford NLP library in IntelliJ IDEA. Feel free to explore more examples and experiment with different texts to gain insights into the sentiment analysis capabilities of Java and NLP. Happy coding!