Background

• Combines MC and DP ideas
• Learns from experience like MC
• Bootstraps like DP

MC Prediction

$$V(S_t)\leftarrow V(S_t)+\alpha [G_t-V(S_t)]$$

• Constant $\alpha$ suitable for nonstationary env.
• MC updates at end of episode when $G_t$ known

TD Prediction

$$V(S_t)\leftarrow V(S_t)+\alpha [R_{t+1}+\gamma V(S_{t+1})-V(S_t)]$$

• Uses idea that $V(S_t)=E[G_t|S_t]$ and $G_t=R_{t+1}+\gamma G_{t+1}$
• Updates immediately on transition to $S_{t+1}$ when $R_{t+1}$ is received
• Does not wait till end of episode
• Called one-step TD or $TD(0)$

TD Prediction Algorithm

TD(0) Bootstraps

• TD estimate depends on previously estimated value
• Also note relation between MC and TD targets

$$\begin{array}{rlrl}{v}_{\pi }(s)& =E_{\pi }[G_t|S_t=s]& & (\text{MC target})\\ & =E_{\pi }[R_{t+1}+\gamma G_t|S_t=s]\\ & =E_{\pi }[R_{t+1}+\gamma v_{\pi }(S_{t+1})|S_t=s]& & (\text{TD target})\end{array}$$

• TD combines sampling of MC and bootstrap of DP

TD(0) Backup Diagram

• TD and MC use sample updates
• DP uses expected updates

TD Advantages

• TD bootstraps (like DP, MC doesn’t)
• TD does not requires $p(s^{\prime },r|s,a)$ (DP requires it)
• TD is online and incremental (MC updates after episodes)
• TD applies to continuing tasks (MC oriented to episodic tasks)
• TD learns from every transition (MC ignores exploratory episodes)

TD(0) Convergence

For stationary MDP and fixed policy $\pi$, TD prediction (learning $v_{\pi }$)

• Convergence in mean to $v_{\pi }$ with $\alpha$=constant
• Convergence with prob. 1 with decreasing $\alpha$

In practice, TD methods converge faster than constant-$\alpha$ MC on stochastic tasks

Example 6.2 Random Walk

Homework: Do exercises 6.3 and 6.4 and 6.6.

Batch Update Algorithm

• Finite amount of experience, say, $N$ episodes
• TD increments computed for every time step
• Value function estimate $V$ changed only once by sum of increments
• Repeat, process all experience again, etc.
• With small $\alpha$, TD(0) and MC convergence determinsitically … to different answers!

Example 6.3 Random Walk

• MC averages actual returns and is optimal (minimizes MSE)
• How does TD perform better?
• TD is optimal in a way that is more relevant to predicting returns

Example 6.4

See example on page 127-128.

What answers do TD and MC give?

Optimality

• Batch MC minimizes MSE on training set
• Batch TD(0) performs ML estimation for Markov model

Certainty-Equivalence Estimate

Given observed episodes:

• $\hat{p}(s^{\prime }|s)$=fraction of observed transitions
• ${\hat{v}}_{\pi }(s)=V(s)$=average of reward on those transitions

Batch TD(0) converges to the certainty-equivalent estimate (CEE)

Clues to Convergence

• Batch TD(0) faster than MC becuase of CEE
• Non-batch methods do not achieve CEE or MSE, they move in those directions, respectively
• Nonbatch TD(0) faster than constant-$\alpha$ MC because it is moving toward a better estimate

Exercise & Homework

Start exercise 6.7 (page 128-129) in class and finish as homework.

Background

• Control = Learning optimal policy
• GPI = Prediction (${\pi }_k\to v_k$) + Improvement ($v_k\to {\pi }_{k+1}$)
• Use TD methods for prediction
• Trade exploration and exploitation
• On-policy and off-policy
• State value and action value functions

Episode

• Previously considered $s\to s^{\prime }$ transitions and learned value $v_{\pi }(s)$ of states
• Now consider $(s,a)\to (s^{\prime },a^{\prime })$ transitions and learn value $q_{\pi }(s,a)$ of state-action pairs

SARSA Update

$$\begin{array}{rl}Q(S_t,A_t)\leftarrow & Q(S_t,A_t)\\ & +\alpha [R_{t+1}+\gamma Q(S_{t+1},A_{t+1})-Q(S_t,A_t)]\end{array}$$

