人智导（六）：“不可测”问题的求解

动作效果的不确定性

如图所示：

• 智能体不能确切地直到其动作的效果，可能有多个结果状态
  • 表示为：$[s_1,\dots ,s_n]=result(s_0,a)$
  • 动作效果不确定，需要与环境交互
• 在执行动作之前，智能体需要计算所用结果状态的概率$P(s_i|a)$
• 动作的期望效用(Expected Utility)：$$EU(a)={\Sigma }_{i}P(s_i|a)V(s_i)$$
  • 状态价值函数$V(s)$：状态到实数值的映射
  • 智能体应当选择当前状态下具有最大期望效用(MEU)的动作

最优策略

• 动作后续状态确定(deterministic)的搜索问题
  • 发现最优(optimal)plan，从初始状态到目标状态的一个动作序列
• 动作后续状态不确定(nondeterministic)
  • 发现一个最优(optimal)policy ${\pi }^{\ast }:s\to a$
  • policy策略为一个状态确定应采取的动作(what to do)
  • 最优的policy是满足MEU的

不确定条件下的搜索问题

如图：

• “不可测”问题
  • 目标导向(goal-seeking)
  • 与环境交互，只有动作执行后才能确定后续状态
  • 趋向目标的累计回报(reward)，而非动作直接的回报值
• 求解方法
  • 发现最优policy策略${\pi }^{\ast }:s\to a$
  • 即在任何一个状态$s$，确定趋向目标的最佳动作$a$
  • 定义Q-state状态表示（计算）EU

与环境交互模型

如图：

定义三个本体元素：
状态(state)、动作(action)、回报(reward)
智能体所面对的问题：
与环境交互中确定动作的后续状态，达到目标

马尔可夫决策过程

马尔可夫决策过程(Markov Decision Process)：

• 一个状态(state)集合：$S$
• 一个动作(actions)集合：$A$
• 一个后继函数$T(s,a,s^{\prime })$，且从状态$s$到$s^{\prime }$的概率为$P(s^{\prime }|s,a)$
• 一个回报(reward)函数：$R(s,a,s^{\prime })$
• 初始状态$s_0$
• 一个或多个目标（结束）状态

马尔可夫过程

基本性质

无记忆性(memoryless)
动作和后继状态仅取决于当前所在状态，与之前的状态无关
$$P(S_{t+1}=s^{\prime }|S_t=s_t,A_t=a_t,S_{t-1}=s_{t-1},A_{t-1},\dots ,S_0=s_0)=P(S_{t+1}=s^{\prime }|S_t=s_t,A_t=a_t)$$
正如标准搜索模型，后续函数仅依赖于当前状态

Markov搜索树

如图：

MDP：求解动作效果不确定问题

• 对任意状态$s$下的动作选择：$policy{\pi }^{\ast }(s):s\to a$
• 任意状态$s$选这样的动作，使得价值函数$V(s)$计算累计回报(sum of rewards)期望最大化

如何选择最优动作

• 对任意一个状态$s$，都通过价值函数对应一个值
• $V(s)=$累计回报最大期望值{目标状态$V$值为0}
• 最优策略：${\pi }^{\ast }=ar{g}_{\pi }max{V}^{\pi }(s),(\forall s)$

示例：

如上图
$$V_0=ma{x}_{a\in 1,\dots ,N}(r_a+\gamma V_a)$$

• 非确定动作的最大期望值（如下图）$$V_0=ma{x}_{a\in A}{\Sigma }_{s\in S}{P}_{a,s_0\to s}(r_s+\gamma V_s)$$
• 同时体现了当前动作对后续进程的影响$$V^{\pi }(s_t)=r_t+\gamma r_{t+1}+{\gamma }^2{r}_{t+2}+\cdots ={\Sigma }_{i=0}^{\infty }{\gamma }^i{r}_{t+i}$$

引入$Q(s,a)$状态表示

• 状态$s$及其状态值：$V(s)=$始于$s$按最优策略行动的累计回报
• $Q(s,a)$的值：$Q(s,a)=EU(a)$，在$s$状态下执行$a$
• 最优策略policy:${\pi }^{\ast }(s)$ $${\pi }^{\ast }=ar{g}_{\pi }max{V}^{|pi}(s),(\forall s)$$

最优策略的计算

• 有如下等式$(0\le \gamma \le 1)$: $$V(s)=ma{x}_{a}Q(s,a)$$ $$Q(s,a)={\Sigma }_{s^{\prime }}P(s,a,s^{\prime })[r(s,a,s^{\prime })+\gamma V(s^{\prime })]$$ $$(Bellmanequation)V(s)=ma{x}_a{\Sigma }_{s^{\prime }}P(s,s,s^{\prime })[r(s,a,s^{\prime })+\gamma V(s^{\prime })]$$
• 迭代计算：$$V_{k+1}(s)\leftarrow ma{x}_a{\Sigma }_{s^{\prime }}P(s,a,s^{\prime })[r(s,a,s^{\prime })+\gamma V_k(s^{\prime })]$$
  状态值迭代计算方法：
  
  状态空间：
  S={s1,…,sn} S=\{s_1, \dots ,s_n\}S={s1​,…,sn​}
  Bellman方程组（每个状态对应一个方程）：
  $$\left[\begin{array}{c}{V}_{s1}\\ ⋮\\ V_{sn}\end{array}\right]=\left[\begin{array}{ccc}{P}_{11}& \cdots & P_{1n}\\ ⋮& \ddots & ⋮\\ P_{n1}& \cdots & P_{nn}\end{array}\right]\left[\begin{array}{c}{V}_{s1}\\ ⋮\\ V_{sn}\end{array}\right]$$
  其中：
  $$P_{ij}=\{\begin{array}{ll}{p}_{i\to j}& ifj\in successor(i)\\ 0& otherwise\end{array}$$
  向量表示：
  $$V_{k+1}=P{V}_k$$
  初始条件：
  $$V_0=\left[\begin{array}{c}0\\ ⋮\\ 0\end{array}\right]$$

举例

问题：

MDP搜索树：

迭代计算：