Introduction to Reinforcement Learning: From Intuition to Q-Learning

Why Do We Need Reinforcement Learning?

You are already familiar with supervised learning: given a pile of (input, label) pairs, a model learns to predict the label from the input. But in reality many problems have no labels—

• Playing chess: there is no standard answer, only the delayed feedback of “won / lost”
• Autonomous driving: there are no annotations for the “correct action”; the goal is “arrive safely”
• Game AI: the goal is “clear the game”, but there is no ready-made answer for which move to take at each step

The common feature of these problems is “sequential decision-making + delayed rewards”: an agent makes consecutive decisions in an environment, affects future states, and finally receives a reward. This is the problem that reinforcement learning (RL) aims to solve.

💡 One-sentence intuition: reinforcement learning is letting AI learn to act through trial and error, discovering the optimal policy on its own through reward signals.

1. Core Concepts: The MDP Five-Tuple

RL problems are usually modeled as a Markov Decision Process (MDP). An MDP is defined by five elements:

The Markov property means: the next state $s’$ depends only on the current state $s$ and action $a$, and is independent of history. That is:

$$P(s_{t+1} \mid s_t, a_t, s_{t-1}, a_{t-1}, \dots) = P(s_{t+1} \mid s_t, a_t)$$

This assumption greatly simplifies the problem—we do not need to remember the entire history; we only need to focus on the “current state” to make decisions.

2. Objective: Maximize Cumulative Reward

The goal of RL is to find a policy $\pi$—a mapping from states to actions $\pi: S \to A$—that maximizes the expected cumulative reward.

Because future rewards are not as “valuable” as immediate rewards (100 dollars today is worth more than 100 dollars tomorrow), we introduce the discount factor $\gamma \in [0,1]$ and define the return $G_t$:

$$G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots = \sum_{k=0}^{\infty} \gamma^k R_{t+k+1}$$

• $\gamma = 0$: only looks at the present; short-sighted
• $\gamma = 1$: treats the future the same as the present; may not converge
• In practice $\gamma$ is usually set to $0.9 \sim 0.99$

Our ultimate goal is to find the optimal policy $\pi^*$ that maximizes expected return:

$$\pi^* = \arg\max_\pi \mathbb{E}\left[\sum_{k=0}^{\infty} \gamma^k R_{t+k+1} \right]$$

3. Value Functions: Measuring “How Good a State Is”

Directly solving for $\pi^*$ is too abstract; we need a more concrete tool—the value function.

State-Value Function $V^\pi(s)$

Under policy $\pi$, the expected return starting from state $s$:

$$V^\pi(s) = \mathbb{E}_\pi \left[ G_t \mid S_t = s \right]$$

Action-Value Function $Q^\pi(s,a)$

Under policy $\pi$, the expected return after taking action $a$ in state $s$:

$$Q^\pi(s,a) = \mathbb{E}_\pi \left[ G_t \mid S_t = s, A_t = a \right]$$

The relationship between the two is intuitive—the state value is the policy-weighted average of all action values in that state:

$$V^\pi(s) = \sum_a \pi(a \mid s) , Q^\pi(s,a)$$

💡 Intuition: $V(s)$ tells you “how good it is to stand here,” while $Q(s,a)$ tells you “how good it is to stand here and take a particular action.” The latter is richer in information and is at the core of most RL algorithms.

4. Bellman Equation: The Cornerstone of RL

Value functions satisfy an elegant recursive relationship—the Bellman equation. It connects the “value of the current state” with the “value of the next state”.

Bellman Equation for $V$

$$V^\pi(s) = \sum_a \pi(a \mid s) \sum_{s’} P(s’ \mid s,a) \left[ R(s,a) + \gamma V^\pi(s’) \right]$$

Intuition: the value of the current state = the expected value, over all actions, of (immediate reward + discounted value of the next state).

Bellman Equation for $Q$

$$Q^\pi(s,a) = \sum_{s’} P(s’ \mid s,a) \left[ R(s,a) + \gamma \sum_{a’} \pi(a’ \mid s’) Q^\pi(s’,a’) \right]$$

Bellman Optimality Equation

For the optimal value functions $V^$ and $Q^$, action selection is no longer “weighted by the policy” but “directly takes the maximum”:

$$Q^(s,a) = \sum_{s’} P(s’ \mid s,a) \left[ R(s,a) + \gamma \max_{a’} Q^(s’,a’) \right]$$

This is the core of all RL—as long as we can solve for $Q^*$, the optimal policy is to choose the action with the largest $Q$ value in each state:

$$\pi^(s) = \arg\max_a Q^(s,a)$$

5. Q-Learning: The Classic Model-Free Learning Algorithm

In reality, the transition probability $P$ and reward function $R$ are often unknown (this is called the model-free setting), and we can only learn by interacting with the environment. Q-Learning is the most classic solution.

Core Idea

Maintain a Q-table (a tabular $Q(s,a)$), continuously update it through interaction with the environment, and finally converge to $Q^*$.

Update Rule

$$Q(s,a) \leftarrow Q(s,a) + \alpha \left[ r + \gamma \max_{a’} Q(s’,a’) - Q(s,a) \right]$$

where:

• $\alpha \in (0,1]$ is the learning rate
• $r + \gamma \max_{a’} Q(s’,a’)$ is the TD target (temporal-difference target)
• $\delta = r + \gamma \max_{a’} Q(s’,a’) - Q(s,a)$ is the TD error