• Update performed immediately after every transition from nonterminal state $S_t$
• $Q(S_t,A_t)=0$ if $S_t$ is terminal
• Uses quintuples $(S_t,A_t,R_{t+1},S_{t+1},A_{t+1})$

SARSA Backup Diagram

?

On-Policy SARSA Control

• Estimate $q_{\pi }$ (prediction)
• Use $q_{\pi }$ as behavior policy
• Change $\pi$ toward greediness wrt $q_{\pi }$ (control)

Convergence of SARSA Control

SARSA converges with prob. 1 to ${\pi }_{\ast }$ provided:

• Policy ${\pi }_k$ converges to greedy
• Use $\epsilon$-greedy or $\epsilon$-soft policies with $\epsilon =1/t$
• Assures all state-action pairs have infinite visits

Exercise 6.8

Do exercise 6.8 (page 129).

Example 6.5 Windy Gridworld

• Discuss example and performance curve
• How can MC fail for this problem?
• See code here

Homework

Do Exercises 6.9 and 6.10 (page 130-131).

Q-Learning

Q-learning = Off-policy TD control

$$\begin{array}{rl}Q(S_t,A_t)\leftarrow & Q(S_t,A_t)\\ & +\alpha [R_{t+1}+\gamma \underset{a^{\prime }}{max}Q(S_{t+1},a^{\prime })-Q(S_t,A_t)]\end{array}$$

• Learned $Q$ approximates $q_{\ast }$ independent of behavior policy
• Behavior policy is $\epsilon$-greedy

Convergence

Guaranteed with prob. 1 provide all state-action pairs are visited

Q-Learning Algorithm

Why is this considered off-policy?

Backup Diagrams

Comparison

• Compare the performance of SARSA and Q-learning in examples 6.6 (page 132).

• Why does SARSA have better rewards?

• Why does SARSA choose the safer path?

SARSA Control Algorithms

$$\begin{array}{rlrl}Q& (S_t,A_t)\leftarrow Q(S_t,A_t)+\alpha [R_{t+1}+& & \gamma \mathrm{\Phi }-Q(S_t,A_t)]\\ \mathrm{\Phi }& =Q(S_{t+1},A_{t+1})& & \text{SARSA}\\ \mathrm{\Phi }& =\underset{a^{\prime }}{max}Q(S_{t+1},a^{\prime })& & \text{Q-learning}\\ \mathrm{\Phi }& =\sum _{a^{\prime }}\pi (a^{\prime }|S_{t+1})Q(S_{t+1},a^{\prime })& & \text{Expected SARSA}\end{array}$$

Expected SARSA

$$\begin{array}{rlrl}\mathrm{\Phi }& =Q(S_{t+1},A_{t+1})& & \text{SARSA}\\ \mathrm{\Phi }& =\sum _{a^{\prime }}\pi (a^{\prime }|S_{t+1})Q(S_{t+1},a^{\prime })& & \text{Expected SARSA}\end{array}$$

• E-SARSA moves deterministically in the same direction that SARSA moves in expectation
• E-SARSA has lower variance
• Given same amount of experience, E-SARSA should perform better

Comparison

Discussion

• Can do off-policy E-SARSA
• E-SARSA = Q-learning when target policy is greedy
• E-SARSA generalizes Q-learning

Q-Learning is Max. Biased

Why does Q-learning choose left (wrong choice)?

Maximization Bias

• Max of estimated value used as estimate of max of true value
• Max of estiamted value $>$ max of true value (bias)
• Problem: same data used to determine max action and estimated value
• Solution: Split the data and have two value functions

Double Learning

$$\begin{array}{rl}{Q}_1(S_t,A_t)& \leftarrow Q_1(S_t,A_t)+\alpha [R_{t+1}\\ & +\gamma Q_2(S_{t+1},\arg \underset{a^{\prime }}{max}{Q}_1(S_{t+1},a^{\prime }))\\ & -Q_1(S_t,A_t)]\end{array}$$

Getting the value from $Q_2$ of the greedy decision from $Q_1$ to update $Q_1$ eliminates maximization bias.

Double Learning Algorithm

Homework

• Add a learning curve for E-SARSA to Fig. 6.5 in example 6.7 (page 134-135)
• Do exercise 6.13 on page 136

Tic-Tac-Toe

• Discuss tic-tac-toe in the agent-environment setting
• Discuss state vs. “afterstate”
• Discuss state-action vs. position-move
• Why is afterstate-value more efficient than action-value?