一个马尔科夫链实例 - 好文

马尔科夫早就了解过，但一直没有真正用马尔科夫的思想求解问题，更没有用到论文中去。

最近发现了一本好书：《Foundations of stochastic inventory theory》，斯坦福大学出版的。这本书不厚，才
200多页，讲的比较清晰，目测比其他库存管理的教材要好，准备精度完这本书。

下面探讨书中的一个马尔科夫实例。

1. 状态（state）

一个零售商面对的顾客有两种状态，
状态 s1：上一个月买过该零售商的商品
状态 s2：上一个月没有买过该零售商的商品

2. 决策 (action)

零售商可以做出 3 个决策及对应的决策成本：
决策 a1 ：什么都不做成本：0
决策 a2 ：发礼物，小促销成本：0.5
决策 a3：发礼物，大促销成本：0.5

3. 状态转移及转移概率 (transition equation and possibility)

Initial state ss Action aa Next state1 and possibility pas1ps1a Next state2
and possibilitypas2ps2a
s1 a1 s1, 0.99 s2, 0.01
s1 a2 s1, 0.93 s2, 0.07
s1 a3 s1, 0.85 s2, 0.15
s2 a1 s1, 0.80 s2, 0.20
s2 a2 s1, 0.72 s2, 0.28
s2 a3 s1, 0.50 s2, 0.50
4. 折现率 (discount factor)

折现率 α=0.99α=0.99
有效转移概率 qasj=α∗pasjqsja=α∗psja

5. 即时收益（immediate value）

若顾客不购买商品，收益为 0；
不促销时，顾客购买商品，收益为 8；
小促销时，顾客购买商品，收益为 7；
大促销时，顾客购买商品，收益为 3；

减去成本，得到的期望即时回报（immediate return）r(s,a)r(s,a) 为：

Initial state ss Action aa Action cost c(a)c(a) Expected immediate return
s1 a1 0 0.99*(0.99*0+0.01*8)-0 = 0.08
s1 a2 0.5 0.99*(0.93*0+0.07*7)-0.5 = -0.01
s1 a3 0.5 0.99*(0.85*0+0.15*3)-0.5 = -0.05
s2 a1 0 0.99*(0.8*0+0.2*8)-0 = 1.6
s2 a2 0.5 0.99*(0.72*0+0.28*7)-0.5 = 1.4
s2 a3 0.5 0.99*(0.5*0+0.5*3)-0.5 = 1
若是单周期决策，从上表可以看出，不论初始状态是什么，最有决策都是 a1a1，即不促销不发礼物。

6. 两阶段决策

若是两阶段决策，则期望回报和需要再算一层。

Initial state ss Action aa Action cost c(a)c(a) Expected immediate return
Expected sum immediate return
s1 a1 0 0.99*(0.99*0+0.01*8)-0 = 0.08 0.08 + 0.99*(0.99*0.08+0.01*1.6)=0.1736
s1 a2 0.5 0.99*(0.93*0+0.07*7)-0.5 = -0.01 -0.01 +
0.99*(0.93*0.08+0.07*1.9)=0.17
s1 a3 0.5 0.99*(0.85*0+0.15*3)-0.5 = -0.05 -0.05+0.99(0.85*0.08+0.15*1.6)=0.2
s2 a1 0 0.99*(0.8*0+0.2*8)-0 = 1.6 0.6+0.99(0.85*0.08+0.15*1.6)=1.87
s2 a2 0.5 0.99*(0.72*0+0.28*7)-0.5 = 1.4 1.4+0.99(0.85*0.08+0.15*1.6)=1.85
s2 a3 0.5 0.99*(0.5*0+0.5*3)-0.5 = 1 1+0.99(0.85*0.08+0.15*1.6)=1.75
从上表可以得出最优决策策略是：若初始状态为 s1s1，最优决策 a3a3，即大促销；若初始状态为 s2s2，最优决策 a1a1，即不促销。

7. 最优递推方程

定义 fn(s)fn(s) 表示初始状态为 ss，之后 nn 个阶段的最优期望回报，则最优递推方程可以表示为：

fn(s)=maxar(s,a)+α∑jpsjfn−1(j)fn(s)=maxar(s,a)+α∑jpsjfn−1(j)

更规范的可以这样写：

fn(s)=supa∈Ar(s,a)+α∑jpsjfn−1(j)fn(s)=supa∈Ar(s,a)+α∑jpsjfn−1(j)

界限方程一般是： f0(s)=v(s)f0(s)=v(s)

这就是一个动态规划表达式。

热门工具换一换