原始视频: bilibili西湖大学赵世钰<<强化学习>>
网格分为: 可达、禁止、目标单元格，边界
Action space是和state有关的， 不同的state会有不同的Action space， 写作
这种表示方式只能表示确定性（deterministic）的例子，一般不用
使用条件概率来表示状态转移：
当前在s1状态，采取a2动作，下一步在s2状态的概率为1；
当前在s1状态，采取a2动作，下一步在si(i不等于2)状态的概率为0；
在强化学习中，我们使用
reward只依赖于当前状态和采取的动作，不取决于它下一刻处于什么状态
在上面的公式中， r已知、$\gamma$ 已知、P已知，则v可求
注意： 这里的$\pi(a|s)$指的是当前状态为是s，采取动作a的概率
贝尔曼公式解释： 在状态s时，对于一个给定的策略$\pi$，所能获得的state value值为两部分，第一部分是即时奖励，第二部分是未来奖励。
其中，$ \pi ( a | s )$含义为当前状态为s, 采取动作a的概率，
这里求解的步骤略过
≜符号在数学上的含义为“等价于”
注意这里的$v_k$是向量，先假设一个$v_0$向量值，然后可以一直递归的求解$v_2 v_3 v_4$......，当k趋近于无穷大的时候，求得的序列${v_k}$向量就等价于原始的$v_\pi$（证明略）
代码实现见demo-bellman.ipynb
**已知$q_\pi(s, a)$(action value)求解$v_\pi(s)$(state value)公式解释：**在某个状态s处的state value值$v_\pi(s)$等于在该状态对可能采取的动作a的概率乘以在该状态采取动作a后得到的action value之积的和，也就是所有action value的期望值。
已知$v_\pi(s)$(state value)求解$q_\pi(s, a)$(action value)公式解释：
公式第一项：$p(r|s, a)$含义为当前所在状态为s, 且采取的动作为a，获得的reward值为r的概率为$p(r|s, a)$。因此第一项含义为当前在状态s采取动作a后能获得的即时reward的期望值。
公式第二项：
由上图中的公式（3）和公式（4）我们可以看出，如果在状态s处的action只有一个，且概率为1，那么$v_\pi(s)$就等于$q_\pi(s, a)$。
上图中的定理就是为什么在求解贝尔曼公式时可以迭代求解的原因
值迭代算法流程：
定义好进入到每个state的reward值---->初始化v_pi---->根据初始化好的v_0值计算每个state的action value值（公式1），记作q_table---->根据q_table中记录的action value值，选取每个state位置的最大action value值对应的action更新策略（公式2）---->更新v_pi，更新方式为将每个state位置的最大action value值赋值给v_pi（公式3）---->计算每个state的action value值......
公式1：$q_k(s,a) = \sum_r p(r|s,a)r + \gamma \sum_{s'} p(s'|s,a)v_k(s')$
公式2：$\pi_{k+1}(a|s)=\left{\begin{array}{ll}1 & a=a_k^(s) \0 & a \neq a_k^(s)\end{array}\right.$
公式3：
代码实现见： "codes/value-iteration-bellman.ipynb"
代码实现见： "codes/policy-iteration-bellman.ipynb"
蒙特卡洛算法的核心思想：
我们求解policy的关键在于求解每个state处的action value，也就是$q_{{\pi}k}$，而求解$q_{{\pi}k}$的一种方式是根据state value和action value的转换公式（比如policy iteration算法），此种方式被称为model-base方法；而另一种方式就是直接根据定义，也就是在一个state处的$q_{{\pi}k}$，等于从这个state处出发可能产生的所有episode的return的期望，此种方式被称为model-free方法
MC-Exploring-Starts缺点很明显，就是要确保所有的state和所有的action都要被探索到，因为没被探索到的action有可能就是最优的action，而全部被探索往往是无法确保的，要确保的话，就需要从每一个(state, action)对儿出发产生episode，这样就又退化成了MC-Basic
解决上述问题的方案就是使用MC Epsilon-Greedy
greedy在这里的含义为，当对某个state来说，如果最大的action value对应的action为a*，那么当产生episode的时候，选择a*的概率是最大的，但是也有一定比较小的概率选择其他的action，这样就保证了不会遗漏每一个action
所以如果采用MC Epsilon算法时， 一般会先设置一个大的epsilon值进行探索，然后逐渐减小epsilon值直到0，以能获取最优策略
注意，该公式和上面引出里的公式是一样的，随机近似理论
代码实现见： "codes/Robbins-Monro.ipynb"
其实这个公式和SGD是一模一样的，在随机梯度下降时，上面的w为待求解参数，$a_k$为学习率，$g(w_k)$为目标函数的导数
上面这个例子实际上目的是求w*，也就是求X的期望，这种情况就等同于mean estimation算法，所以说mean estimation算法是SGD的一种特殊情况。
由上述化简出的公式也可以看出，和mean estimation算法一模一样
SGD的性质：在距离最优点越远的时候，SGD的前进方向和GD越接近；在距离最优点越近的时候，SGD的前进方向和GD越不接近。因此SGD只会在收敛的时候会产生随机性，而在未收敛时，和GD一样，会有一个正确的前进方向。（证明课件略）
代码实现见： "codes/SGD-MBGD-BGD.ipynb"
这里的$v_{t+?}(s_t)$代表的含义均是对$s_t$处的state value的估计，只不过是在这个episode上时，不同时刻对$s_t$处的state value的估计，比如，在t=3时刻，所在位置为$s_3$，利用公式那么对$s_3$的state value会有一次更新，它的state value值从$v_{3}(s_3)$变为$v_4(s_3)$，其余所有state处的state value均保持不变。
公式(2)的含义为，当使用TD learning算法更新state value时，只会更新当前所在state处的state value，其余所有的state value不会被更新
具体可以看Q-learning代码实现更直观
total reward为什么是趋近于0而不是大于0，因为这是使用了epsilon-greedy的方法，也就是对每个state，还是会有一定的概率选择非最优的action，所以还会引入负的reward
On-policy含义为：在生成一个episode的经验的过程中，改进当前策略
Off-policy含义为：先生成一个episode的经验，然后根据该经验改进当前策略
注意off-policy版本的这里的$\pi_b$和$\pi_T$是两个不同的策略，$\pi_b$用来生成数据（产生episode），$\pi_T$是待优化的目标策略
这里的T代表转置的意思，一般，一个一维的向量默认为列向量
如果是数据是均匀分布，那么这里的目标函数实际上就等同于深度学习里的MSE
而实际上在强化学习中，数据分布是不均匀的（比如网格世界中某些state会被频繁访问，而有些几乎不会被访问），所以目标函数实际上应该是一个带权重的MSE
基本思想就是先初始化两个网络，参数相同，一个用来计算上图中的红色的action value，另一个用来计算上图中蓝色的action value；然后在训练过程中，先固定住红色网络的参数，更新蓝色网络参数，一定轮次后将蓝色网络的参数赋值给红色网络。如此循环往复
从上图可以看出，在强化学习中，即使损失函数一直在下降，也不能代表所估计的策略是好的策略，因为在数据不充足的情况下，神经网络逼近的只是当前数据下的'最优'
