---
image: https://i.imgur.com/8OKQQF3.png
---

Reinforcement Learning（增強學習）整理
===

整理者：張頌宇


:::spoiler 文章目錄
[TOC]
:::

建議（錦囊）
---
- RL 特性
- 需要大量樣本（有時是數百萬筆互動資訊）
- Digital Twins：在模擬環境訓練，再到真實環境修正
- 需要非常大量運算
- 訓練的不穩定性（尤其是 DDPG，所以才有 TD3 改良）
- 超參數難調（可以利用超參數最佳化工具）
- 通用性（可以是 Model-Free）
- [Which algorithm should I use?](https://stable-baselines3.readthedocs.io/en/master/guide/rl_tips.html#which-algorithm-should-i-use)
- 離散動作
- 狀態、動作很少：[Q-Learning](#Q-Learning)（建 Q-Table）
- 限單工：[DQN](#Q-Learning) 系列（較慢但可用較少 sample）
- 可多工：[Actor-Critic](#Actor-Critic-Methods（AC）) 系列（[PPO](#PPO（Proximal-Policy-Optimization）)）
- 連續動作
- 限單工：[DDPG](#Deterministic-Policy-Gradient-Methods) 系列（[SAC](#SAC（Soft-Actor-Critic）)、[TD3](#TD3（Twin-Delayed-Deep-Deterministic-policy-gradient-algorithm）)、[TQC](#TQC（Truncated-Quantile-Critics）)）
- 可多工：[Actor-Critic](#Actor-Critic-Methods（AC）) 系列（[PPO](#PPO（Proximal-Policy-Optimization）)、[TRPO](#TRPO（Trust-Region-Policy-Optimization）)）
- 有目標設定：用 [HER](#HER（Hindsight-Experience-Replay）) 當 Replay Buffer
- [Reward 稀少](#Sparse-Reward-的情況)：[Exploration](#Exploration2)
- 沒有 Reward：[GAIL](#Inverse-Reinforcement-Learning（IRL）) 系列
- 多 Agents：[MARL](#Multi-Agent-Reinforcement-Learning（MARL）)、[MAIL](#MAIL（Multi-Agent-Imitation-Learning）)
- 用 RL 硬 Train 一發（目標函數不可微分時）：[RL、ES、ARS](#Reinforcement-Learning（增強學習，RL）)
- [Hyperparameter Tuning](https://github.com/DLR-RM/rl-baselines3-zoo#hyperparameter-tuning)
- 參考：[RL Baselines3 Zoo 的 hyperparams_opt.py](https://github.com/DLR-RM/rl-baselines3-zoo/blob/master/utils/hyperparams_opt.py)
- 用像是 [Optuna](https://optuna.org/) 的工具來選擇最佳的超參數（hyperparameter）
- [Tips and Tricks when creating a custom environment](https://stable-baselines3.readthedocs.io/en/master/guide/rl_tips.html#tips-and-tricks-when-creating-a-custom-environment)
- 將觀察資料（observation space）標準化（normalize）
- 有一些遊戲畫面可以用 stacked frames
- 將連續動作標準化（normalize）到 [-1, 1] 之間
- 在一開始時獎勵盡量訂的細一點
- 先試著跑跑看隨機的動作 Action，看環境有沒有問題
- 環境要符合馬可夫鏈的假設
- 要把因為超時的終止分開處理、提供額外資訊
- [Tips and Tricks when implementing an RL algorithm](https://stable-baselines3.readthedocs.io/en/master/guide/rl_tips.html#tips-and-tricks-when-implementing-an-rl-algorithm)
- 先試簡單的環境，然後注意要把因為超時的終止分開處理
- Continuous Actions（連續動作）
- 易：Pendulum (easy to solve)
- 中：HalfCheetahBullet (medium difficulty with local minima and shaped reward)
- 難：BipedalWalkerHardcore (if it works on that one, then you can have a cookie)
- Discrete Actions（離散動作）
- 易/難：CartPole-v1 (easy to be better than random agent, harder to achieve maximal performance)
- 易：Pong (one of the easiest Atari game)
- 中：LunarLander
- other Atari games (e.g. Breakout)
- 其他建議
- CartPole-v0
- InvertedPendulum-v0
- FrozenLake-v0
- HalfCheetah-v2
- PongNoFrameskip-v4
- BipedalWalker-v3
- 心法
- 未知機率分佈：用 sample 的（期望值就是在算樣本平均）
- 用 KL-Divergence 衡量兩個機率分佈是否相似
- 原因：希望 sample 或生成的機率分佈和真實的越接近越好
- 方法：算機率分佈對應的編碼長度（平均位元長度）
- 也可以考慮其他像是 JS-Divergence、Wasserstein Distance
- 當要建 Table 儲存對應關係，但是範圍太大的時候，就用 NN
- 當最佳化問題不可微分的時候，用 RL 硬 Train 一發
- RL 常常跟 GAN 有關聯，而且都很難 Train
- 工具使用：
- 環境建造：[OpenAI Gym](https://www.gymlibrary.ml/)
- 單機訓練應用：[Stable Baselines3](https://github.com/DLR-RM/stable-baselines3)
- 大規模訓練應用：[RLlib: Industry-Grade Reinforcement Learning](https://docs.ray.io/en/latest/rllib/index.html)
- 程式碼參考：
- [OpenAI - Spinning Up](https://github.com/openai/spinningup)
- [Stable Baselines3](https://github.com/DLR-RM/stable-baselines3)
- [PnPAI - Plug and Play AI Toolkits](https://github.com/timcsy/PnPAI)

[回目錄](#Reinforcement-Learning（增強學習）整理)

學習資源
---
### 教學影片
- 李宏毅
- [李宏毅 Deep Reinforcement Learning, 2018](https://hackmd.io/@shaoeChen/Bywb8YLKS)
- [Deep Reinforcement Learning, 2018 影片](https://www.youtube.com/playlist?list=PLJV_el3uVTsODxQFgzMzPLa16h6B8kWM_)
- 理論較多，實作可參考
- [2021 李宏毅 Introduction of Deep Reinforcement Learning (RL)](https://speech.ee.ntu.edu.tw/~hylee/ml/ml2021-course-data/drl_v5.pdf)
- [Machine Learning (2021) Mandarin Version](https://www.youtube.com/playlist?list=PLJV_el3uVTsMhtt7_Y6sgTHGHp1Vb2P2J)
- 觀念較多
- [莫煩 - 强化学习](https://mofanpy.com/tutorials/machine-learning/reinforcement-learning/)
- 有附實作

### 文章
- [Documents - Spinning Up in Deep RL](https://spinningup.openai.com/en/latest/)
- 整理了超多好多西！還有心法！！還有論文！！！
- [白话强化学习](https://www.zhihu.com/column/c_1215667894253830144)
- 如果想秒懂 RL，推，而且可以融會貫通
- [Lilian Weng’s blog](https://lilianweng.github.io/)
- 觀念講的非常完整，推薦這作者
- [剖析深度學習系列](https://www.ycc.idv.tw/category/aiml.html)
- 很多基礎的觀念建立

[回目錄](#Reinforcement-Learning（增強學習）整理)

工具
---
- [OpenAI Gym](https://www.gymlibrary.ml/)
- 提供很多小遊戲
- [OpenAI - Spinning Up](https://github.com/openai/spinningup)
- 由淺入深，幫助初學者進入狀況，不過有簡化一些東西（影響不大）
- [Documents - Spinning Up in Deep RL](https://spinningup.openai.com/en/latest/)
- 這文件超級棒！整理了超多好多西！！！裡面提供的心法很好
- [Stable Baselines3](https://github.com/DLR-RM/stable-baselines3)
- 首推，好用的 RL 工具包
- [Stable-Baselines3 Docs - Reliable Reinforcement Learning Implementations](https://stable-baselines3.readthedocs.io/en/master/)
- 裡面提供的建議很好
- [RLlib: Industry-Grade Reinforcement Learning](https://docs.ray.io/en/latest/rllib/index.html)
- 集成很多 RL 算法，不過不太適合單一機器
- 在擴大規模時適用
- [Unity ML-Agents Toolkit](https://github.com/Unity-Technologies/ml-agents)
- Unity 官方提供
- [Unity ML-Agents Toolkit Documentation](https://github.com/Unity-Technologies/ml-agents/blob/main/docs/Readme.md)
- [ML-Agents 閱讀筆記](https://hackmd.io/@timcsy/ML-Agents)
- [PnPAI - Plug and Play AI Toolkits](https://github.com/timcsy/PnPAI)
- 自我練習
- [Plug and Play AI（PnPAI）](https://hackmd.io/@timcsy/PnPAI)

[回目錄](#Reinforcement-Learning（增強學習）整理)

分類與觀念整理
---
- [你有一份强化学习线路图，请查收。(原题：看我如何一文从马可洛夫怼到DPPO)](https://zhuanlan.zhihu.com/p/111869532)
- [A (Long) Peek into Reinforcement Learning](https://lilianweng.github.io/posts/2018-02-19-rl-overview/)

[回目錄](#Reinforcement-Learning（增強學習）整理)

基本觀念
---

Environment：環境

Agent：智能體（決策者）

用 Agent 與 Environment 互動來學習

### 馬可夫鏈 / 馬可夫過程（Markov Chain）

描述一連串可能的事件，建構出的機率分佈模型


==假設：一個狀態只跟「前一個狀態」相關==（Marcovian Property）

因為只有因果關係，所以可以簡化許多！

$P(s_{t+1}|s_t) = P(s_{t+1}|s_t)$
$P(s_{t+2}|s_t,s_{t+1}) = P(s_{t+2}|s_{t+1})$
$P(s_{t+3}|s_t,s_{t+1},s_{t+2}) = P(s_{t+3}|s_{t+2})$


換句話說，環境沒有長期的記憶。

### MDP（Markov Decision Process，馬可夫決策過程）

描述狀態轉換，是一個馬可夫過程，符合馬可夫假設

$s$：狀態 State
$a$：動作 Action
$r$：獎勵 Reward
$t$：時間 Time，$t=T$ 是指 terminate（終止）
$P(s_{t+1}|s_t,a_t)$：環境狀態轉移機率分佈


有些文獻會有 Option $o$（一連串 Action 的組合，暫時翻譯為「動作組」）：
- 論文：[Between MDPs and semi-MDPs: A framework for temporal abstraction in reinforcement learning](https://pdf.sciencedirectassets.com/271585/1-s2.0-S0004370200X00549/1-s2.0-S0004370299000521/main.pdf)

與其說是「鏈」，不如說是「樹」

### Policy（決策）

Policy 由 Agent 給出，分為隨機性或決定性

- Stochastic Policy（隨機性的決策）
- 通常 RL 中 action 不是挑最大的執行，而是用機率分佈 sample
- 記為 $a_t \sim \pi(a|s_t)$
- Deterministic Policy（決定性的決策）
- 記為 $a_t = \mu(s_t)$

### Return（報酬 / 累積獎勵）Gt

$\displaystyle G_t = r_t + \gamma G_{t+1} = r_t + \gamma r_{t+1} + \gamma^2 r_{t+2} + ... + \gamma^{T-1-t} r_{T-1} = \sum_{k=0}^{T-1-t} \gamma^k r_{t+k}$

由時間點 $t$ 開始「累積」到最後（$t=T$，terminal state）的獎勵

Discount factor $\gamma$：因為距離遠的 reward 影響對現在影響較小
- 先試 $\gamma$ = 0.99～0.9

不同文獻 reward 的編號會略有不同，不變的是：
- discount factor $\gamma$ 一開始一律是 0 次方，也就是 1
- 第一個 reward 是第一個 action 帶出來的 reward

### Bellman Equation：用 V(s) & Q(s,a) 估計累積獎勵

Value Function $V(s)$：

Given $s$ 下 $G_t$（Return）的期望值，或叫做 V 值。

也就是在狀態 $s$ 下，估算應有的累積獎勵 $G_t$。

$V(s) = E[G_t|s_t=s]$

$\quad\quad = E[r_t + \gamma r_{t+1} + \gamma^2 r_{t+2} + ... + \gamma^{T-1-t} r_{T-1}|s_t=s]$

$\quad\quad = E[r_t + \gamma V(s')|s_t=s]$

$\displaystyle \quad\quad = \sum_a \pi(a|s) \sum_{s'} P(s'|s,a)[r(s,a)+\gamma V(s')]$

Action-Value Function $Q(s,a)$：

Given $s,a$ 下 $G_t$（Return）的期望值，或叫做 Q-Function、Q-Value、Q 值。

也就是在狀態 $s$ 下，指定要做 $a$ 這個 action，估算應有的累積獎勵 $G_t$。

$Q(s,a) = E[G_t|s_t=s,a_t=a]$

$\quad\quad = E[r_t + \gamma r_{t+1} + \gamma^2 r_{t+2} + ... + \gamma^{T-1-t} r_{T-1}|s_t=s,a_t=a]$

$\quad\quad = E[r_t + \gamma V(s')|s_t=s,a_t=a]$

$\displaystyle \quad\quad = \sum_{s'} P(s'|s,a)[r(s,a)+\gamma V(s')]$


$V(s)$ 就是 $Q(s,a)$ 對 $a$ given $s$ 的期望值：

$\displaystyle V(s) = E_{a \sim \pi(a|s)}[Q(s,a)] = \sum_a \pi(a|s) Q(s,a)$

#### Bellman Optimality Equation（貪婪法）

Bellman Equation 算期望值，Action $a \sim \pi(a|s)$
Bellman Optimality Equation 算最大值， Action $a = \pi^*(s) = arg\max\limits_a Q^*(s,a)$

$V^*(s) = \max\limits_a Q^*(s,a) = \max\limits_a E[r_t+\gamma V^*(s_{t+1})|s_t=s,a_t=a]$

$Q^*(s,a) = E[r_t+\gamma V^*(s_{t+1})|s_t=s,a_t=a] = E[r_t+\gamma \max\limits_{a'} Q^*(s',a')|s_t=s,a_t=a]$


#### 小結：Bellman Equation 就是指 $V$ 和 $Q$
- $V$ 就是子節點的 $Q$ 的期望值！但要注意 $V$ 值和策略 $\pi$ 相關
- $V^\pi(s) = E_{a \sim \pi(a|s)}[Q(s,a)] = E[r_t+ \gamma V^\pi(s_{t+1})|s_t=s]$
- $Q$ 就是子節點的 $V$ 的期望值！但要注意，記得把 $r$ 計算在内
- $Q^\pi(s,a) = E[r_t+ \gamma V^\pi(s_{t+1})|s_t=s,a_t=a]$
- $r_t$ 本身是隨機變數

[回目錄](#Reinforcement-Learning（增強學習）整理)

遍歷（Search）/ 取樣（Sample）
---
動態規劃、蒙地卡羅、Temporal Difference（TD） 之間的關係


### Dynamic Programming（動態規劃，DP）

條件：==已知==機率分佈 $P(s'|s,a)$，只看一層（只走一步）

分成 Value Iteration 與 Policy Iteration

參考：[Lecture 3: Planning by Dynamic Programming](https://www.davidsilver.uk/wp-content/uploads/2020/03/DP.pdf)



參考：[策略迭代与值迭代的区别](https://blog.csdn.net/panglinzhuo/article/details/77752574)

通常無法知道機率分佈 $P(s'|s,a)$

### Reinforcement Learning（增強學習，RL）

條件：==未知==機率分佈 $P(s'|s,a)$

原則：用 ==sample（取樣）== 的！
- 蒙地卡羅（Monte Carlo，MC）：取樣幾條路，而且一路走到底
- Temporal Difference（TD）：取樣幾條路，但只走一步

#### Model-based RL
- Monte Carlo Tree Search (MCTS，蒙地法羅樹搜索)
- Model Predictive Control (MPC)

#### Model-free RL
- 大部分 RL 方法屬於這類
- Value-based：主要模型的輸出是 Value
- MC、TD、Q-Learning、DQN 等等
- 容易實作，收斂較快，off-policy，樣本不用太多
- 不適用於 Continuous Action
- Policy-based：主要模型的輸出是 Action
- Policy Gradient 等等
- 較難收斂
- 可以處理 Continuous Action
- 延伸出 Actor-Critic
- 加入了 Network 來估算 Value
- 延伸出 TRPO、PPO
- Deterministic Policy Gradients：用 Generator 生成 Action
- DDPG、TD3、TQC、SAC 等等
- 延伸自 Value-based
- 加入了 Generator 來產生 Action
- 可以解決 Value-based Continuous Action 的問題
- DDPG 跟 GAN 一樣難 Train
- Evolutionary Algorithms（EA，進化式演算法）
- 用演化的角度來做，不同於傳統基於 MDP 的方法
- 論文：
- [Evolution Strategies as a Scalable Alternative to Reinforcement Learning（ES）](https://arxiv.org/pdf/1703.03864.pdf)
- [Simple random search provides a competitive approach to reinforcement learning（ARS）](https://arxiv.org/pdf/1803.07055.pdf)
- 像是基因演算法
- 在「用 RL 硬 Train 一發」時常常使用 ES 的技術

附註：「==用 RL 硬 Train 一發==」的使用時機是遇到 Optimizaion 問題不可解的時候，像是 Loss Function 無法微分，就可以把前面的 Network（像是 Decoder）當 Agent，reward 設成負的 Loss Function 值。

[回目錄](#Reinforcement-Learning（增強學習）整理)

機器學習基礎
---

目的：找一個函數（機率分佈模型）

### 資訊理論（Information Theory）

衡量機率分佈像不像的基礎

#### Self-Information（自編碼）$I(x)$

- 對事件的==機率==做==編碼==之後的==位元長度==
- $I(x) = -\log p(x)$
- 資訊量 ＝ 資訊位元數 $\times$ 位元長度
- 如果是以 2 為底，位元長度的單位是位元（bit），如果是以 $e$ 為底，位元長度的單位是納特（nat）
- 直觀原理：
- 把機率（0 ~ 1）連續映射到長度（0 ~ $\infty$）
- 用 exponential 相關的函數可以處理這方面的問題
- 但是要挑哪一個角度？
- $I(x)=1-\log(-p(x))$
- $I(x)=-\log(p(x))$
- 機率越大的事件可以用比較短的長度來編碼
- $p(x)=1$ 時，極端值 $I(x)=0$
- 機率越小的事件攜帶的資訊量大
- $p(x)=0$ 時，極端值 $I(x)=\infty$
- 對獨立事件有可加性
- 對人類而言加法比乘法還直觀
- $\log$ 把乘法變加法
- 維基：[資訊本體](https://zh.wikipedia.org/zh-tw/%E8%87%AA%E4%BF%A1%E6%81%AF)

#### Entropy（熵 / 亂度）$H(p)$
- Entropy 是 Self-Information $I(x)$ 的期望值（編碼後的==平均位元長度==）
- $H(p) = E_{x \sim p}[-\log p(x)]$
- 或寫為 $H(X) = -E[\log p_X(x)]$
- 期望的資訊量 ＝ 資訊位元數 $\times$ Entropy
- 例子：英語有26個字母，每個字母的訊息量為 4.7 bits
- 我們稱英文字母的 Entropy（編碼後的平均位元長）為 4.7 bits
- 維基：[熵 (資訊理論)](https://zh.wikipedia.org/zh-tw/%E7%86%B5_(%E4%BF%A1%E6%81%AF%E8%AE%BA))
- 內含假設
- 與機率分佈內的順序無關
- 在機率大於 0 時==連續==
- ==獨立可加性==
- 巨觀與微觀等價（大範圍是小範圍對機率的加權平均）
- 像是可以對每個班級進行計算與對個人進行計算是一樣的
- （歸一化，讓位元長度的單位是 bit）
- 與基準分佈互相呈比例對稱的兩個局部分佈差異會互相抵消
- 論文：[On Measures of Entropy and Information](https://digitalassets.lib.berkeley.edu/math/ucb/text/math_s4_v1_article-27.pdf)
- [Joint Entropy](https://en.wikipedia.org/wiki/Joint_entropy)（聯合熵）$H(X,Y)$
- 聯集的概念
- $H(X,Y) = E[-\log p(x,y)]$
- $\max\{H(X),H(Y)\} \le H(X,Y) \le H(X) + H(Y)$
- 完全相依到完全獨立
- 注意，這個不是 Cross Entropy $H(p,q)$！
- [Conditional Entropy](https://en.wikipedia.org/wiki/Conditional_entropy)（條件熵）$H(Y|X)$
- 差集的概念
- 已知 $X$ 的前提下，$Y$ 的 Entropy（不確定性）還有多少
- $H(Y|X) = E[-\log p_{Y|X}(y|x)]$
- 應用：資料壓縮（$X$ 是預先約定好的編碼）
- [Mutual information](https://en.wikipedia.org/wiki/Mutual_information)（相互資訊） $I(X;Y)$
- 兩個變數之間相互依賴的程度，交集的概念
- 很低代表越獨立，知道一個的資訊並不能帶來另一個的資訊
- 很高代表越相依，知道一個的資訊大致能帶來另一個的資訊
- $I(X;Y) = D_{KL}(p_{X,Y}\|p_X \otimes p_Y)$，$\otimes$ 代表機率分佈相乘
- 廣義的熵：[Rényi entropy](https://en.wikipedia.org/wiki/R%C3%A9nyi_entropy)（瑞麗熵）$H_\alpha (p)$
- $\displaystyle H_\alpha (X) = - \log \big(E[p_X(x)^{\alpha-1}]\big)^{\frac{1}{\alpha-1}} = \frac{\alpha}{1-\alpha} \log \big(\|p_X\|_\alpha\big)$, where $\alpha \ge 0 \ and\ \alpha \neq 1$
- $\displaystyle H_1(X) = H(X) = -E[\log p_X(x)]$，稱為 Shannon Entropy（夏農熵）
- ==Shannon Entropy== 特別之處：可以在條件機率上定義 ==Chain Rule==
- $H(X,Y) = H(X|Y) + H(Y) = H(Y|X) + H(X)$
- $H(X) = H(X|Y) + I(X;Y)$
- $H(Y) = H(Y|X) + I(X;Y)$
- $I(X;Y) = H(X,Y) - H(X|Y) - H(Y|X)$
- 貝氏定理：$H(Y|X) = H(X|Y) + H(Y) - H(X)$
- 連續機率分布的 Entropy
- [Differential entropy](https://en.wikipedia.org/wiki/Differential_entropy)
- $\displaystyle h(X) = E[-log(f(X))] = -\int f(x)\log(f(x))dx$
- 直接把原本離散的定義換成連續的
- 會出問題：有一些無法保存的性質
- 變數變換後 Entropy 會改變
- 如果機率密度函數大於 1，Entropy 可能為負值
- 例子：$[0,\frac{1}{2}]$ 上的 Uniform distribution
- 不變的性質
- KL-Divergence（Relative Entropy）性質不變
- [Limiting density of discrete points（LDDP）](https://en.wikipedia.org/wiki/Limiting_density_of_discrete_points)
- 從離散去逼近連續，可以解決上述問題
- 引入 $m(x)$：[Invariant measure](https://en.wikipedia.org/wiki/Invariant_measure)
- 
- 離散時是 uniform distribution
- 連續的時候加入這個可以解決 log 內不能有單位的問題
- 
- 如果只考慮最佳化的情境，$\log(N)$ 可以省略
- 常見的定義：$H(X) = -D_{KL}(p\|m)$
- 這就是為何在連續時 Maximum Entropy 實際上是最小化 KL-Divergence 的原因，或是說 Principle of Maximum Entropy（最大熵原理）是 Principle of minimum discrimination information（最小判別資訊原則）的一個特例（初始時採用 uniform distribution，也就是完全不做任何假設）
- 如果 $m(x)$ 在兩個有相同 support 的分佈不變，那 $H(X)$ 和 $h(X)$ 只差一個常數，換句話說，在最佳化上無法區分

#### Cross Entropy（交叉熵）$H(p,q)$
- ==用機率分佈 $q(x)$ 去編碼機率分佈 $p(x)$==
- $H(p,q) = E_{x \sim p}[-\log q(x)]$
- Cross Entropy $H(p,q)$ 的==下界==是 Entropy $H(p)$
- $H(p,q) = E_{x \sim p}[-\log q(x)] \ge E_{x \sim p}[-\log p(x)] = H(p,p) = H(p)$
- $H(p)$ 是機率分布 $p(x)$ 無損編碼的==最小平均位元長==（下界）
- Shannon（夏農）提出，用 Jensen's Inequality 證明
- 與 Conditional Entropy $H(Y|X)$ 相異之處
- $H(p_X,p_Y)$ 又寫成 $H_X(Y)$
- $H(Y|X)$ 是從 joint distribution sample
- 算條件機率的期望值
- $H_X(Y)$ 是從 marginal distribution sample
- 算 marginal distribution 的期望值
- 維基：[Conditional Entropy](https://en.wikipedia.org/wiki/Cross_entropy)

#### Divergence（統計學中的散度）$D(p,q)$
- 衡量==機率分佈==是否==相似==
- 想像成是統計學中機率分佈的「距離」（不全然是，概念類似）
- 延伸自平方後的歐式距離
- 非負：$D(p,q) \ge 0\ for\ all\ p,q$
- 相等：$D(p,q) = 0\ if\ and\ only\ if\ p = q$
- 可以在每個（微分流形上的）點上面定義黎曼度量張量
- 不保證對稱性
- 定義 dual divergence $D^*(p,q) = D(q,p)$
- 不過 $\displaystyle D_S(p,q) = \frac{1}{2} (D(p,q) + D(q,p))$ 有對稱性
- 不滿足三角不等式，只有 Bregman divergences 滿足廣義的畢達哥拉斯定理
- 可以二階微分項在機率分佈 manifold 上定義 Riemannian metric
- 維基：[Divergence (statistics)](https://en.wikipedia.org/wiki/Divergence_(statistics))

#### KL-Divergence（KL散度 / 相對熵 / 訊息增益）$D_{KL}(p\|q)$
- $D_{KL}(p\|q) = H(p,q) - H(p) = E_{x \sim p}[\log p(x)-\log q(x)]$
- KL-Divergence 越小則 $p(x),q(x)$ 越相似
- 原理：==計算編碼長度分佈的差距==，希望越接近 0 越好
- 但不具有對稱性：$D_{KL}(p\|q) \neq D_{KL}(q\|p)$
- 唯一同時屬於 f-Divergence 和 [Bregman Divergence](https://en.wikipedia.org/wiki/Bregman_divergence) 兩類的 Divergence
- Bregman Divergence 可以定義廣義畢氏理定理（不用平方，因為 Divergence 本身就是延伸自距離的平方）
- 等號成立：w 為目標的 relative interior
- 維基：[Kullback–Leibler divergence](https://en.wikipedia.org/wiki/Kullback%E2%80%93Leibler_divergence)

#### f-Divergence（f-散度）$D_f(p\|q)$
- $f$ 是 convex，並且 $f(1)=0$（機率一樣代表無差距）
- $\displaystyle D_f(p\|q) = E_{x \sim q}[f\big(\frac{p(x)}{q(x)}\big)]$，注意是 sample from $q(x)$
- 性質
- $\displaystyle D_f(p\|q) \ge f\big(E_{x \sim q}[\frac{p(x)}{q(x)}]\big) = f(1) = 0$
- 單調遞減：在馬可夫過程中在穩態時會收斂，過程中會單調遞減
- 具 Joint Convexity
- 維基：[f-divergence](https://en.wikipedia.org/wiki/F-divergence)
- [KL-Divergence](https://en.wikipedia.org/wiki/Kullback%E2%80%93Leibler_divergence)（Kullback-Leibler Divergence）
- $\displaystyle D_{KL}(p\|q)= H(p,q) - H(p) = E_{x \sim p}[\log p(x)-\log q(x)]$
- 選用 $f(t) = t\log t$
- 缺點：非對稱性
- [JS-Divergence](https://en.wikipedia.org/wiki/Jensen%E2%80%93Shannon_divergence)（Jensen–Shannon Divergence）
- $\displaystyle D_{JS}(p\|q)=\frac{1}{2}[D_{KL}(p\|\frac{p+q}{2})+D_{KL}(q\|\frac{p+q}{2})]$
- 選用 $\displaystyle f(t) = \frac{1}{2} [(t+1)\log\big(\frac{2}{t+1}\big)+t\log t]$
- 具對稱性，結果會更平滑
- 開根號之後為 metric
- 常用於 GAN
- 缺點：如果兩個分佈交集很少（現實往往如此），難以看出差異
- $\alpha$-Divergence（[Rényi Divergence](https://en.wikipedia.org/wiki/R%C3%A9nyi_entropy#R%C3%A9nyi_divergence)）
- $\displaystyle D_\alpha(p\|q) = \log \big(E_{x \sim p}[\big(\frac{p(x)}{q(x)}\big)^{\alpha-1}]\big)^{\frac{1}{\alpha-1}}$，where $\alpha \ge 0 \ and\ \alpha \neq 1$
- $D_1(p\|q) = D_{KL}(p\|q)$
- 選用 $\displaystyle f(t) = \frac{t^\alpha-1}{\alpha(\alpha-1)}$，if $\alpha \neq 0, \alpha \neq 1$
- 選用 $f(t) = -\log t$，if $\alpha = 0$
- 選用 $f(t) = t\log t$，if $\alpha = 1$
- 廣義的 KL-Divergence

#### Wasserstein Distance
- 衡量==機率分佈==是否==相似==，符合 metric 的定義
- 可以很==細緻==地看出兩個機率分佈的==差異==
- 又稱為推土機距離（Earth mover's distance）
- 甚至可以提供如何 Transform 的過程
- 沿著定義出來的直線走就是 Geodesics（測地線）
- 找一個分佈的路徑 $c(t), t \in [0,1]$ 從 $\mu$ 到 $\nu$，其中 $c(0) = \mu$，$c(1) = \nu$，如果對於任意的 $t$，$W_p(c(0),c(t))+W_p(c(t),c(1))=W_p(c(0),c(1))$ ，那麼這條路徑就是最短路徑。
- 原始定義
- 特殊狀況（有解析解）
- 維度 d = 1
當 p = 1 時又可以整理成
- Quantile function（分位函數）與 CDF（累積分佈函數）
- $q = F_X(x) = P(X \le x)$ 為累積分佈函數
- $x = F_X^{-1}(q)$ 為 Quantile function
- 是累積分佈函數的反函數
- 四分位數就是從這裡來的
- Quantile function 在以分佈為對象的 RL 很常見
- 大部分只會用到 d = 1，p = 1 的情況
- 像是 WGAN、QR-DQN 等等
- 高斯分佈（公式詳見維基）
- 常用於 Fréchet inception distance (FID)
- 測量生成的影像品質的指標
- 參考
- 維基：[Wasserstein metric](https://en.wikipedia.org/wiki/Wasserstein_metric)
- [還看不懂Wasserstein Distance嗎?看看這篇。](https://chih-sheng-huang821.medium.com/%E9%82%84%E7%9C%8B%E4%B8%8D%E6%87%82wasserstein-distance%E5%97%8E-%E7%9C%8B%E7%9C%8B%E9%80%99%E7%AF%87-b3c33d4b942)
- [【数学】Wasserstein Distance](https://zhuanlan.zhihu.com/p/58506295)

### 機率模型選擇

注意：以下討論是說要選擇哪一「種」模型，而模型的參數未定

一開始挑選模型時根據已知條件做最少的假設（在限制範圍內最大化熵）
- 白話文：知之為知之，不知為不知，是知也
- 原因：[最大熵原理（Principle of maximum entropy）](https://en.wikipedia.org/wiki/Principle_of_maximum_entropy)
- 連續機率分佈的話要用：[Principle of minimum discrimination information](https://en.wikipedia.org/wiki/Kullback%E2%80%93Leibler_divergence#Principle_of_minimum_discrimination_information)
- 觀念：限制狀態數量，產生最多樣性的結果，機率分佈會是最大熵
- 根據觀念用數學再次推導：[The Wallis derivation](https://en.wikipedia.org/wiki/Principle_of_maximum_entropy#The_Wallis_derivation)
- 物理的經驗定律（處於平衡態時）：[熱力學第二定律](https://zh.wikipedia.org/zh-tw/%E7%83%AD%E5%8A%9B%E5%AD%A6%E7%AC%AC%E4%BA%8C%E5%AE%9A%E5%BE%8B)、[統計力學](https://zh.wikipedia.org/wiki/%E7%BB%9F%E8%AE%A1%E5%8A%9B%E5%AD%A6)
- 哲學解釋：[奧卡姆剃刀](https://zh.wikipedia.org/wiki/%E5%A5%A5%E5%8D%A1%E5%A7%86%E5%89%83%E5%88%80)
- 參考
- [Lecture Notes for Statistics 311/Electrical Engineering 377](https://web.stanford.edu/class/stats311/lecture-notes.pdf)
- 主要的 Reference
- p. 210 ~ 225
- Chapter 14: Exponential families and maximum entropy
- Chapter 15: Robustness, duality, maximum entropy, and exponential families
- [Maximal Entropy Principle Optimization – Exponential Family](https://allenlu2007.wordpress.com/2018/04/03/maximal-entropy-principle-optimization/)
- 思路很好，推薦這個作者的文章
- [最大熵模型](https://luweikxy.gitbook.io/machine-learning-notes/linear-model/maximum-entropy-model)
- [最小作用量原理進路的解釋](https://aubinchang.wordpress.com/2012/02/20/%E4%BF%A1%E6%81%AF%E8%AB%96%E7%A0%94%E7%A9%B6%EF%BC%881%EF%BC%89%EF%BC%9A%E6%9C%80%E5%B0%8F%E4%BD%9C%E7%94%A8%E9%87%8F%E5%8E%9F%E7%90%86%E9%80%B2%E8%B7%AF%E7%9A%84%E8%A7%A3%E9%87%8B/)


變成限制條件最佳化問題
- 方法：[Maximum entropy probability distribution](https://en.wikipedia.org/wiki/Maximum_entropy_probability_distribution)
- 限制條件最佳化問題為 convex，可以轉成對偶問題，用 KKT 去解
- 處理變分問題：泛函導數對象是函數 $p$，使用 delta 函數 $\delta$，也就是說在進行積分時可以像求和那樣只對跟自己有關的部分微分
- 變分法可以找到極值，但較難分辨是最大或是最小值，不過可以透過另外的方法證明是極大值（或極小值，看目標函數怎麼定）
- 機率分佈本身須符合
- Support（機率為正）是 Compact Set（有明確邊界）
- 注意
- 有時候熵可能是無限大
- 有時候最大熵有上界，但是無法達到

對於不同類型的問題我們可以選擇適當的限制條件，再解限制條件的最大化熵最佳化問題，得到該類型的機率分佈函數，以下是一些給定條件下最少假設的模型
- 對於限制條件是機率分佈的熵等於機率分佈 $p$ 的熵
- 其中一個 trivial 的解會是 $p$
- 給定 Support 是 interval（或很多 intervals）
- 使用 Uniform Distribution
- 等於不做任何假設
- 給定 Support 為 $(-\infty,\infty)$，給定平均（Mean）和變異數（Variance）
- 使用常態分佈（Normal Distribution）
- 給定 Support 在超球面上
- 參考：[von Mises–Fisher distribution](https://en.wikipedia.org/wiki/Von_Mises%E2%80%93Fisher_distribution)
- 對於一些觀測量 $f_i(x)$ 期望值為定值 $F_i$ 的限制（對機率的 Affine constraints）
- 觀測量很像是量子的概念，同樣的狀態 $x$ 下無法分辨對應觀測量是否相異
- 定值是指對非條件限制的隨機變數而言，對於 given 的隨機變數是可變的
- $E[f_i(X)] = F_i$，$F_i$ 為實數，$i = 1, ..., n$
- 注意這裡用等號，才有以下的解
- Support 只要 Compact（有明確邊界）就好
- 定義 bias $\lambda_0$，且 $f_0(x) = 1$，用來 normalize
- $\displaystyle p(x) = e^{\sum_{i=0}^n \lambda_i f_i(x)} \propto e^{\sum_{i=1}^n \lambda_i f_i(x)}$，根據限制條件把 $\lambda_i$ 解出來
- 如果 $\lambda_i$ 已經是已知了，那就把這條限制併到其他條
- 把一坨線性組合後的東西做 Softmax
- 如果只有一個觀測量（取名為能量），就對應到波茲曼分佈（Boltzmann Distribution）
- Energy-based Model 就是以這個為基礎
- $f_0(x) = 1, \lambda_0 = \frac{F}{kT}$
- $f_1(x) = Energy(x),\ E[f_1(X)] = U, \lambda_1 = -\frac{1}{kT}$
- $\displaystyle p(x) = e^{\frac{F-Energy(x)}{kT}}\ \ \propto e^{-\frac{Energy(x)}{kT}}$
- 例子
- 觀測量的期望值是平均 $\mu$ 與變異數 $\sigma^2$
- 對應到常態分佈
- $f_1(x) = x,\ E[f_1(X)] = E[X] = \mu$
- $f_2(x) = (x-\mu)^2,\ E[f_2(X)]= E[(X-\mu)^2]=\sigma^2$
- $\lambda_0 = -\ln \sqrt{2\pi}\sigma, \lambda_1 = 0, \lambda_2 = -\frac{1}{\sigma^2}$
- $\displaystyle p(x) = \frac{1}{\sqrt{2\pi}\sigma}e^{-\frac{(x-\mu)^2}{\sigma^2}}$
- 觀測量的期望值是狀態所屬類別 $i$ 出現的機率 $\pi_i$
- 對應到 Multinoulli 分佈（類別分佈）
- 符號定義：$[x=n] = 1$ 當 $x=n$，其他時候 $=0$
- $\displaystyle E[X] = \sum_{i=1}^k \pi_i = 1$
- $f_i(x) = [x=i],\ E[f_i(X)] = \pi_i$
- $\lambda_0 = 0, \lambda_i = \log \pi_i$
- $\displaystyle p(x) = \prod_{i=1}^k \pi_i^{[x=i]}$
- 觀測量可以是累積獎勵
- $E_{a \sim \pi(a|s)}[Q(s_t,a_t)|s_t=s,a_t=a]=V(s)$
- $V(s)$ 跟 $a$ 無關，只跟 given 的 $s$ 有關
- $\pi(a|s) \propto e^{\lambda Q(s,a)}$ 這樣是最少假設（最大熵）的模型
- $\lambda$ 可以控制整體穩定度，越小越不穩定
- 也可以看成波茲曼分佈，對應的能量是 $-Q(s,a)$
- [指數族（Exponential Family）](https://en.wikipedia.org/wiki/Exponential_family#Table_of_distributions)
- 最大熵原理限制在 Affine 的解就是指數族
- 這個表非常豐富
- 表中的 $\eta(\theta)_i$ 對應到前面的 $\lambda_i$，$T(x)_i$ 對應到前面的 $f_i(x)$，也叫做充分統計量（sufficient statistic），$h(x)$ 在這裡必須是常數，不然就要使用另一類的限制條件，就不只是觀測量期望值為定值的限制
- [Information projection](https://en.wikipedia.org/wiki/Information_projection)
- 其他案例
- [條件限制和對應到的最大熵機率分佈](https://en.wikipedia.org/wiki/Maximum_entropy_probability_distribution#Other_examples)

想探討資料本身分佈
- 資料型態：$x$ 為資料
- 模型參數：$\theta$
- 模型：$p(x|\theta)$，產生 $x$ 的機率分佈
- 限定條件：看 $X$ 有什麼限定條件，選擇 $p(x|\theta)$

資料有分輸入跟輸出，想探討給定輸入時輸出的分佈
- 資料型態：$(x,y)$，$x$ 為輸入，$y$ 為輸出（答案）
- 模型參數：$\theta$
- 模型：$\pi_\theta(x) = p(y|x,\theta)$，給定輸入 $x$，模型產生 $y$ 的機率分佈
- 限定條件：看 $Y$ 有什麼限定條件，選擇 $p(y|x,\theta)$

### 如何得到一個最好的模型？

目的：選出==機率分佈與手中資料最接近的模型==

白話文
- ==我遇到一些事情想要找一個好的價值觀（世界觀）來解釋==
- 主要有兩種方法（更新原則）
- 最佳化方法：==一個好的價值觀（世界觀）可以讓你解釋大部分的事情==
- 漸進更新法：==用新觀察到的事情更新我的價值觀，會越接近事實==

數學式：找出 $p(\theta|data)$

至於要選擇哪一「種」初始模型請看上文。

### Point Estimation（點估計）

目的：根據關於問題的 Domain Knowledge 對==模型參數的機率分佈==做了一些==假設==，接著選出==機率分佈與手中資料最接近的模型==

- 維基：[Point estimation](https://en.wikipedia.org/wiki/Point_estimation)、[點估計](https://zh.wikipedia.org/zh-tw/%E7%82%B9%E4%BC%B0%E8%AE%A1)
- 以樣本數據來估計母體母數， 估計結果使用一個點的數值表示「最佳估計值」，因此稱為點估計。由樣本數據估計母體分布所含未知母數的真實值，所得到的值，稱為估計值。
- 數學式
- 貝氏定理：$\displaystyle arg\max\limits_\theta p(\theta|data) = arg\max\limits_\theta \frac{p(data|\theta)p(\theta)}{p(data)}$
- 最大化「根據資料而產生模型的機率分佈」＝最大化「根據模型產生資料的機率分佈 $\times$ 對於模型機率分佈的前題假設」
- 調整
- 我們會把機率取 $-\log$（轉化為對應編碼的位元長度）
- 乘除變加減，最大化變最小化
- $\displaystyle \theta^* = arg\min\limits_\theta -\log p(\theta|data) = arg\min\limits_\theta -\log \frac{p(data|\theta)p(\theta)}{p(data)}$
- ==MAP ＝ MLE ＋ 前提假設==
- MLE（Maximum Likelihood Estimation），頻率學派觀點
- $\theta_{MLE}^* = arg\max\limits_\theta p(data|\theta)$
- $p(data|\theta)$ 叫做 Likelihood
- $p(data|\theta)$ 可以看成是很多 $p(x_i|\theta)$ 相乘
- 獨立同分佈，i.i.d.：$x_i \sim p_{data}(x)$
- 以下用 $p_\theta(x)$ 表示 $p(x|\theta)$
- MAP（Maximum A Posterior），貝氏學派觀點
- $\theta_{MAP}^* = arg\max\limits_\theta p(\theta|data) = arg\max\limits_\theta p(data|\theta)p(\theta)$
- $p(data)$ 與 $\theta$ 無關，所以在最佳化時可以忽略
- MLE 的部分就是最小化 Cross Entropy $H(p_{data}, p_\theta)$
- $H(p_{data}, p_\theta) = E_{x \sim p_{data}}[- \log p_{\theta}(x)]$
- 在最佳化情境中也可以想成最小化 KL-Divergence $D_{KL}(p_{data}\|p_{\theta})$
- 因為加上 Entropy $H(p_{data})$ 與模型參數 $\theta$ 無關
- 意義：讓 $p_{data}, p_\theta$ 越接近越好
- 但這樣計算也比較複雜，所以實務上還是用 Cross Entropy 就好
- 前提假設（先驗分佈）就是最小化 Regularization Term $L(\theta)$
- $L(\theta) = E_{x \sim p_{data}}[I(\theta)] = E_{x \sim p_{data}}[-\log p(\theta)]$
- $p(\theta)$：模型參數 $\theta$ 機率分佈的==前題假設==
- Uniform Distribution 對應到常數，不影響最佳化
- 不做任何額外假設，等價於 MLE
- 缺點：需要大量資料
- Normal Distribution 對應到 L2 Regularization Term
- 最符合巨觀的假設
- Laplace Distribution 對應到 L1 Regularization Term
- 接近稀疏（有多個 0）的假設
- 式子整理
- $\theta^* = arg\max\limits_\theta p(data|\theta)p(\theta)$
- ==$\theta^* = arg\min\limits_\theta H(p_{data},p_{\theta}) + L(\theta)$==
- $\theta^* = arg\min\limits_\theta E_{x \sim p_{data}}[-\log p_{\theta}(x) - \log p(\theta)]$

### Bayesian Inference（貝氏推論）
另一種更新模型的方式，同樣根據貝氏定理：

$\displaystyle p(\theta|data) = \frac{p(data|\theta)p(\theta)}{p(data)}$

可以迭代：用 $p(\theta|data)$ 取代 $p(\theta)$ 繼續計算，data 可以是新的

目標：讓新的推論模型在依據新的數據的條件下盡可能地符合舊的推論模型（信念的更新）。

這裡沒有限制資料的格式，通常取樣自 Dataset，常常用到蒙地卡羅法（Monte Carlo）進行機率分佈的 sample，而且用同樣的資料也是被允許的。

與 MLE、MAP 的差異：MLE、MAP 屬於 Point Esitmate，只針對同一個 dataset 去取樣來解最佳化問題，Bayesian Inference 則可以在不同的迭代階段針對不同 dataset。

可能要 sample 夠好或是使用較方便的 Model（像是 Beta Distribution、Dirichlet Distribution、Gaussian Mixture Model 之類的）或是根據經驗挑足夠好的 Model 才比較好實作。而且容易受到信念（bias）的影響，不管是好的影響或是壞的影響。

貝氏推論的延伸 [Bayesian Optimization](https://en.wikipedia.org/wiki/Bayesian_optimization) 常常被用來調整模型的 hyperparameters（超參數），因為取得資料比較不容易。貝氏推論是調整參數，Bayesian Optimization 是調整超參數。

參考
- 維基：[貝氏推論](https://zh.wikipedia.org/zh-tw/%E8%B4%9D%E5%8F%B6%E6%96%AF%E6%8E%A8%E6%96%AD)

論文
- [On the Nature of Bayesian Convergence](https://doi.org/10.1086/psaprocbienmeetp.1994.1.193029)
- [Updating Probabilities](https://arxiv.org/pdf/physics/0608185.pdf)
- Bayesian Inference 是 Maximum (relative) Entropy（ME）的特例
- 其實這邊講的 Maximum (relative) Entropy 實際上是==最小化==新對舊模型之間的 ==KL-Divergence（相對熵為負的 KL-Divergence）==
- 最大化 $S[P,P_{old}] = - D_{KL}(P\|P_{old})$ 等價於最小化 $D_{KL}(P\|P_{old})$
$p_{new} = arg\min\limits_p D_{KL}(p\|p_{old})$
- 有對新模型設下一些 constrain，參考下篇論文
- [Updating Probabilities with Data and Moments](https://arxiv.org/pdf/0708.1593.pdf)
- 限制
- data constrain（資料限制）推出來即為迭代的貝氏推論
盲人 $\theta$ 摸象 $x$，全部（各種不同的 $\theta$）摸完後就是真正的大象 $P(x)$，
只有在 $x=x'$ 時 $P(x)$ 才等於 1，其他時候為 0，
不過不是大家都這麼認為，而是綜合大家的結論才這麼認為。
- moment constrain
- ME 方法，若 $\beta=0,Z=1$ 則為 Bayesian Inference

### 特徵轉換（Feature Transformation）

用一些特徵來表示手中的資料（抽象化），可以是非線性的
簡單來說就是用各種特徵函數進行「編碼」

在做資料分析時前期約有 80% 著重在 Feature 的處理！

拓撲與流形（manifold）
- [拓撲](https://zh.wikipedia.org/wiki/%E6%8B%93%E6%89%91%E5%AD%A6)
- [拓撲空間](https://zh.wikipedia.org/wiki/%E6%8B%93%E6%89%91%E7%A9%BA%E9%97%B4)
- 有好幾種公理可以選擇，都可以互相等價推演
- [連續](https://zh.wikipedia.org/wiki/%E9%80%A3%E7%BA%8C%E5%87%BD%E6%95%B8_(%E6%8B%93%E6%92%B2%E5%AD%B8))
- 用開集定義：開集的 preimage 是開集
- 用閉集定義：閉集的 preimage 是閉集
- 用鄰域定義：限制對應域中 f(x) 的鄰域 V，在定義域中可以找到一個 x 的鄰域 U，使 f(U) 落在 V 之內
- [同胚（Homeomorphism）](https://zh.wikipedia.org/wiki/%E5%90%8C%E8%83%9A)：雙向連續「可逆」的對應關係，不講過程
- 
- 同胚是拓撲空間範疇中的同構
- 同胚是保持給定空間的所有拓撲性質的映射
- 字母 A 和 R 同胚，字母 X 和 Y 不同胚
- 很像是橡膠（不可壓縮）
- [同倫（Homotopic）](https://zh.wikipedia.org/wiki/%E5%90%8C%E5%80%AB)：連續形變的「過程」（可壓縮或延伸）
- 字母 A 和 R 同倫，字母 X 和 Y 也同倫
- 很像是黏土（可壓縮）
- 壓縮：多對一
- 延伸：一對多
- [Hausdorff space（分離空間）](https://zh.wikipedia.org/zh-tw/%E8%B1%AA%E6%96%AF%E5%A4%9A%E5%A4%AB%E7%A9%BA%E9%97%B4)
- 不同的點可由由鄰域分離
- 所有 metric space 都是 Hausdorff space
- 流形
- [歐幾里得空間](https://zh.wikipedia.org/zh-tw/%E6%AC%A7%E5%87%A0%E9%87%8C%E5%BE%97%E7%A9%BA%E9%97%B4)
- 可以在上面討論歐式幾何
- 距離、角度（切、垂直）、平移、旋轉、全等
- 除了 $R^n$ 向量空間之外，還定義了內積
- 由內積可以定義 norm，由 norm 可以定義距離
- 也用內積和 norm 定義角度
- 因為有距離的定義，所以也是拓撲空間
- 可以用開球開始定義開集
- 也是 metric space
- 所以也是 Hausdorff space
- 歐氏空間也被理解為線性流形
- 歐幾里得空間的根本性質為它是平坦的，也就是非彎曲的
- [流形](https://zh.wikipedia.org/wiki/%E6%B5%81%E5%BD%A2)
- 可以局部歐幾里得空間化的一個拓撲空間
- 是 Hausdorff space
- 對任意流形中的點 x，存在 x 的開鄰域 U，使得 U 同胚於歐幾里得空間的開子集
- 流形中連通的點有相同的維數
- 流形可以是不連通的
- [流形如果有邊界](https://en.wikipedia.org/wiki/Manifold#Manifold_with_boundary)，則邊界是 n-1 維的流形，同胚於歐幾里得空間的半開子集
- e.g. 開球第一個維度大於等於 0
- 坐標卡（coordinate chart）
- 或稱坐標映射（coordinate map）
- 開鄰域如何同胚對應到歐幾里得空間的開子集
- 圖冊（atlas）
- 能覆蓋流形的坐標卡的集合
- 不唯一
- [坐標變換映射](https://zh.wikipedia.org/wiki/%E5%9D%90%E6%A0%87%E8%BD%AC%E6%8D%A2)
- 聯繫這些坐標卡
- 很像通訊系統中的 handoff（接力）
- 兩個坐標卡有重疊，在重疊處定義對應關係
- 附加結構
- 如果有些結構在座標卡上分別都有定義
- 所有變換映射和這個結構相容
- 該結構就可以轉到流形上
- e.g. 微分結構可以定義微分流形
- 微分流形
- 如果坐標轉換重疊處對應關係是無限可微
- 可以在流形上面定義可微分函數
- 切向量
- 一次型（Linear-form）
- 定義於流形的曲線上
- 切空間（Tangent Space）
- 
- 切叢（Tangent Bundle）
- 
- 可以在微分流形上應用「微積分」
- 在研究「變化」
- 黎曼流形
- 可以定義「曲線的長度」的微分流形
- 黎曼度量（度量張量）
- 用點積定義度量張量（矩陣）
- 重新定義「長度」，不再視為理所當然
- 度量張量是在流形上連續的
- 每點p的切空間都定義了點積，而且其數值隨p平滑地改變
- 度量張量為二階對稱正定張量場
- 對稱半正定矩陣
- 二次型（Quadratic-form）
- 微小曲線長度 ds 會受到該點度量張量影響長度
- 度量張量會連續變化
- 可以定義直線段：長度最短的曲線（測地線 Geodesic）
- 這可以定義距離
- 納許嵌入定理 (Nash embedding theorems）
- 每個黎曼流形可以等距嵌入到歐幾里得空間
很像波浪，也像是碎形
用這種方式來保持距離一樣

NN 與拓撲、流形的關係
- [Neural Networks, Manifolds, and Topology](https://colah.github.io/posts/2014-03-NN-Manifolds-Topology/)
- [神经网络,流形和拓扑](https://blog.csdn.net/u011196300/article/details/51233277)
- 流形假設是指，自然數據(現實世界數據)在嵌入空間形成低維流形。理論上實驗上都有理由相信這都是真的。如果你相信這個，那麼分類算法從根本上分類了一堆糾纏的流形。
- 一般 NN 都是不可逆的（就算 Activation Function 可逆），所以可以視為同倫到一個我稱之為「線性可處理（包含線性可分、線性迴歸）」的平坦歐式空間，當空間是平坦時，一般的內積（可以定義距離、角度、相關性）才有意義
- [求简要介绍一下流形学习的基本思想？](https://www.zhihu.com/question/24015486/answer/194284643)
- 回答得非常好！
- 既“流型空間上的可以用歐氏距離，不代表低維流型所展開的高維空間中也可以使用歐氏距離進行衡量”。只有在流型空間，用歐氏距離才有意義。
- 流形能夠刻畫數據的本質。也就是說。既然學習到了“將數據從高維空間降維到低維空間，還能不損失信息”的映射，那這個映射能夠輸入原始數據，輸出數據更本質的特徵(就像壓縮一樣，用更少的數據能盡可能多地表示原始數據)。
- 所謂的特徵，在一定程度上就可以用流形的概念來解釋。我們希望我們的模型能夠學習到“數據在流型空間中的表示”。

為何神經網路要用內積（$XW+b$）？
- 把內積想成是使用特徵 Encoding（對局部空間的一階泰勒近似）
- encoding = $f(x)$ = Taylor Expanssion
- 出來是實數，大家再根據基準（來自零階近似）、尺度（來自一階近似）去比較
- 把 Affine Transform 想成是對局部空間的一階泰勒近似

廣義線性模型：$E[Y|X=x] = \mu_Y(x) = g^{-1}(x^T\beta+\beta_0) = g^{-1}(\eta)$
- 這裡的機率分佈選用指數族（來自最大熵原理）
- $g$ 是 Link Function，連結線性預測與機率分佈的期望值
- Link Function 的反函數就是 Activation Function！
- 這裡的線性是指參數 $\beta_i$ 為一次，不是高次
- 使用泰勒展開 $\displaystyle \eta = f(z) = \sum_{n=0}^k \frac{f^{(n)}(0)}{n!}z^n+R_{k+1}(z)$，向量版本
- 以 $0$ 為中心
- 所以盡量把輸入控制在 zero-centered 附近，才會準
- 那麼收集張量 $\displaystyle \frac{f^{(n)}(0)}{n!}$ 內的元素就是 $\beta$，$z^n$ 的各個交互項就是 $x$
- 用 $k$ 階泰勒近似 $f$，再根據輸出的性質決定 Activation Function
- 一般都是近似到一階（線性，Affine）
- 那我們如果用到二階呢？
- Quadratic Neural Networks
- 自然界有很多物理定律都可以用二次微分（或說是黎曼流形，有定義二階度量張量）建模
- 注意：如果近似到二階實作上會有一些效能方面的技巧，像是用一次項相乘
- 主要是想知道這個線性項在輸出之後要變成什麼樣子，較好擬合
- 因為非線性的情況通常複雜許多
- 幾個問題
- 對偶的概念與泰勒展開有沒有關係？
- 因為如果考慮到一次項，還會多出一個 bias
- 如果用 n-mode tensor dot 應該會更好想
- 對偶問題跟對偶空間應該有關係
- 為何要使用線性擬合？
- 指數族如果在 Affine 的限制條件下（期望值的限制條件），得到的解有一部分是線性組合，所以這個線性的由來是源自於對偶問題，對偶問題來自勒壤得變換，勒壤得變換來自凸函數的支持線的證明，Jensen 不等式也可以來自凸函數的支持線的證明
- 當空間是平坦時，一般的內積（可以定義距離、角度、相關性）才有意義
- 參數的部分是線性的
- 會不會是因為均勻連續的關係？不是！
- 擬合需要連續的變化
- 微積分是局部線性的
- Activation Function 的選擇對於連續變化的影響
- 如何用機率來描述函數？

### 深度學習（Deep Learning）

因為我們在擬合模型時是用 GLM（廣義線性模型，多變量的線性迴歸），通常會透過 NN（類神經網路）等方法把原本的問題由==非線性的流形連續變換為平坦的歐式空間==，我稱之為「線性可處理（包含線性可分、線性迴歸）」，再去進行擬合。

而 NN（類神經網路）在適當的調整下，可以擬合大部分==任意的連續函數==。

所以當問題龐大到我們無法經由一一列舉的方式得到答案時，我們會透過建立 NN（類神經網路）來擬合，很像是一個==黑箱==，輸入資料後會得到輸出。

NN（類神經網路）當中的這些連結就是利用==特徵的提取==來轉換資料，NN（類神經網路）的層數越深越可以提取到越==抽象的特徵（Latent Space）==，這是不那麼黑箱的解釋。

[回目錄](#Reinforcement-Learning（增強學習）整理)

Value-based Methods
---

==估計 $V(s)$ 或 $Q(s,a)$ 的值==

- 又稱作 Critic
- 不同的 state 或是 policy 會有不同的 Value
- 採用 Action $a = \pi^*(s) = arg\max\limits_a Q^*(s,a)$
- 通常只能是離散的

### 估計（sample）方式

MC（Monte Carlo，蒙地卡羅）
- 收集到最後
- Target 對象（針對 $V^{\pi}$ 與 $Q^{\pi}$）：$G_t$
- variance 較大，但較精確
- 傳統方式（非 NN）：

TD（Temporal Difference，時序差分）
- 只收集一步（$...,s_t, a_t, r_t , s_{t+1},...$）
- Target 對象（針對 $V^{\pi}$）：$r_t + \gamma V^{\pi}(s_{t+1})$
- Target 對象（針對 $Q^{\pi}$）：$r_t + \gamma Q^{\pi}(s_{t+1}, a_{t+1})$
- variance 較小，比較穩，但較不準，較常見
- 傳統方式（非 NN）：
Q 那條又叫 [SARSA](https://en.wikipedia.org/wiki/State%E2%80%93action%E2%80%93reward%E2%80%93state%E2%80%93action)（state–action–reward–state–action），
==用 ε-greedy 來選 $a_{t+1}$==

目標：縮小 Target 對象與 $V^{\pi}(s_t)$ 或 $Q^{\pi}(s_t, a_t)$ 間的差距
- 是一個 regression 的 problem（最小平方法）
- 從 replay bufffer 去 sample 一個 batch，t 是樣本
- 使用 MSE 當誤差，再取誤差的期望值（平均）

### Q-Learning

Value-based 方法，可以用 TD 或 MC

論文：[Learning from Delayed Rewards](https://www.cs.rhul.ac.uk/~chrisw/new_thesis.pdf)

照下面的原則找到新的 policy 一定會比較好（證明略）



使用目前的狀態下最大的 Q 來更新：

==$Q^{\pi}(s_{t+1}, a_{t+1}) := \max\limits_{a} Q^{\pi}(s_{t+1}, a)$==

傳統方式（非 NN，更新 Q-Table，只是用離散數值且少量）：


DQN（Deep Q-Learning）：用 NN 來學 Q Function


NN 的輸入是 state（或是 stacked states），輸出是每個 action 對應到的 reward

原始論文：[Playing Atari with Deep Reinforcement Learning](https://www.cs.toronto.edu/~vmnih/docs/dqn.pdf)

### 常用技巧

#### Target Network
- 原因：如果沒有固定其中一邊會較難訓練
- 建立一個 V / Q Function 的副本，當作基準
- 通常用 Target 對象的部分來當作 Target
- 只更新原來的 V / Q Function
- N 次之後再把新的參數複製到 Target Network

#### Exploration
- 原因：Q-Learning 只會選到同一個 action（使 Q-Value 最大的那個），就像你每次去餐廳只點肉燥飯一樣
- 解決方法（提供兩種）：
- 論文
- [Reinforcement Learning with Deep Energy-Based Policies](https://arxiv.org/pdf/1702.08165.pdf)
- Soft Q-Learning
- 參考
- [Learning Diverse Skills via Maximum Entropy Deep Reinforcement Learning](https://bair.berkeley.edu/blog/2017/10/06/soft-q-learning/)
- Soft Q-Learning

#### Replay Buffer
- 儲存不同的 policy sample 出來的樣本
- 一個樣本：$(s_t, a_t, r_t, s_{t+1})$
- 有容量限制，如果滿了舊的會先被移除
- 是 sample 一個 batch（沒有順序），不是 trajectory
- 就算是 Off-policy 也沒關係

### Rainbow（組合技）

#### Double DQN
- 原因：DQN 的 Value 往往是被高估的（凡有誤差被高估的，再加給他）
- 原理：立法（提案，找 max）與行政（執行，計算 Target 值）分立
- 實作：拿原本的 Network 選最大值，Target Network 計算 Target 值，其他不用改
- 論文：[Deep Reinforcement Learning with Double Q-learning](https://arxiv.org/pdf/1509.06461.pdf)

#### Deuling DQN
- 唯一做的事：改 Network 的架構
- Q 等於 Advantage（向量）+ Value（純量）
- 原理：擾動純量 V(s) 的部分可以做比較大範圍的擾動，就不用 sample 到全部才能 work
- 會對 A 下 constrain，像是 column 和是 0
- 透過 normalization
- 實作上約束項可以這麼做，假設輸出是7, 3, 2，先做 normalization，7 + 3 + 2 = 12 / 3 = 4，每個項目都減 4，得到3, -1, -2，再用這個值去加上 V(s) 就可以
- 這個 normalization 的 operation 是 NN 的一部份，沒有參數的一個 layer
- 論文：[Dueling Network Architectures for Deep Reinforcement Learning](https://arxiv.org/pdf/1511.06581.pdf)

#### Prioritized Reply
- 讓 TD Error 大的資料有比較高的機率被 sample
- 實作上不止更改 sampling 的流程，也會調整更新參數的方法
- 資料結構：Sum Tree
- 論文：[Prioritized Experience Replay](https://arxiv.org/pdf/1511.05952.pdf)
- 參考
- [强化学习之Sumtree](https://zhuanlan.zhihu.com/p/165134346)
- [强化学习代码实践（二）--prioritized replay 的SumTree实现](https://zhuanlan.zhihu.com/p/47578210)
- [Prioritized Experience Replay - 莫煩](https://mofanpy.com/tutorials/machine-learning/reinforcement-learning/prioritized-replay/)
- [PRIORITIZED DDQN](https://drive.google.com/file/d/1S0Dh4CZCMZ05JU_ngP1i8MC0azXlwd3K/view?usp=sharing) p.37

#### Multi-Step
- 原理：在 TD 和 MC 中間取得平衡
- 實做：Buffer 中的一筆資料為連續大 N 組

#### Noisy Net
- 原理：在所有參數上面加（Gaussian）Noise
- 原因：在用 ε-greedy 產生 Action 時，有時候選最大、有時候隨機，沒有系統的隨機亂試，反觀 Noisy Net，是 Self-Dependent Exploration（看到相同 state 會做同一個 action，但在每個 Episode 時會不一樣），是有系統的試
- 實作：只在每個 Episode「開始」時才 sample network， 接下來就固定，直到下個 Episode
- 論文：[Noisy Networks for Exploration](https://arxiv.org/pdf/1706.10295.pdf)

#### Distributional Q-function（C51）
- 原理：不只給 Q 的期望值，還有它的機率分佈
- 較容易 Under estimate
- 較不好實作
- 全部的運算都變成了機率分佈上的伸縮和平移
- 有用到 Wasserstein Distance
- 論文：[A Distributional Perspective on Reinforcement Learning](https://arxiv.org/pdf/1707.06887.pdf)

#### Rainbow
- 綜合以上，效果最好
- 論文：[Rainbow: Combining Improvements in Deep Reinforcement Learning](https://arxiv.org/pdf/1710.02298.pdf)
- 
- DDQN 加不加影響較小，應該是 Distributional Q-function 本身就不會高估的緣故

### QR-DQN（Quantile Regression DQN）


論文：[Distributional Reinforcement Learning with Quantile Regression](https://arxiv.org/pdf/1710.10044.pdf)
- 學的是 V 或 Q 的機率分佈
- 用一些 Divergence 衡量機率分佈是否相似
- 用 Quantile Regression 學習

### HER（Hindsight Experience Replay）


論文：[Hindsight Experience Replay](https://arxiv.org/pdf/1707.01495.pdf)
- 利用有沒有達成目標來作為依據（事後諸葛）
- 論文說 Prioritized experience replay is orthogonal to our work and both approaches can be easily combined.
- 不過有經驗（Stable Baselines）指出 Prioritized replay buffer 不會增加 HER 什麼表現，所以沒有 implement Prioritized replay buffer

### Ape-X（Distributed Prioritized Experience Replay）

分散式運算，共享 Prioritized Replay Buffer


論文：[Distributed Prioritized Experience Replay](https://arxiv.org/pdf/1803.00933.pdf)

### 對付 Continuous Action

要如何找到 $a = arg\max\limits_a Q(s,a)$？

#### 用 sample 的
- 但結果通常不會非常精確

#### 用 gradoent ascent 來解
- 很花時間

#### Normalized Advantage Functions
- [論文：Continuous Deep Q-Learning with Model-based Acceleration](https://arxiv.org/pdf/1603.00748.pdf)
- $\mu(s)$：mean vector
- $\Sigma(s)$：variance matrix，正定
- 由類似 $A^TA$ 的方式得到
- $V(s)$：純量
- 這樣設計可以取 $a = \mu(s)$

#### 不要用 Q-Learning
- 用 Actor-Critic 系列
- 用 DDPG 系列

[回目錄](#Reinforcement-Learning（增強學習）整理)

Policy-based Methods
---

==選擇 Policy==

- 又稱作 Actor

### Policy Gradient
- 定義：軌跡 Trajectory $\tau=\left\{s_1,a_1,s_2,a_2,...,s_T,a_T\right\}$
- ==假設：對於環境的機率分佈 $P(s'|s,a)$，一個 state 只跟前面的 action 和前一個 state 有關==
- 不可以調（跟 policy 無關，微分不影響）
- Policy 是一個機率分佈 $\pi_\theta(a \vert s)$，可以用 network 學出來
- 可以調
- Log Likelihood
- $p_\theta(\tau)=P(s_1)\pi_\theta(a_1|s_1)P(s_2|s_1,a_1)\pi_\theta(a_2|s_2)P(s_3|s_2,a_2)...$
$\displaystyle = P(s_1)\prod_{t=1}^T \pi_\theta(a_t|s_t)P(s_{t+1}|s_t,a_t)$
- $\displaystyle \log p_\theta(\tau)= \sum_{t=1}^T \log \pi_\theta(a_t|s_t) + \log P(s_1) + \sum_{t=1}^T \log P(s_{t+1}|s_t,a_t)$
- 後面跟 $\theta$ 無關，對 $\theta$ 微分等於 0
- 目標：最大化以 Advantage 作權重的 log likelihood
- $\nabla J(\theta) = E_{\tau \sim p_\theta(\tau)}\left[A(\tau) \nabla \log p_\theta(\tau)\right]$，$p_\theta(\tau)$ 未知 $\Rightarrow$ sample
$\displaystyle \approx \dfrac{1}{N} \sum^N_{n=1} A(\tau^n) \nabla \log p_\theta(\tau^n)$
$\displaystyle =\dfrac{1}{N} \sum^N_{n=1} \sum^{T_n}_{t=1} A(\tau^n) \nabla \log \pi_\theta(a^n_t \vert s^n_t)$
- $l(\theta) = -J(\theta) = E_{\tau \sim Environment\ and\ Policy}[-A(\tau) \log p_\theta(\tau)]$
- 可想成是權重為 Advantage 的 Weighted Cross Entropy
- 這個 Loss Function $J(\theta)$ 的梯度就是 Policy Gradient
- 最佳化的過程就是用 Policy Gradient 更新參數
- Advantage A = Return - Baseline
- 常用 Q 當作 Return
- 常用 V（Q 的期望值） 當作 Baseline
- Baseline 目的是希望有正有負，好訓練
- 一般而言要使用一整個 Trajectory $\tau$ 訓練，除非 Advantage 是使用 Temporal Difference（TD） 之類的
- 這種最基本的（Vanilla）Policy Gradient 叫做 REINFORCE 演算法
- 限制：On-policy
- 論文：[Policy Gradient Methods for Reinforcement Learning with Function Approximation](https://proceedings.neurips.cc/paper/1999/file/464d828b85b0bed98e80ade0a5c43b0f-Paper.pdf)

### Actor-Critic Methods（AC）

延伸自 Policy Gradient（Actor），並加入了估計 Value 的 Network（Critic）

Actor-Critic 的概念其實很早就有了

論文：[Asynchronous Methods for Deep Reinforcement Learning](https://arxiv.org/pdf/1602.01783.pdf)

#### Advantage 的選擇
$A^{\pi_\theta}(s_t^n,a_t^n) = G_t^n - b = Q^{\pi_\theta}(s_t^n,a_t^n) - V^{\pi_\theta}(s_t^n)$
- 上標 $n$ 代表從 $p_\theta(\tau)$ sample 出的樣本
- 用 $G_t^n$ 的期望值（V, Q）代替 sample 的值會比較穩定
- 用 Value-based 的方式估測！
- baseline 選 V 是因為 V 又是 Q 的期望值
- 訓練時就不用丟一整個 Trajectory $\tau$ 了
- 但同時估兩個 Network 不准的風險高，為了減少 Network，我們把 Q 的值用 V 表示
- $Q^{\pi}(s_t^n,a_t^n) = E[r_t^n + \gamma V^{\pi}(s_{t+1}^n)|s=s_t^n] \approx r_t^n + \gamma V^{\pi}(s_{t+1}^n)$
- 但這樣會有一點 $r_t$ 的隨機性，有些 variance
- 不過比原來直接用 $G_t$ 好很多
- ==A3C 實驗證明這樣的組合最好==
- 結論：Advantage $A^{\pi}(s_t^n,a_t^n) = r_t^n + \gamma V^{\pi}(s_{t+1}^n) - V^{\pi}(s_t^n)$
- $A(s,a) = Q(s,a) - V(s) \approx r + \gamma V(s') - V(s)$
- $J(\theta) = E_{\tau}[E_{(s,a)\ in\ \tau}[-A(s,a) \log \pi_\theta(a|s)]]$

### A2C（Advantage Actor-Critic）

由 Policy-Gradient 延伸


#### 技巧
- 共用 Network
- Actor Network 與 Critic Network 共用前幾層 Network
- 理由：前幾層特徵是大家共享的，特別對於影像輸入

### A3C（Asynchronous Advantage Actor-Critic）

A2C 的平行運算版本

- 開分身（worker）同時訓練
- Copy 參數
- 個別收集環境資料
- 算 Gradient，Update「Global」的參數
- 不用在意別人
- 注意回傳的是 Gradient 不是環境資料

### TRPO（Trust Region Policy Optimization）

Actor-Critic 系列

#### ==Off-policy==
- 不用像 On-policy 每一輪訓練都要重新 sample
- Importance Sampling
- 這技巧在很多其他地方也可以用

#### ==假設==
- 兩個 policy 分佈不會差太遠
- 機率分佈差距不大
- 用 KL-Divergence 作為 Regularization Term
- 把 $D_{KL}(p_\theta\|p_{\theta'}) < \delta$ 當作額外的 contrain（限制條件）
- 
- 兩個 policy 的 Advantage 不會差太多
- 兩個 policy 看到相同 state 的機率差不多

目標
- 最大化從舊分佈去 sample 「(新的 $\pi(s|a)$ / 舊的 $\pi(s|a)$) * Advantage」的期望值
- 看不到 Log Likelihood 的部份因為被吸收了

論文：[Trust Region Policy Optimization](https://arxiv.org/pdf/1502.05477.pdf)

### PPO（Proximal Policy Optimization）

==被很多套件當成是預設的演算法==

延伸自 TRPO，實作上比 TRPO 簡單

PPO2 使用 ε clip 技巧控制機率分佈不要差太多：
（先試 ε = 0.2～0.1）

與 TRPO 的差別
- TRPO 把 KL-Divergence 當作額外的 constrain
- PPO 直接納入目標函數
- PPO2 用 ε clip（最容易實作）

論文：[Proximal Policy Optimization Algorithms](https://arxiv.org/pdf/1707.06347.pdf)

### DPPO（Distributed Proximal Policy Optimization）
- 跟 A3C 很像，開多個分身訓練
- 差別是 A3C 回傳 Gradient，DPPO 回傳資料（因為是 Off-policy 所以不同環境沒影響太大）

論文：[Emergence of Locomotion Behaviours in Rich Environments](https://arxiv.org/pdf/1707.02286.pdf)

### Exploration
- 對於 Actor 的輸出，Entropy 越大越好
- 設這樣的 constrain / regularization term
- 理由：Entropy 越大，越有可能選到沒看過的動作，比較好探索環境

[回目錄](#Reinforcement-Learning（增強學習）整理)

Deterministic Policy Gradient Methods
---
延伸自 Value-based Methods（Q-Learning）

==用 Generator 生成 Action==
- 可以處理連續動作
- 跟 GAN 很像，同樣難 Train
- 跟 Policy-based 的系列關係不大，只是用詞像

論文：[Deterministic Policy Gradient Algorithms](http://proceedings.mlr.press/v32/silver14.pdf)

### DDPG（Deep Deterministic Policy Gradient）

延伸自 Value-based（Q-Learning）

- 一般的 Critic 只會評斷 Actor 做這個 Action 是好還是不好，但是現在 Critic 會引導說做什麼 Action 才是好的
- 由 Q-Learning 的 $a = arg\max\limits_a Q(s,a)$ 出發
- 想法：訓練一個 Actor 來產生 Action，就像是 ==GAN 中的 Generator==
- 這個 Actor 會在給定 State 時試著產生能給出最大 Q-Value 的 Action
- 可以想成是延伸 Q-Learning 的架構，之前提到的 Q-Learning 的技巧都可以用，訓練時不會用到前面定義的 Policy Gradient（這個系列和 Actor-Critic 或是 PPO 無關），是用另一個 Update Actor 參數（policy）的方式
- 與 Q-Learning 的比較
- 可以跟 GAN 互通有無（同為難 train 的模型）
- [Connecting Generative Adversarial Networks and Actor-Critic Methods](https://arxiv.org/pdf/1610.01945.pdf)
- 名詞釋義
- 李宏毅在這段的用詞是 Pathwise Derivative Policy Gradient
- 論文：[Continuous control with deep reinforcement learning](https://arxiv.org/pdf/1509.02971.pdf)

### TD3（Twin Delayed Deep Deterministic policy gradient algorithm）

DDPG 的進化版

- 因為 DDPG 很難 Train（不穩定）
- 用類似 Double Q-Network 的方式，解決了 DDPG 中 Critic 高估 Action Q Value 的問題
- 延遲 Actor 更新，讓 Actor 的訓練更加穩定
- 在 Target Actor 中加上 noise，增加穩定性
- 論文：[Addressing Function Approximation Error in Actor-Critic Methods](https://arxiv.org/pdf/1802.09477.pdf)

### TQC（Truncated Quantile Critics）

DDPG 系列

直接對機率分佈進行操作，而不只是期望值

論文：[Controlling Overestimation Bias with Truncated Mixture of Continuous Distributional Quantile Critics](https://arxiv.org/pdf/2005.04269.pdf)

### D4PG（Distributed Distributional Deterministic Deep Policy Gradients）

DDPG 系列

可以分散式計算，學習的是機率分佈，而不只是期望值

論文：[Distributed Distributional Deterministic Policy Gradients](https://arxiv.org/pdf/1804.08617.pdf)

### SAC（Soft Actor-Critic）

是 DDPG 的延伸

用==最大化 Action 的 Entropy== 增加==探索（Exploration）== 的可能性

與 DDPG 不同的是，SAC 輸出的 Action 是隨機性的

Boltzmann Exploration 可以更適用在不同類型的任務（多模態，multimodal）

可惜 SAC 最後還是限制在 Normal Distribution，但效果已經夠好了

SAC 對整個過程，而不只是單一 Action 的選擇使用最大化 Entropy，所以 Value Function 和 Q-Function 都要加上 Entropy 最大化的限制，叫做 Soft，論文有證明這樣還是可以收斂到最佳解。

如何連結三者的三角關係：

主要流程：
- 兩個 Q Network 的更新（regression problem）
- Policy Network 的更新（與 Maximum Entropy Policy 的差距）
這裡為了方便追蹤，限制 Policy Network 為高斯分佈（Network 的輸出有平均跟標準差，再加上 Gaussian Noise）
完整的式子：
- Temperature $\alpha$ 的更新
- 這是一個對於整體的限制
Temperature 的 Loss Function：

整體 Network 架構：

連續動作與離散動作：


還有一些細節請看參考資料

參考
- [最前沿：深度解读Soft Actor-Critic 算法](https://zhuanlan.zhihu.com/p/70360272)
- 說明得非常清楚！

論文
- [Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor](https://arxiv.org/pdf/1801.01290.pdf)
- [Soft Actor-Critic Algorithms and Applications](https://arxiv.org/pdf/1812.05905.pdf)
- 更新版

[回目錄](#Reinforcement-Learning（增強學習）整理)

Sparse Reward 的情況
---

### Reward Shapping
- 用「設計過」的 reward 取代原來的 reward
- 需要 Domain Knowledge
- 例子
- 射擊遊戲
- 站著不動會扣分
- 用機械手臂把有洞的板子穿過柱子
- 方法：Curiosity（好奇心）
- 論文：[Curiosity-driven Exploration by Self-supervised Prediction](https://arxiv.org/pdf/1705.05363.pdf)
- 鼓勵冒險（發現越沒有辦法預測的 state 獎勵會更大）
- 加入好奇心的 reward $r_t^i$（根據 $s_t, a_t, s_{t+1}$）
- $r_t = r_t^e + \beta r_t^i$（外部＋內部）
- 
- ICM：Intrinsic Curiosity Module
- $r_t^i$ 是另外訓練出來的
- 預測出的狀態與遇到的狀態差異越大，獎勵越大
- 光有好奇心不夠，較難預測和真正重要不一定相等，像是一直盯著樹葉飄動
- 解決方法：再訓練一個 feature extrator
- 濾掉無關緊要的事
- 
- ICM 是另外訓練的，在一般訓練時是 Fixed

### Curriculum Learning（課程學習）
- 不只用在 RL
- 從簡單到難，規劃課程
- 例子：用機械手臂把有洞的板子穿過柱子
- 可以先訓練在柱子上把板子壓下去
- Reverse Curriculum Generation
- 從 goal state $s_g$ 開始往回推
- 選一些 reward 適中的 case 再繼續往回推
- 不會太簡單也不會太難
- 
- 論文
- [Curriculum Learning](https://ronan.collobert.com/pub/2009_curriculum_icml.pdf)
- [Reverse Curriculum Generation for Reinforcement Learning](https://arxiv.org/pdf/1707.05300.pdf)

### Hierarchical Reinforcement Learning（HRL）
- 有一些負責訂目標（願景）的 Agent
- 如何拆解任務？目標（願景）有階層式的
- 如果底下的 Agent 做不到這個目標（願景），上層就會被討厭（得到 penalty）
- 有可能中途換目標（願景）
- 論文：
- [Between MDPs and semi-MDPs: A framework for temporal abstraction in reinforcement learning](https://pdf.sciencedirectassets.com/271585/1-s2.0-S0004370200X00549/1-s2.0-S0004370299000521/main.pdf)
- Option（動作組合）
- semi-MDP（SMDP）：叫做 semi 是因為機率總和小於 1
- [Strategic Attentive Writer for Learning Macro-Actions（STRAW）](https://arxiv.org/pdf/1606.04695.pdf)
- [FeUdal Networks for Hierarchical Reinforcement Learning](https://arxiv.org/pdf/1703.01161.pdf)
- [Data-Efficient Hierarchical Reinforcement Learning（HIRO）](https://proceedings.neurips.cc/paper/2018/file/e6384711491713d29bc63fc5eeb5ba4f-Paper.pdf)
- DDPG 應用在 Option 上
- [State-Temporal Compression in Reinforcement Learning with the Reward-Restricted Geodesic Metric](https://ieeexplore.ieee.org/document/9387144)
- 壓縮 State-Temporal 空間
- 提出 Reward-Restricted Geodesic Metric（RRG）
- Q-Learning based RL 演算法

[回目錄](#Reinforcement-Learning（增強學習）整理)

Exploration
---
- 如何探索一些未知的領域？
- 前面都已經略略有提到了
- [Exploration Strategies in Deep Reinforcement Learning](https://lilianweng.github.io/posts/2020-06-07-exploration-drl/)
- 參考這篇，寫得很好

### Stochastic Policy

#### Classic Exploration Strategies
- ε-greedy
- Boltzmann Exploration（sample $a$ from $\pi(a|s)$）
- Energy-based model
- $p(x) \propto e^{f(x)}$
- $\displaystyle p(x) = \frac{e^{f(x)}}{\sum_{t} e^{f(t)}}$，令 $\displaystyle Z = \sum_{t} e^{f(t)}$，$\displaystyle p(x) = \frac{1}{Z}e^{f(x)}$
- Softmax $\sigma(f(x)) := p(x)$，為波茲曼分佈
- Soft 的名字由來，是因為 Softmax
- Energy-based model 研究上常見
- 像是 Soft Actor-Critic、Soft Q-Learning
- [波茲曼分布](https://zh.wikipedia.org/wiki/%E7%8E%BB%E5%B0%94%E5%85%B9%E6%9B%BC%E5%88%86%E5%B8%83)（統計力學）
- 粒子處於特定狀態（能量）下的機率
- $P(state) \propto e^{-\frac{E}{kT}}$，$E$ 是能量，$T$ 是溫度，$k$ 是波茲曼常數
- $P(state) = \sigma(-\frac{E(state)}{kT})$
- 以下使用 [Canonical ensemble（正則系綜）](https://en.wikipedia.org/wiki/Canonical_ensemble)
- $P(state) = e^{\frac{F - E}{kT}}$
- 同狀態粒子能量 $E(state) = F - kT\ln P(state)$
- 巨觀來看，$U = E[E(state)] = F + TE[-k \ln P(state)] = F + TS$
- 其中 $U$ 為[內能](https://zh.wikipedia.org/zh-tw/%E5%86%85%E8%83%BD)，$F$ 為[亥姆霍茲自由能](https://zh.wikipedia.org/zh-tw/%E4%BA%A5%E5%A7%86%E9%9C%8D%E5%85%B9%E8%87%AA%E7%94%B1%E8%83%BD)，$T$ 為溫度，$S$ 為[熵（Entropy）](https://zh.wikipedia.org/zh-tw/%E7%86%B5)
- $U = E[E(state)]$
- $S = E[-k \ln P(state)]$
- $\displaystyle \Delta S := \frac{\Delta Q}{T}$，$Q$ 為熱量
- 絕熱環境、等溫條件下，$\Delta U = 0 = \Delta F + T \Delta S$
- 自由能會被消耗讓 Entropy 增加，達成熱平衡
- 在給定 states、每種 state 對應的能量 $E(state)$、限制總能量不變之下，找到 state 對應到的機率分佈 $P(state)$，使得 Entropy $H(P)$ 最大，根據熱力學第二定律，就是達到熱平衡的結果（Entropy 變化為 0），這樣的 $P$ 求出來就是波茲曼分布
- 參考：[玻尔兹曼分布与Softmax的关联](https://zhuanlan.zhihu.com/p/286724281)
- [The Wallis derivation](https://en.wikipedia.org/wiki/Principle_of_maximum_entropy#The_Wallis_derivation)
- 有推導，用到 Stirling Approximation
- 實驗導出溫度的影響，會影響分佈的集中程度
- 想要選擇 Entyopy 最大的結果
- 選 $\pi^*(a|s) = arg\max\limits_\pi H(\pi(\cdot|s)) = arg\max\limits_\pi E_{a \sim \pi(a|s)}[-\ln \pi(a|s)]$
- 我們使用 $E(s,a) = F - kQ(s,a)$
- 等價於 $e^{-\frac{E(s,a)}{kT}} \propto e^{\frac{Q(s,a)}{T}}$
- 累積獎勵 $Q(s,a)$ 值越大則能量越小，越安定，出現機率越大
- 溫度 T 越高會增加不安定性（更容易探索）
- 套用 $\pi(a|s) \propto e^{\frac{Q(s,a)}{T}}$，固定 $T$，$\pi^*(a|s)= arg\max\limits_\pi E_{a \sim \pi(a|s)}[Q^\pi(s,a)] = arg\max\limits_\pi V^\pi(s)$
- 照這樣的分佈去選擇，會是可以得到最高期望累積獎勵的
- 論文
- [Boltzmann Exploration Done Right](https://proceedings.neurips.cc/paper/2017/file/b299ad862b6f12cb57679f0538eca514-Paper.pdf)

#### Maximum Entropy RL Frameworks
- 像是 Soft Actor-Critic（SAC）
- 延伸自 DDPG
- 對整個過程，而不只是單一 Action 的選擇

### Novelty Intrinsic Reward

#### Prediction-based Exploration
- 看是不是我沒怎麼看過的（預測不太出來）
- ICM：Intrinsic Curiosity Module
- 前面有整理了（[Reward Shapping](#Reward-Shapping)）
- 論文：[Curiosity-driven Exploration by Self-supervised Prediction](https://arxiv.org/pdf/1705.05363.pdf)
- Measure the Model Uncertainty
- 論文：[VIME: Variational Information Maximizing Exploration](https://arxiv.org/pdf/1605.09674.pdf)

#### Count-based Exploration
- 看 state 出現的次數
- 論文：[Unifying Count-Based Exploration and Intrinsic Motivation](https://arxiv.org/pdf/1606.01868.pdf)
- Counting After Hashing
- 論文：[#Exploration: A Study of Count-Based Exploration for Deep Reinforcement Learning](https://arxiv.org/abs/1611.04717)
- Neural Density Model
- PixelRNN
- 論文：[Pixel Recurrent Neural Networks](https://arxiv.org/pdf/1601.06759.pdf)
- PixelCNN
- 論文
- [Count-Based Exploration with Neural Density Models](https://arxiv.org/pdf/1703.01310.pdf)
- [Conditional Image Generation with PixelCNN Decoders](https://arxiv.org/pdf/1606.05328.pdf)

#### Random Networks
Task-Independent MDP
- Directed Outreaching Reinforcement Action-Selection（DORA）
- 論文：[DORA The Explorer: Directed Outreaching Reinforcement Action-Selection](https://arxiv.org/pdf/1804.04012.pdf)
- Random Network Distillation（RND）
- 論文：[Exploration by Random Network Distillation](https://arxiv.org/pdf/1810.12894.pdf)
- 原理：利用一個隨機生成但是固定的網絡為基準，還有一個去預測的網絡，這是要學習的，去比對目前狀態是不是沒有看過，作為內部獎勵，因為如果沒有看過就會跟隨機的固定網絡差很多
- 效果很好，比較適用在跨回合、較沒有外部獎勵的狀況

### Memory-based Exploration

#### Episodic Memory
- Never Give Up（NGU）
- 結合短期（單回合）與長期（跨回合，Life-Long）
- 論文：[Never Give Up: Learning Directed Exploration Strategies](https://arxiv.org/pdf/2002.06038.pdf)
- Episodic Curiosity（EC）
- 用 Memory 中兩個 state 經過幾個 step 可以 reach 到取代原本歐式距離
- 生成 Reward 的架構圖：
- 可以解決 [Noisy-TV 問題](https://lilianweng.github.io/posts/2020-06-07-exploration-drl/#the-noisy-tv-problem)
- 論文：[Episodic Curiosity through Reachability](https://arxiv.org/pdf/1810.02274.pdf)

#### Direct Exploration
- Go-Explore
- 解決 hard-exploration 問題（分離或出軌）
- 分兩部分（Explore until solved、Robustification）
- 效果很好！
- 論文
- [Go-Explore: a New Approach for Hard-Exploration Problems](https://arxiv.org/pdf/1901.10995.pdf)
- [Self-Imitation Learning（SIL）](https://arxiv.org/pdf/1806.05635.pdf)
- [Memory Based Trajectory-conditioned Policies for Learning from Sparse Rewards](https://arxiv.org/pdf/1907.10247.pdf)
- [First return, then explore](https://arxiv.org/pdf/2004.12919.pdf)
- Go-Explore 進化版，用到 SIL
- [Directed Exploration for Reinforcement Learning](https://arxiv.org/pdf/1906.07805.pdf)
- 也提出類似概念

### Q-Value Exploration
- Bootstrapped DQN
- Bootstrapping（統計學）：一種從給定訓練集中「有放回」的均勻抽樣
- 論文：[Deep Exploration via Bootstrapped DQN](https://arxiv.org/pdf/1602.04621.pdf)

### Unsupervised RL / Varitional Options（變分動作組）

Option：一連串的動作，常見於 HRL（Hierarchical Reinforcement Learning）

- Variational Intrinsic Control（VIC）
- 以 Option 為基礎
- 最大化可以到達的 states（用到 Mutual Information）
- 越精準知道 Option 最後會到哪裡
- 論文：[Variational Intrinsic Control](https://arxiv.org/pdf/1611.07507.pdf)
- Diversity is all you need（DIAYN）
- 容易適應新環境
- 用 Hierarchical RL 解決複雜任務
- 學像專家
- 論文：[Diversity is All You Need: Learning Skills without a Reward Function](https://arxiv.org/pdf/1802.06070.pdf)
- 參考：[Meta Reinforcement Learning - Learning with Random Rewards](https://lilianweng.github.io/posts/2019-06-23-meta-rl/#learning-with-random-rewards)
- Variational Auto-encoding Learning of Options by Reinforcement（VALOR）
- Policy：是一個 Encoder，從 Noise Distribution 轉換到 Trajectories
- Decoder：從 Trajectories 轉換到 Noise Distribution
- 用 VAE 的方式去衡量
- 論文：[Variational Option Discovery Algorithms](https://arxiv.org/pdf/1807.10299.pdf)

[回目錄](#Reinforcement-Learning（增強學習）整理)

Imitation Learning（模仿學習）
---
又稱 Learning by demonstration

使用時機：沒有 Reward 時

- 只能透過專家示範來學習什麼是好，什麼是不好
- 例子：自駕車、Chat Bot

### Behavior Cloning（BC）

訓練一個 Actor 模仿專家的 demo

其實就是 Supervised Learning

對於專家比較不會遇到的狀況，需要 Data Aggregation

另一個問題：有時候機器只學到不該學的（像是賈伯斯的邋遢）

蝴蝶效應（失之毫釐，差之千里）
對於稍微一點不同的 policy 機率分佈，可能造成很大的誤差

### Inverse Reinforcement Learning（IRL）

現在有專家示範，要反推 reward

==原則：學生不能高過老師==

可以用 Maximum causal entropy IRL：

與 GAN 的關係
其實實作時應該可以不用 TRPO，可以用 PPO 取代，只是把 PPO 中的 Advantage 換成這邊定義的 Q，然後後面的 H 不管他

複習一下 Generative Models：

論文：
- [Generative Adversarial Imitation Learning（GAIL）](https://arxiv.org/pdf/1606.03476.pdf)
- 用類似 GAN 的想法繞過 reward 這關
- [Learning Robust Rewards with Adversarial Inverse Reinforcement Learning（AIRL）](https://arxiv.org/pdf/1710.11248.pdf)
- 對 GAIL 做了點修改
- 比 GAIL 較擅長於 generalizaion
- [Variational Discriminator Bottleneck: Improving Imitation Learning, Inverse RL, and GANs by Constraining Information Flow（VAIL、VAIRL）](https://arxiv.org/pdf/1810.00821.pdf)
- 提出 latent distribution $p_E(z|x)$ 來 Encode state
- [One-Shot High-Fidelity Imitation: Training Large-Scale Deep Nets with RL（MetaMimic）](https://arxiv.org/pdf/1810.05017.pdf)
- [Adversarial Option-Aware Hierarchical Imitation Learning（Option-GAIL）](https://arxiv.org/pdf/2106.05530.pdf)

與 Setence Generation 的關係
- Maximum likelihood 對應到 Imitation learning 就是 Behavior cloning
- Sequence GAN 對應到的就是 IRL
- 論文：[SeqGAN: Sequence Generative Adversarial Nets with Policy Gradient](https://arxiv.org/pdf/1609.05473.pdf)

不同的 Expert 會訓練出不同的風格

### Third Person Imitation Learning

機器人看著人去學（第三人稱的角度）

Domain-Adversarial Training 的技術：
Train 一個 feature extractor，讓機器無法分辨它是來自那一個domain。同理，希望利用 feature extractor 讓機器的第一人稱、第三人稱視野所看到的東西一樣，只抽出重要的資訊。

論文：[Third-Person Imitation Learning](https://arxiv.org/pdf/1703.01703.pdf)

看到畫面就達到目標：

機器會在心裡想一些目標，然後達到這些目標

論文：
- [Visual Reinforcement Learning with Imagined Goals](https://arxiv.org/pdf/1807.04742.pdf)
- [Skew-Fit: State-Covering Self-Supervised Reinforcement Learning](https://arxiv.org/pdf/1903.03698.pdf)

[回目錄](#Reinforcement-Learning（增強學習）整理)

Multi-Agent Reinforcement Learning（MARL）
---


### MAPG（Multi-Agent Policy Gradients）

論文：
- [Counterfactual Multi-Agent Policy Gradients（COMA）](https://arxiv.org/pdf/1705.08926.pdf)

### MADDPG（Multi-Agent DDPG）

論文：
- [Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environments](https://arxiv.org/pdf/1706.02275.pdf)

### Q-MIX

論文：
- [QMIX: Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learning](https://arxiv.org/abs/1803.11485)

### MA-POCA (MultiAgent POsthumous Credit Assignment)

論文：
- [On the Use and Misuse of Absorbing States in Multi-agent Reinforcement Learning](http://aaai-rlg.mlanctot.info/papers/AAAI22-RLG_paper_32.pdf)

### MAIL（Multi-Agent Imitation Learning）

演講：Microsoft - Deep Generative Models for Imitation Learning and Fairness
- [Youtube - Deep Generative Models for Imitation Learning and Fairness](https://www.youtube.com/watch?v=rMruz9vIbSQ)
- [Slides - Deep Generative Models for Imitation Learning and Fairness](https://www.microsoft.com/en-us/research/uploads/prod/2018/12/Deep-Generative-Models-for-Imitation-Learning-and-Fairness-SLIDES.pdf)
- 論文
- [Multi-agent Generative Adversarial Imitation Learning（MAGAIL）](https://arxiv.org/pdf/1807.09936.pdf)
- [Learning Fair and Controllable Representations](https://arxiv.org/pdf/1812.04218.pdf)

[回目錄](#Reinforcement-Learning（增強學習）整理)