Deep Q-learning

(Tabular) Q-Learning

Tabular means storing one Q-value for each state-action pair (s, a). Q-learning uses experience to update these entries without needing the transition probabilities.

Q-value iteration:

Q_{k + 1} (s, a) \leftarrow \sum_{s^{'}} P (s^{'} | s, a) (R (s, a, s^{'}) + γ max_{a^{'}} Q_{k} (s^{'}, a^{'}))

For a fixed (s, a), consider every possible next state s′. In each case, add the immediate reward to the discounted best next Q-value, then average using the transition probabilities. The max chooses the next action a′; the current action a is already fixed.

Rewrite as expectation:

Q_{k + 1} (s, a) \leftarrow \underset{s^{'} \sim P (s^{'} | s, a)}{E} [R (s, a, s^{'}) + γ max_{a^{'}} Q_{k} (s^{'}, a^{'})]

This is exactly the same update. E is shorthand for the probability-weighted sum above, and s′ ∼ P(s′ | s, a) means the next state follows the environment’s transition distribution.

(Tabular) Q-Learning: replace expectation by samples

For a state-action pair (s, a), receive:

$s^{'} \sim P (s^{'} | s, a)$

Take action a in state s and observe one next state s′ and reward r. The environment produces the sample; we do not need to know the numerical probabilities in P.
Consider your old estimate:

$Q_{k} (s, a)$

This is the Q-value currently stored for the state and action just visited.
Consider your new sample estimate:

