Strategies learned through trial and error — the formal version of what every child does.
Fundamentals 10 min Intermediate June 29, 2026
You already know about agents, environments, states, actions, and rewards from the RL fundamentals article. But how does the agent actually decide what to do? Q-Learning gives it a simple bookkeeping trick: a table that records how promising each state-action pair has been so far.
In this article, you will learn the mathematical framework (MDP) that defines the rules of the game, the algorithm (Q-Learning) that discovers the best strategy, and the balancing act (exploration vs. exploitation) that prevents the agent from getting stuck with a mediocre plan.
The Rules of the Game — Markov Decision Process
Markov Decision Process (MDP)
AnalogyDefinition
Think of a board game: the game board defines all possible fields (states), the rules determine allowed moves (actions), dice rolls create transition probabilities, victory points are rewards, and the discount factor is like human impatience — would you rather have 10 euros today or 11 euros next week?
Analogy:
Think of a board game: the game board defines all possible fields (states), the rules determine allowed moves (actions), dice rolls create transition probabilities, victory points are rewards, and the discount factor is like human impatience — would you rather have 10 euros today or 11 euros next week?
Definition:
An MDP formalises the RL environment as a tuple (S, A, P, R, γ). S = states, A = actions, P = transition probabilities, R = reward function, γ = discount factor. The Markov property states: the next state depends only on the current state and the chosen action — history does not matter.
The board game analogy has limits: real environments do not always fit perfectly into the MDP framework, especially when the agent cannot observe everything. But for getting started, the model is a powerful tool. As an environment, imagine a simple 4×4 grid:
Start Top-left — the agent begins here
Goal (+10) Bottom-right — reward of +10 points
Trap (-10) Position (2,2) — penalty of -10 points
Step (-1) Every move costs -1 point
The discount factor γ fundamentally changes strategy: with γ=0.9, the agent senses the goal many steps ahead and learns the shortest path past the trap. With γ=0.1, it is shortsighted: a goal more than two steps away barely counts, and it wanders around for a long time.
Common Misconception
The discount factor is not an unimportant fine-tuning parameter. It fundamentally changes strategy: near 0, the agent grabs the nearest reward regardless of consequences. Near 1, it accepts short-term costs for larger long-term gains.
Deep Dive: The Discount Factor in Detail
In the 4×4 grid with γ=0.9, the agent values the goal (+10) several steps ahead: 0.9³ × 10 = 7.29 points even three steps away. That is why it finds the shortest path to the goal and avoids the trap (-10). With γ=0.1, however: 0.1³ × 10 = 0.01 points — the goal three steps away is practically worthless. The agent only reacts to immediate rewards and barely finds a clear direction.
The Bookkeeper's Algorithm — Q-Learning
Q-Learning
AnalogyDefinition
Imagine a tourist exploring a new city with a notebook. After each walk, the tourist writes down: "turning left from this intersection led to a great view" (high Q-value) or "turning right was a dead end" (low Q-value). After many walks, the notebook converges to the optimal sightseeing route.
Analogy:
Imagine a tourist exploring a new city with a notebook. After each walk, the tourist writes down: "turning left from this intersection led to a great view" (high Q-value) or "turning right was a dead end" (low Q-value). After many walks, the notebook converges to the optimal sightseeing route.
Definition:
Q-Learning maintains a table Q(s,a) where each entry stores the expected future reward for taking action a in state s. After each step, the entry is updated. After enough episodes, the optimal policy is simply: in each state, pick the action with the highest Q-value.
Old Q-value: Q(s,a) = 5.0. The agent takes the action and receives reward r = 2. Best Q-value in the next state: max Q(s',a') = 8.0. Learning rate α = 0.1, discount factor γ = 0.9. Calculation: 5.0 + 0.1 × [2 + 0.9 × 8.0 − 5.0] = 5.0 + 0.1 × [2 + 7.2 − 5.0] = 5.0 + 0.1 × 4.2 = 5.42. The Q-value increased because the new experience was more valuable than expected.
A special property of Q-Learning: the algorithm is off-policy — it learns the optimal strategy even while the agent performs suboptimal actions. The notebook keeps getting better regardless of which path the tourist actually takes, as long as every turn-off gets tried again now and then.
Common Misconception
Q-Learning does not work for every problem. The table must store one entry per state-action pair. Chess has approximately 10⁴⁴ states — a table that large is physically impossible. For complex problems, Deep Q-Networks (DQN) use neural networks to approximate Q-values instead.
Deep Dive: When Q-Tables Break
The 4×4 grid has 16 states × 4 actions = 64 Q-values — no problem. But chess has an estimated 10⁴⁴ states. A Q-table that large would far exceed all available storage capacity on Earth. Mnih et al. (2013, expanded in Nature in 2015) solved this problem with Deep Q-Networks: a neural network learns to estimate Q-values for arbitrary states instead of storing them in a table. The DQN learned 49 Atari games, reached human level in the majority of them and opened the door to modern deep reinforcement learning.
2015 Breakthroughs
Deep Q-Networks: AI Learns Atari from Pixels
Long before AlphaGo made headlines, in 2015 DeepMind got an AI to learn Atari video games from raw pixels alone — laying the foundation of deep reinforcement learning. In February 2015 the team led by Volodymyr Mnih presented “Human-level control through deep reinforcement learning” in Nature (an earlier precursor had appeared in 2013). A single neural network that saw only the screen and the score learned 49 different Atari games — with the same architecture, without per-game tuning. Technically, DeepMind combined a convolutional network with Q-learning, an experience-replay memory (introduced by Lin in the early 1990s) and a stabilising target network. Precision matters in the assessment: the system reached human level on about half of the games and beat all prior methods on 43 of 49 — yet on sparse-reward games such as Montezuma's Revenge it failed almost completely. Even so, it was the proof that deep networks and reinforcement learning fit together at scale — the bridge from the Q-learning of the 1990s to AlphaGo and AlphaZero.
Try it: Watch the Q-Table Fill Up
Now you fill in the Q-table yourself. The agent starts top left in the 4×4 grid from before and knows nothing yet: every Q-value is 0. Each click on “Next step” makes one move and changes exactly one value by the update rule. Then play whole episodes: the goal’s +10 travels back step by step to the start, and after many episodes the arrows show the shortest path past the trap.
Try it: Optimist versus Realist (TD & SARSA)
The difference in the square brackets of the update rule is called the TD error (temporal difference). Q-Learning is off-policy: it learns with the best possible next move (max Q). SARSA is the on-policy twin: it learns with the move it actually takes next. Here you see both at once — and feel why on-policy is more cautious.
Loading the interactive TD / SARSA junction …
The Restaurant Dilemma — Exploration vs. Exploitation
Epsilon-Greedy Strategy
AnalogyDefinition
Every Friday you must choose: your favourite restaurant (exploitation — reliable, but you might miss the amazing new place around the corner) or a random new restaurant (exploration — risky, but you might find something even better). Early on, trying many restaurants makes sense. After years, you mostly go to proven favourites but occasionally try something new.
Analogy:
Every Friday you must choose: your favourite restaurant (exploitation — reliable, but you might miss the amazing new place around the corner) or a random new restaurant (exploration — risky, but you might find something even better). Early on, trying many restaurants makes sense. After years, you mostly go to proven favourites but occasionally try something new.
Definition:
The epsilon-greedy strategy balances exploration and exploitation: with probability ε, the agent chooses a random action; with probability 1−ε, it chooses the action with the highest Q-value. Epsilon starts high (e.g. 1.0) and decays over training to a small value (e.g. 0.01) — shifting the focus from exploration to exploitation.
Pure Exploitation
Reliable, but the agent sticks with the first decent strategy. Better paths are never discovered.
Pure Exploration
Discovers everything, but never uses known good options. The agent stumbles around aimlessly.
In the grid world example: episodes 1–100, ε=1.0 (pure random exploration, the agent stumbles everywhere). Episodes 100–500, ε decays from 1.0 to 0.1 (the agent follows the best route more and more often and by the end deviates only 10% of the time to discover shortcuts). From episode 500, ε=0.01 (the agent follows the optimal route and rarely deviates).
2019 Competitions
AlphaStar Reaches Grandmaster Level
The conquest of the most complex real-time strategy by artificial intelligence. In July and August 2019, DeepMind's AlphaStar competed anonymously in ranked mode on Battle.net; on October 30, 2019, DeepMind reported in the journal Nature that the system had become the first AI to reach Grandmaster level in StarCraft II — a game considered too complex for machines. AlphaStar ranked above 99.8% of all active Battle.net players and mastered all three races: Protoss, Terran, and Zerg. Prior to this, AlphaStar had already defeated professional players Grzegorz 'MaNa' Komincz and Dario 'TLO' Wunsch 5:0 each. Its distinctiveness lay in the multi-agent reinforcement learning architecture, which trained various strategies and counter-strategies within a league. With an average of 280 actions per minute, AlphaStar was even below human professionals, but demonstrated more precise execution. This achievement marked a milestone for AI in video games and real-time decision-making.
Common Misconception
More exploration is not always better. Exploration is only valuable during learning and in changing environments. An agent that never stops exploring wastes resources on actions it already knows are bad. Epsilon decay ensures that exploration gradually yields to exploitation.
Key Takeaways
An MDP formalises the RL environment into states, actions, transitions, rewards, and a discount factor — the Markov property says: "Only the present matters."
Q-Learning fills a table with expected future rewards for every state-action pair, updated after each experience via a single arithmetic rule.
Epsilon-greedy with decay solves the exploration-exploitation dilemma: explore broadly at first, then gradually shift to exploiting the best-known strategy.
Tabular Q-Learning works for small environments. For complex problems, neural networks approximate Q-values instead (Deep Q-Networks).
Quiz: Q-Learning & MDPs
Question 1 / 6
Not completed
Which of the following is NOT one of the five components of a Markov Decision Process?
1. Which of the following is NOT one of the five components of a Markov Decision Process?
☐ A) States (S)
☐ B) Actions (A)
☐ C) Learning Rate (α)
☐ D) Discount Factor (γ)
2. What does the Markov property guarantee about an MDP?
☐ A) The agent always finds the optimal policy
☐ B) The next state depends only on the current state and action, not on history
☐ C) Rewards are always positive
☐ D) Every action always leads to the same next state
3. Given: Q(s,a)=4.0, α=0.1, r=3, γ=0.9, max Q(s',a')=7.0. What is the new Q(s,a)?
☐ A) 4.53
☐ B) 4.00
☐ C) 5.23
☐ D) 4.93
4. An agent uses epsilon-greedy with ε=0.3. In 200 steps, approximately how many random actions will it take?
☐ A) 30
☐ B) 60
☐ C) 140
☐ D) 200
5. A Q-Learning agent always chooses the highest Q-value action (ε=0). After 1,000 episodes it still performs poorly. What is the most likely cause?
☐ A) The learning rate is too high
☐ B) The agent never explored enough to discover the optimal path
☐ C) The discount factor is exactly 1.0
☐ D) The Q-table is too large
6. Why is tabular Q-Learning impractical for a game like chess?
☐ A) Chess has no clearly defined reward function
☐ B) The number of possible states (~10⁴⁴) makes the Q-table impossibly large
☐ C) Chess requires continuous actions, not discrete ones
☐ D) Q-Learning only works for single-player games
Answer Key: 1) C · 2) B · 3) A · 4) B · 5) B · 6) B
Comprehension Check
Explain in one sentence what the Markov property states and why it matters for MDPs.
Walk through the Q-Learning update rule with your own numerical example.
Why must epsilon decay over time instead of staying constant?