# Q-Learning

Learning the value of taking an action in a state by bootstrapping from observed rewards, without needing a model of the environment.

**Rests on:** Markov Decision Processes

*Machine Learning · Reinforcement Learning*


## Why learn this

Q-learning teaches you how to find the best course of action when you do not know the rules of the game and cannot predict the consequences of your moves. Consider a delivery driver in a city they have never visited before. They do not have a map, and traffic conditions are unpredictable. The only way they know if a turn is good is by arriving at their destination quickly. Q-learning describes the mathematical process a system uses to learn from these arrivals and departures until it can navigate efficiently without prior knowledge of the roads. This is the same mechanism that powers recommendation engines which guess what you might like before you confirm, or robotics that learn to walk by falling and getting back up.


## The intuition

Imagine you are in a maze. Each square in the maze gives you a small signal: perhaps +10 points for reaching the exit, 0 points for walking through empty corridors, and -1 point for hitting a wall. You do not know where the exit is. At first, you move randomly, stepping up, down, left, or right. Every time you step, you learn a little bit about that specific square. For example, if you step right from Square A and immediately see the exit, you realize that 'going right from Square A' was a very good move. You build a mental ledger: for every square (state) and every possible direction (action), you store a score estimating how good that move is. 

The learning happens through a simple update rule. Suppose you are in Square B. You decide to go East. You take the step and land in Square C. Let us say reaching Square C gives you a reward of 0 points, but from Square C, your mental ledger says the best possible future score is +20 (because you know there is an exit nearby if you play optimally from there). Your new estimate for 'going East from Square B' should be closer to the sum of the immediate reward (0) plus the best future expectation (+20). 

Mathematically, you do not replace your old guess entirely. You keep a little bit of what you thought before, and add a small fraction of the difference between your new estimate and your old one. If your old guess for 'East from B' was 5, and your new target is 20, you might adjust it by 10% toward 20, making it 6. As you repeat this process over thousands of steps in the maze, these scores stabilize. Eventually, the score for every square and direction reflects the true best path to the exit. You have learned the map without anyone showing it to you.


## An analogy

Think of a new employee learning to navigate a large office building to find supplies. They start with no floor plan. Every time they go to a desk to get an item, they receive positive feedback if the item was found quickly, or negative feedback if they got lost or wasted time. They keep a small notebook where they write down, for every starting desk and every door choice, a 'reliability score.' Initially, all scores are zero. When they choose Door A from Desk 1, walk through it, arrive at the copy room (which is useful), and get a positive signal, they update the score for 'Door A from Desk 1' to be higher. They also look at their notebook for the copy room: if they already know that 'from the copy room, the best next step is always upstair,' they add that known value to their current reward. Over weeks of navigating, these scores converge to reflect the most efficient routes. The analogy holds because the employee learns by doing and updating estimates based on outcomes rather than being handed a diagram. Caveat: in this office scenario, the employee can use maps or ask colleagues for help (model-based learning), whereas pure Q-learning assumes the agent must figure it out entirely through trial and error.


## Definition

Q-learning is an algorithm that learns the expected long-term value of taking a specific action in a specific state by iteratively updating an estimate toward the immediate reward received plus the best possible future reward, without requiring prior knowledge of how the environment changes.


## How it connects

This concept sits within Reinforcement Learning, which is the broader field where agents learn optimal behavior through trial and error interactions. It directly relates to the Exploration-Exploitation Tradeoff, a principle describing the balance between trying new actions to gather information and sticking with known good actions to maximize reward.


## The mathematics

Q-learning is a method for teaching a computer how to make decisions by trying things out and learning from the results. It works in situations where you can describe the world as being in a specific **state** (for example, the position of a robot or the layout of a game board) and where you can take an **action** (like moving forward or turning left).

The core of Q-learning is a table of numbers. We call this table the **Q-table**. Each cell in the table holds a single number that represents how good it is to take a specific action while in a specific state. We write this number as Q(s, a). Here is what the letters mean:

- **s** stands for **state**. It identifies where you are right now.
- **a** stands for **action**. It identifies what you choose to do.
- **Q(s, a)** is read as "Q of s and a". It is the estimated total reward you will get in the future if you take action **a** while in state **s**, and then continue playing optimally afterward.

