Bellman方程在派单和调度中的应用
从MP到MRP再到MDP
MP
M = {S, P}
马尔科夫过程。后续的状态只与当前状态有关，与当前状态之前的状态无关。
MRP
M = {S, P, R, γ}
马尔科夫奖励过程。在马尔科夫过程的基础上增加了奖励R和衰减系数γ<0。
定义Gt为在此时刻到过程结束后所得到的收益。衰减系数体现了时间上的不确定性，离此时刻的状态越远，折扣的越多。
定义v(s)为状态s的价值函数。价值函数是Gt的期望，因为状态s是依照不同的概率转移到下一个状态的，所以不同的状态转移概率乘以对应状态的收益，得到的期望，就是我们要的价值函数。
价值函数可以拆解成如下形式：
可以看成一个状态的价值 = 即时回报+下一状态的折扣价值。这里的Rt+1可以当做Rt，符号问题不用纠结，就当做即使回报就好。
如果知道了状态转移概率矩阵Pss'，那么期望就可以进一步拆为
如果状态是有限且各个状态的即使回报、状态转移概率都是已知的，那么该式有解析解
MDP
M = {S, A, P, R, γ}
马尔科夫决策过程。在马尔科夫奖励过程的基础上增加了决策过程，也就是行动集A，且这里的P和R都与具体的行为a对应，而不像马尔科夫奖励过程那样仅对应于某个状态，a∈A。
既然引入了行动，必然会涉及到策略，这里用π表示策略(Policy)。含义是在状态s下，采取各个行动a的概率，记为π(a|s)。
马尔科夫奖励过程(MRP)，在执行策略π时，有如下的状态转移概率和奖励函数
由于行动a的加入，定义行为价值函数，记为qπ(s,a)，表示在执行策略π时，对当前状态s执行某一具体行为a所能得到的收益的期望，也就是在状态s执行a的价值。
我们知道，状态s，采取了行动a，转移到了状态s'，这其中的状态价值可以通过全部的行为价值求和计算得到，而行为价值，也可以通过全部的状态价值求和计算得到，可以写出以下公式
该状态的价值，等于该状态能采取的动作的动作价值之和
该动作的价值，等于该动作带来的即时收益，加上在该动作的作用下，能够转移到的所有的下一个状态的状态价值之和
将公式互相带入，可以得到迭代式
放两个图帮助理解
同样的，类似MRP里讲的，vπ(s)是有解析解的 
Bellman方程
Bellman方程用于求解马尔科夫决策过程（MDP）。 Bellman方程是一个递归方程，可以用动态规划求解，通过求解该方程可以找到最优值函数和最优策略。
其实上面已经将贝尔曼方程解释过了，他就是将优化问题迭代的变成了子问题，通过寻找下一阶段的子问题的最优解来解决这一个子问题的最优解。
最优值函数V*的求解公式如下：
对于每个MDP，总有至少一个策略优于或等于所有其他策略。如上图的公式，V(s) = f(V(s))，MDP一定有一个最优解，这个可以用不动点定理证明。
解方程：展开成矩阵的形式
线性方程求解：
此解法为O(n3)的时间复杂度(为啥我也不知道)，所以一般用一些逐步迭代的算法进行求解，如下：
- 动态规划Dynamic Programming
- 蒙特卡洛评估Monte-Carlo evaluation
- 时序差分学习Temporal-Difference
在派单决策中的MDP
在派单决策中，构建MDP来表示不同时空下的价值，并应用到线上派单中。以司机为智能体，有：
S：时间和空间预先划分为时间片和六边形区域，每一个(时间片-六边形)表示一个状态
A：两种动作：接单和空闲。
P：接单会100%概率转移到状态(完单时间片，终点六边形)，不接单会100%概率转移到状态(下一个时间片，此六边形)。
R：接单会收获订单价值，不接单则收获0。R由系统的优化目标决定，一般来说，目标设为最大GMV，则R可定义为订单金额。
γ：折扣因子表示着未来的状态能够多大程度影响到现在的收益。这里有一个分歧，折扣因子可以理解为对未来的不确定性，而我们的历史数据，无论是回报（订单金额），还是时间（送驾时间），都已经是确定的值了，所以收益并不会随着时间的增加而降低。论文中用的
来表示收益，而实践中，我们将这里的γ定为了1。
Learning
这一步利用离线数据，在线下学习每一个时空分布的状态价值，该价值就表示司机在在此状态下直到过程结束的未来的收益。
用时序差分TD定义了迭代公式：
空闲的：
， 
接单的：
，
这里用了动态规划DP做计算，我们只计算司机在一天内的过程。在实践中，为了最小化跨日期的订单带来的影响，我们将一天的切分时间定在了凌晨4点。
此处的γ△t(ai)和计算Rγ中的γ不同，前者设置为0.95，后者设为1。
时序差分：
动态规划：
Planning
这一步设置线上的目标函数和约束项
找到最大化行动价值的每个司机的行动策略，并在一个司机只能接一单，一单只能被一个司机接的约束下求解。
由此可以将问题建模为二分图，司机和订单节点之间的权重用该行动的行为价值Qπ(i,j)表示。
优势函数简化Planning
在二部图中，司机可以不接订单，什么都不做，这样的司机和订单之间也会有连线，这个二部图是一个完全二部图。为了减少计算的复杂度，采用了优势函数进行简化计算。
- 在实时计算中，由于派单的间隔很短（1s-3s），这个量级比上状态的时间（10min）是非常小的，所以可以认为当司机采取不接单的动作时，状态价值不会改变，所以司机不接单，他的动作价值就等于该司机当前的状态价值：Qπ(i,0) = V(i)
- 对于优势函数
来说，不接单相当于A=0。把二部图的权重转换为优势函数A，可以在二部图中删除权重为0的连线。（优势函数Aπ(s,a)>0说明行为a的价值大于平均值，应当鼓励，反之则应当避免）
一番操作之后，可以将二部图从左边变为右边的形式，注意权重的定义的改变，目标函数和约束项也随之改变
取消率
论文中没有提及取消率，实际上取消率是隐含在Q函数里面的。把下式的Q(s, a)拆开可以看到
这里的P表示订单的取消率。因为在现实情况下，给订单指派司机，有可能会被渠道PK取消和司乘派后取消，所以在行动 a=接单 的情况下，状态s会有两种转移的可能性：订单被取消，还是状态s不变；订单完单，则转移到状态s'，s'是订单完单的时间片和订单的终点六边形所在的状态。所以定义P为订单取消的概率，简称取消率。
正因为取消率P的存在，行动a的即时收益应该为订单价格的期望，所以R=(1-P)*price
取消率用二分类模型做预测，注意的是取消率说的是司乘对的取消率，考虑到订单和司机两方面因素，还要考虑到渠道因素等特征。
isotonic regression
对模型进行校准是因为我们希望模型给出的预测概率能反映真实的取消率。预测取消率用的模型是xgboost，需要进行校准。
isotonic regression又叫保序回归，是一种校准算法，主要思想是通过不断合并、调整违反单调性的局部区间，使得最终得到的区间满足单调性。他的优点是在数据集大的时候效果更好（否则容易过拟合）、不用训练、且调整之后排序不变（AUC不变）。
对于订单挑司机的情况（一个订单n个司机），我们更看重的是各个司机取消率的排序位置。
对于全局最优的情况（n个订单n个司机），由于不同订单可能来自不同渠道，意味着通过不同模型做的预测，我们更希望预测概率即为真实概率，这样不同渠道之间才有可比性。
网上抄的，不一定对
- 这种boosting decision tree算法，在利用对数损失进行优化模型时，需要校准模型。这是因为预测值大多集中于中间区域，很少预测到接近0或接近1，这也就导致了在给预测值分桶的时候落到首末的桶样本数量少，无法准确地估计概率。
将取消率模型通过isotonic拉齐，派单策略才是完整版，函数f是isotonic模型。
