Reinforcement Learning - Basics

1. 基本概念

这是一个强化学习的最基本示例：

• Task

  机器人在一个 Grid of Cells 里，找到从起点走到终点的最优路径

• Rules

  1. 可以自由移动（不能斜着走），但是不应该进入 Forbidden Cells，会因此受罚

  2. 机器人无法感知，Grid of Cells 对它而言是个黑箱

 

 

1.1 State

Status of the agent with respect to the environment

本案例中机器人的 Location 就是 State，9 个 Cells 就是 9 个 State: $s_1,s_2,...,s_9$$s_1, s_2,..., s_9$

State Space = The set of all States $S=\{s_i{\}}_{i=1}^9$$S = \{s_i\}^9_{i=1}$

 

 

1.2 Action

每一个 State 都有可以执行的 Action，本案例中有 5 种：上 ($a_1$$a_1$)，下 ($a_3$$a_3$)，左 ($a_4$$a_4$)，右 ($a_2$$a_2$)，静止 ($a_5$$a_5$)

不同的 State 可用的 Action 不一样，比如理论上位于最上方的 State $s_1,s_2,s_3$$s_1,s_2,s_3$ 就不应该有 Action $a_1$$a_1$，否则会撞墙

但实际上可能仍然会保留 $a_1$$a_1$，并为了严谨性增加 “撞墙回弹的功能”

Action Space of State = The set of all Actions of a State $A(s_i)=\{a{\}}_{i=1}^5$$A(s_i) = \{a\}^5_{i=1}$

 

 

1.3 State-Transition

它描述的是这么一个过程：When taking an Action, the agent may move from one State to another

• Deterministic

  在哪一个 State 做了哪一个 Action 会转到哪一个 State 是100%确定的，你在 $s_5$$s_5$ 左转 ($a_2$$a_2$) 一定会进入 $s_6$$s_6$

  $$s_5\stackrel{a_2}{\to }{s}_6$$

  用 State-Transition Probability 的方式表示为

  $$\begin{array}{rl}p(s_6|s_5,a_2)& =1\\ p(s_i|s_5,a_2)& =0\mathrm{\forall }i\ne 6\end{array}$$

  也可以用 Tabular Representation

  

• Stochastic

  很多情况下 State-Transition 是 Stochastic 的，即在同一 State 采取同一 Action 可能跳转到不同的新 State，比如：

  1. 上面的 Table 里 $s_1,s_2,s_3$$s_1,s_2,s_3$ 的 Action Space 包含了 $a_1$$a_1$，但是采取后的效果相当于静止

  2. 墙若有弹性，那么在 $s_1$$s_1$ 采取 $a_1$$a_1$ 后撞墙，Agent 的状态有两种可能性：

     • 弹回到 $s_1$$s_1$ 原地静止

     • 弹回到 $s_4$$s_4$

  假设 2. 中所述两种情况的概率是 50-50，那么用 Conditional Probability 可表示为

  $$\begin{array}{rl}p(s_1|s_1,a_1)& =0.5\\ p(s_4|s_1,a_1)& =0.5\\ p(s_i|s_1,a_1)& =0\mathrm{\forall }i\ne 1,4\end{array}$$

  不过 Stochastic 的 State-Transition 就没法写成 Table 了

• General Form

   

 

 

1.4 Policy

这和 State-Transition 是两个东西！各自的 Conditional Probability 定义不一样！！！

Policy $\pi$$\pi$ is a (probabilistic) mapping from State Space to Action Space

有点像是一种 “场”，在当前类型的案例里一般用箭头表示；无论 Agent 在哪里 / 哪个 State，Policy 都能告诉它下一步要往哪里走

所以无论 Agent 从哪里开始任务，policy 最终都应该能把它带到目的地，就像上图一样

• Deterministic

  如上图，一个 State 能采取的 Action 是确定的，只有一个

  

  以 $s_1$$s_1$ 为例，与它相关的 Policy 用 Conditional Probability 可表示为

  $$\begin{array}{rl}\pi (a_2|s_1)& =1\\ \pi (a_i|s_1)& =0\mathrm{\forall }i\ne 2\end{array}$$

