系列文章目錄

---

---

前言

本系列文章主要用于記錄 B站 趙世鈺老師的【強化學習的數學原理】的學習筆記，關于趙老師課程的具體內容，可以移步：
B站視頻：【【強化學習的數學原理】課程：從零開始到透徹理解（完結）】
GitHub 課程資料：Book-Mathematical-Foundation-of-Reinforcement-Learning

---

Definition of optimal policy

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

$v_{{\pi }_1}(s)\ge v_{{\pi }_2}(s),?s\in \mathcal{S}$

then ${\pi }_1$ is “better” than ${\pi }_2$.

A policy ${\pi }^{?}$ is optimal if

$v_{{\pi }^{?}}(s)\ge v_{\pi }(s),?s\in \mathcal{S},?\pi .$

---

Bellman optimality equation

Introduction

Bellman optimality equation (elementwise form):

$v(s)={\max }_{\pi }{\sum }_a\pi (a\mid s)\left({\sum }_{r}p(r\mid s,a)r+\gamma {\sum }_{s^{\prime }}p(s^{\prime }\mid s,a)v(s^{\prime })\right),?s\in \mathcal{S}$

$={\max }_{\pi }{\sum }_a\pi (a\mid s)q(s,a),s\in \mathcal{S}$

Remarks:

• $p(r\mid s,a),p(s^{\prime }\mid s,a)$ are known.
• $v(s),v(s^{\prime })$ are unknown and to be calculated.
• $\pi (s)$ is known!

結合 Bellman 方程依賴于已知策略，解釋為什么在 Bellman 最優性方程 里要取 ${\max }_{\pi }$，以及它和最優策略 ${\pi }^{?}$ 的關系

1. 回顧：Bellman 方程（依賴已知策略）

   對于一個固定的策略 $\pi$，狀態價值函數定義為：

   $v_{\pi }(s)={\sum }_a\pi (a\mid s)[{\sum }_{r}p(r\mid s,a)r+\gamma {\sum }_{s’}p(s’\mid s,a)v_{\pi }(s’)]$

   • 這里 $\pi (a|s)$ 是 已知的動作分布，所以 Bellman 方程在這種情況下是 策略評估 (policy evaluation) 工具。
     • 策略 = 對每個狀態 $s$，給所有可能動作 $a$ 分配概率，即一個策略對應了一組“所有狀態的動作概率分布”。
     • 不同策略對應的就是 不同的動作概率分布集合。

       • 策略 ${\pi }_1$：

         在狀態 $s$，可能給動作 $a_1$ 的概率高一些，給動作 $a_2$ 的概率低一些。

       • 策略 ${\pi }_2$：

         在相同狀態 $s$，可能恰好相反，給 $a_1$ 的概率低，給 $a_2$ 的概率高。

2. 從策略依賴到最優性

   • 如果我們不想只評估一個具體策略，而是想找到 最優策略，那就需要考慮：對于每個狀態 $s$，什么樣的動作選擇（或策略）能最大化長期回報？

   • 于是，狀態價值的定義變成：

     $v^{?}(s)={\max }_{\pi }{v}_{\pi }(s),?s\in \mathcal{S}$

   • 這里的 ${\max }_{\pi }$ 表示：在所有可能的策略中，找到一個能使價值函數最大的策略。

3. Bellman 最優性方程

   • 把 ${\max }_{\pi }$ 引入 Bellman 方程，得到：

     $v^{(}s)={\max }_a[{\sum }_{r}p(r\mid s,a)r+\gamma {\sum }_{s’}p(s’\mid s,a)v^{(}s’)]$

   • 關鍵點：

     • 在普通 Bellman 方程里：$\pi (a|s)$ 是已知的分布。
     • 在 Bellman 最優性方程里：我們不固定策略，而是 直接在動作層面取最大化，等價于“選擇最優動作”。
     • 因此，最優價值函數 $v^{?}(s)$ 不再依賴于某個具體的 $\pi$，而是內含了 策略優化的過程。

4. 和最優策略 ${\pi }^{?}$ 的關系

   • 定義：

     ${\pi }^{(}s)=\arg {\max }_a[{\sum }_{r}p(r\mid s,a)r+\gamma {\sum }_{s’}p(s’\mid s,a)v^{(}s’)]$

     即最優策略就是在每個狀態下選擇能使未來回報最大的動作。

   • 換句話說：

     • 普通 Bellman 方程 = 已知策略的價值評估。
     • Bellman 最優性方程 = 在所有策略中選擇最優的價值函數，從而定義了最優策略。

Bellman optimality equation (matrix-vector form):

$v={\max }_{\pi }(r_{\pi }+\gamma P_{\pi }v)$

where the elements corresponding to $s$ or $s^{\prime }$ are

