2. Stochastic Finite Horizon Problem

在这一节中主要介绍了随机DP算法来解决不确定性下的有限地范围问题，如Denition 1.4所述，它被表述为一个组合优化问题。众所周知，由于组合爆炸，它是一个极其困难的问题。为了从结构上缓解这种极端的复杂性，一种方法是对所有决策规则的空间进行建模，这样就可以在一些方便的搜索空间，即策略空间中有效地解决这个问题。

Review

Definition 1.4 有限范围的随机顺序决策(Stochastic Sequential decision making with finite horizon).

给定一个如公式（1.2）的离散时间动态系统，一个有限范围SDM问题旨在为任意$x_0\in {\mathcal{X}}_0$，找到一个行动序列$\pi \in {\mathcal{U}}_0\times ...\times {\mathcal{U}}_{N-1}$，这样就可以解决以下最小化问题

$$\underset{\pi }{\min }{\mathbb{E}}_{p(w)}[g_N(x_N)+\sum _{k=0}^{N-1}{g}_k(x_k,u_k,w_k)]\text{\hspace{1em}(1.6)}$$

以上定义了组合优化问题（combinatorial optimisation problem），但是同时会造成组合爆炸问题（combinatorial explosion）。为了减少这种复杂性，一种方法是对所有决策规则空间建模。

可以看到，一旦Definition 1.4中给出的随机有限范围问题的解决方案被确定下来，它就对任意状态$x-k$有一个明确的动作分配$u_k$。这类分配的集合被称为确定性的历史无关策略。

Definition 2.1 确定性的历史无关策略(Deterministic History-independent Policy).

确定性的历史无关策略，也被称为确定性的马尔科夫策略( deterministic Markov Policy)， 对于所有$k=0,1,...,N-1$ 它是一个只基于状态$x_k$决策规则, 即

$${\pi }_k:{\mathcal{X}}_k\to {\mathcal{U}}_k,x_k\to u_k\text{\hspace{1em}(2.1)}$$

Definition 2.2 有限范围的尾部子问题 (Tail subproblems of a finite horizon problem).

给定一个如公式（1.2）的离散时间动态系统，在每个阶段$k=1,2,\dots ,N-1$，随机有限水平问题的第$k$个尾部子问题旨在为任何$x_k\in {\mathcal{X}}_k$找到行动序列 ${\mu }_k:=\left\{u_k,u_{k+1},\dots ,u_{N-1}\right\}\in {\mathcal{U}}_k\times \dots \times {\mathcal{U}}_{N-1}$ ，这样就解决了以下最小化问题

$$\underset{{\mu }_k}{\min }{\mathbb{E}}_{p\left({\tilde{w}}_k\right)}[g_N\left(x_N\right)+\sum _{t=k}^{N-1}{g}_t(x_{}$$