Notes

Temporal Difference (TD) Rule to Q-Learning Key Idea of the Temporal Difference Rule (TDR): update the value of the current state based on the immediate reward and the estimated value of the next state. Interpretation: we must not look only at immediate rewards but future rewards should be taken into consideration as well on a discounted valuation. We assume that the path our agents takes to navigate the system is given.

$$V\left( s_{t} \right) \leftarrow V\left( s_{t} \right) + \eta\left\lbrack r_{t + 1} + \gamma V\left( s_{t + 1} \right) - V\left( s_{t} \right) \right\rbrack$$

where $V\left( s_{t} \right)$ is the previous estimate, $r_{t + 1}$ is the next reward, $\gamma V\left( s_{t + 1} \right)$ is the discounted value on the next step and $r_{t + 1} + \gamma V\left( s_{t + 1} \right)$ represents the TD target.

Lets now include the fundamental concept of an action to this equation. This adds one dimension to the value function and gives the agent a choice. This new function is called $Q(s,\ a)$

$$Q(s,\ a) = \mathbb{E}_{(r',\ s')|s,a}\lbrack r + \gamma\max_{a^{'}}\lbrack Q(s',\ a')\rbrack\rbrack$$

By just a few trivial steps one can show that the TD rule is used to get the convex combination in the Q-Learning update rule between old and new Q value seen in the literature:

Given this rule, we can create and update a map over future states and actions. We can optimize w.r.t. the action to get an optimal path (policy). The key idea is that we do not need to know any transition probabilities to learn (model), we just need an unbiased estimate from out world (sample). We can get these samples by just playing the "game". If we store the actions a and rewards r from these samples, we can directly apply Q-learning. Thus, Q-learning is considered model-free. Keep in mind that (in the end), the optimal policy can be deducted from the optimal value function V*:

$$V^{*}(x) = max_{a}Q^{*}(x,a)$$