强化学习

强化学习是机器学习的一个重要分支，包含两种基本元素：状态和动作，旨在学习一种策略，在某种状态下执行某种动作，找到一个状态到动作的映射。

基本要素

强化学习中使用马尔可夫决策过程来描述，机器处于一个环境中，每个状态为机器当前环境的感知，机器只能通过动作来影响环境，当机器执行一个动作后，使得环境按某种概率转移到另一个状态，同时，环境根据潜在的奖赏函数反馈给机器一个奖赏。一般包含四个要素：状态，动作，转移概率及奖赏函数

• 状态（X）：机器对环境的感知，所有可能的状态称为状态空间
• 动作（A）：机器所采取的动作，所有能采取的动作构成动作空间
• 转移概率（P）：当执行某个动作后，当前状态会以某种概率转移到另一个状态
• 奖赏函数（R）：状态转移后，环境会给机器一个奖赏

强化学习的主要任务就是通过在环境中不断尝试，获得反馈信息调整策略，最终生成一个较好的策略$\Pi$，并根据这个策略在环境中运作

• 确定性策略：$\Pi (x)=a$， 即在状态x下执行a动作
• 随机性策略：$P=\Pi (x,a)$， 在状态x下执行a的概率

一个策略的优劣取决于长期执行这个策略后的累积奖赏，也就是用累积的奖赏来评价策略的好坏，最优策略表示在初始状态下一直执行该策略后，最后的累积奖赏值最高。

• T步累积奖赏：$\mathbb{E}\left[\frac{1}{T}{\sum }_{t=1}^T{r}_t\right]$，即执行策略T步的平均奖赏的期望值
• r折扣累积奖赏：$\mathbb{E}\left[{\sum }_{t=0}^{+\infty }{\gamma }^t{r}_{t+1}\right]$, 一直执行到最后，越往后奖赏权重越低

K摇摆赌博机

考虑强化学习最简单的情形：一步操作就可以得到奖赏结果。

要最大化奖赏，就需要知道每个动作带来的期望奖赏值，如果每个动作奖赏都是确定的，那么只要尝试一遍即可。一般的，一个动作的奖赏值来源于一个概率分布，因此需要多次尝试

单步强化学习的实质是K-摇臂赌博机(K-armed bandit)，由于尝试的次数有限，需要有利用有限次数有效探索的策略：

• 仅探索：将机会均分，轮流执行每个动作，最终根据每个动作的平均奖赏作为期望奖赏的近似值
• 仅利用：尝试的机会分给当前平均奖赏值最大的动作

仅探索法可以估算每个动作的期望奖赏，可没能根据当前反馈结果调整尝试策略，仅利用法每次尝试之后都更新策略，符合强化学习的思路，但是容易找不到每次的最优动作

$\epsilon$ -贪心

这基于一个概率对探索和利用进行折中，具体而言，每次尝试时，以$\epsilon$的概率机型探索，以$1-\epsilon$ 的概率进行利用，选择最优的动作。只需记录每个动作当前的平均奖赏值和被选中的次数，便可以增量式更新

Softmax

算法基于当前每个动作的平均奖赏对探索和利用进行折中，Softmax将一组值转换为概率，值越大概率越大，当前平均奖赏值越高的动作被选中的几率也越大

$$P(k)=\frac{e^{\frac{Q(k)}{\tau }}}{{\sum }_{i=1}^K{e}^{\frac{Q(i)}{\tau }}}$$

除了k的选择根据上述式子选取之外，其余都与上述流程相同

有模型学习

若学习任务中四个要素已知，状态空间、动作空间、转移概率和奖赏函数都已知，这样的情形称为“有模型学习”。假设状态空间和动作空间均有限，那么不用尝试就能对某个策略及评估

• 状态值函数（V）：V(x)，从状态X出发，使用$\Pi$策略后带来的累积奖赏
• 状态-动作值函数(Q)：Q(x, a)，状态x出发，执行动作a后再使用$\Pi$策略得到的累积奖赏

