Reinforcement Learning Exercises
Exercises for every lecture, in teaching order, from easy to hard within each concept.
Exercises for the lectures, grouped by the concept they practise and in the order the slides teach them. Within a concept they go from easy to hard. An exercise that practises several concepts is filed under the last of them (review exercises stay in the review), and the other concepts list it under "Also practised in". Each exercise has its own page; the course map links to them next to the slides and tutorial tasks.
RBackground review29 exercises
R.1 Random variablesSlides L1 · 8–10
- Ex R.1.1 Conditional probability: pass versus study-and-pass (conjunction fallacy) Easy Written
- Ex R.1.2 Conditional probability: prove Bayes' theorem Easy Written
- Ex R.1.3 Conditional probability: random moves between four rooms Easy Written
- Ex R.1.4 Independence: the two definitions are equivalent Easy Written
- Ex R.1.5 Law of total probability: bulbs from two factories Easy Written
- Ex R.1.6 Probability density function: P(X=x)=0 for a continuous variable Easy Written
- Ex R.1.7 Probability density function: show the uniform density is a pdf Easy Written
- Ex R.1.8 Random variables: values and type of number of sixes in N dice Easy Written
- Ex R.1.9 Conditional probability: conditional is at least the joint Medium Written
- Ex R.1.10 Conditional probability: ratio of conditionals equals ratio of joints Medium Written
- Ex R.1.11 Random variables: are rewards discrete, continuous or mixed Medium Written
Also practised in Ex R.4.4
R.3 Expected valueSlides L1 · 14–17
- Ex R.3.1 Expected value: return of policies in a three-cell corridor Easy Written
- Ex R.3.2 Gradients: simplify five expressions with expectations Easy Written
- Ex R.3.3 Partial derivatives: six expressions including an expectation Easy Written
- Ex R.3.4 Expected value: r(s,a,s') from p Medium Written
- Ex R.3.5 Gradients: true or false on six identities Medium Written
Also practised in Ex R.4.1, Ex R.4.2, Ex R.4.3, Ex 2.4.4, Ex 2.4.5, Ex 2.4.6, Ex 2.4.7, Ex 5.5.4
R.4 Probability mass functionsSlides L1 · 26
- Ex R.4.1 Expected value: gradient of E[log π(X)] is zero Easy Written
- Ex R.4.2 Expected value: r(s,a) from the four-argument p Easy Written
- Ex R.4.3 Expected value: r(s,a) from the four-argument p Easy Written
- Ex R.4.4 Joint pmf: marginals, conditional and independence Easy Written
- Ex R.4.5 Probability mass functions: construct and verify a fair-coin pmf Easy Written
- Ex R.4.6 Probability mass functions: show the ε-greedy policy is a pmf Easy Written
Also practised in Ex 2.4.4
R.5 Step-size conditionsSlides L1 · 38
- Ex R.5.1 Derivatives: four elementary derivatives Easy Written
- Ex R.5.2 Gradient descent: learning rate reaching the minimum in one step Easy Written
- Ex R.5.3 Sequences: convergence and limits of three sequences Easy Written
- Ex R.5.4 Series: convergence of eight sums (geometric, p-series) Easy Written
- Ex R.5.5 Gradient descent: starting points stuck at a saddle point Medium Written
- Ex R.5.6 Gradient descent: starting points that end in a local minimum Medium Written
- Ex R.5.7 Gradients: counterexample for swapping gradient and sum Hard Written
1Exploration Methods17 exercises
1.2 Sample-average methodSlides L1 · 33–38
- Ex 1.2.1 Sample-average method: Q-values at t = 9 from a reward table Easy Written
1.3 Weighted-average method (nonstationary problems)Slides L1 · 39–46
- Ex 1.3.1 Weighted-average method: step size α from the target and estimate plot Easy Multiple choice
- Ex 1.3.2 Weighted-average method: step size α from the target and estimate plot Easy Multiple choice
- Ex 1.3.3 Weighted-average method: Q-values at t = 9 from a reward table, α = 0.5 Easy Written
- Ex 1.3.4 Weighted-average method: Q_{n+1} in terms of Q_1 and past rewards Medium Written
Also practised in Ex 1.9.3
1.4 GreedySlides L1 · 49–53
1.5 ε-greedySlides L1 · 54–63
- Ex 1.5.1 ε-greedy: probability of the greedy action, five actions, ε = 0.3 Easy Multiple choice
- Ex 1.5.2 ε-greedy: probability of the greedy action, four actions, ε = 0.2 Easy Multiple choice
- Ex 1.5.3 ε-greedy: probability of the greedy action, two actions, ε = 0.5 Easy Written
- Ex 1.5.4 ε-greedy: long-run best method in the 10-armed testbed figure Medium Written
- Ex 1.5.5 ε-greedy: time steps where exploration definitely or possibly occurred Medium Written
Also practised in Ex R.4.6, Ex 1.9.2, Ex 1.9.3, Ex 5.2.3, Ex 5.5.3, Ex 5.6.1
1.7 Upper confidence bound (UCB)Slides L1 · 71–77
- Ex 1.7.1 Upper confidence bound (UCB): derive the uncertainty term Hard Written
1.9 Policy gradient methods: action preferencesSlides L1 · 83–100
- Ex 1.9.1 Action preferences with baseline: effect of reward above or below baseline Easy Written
- Ex 1.9.2 Exploration methods: deterministic versus stochastic policies, hyperparameters, baseline Easy Written
- Ex 1.9.3 Action-value methods and policies: probabilities of each action at t = 9 Easy WrittenCoding
- Ex 1.9.4 Softmax over Q* (SARSA) vs softmax over action preferences Medium Written
2The RL Problem and Finite MDPs17 exercises
2.1 Markov decision processSlides L2 · 15–26
- Ex 2.1.1 Markov decision process: states, actions, rewards for traffic light control Medium Written
2.2 Markov propertySlides L2 · 27–29
2.3 Returns and discountingSlides L2 · 34–40
- Ex 2.3.1 Returns and discounting: G_1 with γ = 0.5 and five rewards Easy Multiple choice
- Ex 2.3.2 Returns and discounting: G_2 with γ = 0.5 and five rewards Easy Multiple choice
- Ex 2.3.3 Returns and discounting: maze, reward design, discounted and undiscounted Medium Written
- Ex 2.3.4 Returns and discounting: pole balancing, episodic vs continuing return Medium Written
Also practised in Ex 2.4.5, Ex 2.4.6, Ex 2.4.7, Ex 2.5.1, Ex 3.6.2, Ex 3.6.3, Ex 4.1.1, Ex 4.2.1, Ex 5.2.2
2.4 Bellman expectation equationsSlides L2 · 47–61
- Ex 2.4.1 Value functions: comparing policies by v_π(s) in every state Easy Multiple choice
- Ex 2.4.2 Bellman expectation equations: numeric check at a gridworld state valued +3.0 Easy Written
- Ex 2.4.3 Bellman expectation equations: numeric check at the gridworld centre state Easy Written
- Ex 2.4.4 Bellman expectation equations: derive v_π(s) = Σ π(a|s) q_π(s,a) Medium Written
- Ex 2.4.5 Bellman expectation equations: prove q_π from v_π and p Medium Written
- Ex 2.4.6 Bellman expectation equations: prove q_π from v_π and p Medium Written
- Ex 2.4.7 Bellman expectation equations: q_π in terms of v_π and four-argument p Medium Written
Also practised in Ex 2.6.2, Ex 3.1.1, Ex 3.1.2, Ex 3.3.1, Ex 7.5.3
2.5 Bellman optimality equationsSlides L2 · 62–69
- Ex 2.5.1 Returns and discounting: optimal policy of a two-action MDP for γ = 0, 0.5, 0.9 Medium Written
2.6 Bellman equation in matrix formSlides L2 · 73–74
- Ex 2.6.1 Bellman equation in matrix form: r^π and P^π, equiprobable policy Easy Written
- Ex 2.6.2 Bellman equation in matrix form: three-state MDP, r^π, P^π, v Easy WrittenCoding
Also practised in Ex 3.4.3
3Dynamic Programming13 exercises
3.1 Policy evaluationSlides L3 · 12–19
- Ex 3.1.1 Policy evaluation: q_π and an added state in the 4x4 gridworld Medium Written
- Ex 3.1.2 Policy evaluation: q_π and an added state in the 4x4 gridworld (exam) Medium Written
Also practised in Ex 3.3.1, Ex 3.3.3, Ex 3.4.3, Ex 3.4.4, Ex 5.3.5
3.3 Policy iterationSlides L3 · 37–39
- Ex 3.3.1 Policy iteration: stochastic policies, 3-argument p, and the action-value version Medium Written
- Ex 3.3.2 Policy iteration: time complexity with V(s) versus Q(s,a) Medium Written
- Ex 3.3.3 Policy iteration: ε-soft policies, tie-breaking, action-value version Medium Written
- Ex 3.3.4 Policy improvement theorem: proof for stochastic policies Hard Written
3.4 Value iterationSlides L3 · 40–44
- Ex 3.4.1 Value iteration: action-value analogue q_{k+1}(s,a) Easy Written
- Ex 3.4.2 Value iteration: update rule for action values q_{k+1}(s,a) Easy Written
- Ex 3.4.3 Dynamic programming solvers: design an MDP, matrix-form Bellman solver, VI and PI Medium Coding
- Ex 3.4.4 Policy iteration and value iteration: implement on a 3-state MDP Medium Coding
3.6 Bellman operators and the Banach fixed-point theoremSlides L3 · 46–66
- Ex 3.6.1 Bellman optimality operator: why γ-contraction gives convergence of value iteration Easy Written
- Ex 3.6.2 Value iteration: return bound, convergence, stopping rule, numeric threshold Medium Written
- Ex 3.6.3 Value iteration: return bound, error bound proof, stopping rule, convergence Hard Written
4Monte Carlo Methods and TD Learning12 exercises
4.1 Monte Carlo predictionSlides L4 · 7–17
4.2 Temporal-difference learning: TD(0)Slides L4 · 18–29
- Ex 4.2.1 TD error for action values: identity G_t - Q(S_t,A_t) as a sum of TD errors Easy Written
- Ex 4.2.2 TD(0): first-episode update in the random walk Medium Written
Also practised in Ex 4.3.1, Ex 4.3.2, Ex 4.3.3, Ex 4.3.4, Ex 4.5.2, Ex 5.2.2, Ex 5.3.5, Ex 5.7.2, Ex 6.1.2, Ex 7.5.1, Ex 7.5.2, Ex 7.5.3
4.3 MC vs TD: bias and variance, batch updatesSlides L4 · 30–39
- Ex 4.3.1 Temporal-difference learning: why TD estimates are biased (MCQ) Easy Multiple choice
- Ex 4.3.2 Batch Monte Carlo versus batch TD(0): value estimates from eight episodes Easy Written
- Ex 4.3.3 MC vs TD: when a TD update beats a Monte Carlo update (driving home) Medium Written
- Ex 4.3.4 TD(0): Monte Carlo error as a sum of TD errors when V changes Hard Written
Also practised in Ex 8.1.1
4.4 Multi-step TDSlides L4 · 40–45
- Ex 4.4.1 n-step TD: why a 19-state random walk and how n changes with the task Medium Written
Also practised in Ex 8.1.2
4.5 Mixed multi-step returns and eligibility tracesSlides L4 · 46–66
5Model-Free Control16 exercises
5.2 SARSA: on-policy TD controlSlides L5 · 22–24
- Ex 5.2.1 Monte Carlo control, GLIE: behaviour-policy conditions for SARSA convergence Easy Multiple choice
- Ex 5.2.2 SARSA: derive sampled policy-evaluation update, role of alpha and gamma Easy Written
- Ex 5.2.3 SARSA: find and fix errors in faulty pseudocode Medium Written
Also practised in Ex 5.3.1, Ex 5.3.2, Ex 5.3.4, Ex 5.3.5, Ex 5.3.6, Ex 5.6.1, Ex 6.3.1, Ex 6.3.2
5.3 Q-learning (off-policy learning)Slides L5 · 26–30
- Ex 5.3.1 On-policy vs off-policy: SARSA vs Q-learning, advantages and disadvantages Easy Multiple choice
- Ex 5.3.2 Q-learning vs SARSA: off-policy vs on-policy control Easy Written
- Ex 5.3.3 Q-learning: find and fix errors in faulty pseudocode Easy Written
- Ex 5.3.4 SARSA/Q-learning: numeric update of Q(s1,1) from a Q-table Easy Written
- Ex 5.3.5 DP vs sampled updates: model-free counterparts, no sampled value iteration Medium Written
- Ex 5.3.6 Q-learning vs SARSA: equivalence under greedy action selection Hard Written
Also practised in Ex 5.5.1, Ex 5.5.2, Ex 5.5.4, Ex 5.6.1, Ex 5.7.1, Ex 6.3.2, Ex 8.1.2
5.5 Maximization bias and double Q-learningSlides L5 · 34–42
- Ex 5.5.1 Maximization bias: why Q-learning overestimates Easy Multiple choice
- Ex 5.5.2 Maximization bias: why Q-learning overestimates, mitigation Easy Written
- Ex 5.5.3 Expected SARSA: Double Expected SARSA update equations Medium Written
- Ex 5.5.4 Maximization bias: when overestimation helps, bias parameter mu Medium Written
Also practised in Ex 5.6.1
5.6 Deep Q-networks: experience replay, target networkSlides L5 · 44–48
- Ex 5.6.1 Cliff Walking: SARSA, Q-learning, double Q-learning, DQN experiments Medium WrittenCoding
5.7 Importance samplingSlides L5 · 50–60
- Ex 5.7.1 Off-policy learning: identify an off-policy scenario Easy Multiple choice
- Ex 5.7.2 Importance sampling: off-policy TD(0) update (exercise 6.7) Easy Written
Also practised in Ex 7.2.1
6Function Approximation11 exercises
6.1 Value function approximation by stochastic gradient descentSlides L6 · 14–35
6.2 Linear function approximationSlides L6 · 40–51
6.3 Control with value-function approximationSlides L6 · 52–57
- Ex 6.3.1 Tabular methods as linear function approximation with one-hot features Easy Written
- Ex 6.3.2 On-policy vs off-policy control: data efficiency and exploration Medium Written
Also practised in Ex 6.4.5
6.4 Convergence, divergence and experience replaySlides L6 · 58–63
- Ex 6.4.1 Deep Q-networks: target network against the deadly triad Easy Multiple choice
- Ex 6.4.2 Linear to deep function approximation: DQN, challenges, remedies Easy Written
- Ex 6.4.3 Linear vs non-linear function approximators: trade-offs Easy Written
- Ex 6.4.4 Deadly triad and DQN: instability, experience replay, target network Medium Written
- Ex 6.4.5 Semi-gradient SARSA: on-policy vs off-policy closeness to gradient descent Medium Written
7Policy Gradients and Actor-Critic16 exercises
7.1 Policy-based RL: parameterized policiesSlides L7 · 9–18
- Ex 7.1.1 Policy-based RL: advantage over value-based methods (MCQ) Easy Multiple choice
- Ex 7.1.2 Policy-based RL: family for continuous action spaces (MCQ) Easy Multiple choice
- Ex 7.1.3 Stochastic policies: advantage under partial observability (MCQ) Easy Multiple choice
- Ex 7.1.4 Stochastic policies: advantage with near-optimal actions (MCQ) Easy Multiple choice
- Ex 7.1.5 Policy-based vs value-based RL: continuous action spaces Easy Written
- Ex 7.1.6 Stochastic policies: perceptual aliasing, policy gradient vs Q-learning Easy Written
Also practised in Ex 7.4.2
7.2 Policy-gradient theoremSlides L7 · 19–30
- Ex 7.2.1 Policy-gradient theorem: on-policy requirement and off-policy mismatch Medium Written
7.3 REINFORCESlides L7 · 31–32
- Ex 7.3.1 REINFORCE derivation: model-dependent terms and model-free property Easy Written
7.4 Reducing the variance: causality and baselineSlides L7 · 33–40
- Ex 7.4.1 Baseline in REINFORCE: motivation and required property Easy Written
- Ex 7.4.2 REINFORCE vs value-based: action spaces, exploration, variance (mock) Easy Written
- Ex 7.4.3 Policy-gradient theorem: unbiasedness of the baseline estimate Medium Written
- Ex 7.4.4 REINFORCE with baseline: unbiasedness, variance, exploration, principles Medium Written
7.5 Actor-critic, advantage function, A2CSlides L7 · 41–54
- Ex 7.5.1 Actor-critic: roles of actor and critic, TD error as baseline Easy Written
- Ex 7.5.2 Baseline and advantage function: TD error as advantage estimate Easy Written
- Ex 7.5.3 TD target as estimate of V or Q; TD error as advantage Medium Written
- Ex 7.5.4 REINFORCE, actor-critic and PPO: Inverted Pendulum programming task Hard Coding