# 第三章：基于模型的动态规划方法

## 3.1 基于模型的动态规划方法理论

强化学习可以归结为序贯决策问题。即找到一个决策序列，使得目标函数最优。

![](/files/-M9D-0oYmxnKc5cU1Pal)

强化学习可以用动态规划的思想求解，要使用动态规划，需要满足两个条件：

1. 整个优化问题可以分解为多个子优化问题；
2. 子优化问题可以被存储和重复利用。

强化学习中动态规划的核心是寻找最优值函数。对于状态值函数的迭代公式：

$$
v\_{\pi}(s)=\sum\_{a\in A}\pi(a|s)(R\_s^a+\gamma \sum\_{s' \in S}P\_{ss'}^a v\_\pi (s'))
$$

在模型已知的情况下，方程中的$$P\_{ss'}^a$$，$$\gamma$$，$$R\_s^a$$都是已知数，$$\pi(a|s)$$是要评估的策略，所以也是已知的，$$x = y$$表示后继状态的值函数。由此可见，方程中唯一的未知数是值函数，所以上面方程是关于值函数的线性方程组，其未知数的个数是状态的总数，用$$|S|$$表示。此处，可以用**高斯-赛德尔**方法求解：

$$
v\_{k+1}(s) = \sum\_{a \in A}\pi(a|s)(R\_s^a+\gamma\sum\_{s'\in S}P^a\_{ss'}v\_k(s'))
$$

**策略评估算法**

```
输入：需要评估的策略pi和状态转移概率p,回报函数r,折扣因子gamma
初始化值函数：V(s)=0
Repeat k=0,1,...
    for every s do
        execute Gaussian-Seidel method
    end for
Until u[k+1] = u[k]
```

网格世界的例子，需要补充两点

1. 衰减系数$$\gamma = 1$$
2. 对于边界情况，用当前位置的值补充遍历无方向的值

更详细的可以参考[知乎讨论](https://zhuanlan.zhihu.com/p/28084990)

两个重要代码：

1. 边界处理

```python
# 根据当前状态和采取的行为计算下一个状态id以及得到的即时奖励
def nextState(s, a):
  next_state = s
  if (s%4 == 0 and a == "w") or (s<4 and a == "n") or \
     ((s+1)%4 == 0 and a == "e") or (s > 11 and a == "s"):
    pass
  else:
    ds = ds_actions[a]
    next_state = s + ds
  return next_state
```

1. 更新规则

```python
# update the value of state s
def updateValue(s):
  sucessors = getSuccessors(s)
  newValue = 0  # values[s]
  num = 4       # len(successors)
  reward = rewardOf(s)
  for next_state in sucessors:
    newValue += 1.00/num * (reward + gamma * values[next_state])
  return newValue
```

得到更新后的值函数后，贪心算法是一种最常见的策略改善算法，即$$\pi\_{l+1}(s) \in argmax\_a q^{\pi\_l}(s,a)$$

至此，已经可以得到策略改善算法

**策略改善算法**

```
输入：需要评估的策略pi和状态转移概率p,回报函数r,折扣因子gamma
初始化值函数：V(s)=0
Repeat k=0,1,...
    for every s do
        策略评估：高斯赛德尔算法
        策略改善：贪心算法
    end for
Until u[k+1] = u[k]
```

不一定要等到策略值函数收敛之后再进行策略改善。如果我们在评估一次之后就进行策略改善，则称之为**值函数迭代算法。**

## 3.2 动态规划中的数学基础讲解

### 3.2.1 线性方程组的迭代解法

状态值函数的计算公式

$$
v\_{\pi}(s)=\sum\_{a\in A}\pi(a|s)(R\_s^a+\gamma \sum\_{s' \in S}P\_{ss'}^a v\_\pi (s'))
$$

是一个线性方程组，求解线性方程组有直接法和简介迭代法。策略评估中采用的是迭代解法。

#### 什么是迭代解法

一般的线性方程组可以表示为：

$$
AX=b
$$

所谓迭代解法就是根据上式设计一个迭代公式，代入初始值$$X^{(0)}$$，将其代入迭代公式得到$$X^{(1)}$$，再代入$$X^{(1)}$$得到$$X^{(2)}$$，如此循环直到收敛到$$X$$

求解迭代公式有两种解法：

（1）雅克比迭代法

（2）高斯-赛德尔迭代法

### 3.2.2 压缩映射证明策略评估的收敛性

不动点和压缩映射常用来解决代数方程，微分方程，积分方程等，为方程解的存在性，唯一性和讨论迭代收敛性证明提供有力的工具。

定义：设X是度量空间，其度量用$$\rho$$表示。映射$$T:X\rightarrow X$$，若存在$$a$$，$$0 \leq a < 1$$使得$$\rho(Tx, Ty) \leq \rho(x,y), \forall x,y \in X$$，则称T是X上的一个**压缩映射**。

若存在$$x\_0 \in X$$使得$$Tx\_0 = x\_0$$，则称$$x\_0$$是$$T$$的**不动点**。

#### 定理1：完备度量空间上的压缩映射具有唯一的不动点。

定理1是说：从度量空间任何一点出发，只要满足压缩映射，压缩映射的序列必定会收敛到唯一的不动点。所以可以通过证明压缩映射来评估策略的收敛性。

## 3.3 基于gym的变成实例

下面给出重要函数的代码片段

**策略迭代方法**

```python
def policy_evaluate(self, grid_mdp):
    for i in range(1000):
        delta = 0.0
        for state in grid_mdp.states:
            if state in grid_mdp.terminal_states: continue
            action = self.pi[state]
            t, s, r = grid_mdp.transform(state, action)
            new_r = r + grid_mdp.gamma * self.v[s]
            delta += abs(self.v[state] - new_v)
            self.v[state] = new_v
        if delta < 1e-6:
            break
```

**策略改善方法**

```python
def policy_improve(self, grid_mdp):
    for state in grid_mdp.states:
        if state in grid_mdp.terminal_states: continue
        a1 = grid_mdp.actions[0]
        t, s, r = grid_mdp.transform(state, a1)
        v1 = r + grid_mdp.gamma * v[s]
        for action in grid_mdp.actions:
            t, s, r = grid_mdp.transform(state, action)
                if v1 < r + grid_mdp.gamma * v[s]:
                    a1 = action
                    v1 = r + grid_mdp.gamma * v[s]
        self.pi[state] = a1
```

**值迭代算法**

```python
def value_iteration(self, grid_mdp):
    for i in range(1000):
        delta = 0.0
        for state in grid_mdp.states:
            if state in grid_mdp.terminal_states: continue
            a1 = grid_mdp.actions[0]
            t, s, r = grid_mdp.transform(state, a1)
            v1 = r + grid_mdp.gamma * v[s]
            for action in grid_mdp.actions:
                t, s, r = grid_mdp.transform(state, action)
                    if v1 < r + grid_mdp.gamma * v[s]:
                    a1 = action
                    v1 = r + grid_mdp.gamma * v[s]

            delta += abs(self.v[state] - new_v)
            self.v[state] = v1
            self.pi[state] = a1
        if delta < 1e-6:
            break
```

## 3.3 最优控制与强化学习比较

最优控制的计算方法分类如下图

![](/files/-M9D-0odvzsYAbBQInUJ)

间接法：是指首先利用变分法，最大值原理或者动态规划方法得到求解最优解的一组微分方程，之后，利用数值求解方法求出此微分方程的解，此解即为原最优问题的解

直接法：直接在可行控制集上搜索，找到最优的解

1. 将状态变量和控制变量参数化，将最优控制问题转换为参数优化问题
2. 引入空间中的內积和泛函的梯度，将静态的优化方法推广导函数空间中

**最优控制和强化学习的联系**

在基于模型的强化学习中，智能体会先利用交互数据拟合一个模型，有了模型，我们就可以利用最优控制的计算方法计算当前最优解，产生当前的最优控制率。智能体会利用当前的最优控制率与环境交互，进一步优化行为。


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://senliuy.gitbook.io/reinforcement-learning-note/shen-ru-qian-chu-qiang-hua-xue-xi-yuan-li-ru-men/di-san-zhang-ff1a-ji-yu-mo-xing-de-dong-tai-gui-hua-fang-fa.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.