Fitted Q-Learning

The tabular Monte Carlo methods and TD algorithms repeatedly traverse the entire MDP and update the action values. However, this is only practical if the state-action space is small.

In fitted Q-learning, the discrete representation $q[s_t,a_t]$ of the action values is replaced by a machine learning model $q[{\mathbf{s}}_t,a_t,\varphi ]$, where now the state is represented by a vector $s_t$ rather than just an index.

We then define a least squares loss based on the consistency of adjacent action values (similar to Q-Learning):

$$L[\varphi ]=(r[{\mathbf{s}}_t,a_t]+\gamma \cdot \underset{a}{\max }[q[{\mathbf{s}}_{t+1},a,\varphi ]]-q[s_t,a_t,\varphi ]{)}^2$$

which in turn leads to the update:

$$\varphi \leftarrow \varphi +\alpha (r[{\mathbf{s}}_t,a_t]+\gamma \cdot \underset{a}{\max }[q[{\mathbf{s}}_{t+1},\alpha ,\varphi ]]-q[{\mathbf{s}}_t,a_t,\varphi ])\frac{\partial q({\mathbf{s}}_t,a_t,\varphi )}{\partial \varphi }$$

Fitted Q-learning differs from Q-Learning in that convergence is no longer guaranteed. A change to the parameters potentially modifies both the target $r[{\mathbf{s}}_t,a_t]+\gamma \cdot {\text{max}}_{a_{t+1}}[q[{\mathbf{s}}_{t+1},a_{t+1},\varphi ]]$ (the maximum value may change) and the prediction $q[{\mathbf{s}}_t,a_t,\varphi ]$. This can be shown both theoretically and empirically to damage convergence.

• Deep Q-Networks
• Double Q-Learning