Chapter 3: Optimal Policy and Bellman Optimality Equation

Motivating examples

给定如下策略（令$\gamma=0.9$）：

贝尔曼公式：

$$\begin{aligned} v_{\pi}(s_1) &= -1 + \gamma v_{\pi}(s_2), \\ v_{\pi}(s_2) &= +1 + \gamma v_{\pi}(s_4), \\ v_{\pi}(s_3) &= +1 + \gamma v_{\pi}(s_4), \\ v_{\pi}(s_4) &= +1 + \gamma v_{\pi}(s_4). \end{aligned}$$

解方程组得 State values: $v_{\pi}(s_4) = v_{\pi}(s_3) = v_{\pi}(s_2) = 10, v_{\pi}(s_1) = 8$

有了state value之后我们可以计算action values:

$$\begin{aligned} q_{\pi}(s_1, a_1) &= -1 + \gamma v_{\pi}(s_1) = 6.2, \\ q_{\pi}(s_1, a_2) &= -1 + \gamma v_{\pi}(s_2) = 8, \\ q_{\pi}(s_1, {\color{blue}a_3}) &= 0 + \gamma v_{\pi}(s_3) = 9, \\ q_{\pi}(s_1, a_4) &= -1 + \gamma v_{\pi}(s_1) = 6.2, \\ q_{\pi}(s_1, a_5) &= 0 + \gamma v_{\pi}(s_1) = 7.2. \end{aligned}$$

• 接下来的问题是 $\color{blue}\text{While the policy is not good, how can we improve it?}$
• Answer: We can improve the policy based on action values

目前的$\pi(a|s_1)$ 策略：

$$\pi(a|s_1) = \begin{cases} 1 & a = a_2 \\ 0 & a \neq a_2 \end{cases}$$

显然这个策略不够好，因为从$s_1$向右走（$a_2$）会进入forbidden area。

观察上面的action value，$q_{\pi}(s_1,a_3)$最大，那么我们可以改进策略：

$$\pi_{\star}(a|s_1) = \begin{cases} 1 & a = a_3 \\ 0 & a \neq a_3 \end{cases}$$

Optimal Policy

The state value could be used to evaluate if a policy is good or not: if

$$v_{\pi_1}(s) \geq v_{\pi_2}(s) \quad \text{for all } s \in \mathcal{S}$$

then $\pi_1$ is “better” than $\pi_2$.

The definition leads to many questions:

• Does the optimal policy exist?
• Is the optimal policy unique?
• Is the optimal policy stochastic or deterministic?
• How to obtain the optimal policy?

To answer these questions, we study the Bellman optimality equation.

Bellman optimality equation (BOE) 贝尔曼最优化公式

Element-wise

贝尔曼方程（element-wise form）