Because the future is uncertain, we cannot know the exact total reward. Instead, we estimate it. The estimation uses two key ideas:

1. **Immediate Reward**: When you take an action, you get a reward right away. Let's call this **r**. This is a number given by the environment (for example, +10 points for winning, -1 point for hitting a wall).
2. **Discount Factor**: We use a number called **gamma** (written as γ). It is a value between 0 and 1 (for example, 0.9). It represents how much we care about future rewards compared to immediate ones. A gamma of 0.9 means we value next step's reward at 90% of its face value.

The update rule tells us how to change the number in the Q-table after we try an action. The formula is:

Q(s, a) ← Q(s, a) + α [ r + γ maxₐ' Q(s', a') − Q(s, a) ]

Let's break this down into plain words and steps.

**Step 1: Identify the components.**
- **s**: The state you were in before the action.
- **a**: The action you just took.
- **r**: The reward you received immediately after taking that action.
- **s'**: The new state you landed in after taking the action.
- **α** (alpha): The **learning rate**. This is a small number between 0 and 1 (for example, 0.5). It controls how much we trust the new information versus what we already knew. A learning rate of 0.5 means we move halfway toward the new estimate.

**Step 2: Calculate the "Target" value.**
The target is what the number *should* be, based on the latest experience. We calculate it in two parts:

1. Look at the new state **s'**. Find the best possible action you could take from there. In the Q-table, look at all actions available in state **s'**. Find the largest number among them. We write this as **maxₐ' Q(s', a')**. This represents the best future value we expect.
2. Multiply that best future value by the discount factor **γ**. This shrinks the future value to reflect uncertainty and time preference.
3. Add the immediate reward **r** to that discounted future value.

So, Target = r + γ * (the largest Q-value in the new state s').

**Step 3: Calculate the "Error" or "Difference".**
We compare our old estimate with the new target. The old estimate is simply the current number in the table, **Q(s, a)**. The difference is:

Difference = Target − Q(s, a)

If the difference is positive, it means the action was better than we thought. If negative, it was worse.

**Step 4: Update the table.**
We do not replace the old number entirely. We adjust it slightly toward the target. The size of the adjustment is controlled by the learning rate **α**.

New Q(s, a) = Old Q(s, a) + α * Difference

This can also be written as:
New Q(s, a) = (1 − α) * Old Q(s, a) + α * Target

This second form shows clearly that the new value is a weighted average of what we knew before and what we just learned.

**Why this works:**
Over time, as you repeat this process many times, the numbers in the Q-table will converge to accurate estimates of the true expected rewards. Once the table is stable, you can simply look up the state **s**, find the action **a** with the highest Q-value, and take that action. This is called a "greedy" policy because it always picks the best-known option.


## A worked example

Let's walk through one single update step with real numbers.

**The Setup:**
- We have two states: **A** and **B**.
- From any state, you can take two actions: **Left** or **Right**.
- The discount factor **γ** is 0.9.
- The learning rate **α** is 0.5.
- The Q-table is currently all zeros because we haven't learned anything yet.

**The Event:**
1. You are in state **A**.
2. You choose the action **Right**.
3. The environment gives you an immediate reward **r = 10**.
4. You land in the new state **B**.

**The Goal:**
Update the value Q(A, Right) in the table.

**Step-by-Step Calculation:**

**1. Find the best future value in the new state B.**
We look at the row for state **B** in the Q-table. Since the table is all zeros, both Q(B, Left) and Q(B, Right) are 0.
We need the maximum of these values:
maxₐ' Q(B, a') = max(0, 0) = 0.

**2. Calculate the Target.**
The target is the immediate reward plus the discounted best future value.
Target = r + γ * maxₐ' Q(B, a')
Target = 10 + 0.9 * 0
Target = 10 + 0
Target = 10.

This means that based on this single experience, the total expected return from taking Right in state A is estimated to be 10.

**3. Calculate the Difference.**
The old value for Q(A, Right) was 0 (from the initial table).
Difference = Target − Old Value
Difference = 10 − 0
Difference = 10.

