马尔科夫决策过程MDP值迭代和政策迭代 值迭代政策迭代比较 MDP模型无限状态的MDPs 离散化值函数估计 使用一个模型或模拟器适应值迭代

在强化学习中，我们将提供一个奖赏函数，当目标完成的好时，便奖赏；当目标完成的不好时，就惩罚。鞭策算法走一条良好的道路。

马尔科夫决策过程（MDP）

一个Markov decision process是一个元组 (S,A,Psa,γ,R) 。其中：

S 是状态集。比如在自动直升机驾驶中，S就是直升机的所有可能位置，方向。 A 是行动。比如所有你能控制直升机的方向。 Psa是状态转移概率。对于每个状态 s∈S 每个行动 a∈A ， Psa 给出了当我们在状态 s 采取行动a时，我们将会转移到的状态的分布。 γ∈[0,1) 称为阻尼系数。 R:S∗A−>RealNumber 叫做回报函数。

MDP的动态过程：从初始状态 s0 开始，采取行动 a0∈A ；MDP过程向前推进，按分布 s1∼Ps0a0 随机转换到下一个状态 s1 。以此类推，不断转换。用流程可以表示为： s0−>(a0)−>s1−>(a1)−>s2−>(a2)−>... 定义其总花费： R(s0,a0)+γR(s1,a1)+γ2R(s2,a2)+... 我们要做的是选择随时间变化的行动，来使得总花费的期望值最大： max,E[R(s0,a0)+γR(s1,a1)+γ2R(s2,a2)+...]

一个政策是指任意的函数 π:S→A 从状态到行动的映射。当在状态 s 时，我们可以得到行动a=π(s)。 对于一个政策，其价值函数为： Vπ(s)=E[R(s0,a0)+γR(s1,a1)+γ2R(s2,a2)+...|s0=s,π] 给定一个政策 π 其价值函数 Vπ 满足Bellman Equations： Vπ(s)=R(s)+γ∑s′∈SPsπ(s)(s′)Vπ(s′) 最佳值函数： V∗(s)=maxπVπ(s) 可以进一步写为： V∗(s)=R(s)+maxa∈Aγ∑s′∈SPsa(s)(s′)V∗(s′) 最佳政策： π∗(s)=argMaxa∈Aγ∑s′∈SPsa(s)(s′)V∗(s′) 有不等式： V∗(s)=Vπ∗(s)>=Vπ(s)

值迭代和政策迭代

讨论两个解决有限状态MDPs的高效算法。

值迭代

伪代码：

1.For each state s, initialize V(s):=0 . 2.Repeat until convegence{ For every state, update V(s):=R(s)+maxa∈Aγ∑s′∈SPsa(s)(s′)V∗(s′) }

思想：使用Bellman equations重复尝试更新值函数的估计。

政策迭代

伪代码：

1.Initialize π randomly. 2.Repeat until convergence{ Let V:=Vπ For each state s ,let π(s):=argMaxa∈Aγ∑s′∈SPsa(s)(s′)V∗(s′) }

思想：内循环对当前政策重复计算值函数，然后使用当前的值函数更新政策。

比较

对于较小的MDPs，政策迭代会较快收敛；对于大状态集的MDPs，值迭代较为有效。实际中，较常使用的是值迭代。

MDP模型

在实际问题中，我们并得不到确切的转换概率和回报函数，需要从有限的数据中估计他们（通常已知 S,A,γ ）。 而我们所观察到的数据集是： s(1)0−>(a(1)0)−>s(1)1−>(a(1)1)−>s(1)2−>(a(1)2)−>... s(2)0−>(a(2)0)−>s(2)1−>(a(2)1)−>s(2)2−>(a(2)2)−>... ... 这些数据都随时间运行到目标失败的那一刻，因此数据是有限的。 状态转移概率的计算方法： Psa(s′)=#times we took action a in state s and got to s′#times we took action a in state s 以下是一种学习未知状态转移概率的MDP算法：

1.Initialize π randomly. 2.Repeat{ Execute π in the MDP for some number of trials. Using the accumulated experience in the MDP, update our estimates for Psa (and R , if applicable). Apply value iteration with the estimated state transition probabilities and rewards to get a new estiated value function V. Update π to be the greedy policy with respect to V . }

无限状态的MDPs

离散化

通常可以用离散化来解决连续性的问题，当其缺点也显而易见，一个是离散化存在一定误差，另一个是会导致数据维数指数增加。因此，离散化通常用在4d以下的数据中。

值函数估计

不依靠离散化，现在提出另一种直接估计V∗的方法来解决连续MDPs。

使用一个模型或模拟器

可以通过物理性质来建立模型，或者从数据来建立模型。

这里我个人感觉已经非常接近自动控制原理了，在对目标实施控制的时候采取的是建立传递函数，然后反馈的方法。而更进一步，说明无模型的PID算法完全是可以应用在强化学习中的。

适应值迭代

从有限的行动集 A 入手，采用线性规划的方法来估计连续MDPs的价值函数。

1.Randomly m sample states s(1),s(2),s(3),...s(m)∈S. 2.Initialize θ:=0 . 3.Repeat{ For i = 1,…,m{ For each action a∈A { Sample s′1,s′2,...,s′k～Ps(i)a (using a model of the MDP). Set q(a)=1k∑kj=1R(s(i))+γV(s′j)) } set y(i)=maxaq(a) . } set θ:=argMinθ12∑mi=1(θTϕ(s(i))−y(i))2 }