强化学习
基本概念
强化学习中的问题是如何去定义一个reward。
强化学习（Reinforcement Learning, RL）是一种机器学习的类型，它让智能体（Agent）通过与环境的交互来学习行为策略，目标是通过试错过程找到一种可以最大化长期奖励的策略。
agent的状态是有关于环境的
- 状态：假设我们要将机器人从s1走到s9。我们将这称为机器人的状态。
- 动作：所有的状态在一起组成了状态空间。在这里有5个行动a1-a5。分别是上右下左不动。把所有的action 放在一起就得到了action space。不同状态的action空间是不一样的。也就是说A是si的函数$A(s_i)$的函数。
- 状态改变（state transition）状态改变。比如状态s1的动作是a2。可以写为$s_1 \xrightarrow{a_2}s_2$。同样，向上走并不会改变当前的状态。所以他定义了和环境的交互行为。
forbidden area：如果进入中国区域就会相应的减分（有的时候设计为禁止进入）。
状态改变可以这样定义，但是用的比较少。因为状态太多了。
我们一般用的是状态改变率：使用概率去描述状态改变。
比如从s1走到了a2，那么就描述为。在s1执行a2的情况下一定会到s2
$$ p(s_2|s_1,a_2)=1\\ p(s_i|s_1,a_2)=0 $$
他可以描述一些随机例子。
- 策略：告诉代理在当前状态下进行什么动作直观的表示方法是用箭头表示一个策略。
基于这些策略我们在不同的开始点，会得到一些路径
我们可以用更加数学的表示。使用条件概率，我们用$\pi$表示条件概率。
比如$\pi(a_1|s1)=0$。以此类推，可以计算s1走到每个点的概率。
- reward：他是一个标量，在agent采取了一个动作之后会得到这样一个分数。
正数就是鼓励，负数就是惩罚。如果为0的化其实是在鼓励。
在上图的任务中我们这样设计分数。
- 如果代理有进入边界的倾向设置为-1
- 如果走向禁止区域设置为-1
- 如果走到了目标区域设置为+1
- 不然的化agent的reward为0
reward可以理解为一种人机交互的接口。同样我们可以表示为数学的形式。当状态s1选择了动作a1，reward就是-1。（得到-1的概率是1，得到不是-1的概率为0）
$$ p(r=-1|s_1,a_1)=1 \text{and} p(r\neq-1|s_1,a_1)=0 $$
有的时候会有相同的下一个状态，但是此时给的reward是不一样的。比如选择原地不同，和选择向上走。虽然最后结果都是留在原地，但撞墙需要扣分。
trajectory（轨迹）：是状态-动作-reward链：
$$ s_1\xrightarrow{a_2}s_2\xrightarrow{a_3}s_5\xrightarrow{a_3}s_8\xrightarrow{a_2}s_9 $$
一个trajectory的return是这一条state-action-reward轨迹分数的集合。
$$ return=0+0+0+1=1 $$
同样不同的策略有不同的trajectory。
如何在数学上刻画策略的好坏呢？就是用return的分数来决定的。但是机器在蓝色区域之后有可能一直不动。
因此我们引入了discounted return（由discounted rate而来）。在每个数字上加上折扣。
这就是一个等比数列。
$$ \begin{aligned} \text{discounted return}& =0+\gamma0+\gamma^{2}0+\gamma^{3}1+\gamma^{4}1+\gamma^{5}1+\ldots \\ &=\gamma^3(1+\gamma+\gamma^2+\ldots)=\gamma^3\frac{1}{1-\gamma} \end{aligned} $$
我们通过引入discounted return平衡更远和更近外来的reward。
- Episode（经历）
这是强化学习中很重要的概念。episode包含了终止状态这个概念。代理可能会在terminal状态停止。任务通常是有限步的。这样的任务我们称之为Episode tasks。
有些任务是没有terminal state的。这样的任务我们称之为continuing tasks。
我们可以将episodic task转换为continuing task。有俩种方法进行转换。
第一种转换方式就是当成一个特殊的absorbing state。，一旦模型达到absorbing state就不会厉害。reward持续设置为0
- 把target state当做是一种普通的状态，如果策略合适就会一直留在当前的状态。
马尔科夫决策过程
马尔科夫性质：（markov decision process）MDP历史无关的性质。也就是当前的决策，只取决于现在的状态。
贝尔曼公式
定义
如果区分图中哪个策略是好的，不好的。
其中第三个的分数为。其中的0.5是概率。
$$ \begin{align*} \text{return}_3 &= 0.5 \left( -1 + \frac{\gamma}{1 - \gamma} \right) + 0.5 \left( \frac{\gamma}{1 - \gamma} \right), \\ &= -0.5 + \frac{\gamma}{1 - \gamma} \end{align*} $$
我们用$v_i$来表示从$s_i$出发的return
它的轨迹是
$$ v_1=r_1+\gamma r_2+\gamma ^2 r_3+...\\ v_2=r_2+\gamma r_3+\gamma ^2 r_4+... $$
第二种方法为
$$ v_1=r_1+\gamma(r_2+\gamma r_3+...)=r_1+\gamma v_2 $$
这个告诉我们从不同状态出发得到return。依赖于从其他状态出发得到return。这个idea被称为bootstrapping法。对自己进行迭代。
但是这里好像出现了循环依赖问题
$$ \left.\left[\begin{array}{c}v_1\\v_2\\v_3\\v_4\end{array}\right.\right]=\left[\begin{array}{c}r_1\\r_2\\r_3\\r_4\end{array}\right]+\left[\begin{array}{c}\gamma v_2\\\gamma v_3\\\gamma v_4\\\gamma v_1\end{array}\right]=\underbrace{\left[\begin{array}{c}r_1\\r_2\\r_3\\r_4\end{array}\right]}_{\mathbf{r}}+\underbrace{\gamma\left[\begin{array}{ccc}0&1&0&0\\0&0&1&0\\0&0&0&1\\1&0&0&0\end{array}\right]}_{\mathbf{P}}\underbrace{\left[\begin{array}{c}v_1\\v_2\\v_3\\v_4\end{array}\right]}_{\mathbf{v}} $$
我们把它写成矩阵和向量的形式。左边是一个向量。它等于
$$ v=r+\gamma Pv $$
这个就叫做贝尔曼公式。（对于特定的确定性的问题）。
循环矩阵（Circulant Matrix）是一种特殊的矩阵类型，它的每一行（或每一列）都是由前一行（或前一列）通过循环右移或左移得到的。换句话说，矩阵中的元素是按照一定的规则周期性地排列的。
r是reward。其中的p是状态转移矩阵。描述了从一个状态转移到下一个状态的可能性。
求解：上式等于如下公式，这里的I是恒等矩阵。
$$ (I-\gamma P)v=r $$
- 它告诉我们一个状态的值，实际上依赖于其他状态的值。
- 矩阵向量的形式更容易对状态值进行求解。
这样我们可以得到上图中，
$$ \begin{align*} v_1 &= 0 + \gamma v_3, \\ v_2 &= 1 + \gamma v_4, \\ v_3 &= 1 + \gamma v_4, \\ v_4 &= 1 + \gamma v_4. \end{align*} $$
state value的定义
在强化学习中，状态价值（State Value）是指在给定状态下，智能体（Agent）遵循某个策略（Policy）时所期望获得的回报的度量。状态价值函数用于评估每个状态的好坏，帮助智能体判断在某个状态下采取什么行动是最优的。
考虑如下的单步过程。
$$ S_t \xrightarrow{A_t}R_{t+1},S_t+1 $$
我们引入一些符号
- 其中t代表的是时间
- $S_t$是当前时间的状态
- $A_t$是当前状态状态$S_t$下所采取的动作
- $R_t+1$是在$A_t$之后获得的分数
- $S_t+1$是在$A_t$之后所改变的状态
其中SAR都是随机变量。我们可以对他们求期望。其中所有的跳跃都是由概率分布来决定的。
这样单步的过程，可以推广到多步的trajectory
$$ S_t\xrightarrow{A_t}R_{t+1},S_{t+1}\xrightarrow{A_{t+1}}R_{t+2},S_{t+2}\xrightarrow{A_{t+2}}R_{t+3},\ldots $$
我们可以对它求discounted return
$$ G_t=R_{t+1}+\gamma R_{t+2}+\gamma^2R_{t+3}+... $$
因为Rt是随机变量，所以Gt也是随机变量。
所谓的state value就是Gt的期望值。有时候也被叫做expected value或者mean，全称是state value function。
$$ v_\pi(s)=\mathbb E[G_t|S_t=s] $$
它的数学的定义就是对于$G_t$求条件概率。这个条件就是当前的状态。
这里的$v_\pi(s)$是关于s的函数，是一个基于策略$\pi$的函数。对于不同的策略状态值是不同的。它可以写为$v(s,\pi)$
不同的策略会得到不同的轨迹。当state vlaue比较大的时候状态是比较有价值的。
return 和state value的区别是return是针对单个trajectory，而state value是针对于多个的得到的return求平均值。如果从一个状态出发有可能得到多个trajectory。这时候return 和state value就是不一样的，反之这俩这者就是一样的。
下面是state value的求法
公式推导
R是即时奖励 reward
G是汇报Return
v是状态价值函数，state value：agent从一个状态出发得到的平均return
考虑这样一个随机trajectory
$$ S_t\xrightarrow{A_t}R_{t+1},S_{t+1}\xrightarrow{A_{t+1}}R_{t+2},S_{t+2}\xrightarrow{A_{t+2}}R_{t+3},\ldots $$
我们把$G_t$求期望。记住最后一行的结论。
$$ \begin{aligned} G_{t}& =R_{t+1}+\gamma R_{t+2}+\gamma^{2}R_{t+3}+\ldots \\ &=R_{t+1}+\gamma(R_{t+2}+\gamma R_{t+3}+\ldots) \\ &=R_{t+1}+\gamma G_{t+1} \end{aligned} $$
根据状态值的定义
下列第二行公式把$G_t$分为了俩部分，一个是当前状态，一个是未来状态。因为对着俩个求期望可以分割成分别求期望再相加，就得到了第三行的公式。
$$ \begin{aligned} v_{\pi}(s)& =\mathbb{E}[G_t|S_t=s] \\ &=\mathbb{E}[R_{t+1}+\gamma G_{t+1}|S_t=s] \\ &=\mathbb{E}[R_{t+1}|S_t=s]+\gamma\mathbb{E}[G_{t+1}|S_t=s] \end{aligned} $$
首先计算$\mathbb[R_{t+1}|S_t=s]$。也就是在状态为s的情况下执行a的期望是
第二行代表是得到r的概率乘以期望。第二行这一项代表的是。在s情况下执行a动作发生的概率乘以权重。
$$ \begin{aligned} \mathbb{E}[R_{t+1}|S_{t}=s]& \begin{aligned}=\sum_a\pi(a|s)\mathbb{E}[R_{t+1}|S_t=s,A_t=a]\end{aligned} \\ &=\sum_a\pi(a|s)\sum_rp(r|s,a)r \end{aligned} $$
来计算第二项$\mathbb E[G_{t+1}|S_t=s]$
这里假设当前的状态是s，下一个状态是s'（很多个s'）。
第一行代表当前是s，下一个状态是s'，从当前出发得到return的mean，其实这里$s_t=s$是可以去掉的，因为知道了下一个状态是s'：马尔科夫性质，memoryless 也就是没有记忆。最后的一行就是从s出发到s'的概率。因为从s出发有不同的action
$$ \mathbb{E}[G_{t+1} | S_t = s] = \sum_{s'} \mathbb{E}[G_{t+1} | S_t = s, S_{t+1} = s'] p(s' | s) \\ = \sum_{s'} \mathbb{E}[G_{t+1} | S_{t+1} = s'] p(s' | s) \\ = \sum_{s'} v_\pi(s') p(s' | s) \\ = \sum_{s'} v_\pi(s') \sum_a p(s' | s, a) \pi(a | s) $$
最后我们将俩个上式相加进行一个提取就得到了
$$ \begin{aligned}=\sum_a\pi(a|s)\left[\sum_rp(r|s,a)r+\gamma\sum_{s'}p(s'|s,a)v_\pi(s')\right],\quad\forall s\in\mathcal{S}.\end{aligned} $$
以上就是完整的贝尔曼公式
它包含了俩项，左边是s的状态值，右边是s。这个式子包含俩项，第一项是immediate reward，另一个表示future reward
这个式子在状态空间所有的地方都成立。
其中$v_\pi(s),v_\pi(s')$是我们需要计算的状态值，使用bootstrapping进行计算。
贝尔曼公式是依赖于策略的($\pi$)。求解等式的过程被叫做策略评估。评估这个policy是好是坏。
其中上图俩个p函数指的是dynamic model或者叫我environment model。这例有俩种情况，一种是我们知道这个model，另一个是不知道model。
公式使用
这个例子很简单，因为策略是确定的
我们考虑$s_1$的状态值
$$ \begin{aligned} &\begin{aligned}\pi(a=a_3|s_1)=1\text{ and }\pi(a\neq a_3|s_1)=0.\end{aligned} \\ &p(s'=s_3|s_1,a_3)=1\text{ and }p(s'\neq s_3|s_1,a_3)=0. \\ &p(r=0|s_{1},a_{3})=1\text{ and }p(r\neq0|s_{1},a_{3})=0. \end{aligned} $$
- 执行a3的概率是1，不执行的概率是0
- 从s1出发到，执行a3，跳到s3的概率是1，跳不到s3的概率是0
- s1出发得到s3的概率是1，不到s3的概率是0
也就是说公式可以写成这样。
其中的0是因为不管是概率为0，乘以reward为1。还是概率为1乘以reward为0得到的总分都是0.
$$ v_\pi(s_1)=0+\gamma v_\pi(s_3) $$
这是s1的状态价值函数，相同的。我们可以把s1-s4的状态价值函数写出来
$$ \begin{gathered} v_{\pi}(s_{1}) =0+\gamma v_{\pi}(s_{3}), \\ v_{\pi}(s_{2}) =1+\gamma v_\pi(s_4), \\ v_{\pi}(s_{3}) =1+\gamma v_\pi(s_4), \\ v_{\pi}(s_{4}) =1+\gamma v_{\pi}(s_{4}). \end{gathered} $$
对方程组求解之后就得到了
$$ \begin{gathered} v_{\pi}(s_{4}) =\frac1{1-\gamma}, \\ v_{\pi}(s_{3}) =\frac{1}{1-\gamma}, \\ v_{\pi}(s_{2}) =\frac{1}{1-\gamma}, \\ v_{\pi}(s_{1}) =\frac{\gamma}{1-\gamma}. \end{gathered} $$
我们将$\gamma=0.9$带入上式得到
$$ \begin{gathered} v_{\pi}(s_{4}) =\frac{1}{1-0.9}=10, \\ v_{\pi}(s_{3}) =\frac{1}{1-0.9}=10, \\ v_{\pi}(s_{2}) =\frac{1}{1-0.9}=10, \\ v_{\pi}(s_{1}) =\frac{0.9}{1-0.9}=9. \end{gathered} $$
我们发现s1的分数是最低的。我们一般希望向状态最高的方向走。这也是我们改进的方向。
求解贝尔曼公式
我们要求解这个公式
$$ \begin{aligned}v_\pi(s)=\sum_a\pi(a|s)\left[\sum_rp(r|s,a)r+\gamma\sum_{s'}p(s'|s,a)v_\pi(s')\right],\quad\forall s\in\mathcal{S}.\end{aligned} $$
左边有状态值价值函数，右边也有一个状态值。
如果我们把这些所有公式都放在一起我们就得到了一组，我们有一组线性等式，它可以简单的写成一个矩阵向量形式。
矩阵向量形式非常的简洁和重要。
我们可以将等式重写为（因式分解）
$$ v_\pi(s)=r_\pi(s)+\gamma\sum p_\pi(s'|s)v_\pi(s') $$
其中$r_\pi(s)$是状态s在策略$\pi$下时的期望奖励。
我们给s进行标号从s1-sn。其中$p_\pi(s_j|s_i)$表示的是从在策略$\pi$下从$s_i$跳到$s_j$的概率。
$$ v_\pi(s_i)=r_\pi(s_i)+\gamma\sum_{s_j}p_\pi(s_j|s_i)v_\pi(s_j) $$
把这些状态和方程式放在一起，并且重写为矩阵向量形式
$$ v_\pi=r_\pi+\gamma P_\pi v_\pi $$
其中
$$ \begin{aligned}&v_{\pi}=[v_{\pi}(s_{1}),\ldots,v_{\pi}(s_{n})]^{T}\in\mathbb{R}^{n}\\&r_{\pi}=[r_{\pi}(s_{1}),\ldots,r_{\pi}(s_{n})]^{T}\in\mathbb{R}^{n}\\&P_{\pi}\in\mathbb{R}^{n\times n}\text{,where }[P_{\pi}]_{ij}=p_{\pi}(s_{j}|s_{i})\text{,is the state transition matrix}\end{aligned} $$
也就是公式可以被在问题中写为：
$$ \left.\left[\begin{array}{c}v_\pi(s_1)\\v_\pi(s_2)\\v_\pi(s_3)\\v_\pi(s_4)\end{array}\right.\right]=\underbrace{\left[\begin{array}{c}r_\pi(s_1)\\r_\pi(s_2)\\r_\pi(s_3)\\r_\pi(s_4)\end{array}\right]}_{r_\pi}+\gamma\underbrace{\left[\begin{array}{c}p_\pi(s_1|s_1)&p_\pi(s_2|s_1)&p_\pi(s_3|s_1)&p_\pi(s_4|s_1)\\p_\pi(s_1|s_2)&p_\pi(s_2|s_2)&p_\pi(s_3|s_2)&p_\pi(s_4|s_2)\\p_\pi(s_1|s_3)&p_\pi(s_2|s_3)&p_\pi(s_3|s_3)&p_\pi(s_4|s_3)\\p_\pi(s_1|s_4)&p_\pi(s_2|s_4)&p_\pi(s_3|s_4)&p_\pi(s_4|s_4)\end{array}\right]}_{P_\pi}\underbrace{\left[\begin{array}{c}v_\pi(s_1)\\v_\pi(s_2)\\v_\pi(s_3)\\v_\pi(s_4)\end{array}\right]}_{v_\pi}. $$
其中n=4，代表状态数量。
对于例子
上述的公式可以写成.左侧的是一列数字是immediately reward
$$ \left.\left[\begin{array}{c}v_\pi(s_1)\\v_\pi(s_2)\\v_\pi(s_3)\\v_\pi(s_4)\end{array}\right.\right]=\left[\begin{array}{c}0\\1\\1\\1\end{array}\right]+\gamma\left[\begin{array}{cccc}0&0&1&0\\0&0&0&1\\0&0&0&1\\0&0&0&1\end{array}\right]\left[\begin{array}{c}v_\pi(s_1)\\v_\pi(s_2)\\v_\pi(s_3)\\v_\pi(s_4)\end{array}\right] $$
同样下图可以写为
$$ \begin{bmatrix}v_\pi(s_1)\\v_\pi(s_2)\\v_\pi(s_3)\\v_\pi(s_4)\end{bmatrix}=\begin{bmatrix}0.5(0)+0.5(-1)\\1\\1\\1\end{bmatrix}+\gamma\begin{bmatrix}0&0.5&0.5&0\\0&0&0&1\\0&0&0&1\\0&0&0&1\end{bmatrix}\begin{bmatrix}v_\pi(s_1)\\v_\pi(s_2)\\v_\pi(s_3)\\v_\pi(s_4)\end{bmatrix} $$
如何求解
为什么要求解贝尔曼公式？给定一个策略找到对应的状态值。这个过程叫做策略评估（policy evaluation）是RL中的基本原理。
对于公式
$$ v_\pi=r_\pi+\gamma P_\pi v_\pi $$
封闭解是
$$ v_\pi=(I-\gamma P_\pi)^{-1}r_\pi $$
在现实中我们仍然需要使用数学工具去计算矩阵的逆。我们可以避免矩阵的逆运算。
我们可以使用迭代法（iterative solution）
$$ v_{k+1}=r_{\pi}+\gamma P_{\pi}v_{k} $$
使用这个算法我们可以得到一个序列$\{v_0,v_1,v_2,...\}$。我们可以表示为。当k趋向于无穷的时候$v_k$就收敛到了$v_\pi$
$$ v_k\to v_\pi=(I-\gamma P_\pi)^{-1}r_\pi,\quad k\to\infty $$
直观演示，下面俩个策略的分数是一样的，但是箭头不一样
如下的策略就是不好的，所以分数很低
action value
- state value：agent从一个状态出发得到的平均return
- action value：从一个状态出发并且选择了一个action之后得到的平均return
为什么我们要关注这个action value呢？我们需要知道哪个策略更好，我们会频繁的用到action value。
action value的定义为
$$ q_\pi(s,a)=\mathbb{E}[G_t|S_t=s,A_t=a]（1） $$
它表示了从状态s出发，执行action a会得到的return的均值（期望）。
其中$q_\pi(s,a)$是关于状态动作对(s,a)，并且action value是依赖于这个策略$\pi$的。
其中action value和state value的公式如下
$$ \begin{aligned}&\mathbb{E}[G_t|S_t=s]=\sum_a\underbrace{\mathbb{E}[G_t|S_t=s,A_t=a]}_{q_\pi(s,a)}\pi(a|s)\\\end{aligned}（1） $$
因此，state value为选择不同action value得到的一个平均值。
$$ v_\pi(s)=\sum_a\pi(a|s)q_\pi(s,a)（2） $$
会议之前的state value
$$ v_{\pi}(s)=\sum_{a}\pi(a|s)\Big[\underbrace{\sum_{r}p(r|s,a)r+\gamma\sum_{s'}p(s'|s,a)v_{\pi}(s')}_{q_{\pi}(s,a)}\Big]（4） $$
因此我们可以得到action value的表达式
$$ q_\pi(s,a)=\sum_rp(r|s,a)r+\gamma\sum_{s^{\prime}}p(s^{\prime}|s,a)v_\pi(s^{\prime})（4） $$
公式2和公式4是一个硬币的俩面。
- 2告诉我们从action value中得到state value
- 4告诉我们得到从state value中得到action value
我们还是通过这个例子来理解
我们先写出对于s1的action value
$$ q_\pi(s_1,a_2)=-1+\gamma v_\pi(s_2), $$
- 求action value可以通过计算所有的state value我，然后计算action value
- 也可以直接计算action使用或不使用environment。
贝尔曼最优公式
问题
贝尔曼最优公式是贝尔曼公式的一个特例。
强化学习的概念核心就是优化策略。
上图中贝尔曼公式为
$$ \begin{gathered} v_{\pi}(s_{1}) =-1+\gamma v_{\pi}(s_{2}), \\ v_{\pi}(s_{2}) =+1+\gamma v_\pi(s_4), \\ v_{\pi}(s_{3}) =+1+\gamma v_\pi(s_4), \\ v_{\pi}(s_{4}) =+1+\gamma v_\pi(s_4). \end{gathered} $$
我们让$\gamma =0.9$。那么我们可以计算得出
$$ v_\pi(s_4)=v_\pi(s_3)=v_\pi(s_2)=10,\quad v_\pi(s_1)=8 $$
有了state value就可以求解action vlaue
$$ \begin{gathered} q_\pi(s_1,a_1) =-1+\gamma v_{\pi}(s_{1})=6.2, \\ q_\pi(s_1,a_2) =-1+\gamma v_\pi(s_2)=8, \\ q_\pi(s_1,a_3) =0+\gamma v_{\pi}(s_{3})=9, \\ q_\pi(s_1,a_4) =-1+\gamma v_\pi(s_1)=6.2, \\ q_\pi(s_1,a_5) =0+\gamma v_\pi(s_1)=7.2. \end{gathered} $$
其中a3的action value是最大的
很明显当前的策略不太好，如何改进它呢？答案是使用action value。我们一般用$a^*$来表示最优策略来表示最优策略。
也就是说
$$ a^* =arg max_aq_\pi(s_1,a)=a_3 $$
在本例中除了s1的策略其他格子的策略都是最优的。但有的时候其他格子的策略并不一定是最优的。但是我们可以迭代n次后，最终得到最优策略。
如果对于所有的状态s $\pi_1$得到的state value都大于$\pi_2$得到的state value。那么就是说$\pi_1$比$\pi_2$要好
$$ v_{\pi_1}(s)\geq v_{\pi_2}(s)\quad\text{for all }s\in\mathcal{S} $$
因此可以下定义：如果$v_{\pi^*}(s)\geq v_\pi(s)$对于任意的状态相比任意的策略$\pi$得到的状态是最优的，那么策略$\pi^*$是最优的
我们对贝尔曼公式前面加上一个max$\pi$
$$ \begin{aligned}v_\pi(s)=\max_\pi\sum_a\pi(a|s)\left[\sum_rp(r|s,a)r+\gamma\sum_{s'}p(s'|s,a)v_\pi(s')\right],\quad\forall s\in\mathcal{S}.\end{aligned} $$
我们可以把其他简写为
$$ =\max_\pi\sum_a\pi(a|s)q(s,a)\quad s\in\mathcal{S} $$
- 其中$p(r|s,a),p(s'|s,a)$是已知的
- $v(s),v(s')$是已知的可计算的
- 其中$\pi(s)$在贝尔曼公式中是已知的，在贝尔曼最优公式就是未知的。
我们再把上市式变为矩阵向量形式
$$ v=\max_\pi(r_\pi+\gamma P_\pi v) $$
而这个公式就是贝尔曼最优公式。它形式非常简洁并且能刻画最优的策略， 以及最优的state value。
在这个公式中我们要求解$\pi$和v。我们在这里考虑$\sum_a \pi(a|s)=1$我们有了。
$$ =\max_\pi\sum_a\pi(a|s)q(s,a)=\max _{a\in\mathcal A(s)}q(s,a) $$
所以 如下方式能达到最优
$$ \left.\pi(a|s)=\left\{\begin{array}{ll}1&a=a^*\\0&a\neq a^*\end{array}\right.\right. $$
其中
$$ a^* =arg max_aq_i(s,a) $$
我们将
$$ f(v):=\max_\pi(r_\pi+\gamma P_\pi v) $$
其中贝尔曼最优公式会变为
$$ v=f(v) $$
这里的f(v)其实是一个向量 其中
$$ [f(v)]_s=\max_\pi\sum_a\pi(a|s)q(s,a),\quad s\in\mathcal{S} $$
那么如何求解这个等式呢。
contraction mapping理论
不动点(fixed point)
如果$f(x)=x$那么这个x就是不动点。
contraction mapping
也叫contractive function 如果一个函数满足
$$ \|f(x_1)-f(x_2)\|\leq\gamma\|x_1-x_2\| $$
就叫做收缩函数。直观来说就是俩者映射之后的距离比原来的距离要小。比如f(x)=0.5x就是
contraction mapping theorem定理：如果f是一个contraction mapping，那么：
- 存在一个fixed point$x^*$，满足$f(x^*)=x^*$
- 并且这个fixed point是唯一的
- 求解fixed point：考虑一个序列$\{x_k\}$其中$x_{k+1}=f(x_k)$，那么当k趋向于无穷的时候$x_k \to x^*$ 。收敛率从呈指数增长。
例子：$x_0=10,x_1=5,x_2=2.5$，当k无穷的时候就能收敛到0。同理
同样对于Ax，x如果是一个向量A是一个矩阵，这个理论可以相同的被推广到高维。
求解公式
为了讲contraction mapping应用，我们需要证明 f(v)是contraction mapping
$$ v=f(v)=\max_\pi(r_\pi+\gamma P_\pi v) $$
其中我们可以证明
$$ \|f(v_1)-f(v_2)\|\leq\gamma\|v_1-v_2\| $$
其中$\gamma$是discount rate。
因此我们可以知道贝尔曼公式中的f(v)是存在最优解$v^*$并且这个解是唯一存在的。
我们可以进行迭代求解：
$$ v_{k+1}=f(v_k)=\max_\pi(r_\pi+\gamma P_\pi v_k) $$
并且$v_k$会收敛到$v^*$
假设$v^*$是最优的状态值，而$\pi^*$是最优的状态值策略。那么我们就得到了公式(去掉了前面的max $\pi$)
$$ v^*=r_{\pi^*}+\gamma P_{\pi^*}v^* $$
它就是对应$\pi^*$的贝尔曼公式（贝尔曼公式对应的是一个策略）。因此贝尔曼最优公式是特殊的贝尔曼公式。
因此$v^*$可以获得最大的state value。其中$\pi ^*$可以表示为
$$ \pi^*(a|s)=\left\{\begin{array}{ll}1&a=a^*(s)\\0&a\neq a^*(s)\end{array}\right. $$
它可以求解贝尔曼最优方程
$$ a^*(s)=\arg\max_aq^*(a,s),\\其中 q^*(s,a):=\sum_rp(r|s,a)r+\gamma\sum_{s'}p(s'|s,a)v^*(s'). $$
贝尔曼最优公式的性质
其中红色的内容都是已知的。我们要求解的是黑色的内容
我们使用贝尔曼公式对之前的图建模,我们得到了。
我们发现它穿过了一个forbidden areas。为什么会出现这种情况呢？因为虽然这暂时带来了一个负数的惩罚，但是长远来看，比我绕一大圈得到的return要大。
我们去改变一些参数。比如我们把$\gamma$改为0.5就得到了
当$\gamma$较大的时候agent会比较远视，小的时候就近视。
如果把$\gamma$设置为0，那么就会变得极度近视.。它只会关注当前分数。
如果我们把禁止区域设置为-10的reward。$\gamma$还是0.9。
那么策略就变成了
假设我们加上一个偏置b
然后其他的我们修改
$$ r_{\mathrm{boundary}}=r_{\mathrm{forbidden}}=0,\quad r_{\mathrm{target}}=2,\quad r_{\mathrm{otherstep}}=1 $$
这个otherstep就是从白色的格子移动到白色的格子。
经过修改之后我们发现最优策略不会改变。因为最重要的不是reward的绝对位置而是相对位置。
在设计reward的时候不需要进行惩罚。因为$\gamma $衰减的存在自然能够保证它走最短路径。
优化策略不变性
我们对每一个reward加上一个b。
$$ v'=av^*+\frac{b}{1-\gamma}\mathbf{1}, $$
贝尔曼公式中的优化策略不变性（Policy Invariance）是指在马尔可夫决策过程（MDP）中，最优值函数和最优策略之间的关系是稳定的，换句话说，在找到一个最优策略后，该策略下的值函数和在相同状态下执行其他策略的值函数之间有一定的等价性。
值迭代与策略最优
值迭代算法
$P_\pi$在策略$\pi$表示转移到下一个状态的概率
步骤1：策略更新，这一步去解决。其中的策略更新这一部使用的是贪心策略。
$$ \pi_{k+1}=\arg\max_\pi(r_\pi+\gamma P_\pi v_k) $$
求解出$\pi_k+1$然后步骤2：进行值更新
$$ v_{k+1}=r_{\pi_{k+1}}+\gamma P_{\pi_{k+1}}v_k $$
公式中把 $v_k$当做一个普通的值来进行处理。
$$ v_{k+1}(s)=\max_a q_k(a,s) $$
整个策略为计算状态值，计算action 更新策略更新$\pi$。然后用新的状态值周而复始
$$ v_k(s)\to q_k(s,a)\to\text{greedy policy}\pi_{k+1}(a|s)\to\text{new value}v_{k+1}=\max_aq_k(s,a) $$
用代码写就是
遍历所有的状态 $s\in\mathcal{S}$,do
遍历所有的动作$a\in\mathcal{A}(s)$,do
$\mathbf{q- value: }$ $q_{k}( s, a) = \sum _{r}p( r| s, a) r+ \gamma \sum _{s^{\prime }}p( s^{\prime }| s, a) v_{k}( s^{\prime })$ 计算状态第k个action value
Maximum action value: $a_k^*(s)=\operatorname{arg}\operatorname*{max}_aq_k(a,s)$ 看哪个action对应的是最大的$q_k$
Policy update: $\pi_k+1(a|s)=1$ if $a=a_k^*$, and $\pi_k+1(a|s)=0$ otherwise
Value update: $v_{k+1}(s)=\max_aq_k(a,s)$
我们可以基于这个表格来进行一次值的迭代
这里的$v_0$是可以任意选取的，这里为了简单先选0。
这一步我们算出了v1的值那么我们可以根据v1再进行一次迭代。
当$||v_k-v_{k+1}||$小于定义的阈值，或者没有更新action的时候。
策略迭代算法
策略迭代算法有俩步，最开始有一个初始策略叫做$\pi_0$。可以是任意的策略。
步骤1：策略评估（policy evaluation PE），这一部是要计算$\pi_k$的状态值。也就是评估这个策略。
$$ v_{\pi_k}=r_{\pi_k}+\gamma P_{\pi_k}v_{\pi_k} $$
这里的$v_{\pi_k}$是state value函数
步骤2：策略增强（policy improvement PI）
$$ \pi_{k+1}=\arg\max_\pi(r_\pi+\gamma P_\pi v_{\pi_k}) $$
这样我们得到了新的策略$\pi_{k+1}$,它比$\pi_k$更好。
写出来就是
$$ \pi_0\xrightarrow{PE}v_{\pi_0}\xrightarrow{PI}\pi_1\xrightarrow{PE}v_{\pi_1}\xrightarrow{PI}\pi_2\xrightarrow{PE}v_{\pi_2}\xrightarrow{PI}\ldots $$
我们可以用俩中方法来进行求解（上问提到过）
一个是closed-form solution
$$ v_{\pi_k}=(I-\gamma P_{\pi_k})^{-1}r_{\pi_k} $$
另一个是迭代法。这里可以看成一个大的迭代算法里面有小的迭代算法。一般用的都是这个值迭代算法。
$$ v_{\pi_k}^{(j+1)}=r_{\pi_k}+\gamma P_{\pi_k}v_{\pi_k}^{(j)},\quad j=0,1,2,... $$
那么值迭代算法和策略迭代算法有什么关系呢。我们证明策略迭代算法收敛的时候使用到了值迭代算法收敛的特性。实际上他们是俩个极端。
矩阵形式
$$ v_{\pi_k}^{(j+1)}=r_{\pi_k}+\gamma P_{\pi_k}v_{\pi_k}^{(j)} $$
其中的j是第j个估计出来的迭代
逐元素形式
$$ v_{\pi_k}^{(j+1)}(s)=\sum_a\pi_k(a|s)\left(\sum_rp(r|s,a)r+\gamma\sum_{s'}p(s'|s,a)v_{\pi_k}^{(j)}(s')\right),\quad s\in\mathcal{S}, $$
括号中的就是$q_{\pi_k}(s,a)$
其中
$$ a_k^*(s)=\arg\max_aq_{\pi_k}(a,s) $$
她选取最优策略的方法是
$$ \left.\pi_{k+1}(a|s)=\left\{\begin{array}{ll}1&a=a_k^*(s),\\0&a\neq a_k^*(s).\end{array}\right.\right. $$
我们要求解$v_{\pi_k}$然后我们给初始的猜测参数。然后将猜测带到迭代算法中最后就能得到$v_{\pi_k}$。然后遍历所有状态求出$q_{\pi_k}$
假设初始的策略如下图，希望优化到右图。
我们先利用贝尔曼公式求解$v_{\pi_0}$
然后是求解$q_{\pi_k}$
截断策略迭代算法
truncated policy iteration是值迭代算法和策略迭代算法的推广（特殊情况）。
对于策略迭代算法：是从$\pi_0$开始的
Policy evaluation (PE)
$$ v_{\pi_k}=r_{\pi_k}+\gamma P_{\pi_k}v_{\pi_k} $$
Policy improvement (PI):
$$ \pi_{k+1}=\arg\max_\pi(r_\pi+\gamma P_\pi v_{\pi_k}) $$
对于值迭代算法是从$v_0$开始的,而不是从策略开始的。最后收敛到$v^*$
Policy update (PU):
$$ \pi_{k+1}=\arg\max_\pi(r_\pi+\gamma P_\pi v_k) $$
Value update (VU):
$$ v_{k+1}=r_{\pi_{k+1}}+\gamma P_{\pi_{k+1}}v_k $$
一个是随机state value一个是随机一个策略$\pi$
俩个算法是非常类似的
$$ \text{Policy iteration:}\pi_0\xrightarrow{PE}v_{\pi_0}\xrightarrow{PI}\pi_1\xrightarrow{PE}v_{\pi_1}\xrightarrow{PI}\pi_2\xrightarrow{PE}v_{\pi_2}\xrightarrow{PI}\ldots\\\text{Value iteration:}u_0\xrightarrow{PU}\pi_1^{\prime}\xrightarrow{VU}u_1\xrightarrow{PU}\pi_2^{\prime}\xrightarrow{VU}u_2\xrightarrow{PU}\ldots $$
我们可以从表格中看到
关键的是蓝色的字体的不同之处。关键区别在左侧在此时往前迭代了策略，右边迭代了
策略迭代算法在实际上是不可能存在的，因为它要计算无穷多步。
我们要求解
$$ v_{\pi_1}=r_{\pi_1}+\gamma P_{\pi_1}v_{\pi_1} $$
我们要进行k词次迭代。第0次从任意的初始值出发。
$$ \begin{aligned}&v_{\pi_1}^{(0)}=v_0\\&v_{\pi_1}^{(1)}=r_{\pi_1}+\gamma P_{\pi_1} v_{\pi_1}^{(0)}\\&v_{\pi_1}^{(2)}=r_{\pi_1}+\gamma P_{\pi_1} v_{\pi_1}^{(1)}\\&v_{\pi_1}^{(j)}=r_{\pi_1}+\gamma P_{\pi_1} v_{\pi_1}^{(j-1)}\\&\vdots\\&v_{\pi_1}^{(\infty)}=r_{\pi_1}+\gamma P_{\pi_1} v_{\pi_1}^{(\infty)}\end{aligned} $$
迭代到无穷。其实第二行就是值迭代算法得到的值，它会把$v_1$立刻用到下一步的策略更新中。我们可以只计算j词然后作为新的值进行计算策略。这样的算法就叫做截断迭代算法。但是因为进行了截断$v_k$不等于$v_{\pi_k}$
来比较不同的算法的收敛速度
蒙特卡洛方法
基于蒙特卡洛的强化学习算法basic
这是model-free（无模型）的RL算法。
最简单的凡不基于模型的方法是蒙特卡洛估计（Monte Carlo estimation ）
一个硬币正面向上是1反之是0。求他的期望是什么呢？
$$ \mathbb{E}[X]=\sum_xxp(x)=1\times0.5+(-1)\times0.5=0 $$
但是我们可能无法知道精确的分布。那能不能在没有模型的情况下也去估计呢？
我们可以抛硬币许多次，然后求输出的均值。随着任务数量次数的增多它的结果会越来越精确。这个理论符合大数定律。
为什么我们关心估计的均值呢？因为state value和action value的定义就是随机变量的均值。
无模型的核心就是如何把策略迭代算法变成model-free的
策略迭代：
策略估计$v_{\pi_k}=r_{\pi_k}+\gamma P_{\pi_k}v_{\pi_k}$。
策略增强$\pi_{k+1}=\arg\max_\pi(r_\pi+\gamma P_\pi v_{\pi_k})$
需要模型的
$$ q_{\pi_k}(s,a)=\sum_rp(r|s,a)r+\gamma\sum_{s'}p(s'|s,a)v_{\pi_k}(s') $$
不需要模型的
$$ q_{\pi_k}(s,a)=\mathbb{E}[G_t|S_t=s,A_t=a] $$
这是一个均值估计的过程。
- 从任意一个(s,a)出发使用策略$\pi_k$生成episode
- 计算eposode的discounted return g(s,a)
- g(s,a)是$q_{\pi_k}(s,a)=\mathbb{E}[G_t|S_t=s,A_t=a]$里 $G_t$的样本
如果我们有很多这样的采样，我们就可以用$\{g^{(j)}(s,a)\}$求一个均值，来估计$G_t$的平均值。
$$ q_{\pi_k}(s,a)=\mathbb{E}[G_t|S_t=s,A_t=a]\approx\frac{1}{N}\sum_{i=1}^{N}g^{(i)}(s,a). $$
当模型是未知的，我们可以使用数据。这个数据在统计中叫做采样，在强化学习中叫做经验。
蒙特卡洛基础算法：
首先初始化一个策略$\pi_0$，在第k次叠代中包含俩个步骤
- 策略评估：这一步对所有的(s,a)获得$q_{\pi_k}(s,a)$。对于每一个action-state对(s,a)，运行无限次数的（或者足够多的）episode。return的平均值被用来近似$q_{\pi_k}(s,a)$。
- 策略增强：第二步和策略迭代是一模一样。
mc basic 是策略迭代的变种，把基于模块的那部给拿掉，换成不需要的。
mc basic非常清晰的解释了如何将基于模型的变成model-free的，但它不是非常实用因为它的效率较低。
因为策略迭代是收敛的，所以MC basic算法也是收敛的。
例子：
假设有这样的策略$\pi_0$
- 步骤1：策略评估计算$q_{\pi_k}(s,a)$。
有多少个state-action对？一共有9x5=45个state-action对。 - 步骤2：策略增强，求出哪个action是最大的，然后选择那个。
由于空间限制我们只找s1的五个action
因为当前的环境是确定的，那么就只需要采样一次就可以了。如果不确定的话就采样多次求平均。
我们采样的时候如何确定episode的长度呢？()
随着episode越长目标会越来越接近。
MC Exploring start
visit（访问）：每个时间都有状态动作对发生在episode对立，它被叫做状态动作对的visit
$$ s_1\xrightarrow{a_2}s_2\xrightarrow{a_4}s_1\xrightarrow{a_2}s_2\xrightarrow{a_3}s_5\xrightarrow{a_1}\ldots $$
在mc basic中我们用的策略叫做initial-visit：也就是说对于整个episode只考虑$(s1,a2)$，然后用剩下的return来估计s1，a3的action value。也就是$q_\pi(s1,a2)$。它的问题是没有充分的利用episode。
后一个的估计是基于前一个
$s_1\xrightarrow{a_2}s_2\xrightarrow{a_4}s_1\xrightarrow{a_2}s_2\xrightarrow{a_3}s_5\xrightarrow{a_1}\ldots$ [original episode]
$s_2\xrightarrow{a_4}s_1\xrightarrow{a_2}s_2\xrightarrow{a_3}s_5\xrightarrow{a_1}\ldots$ [episode starting from $(s_2,a_4)]$
$s_1\xrightarrow{a_2}s_2\xrightarrow{a_3}s_5\xrightarrow{a_1}\ldots$ [episode starting from $(s_1,a_2)]$
$s_2\xrightarrow{a_3}s_5\xrightarrow{a_1}\ldots$ [episode starting from $(s_2,a_3)]$
$$s_5\xrightarrow{a_1}\ldots $$
. [episode starting from $(s_5,a_1)]$
Can estimate $q_\pi(s_1,a_2),q_\pi(s_2,a_4),q_\pi(s_2,a_3),q_\pi(s_5,a_1),...$
First-vist
- 在一次模拟中，当一个状态第一次被访问时，记录它的回报（从该状态之后获得的累积回报）。
- 只有第一次访问该状态时，才使用这次的回报来更新状态值函数。
- 适合于分析每个状态的“首次访问”时的回报如何，确保每个状态的值是基于它第一次被访问后的表现。
Every-visit
- 每次访问某个状态时，都会记录该状态的回报，并用于更新该状态的值函数。
- 即使同一个状态在一次模拟中被访问多次，每次访问都会产生一个更新。
- 这种方法更多地利用了模拟中所有的状态信息，但它的计算复杂度也稍微高一些。
除了让数据的利用更加高效，我们还可以更加高效的更新策略
其中一种是，把所有从state-action出发的episode都收集到，之后做average return来估计这个action value。但是他要等所有的episode被收集才可以。
另外一个是得到一个episode就进行立刻估计，然后改进策略。很明显这个策略更为合理一点
这些方法有个名词叫做GPI（generalized policy itration）它不是具体的算法，是一大类算法的架构和思想。
它在策略评估和策略增强之间不断进行切换。
使用这个思想我们就得到了MC exploring starts。它是mc basic的推广。
为什么要考虑exploring starts？
exploring 是从每一个s，a出发都要有episode这样我才能用后面的return来进行估计。但是我们希望每一个s，a都可以被访问到。因为这样就可以防止丢掉重要的一个state。
start指的是，我们有俩种方法。第一种是从一个s，a开始（start）。第二种方法是从其他的s，a开始（visit）。但是这个visit是无法确保的：我们无法保证从其他的s，a开始，一定能经过所有剩下的s，a。所以我们要确保每一个s，a开始都有属于自己的episode。
但是在实际上exploring start是非常难实现的。我们可以用一种软策略实现。
Epsilon greedy
我们需要引入soft policies。之前的greedypolicy就是deterministic的策略。还有一种策略是stochastic的，soft policy就是随机的。
在soft policy中，因为少量的episode已经足够长可以visit全部的state-action足够多次。因此我们不需要从每个state-action对开始的大量的episode。
那么我们使用什么的softpolicies呢？答案是$\epsilon$greedy policies$\epsilon$greedy policies
$$ \pi(a|s) = \begin{cases} 1 - \frac{\epsilon}{|A(s)|} (|A(s)| - 1), & \text{for the greedy action,} \\ \frac{\epsilon}{|A(s)|}, & \text{for the other } |A(s)| - 1 \text{ actions.} \end{cases} $$
这里的$\epsilon$是一个正数。|A(s)|就是s所对应的action的个数。比如网格世界中，每一个状态可能性就是5，上面的$\epsilon$是超参数假设为0.2。那么有0.84的可能性选择贪心的动作，但是也有小可能性选择其他策略。上面有一个性质是选择greedy action的概率比其他的选择的概率都来的大。证明如下
$$ 1 - \frac{\epsilon}{|A(s)|} (|A(s)| - 1) = 1 - \epsilon + \frac{\epsilon}{|A(s)|} \geq \frac{\epsilon}{|A(s)|}. $$
那为什么要使用$\epsilon$，因为它是一个exploitation和exploration之间的平衡。（利用和探测）。
当$\epsilon$趋近于0，那么他就会变成greedy，探索就弱了，充分利用就会强一些。
如果$\epsilon$趋向于1，那么就会趋近于一个均匀分布，更多的exploitation更少的利用。
$$ \pi_{k+1}(s) = \arg \max_{\pi \in \Pi} \sum_a \pi(a|s) q_{\pi_k}(s, a). $$
其中的$\Pi$代表着，所有可能的策略集合。求解出来最优的策略就是贪心策略。
$$ \pi_{k+1}(a|s)=\left\{\begin{array}{ll}1,&a=a_k^*,\\0,&a\neq a_k^*,\end{array}\right. $$
现在我们要把epsilon greedy算法嵌入
$$ \pi_{k+1}(s) = \arg \max_{\pi \in \Pi_\epsilon} \sum_a \pi(a|s) q_{\pi_k}(s, a). $$
其中$\Pi _\epsilon$策略代表哦了给定$\epsilon$下所有的$\epsilon$-greedy策略。
$$ \left.\pi_{k+1}(a|s)=\left\{\begin{array}{ll}1-\frac{|\mathcal{A}(s)|-1}{|\mathcal{A}(s)|}\varepsilon,&a=a_k^*,\\\frac{1}{|\mathcal{A}(s)|}\varepsilon,&a\neq a_k^*.\end{array}\right.\right. $$
MC $\epsilon$-greedy和MC exploring starts除了使用了$\epsilon$完全是一样的。因为使用了这个策略我们就不需要包含exploring start了。
探索性较强$\epsilon$-greedy的探索性很强，但最优性被牺牲掉了。实际当中我们可以通过调整$\epsilon$算法来进行。
虽然所有的策略都和贪心策略保持一致。但是他们的最优变得越来越差。一个常用的技巧$\epsilon$一开始可以稍微大一些，在之后慢慢的减小。