一、马尔可夫

1.马尔科夫过程

如果一个状态转移是符合马尔科夫的，那就是说下一个状态只与当前状态有关，与当前状态之前的状态没有关系。马尔科夫性： $P[s_{t+1}|s_t]=P[s_{t+1}|s_1,···s_t]$
也就是说，未来的转移跟过去是独立的，他只取决于现在。马尔可夫性质是所有马尔可夫过程的基础
马尔可夫过程有一个二元组（S,P）表示，其中S表示有限状态集合，P表示状态转移概率。

2.马尔科夫决策过程

马尔可夫决策过程由元组 $(S,A,P,R,\gamma)$ 来描述，其中：
$S$ 为有限的状态集
$A$ 为有限的动作集
$P$ 为状态转移概率
$R$ 为回报函数
$\gamma$ 为折扣因子，用来计算累计回报

强化学习的目的是给定一个马尔可夫决策过程，寻找到最优策略。策略是指状态到动作的映射，即输入一个状态，输出一个对应的动作，策略常用 $\pi$ 来表示：
$\pi(a|s)=p[A_t=a|S_t=s] \tag{1}$ 策略的定义是用条件概率分布给出的。例如：小明处于状 $s_1$ 可以采取的动作集合为 $\{玩，学\}$ ，其中玩的概率为0.8，学习的概率为0.2，所以就有 $\pi(玩|s_1)=0.8, \pi(学|s_1)=0.2$ .

给定一个策略后，可以计算未来 $k$ 步以内的累计回报，定义累计回报如下：
$G_t=R_{t+1}+\gamma R_{t+2}+···=\sum_{k=0}^\infty \gamma ^kR_{t+k+1} \tag{2}$ 由于策略 $\pi$ 是一个概率分布，可能采取动作 $a_1$ ，也可能采取动作 $a_2$ ，所以累计回报 $G_t$ 也是一个随机变量，不能用累计回报来衡量某状态的价值。因此引出状态值函数。

状态值函数：给定策略 $\pi$ ，累计回报服从一个分布，对累计回报求期望，得到状态值函数。 $v_\pi(s)=E_\pi\left[\sum_{k=0}^\infty\gamma^kR_{t+k+1}|S_t=s\right] \tag{3}$
状态-动作值函数： $q_\pi(s,a)=E_\pi\left[\sum_{k=0}^\infty\gamma^kR_{t+k+1}|S_t=s,A_t=a\right] \tag{4}$
状态值函数与状态-行为值函数关系： $v_\pi(s)=\sum_{a\in A}\pi(a|s)q_\pi(s,a)\tag{5}$
计算状态行为值函数： $q_\pi(s,a)=R_s^a+\gamma\sum_{s'}P_{ss'}^av_\pi(s')\tag{6}$

二、Q表格

强化学习的核心就是学习到在某个状态（State）下采取合适的动作（Action），Q_learning就是做了一件这样的事情。
如下就是一个Q表格：

Q表	$a_1$	$a_2$	$a_3$	$a_4$
$s_1$	17	6	7	0
$s_2$	28	0	1	3
$s_3$	16	-3	0	-1
$s_4$	14	23	11	9

上面的表格就是一个Q表，每个状态有4个动作，分别有一个状态-动作值。这个Q表就是用表格的形式表达出了上面的公式（4）状态-动作值函数。当智能体（Agent）处于某个状态时，这个表就告诉agent该选择什么样的动作，这里选择Q值最大的动作。比如，在状态 $s_1$ 时，动作 $a_1$ 的Q值最大，所以选择动作 $a_1$ 。

Q_learning核心就是维护这个Q表，不断地更新这个表，依据这个表来选取动作，所以这个表就是智能体（agent）的“智商”。

Q_learning算法属于off-policy，行动策略和评估策略不一样，行动策略采用 $\epsilon-greedy$ 策略，评估策略采用贪婪算法来更新Q表。伪代码如下：

Initialize $Q(s,a)$ arbitrarily
Repeat (for each episode):
Initialize $s$
Repeat (for each step of episode):
Choose $a$ from $s$ using policy derived from $Q(e.g., \underline{\epsilon-greedy})$
Take action $a$ ,observe $r,s'$
$Q(s,a)\leftarrow Q(s,a)+a\left[r+\gamma \underline{max_{a'}Q(s',a')}-Q(s,a)\right]$
$s\leftarrow s'$
Until $s$ is terminal

伪代码中，第一个下划线行动策略采用的是 $\epsilon-greedy$ 策略；第二个下划线评估策略采用的是贪婪策略；
伪代码中的第七行，我们可以看发现这是利用下一个状态的价值来更新当前状态的价值，这就是一个bootstrap（自举）的概念，在强化学习里面，你可以每走一步更新一下 Q 表格，然后用下一个状态的 Q 值来更新这个状态的 Q 值，这种单步更新的方法叫做时序差分 。

三、Sarsa算法

Sarsa算法的全称是state-action-reward-state'-action'，这正是对应了算法中的5个参数： $s,a,r,s',a'$
Sarsa算法属于on-policy，行动策略和评估策略都是 $\epsilon-greedy$ 策略
该算法先通过 $\epsilon-greedy$ 策略执行动作，然后再根据执行的动作更新值函数。
伪代码如下：

Initialize $Q(s,a)$ arbitrarily
Repeat (for each episode):
Initialize $s$
Choose $a$ from $s$ using policy derived from $Q(e.g., \underline{\epsilon-greedy})$
Repeat (for each step of episode):
Take action $a$ ,observe $r,s'$
Choose $a'$ from $s'$ using policy derived from $Q(e.g., \epsilon-greedy)$
$Q(s,a)\leftarrow Q(s,a)+a\left[r+\gamma Q(s',a')-Q(s,a)\right]$
$s\leftarrow s',a\leftarrow a'$
Until $s$ is terminal

四、Questions

构成马尔可夫决策过程的四元组？
答： $(S,A,P,R)$ ，考虑折扣因子的话就是五元组 $(S,A,P,R,\gamma)$
描述所构成的强化学习的“学习”流程。
答：强化学习要像人类一样去学习了，人类学习的话就是一条路一条路的去尝试一下，先走一条路，我看看结果到底是什么。多试几次，只要能一直走下去的，我们其实可以慢慢的了解哪个状态会更好。我们用价值函数 $V(s)$ 来代表这个状态是好的还是的。然后用这个 $Q$ 函数来判断说在什么状态下做什么动作能够拿到最大奖励，我们用 $Q$ 函数来表示这个状态-动作值。
Q_learning和Sarsa的区别？
答：Sarsa是由Q_learning改进得来的。Q_learning是off-policy的时序差分学习方法，Sarsa是on-policy的时序差分学习方法。更新公式不同。选取动作action不同。
On-policy和 off-policy 的区别？
答：sarsa是on-policy，只用一个策略 $\pi$ ，兼顾探索和利用，所以在悬崖问题上表现得“胆小怕事”。Q_learning是off-policy，他有目标策略和行为策略，这两个分离开来，所以更有利于找到最优的策略。

强化学习笔记2