**4. Apply the Learning Rate.**
We multiply the difference by the learning rate α = 0.5.
Adjustment = α * Difference
Adjustment = 0.5 * 10
Adjustment = 5.

**5. Update the Table.**
New Q(A, Right) = Old Q(A, Right) + Adjustment
New Q(A, Right) = 0 + 5
New Q(A, Right) = 5.

**Result:**
After this one update, the entry for state A and action Right becomes 5. The other entries in the table remain 0.

**Interpretation:**
You might wonder why the value is 5 instead of 10. This is because the learning rate α = 0.5 means we only trust half of the new information. We are blending our old belief (0) with the new evidence (10). If we had used a learning rate of 1.0, the value would have jumped directly to 10. With 0.5, it moves halfway there. In subsequent updates, if you take this action again and get similar rewards, the value will continue to climb toward the true expected return.


## From scratch, in Python

```python
# First, the building blocks you need:
# A dictionary in Python is a set of key-value pairs.
# Here we'll use a dictionary with (state, action) as the key.
# For example, q_table[('A', 'right')] = 5.

# Let's set up a tiny environment.
# States: 'A', 'B'. Actions: 'left', 'right'.
# The transition function: from state 'A', if you go 'right', you get reward 10 and go to 'B'.
# For simplicity, we'll just simulate a few steps.

# Initialise the Q-table as an empty dictionary.
q_table = {}

# A function to get the Q-value, defaulting to 0 if not seen yet.
def get_q(state, action):
    return q_table.get((state, action), 0)

# A function to set the Q-value.
def set_q(state, action, value):
    q_table[(state, action)] = value

# Hyperparameters
alpha = 0.5   # learning rate
gamma = 0.9  # discount factor

# Simulate one episode (a few steps)
# We'll just do one step for clarity.
state = 'A'
action = 'right'
reward = 10
next_state = 'B'

# Compute the target: reward + gamma * max over Q(next_state, a') for all a'
# First, list of actions available in next_state (same as states)
actions = ['left', 'right']
# Find the max Q value among those actions
best_next = max(get_q(next_state, a) for a in actions)  # initially 0

target = reward + gamma * best_next

# Update rule
current_q = get_q(state, action)
new_q = current_q + alpha * (target - current_q)
set_q(state, action, new_q)

print(q_table)  # {('A','right'): 5.0}
```


## The same thing, with a framework

```python
# In practice, you'd use NumPy for the Q-table as a 2D array.
# Rows are states, columns are actions. Indexing is faster.
import numpy as np

# Suppose we have 2 states, 2 actions
num_states = 2
num_actions = 2
q_table = np.zeros((num_states, num_actions))

# Suppose state 0, action 1 (right) gives reward 10, transitions to state 1
s = 0
a = 1
r = 10
s_next = 1

# Update
best_next_action_value = np.max(q_table[s_next, :])
target = r + gamma * best_next_action_value
q_table[s, a] += alpha * (target - q_table[s, a])

print(q_table)
```


## What the code does

The code builds a Q-table as a dictionary mapping (state, action) tuples to Q-values. `get_q` returns 0 if unknown. After one step, we compute `best_next` as the max Q over all actions in the next state (initially 0). `target` is reward + gamma * best_next. Then `new_q` moves the old value toward the target by alpha fraction. That's the entire update. In the framework version, NumPy array is used for speed; the update line does exactly the same arithmetic. In a real RL loop, this update runs inside a loop over many episodes, also choosing actions with an epsilon-greedy strategy.


## Common misconceptions

**Q-learning needs a model of the environment** — I can't use Q-learning because I don't know the transition probabilities of the environment.

Q-learning is model-free — it does not need to know how the environment changes state. It just observes the resulting state and reward after each action. In fact: Q-learning learns from experience: you just observe (state, action, reward, next_state) and update the Q-value. No model needed.

**Q-learning only works in discrete grid worlds** — Q-learning is only for toy games like mazes, not for real problems.

While the tabular version is limited to discrete states, deep Q-learning (DQN) uses a neural network to handle continuous or high-dimensional states (like images). In fact: Q-learning with function approximation can scale to real-world tasks like playing Atari games or controlling robots.

**The Q-value is the final reward** — Q(s,a) should equal the immediate reward after taking action a.