• Stochastic

  一个 State 有概率采取不同的 Action

  

  以 $s_1$$s_1$ 为例，与它相关的 Policy 用 Conditional Probability 可表示为

  $$\begin{array}{rl}\pi (a_2|s_1)& =1\\ \pi (a_3|s_1)& =0.5\\ \pi (s_i|a_1)& =0\mathrm{\forall }i\ne 2,3\end{array}$$

  也可以写成 Table，与 State-Transition 完全不一样，Policy 无论 Deterministic / Stochastic 都可以用 Tabular Representation

  

 

 

1.5 Reward

在采取某个 Action 后得到的数值

• Positive Reward = Encouragement to take such Action

• Negative Reward = Punishment to take such Action

好吧，其实你也可以用 Positive Number 表示 punishment，但那样 Reward 就该改名叫 Cost 了

Reward 的 Absolute Values 不重要，重要的是 Relative Values

Changing $r=\{+1,-1\}$$r = \{+1, -1\}$ to $r=\{+2,0\}$$r = \{+2, 0\}$ will not make any difference

• Deterministic

  一个 Action 始终只会对应一个 Reward 数值

  

  可以写成如上 Table 并作如下设定

  • $r_{bound}=-1⟶$$r_{bound}=-1 \longrightarrow$ Agent 撞墙

  • $r_{forbid}=-1⟶$$r_{forbid}=-1\longrightarrow$ Agent 进入禁区

  • $r_{target}=+1⟶$$r_{target}=+1 \longrightarrow$ Agent 抵达终点

  • $r=0⟶$$r = 0\longrightarrow$ For all other cases

  以 $(s_1,a_1)$$(s_1, a_1)$ 的 (State, Action) 组合为例子，Reward 用 Conditional Probability 表示为

  $$\begin{array}{rl}p(r=-1|s_1,a_1)& =1\\ p(r\ne -1|s_1,a_1)& =0\end{array}$$

• Stochastic

  现实中一个 Action 对应的 Reward 数值并不会完全固定

  比如努力学习 （这是 Action），考试分数一定会提高（这是 Reward），但提高多少（这是 Reward 的数值）会取决于其它因素

  这种没法写成 Table

• [ Reward Hacking ]

  如果奖励机制设计得很烂，训练出来的 Agent 可能会通过执行 Penalized Action 来最大化 Reward 收益

  比如在本案例中，Agent 可能会故意跨入 Forbidden Cell 抄近道抵达目的地

 

 

1.6 Episode & Trajectory

• Trajectory

  Trajectory 是一条 State-Action-Reward Chain，如下两个例子

  

  对应的两条 Trajectory 为

  $$\begin{array}{rl}\text{Policy 1:}& s_1\underset{r=0}{\overset{a_2}{\to }}{s}_2\underset{r=0}{\overset{a_3}{\to }}{s}_5\underset{r=0}{\overset{a_3}{\to }}{s}_8\underset{r=+1}{\overset{a_2}{\to }}{s}_9\\ \text{Policy 2:}& s_1\underset{r=0}{\overset{a_3}{\to }}{s}_4\underset{r=-1}{\overset{a_3}{\to }}{s}_7\underset{r=0}{\overset{a_2}{\to }}{s}_8\underset{r=+1}{\overset{a_2}{\to }}{s}_9\end{array}$$

• Episode

  有 Terminal State 的 Finite Trajectory 是一个 Episode

  上面的两个 Trajectory 就是两个 Episode

  • Task with Terminal State $⟶$$\longrightarrow$ Episodic Task

  • Task with no Terminal State $⟶$$\longrightarrow$ Continuing Task

  Infinite Trajectory 见 1.7 Return - Discounted Return

 

 

1.7 Return

The sum of all Rewards along the Trajectory，用于评估一个 Policy 的好坏程度

以 1.6 的两个示例为基础，两个 Policy 的 Return 为

