Q-Learning

Definition

$Q(S_t,A_t)\leftarrow Q(S_t,A_t)+\alpha [R_{t+1}+\gamma {\max }_{a}Q(S_{t+1},a)-Q(S_t,A_t)]$ Q-learning directly learns $Q^{\ast }$ by using Bellman Optimality Equation. The behavior policy of Q-learning is derived from $Q$ while the target policy is ${\max }_{a}Q$, so it is an off-policy method.

Algorithm

1. Initialize $\forall s\in \mathcal{S},a\in \mathcal{A}(S)$, $Q(s,a)$ arbitrarily, and $Q(\text{terminal},\cdot )=0$.
2. Repeat for each episode:
   1. Initialize $S$.
   2. Repeat for each step of an episode until $S$ is terminal:
      1. Choose an action $A$ from the initial state $S$ using policy derived from $Q$ (e.g. $ϵ$-greedy).
      2. Take the action $A$ and observe a reward $R$ and a next state $S^{\prime }$.
      3. $Q(S,A)\leftarrow Q(S,A)+\alpha [R+\gamma \underset{a}{\max }Q(S^{\prime },a)-Q(S,A)]$
      4. Update $S\leftarrow S^{\prime }$