Developing Strategies (Q-Learning & MDPs)
Strategies learned through trial and error — the formal version of what every child does.
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
Definition
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:
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
Definition
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.
Deep Q-Networks: AI Learns Atari from Pixels
About a year 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 more than half of the games (29 of 49) 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.
The Restaurant Dilemma — Exploration vs. Exploitation
Definition
Epsilon-Greedy Strategy
Analogy
Definition
Reliable, but the agent sticks with the first decent strategy. Better paths are never discovered.
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).
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. In its games against MaNa and TLO, AlphaStar averaged around 280 actions per minute, even below human professionals, but demonstrated more precise execution. This achievement marked a milestone for AI in video games and real-time decision-making.
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
- 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).
Check
Quiz: Q-Learning & MDPs
Which of the following is NOT one of the five components of a Markov Decision Process?
Select one answer
1. Which of the following is NOT one of the five components of a Markov Decision Process?
2. What does the Markov property guarantee about an MDP?
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)?
4. An agent uses epsilon-greedy with ε=0.3. In 200 steps, approximately how many random actions will it take?
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?
6. Why is tabular Q-Learning impractical for a game like chess?
Check
Comprehension Check
Can you explain this in your own words? Tick what you've got.
0 of 3 done