Policy 1 的 Return 更大，显然它更好

 

1.7.1 Discounted Return

有时 Policy 在 Agent 抵达目的地后仍然会继续运行，类似于 “动态静止”

如上图，此时这条 Trajectory 从定义上而言，是 Infinite 的

那么 Trajectory 的 Return 就 diverge 了

不止这条，其实从任何起点出发的 Trajectory 的 Return 最后都会因为抵达终点而发散，若 Return 的大小都是无穷，便无法比较 Policy 之优劣，这个衡量标准就失去了意义

所以需要引入一个 Discount Rate $\gamma \in (0,1)$$\gamma \in (0,1)$

无论 Intuitively 还是 Mathematically，引入这个值一定能让 Return 收敛

• $\gamma \to 0$$\gamma\rightarrow0$ Emphasis on Near Future

• $\gamma \to 1$$\gamma\rightarrow1$ Emphasis on Far Future

上面的描述是从 “计算尚未开始” 的角度解释

若从 “计算已经结束” 的角度解释：

• Near Future = 古早历史记录

• Far Future = 近期历史记录

 

1.7.2 Bootstrapping

Consider the following example

Assume the Return obtained from State $s_i$$s_i$ is denoted as $v_i$$v_i$, then

Bootstrapping = Returns rely on each other

类似于 “一直脚踩在另一只脚上，那就能走到无限高处”，概念荒唐但公式本身并不荒唐且可解

够明显了，非齐次线性方程组，四个未知量四个公式，4 个 Return 求出来很容易

 

 

 

2. Markov Decision Process

2.1 Definition

Markov Decision Process (MDP) 是一个 Tuple

where

