Q-learning:Temporal Difference / Monte Carlo

Q-learning 是RL的核心
Q 代表 Quality 品质

系统维护一个Q值表：

$state$	$action_1$	$action_2$
1	3.3	1.6
2	2.6	7.8
3	2.4	9.5
4	1.3	5.6

当前agent下一步要采取什么动作，完全根据当前状态的Q值来判断：
在状态1的时候，采取动作 $a_1$ 价值更大（ 3.3 > 1.6）。
在状态3的时候，采取动作 $a_2$ 价值更大（9.5 > 2.4）。
里面每个数值叫 $V$ 。比如 $V_{state_1} = max(3.3, 1.6)=3.3$

各种表达公式总结：

获取状态s的V： $V(s)$ 或 $Q(s, A)$ 返回的是所有action的值
第4个状态对应的V： $V(S_4)$ 或 $Q(S_4, A)$ 返回的是所有action对应的值
第4个状态动作1 对应的V： $Q(S_4, A_1)$
t 时刻的状态 / 动作对应的V： $Q(S_t, A_t)$
状态 $s$ 对应动作 $a$ 的V： $Q(s,a), R(s,a)$
状态 $s'$ 对应动作 $a'$ 的V： $Q(s',a')$
状态 $s$ 对应动作 $a$ 的概率： $\pi(a|s)$
状态s里，V最大的动作： $\mathop{argmax}_{a \in A} Q(s, a)$ 或 $\mathop{argmax}_a Q(s, a)$
状态s里，所有动作中，最大的V： $\mathop{max}_{a \in A} Q(s, a)$ 或 $\mathop{max}_a Q(s, a)$

如何计算Q值表，便是Q-Learning要做的事情。
然后agent通过一个策略 $\pi$ ，结合Q表，做出动作选择。
比如这样的策略：90%的情况下选择 $V$ 值大的动作，%10的情况随机选一个。

# select_action
def policy_pi(state):
    if random.random() > 0.9:
        return random_action
    else：
        return argmax(state)

蒙特卡洛MC法：

首先， $V$ 是通过每一个状态获取的奖励 $R$ 算出来的。具体算法后面讲。先用 $v_\pi(s)$ 来表示， $\pi$ 的意思是，这个函数，会在策略 $\pi$ 里面使用。 $\pi$ 会根据当前 state 来产生 action:
$\pi:s\rightarrow a$
$\pi(s)\rightarrow a$

def pi(s):
  #.....
  return a

如果策略不是一个固定的值，而是返回一个概率，状态a下执行动作s的概率:
$\pi(s, a) = \mathbb{P}[a|s]$
$\pi(a|s) = \mathbb{P}[a|s]$

# select_action
def policy_pi(state):
    return (p_act_0, p_act_1)

MC的基础思想就是：让agent不停的去尝试各种可能，获取奖励，算出单次 $V$ 值 $G$ ，最后计算所有 $G$ 的平均值作为总的 $V$ 值。

完整的收集各种状态/动作/奖励，直到此经历结束，比如：

.	ep1	ep2	ep3	ep4	ep5	...
state	a	b	c	d	a	...
action	0	1	1	0	0	...
reward	1	1	1	0	1	...

$\downarrow$

.	ep1	ep2	ep3	ep4	ep5	...
state/action	a,0	b,1	c,1	d,0	a,0	...
reward	1	1	1	0	1	...

$\downarrow$

state/action	reward = R(s,a)
a,0	1
b,1	1
c,1	1
d,0	0
a,0	1

单次迭代的得分 $G$ 计算方法：因为状态/动作是一个连续的序列，后续 $R$ 也会影响到前面的 $V$ ，所以每个状态的 $V$ ，都需要包含后续所有动作的 $R$ 。

state/action	$G$
a,0	$1 + R(b,1) + R(c,1) + R(d,0) + \cdots$
b,1	$1 + R(c,1) + R(d,0) +\cdots$
c,1	$1 + R(d,0) + R(a,0)+ \cdots$
d,0	$0 + R(a,0)+\cdots$
a,0	$1 +\cdots$

后续步骤的奖励，可能并没有那么重要，所以需要做一个递减，加入一个 < 1 的 $\gamma$ 递减：

state/action	$G$
a,0	$1 + \gamma^1 R(b,1) + \gamma^2 R(c,1) + \gamma^3 R(d,0) + \cdots$

经过无数次迭代后，某个状态/动作收集了无数个 $G$ ，取平均值，便是这个状态/动作的 $V$ 值。公式表示如下：

$V(s_t) = G_t =R_{t} + \gamma R_{t+1} + \gamma^2R_{t+2}+... \gamma^{T-t}R_{T}$
这就是 Reward Hypothesis 奖励假说中的“递减奖励累加”
这个 $V(s_t)$ 也会被写作： $R(s, a), \;R(\tau)$ 反正都是一回事。

如何实现？要么：

维护一个G的list，算平均值，要么
用动态平均值函数：
$a = a+ (v - a)/n$ （ a是平均值，v是新加入的值）
求V的公式便出来了： $v_{\pi}(s) \approx average(G_t)$
也就是这样不停的去迭代，直到结果足够好：
$Q(S_t, A_t) \leftarrow Q(S_t, A_t) +(G_t - Q(S_t, A_t) ) / N(S_t)$

时间差分TD法：

初始Q值表，全是0

s	$a_1$	$a_2$
1	0	0
2	0	0
3	0	0
...	...	...

状态 $s$ 经过动作 $a$ 后，变为状态 $s'$ ，再经过动作 $a'$ 后，变为其他状态。
$s\mathop{\rightarrow}^a s' \mathop{\rightarrow}^{a'} \cdots$

$s'$ 的所有动作： $a' = [a_1'， a_2' ， a_3'，\cdots]$
公式：
$Q(s,a) \leftarrow Q(s,a) + \alpha [r + \gamma \mathop{max}_{a'}Q(s',a')-Q(s,a)]$ 或
$Q(s,a) \leftarrow (1-\alpha)Q(s,a) + \alpha [r + \gamma \mathop{max}_{a'}Q(s',a')]$
$\alpha \; \gamma$ 都是常量
$\alpha$ alpha 可以看作是遗忘率，越大，本次奖励越重要（之前同等状态下的奖励情况都忘了）
$\gamma$ gamma 可以看作是后续奖励重要性，越大，基于本次行为的以后可获得奖励越重要（长远考虑）

可以看出，如果状态比较多，action也很多的情况下，Q table是无法适用的。cart pole环境state有4个变量：位置、速度、角度、角速度，两个动作：左、右。

$S_{pos}$	$S_{vel}$	$S_{ang}$	$S_{angv}$	$Va_0$	$Va_1$
1.2	-2.1	0.1	-2.1	3.1	4.5

如果 4个变量离散化，只保留0~10的范围，那么这个表的大小是： $10\times10\times10\times10\times2 = 20000$ ，这个精度很低了，对cart pole来说凑活够用，1维的小车，已经2万个Q值了，那如果是2维、3维连续坐标空间，要求又很精细，参数又很多的话，比如现实中的自动驾驶，动作有左转n度/右转n度/刹车力度/加速力度，太离散化的取值，是无法完成任务的，但是将采样粒度设置的特别小，又是无法完成的任务。这种时候，就要直接对策略进行优化了，而不是通过Q值，这是 policy gradient