Q-value is the expected *total* discounted future reward, not just the immediate one. It includes future rewards. In fact: Q-value = immediate reward + discounted best future value. It's a long-term measure.

**Q-learning always converges to the optimal policy** — If I run Q-learning long enough, it will always find the best policy.

Convergence requires certain conditions: infinite exploration, appropriate learning rate decay, and a stationary environment. In practice, you may get stuck in a local optimum if exploration is insufficient. In fact: Q-learning converges to the optimal Q-function under theoretical conditions, but practical implementations often use approximations and need careful tuning.


## In short

Q-learning is a model-free algorithm that learns the value of taking an action in a state by updating a table toward the observed reward plus the best discounted future reward. It handles the exploration-exploitation tradeoff by sometimes trying random actions. It's the foundation for deep Q-networks and modern RL methods like RLHF. The key formula: Q(s,a) ← Q(s,a) + α[r + γ max Q(s',a') − Q(s,a)]. It's arithmetic, no calculus needed.


## Where this is used

**Where Q-learning really shows up in AI systems:**

- **Large Language Models (LLMs):** Q-learning itself isn't used directly in training GPT-4, but its descendant — **RLHF** (Reinforcement Learning from Human Feedback) — uses the same value-estimation idea. After the model is pre-trained, it generates responses; a reward model scores them. Then a policy is optimised to maximize that reward, using a variant of policy-gradient, which is built on the same Bellman-style bootstrapping. So when you hear 'RLHF', think 'Q-learning's family'.

- **Small models on devices (TinyML):** In embedded systems, a robot vacuum learning to navigate a room uses Q-learning with a small Q-table if state space is small. For example, a simple thermostat that learns when to preheat based on user behaviour. Because Q-learning is simple and doesn't need a simulator, it's often the first algorithm tried for small-state problems.

- **Retrieval-Augmented Generation (RAG):** Not directly. RAG is about retrieving documents, which is more of a search problem. However, if you think of a RAG system as an agent that decides which tool to call (retrieve, search, etc.), Q-learning could be used to learn that policy — but it's rare. More typically, RL is used to optimise the retriever's rewards (like click feedback), but that's again policy gradient, not tabular Q-learning.

- **Agentic systems that plan, call tools, and act in loops:** Here Q-learning is very relevant. An agent that must decide which tool to call (e.g., web search, calculator, code interpreter) can be trained with RL to maximise success. For a small number of tools and states, tabular Q-learning can be used to learn a policy. For example, a simple assistant that learns to call 'search' when unsure vs. 'calculate' when arithmetic is needed. But current LLM agents use a combination of prompting, planning, and sometimes RL (like RLHF) rather than tabular Q-learning because the state space is huge.

- **Everyday applied ML (recommendation, forecasting, fraud detection):** Q-learning is used in fraud detection as a way to adapt to changing patterns — for example, a system that decides whether to block a transaction based on state (user history, location) and action (block, allow). It learns from rewards (fraud or not). In recommendation systems, bandit algorithms (which are simpler cousins of Q-learning) are widely used to balance exploration vs. exploitation for showing content. So while full Q-learning is less common in production due to large state spaces, its principles are everywhere.

**What a developer actually writes:** For a simple tabular problem, they'd write a loop: for each episode, choose action (epsilon-greedy), take it, observe reward, update Q-table exactly as we did. For larger problems, they'd reach for a library like **Stable-Baselines3** (a PyTorch-based RL library). They'd use a DQN or PPO algorithm — the code is just a few lines to set up the environment and agent, but underneath it does the same Q-learning update but with a neural network function approximator instead of a table.

**What breaks when it's done badly:**
- If exploration is too low, the agent may never discover good rewards and converge to a suboptimal policy.
- If the learning rate is too high, the Q-values can diverge or oscillate.
- If the discount factor is too low, the agent becomes myopic and ignores long-term consequences.
- In practice, tabular Q-learning fails for large state spaces because the table is too big — that's why DQN uses neural networks.

If you're building an AI system that must act in the world, Q-learning gives you the core concept: learning from rewards without a model. Even if you never implement it, you'll recognise the update loop everywhere.


---

Read this on the web: https://basavapurushottam.com/learn-ai/q-learning
