马尔科夫早就了解过，但一直没有真正用马尔科夫的思想求解问题，更没有用到论文中去。
最近发现了一本好书： 《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 s s | Action a a | Next state1 and possibility p a s 1 ps1a | Next state2 and possibility p a s 2 ps2a |
|---|---|---|---|
| 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
有效转移概率
q
a
s
j
=
α
∗
p
a
s
j
qsja=α∗psja
5. 即时收益（immediate value）
若顾客不购买商品，收益为 0；
不促销时，顾客购买商品，收益为 8；
小促销时，顾客购买商品，收益为 7；
大促销时，顾客购买商品，收益为 3；
减去成本，得到的期望即时回报（immediate return） r ( s , a ) r(s,a) 为：
| Initial state s s | Action a a | Action cost c ( a ) c(a) | Expected immediate return |
|---|---|---|---|
| s1 | a1 | 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.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 |
若是单周期决策，从上表可以看出，不论初始状态是什么，最有决策都是 a 1 a1 ，即不促销不发礼物。
6. 两阶段决策
若是两阶段决策，则期望回报和需要再算一层。
| Initial state s s | Action a a | Action cost c ( a ) c(a) | Expected immediate return | Expected sum immediate return |
|---|---|---|---|---|
| s1 | a1 | 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.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 |
从上表可以得出最优决策策略是：若初始状态为 s 1 s1 ，最优决策 a 3 a3 ，即大促销；若初始状态为 s 2 s2 ， 最优决策 a 1 a1 ，即不促销。
7. 最优递推方程
定义
f
n
(
s
)
fn(s)
表示初始状态为
s
s
，之后
n
n
个阶段的最优期望回报，则最优递推方程可以表示为：
f n ( s ) = max a r ( s , a ) + α ∑ j p sj f n −1 ( j ) fn(s)=maxar(s,a)+α∑jpsjfn−1(j)
更规范的可以这样写：
f n ( s ) = sup a ∈ A r ( s , a ) + α ∑ j p sj f n −1 ( j ) fn(s)=supa∈Ar(s,a)+α∑jpsjfn−1(j)
界限方程一般是： f ( s ) = v ( s ) f0(s)=v(s)
这就是一个动态规划表达式。