Intuition: use the new estimate computed from “actual experience” $(r, s’)$ to correct the old $Q(s,a)$, moving a little closer to the target each time.

Exploration vs. Exploitation

Q-Learning uses an $\varepsilon$-greedy policy to balance exploration and exploitation:

• With probability $\varepsilon$: choose an action randomly (exploration, to avoid getting stuck in local optima)
• With probability $1-\varepsilon$: choose the action with the largest $Q$ value (exploitation of known information)

Usually $\varepsilon$ decays from 1.0 to 0.1: more exploration early on and more exploitation later.

6. Code Example: Q-Learning in a Maze

Below we use the most classic example—GridWorld maze navigation—to show the complete Q-Learning workflow. The agent moves from the start to the goal while avoiding traps.

import numpy as np
import random

# 网格世界:4x4
# S = 起点, G = 终点(+1), X = 陷阱(-1)
# . = 普通格子(0)
grid = [
    ['S', '.', '.', 'X'],
    ['.', 'X', '.', '.'],
    ['.', '.', '.', 'X'],
    ['X', '.', '.', 'G'],
]
N = 4
ACTIONS = ['up', 'down', 'left', 'right']

def get_reward(cell):
    if cell == 'G': return 1.0       # 到达终点,正向奖励
    if cell == 'X': return -1.0      # 踩到陷阱,负向奖励
    return -0.01                     # 普通格子,小惩罚(鼓励尽快到达)

def is_terminal(cell):
    return cell in ('G', 'X')

def step(state, action):
    """执行动作,返回 (next_state, reward, done)"""
    r, c = state
    if   action == 'up':    r = max(0, r - 1)
    elif action == 'down':  r = min(N - 1, r + 1)
    elif action == 'left':  c = max(0, c - 1)
    elif action == 'right': c = min(N - 1, c + 1)
    next_state = (r, c)
    cell = grid[r][c]
    return next_state, get_reward(cell), is_terminal(cell)

# Q 表:state -> action -> value
Q = {}
def q_value(state, action):
    return Q.setdefault(state, {}).setdefault(action, 0.0)

# === Q-Learning 训练 ===
alpha, gamma, epsilon = 0.1, 0.95, 1.0
EPISODES = 2000

for ep in range(EPISODES):
    state = (0, 0)  # 起点 S
    done = False
    while not done:
        # ε-greedy 选动作
        if random.random() < epsilon:
            action = random.choice(ACTIONS)        # 探索
        else:
            action = max(ACTIONS, key=lambda a: q_value(state, a))  # 利用

        next_state, reward, done = step(state, action)

        # Q-Learning 更新
        td_target = reward + gamma * max(
            (q_value(next_state, a) for a in ACTIONS), default=0.0
        )
        Q.setdefault(state, {})[action] += alpha * (td_target - q_value(state, action))

        state = next_state

    # epsilon 衰减:从探索逐渐转向利用
    epsilon = max(0.1, epsilon * 0.995)

# === 提取学到的最优策略 ===
print("学到的最优策略:")
arrows = {'up': '↑', 'down': '↓', 'left': '←', 'right': '→'}
for r in range(N):
    row = []
    for c in range(N):
        cell = grid[r][c]
        if cell in ('G', 'X', 'S'):
            row.append(f' {cell} ')
        else:
            best = max(ACTIONS, key=lambda a: q_value((r, c), a))
            row.append(f' {arrows[best]} ')
    print(''.join(row))

After running it, you will see the path the agent learned—it will bypass traps and head toward the goal, even though we never told it “how to get there”.

7. From Q-Learning to Deep Reinforcement Learning

The fatal limitation of Q-Learning: a Q-table cannot handle large state spaces. Chess has about $10^{47}$ states, Go about $10^{170}$—a table simply cannot store them.

The natural solution: use a neural network to approximate the $Q$ function $Q_\theta(s,a)$. This is DQN (Deep Q-Network); DeepMind used it to make AI reach human-level performance on Atari games for the first time.

Key innovations of DQN:

1. Experience replay: store interaction data in a buffer, sample randomly for training, and break data correlation
2. Target network: use a separate network to compute the TD target, stabilizing training

Beyond that, the RL family continues to evolve:

8. Final Words

The beauty of reinforcement learning is that it uses a unified mathematical framework (Bellman equation + value functions) to describe “how to learn to act through trial and error without a teacher”. This may be the learning paradigm closest to the “essence of intelligence”.

This article walks through the core thread from intuition to Q-Learning:

1. MDP models the problem
2. Value functions measure goodness
3. Bellman equation gives the recursive relationship
4. Q-Learning achieves model-free learning
5. DQN scales to large state spaces with deep networks

Suggested next steps:

• 📖 Sutton & Barto, Reinforcement Learning: An Introduction (the RL bible, free PDF)
• 🎮 OpenAI Gym / Gymnasium — the standard tool for running various RL environments
• 🧪 Stable Baselines3 — out-of-the-box implementations of RL algorithms (PPO/SAC, etc.)
• 🏆 Start from simple environments (CartPole) and gradually tackle more complex tasks

The next post will cover policy gradient methods, discussing why “directly optimizing the policy” is more powerful than value-based methods in some scenarios.

Happy learning! 🚀