The Q-Learning algorithm#

Step 1: We initialize the Q-table

Step 2: Choose an action using the epsilon-greedy strategy

The epsilon-greedy strategy is a policy that handles the exploration/exploitation trade-off. The idea is that:

• With probability $1-ϵ$ : we do exploitation (our agent selects the action with the highest state-action pair value).

• With probability $ϵ$ : we do exploration (trying random action).

At the beginning of the training, the probability of doing exploration will be huge since $ϵ$ is very high, so most of the time, we’ll explore. But as the training goes on, and consequently our Q-table gets better and better in its estimations, we progressively reduce the epsilon value since we will need less and less exploration and more exploitation.

Step 3: Perform action $A_t$, get reward $R_{t+1}$ and next state $S_{t+1}$

Step 4: Update $Q(S_t,A_t)$

Remember that in TD Learning, we update our value function after one step of the interaction.

In Q-learning, to produce our TD target, we used the immediate reward $R_{t+1}$ plus the discounted value of the next state, computed by finding the action that maximizes the current Q-function at the next state.

Off-policy vs On-policy#

Two policies exist in any reinforcement learning task: a behavior policy and a target policy. The behavior policy is the one used to generate experience samples. The target policy is the one that is constantly updated to converge to an optimal policy. When the behavior policy is the same as the target policy, such a learning process is called on-policy. Otherwise, when they are different, the learning process is called off-policy.

• Sarsa is on-policy. The samples required by Sarsa in every iteration include $(S_t,A_t,R_{t+1},S_{t+1},A_{t+1})$. How these samples are generated is illustrated below:

  $$S_t,A_t\stackrel{\text{enviroment}}{⟶}{R}_{t+1},S_{t+1}\stackrel{\pi }{⟶}{A}_{t+1}$$

  $A_{t+1}$ is dependent on the target policy $\pi$.

• Q-learning is off-policy. The samples required by Q-learning in every iteration is $(S_t,A_t,R_{t+1},S_{t+1})$. How these samples are generated is illustrated below:

  $$S_t,A_t\stackrel{\text{enviroment}}{⟶}{R}_{t+1},S_{t+1}$$

  the estimation of the optimal action value of $(S_t,A_t)$ does not involve $\pi$ and we can use any policy to generate samples.