5.3. Model-Free Learning

Model-Free Learning

Model-free learning bypasses explicit modeling of $T$ and $R$ by learning values or Q-values directly from experience. There are several model-free learning algorithms:

• Direct Evaluation is a passive algorithm that evaluates a fixed policy $\pi$ by following it for many episodes and recording the total utility obtained from each state. Then, it computes
  $V^{\pi }(s)=\frac{1}{N_s}{\sum }_{k=0}^{T-t_s-1}{\gamma }^k{r}_{t+k},$
  where $N_s$ is the number of visits to state $s$, $T$ is the total length of the episode, $t_s$ is the time-step of the first appearance of state $s$ in the current episode, $\gamma$ is the discount factor, and $r_t$ is the reward at time-step $t$. Although direct evaluation is guaranteed to converge, it is slow, since it ignores transition structure and learns only from complete episodes.
  ⠀
• Temporal Difference Learning improves on direct evaluation by learning after every step rather than after each episode using an exponential moving average, slowly iterating over
  $V^{\pi }(s)\leftarrow (1-\alpha )V^{\pi }(s)+\alpha [R(s,\pi (s),s’)+\gamma V^{\pi }(s’)],$
  where $0\le \alpha \le 1$ is the learning rate, which starts at $1$ and slowly converges to $0$, thereby making all subsequent samples have no affect on the model.
  ⠀
• Q-Learning is an active, model-free algorithm that learns optimal Q-values directly, without needing an optimal policy. It uses a similar update rule to TDL, such that
  $Q(s,a)\leftarrow (1-\alpha )Q(s,a)+\alpha [R(s,a,s’)+\gamma {\max }_{a’}Q(s’,a’)].$
  This enables the agent to learn the optimal policy while still exploring - known as off-policy learning - since updates can be made even from suboptimal or random actions. Over time (with sufficient exploration and decaying $\alpha$), Q-learning converges to $Q^{\ast }(s,a)$, and the agent can act greedily with respect to $Q^{\ast }$ for reward maximization.