Skip to content
ML Atlas

Q-Learning

Learns how good each action is in each state (its Q-value) from experience, by repeatedly nudging estimates toward 'reward now plus the best value next'.

AlsoQ-values · Q-table · temporal difference · TD learning

Fig. / How it works
StateStateAct (ε-greedy)Act (ε-greedy)RewardRewardUpdate QUpdate Q
Role · kind
Models and algorithmsModel
Level
Intermediate

Watkins, 1989

Keep a notebook with a score for every move in every situation. After each move, update the score a little toward what you got plus how good the next situation looks. Eventually the notebook tells you the best move everywhere.

Where it fits

Reinforcement LearningReinforcement LearningExploration vs ExploitationExploration vs Explo…Markov Decision ProcessMarkov Decision Proc…Actor-Critic MethodsActor-Critic MethodsDeep Q-NetworkDeep Q-NetworkTD-GammonTD-GammonQ-Learning
+All relationships as a list

Is a kind of / part of

Evolved into

See it on the full map

Try it

Q-learning in a gridworld
Loading interactive widget…
TakeawayNobody tells the agent the way. Reward at the goal slowly spreads backward through the Q-values, one step per episode, until a path emerges.

How it works

Q-learning keeps a table with one number for every combination of state and action: Q(s, a), the total future reward expected from taking action a in state s and then acting well.

Each step of experience improves one entry:

  1. In state s, pick an action (usually epsilon-greedy: mostly the best-known one, sometimes random).
  2. Observe the reward r and the new state s′.
  3. Compute a target: r plus the discounted best Q-value available from s′.
  4. Move Q(s, a) a fraction α of the way toward that target.

At first the table is all zeros, and only steps that reach a reward change anything. Then value spreads backwards, one step per episode, from the goal to the states leading to it, like water filling a maze from the exit. Watch it happen in the gridworld widget.

Replacing the table with a neural network that estimates Q from raw input gives the Deep Q-Network.

The mathQ(s,a)←Q(s,a)+α[r+γmax⁡a′Q(s′,a′)−Q(s,a)]Q(s, a) \leftarrow Q(s, a) + \alpha \Big[r + \gamma \max_{a'} Q(s', a') - Q(s, a)\Big]

The bracket is the temporal-difference error: how surprised the agent was.

Everyday use cases

  • Case 01

    Learning to navigate

    A robot in a simple maze learns which way to go from each position.

  • Case 02

    The basis of DQN

    DeepMind's Atari-playing agent is Q-learning with a neural network in place of the table.

Famous examples

Strengths, weaknesses and when to use it

Strengths

  • Simple and model-free: no need to know how the environment works.
  • Learns the optimal policy even while exploring.

Weaknesses

  • A table of states only works for small problems.
  • Learning can be slow when rewards are rare.

When to use itFor small, discrete problems, and as the conceptual basis of deep value-based RL.

Compare with

Check yourself

  1. Q01

    What is a Q-value?

    Show answer

    A: The expected total future reward of taking an action in a state and then acting well

  2. Q02

    Why does Q-learning use max over the next actions in its update?

    Show answer

    A: It estimates the value of acting optimally afterwards, even if the agent explores

Go deeper

Next topics

Sources

  1. [1]Watkins and Dayan, Q-learning, Machine Learning 8 (1992)
  2. [2]Karpathy, REINFORCEjs GridWorld demo