Exercise 6.3.1

Tabular methods as linear function approximation with one-hot features

Reinforcement Learning › Exercises › Lecture 6 · Function Approximation › 6.3 Control with value-function approximation
EasyWritten

Explain how tabular methods for action-value functions (such as SARSA and Q-learning) can be viewed as a special case of linear function approximation.

  • (a) First, describe the specific choice of feature vectors, \(\mathbf{x}(s,a)\), that makes the linear approximation \(\hat{q}(s,a, \mathbf{w}) = \mathbf{w}^\top \mathbf{x}(s,a)\) equivalent to a Q-table. What is the relationship between the weight vector \(\mathbf{w}\) and the Q-table entries in this case?

  • (b) Using these features, take the general semi-gradient SARSA update rule and show how it simplifies to become identical to the standard tabular SARSA update rule.

Adapted from Sutton & Barto (2018), Reinforcement Learning: An Introduction, 2nd ed., Exercise 9.1. Licensed CC BY-NC-ND 2.0.