MDP - Markov decision problem
###术语解释
state：系统的状态指的是能够描述系统的一个参数或者一组参数。比如一个机器人的地理坐标就是一个状态。状态随时间变化的系统叫做dynamic system。还有一个例子是超市的队伍，假设队伍的长度是一个状态，那么这个状态随时间改变，因此这是一个dynamic system。
需要注意的是MDP中状态之间的转移通常是随机的。
action: 通常，机器人的行动是可控制的，我们希望让机器人选择最优的行动。假设机器人行走的步数是离散的，那么机器人通过每一步的积累就可以向东西南北各个方向行走。东西南北四个选择就称作action或control。
对于前面说过的排队系统，当队伍长度超过一定值，比如10个人，就新开一个柜台。因此，这个系统就有两个action：开柜台，不开柜台。
transition probability：假设action a在状态i被选择，j是下一个状态。p(i,a,j)表示在a的影响下，系统从i过度到j的概率（称作transition probability）。如果一个MDP有3个状态，2个action，则每个action有9个transition probability. 如下图
Immediate Rewards
通常，系统从一个状态转移到另一个状态会立即得到一个reward（可能是正的，也可能是负的，即奖励或者惩罚）。用r(i,a,j)表示。
policy
policy决定了系统在每个状态上要如何采取action。注意有些状态下，没有action可供选择。decision-making states指的就是系统选择action的状态。本教程中所有的状态都是decision-making states。
performance metric
给定Policy，就得有performance metric去度量Policy的优劣。我们的目标是选择Performance metric最好的plicy。
比如，我们可以考虑选择average reward policy。
Time of transition
我们假设MDP的转化时间是均匀的，也即是状态之间的转换时间相同（数据库调优里面是否可以引入time of transition，表示重启数据库的代价？）。对于SMDP，转换时间则不是固定的。
average reward policy
现在，假设一个policy p， p(i)表示该policy在状态i选择的action。当Markov chain上发生jump，我们称一个transition发生了。注意，一个状态也有可能transition到自己。 Xs 表示第s次transition前的状态，注意，在infinite horizon problem中，s是有可能从1到infinity的。下面这个公式表示系统从状态i开始的average reward：
average reward表示immediate reward之和除以jump(transition)次数.E[.]表示方括号内数值的平均值。但是这里有个问题：除以k才是平均值，为什么又用E表示。
不难看到，如果满足一定条件（现实情况下这样的条件也能得到满足），（1）式对任何x1都成立。
average reward MDP的目标就是寻找到能够最大化performance metric(average reward)的plicy。
discounted reward
另外一个比较常用的performance metric是discounted reward。policy p 的 total discounted reward如下：
这里，¡为discount factor，0 < ¡ <1。
SMDP - semi-Markov decision problem RL END 参考资料：
A Tutorial for Reinforcement Learning.Abhijit Gosavi.
|
|