Back to Learning Area

Developing Strategies (Q-Learning & MDPs)

Strategies learned through trial and error — the formal version of what every child does.

  • Fundamentals
  • 10 min
  • Intermediate

Plain Language

This preview is in Plain Language. The whole portal is also available in Plain Language. You can change the language at the top. Or use the button below. Our Plain Language texts are AI-assisted and editorially reviewed. They follow the core principles of easy-to-read language, but they are not certified Easy Read: a review panel of people with learning difficulties does not test them.

Preview: Learning through reward

What is Q-learning?

Q-learning is a learning method. An agent is an AI program. It tries out different actions. It gets rewards for good actions. This is how it improves its strategy.

The Q-table

The agent maintains a table. This table is called the Q-table. In the table, it says: how good is action X in state Y? The agent always searches for the action with the highest value.

Explore or use?

The agent must choose. It can use known good actions. It can also try out new actions. This is called exploration. Exploration means: exploring new paths. This is how it might find better strategies.

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

Definition

Markov Decision Process (MDP)

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?

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, the paths differ only minutely in its table, and it wanders around for a long time.

Caution

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.

In the 4×4 grid with γ=0.9, the agent values the goal (+10) several steps ahead: 0.9³ × 10 = 7.29 points even four 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 four steps away is practically worthless. Almost only the immediate step costs count: at the start, the Q-values of the directions differ only in the fourth decimal place, and the agent takes a very long time before a clear direction emerges.

The Bookkeeper's Algorithm — Q-Learning

Definition

Q-Learning

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.
Q(s,a) ← Q(s,a) + α · [r + γ · max Q(s',a') − Q(s,a)]
Q-Learning Update Rule

Note

Worked Example

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.

Caution

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.

The 4×4 grid has 16 states × 4 actions = 64 Q-values (56 of them are learned, because the goal and the trap end the episode) — 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.

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.

The Restaurant Dilemma — Exploration vs. Exploitation

Definition

Epsilon-Greedy Strategy

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.
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 101–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).

Caution

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.

Note

Key Takeaways

  1. An MDP formalises the RL environment into states, actions, transitions, rewards, and a discount factor — the Markov property says: "Only the present matters."
  2. Q-Learning fills a table with expected future rewards for every state-action pair, updated after each experience via a single arithmetic rule.
  3. Epsilon-greedy with decay solves the exploration-exploitation dilemma: explore broadly at first, then gradually shift to exploiting the best-known strategy.
  4. Tabular Q-Learning works for small environments. For complex problems, neural networks approximate Q-values instead (Deep Q-Networks).

Check

Quiz: Q-Learning & MDPs

Not completed

Which of the following is NOT one of the five components of a Markov Decision Process?

Select one answer

Answer Key: 1) C · 2) B · 3) A · 4) B · 5) B · 6) B

Check

Comprehension Check

Can you explain this in your own words? Tick what you've got.

0 of 3 done