Model-Free Control (RL)

Notes of lectures by D. Silver.

For problems like elevator, robot walking and the game of Go, MDP model is unknown, but experience can be sampled; or MDP model is known, but is too big to use, except by samples. Model-free control could solve this.

• On-policy learning
  • “learn on the job“
  • Learn about policy $\pi$ from experience sampled from $\pmb{\pi}$
• Off-policy learning
  • “learn over someone’s shoulder“
  • Learn about policy $\pi$ from experience sampled from $\pmb{\mu}$

On-policy

On-policy Monte-Carlo control

• Greedy policy improvement over $V(s)$ requires model of MDP: $$\pi'(s) = \arg\max_{a \in \mathcal{A}} \mathcal{R}_s^a + \mathcal{P}_{ss'}^a V(s')$$
• Greedy policy improvement over $Q(s,a)$ is model-free: $$\pi'(s) = \arg\max_{a \in \mathcal{A}} Q(s,a)$$

$\epsilon$-greedy exploration

• Simplest idea for ensuring continual exploration
• All $m$ actions are tried with non-zero probability
• With probability $1-\epsilon$ choose the greedy action
• With probability $\epsilon$ choose an action at random

$$\pi(a \vert s) = \left\{ \begin{array}{ll} \frac{\epsilon}{m} + 1 - \epsilon \quad \text{if } a^* =\arg\max_{a \in \mathcal{A}} Q(s,a) \\ \frac{\epsilon}{m} \quad \text{ otherwise} \end{array} \right.$$

On-policy Temporal-Difference learning

MC vs. TD control

• TD learning has several advantages over MC:
  • Lower variance
  • Online
  • Incomplete sequences
• Natural idea: use TD instead of MC in out control loop
  • Apply TD to $Q(S,A)$
  • Use $\epsilon$-greedy policy improvement
  • Update every time-step

Sarsa($\lambda$)

SARSA:

$$Q(S,A) \leftarrow Q(S,A) + \alpha (R+ \gamma Q(S',A') - Q(S,A))$$

Every time-step:

• Policy evaluation Sarsa: $Q \approx q_{\pi}$
• Policy improvement $\epsilon$-greedy policy improvement

$n$-step Sarsa

• Consider the following $n$-step returns for $n=1,2,\infty$

$$\begin{bmatrix} n=1 & (Sarsa) & q_t^{(1)} = R_{t+1} + \gamma Q(S_{t+1}) \\ n=2 & & q_t^{(2)} = R_{t+1} + \gamma R_{t+2} + \gamma^2 Q(S_{t+2}) \\ \vdots & & \vdots \\ n=\infty & (MC) & q_t^{(\infty)} = R_{t+1} + \gamma R_{t+2} + \cdots +\gamma^{T-1} R_T \end{bmatrix}$$

• Define the $n$-step Q-return

  $$q_t^{(n)} = R_{t+1} + \gamma R_{t+2} + \cdots + \gamma^{n-1}R_{t+n} + \gamma^n Q(S_{t+n})$$

• $n$-step Sarsa updates $Q(s,a)$ towards the n-step Q-return

  $$Q(S_t,A_t) \leftarrow Q(S_t,A_t) + \alpha \big( q_t^{(n)} - Q(S_t, A_t) \big)$$

Forward-view Sarsa($\lambda$)

• The $q^{\pi}$ return combines all $n$-step Q-returns $q_t^{(n)}$
• Using weight $(1-\lambda) \lambda^{(n-1)}$ $$q_t^{\lambda} = (1-\lambda) \sum_{n=1}^{\infty} \lambda^{n-1} q_t^{(n)}$$
• Forward-view Sarsa($\lambda$) $$Q(S_t,A_t) \leftarrow Q(S_t,A_t) + \alpha \big( q_t^{(n)} - Q(S_t, A_t) \big)$$

Back-view Sarsa($\lambda$)

• Like TD($\lambda$), we use eligibility traces
• Sarsa($\lambda$) has one eligibility trace for each state-action pair

$$E_0(s,a) = 0$$ $$E_t(s,a) = \gamma \lambda E_{t-1}(s,a) + \mathbb{I}(S_t = s, A_t = a)$$

• $Q(s,a)$ is updated for every state $s$ and action $a$
• In proportion to TD-error $\delta_t$ and eligibility trace $R_t(s,a)$ $$\delta_t = R_{t+1} + \gamma Q(S_{t+1}, A_{t+1}) - Q(S_t, A_t)$$ $$Q(s,a) \leftarrow Q(s,a) + \alpha \delta_t E_t (s,a)$$

Off-policy learning

Off-policy control with Q-learning

$$Q(S,A) \leftarrow Q(S,A) + \alpha \big( R + \gamma \max_{a'} Q(S', a') - Q(S,A) \big)$$