Q-learning and SARSA updates

ImplementEasy15 min13 checks

reinforcement-learning q-learning sarsa exploration

Lesson: Temporal Difference — Q-Learning & SARSA Cheat sheet Track: RL basics

Tabular Q-learning and SARSA learn a table of action values from one transition at a time. Both move $inline$ toward a target. Q-learning uses the best next action in the target. SARSA uses the next action that the agent really takes. An epsilon-greedy policy picks the actions while the table learns.

Task

Write three functions.

q_learning_update(Q, s, a, r, s_next, done, alpha=0.1, gamma=0.99) returns the table after one Q-learning update.
sarsa_update(Q, s, a, r, s_next, a_next, done, alpha=0.1, gamma=0.99) returns the table after one SARSA update.
epsilon_greedy(Q, s, epsilon, rng) returns the action for state s.

Both updates change only the entry $inline$ :

display

The target $inline$ for Q-learning is $inline$ . The target for SARSA is $inline$ . When done is True, the target is $inline$ only, with no term for the next state. The target uses the values of Q before the update.

epsilon_greedy uses the generator rng in this exact order:

Draw u = rng.random().
If u < epsilon, draw and return rng.integers(n_actions).
Else return the action with the largest Q[s]. On a tie, return the lowest index.

Input and output

Name	Type	Shape	Meaning
`Q`	float array	`(n_states, n_actions)`	the action values
`s`, `s_next`	int		the state and the next state
`a`, `a_next`	int		the action and the next action
`r`	float		the reward of the transition
`done`	bool		`True` when `s_next` is terminal
`alpha`	float		the step size, from 0 to 1
`gamma`	float		the discount, from 0 to 1
`epsilon`	float		the probability of a random action, from 0 to 1
`rng`	`np.random.Generator`		the random generator

q_learning_update and sarsa_update return a new float array of shape (n_states, n_actions).
epsilon_greedy returns a Python int.

Constraints

1 <= n_states <= 1000 and 1 <= n_actions <= 20.
s_next can be equal to s.
Do not change the input table. Return a new table.
Use numpy only.

Examples

pythonQ = np.array([[0.0, 1.0], [2.0, -1.0], [0.5, 0.5]])
q_learning_update(Q, 0, 1, -1.0, 1, False, alpha=0.5, gamma=0.9)
sarsa_update(Q, 0, 1, -1.0, 1, 1, False, alpha=0.5, gamma=0.9)
q_learning_update(Q, 0, 1, -1.0, 1, True, alpha=0.5, gamma=0.9)

text[[ 0.   0.9]
 [ 2.  -1. ]
 [ 0.5  0.5]]
[[ 0.   -0.45]
 [ 2.   -1.  ]
 [ 0.5   0.5 ]]
[[ 0.   0. ]
 [ 2.  -1. ]
 [ 0.5  0.5]]

pythonrng = np.random.default_rng(7)
Q = np.array([[1.0, 3.0, 3.0, 0.0]])
[epsilon_greedy(Q, 0, 0.5, rng) for _ in range(12)]

text[1, 1, 1, 0, 1, 1, 1, 1, 3, 1, 3, 1]

Hints

4 hints

Solution and notes

Locked

Pass every check with Submit to open the reference solution and the notes.

Run it on your computer

Clone the repository, install numpy and run the same checks in a terminal:

python3 scripts/practice/run.py q-learning-update my_answer.py
python3 scripts/practice/run.py q-learning-update my_answer.py --examples

Start my_answer.py from starter.py.

Your code is saved in this browser as you type. On a phone you can read and edit the code, but the checks are easier to use on a desktop.

Keyboard shortcuts

Ctrl Enter: Run the examples
Ctrl Shift Enter: Submit
Tab / Shift Tab: Indent or outdent the lines
Esc then Tab: Move the focus out of the editor
Alt H: Show the next hint

On a Mac, use Cmd in place of Ctrl.

Select Run to check the examples, or Submit to run every check.

Problem