$$v_{\pi}(s) = \sum_{a} \pi(a|s) \left[ \sum_{r} p(r|s, a) r + \gamma \sum_{s'} p(s'|s, a) v_{\pi}(s') \right], \quad s \in \mathcal S$$

右侧加上取最大值，得到Bellman optimality equation (BOE)

$$\begin{aligned} v(s) &= {\color{blue}\max_{\pi}} \sum_{a} {\color{blue}\pi(a|s)} \left( \sum_{r} p(r|s, a) r + \gamma \sum_{s'} p(s'|s, a) v(s') \right), \quad s \in \mathcal{S} \\ &= {\color{blue}\max_{\pi}} \sum_{a} {\color{blue}\pi(a|s)} q(s, a), \quad s \in \mathcal{S} \end{aligned}$$

Remarks:

• $p(r|s,a), p(s'|s,a), r, \gamma$ are known.
• $v(s), v(s')$ are unknown and to be calculated.
• Is $\pi(s)$ known or unknown?
  • 贝尔曼公式$\pi$是给定的，贝尔曼最优公式是不给定的，你需要去求解 ${\color{blue}\argmax_{\pi}} \sum_{a} {\color{blue}\pi(a|s)} q(s, a), \quad s \in \mathcal{S}$ 然后带回公式

Matrix-vector form

Bellman optimality equation (matrix-vector form):

$${\color{red}v = \max_{\pi}(r_{\pi} + \gamma P_{\pi} v)}$$

where the elements corresponding to $s$ or $s'$ are

$$\begin{aligned} [r_{\pi}]_s &\triangleq \sum_{a} \pi(a|s) \sum_{r} p(r|s, a) r, \\ [P_{\pi}]_{s,s'} &= p(s'|s) \triangleq \sum_{a} \pi(a|s) \sum_{s'} p(s'|s, a) \end{aligned}$$

Here $\max_{\pi}$ is performed elementwise:

$$\max_{\pi} \begin{bmatrix} * \\ \vdots \\ * \end{bmatrix} = \begin{bmatrix} \max_{\pi(s_1)} * \\ \vdots \\ \max_{\pi(s_n)} * \end{bmatrix}$$

注意这里max作用于一个向量的时候是逐元素的，上面向量中也把下标写成了$\max_{\pi(s_i)}$来表示对每个s对应的action进行最大化

更准确的可以写成：

$$\begin{bmatrix} \max_{\pi(\cdot|s_1)}F_{s_1}(\pi)\\ \max_{\pi(\cdot|s_2)}F_{s_2}(\pi)\\ \vdots\\ \max_{\pi(\cdot|s_n)}F_{s_n}(\pi) \end{bmatrix}$$

因为一个完整 policy $\pi$ 本身其实就是：

$$\boxed{ \pi= \{ \pi(\cdot|s_1), \pi(\cdot|s_2), \dots, \pi(\cdot|s_n) \} }$$

也就是说，policy 是每个状态下 action 概率分布的集合。上面的向量中每个分量求出$\pi(\cdot | s_i)$ 最终合起来变成完整的使action value最大化的$\pi$

Maximization on the right-hand side of BOE

$$\begin{aligned} v(s) &= {\color{blue}\max_{\pi}} \sum_{a} {\color{blue}\pi(a|s)} \left( \sum_{r} p(r|s, a) r + \gamma \sum_{s'} p(s'|s, a) v(s') \right), \quad s \in \mathcal{S} \\ &= {\color{blue}\max_{\pi}} \sum_{a} {\color{blue}\pi(a|s)} q(s, a), \quad s \in \mathcal{S} \end{aligned}$$

由于$\pi$是可以改变的，那么我们应该固定$q(s,a)$，所以上式：

$$= \color{red} \max_{a \in \mathcal A(s)} q(s,a)$$

where the optimality is achieved when

$$\pi(a|s) = \begin{cases} 1 & a = a^* \\ 0 & a \neq a^* \end{cases}$$

where $a^* = \arg\max_a q(s,a)$.

Solve the Bellman optimality equation

The BOE is $v = \max_{\pi}(r_{\pi} + \gamma P_{\pi} v)$ , Let:

$$f(v) := max_{\pi} (r_{\pi} + \gamma P_{\pi} v)$$

BOE becomes:

$$v=f(v)$$

因为这是向量形式，拆开：

$$v= \begin{bmatrix} v(s_1)\\ v(s_2)\\ \vdots\\ v(s_n) \end{bmatrix} = \begin{bmatrix} [f(v)]_{s_1}\\ [f(v)]_{s_2}\\ \vdots\\ [f(v)]_{s_n} \end{bmatrix}$$

where

$$[f(v)]_s = \max_{\pi} \sum_{a} \pi(a|s) q(s,a), \quad s \in \mathcal{S}$$

Preliminaries: Contraction mapping Theorem

• Fixed point: $x \in X$ is a fixed point of $f : X \to X$ if

  $$f(x) = x$$

• Contraction mapping (or contractive function): $f$ is a contraction mapping if

  $$\|f(x_1) - f(x_2)\| \leq \gamma \|x_1 - x_2\|$$

  where $\gamma \in (0, 1)$.

  • $\gamma$ must be strictly less than 1 so that many limits such as $\gamma^k \to 0$ as $k \to 0$ hold.
  • Here $\|\cdot\|$ can be any vector norm.

这里这个Algorithm迭代法，画成函数图像比较像蛛网模型

Solve the Bellman optimality equation

Let’s come back to the Bellman optimality equation:

$$v = f(v) = \max_{\pi}(r_{\pi} + \gamma P_{\pi} v)$$

Theorem (Contraction Property)

$f(v)$ is a contraction mapping satisfying

$$\|f(v_1) - f(v_2)\| \leq \gamma \|v_1 - v_2\|$$

where $\gamma$ is the discount rate!

（证明没看qaq）

既然贝尔曼最优方程已经满足contraction property，那么直接用上contraction mapping theorem

Important: The algorithm in (1) is called the value iteration algorithm. We will analyze it in the next lecture! This lecture focuses more on the fundamental properties.

Policy optimality

Suppose $v^{\star}$ is the solution to the Bellman optimality equation. It satisfies

$$v^{\star} = \max_{\pi} (r_{\pi} + \gamma P_{\pi} v^{\star})$$

设：

$$\pi^{\star} = \arg \max_{\pi} (r_{\pi} + \gamma P_{\pi} v^{\star})$$

则：

$$v^{\star} = r_{\pi^{\star}} + \gamma P_{\pi^{\star}} v^{\star}$$

此时$\pi^{\star}$是一个策略，并且$v^{\star} = v_{\pi^{\star}}$ 是$\pi^{\star}$所对应的state value

并且我们有结论，$\pi^{\star}$就是最优策略，并且$v^{\star}$就是最优策略所对应的state value

Theorem（Policy Optimality）

Suppose That $v^{\star}$ is the unique solution to $v = \max_{\pi} (r_{\pi} + \gamma + P_{\pi} v)$ , and $v_{\pi}$ is the state value function satisfying $v_{\pi} = r_{\pi} + \gamma + P_{\pi} v_{\pi}$ for any given policy $\pi$ , then:

$$v^{\star} \ge v_{\pi}, \quad \forall \pi$$

What does an optimal policy $\pi^\star$ look like?

$$\pi^\star(s) = \arg\max_{\pi} \sum_a \pi(a|s) \underbrace{\left( \sum_r p(r|s,a) r + \gamma \sum_{s'} p(s'|s,a) v^\star(s') \right)}_{q^\star(s,a)}$$

Analyzing optimal policies

What factors determine the optimal state value and optimal policy? It can be clearly seen from the BOE

$$v(s) = \max_{\pi} \sum_a \pi(a|s) \left( \sum_r {\color{red}p(r|s,a) r} + {\color{red}\gamma } \sum_{s'} {\color{red} p(s'|s,a) v(s')} \right)$$

这里红色的量是已知的（$\gamma, r$等等我们可以去设计），需要求解最优策略$\pi$和对应状态量$v$

that there are three factors:

• System model: $p(s'|s,a)$, $p(r|s,a)$
• Reward design: $r$
• Discount rate: $\gamma$

We next show how $r$ and $\gamma$ can affect the optimal policy.

这里有一个隐藏条件$r_{otherstep} = 0$

主要的规律是：

• $\gamma$大，策略远视，$\gamma$小，策略偏向即时reward
• $\gamma = 0$ The optimal policy becomes extremely short-sighted
• $r$的变化会改变策略，改变所有r： $r \rightarrow ar+b$不会改变最优策略
• $\gamma < 1$也会约束策略不会走特别长的步数