引言——成本总和的最小化
无限阶段问题的成本总和
定义非时变离散时间动态系统： \[x_{k+1}=f(x_k,u_k,w_k)\] \[x_k\in{}S,u_k\in{}U(x_k)\subset{}C,w_k\sim{}P(\cdot{}|x_k,u_k)\]
给定初始状态\(x_0\)，成本函数\(g(\cdot,\cdot,\cdot):S\times{}C\times{}D\rightarrow\mathcal{R}\)和折扣因子\(\alpha\)，现需要找到\(\pi=\{\mu_0,\mu_1,...\},\mu_k\in{}U(x_k)\)，使得如下定义的成本最小：
\[J_\pi(x_0)=\lim_{N\rightarrow{}\infty}E_{w_k}\{\sum_{k=0}^{N-1}\alpha^kg(x_k,\mu_k(x_k),w_k)\}\]
对于所有合法的\(\pi\)构成的集合记为\(\Pi\)，则记最优成本函数为： \[J^*(x)=\min_{\pi\in\Pi}J_\pi(x)\quad{}x\in{}S\]
如果对于所有初始状态，其最优策略相同，则称该问题为稳定问题，该最优策略为最优稳定策略：
\[J_\mu(x)=J^*(x)\]
有限阶段问题的DP算法
对于\(N\)个阶段的成本问题，DP算法为： \[J_{N-k}(x)=\min_{u\in{}U(x)}E\{\alpha^{N-k}g(x,u,w)+J_{N-k+1}(f(x,u,w))\}\] \[J_N(x)=\alpha^NJ(x)\] 重新作如下记号： \[V_k(x)=\frac{J_{N-k}(x)}{\alpha^{N-k}},\quad{}V_0(x)=J(x)\] \[V_{k+1}(x)=\min_{u\in{}U(x)}E\{g(x,u,w)+\alpha{}V_k(f(x,u,w))\}\]
简记与单调性
对于\(J:S\rightarrow\mathcal{R}\)，采用\(TJ\)记对\(J\)应用DP算法： \[(TJ)(x)=\min_{u\in{}U(x)}E\{g(x,u,w)+\alpha{}J(f(x,u,w))\}\] 我们视\(T\)为\(S\)上函数\(J\)到\(TJ\)的映射。 同样，有如下简记： \[(T_\mu{}J)(x)=E\{g(x,\mu(x),w)+\alpha{}J(f(x,\mu(x),w))\}\] \[(T^kJ)(x)=(T(T^{k-1}J))(x),\quad{}(T^0J)(x)=J(x)\]
引理 1.1.1: 单调性引理
对于任何函数\(J:S\rightarrow{}\mathcal{R}\)和\(J^{'}:S\rightarrow\mathcal{R}\) \[J(x)\leq{}J^{'}(x)\quad{}\text{for all }x\in{}S\] 对于任何稳定策略\(\mu:S\rightarrow{}C\)： \[(T^kJ)(x)\leq{}(T^kJ^{'})(x)\quad{}\text{for all }x\in{}S,k=1,2,...,\] \[(T_\mu^kJ)(x)\leq{}(T_\mu^kJ^{'})(x)\quad{}\text{for all }x\in{}S,k=1,2,...,\]
引理 1.1.2
定义单位函数为\(e(x)\equiv1(\forall{}x\in{}S)\)，则对于任何函数\(J:S\rightarrow{}\mathcal{R}\)，稳定策略\(\mu:S\rightarrow{}C\)，标量\(r\)： \[(T^k(J+re))(x)=(T^kJ)(x)+\alpha^kr\quad{}\text{for all }x\in{}S\] \[(T_\mu^k(J+re))(x)=(T_\mu^kJ)(x)+\alpha^kr\quad{}\text{for all }x\in{}S\]
随机的过去依赖策略
命题 1.1.1： Markov策略的合理性
假设策略集合是可数的，初始状态是可数集合上的分布。则每对\((x_k,u_k)\)以及与随机的过去依赖策略相对应的每阶段的期望成本，同样可以以随机Markov策略获得。
有界的阶段成本的折扣问题
假设D： 折扣成本-有界的阶段成本
存在标量\(M\)使阶段成本\(g\)满足 \[|g(x,u,w)|\leq{}M,\quad\text{for all }(x,u,w)\in{}S\times{}C\times{}D\]
命题 1.2.1： DP算法的收敛性
对于有界函数\(J:S\rightarrow{}\mathcal{R}\)，最优成本函数满足： \[J^*(x)=\lim_{N\rightarrow\infty}(T^NJ)(x)\quad\text{for all }x\in{}S\]
推论 1.2.1.1
对于稳定策略\(\mu\)，相关联的成本函数满足： \[J_{\mu}(x)=\lim_{N\rightarrow\infty}(T_{\mu}^NJ)(x)\quad\text{for all }x\in{}S\]
命题 1.2.2：贝尔曼方程
最优成本函数满足： \[J^*=TJ^*\] 此外，\(J^*\)也是有界成本函数中满足这一方程的唯一解
推论 1.2.2.1
对于稳定策略\(\mu\)，相关联的成本函数满足： \[J_{\mu}=T_{\mu}J_{\mu}\] 此外，\(J_{\mu}\)也是有界成本函数中满足这一方程的唯一解
命题 1.2.3：最优的充要条件
稳定策略\(\mu\)是最优的当且仅当对于\(\forall{}x\in{}S\)，\(\mu(x)\)取得了贝尔曼方程的最小值，即： \[TJ^*=T_{\mu}J^*\]
命题 1.2.4
对于任意两个有界函数\(J:S\rightarrow{}\mathcal{R},J^{'}:S\rightarrow{}\mathcal{R}\)，有： \[(\forall{}k)~\max_{x\in{}S}|(T^kJ(x)-(T^kJ^{'})(x))|\leq\alpha^k\max_{x\in{}S}|J(x)-J^{'}(x)|\]
