07 Temporal-Difference Methods

• Classic RL algorithms
• Algorithms:
  • TD learning of state values
  • Sarsa: TD learning of action values
  • Q-learning: TD learning of optimal action values
    • on-policy & off-policy
  • Unified point of view

on-policy vs. off-policy

在强化学习中有两个策略，一个是behavior policy，用来生成经验数据的；一个是target policy，这是我们的目标策略，用来不断改进的，希望收敛到最优策略的。如果这两个policy是同一个policy，那么就是on-policy；如果两个可以不同，那就是off-policy。

• on-policy: 自己下棋，自己看棋思考最优策略；
• off-policy: 别人下棋，自己看棋思考最优策略，偶尔交流一下

Outline

1. Motivating example
2. TD learning of state values
3. TD learning of action values
4. TD learning of optimal action values
5. A unified point of view
6. Summary

A unified point of view

All the algorithms intoduced above can be unified in the following way:

$$q_{k+1}(s_t,a_t)=q_k(s_t,a_t)-{\alpha }_k(s_t,a_t)\left[q_k(s_t,a_t)-{\bar{q}}_k\right]$$

Expression of TD target

${\bar{q}}_k$ is the TD target, which can be different for different algorithms:

Algorithm	Expression of ${\bar{q}}_k$
Monte Carlo	$r_{t+1}+\gamma r_{t+2}+{\gamma }^2{r}_{t+2}+\cdots$
n-step Sarsa	$r_{t+1}+\gamma r_{t+2}+\cdots +{\gamma }^n{q}_k(s_{t+n},a_{t+n})$
Sarsa	$r_{t+1}+\gamma q_k(s_{t+1},a_{t+1})$
Expected Sarsa	$r_{t+1}+\gamma {\mathbb{E}}_{\pi }[q_k(s_{t+1},A)]$
Q-learning	$r_{t+1}+\gamma {\max }_a{q}_k(s_{t+1},a)$

Equation to solve

Algorithm	Equation to solve
Monte Carlo	BE: $q_{\pi }(s,a)={\mathbb{E}}_{\pi }\left[R_{t+1}+\gamma R_{t+2}+\cdots \mid S_t=s,A_t=a\right]$
n-step Sarsa	BE: $q_{\pi }(s,a)={\mathbb{E}}_{\pi }\left[R_{t+1}+\gamma R_{t+2}+\cdots +{\gamma }^n{q}_{\pi }(s_{t+n},a_{t+n})\mid S_t=s,A_t=a\right]$
Sarsa	BE: $q_{\pi }(s,a)={\mathbb{E}}_{\pi }\left[R_{t+1}+\gamma q_{\pi }(S_{t+1},A_{t+1})\mid S_t=s,A_t=a\right]$
Expected Sarsa	BE: $q_{\pi }(s,a)={\mathbb{E}}_{\pi }\left[R_{t+1}+\gamma {\mathbb{E}}_{\pi }[q_{\pi }(S_{t+1},A)]\mid S_t=s,A_t=a\right]$
Q-learning	BOE: $q(s,a)=\mathbb{E}\left[R_{t+1}+\gamma {\max }_{a}q(S_{t+1},a)\mid S_t=s,A_t=a\right]$

Need data

Algorithm	Data needed
Monte Carlo	$(s_t,a_t,r_{t+1},s_{t+1},a_{t+1},\cdots )$
n-step Sarsa	$(s_t,a_t,r_{t+1},s_{t+1},a_{t+1},\cdots ,r_{t+n},s_{t+n},a_{t+n})$
Sarsa	$(s_t,a_t,r_{t+1},s_{t+1},a_{t+1})$
Expected Sarsa	$(s_t,a_t,r_{t+1},s_{t+1})$
Q-learning	$(s_t,a_t,r_{t+1},s_{t+1})$

Summary

1. Various TD learning algorithms
2. Expressions. math interpretations, implementations, relationships
3. A unified point of view

Later

tabular representation to function representation ⇒ 08 Value Function Methods