• State-Transition Probability Matrix

  正如其名，只是把所有的概率全写在一起

  $$\begin{array}{c}\mathcal{P}=p(S_{t+1}|S_t,A_t)\text{where }\{\begin{array}{rl}{S}_{t+1}& \in \mathcal{S}\\ S_t& \in \mathcal{S}\\ A_t& \in \mathcal{A}\end{array}\end{array}$$

  and it holds that $\sum _{s_{t+1}\in \mathcal{S}}p(s_{t+1}|s_t,a_t)=1$$\sum_{s_{t+1}\in \mathcal{S}} p(s_{t+1}|s_t,a_t) = 1$ for any $(s,a)$$(s,a)$

• Reward Function

  可以写成 Probability Distribution

  $$\begin{array}{c}\mathcal{R}\sim p(R_{t+1}|S_t,A_t)\text{where }\{\begin{array}{rl}{R}_{t+1}& \in \mathcal{R}\\ S_t& \in \mathcal{S}\\ A_t& \in \mathcal{A}\end{array}\end{array}$$

  也可以写成 Expectation

  $$\begin{array}{c}\mathcal{R}=\mathbb{E}[R_{t+1}|S_t,A_t]\text{where }\{\begin{array}{rl}{R}_{t+1}& \in \mathcal{R}\\ S_t& \in \mathcal{S}\\ A_t& \in \mathcal{A}\end{array}\end{array}$$

  and it holds that $\sum _{r_{t+1}\mathcal{R}}p(r_{t+1}|s_t,a_t)=1$$\sum_{r_{t+1}\mathcal{R}} p(r_{t+1}|s_t,a_t) = 1$ for any $(s,a)$$(s,a)$

  此处之所以用 $R_{t+1}/r_{t+1}$$R_{t+1} / r_{t+1}$ 是因为倾向于理解为离开状态 $S_t/s_t$$S_t / s_t$ 才能获得 Reward

  如果阁下有不同的想法，比如 “进入 State 时获得 Reward”，事先定义一下，效果是一样的

 

 

2.2 其他特征

• Policy

  $\pi (\mathcal{A}|\mathcal{S})=$$\pi(\mathcal{A}|\mathcal{S}) =$ Probability of chooing Action $\mathcal{A}$$\mathcal{A}$ in State $\mathcal{S}$$\mathcal{S}$

  此处写成一个 Matrix Form

  And it holds that $\sum _{a_t\in \mathcal{A}}p(a_t|s_t)=1$$\sum_{a_t\in\mathcal{A}} p(a_t|s_t) = 1$ for any $s\in \mathcal{S}$$s\in\mathcal{S}$

• Markov Property

  鬼话：The Memoryless property of a stochastic process

  人话：新决策的概率无关于决策的历史记录，MDP无记忆

  $$\begin{array}{c}p(s_{t+1}|s_t,a_t)=p(s_{t+1}|s_t,a_t,s_{t-1},a_{t-1},...,...,s_0,a_0)\\ p(r_{t+1}|s_t,a_t)=p(r_{t+1}|s_t,a_t,s_{t-1},a_{t-1},...,...,s_0,a_0)\end{array}$$

  从数学表达式可以看出，你可以提供很多的过去决策供参考，但是全部木大

  下一个 State / Reward 只会参考现在 的 State & Action！

 

 

2.3 Markov Process

Markov Decision Process becomes Markov Process once the Policy is given

比如 1. 中的 Grid of Cells，左图里描述了采取的 Policy，右侧更加抽象的图就是对应的 Markov Process

 

 

 

3. Bellman Expectation Equation

一般的称谓是 Bellman Equation

 

3.1 State Value 状态价值

“告诉我们从哪个 State 出发最合适”

State Value $v_{\pi }(s)$$v_{\pi}(s)$ is the Expected Return $G_t$$G_t$ the Agent can get starting at State $s$$s$

关于 State Value $v_{\pi }(s)$$v_{\pi}(s)$：

1. $G_t$$G_t$ 有 Expectation 在数学上合理

   此处的 $G_t,R_{t+1},R_{t+2},R_{t+3}$$G_t,R_{t+1},R_{t+2},R_{t+3}$ 均为 Random Variable

   不如说是因为 $R_{t+1},R_{t+2},R_{t+3}$$R_{t+1},R_{t+2},R_{t+3}$ 是 Random Variable，所以作为结果的 $G_t$$G_t$ 也是 Random Variable

2. $G_t$$G_t$ 有 Expectation 在直觉上合理

   以某个 State 为起点寻路，能抵达终点的 Trajectory 可能会有很多条，那么也可能会有多个 Discounted Return

   如果 State-Transition 是完全 Deterministic 的，那么此时以某一个 State 为起点的 Trajectory 必定只有一条，因此有

   $$v_{\pi }=G_t$$

3. State Value 依赖 Policy

   Policy 变了 Trajectory 也会变，这很合理

   所以 State Value 的表达方式改成 $v(\pi ,s)$$v(\pi,s)$ 会更合适

[ Example ]

在 State-Transition 上，左图的 Policy ${\pi }_1$$\pi_1$，Deterministic 的；右图的 Policy ${\pi }_2$$\pi_2$，Stochastic 的

各自以 $s_1$$s_1$ 为起点的 State Value 为

最终结果

 

3.2 Elementwise Form

Bellman Expectation Equation 用于计算 State Value

Consider the following Random Trajectory

其 Discounted Return 为

那么 State Value 公式可作如下处理

分开计算

• "Immediate Reward" Term

  $$\begin{array}{rl}\mathbb{E}[R_{t+1}|S_t=s_t]& =\sum _{a_t}\{\pi (a_t|s_t)\mathbb{E}[R_{t+1}|S_t=s_t,A_t=a_t]\}\\ & =\sum _{a_t}\{\pi (a_t|s_t)\sum _{r_{t+1}}[p(r_{t+1}|s_t,a_t)r_{t+1}]\}\end{array}$$

• "Future Reward"Term

  第二步的 Expectation 部分通过 Markov Property 化简

  $$\begin{array}{rl}\mathbb{E}[G_{t+1}|S_t=s_t]& =\sum _{s_{t+1}}\{\mathbb{E}[G_{t+1}|S_{t+1}=s_{t+1},S_t=s_t]p(s_{t+1}|s_t)\}\\ & =\sum _{s_{t+1}}\{\mathbb{E}[G_{t+1}|S_{t+1}=s_{t+1}]\sum _{a_t}[\pi (a|s_t)p(s_{t+1}|s_t,a_t)]\}\\ & =\sum _{s_{t+1}}\{v_{\pi }(s_{t+1})\sum _{a_t}[\pi (a|s_t)p(s_{t+1}|s_t,a_t)]\}\end{array}$$

两部分合并可得

where

• $v_{\pi }(s_t),v_{\pi }(s_{t+1})⟶$$v_{\pi}(s_t), v_{\pi}(s_{t+1}) \longrightarrow$ State Values to be computed

  with Bootstrapping in 1.7.2

• $\pi (a_t|s_t)⟶$$\pi(a_t|s_t) \longrightarrow$ given Policy

• $p(r_{t+1}|s_t,a_t),p(s_{t+1}|s_t,a_t)⟶$$p(r_{t+1}|s_t,a_t), p(s_{t+1}|s_t,a_t) \longrightarrow$ Environment Models

  1. 当前语境下，这些 Model 是 known 的

  2. 若 Model unknown，那就是 Model-Free RL 的内容了

确认 Policy 和 Environment Models （以及 $\gamma$$\gamma$）的数值后，State Values 就很好求了

略微偷懒一点的写法（公式项的包含关系还是上面的那个更详细）

 

 

3.3 Matrix-Vector Form

3.3.1 Derivation

Elementwise Form 的 BEE 与 State 数量挂钩，即有多少个 State 就会有多少个这样的公式，把它们联立会非常 nice

先对 Elementwise Form 进行修改，退回到 3.2 的 “两部分合并”，第三行

where

• $r_{\pi }(s_t)⟶$$r_{\pi}(s_t) \longrightarrow$ Expectation of Immediate Reward

• $p_{\pi }(s_{t+1}|s_t)⟶$$p_{\pi}(s_{t+1}|s_t)\longrightarrow$ 从 State $s_t$$s_t$ 转到 State $s_{t+1}$$s_{t+1}$ 的概率

更换一下 Notation，使 $s_i=s_t,s_j=s_{t+1}$$s_i = s_t, s_j = s_{t+1}$，那么 BEE for $s_i$$s_i$ 为

然后写出所有 State 对应的上式，联立后得到 Matrix-Vector Form

where

 

3.3.2 Example

Assume $n=4$$n=4$，then

如果 Policy 和 Reward 如下

那么 Matrix-Vector Form 变成

 

3.3.3 How to Solve

• Closed-Form Solution

  好消息是它很简洁很方便，坏消息是涉及 Matrix Inversion，所以大概是用不上了

  $$v_{\pi }=(I-\gamma P_{\pi }{)}^{-1}{r}_{\pi }$$

• Iterative Solution

  坏消息是证明起来很烦，好消息是好理解也很好用

  $$v_{k+1}=r_{\pi }+\gamma P_{\pi }{v}_k$$

  你可以设定 $k=0$$k=0$，然后 Guess 一个 $v_0$$v_0$ 代入上式，得到 $v_1$$v_1$

  不断接替代入就能获得一长串结果 $\{v_0,v_1,v_2,...\}$$\{v_0, v_1, v_2,...\}$，最终会发现

  $$v_k\to v_{\pi }=(I-\gamma P_{\pi }{)}^{-1}{r}_{\pi }\text{as }k\to \mathrm{\infty }$$

  [ Tips ]

  1. 这里用的下标 Notation 是 $k$$k$ 不是 $t$$t$，它和 State 没有关系

  2. 这是一种类似于级数逼近的方法，不用真的算到 $k\to \mathrm{\infty }$$k\rightarrow \infin$

     只需设置一个收敛阈值 $ϵ$$\epsilon$，然后迭代到 $\Vert v_k-v_{\pi }\Vert <ϵ$$\lVert v_k - v_{\pi} \rVert < \epsilon$ 即可

 

 

3.4 Action Value 动作价值

“告诉我们采取 State 中的哪个 Action 最合适”

3.4.1 Definition

Action Value $q_{\pi }(s,a)$$q_{\pi}(s,a)$ is the Expected Return $G_t$$G_t$ the Agent can get starting at State $s$$s$ and taking Action $a$$a$

Action Value 也称 Q-Value

 

3.4.2 与 State Value 的关系

• "Action $\to$$\to$ State"

  Action Value 与 3.1 中定义的 State Value 只差了一个 “选择某个 Action” 的过程

  以下是 State Value 的定义与公式，以供对比：

  State Value $v_{\pi }(s)$$v_{\pi}(s)$ is the Expected Return $G_t$$G_t$ the Agent can get starting at State $s$$s$

  $$v_{\pi }(s)=\mathbb{E}[G_t|S_t=s]$$

  所以 Action Value 与 State Value 的关系式为

  $$\begin{array}{rl}{v}_{\pi }(s)& =\mathbb{E}[G_t|S_t=s]\\ \\ & =\sum _a\{\pi (a|s)\cdot \mathbb{E}[G_t|S_t=s,A_t=a]\}\\ \\ v_{\pi }(s)& =\sum _a[\pi (a|s)\cdot q_{\pi }(s,a)]\end{array}$$

• "State $\to$$\to$ Action"

  与 3.2 的 Elementwise BEE 联立可发现

  $$v_{\pi }(s_t)=\sum _{a_t}\{\pi (a_t|s_t)\cdot \underset{q_{\pi }(s_t,a_t)}{\underbrace{(\sum _{r_{t+1}}[p(r_{t+1}|s_t,a_t)r_{t+1}]+\gamma \sum _{s_{t+1}}[p(s_{t+1}|s_t,a_t)v_{\pi }(s_{t+1})])}}\}$$

  也就是 $q_{\pi }(s_t,a_t)$$q_{\pi}(s_t,a_t)$ 与 $v_{\pi }(s_{t+1})$$v_{\pi}(s_{t+1})$ 存在联系

  $$q_{\pi }(s_t,a_t)=\sum _{r_{t+1}}[p(r_{t+1}|s_t,a_t)r_{t+1}]+\gamma \sum _{s_{t+1}}[p(s_{t+1}|s_t,a_t)v_{\pi }(s_{t+1})]$$

• Summary

  $$\begin{array}{rl}\text{AV to SV:}& v_{\pi }(s_t)=\sum _{a_t}[\pi (a_t|s_t)\cdot q_{\pi }(s_t,a_t)]\\ \\ \text{SV to AV:}& q_{\pi }(s_t,a_t)=\sum _{r_{t+1}}[p(r_{t+1}|s_t,a_t)r_{t+1}]+\gamma \sum _{s_{t+1}}[p(s_{t+1}|s_t,a_t)v_{\pi }(s_{t+1})]\end{array}$$

 

 

 

4. Bellman Optimality Equation

Policy ${\pi }^{\ast }$$\pi^*$ is Optimal if $v_{{\pi }^{\ast }}(s)>v_{\pi }(s)$$v_{\pi^*}(s) > v_{\pi}(s)$ for all States $s$$s$ & all other Policies $\pi$$\pi$

 

4.1 Definition

Bellman Optimality Equation (BOE):

1. 假设我们不知道 Policy $\pi (a_t|s_t)$$\pi(a_t|s_t)$

2. 相比 BEE 前面多了一个最大化的语句

以下是两种 BOE 公式

• Elementwise Form

  $$\begin{array}{rl}{v}_{\pi }(s_t)& =\underset{\pi }{max}\sum _{a_t}\{\pi (a_t|s_t)\cdot (\sum _{r_{t+1}}[p(r_{t+1}|s_t,a_t)r_{t+1}]+\gamma \sum _{s_{t+1}}[p(s_{t+1}|s_t,a_t)v_{\pi }(s_{t+1})])\}\\ \\ & =\underset{\pi }{max}\sum _{a_t}[\pi (a_t|s_t)\cdot q_{\pi }(s_t,a_t)]\end{array}$$

  where

  • $p(r_{t+1}|s_t,a_t),p(s_{t+1}|s_t,a_t)⟶$$p(r_{t+1}|s_t,a_t), p(s_{t+1}|s_t,a_t)\longrightarrow$ Known

  • $v_{\pi }(s_t),v_{\pi }(s_{t+1})⟶$$v_{\pi}(s_t), v_{\pi}(s_{t+1})\longrightarrow$ Unknown, to be Computed

  • $\pi (a_t|s_t)⟶$$\pi(a_t|s_t)\longrightarrow$ Unknown, to be Computed

• Matrix-Vector Form

  此处的 $\underset{\pi }{max}$$\max_{\pi}$ 会 Elementwise 施加在矩阵 $(r_{\pi }+\gamma P_{\pi }{v}_{\pi })$$(r_{\pi} + \gamma P_{\pi}v_{\pi})$ 的每一项上

  $$v_{\pi }=\underset{\pi }{max}[r_{\pi }+\gamma P_{\pi }{v}_{\pi }]$$

 

 

4.2 解法前置理论

4.2.1 Elementwise Form 解

以有 Action Value 的版本为基础

问题可以简化为

Find optimal coefficients $c_1^{\ast },c_2^{\ast },c_3^{\ast }$$c_1^*,c_2^*,c_3^*$ given

为了让 $c_i$$c_i$ 能对应上 $\pi$$\pi$ 的特征，设定 $c_1+c_2+c_3=1$$c_1+c_2+c_3=1$ 且 $c_1,c_2,c_3\ge 0$$c_1,c_2,c_3 \geq 0$

在不失普适性的前提下，若假定 $q_3>q_1,q_2$$q_3 > q_1,q_2$，那么 Optimal Coefficient 应当为

把最大的 Weight 给最大的 Term，就能最大化它们之和

所以回到 BOE 上，可以得出结论

 

4.2.2 Matrix-Vector Form 解

以该形式为基础，要求 $\pi$$\pi$ 和 $v_{\pi }$$v_{\pi}$ 两个变量

类似于是在解如下类型的问题

Find $x,a\in \mathbb{R}$$x,a\in\R$ that satisfies

首先可以确定 $a^2\ge 0$$a^2 \geq 0$，所以在公式的 Maximum 处必有 $a=0$$a = 0$，所以就变成了

说实话我写这一部分的时候都在怀疑是否真的需要写下来，但是为了防止脑子 GaGa 了，还是留个记录吧（恼

 

4.2.3 Contraction Mapping Theorem

• Fixed Point

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

  $$x=f(x)$$

• Contraction Mapping

  $f$$f$ is a contraction mapping if

  $$\Vert f(x_1)-f(x_2)\Vert \le \gamma \Vert x_1-x_2\Vert$$

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

  一个直观的解释是

  

• Contraction Mapping Theorem

  1. Definition

     For any contraction mapping $f$$f$，there exists a unique fixed point $x^{\ast }$$x^*$ such that $x^{\ast }=f(x^{\ast })$$x^* = f(x^*)$

  2. Algorithm

     Define a sequence $\{x_k\}$$\{x_k\}$ where $x_{k+1}=f(x_k)$$x_{k+1} = f(x_k)$，从任意起点 Initial Guess $x_0$$x_0$ 开始不断代入上式，得到 $\{x_0,x_1,...,x_{\mathrm{\infty }}\}$$\{x_0,x_1,...,x_{\infin}\}$，然后...

     $$x_k\to x^{\ast }\text{as}k\to \mathrm{\infty }$$

     Convergence Rate is Exponentially Fast given any Initial Guess，非常好用

  [ Example ]

  Given Contraction Mapping $f(x)=0.5x$$f(x)=0.5x$ where $x\in \mathbb{R}$$x\in\R$

  则迭代公式为

  $$x_{k+1}=0.5x_k$$

  若从 $x_0=10$$x_0 = 10$ 开始，则得到的数列 $\{x_k\}$$\{x_k\}$ 为

  $$x_0=10,x_1=5,x_2=2.5,...,x_{\mathrm{\infty }}=x^{\ast }=0$$

  最后得到 $x^{\ast }=0$$x^* = 0$ 满足 Fixed Point 的结果（虽然实际上可以一眼出答案...）

 

 

4.3 Solution

BOE 的 Matrix-Vector Form 是关于 $v_{\pi }$$v_{\pi}$ 的函数，所以可以有

那么 BOE 就可以写成下面这个贼简洁的公式

[ 重要结论 ]：BOE 的 $f(v_{\pi })$$f(v_{\pi})$ 是一个 Contraction Mapping

具体证明就不说了，但是有个很 Intuitive 的证据，即 $\gamma <0$$\gamma <0$；总之，可以直接套用 4.2.3 Contraction Mapping Theorem 的结论

1. Existence

   一定存在一个 Unique Fixed Point $v_{\pi }^{\ast }$$v_{\pi}^*$ 满足

   $$v_{\pi }^{\ast }=f(v_{\pi }^{\ast })=\underset{\pi }{max}[r_{\pi }+\gamma P_{\pi }{v}_{\pi }^{\ast }]$$

2. Algorithm

   与 4.2.3 中的相同，could be solved iteratively by

   $$\begin{array}{c}{v}_{k+1}=f(v_k)=\underset{\pi }{max}[r_{\pi }+\gamma P_{\pi }{v}_k]\\ \\ v_k\to v^{\ast }\text{as}k\to \mathrm{\infty }\end{array}$$

   Convergence Rate is determined by $\gamma$$\gamma$

 

 

4.4 Policy Optimality & 总结

• State Value

  Assume $v^{\ast }$$v^*$ is the Unique Solution to BOE

  $$v^{\ast }=\underset{\pi }{max}[r_{\pi }+\gamma P_{\pi }{v}^{\ast }]$$

  Assume $v_{\pi }$$v_{\pi}$ is the State Value that satisfies BEE for all Policies $\pi$$\pi$

  $$v_{\pi }=r_{\pi }+\gamma P_{\pi }{v}_{\pi }$$

  Then

  $$v^{\ast }\ge v_{\pi }\mathrm{\forall }\pi$$

• Policy

  $$\begin{array}{rl}{\pi }^{\ast }(a_t|s_t)& =\arg \underset{\pi }{max}[r_{\pi }+\gamma P_{\pi }{v}^{\ast }]\\ \\ & =\arg \underset{\pi }{max}\sum _{a_t}\{\pi (a_t|s_t)\cdot (\sum _{r_{t+1}}[p(r_{t+1}|s_t,a_t)r_{t+1}]+\gamma \sum _{s_{t+1}}[p(s_{t+1}|s_t,a_t)v^{\ast }(s_{t+1})])\}\\ \\ & =\arg \underset{\pi }{max}\sum _{a_t}[\pi (a_t|s_t)\cdot q^{\ast }(s_t,a_t)]\end{array}$$

  For any $s\in \mathcal{S}$$s \in \mathcal{S}$, the Deterministic Greedy Policy

  $$\begin{array}{c}{\pi }^{\ast }(a_t|s_t)=\{\begin{array}{ll}1& a_t=a^{\ast }\\ 0& a_t\ne a^{\ast }\end{array}\end{array}$$

  is an Optimal Policy solving the BOE

  所以其实可以这么表述

  $$v^{\ast }=v_{{\pi }^{\ast }}$$

• Action Value

  $$\begin{array}{rl}{a}^{\ast }& =\arg \underset{\pi }{max}{q}^{\ast }(s_t,a_t)\\ \\ & =\arg \underset{a}{max}(\sum _{r_{t+1}}[p(r_{t+1}|s_t,a_t)r_{t+1}]+\gamma \sum _{s_{t+1}}[p(s_{t+1}|s_t,a_t)v^{\ast }(s_{t+1})])\end{array}$$