函数、老虎机、强化学习优化问题的辨识与区别

柏舟   新冠5年 01-11

最近看优化理论有很多感触，比如人生的决策就是一个典型的强化学习问题。但是不同人的境遇不同，大部分人没有资源，世界又很复杂，人生决策都是无模型的强化学习问题。你不得不平衡探索和收益才能达到最优，但是这两项往往是矛盾的。

但是有的人家境比较好，有很多信息，问题就可以简化成一个有部分模型的强化学习问题，相当于你有一个启发式函数，可以少走很多弯路。

更有甚者，可以快速试错，亏了钱失败了可以重来，也就是说他可以探索多个路径，并且没有状态转移，这个问题就简化成了一个函数极值的问题。

几种优化问题

整理一下思路，优化问题分为以下几种：

f(x)寻找极大值点

寻找极值点是一种最基本的形式，x在现实中往往是一个动作序列，这个动作空间很大，f(x)是最终的状态值，比如人死时的评价。

假如存在一个计算能力无限的电脑，有f(x)的模型，就可以通过遍历的方式获得最优的序列。但是往往我们既没有强大的计算能力，也没有f(x)的模型，所以，我们需要一种好的采样策略，尽量观测少的动作序列x，得到观测值，然后建立模型逼近f(x)。

多摇臂老虎机问题形式

问题形式：有很多老虎机，每个老虎机的收益是不同且未知，需要某种策略，使最终的收益最大。这个模型的特点是

1. 老虎机互相独立、并且状态不会发生转移，这就比强化学习简单很多了。
2. 需要平衡探索和收益，需要得到老虎机准确的信息的同时少摇次优的老虎机。
3. 不能回退。你不能摇了老虎机反悔。虽然表面上看多摇臂和强化学习问题，都可以转化成一个动作序列，求最终状态f(x)的最大值。但是你只有一次选择x的机会，不能求f(x)第二次。

典型应用：

1. A/B测试，对页面的字体、大小、颜色进行设计。Google蓝就是这么来的，通过每个人发放不同的颜色，选取页面留存最高的。
2. 广告发放：有几种投放广告的途径，比如：电梯、电视、网络，选取最优的方式使营销最大化。这是一种典型的多摇臂老虎机的形式。

强化学习的问题形式

强化学习与老虎机最大的不同是当你做完决策/行动时，状态就发生了改变。可能你接下来可选的动作就完全不同了，过去的经验也没用了。强化学习可以细分为：

1. 有模型进行探索的，有奖励函数形式的。虽然强化学习有自己的一套做法，但是只要有模型进行探索的都可以转化成函数极值问题，甚至是泛函的极值问题，用变分法还可以求解析解。我感觉大部分能做的强化学习都是有模型的。
2. 有模型进行探索的，只有终局条件和终局结果的。这种问题类似于围棋，做了决定后不一定能看出效果，只要结局才能评价所有动作的好坏。
3. 无模型的。我感觉这种问题根本做不了，最次的都是游戏这种虽然不能回退，但是可以重来的问题。

所以同是强化学习的形式，也有有无模型之分，有无奖励函数之分。而人生决策是最难的那种，既没有模型，动作还不一定有明确的反馈。强化学习问题不仅要平衡探索和收益，还要考虑未来，不能因为当下最优而放弃全局最优。

总结

1. 所有优化问题在数学上都可以转化成函数最值问题，变成动作序列或者轨迹函数x(t)，求最终状态高维函数f(x)或泛函f(x)的极值，这是一种全局的自上而下的思路。但是从多摇臂和强化学习的角度看这个问题完全不同，更像是在一个局部进行动态规划。这个区别主要来自于是否有模型进行搜索，如果存在一个模型，那个就可以对全局的f(x)进行拟合，否则，一旦做出决策就无法回退，就必须权衡探索与收益。
2. 状态是否发生转移。如果明确的知道每个老虎机的概率分布就变成了一个贪婪的问题。但是强化学习的状态和动作都在发生变化，如果选取当前最优的动作，到达一个极坏的处境，最终可能总的收益都很低。
3. 奖励是确定值，还是有随机噪声干扰，还是像隐马尔可夫模型那样无法观测到真实状态。或者只有终局的评价，没有动作的评价。

对应的困难：

1. 平衡探索、收益、未来。
2. 动作空间极大，维度爆炸。
3. 奖励难以观测，动作难以评价。
4. 状态难以观测。

目前的方法都对上述的困难进行简化，简化的方面各有不同：

所以就没有什么好的办法，只能具体问题具体分析。后续可能会深入分析强化学习与最优控制的区别。