$[r_{\pi }{]}_s?{\sum }_a\pi (a\mid s){\sum }_{r}p(r\mid s,a)r,$

$[P_{\pi }]s,s^{\prime }=p(s^{\prime }\mid s)?{\sum }_a\pi (a\mid s)\sum s^{\prime }p(s^{\prime }\mid s,a)$

Here ${\max }_{\pi }$ is performed elementwise.

Maximization on the right-hand side

Solve the Bellman optimality equation

必須先考慮右邊的式子，即先有某個最優策略 $\pi$，然后才有最優的狀態價值 $v(s)$

• elementwise form

  $v(s)={\max }_{\pi }{\sum }_a\pi (a\mid s)\left({\sum }_{r}p(r\mid s,a)r+\gamma {\sum }_{s^{\prime }}p(s^{\prime }\mid s,a)v(s^{\prime })\right),?s\in \mathcal{S}$

  • Fix $v^{\prime }(s)$ first and solve $\pi$:

    $v(s)={\max }_{\pi }{\sum }_a\pi (a\mid s)q(s,a)$

  • Inspired by the above example, considering that ${\sum }_a\pi (a\mid s)=1$, we have

    ${\max }_{\pi }{\sum }_a\pi (a\mid s)q(s,a)={\max }_{a\in \mathcal{A}(s)}q(s,a),$

  • where the optimality is achieved when

    $\pi (a\mid s)=\{\begin{array}{ll}1,& a=a^{?}\\ 0,& a\ne a^{?}\end{array}$

  • where $a^{?}=\arg {\max }_{a}q(s,a)$.

• matrix-vector form

  $v={\max }_{\pi }(r_{\pi }+\gamma P_{\pi }v)$

  • Let

    $f(v):={\max }_{\pi }(r_{\pi }+\gamma P_{\pi }v).$

  • Then, the Bellman optimality equation becomes

    $v=f(v)$

  • where

    $[f(v)]s=\max \pi {\sum }_a\pi (a\mid s)q(s,a),s\in \mathcal{S}.$

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 $\Vert f(x_1)?f(x_2)\Vert \le \gamma \Vert x_1?x_2\Vert$, 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 \infty$ hold.
• Here $\Vert ?\Vert$ can be any vector norm.

Contraction mapping theorem

For any equation that has the form of $x=f(x)$, if $f$ is a contraction mapping, then

• Existence: There exists a fixed point $x^{?}$ satisfying $f(x^{?})=x^{?}$.
• Uniqueness: The fixed point $x^{?}$ is unique.
• Algorithm: Consider a sequence {xk}\{x_k\}{xk?} where $x_{k+1}=f(x_k)$, then $x_k\to x^{?}$ as $k\to \infty$. Moreover, the convergence rate is exponentially fast.

Solution

Let’s come back to the Bellman optimality equation:

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

Contraction Property:

• $f(v)$ is a contraction mapping satisfying

  $\Vert f(v_1)?f(v_2)\Vert \le \gamma \Vert v_1?v_2\Vert$

• where $\gamma$ is the discount rate!

Existence, Uniqueness, and Algorithm:

• For the BOE $v=f(v)={\max }_{\pi }(r_{\pi }+\gamma P_{\pi }v)$, there always exists a solution $v^{?}$ and the solution is unique. The solution could be solved iteratively by

  $v_{k+1}=f(v_k)={\max }_{\pi }(r_{\pi }+\gamma P_{\pi }{v}_k)$

• This sequence {vk}\{v_k\}{vk?} converges to $v^{?}$ exponentially fast given any initial guess $v_0$. The convergence rate is determined by $\gamma$.

Optimality

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

$v^{?}={\max }_{\pi }(r_{\pi }+\gamma P_{\pi }{v}^{?})$

Suppose

${\pi }^{?}=\arg {\max }_{\pi }(r_{\pi }+\gamma P_{\pi }{v}^{?})$

Then

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

Therefore, ${\pi }^{?}$ is a policy and $v^{?}=v_{{\pi }^{?}}$ is the corresponding state value.

Policy Optimality

• Suppose that $v^{?}$ 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^{\ge }{v}_{\pi },?\pi$

Greedy Optimal Policy

• For any $s\in \mathcal{S}$, the deterministic greedy policy

  ${\pi }^{(}a\mid s)=\{\begin{array}{ll}1,& a=a^{(}s)\\ 0,& a\ne a^{(}s)\end{array}$

• is an optimal policy solving the BOE. Here,

  $?a^{(}s)=\arg {\max }_a{q}^{(}s,a),?$

• where $q^{(}s,a):={\sum }_{r}p(r\mid s,a)r+\gamma {\sum }_{s^{\prime }}p(s^{\prime }\mid s,a)v^{?}(s^{\prime })$

• Proof

  ${\pi }^{(}s)=\arg {\max }_{\pi }{\sum }_a\pi (a\mid s)\left({\sum }_{r}p(r\mid s,a)r+\gamma {\sum }_{s^{\prime }}p(s^{\prime }\mid s,a)v^{(}{s}^{\prime })\right)$

對公式的概括

1. $v^{?}$ 的意義

   • $v^{?}$ 是一個“理想值表”，它告訴你：從每個狀態出發，如果以后一直做出最優選擇，能拿到的總回報是多少。

   • 它滿足一個自洽的關系式（Bellman 最優性方程）：

     $v^{?}(s)={\max }_a[\text{即時獎勵}+\gamma \times \text{未來價值}]$

2. ${\pi }^{?}$ 的意義

   • ${\pi }^{?}$ 是“最優策略”，它規定了：在每個狀態下應該采取哪個動作，才能保證總回報不比任何其他策略差。
   • 從公式上看，${\pi }^{?}$ 就是選擇能讓 $v^{?}$ 達到最大的那個動作（也就是“貪心選擇”）。

3. Policy Optimality 定理

   • 對于任意其他策略 $\pi$，它的價值函數 $v_{\pi }$ 都不會超過 $v^{?}$。
   • $v^{?}$ 是所有策略里能實現的最高水平，它一定支配所有其他策略的價值表。

4. Greedy Optimal Policy 定理

   • 只要你已經有了 $v^{?}$，那么直接在每個狀態里“選那個讓回報最大化的動作”就能得到 ${\pi }^{?}$。
   • 最優策略其實就是“貪心地”選動作，但前提是這個貪心是基于正確的 $v^{?}$。

更進一步的解釋

1. 為什么要先有 $v^{?}$ 才能得到 ${\pi }^{?}$？
   • 因為 ${\pi }^{?}$ 的定義依賴于“未來回報”，而未來回報就是由 $v^{?}$ 描述的。
   • 一旦知道了 $v^{?}$，最優策略就能“順理成章”地通過貪心法則推出來。
2. 為什么 $v^{?}$ 比任何 $v_{\pi }$ 都大？
   • $v_{\pi }$ 是“固定策略下”的表現。
   • $v^{?}$ 是在每一步都挑選最優動作的表現。
   • 顯然，如果你隨時都能選最好的動作，你的表現不可能比其他任何固定策略差。
3. 為什么貪心策略一定最優？
   • 因為 Bellman 方程已經保證了：在 $v^{?}$ 下，每個狀態的最優價值都等于“選擇最優動作”得到的回報。
   • 所以只要你在每個狀態都執行這個“最優動作”，整個過程的價值函數自然等于 $v^{?}$。
   • 也就是說：貪心 + 正確的價值表 = 全局最優策略。

Analyzing optimal policies

What factors determine the optimal policy?

• It can be clearly seen from the BOE

  $v(s)={\max }_{\pi }{\sum }_a\pi (a\mid s)\left({\sum }_{r}p(r\mid s,a)r+\gamma {\sum }_{s^{\prime }}p(s^{\prime }\mid s,a)v(s^{\prime })\right)$

• that there are three factors:

  • Reward design: $r$
  • System model: $p(s^{\prime }\mid s,a),p(r\mid s,a)$
  • Discount rate: $\gamma$

• In this equation, $v(s),v(s^{\prime }),\pi (a\mid s)$ are unknowns to be calculated.

Optimal Policy Invariance

• Consider a Markov decision process with $v^{?}\in {\mathbb{R}}^{|\mathcal{S}|}$ as the optimal state value satisfying

  $v^{?}={\max }_{\pi }(r_{\pi }+\gamma P_{\pi }{v}^{?}).$

• If every reward $r$ is changed by an affine transformation to $ar+b$, where $a,b\in \mathbb{R}$ and $a\ne 0$, then the corresponding optimal state value $v^{\prime }$ is also an affine transformation of $v^{?}$:

  $v^{\prime }=a{v}^{?}+\frac{b}{1?\gamma }1,$

  • where $\gamma \in (0,1)$ is the discount rate and $1=[1,\dots ,1{]}^T$.

• Consequently, the optimal policies are invariant to the affine transformation of the reward signals.

---

總結

Bellman 最優性方程刻畫了在所有策略中選擇最優策略的價值函數，它保證存在唯一的最優狀態價值 $v^{?}$，并且通過對每個狀態下的動作取最大化（貪心原則）即可導出最優策略 ${\pi }^{?}$，同時最優策略的性質只依賴于獎勵設計、環境轉移模型和折扣因子，而對獎勵的仿射變換保持不變。