随机最优控制理论1: 动态规划

最近在倒腾订单执行的东西，发现这套数学框架非常满足我的需求，因此现学现卖，做点笔记。

基础的定义

定义1. state, action, rewards

考虑一个离散时间的系统\(t=\{0,1,...T\}\)，定义:

1.\(x\in\mathcal{X}\)为状态以及所有状态的集合, \(x_t\)为\(t\)时刻的状态.

2.\(a\in\mathcal{A}\)为操作以及所有可能操作的集合

3.在状态\(x\)时采取操作\(a\)获得的回报为\(r=r(a,x)\), 并且定义\(r(x)\)为在最终时间\(T\)，状态为\(x\)时的最终回报

定义2. 动态规划函数

操作\(a\)作用以后，我们会从当前状态\(x\)进入下一个状态\(\hat{x}\), 这个状态转移函数称动态规划函数\(f: \mathcal{X}\times\mathcal{A}\rightarrow \mathcal{A}\) \[ \hat{x} = f(x,a) \] 定义3. 策略和效用函数

定义一个策略\(\pi = (\pi_0,\pi_1,...\pi_{T-1})\), 表示在时刻\(t\)时采用操作\(\pi_t\). 在选定了最初状态\(x_0\)后，该操作与动态规划函数定义了一个状态序列\(x_t\): \[ x_{t+1}=f(x_t,\pi_t) \] 我们定义从时间0到T结束后，每次action的回报之和为效用函数: \[ R(x_0,\pi) = r(x_T) + \sum_{i=0}^{T-1}r(x_i,\pi_i) \] 定义4. 动态规划

整个最优控制理论的目标，就是找到一个策略\(\pi\in\Pi\)，能够使得效用函数达到最大： \[ V(x_0)=\max_{\pi} R(x_0, \pi) \] 其中\(V(x_0)\)是最大效用, \(\Pi\)为所有可能策略的集合。

对于任意时间节点\(t\)，我们也有

一个动态规划用形式化的语言定义就是: \[ \begin{equation} V(x_0)=\left\{ \begin{aligned} \max_\pi& R(x_0,\pi) = r(x_T) + \sum_{i=0}^{T-1}r(x_i,\pi_i)\\ \text{s.t }& x_{t+1} = f(x_t,\pi_t) \\ \text{over }& \pi_t \in \mathcal{A} \end{aligned} \right. \end{equation} \]

Bellman Equation

定理1. Bellman Equation

我们考虑从终止时间\(T\)往前数\(\tau\)个时间，也就是从\(t=T-\tau\)时刻后的的未来回报： \[ \begin{equation} \begin{aligned} R(x_{T-\tau},\pi_{T-\tau}) &= r(x_T) + \sum_{i=T-\tau}^{T-1}r(x_i,\pi_i)\\ &= r(x_T) +\sum_{i=T-(\tau-1)}^{T-1}r(x_i,\pi) + r(x_\tau,\pi_\tau)\\ &= R(x_{T-(\tau-1)},\pi_{T-(\tau-1)}) + r(x_\tau,\pi_\tau) \end{aligned} \end{equation} \] 这一段时间的未来回报，也对应了一个动态规划： \[ \begin{equation} \begin{aligned} V(\tau,x_{T-\tau}) &= \max_{\pi}R(x_{T-\tau},\pi_{T-\tau}) \\ &= \max_{\pi}\left\{ R(x_{T-(\tau-1)},\pi_{T-(\tau-1)}) + r(x_\tau,\pi_\tau) \right\}\\ &= \max_{\pi}\left\{ \max _{\pi}R(x_{T-(\tau-1)},\pi_{T-(\tau-1)}) + r(x_\tau,\pi_\tau) \right\}\\ &= \max_{\pi}\left\{ V(\tau-1, x_{T-(\tau-1)}) + r(x_\tau,\pi) \right\} \\ &= \max_{\pi}\left\{ V(\tau-1,f(x_{T-\tau},\pi)) + r(x_\tau,\pi) \right\} \end{aligned} \end{equation} \] 这个结果称为Bellman Equation。它展示了一个以递归方式总的最优解的寻找方法：先寻找\(t=T\)时的最优策略，再寻找\(t=[T-1,T]\)时间段内的最优策略，以此类推。

例：平衡二叉树路径最大值

给定一个平衡二叉树，每个节点上有一值score:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

寻找其从根节点到某个叶子节点的最大score路径。

Solution:

设平衡二叉树的深度为\(T\)，根节点深度为0。\(x \in \mathcal{X}\)为所有的树节点. Bellman Equation为 \[ V_{\tau} = \max_{\pi\in[\text{left, right}]}\left\{ V_{\tau-1}(f(x_\tau,\pi)) + r(x_\tau,\pi) \right\} \] 其中 \[ \begin{aligned} f(x,\text{left}) &:= \text{left}(x) \\ f(x,\text{right}) &:= \text{right}(x) \\ r(x,\pi) &:= \text{value}(x) \end{aligned} \] 于是可以通过递归的方式寻找最大score：

def maximum_path(node: TreeNode): int:
	if node == None:
        return 0
   	return node.score + max(maximum_path(node.left), maximum_path(node.right))

对于一个input:

     1
   /   \
  0     7
 / \   / \
1   5 6   5

最终得到结果为：14 root->right->left->terminated