$target (s^{'}) = \underset{\begin{matrix} ↑ \\ Observed reward \end{matrix}}{R (s, a, s^{'})} + \underset{\begin{matrix} ↑ \\ Discounted future value \end{matrix}}{γ max_{a^{'}} Q_{k} (s^{'}, a^{'})}$

Use the observed reward r for R(s, a, s′), then add the best next Q-value from the current table, discounted by γ. This target uses one observed outcome instead of averaging over all possible outcomes. The future value is still an estimate.
Incorporate the new estimate into a running average:

$Q_{k + 1} (s, a) \leftarrow \underset{\begin{matrix} ↑ \\ Keep old estimate \end{matrix}}{(1 - α) Q_{k} (s, a)} + \underset{\begin{matrix} ↑ \\ Add sample estimate \end{matrix}}{α [target (s^{'})]}$

α is the learning rate, with 0 < α ≤ 1. Keep a fraction 1 − α of the old estimate and add a fraction α of the target. A smaller α makes a smaller adjustment; α = 1 replaces the old value with the target. Only the visited (s, a) entry changes.

For example, let the old Q-value be 4, the target be 10, and α = 0.1:

$0.9 \times 4 + 0.1 \times 10 = 4.6$

With a constant α, this is a weighted running average: recent samples receive more weight.

(Tabular) Q-Learning: Algorithm

Start with $Q_{0} (s, a)$ for all s, a.

Get initial state s.

For k = 0, 1, 2, … till convergence:

Sample action a, get next state s′ and reward r.

If s′ is terminal:

target = R (s, a, s^{'})

Sample a new initial state s′.

Else:

target = R (s, a, s^{'}) + γ max_{a^{'}} Q_{k} (s^{'}, a^{'})

Q_{k + 1} (s, a) \leftarrow (1 - α) Q_{k} (s, a) + α [target]

s \leftarrow s^{'}

Initialize: give each table entry a starting value, often 0, and choose the first state.
Observe: select and execute an action, then receive the next state and reward. The sampled action does not have to be the maximizing action used in the target.
Terminal: the episode has ended, so there is no future reward to add. Compute the reward-only target before selecting a fresh initial state for the next episode.
Nonterminal: the episode continues, so the target includes the discounted best next Q-value.
Update and continue: update the original (s, a) entry using the stored target, then set s ← s′. Here s′ is either the observed next state or the new initial state after a terminal transition. All other Q-table entries keep their previous values.

How to sample actions?

Choose random actions?

This provides exploration: try different actions and collect evidence about their returns. But choosing randomly all the time does not use what we have learned to favor good actions.

Choose action that maximizes $Q_{k} (s, a)$ (i.e. greedily)?

This is exploitation: use the current Q estimates to choose the action that appears best. It helps turn learned values into good decisions, but these estimates can be wrong, especially early in learning.

Pure greedy selection can get stuck. Q-learning updates only the state-action pairs it visits. If an action has a low estimate and is never tried, its estimate cannot improve, even if that action is actually better.

Why exploration matters

Consider a one-step task. A always gives reward 1, and B always gives reward 10. We have tried A, but not B:

Action	Current Q estimate	Actual reward
A	1	1
B	0	10

Pure greedy selection keeps choosing A because 1 > 0. B stays at 0 because it is never tried. Exploration occasionally tries B, discovers its reward, and lets us update its Q-value. We can then learn to prefer B.

ε-Greedy: choose random action with prob. ε, otherwise choose action greedily

With probability ε: sample an action uniformly at random. This is the exploration branch.
With probability 1 − ε: choose an action with the highest current Q-value. This is the exploitation branch.

For ε = 0.1, we use the random branch 10% of the time and the greedy branch 90% of the time. The random branch samples from all actions, so it can also pick the greedy action.

ε-greedy balances earning reward using what we currently know with gathering experience that may reveal a better action. The sampled action determines what experience we collect; the Q-learning target still uses the max over next actions.

Why is it off-policy?

Amazing result: Q-learning converges to optimal policy — even if you’re acting suboptimally!
This is called off-policy learning.

Two roles for a policy

Behavior policy: how we actually choose actions to collect experience. For example, ε-greedy sometimes chooses an action that does not have the highest current Q-value.
Target policy: the policy our update learns about. Q-learning uses a greedy next action: the one with the highest current Q-value at s′.

target (s^{'}) = \underset{\begin{matrix} ↑ \\ Observed reward \end{matrix}}{R (s, a, s^{'})} + \underset{\begin{matrix} ↑ \\ Greedy future value \end{matrix}}{γ max_{a^{'}} Q_{k} (s^{'}, a^{'})}

The max builds the target around the best next action, regardless of which next action the behavior policy actually chooses. This lets us collect experience with one policy while learning about another: off-policy learning.

We still update the Q-value for the action a actually taken. The max concerns the future continuation from s′; it does not change which current action produced the observed reward and next state.

Example

At s′, suppose going left has Q-value 5 and going right has Q-value 2. The behavior policy may go right to explore. The preceding Q-learning update still uses 5 as the future value, because its target selects the best next action.

If the observed reward is 1 and γ = 0.9, the target is:

target = 1 + 0.9 \times 5 = 5.5

What does “converges to optimal policy” mean?

With sufficient exploration and suitable learning rates, tabular Q-values approach the optimal Q-values. Choosing greedily from those learned values gives an optimal policy. A behavior policy that keeps exploring can still take suboptimal actions even after the values have converged.

The conditions below apply to a finite tabular MDP with bounded rewards and 0 ≤ γ < 1. Deep Q-learning keeps the off-policy target, but using a neural network does not automatically inherit this tabular convergence guarantee.

Caveats:

You have to explore enough

Q-learning only updates the state-action pair it visits. An action that is never tried can keep a wrong Q-value forever, even if it is actually the best action. Exploration supplies the experience needed to correct these estimates.
You have to eventually make the learning rate small enough

Each sample is noisy. If α stays large, one lucky or unlucky outcome can keep moving the Q-value substantially. Smaller learning rates make later updates gentler, allowing the estimate to settle.
… but not decrease it too quickly

If α becomes tiny too early, new experience has too little influence to undo early mistakes. The learning rate needs to shrink while leaving enough total learning ahead to correct the estimate.

Technical requirements.

All states and actions are visited infinitely often

Every state-action pair (s, a) must keep receiving updates as training continues. Visiting a state repeatedly is not enough if we always choose the same action there.

Basically, in the limit, it doesn’t matter how you select actions (!) The behavior policy can be suboptimal and need not be greedy, provided it keeps visiting every pair and the learning rates satisfy the conditions below. How we choose actions still affects how quickly we learn in a finite run.
Learning rate schedule such that for all state and action pairs (s, a):

$\underset{\begin{matrix} ↑ \\ Enough total learning \end{matrix}}{\sum_{t = 0}^{\infty} α_{t} (s, a) = \infty} \underset{\begin{matrix} ↑ \\ Control sampling noise \end{matrix}}{\sum_{t = 0}^{\infty} α_{t}^{2} (s, a) < \infty}$

αₜ(s, a) is the learning rate for that pair’s (t + 1)-th update, starting with t = 0. Each pair has its own update count, so rarely visited pairs do not lose their learning rate just because other pairs were updated many times.

The first sum equals ∞: the updates get smaller, but their total size never runs out. Even after many updates, there is still enough learning left to correct an early error. This is the precise meaning of “not decrease it too quickly.”

The second sum is finite: the squared learning rates have a finite total. Squaring appears because multiplying sample noise by α multiplies its variance by α². This condition controls the accumulated noise and forces αₜ to approach zero.

Example: $α_{t} (s, a) = \frac{1}{t + 1}$

The learning rates are 1, 1/2, 1/3, … . They become smaller without shrinking too quickly:

1 + \frac{1}{2} + \frac{1}{3} + \dots = \infty 1 + \frac{1}{4} + \frac{1}{9} + \dots < \infty

A constant α = 0.1 fails the second condition: its squares keep adding 0.01 forever. A faster decrease, αₜ = 1 / (t + 1)², fails the first condition: the total learning is finite. The schedule 1 / (t + 1) satisfies both.

Can Tabular Methods Scale?

Discrete environments

Gridworld with a nearby exit, a distant exit, and a cliff — Gridworld10¹

A Tetris board with falling and stacked blocks — Tetris10⁶⁰

Atari Breakout with bricks, a ball, and a paddle — Atari10³⁰⁸ (RAM)10¹⁶⁹⁹² (pixels)

Discrete means states can be counted; it does not mean there are few of them. Gridworld has only a small set of positions, while a Tetris board or an Atari screen can have an enormous number of configurations.

These are illustrative sizes from the slides. For example, a 10 × 20 board with each cell empty or occupied has 2²⁰⁰ ≈ 10⁶⁰ patterns. For Atari, 128 bytes have 256¹²⁸ ≈ 10³⁰⁸ combinations; an 84 × 84 image with 256 grayscale values per pixel has about 10¹⁶⁹⁹² possible images. Not every possible pattern is a reachable game situation.

Continuous environments (by crude discretization)

A simulated crawler with an articulated arm touching the ground — Crawler10²

A one-legged Hopper robot on a checkerboard floor — Hopper10¹⁰

A Humanoid robot walking on a checkerboard floor — Humanoid10¹⁰⁰

Angles, velocities, and joint positions take continuous values. Crude discretization replaces each variable with a small number of bins, allowing us to use a table, but the number of combinations grows exponentially with the number of variables.

\underset{\begin{matrix} ↑ \\ B bins for each of d variables \end{matrix}}{B^{d}}

With 10 bins per variable, 2 variables give 100 combinations, 10 give 10¹⁰, and 100 give 10¹⁰⁰. The slides’ continuous-environment counts depend on how the states are discretized. Finer bins grow the table further, while coarse bins lose detail.

A Q-table needs a value for every state-action pair. The obstacle is both memory and experience: too many entries to store, and too many to visit often enough. We need to share what we learn across similar states.

Approximate Q-Learning

Instead of a table, we have a parametrized Q function: Q_θ(s, a). The function predicts a Q-value from the state and action; θ is a shared set of learned parameters.

Can be a linear function in features:

Q_{θ} (s, a) = θ_{0} f_{0} (s, a) + \underset{\begin{matrix} ↑ \\ Learned weight \end{matrix}}{θ_{1}} \underset{\begin{matrix} ↑ \\ Feature \end{matrix}}{f_{1} (s, a)} + \dots + θ_{n} f_{n} (s, a)

Each fᵢ(s, a) describes some aspect of the state and action, and θᵢ controls its contribution. For example, navigation features could describe distance to the goal and nearby obstacles. A constant feature f₀ = 1 supplies a bias term. Shared weights let experience in one situation affect predictions in other, similar situations.

Or a neural net, decision tree, etc.

With a deep neural network, θ contains its weights and biases: this gives deep Q-learning. The gradient rule below applies to differentiable models, such as linear functions and neural networks.

Learning rule:

Remember:
$target (s^{'}) = \underset{\begin{matrix} ↑ \\ Observed reward \end{matrix}}{R (s, a, s^{'})} + \underset{\begin{matrix} ↑ \\ Best predicted future value \end{matrix}}{γ max_{a^{'}} Q_{θ_{k}} (s^{'}, a^{'})}$
This is the same sample target as before, now using Q_θₖ instead of a table. Compute it using the current parameters θₖ; hold that number fixed during this update. For a terminal next state, the target is just the observed reward.
Update:
$θ_{k + 1} \leftarrow θ_{k} - α \underset{\begin{matrix} ↑ \\ Gradient at current parameters \end{matrix}}{{\nabla_{θ} [\frac{1}{2} {(Q_{θ} (s, a) - target (s^{'}))}^{2}] ∣}_{θ = θ_{k}}}$
The squared error measures how far the current prediction is from the target. ∇_θ tells us how that error changes when the parameters change. Evaluate it at θₖ, then subtract α times the gradient to move toward a better prediction. The factor 1/2 cancels the 2 that appears when differentiating a square.
The target is fixed for this gradient step. Differentiate through the current prediction Q_θ(s, a), without differentiating through the target. We update shared parameters rather than one isolated table entry.

Recall Approximate Q-Learning

Instead of a table, we have a parametrized Q function. For example, a neural net Q_θ(s, a).

Learning rule:

Compute target:
$target (s^{'}) = \underset{\begin{matrix} ↑ \\ Observed reward \end{matrix}}{R (s, a, s^{'})} + \underset{\begin{matrix} ↑ \\ Best predicted future value \end{matrix}}{γ max_{a^{'}} Q_{θ_{k}} (s^{'}, a^{'})}$
Update Q-network:
$θ_{k + 1} \leftarrow θ_{k} - α \underset{\begin{matrix} ↑ \\ Gradient at current parameters \end{matrix}}{{\nabla_{θ} [\frac{1}{2} {(Q_{θ} (s, a) - target (s^{'}))}^{2}] ∣}_{θ = θ_{k}}}$

First predict the future return and construct a target; then train the network’s current prediction toward that target. θₖ labels the parameters before this update, and θₖ₊₁ labels them afterward. For example, if Q predicts 4 and the fixed target is 7, the update tries to raise that prediction.

DQN Training Algorithm

Algorithm 1: deep Q-learning with experience replay.

Initialize replay memory D to capacity N.

Initialize action-value function Q with random weights θ.

Initialize target action-value function Q̂ with weights θ⁻ = θ.

For episode = 1, …, M do

Initialize sequence and preprocessed sequence:

s_{1} = {x_{1}}, φ_{1} = φ (s_{1})

For t = 1, …, T do

With probability ε select a random action aₜ; otherwise select:

a_{t} = \underset{a}{arg max} Q (φ (s_{t}), a; θ)

Execute action aₜ in the emulator and observe reward rₜ and image xₜ₊₁.

Set sₜ₊₁ = (sₜ, aₜ, xₜ₊₁) and preprocess φₜ₊₁ = φ(sₜ₊₁).

Store transition (φₜ, aₜ, rₜ, φₜ₊₁) in D.

Sample a random minibatch of transitions (φⱼ, aⱼ, rⱼ, φⱼ₊₁) from D.

Set:

y_{j} = {\begin{cases} r_{j} & if episode terminates at step j + 1 \\ r_{j} + γ max_{a^{'}} \hat{Q} (φ_{j + 1}, a^{'}; θ^{-}) & otherwise \end{cases}

Perform a gradient descent step on:

{(y_{j} - Q (φ_{j}, a_{j}; θ))}^{2}

with respect to the network parameters θ, averaged over the minibatch.

Every C steps reset:

\hat{Q} = Q

End For

The agent acts in the environment and stores transitions in replay memory. A learner samples minibatches, updates the online Q-network, and periodically copies it to the target network.

Preprocessing φ: converts observation history into network input. A short stack of frames supplies motion information that a single image can miss.
Replay memory D: reuses past experience. Random minibatches reduce the strong correlations between consecutive observations. j indexes a stored transition, rather than the current interaction time t.
Online network Q, weights θ: selects greedy actions and receives gradient updates.
Target network Q̂, weights θ⁻: supplies future values for yⱼ. Keep it fixed between copies every C steps, so the network is not chasing a target that changes after every gradient update.
Terminal transitions: use only rⱼ because the episode has no future reward. Store whether a transition is terminal alongside the replay data.

DQN Details

Uses Huber loss instead of squared loss on Bellman error:
$L_{δ} (a) = {\begin{cases} \underset{\begin{matrix} ↑ \\ Small error: quadratic \end{matrix}}{\frac{1}{2} a^{2}} & for | a | \leq δ \\ \underset{\begin{matrix} ↑ \\ Large error: linear \end{matrix}}{δ (| a | - \frac{1}{2} δ)} & otherwise \end{cases}$
Here a is the prediction error Q − target, and δ > 0 is the threshold. Small errors use a smooth quadratic penalty. Large errors use a linear penalty, whose slope stops growing with the error. This reduces the influence of extreme errors compared with squared loss.
Uses RMSProp instead of vanilla SGD.
RMSProp adjusts parameter step sizes using a running average of squared gradients. Optimization in RL really matters: the network, the data we collect, and the targets all change during learning, so the optimizer and learning rate affect training stability.
It helps to anneal the exploration rate.
Start ε at 1 and gradually lower it to 0.1 or 0.05 over the first million frames, as in the slide. Early training explores broadly; later training uses the learned values more often. Keeping ε above zero leaves some exploration. ε controls action selection, while α controls how far a parameter update moves.

DQN on ATARI

49 ATARI 2600 games.
From pixels to actions.
The change in score is the reward.
Same algorithm.
Same function approximator, with about 1.7M learned parameters.
Same hyperparameters.
Roughly human-level performance on 29 out of 49 games.

The input is screen pixels; the outputs are Q-values for the available actions. Game-score changes provide reward, clipped to −1, 0, or +1 during training. The same architecture and training recipe were used across games, with a separate set of network weights trained for each game.

Double DQN

There is an upward bias in the maximum of estimated Q-values: when estimates contain error, the max tends to pick an action whose value has been overestimated.

max_{a} Q (s, a; θ)

For example, suppose two actions both have true value 5, and each estimate independently takes value 4 or 6 with equal probability. The four equally likely pairs have maxima 4, 6, 6, and 6. Their average is 5.5, even though each individual estimate averages 5. Selecting the largest estimate creates overestimation.

DQN already maintains two sets of weights, θ and θ⁻. Double DQN uses them for different parts of the next-state target:

θ: select the best next action with the online network.
θ⁻: evaluate that selected action with the target network.

a^{*} = \underset{\begin{matrix} ↑ \\ Select with online network \end{matrix}}{\underset{a^{'}}{arg max} Q (s^{'}, a^{'}; θ)}

y = r + γ \underset{\begin{matrix} ↑ \\ Evaluate with target network \end{matrix}}{Q (s^{'}, a^{*}; θ^{-})}

The online network supplies the action index a*. The target network then supplies the value of that action. This reduces the coupling between choosing an action for its high estimate and evaluating it with the same estimate.

Double DQN loss:

L_{i} (θ_{i}) = 𝔼_{(s, a, s^{'}, r) \sim D} [{(r + γ Q (s^{'}, \underset{a^{'}}{arg max} Q (s^{'}, a^{'}; θ_{i}); {θ_{i}}^{-}) - Q (s, a; θ_{i}))}^{2}]

The inner arg max uses θᵢ to choose an action at s′. The outer Q uses θᵢ⁻ to evaluate it. Discount that future value by γ and add the observed reward r to form the target; compare that target with Q(s, a; θᵢ), square the difference, and average over samples from replay memory D. Hold the target fixed when updating θᵢ. For terminal transitions, the target is just r.

For example, at s′ the online network estimates A = 8 and B = 7, while the target network estimates A = 5 and B = 6. Double DQN selects A with the online network and uses the target network’s value 5. With r = 1 and γ = 0.9, the target is 5.5. Standard DQN takes the target network’s maximum 6, giving a target of 6.4.

Atari results

Statistic	No ops		Human starts
Statistic	DQN	DDQN	DQN	DDQN	DDQN (tuned)
Median	93%	115%	47%	88%	117%
Mean	241%	330%	122%	273%	475%

These are human-normalized game scores: 100% corresponds to the human reference and 0% to the random-agent reference. “No ops” randomizes the initial state by waiting before play. “Human starts” begins from states sampled from human play, testing performance across a wider range of starting situations. Median summarizes the middle game; mean is more sensitive to very large scores on a few games.

Original Double DQN plots for Wizard of Wor and Asterix: orange DQN value estimates become large and unstable, while blue Double DQN estimates are steadier. The score plots below show stronger Double DQN performance. — Original paper, Figure 3: value estimates above and game scores below, for Wizard of Wor and Asterix. Orange: DQN; blue: Double DQN. In these examples, reducing overestimation also improves learning stability.

Prioritized Experience Replay

Replaying all transitions with equal probability is highly suboptimal.
Uniform replay gives every stored transition the same chance of being sampled. Some transitions are already predicted accurately, while others reveal a substantial mismatch between the prediction and its target. Training can use experience more efficiently by replaying the latter more often.
Replay transitions in proportion to absolute Bellman error:
$\underset{\begin{matrix} ↑ \\ Absolute TD error \end{matrix}}{| r + γ max_{a^{'}} Q (s^{'}, a^{'}; θ^{-}) - Q (s, a; θ) |}$
The first part, r + γ max Q(s′, a′; θ⁻), is the target. Subtract Q(s, a; θ), the current prediction. The absolute value measures how far apart they are, regardless of whether the prediction is too high or too low. A larger error raises the transition’s sampling priority. For a terminal transition, the target is just r.
For example, if one transition has target 10 and prediction 9.8, its error magnitude is 0.2. Another has target 5 and prediction 1, giving magnitude 4. In the slide’s direct proportional scheme, the second is 20 times as likely to be sampled. Its mismatch is larger, although its target is smaller.
In practice, a small positive priority keeps low-error transitions eligible for sampling. Importance-sampling weights correct the bias introduced by unequal sampling. Large TD error is a useful proxy for learning potential, though noisy outcomes can also produce large errors.
Leads to much faster learning.
More updates focus on transitions with substantial prediction errors. As the network learns, these errors and their priorities change. The original Atari experiments show faster learning and improved final scores.

Statistic	DQN		Double DQN (tuned)
Statistic	Baseline	Rank-based	Baseline	Rank-based	Proportional
Median	48%	106%	111%	113%	128%
Mean	122%	355%	418%	454%	551%
> baseline	—	41	—	38	42
> human	15	25	30	33	33
# games	49	49	57	57	57

Baseline uses uniform replay. Rank-based sampling prioritizes a transition according to its error’s position in the sorted list; proportional sampling uses the error magnitude. “> baseline” counts games that improve over the corresponding baseline, and “> human” counts games that exceed the human reference. The DQN results cover 49 games; the Double DQN results cover 57.

Original prioritized replay learning curves. Red rank-based and blue proportional replay reach the reference score sooner than black uniform Double DQN. Gray uniform DQN is lower. — Original paper, Figure 4: learning speed across 57 Atari games. Left: median of the best score achieved so far; right: median of the mean score achieved so far. Scores are normalized to the uniform Double DQN reference, so 100% marks that reference level. Red: rank-based; blue: proportional; black: uniform Double DQN; gray: uniform DQN.

Further DQN improvements

Prioritized Replay DDQN
Combines Double DQN’s action selection and evaluation with prioritized replay, so training samples emphasize transitions with larger TD errors.
Dueling DQN
The network has separate streams for the state’s value V(s) and each action’s advantage A(s, a), then combines them to form Q-values. This helps it learn how valuable a state is even when many actions have similar effects.
Distributional DQN
Predicts a probability distribution over possible future returns, giving more information than the average return alone. It can capture multiple possible outcomes even when we take the same action.
Noisy DQN
Adds learnable noise to network parameters to support exploration. The noise changes the action preferences produced by the network, and its scale is learned during training.

“Rainbow: Combining Improvements in Deep Reinforcement Learning,” Matteo Hessel et al., 2017

Rainbow combines six improvements: Double Q-learning, prioritized replay, dueling networks, multi-step returns, distributional learning, and noisy networks.

(Tabular) Q-Learning

Q-value iteration:

Rewrite as expectation:

(Tabular) Q-Learning: replace expectation by samples

For a state-action pair (s, a), receive:

Consider your old estimate:

Consider your new sample estimate:

Incorporate the new estimate into a running average:

(Tabular) Q-Learning: Algorithm

How to sample actions?

Choose random actions?

Choose action that maximizes Qk(s,a) (i.e. greedily)?

Why exploration matters

ε-Greedy: choose random action with prob. ε, otherwise choose action greedily

Two roles for a policy

Example

What does “converges to optimal policy” mean?

Caveats:

You have to explore enough

You have to eventually make the learning rate small enough

… but not decrease it too quickly

All states and actions are visited infinitely often

Learning rate schedule such that for all state and action pairs (s, a):

Example: αt(s,a)=1t+1

Discrete environments

Continuous environments (by crude discretization)

Can be a linear function in features:

Or a neural net, decision tree, etc.

Learning rule:

Remember:

Update:

Learning rule:

Compute target:

Update Q-network:

Algorithm 1: deep Q-learning with experience replay.

Uses Huber loss instead of squared loss on Bellman error:

Uses RMSProp instead of vanilla SGD.

It helps to anneal the exploration rate.

Double DQN loss:

Atari results

Replaying all transitions with equal probability is highly suboptimal.

Replay transitions in proportion to absolute Bellman error:

Leads to much faster learning.

Further DQN improvements

Choose action that maximizes $Q_{k} (s, a)$ (i.e. greedily)?

Example: $α_{t} (s, a) = \frac{1}{t + 1}$