按累积奖赏的定义分成：T步累积奖赏与r折累积奖赏

$$\{\begin{array}{l}\begin{array}{rlrl}{V}_T^{\pi }(x)& ={\mathbb{E}}_{\pi }\left[\frac{1}{T}\sum _{t=1}^T{r}_t\mid x_0=x\right],& & T\text{步累积奖赏};\\ V_{\gamma }^{\pi }(x)& ={\mathbb{E}}_{\pi }\left[\sum _{t=0}^{+\infty }{\gamma }^t{r}_{t+1}\mid x_0=x\right],& & \gamma \text{折扣累积奖赏}.\end{array}\end{array}$$ $$\{\begin{array}{l}{Q}_T^{\pi }(x,a)={\mathbb{E}}_{\pi }\left[\frac{1}{T}{\sum }_{t=1}^T{r}_t\mid x_0=x,a_0=a\right];\\ Q_{\gamma }^{\pi }(x,a)={\mathbb{E}}_{\pi }\left[{\sum }_{t=0}^{+\infty }{\gamma }^t{r}_{t+1}\mid x_0=x,a_0=a\right].\end{array}$$

由于MDP具有马尔可夫性，即现在决定未来，将来和过去无关，可以找到值函数的递归关系

$$\begin{array}{rl}{V}_T^{\pi }(x)& ={\mathbb{E}}_{\pi }\left[\frac{1}{T}\sum _{t=1}^T{r}_t\mid x_0=x\right]={\mathbb{E}}_{\pi }\left[\frac{1}{T}{r}_1+\frac{T-1}{T}\frac{1}{T-1}\sum _{t=2}^T{r}_t\mid x_0=x\right]\\ & =\sum _{a\in A}\pi (x,a)\sum _{x^{\prime }\in X}{P}_{x\to x^{\prime }}^a\left(\frac{1}{T}{R}_{x\to x^{\prime }}^a+\frac{T-1}{T}{\mathbb{E}}_{\pi }\left[\frac{1}{T-1}\sum _{t=1}^{T-1}{r}_t\mid x_0=x^{\prime }\right]\right)\\ & =\sum _{a\in A}\pi (x,a)\sum _{x^{\prime }\in X}{P}_{x\to x^{\prime }}^a\left(\frac{1}{T}{R}_{x\to x^{\prime }}^a+\frac{T-1}{T}{V}_{T-1}^{\pi }(x^{\prime })\right)\end{array}$$

其中第二步为全概率公式展开，外部求和，是对所有可能的行为加权求和，权重是行动的概率，内部求和，某个行动后，对所有可能的下一状态加权求和，权重就是转移到该状态的概率

这样就求出了递归关系

类似的，对$\gamma$折扣累积奖赏可以得到：

$$V_{\gamma }^{\pi }(x)=\sum _{a\in A}\pi (x,a)\sum _{x^{\prime }\in X}{P}_{x\to x^{\prime }}^a\left(R_{x\to x^{\prime }}^a+\gamma V_{\gamma }^{\pi }(x^{\prime })\right).$$

当模型已知，策略评估转化成一种动态规划，先求解每个状态的单步累积奖赏，再求解每个状态的两步累积奖赏，移植到逐步求解出每个状态的T步累积奖赏

同样的，对于状态-动作函数，有：

$$\{\begin{array}{l}{Q}_T^{\pi }(x,a)={\sum }_{x^{\prime }\in X}{P}_{x\to x^{\prime }}^a\left(\frac{1}{T}{R}_{x\to x^{\prime }}^a+\frac{T-1}{T}{V}_{T-1}^{\pi }(x^{\prime })\right);\\ Q_{\gamma }^{\pi }(x,a)={\sum }_{x^{\prime }\in X}{P}_{x\to x^{\prime }}^a\left(R_{x\to x^{\prime }}^a+\gamma V_{\gamma }^{\pi }(x^{\prime })\right).\end{array}$$

Refer

西瓜书学习笔记(16)—强化学习 - Heywhale.com