Q-learning

Machine Learning methodology to optimize actions $a\in A$ taken over states $s\in S$ by learning the $Q$-function $Q(s,a)$. This is done by:

1. Initialising the $Q$-table $Q(s,a)$, possibly with random values
2. Updating $Q(s,a)$ with $Q(s_t,a)+\alpha \left[r+\gamma ma{x}_{a’}Q(s_{t+1},a’)-Q(s,a)\right]$ by taking an exploratory action $a$ where:
   1. $\alpha$ is our learning rate
   2. $r$ is our immediate reward, built as an estimate of how far we are from our target.
   3. $\gamma$ is the time based discount applied to our rewards.
   4. $Q(s,a)$ is our previous estimate of the $Q$-function.
   5. $s_{t+1}$ is our state after we took a potentially probabilistic action $a$, weighted towards actions with higher expected $Q$-value.

It is optimal to let our choice of $a$ have high Entropy at first, and as we have a better estimate of $Q$-values, we bias our choice of $a$ towards high reward actions.

Info

E-learning can be seen as Dynamic programming with recursive dependencies. The true value of each entry in the dynamical programming table is done through multiple passes of the table, with the end result converging to the true value.