Flink + 強化學習 搭建實時推薦系統

如今的推薦系統，對于實時性的要求越來越高，實時推薦的流程大緻可以概括為這樣： 推薦系統對于使用者的請求産生推薦，使用者對推薦結果作出回報 (購買/點選/離開等等)，推薦系統再根據使用者回報作出新的推薦。這個過程中有兩個值得關注的地方：

• 這可被視為是一個推薦系統和使用者不斷互動、互相影響的過程。
• 推薦系統需要對使用者回報作出快速及時的響應。

這兩點本篇分别通過強化學習和 Flink 來實作，而在此之前先了解一些背景概念。

強化學習

強化學習領域的知名教材 《Reinforcement Learning: An Introduction》開篇就寫道：

當我們思考學習的本質的時候，腦中首先聯想到的可能就是在與環境不斷互動中學習。當一個嬰兒在玩耍、揮舞手臂或是旁顧四周時，并沒有任何老師教它，但它确實能直接感覺到周圍環境的變化。

強化學習的主要過程是建構一個智能體，使之與環境互動的過程中不斷學習，以期獲得最大的期望獎勵。它是一種非常通用的學習範式，可以用于對各種各樣問題的模組化，比如遊戲、機器人、自動駕駛、人機互動、推薦、健康護理等等。其與監督學習的主要不同點在于：強化學習根據延遲的回報通過不斷試錯 (trial-and-error) 進行學習，而監督學習則是每一步都有明确的回報資訊進行學習。

下圖反映了一個推薦智能體 (recommender agent) 與環境進行互動的過程。這裡将使用者 (user) 視為環境，使用者的行為資料作為狀态 (state) 輸入到智能體中，智能體據此作出相應的動作 (action) ，即推薦相應的物品給使用者，使用者對此推薦的反應如點選/不點選、購買/不購買等可視為新一輪的獎勵。從這裡可以看出，推薦可被認為是一個動态序列決策過程，推薦物品對使用者産生影響，進而使用者的回報反過來影響推薦系統的決策本身，這樣的過程會不斷延續下去形成一個序列。

“決策” 這個詞實際上很能代表強化學習本身的特點。設想當一個人在做決策的時候，很多時候需要對瞬息萬變的局勢進行評估并快速作出相應的選擇，而另一方面，作出的決定需要考慮長期的目标而非僅僅是短期收益。而這兩點恰恰是幾乎所有用強化學習做推薦系統的論文中都會提到的關于傳統推薦方法的問題，即将推薦視為靜态預測的過程以及隻注重短期收益等等。當然論文裡這麼說主要是為了凸顯自己的成果，但實際的情況應該遠不是這麼簡單。

強化學習的最終目标是學習出一個政策 \(\pi(\bold{a}|\bold{s})\) 來最大化期望獎勵。政策 (policy) 指的是智能體如何根據環境狀态 \(\bold{s}\) 來決定下一步的動作 \(\bold{a}\)，對應到推薦的場景中就是根據使用者過往行為記錄來決定下一步推薦的物品。對于如何通過訓練得到最優政策，目前主流有兩類方法: on-policy 和 off-policy 。不同于監督學習的需要預先人工收集資料并标注，強化學習的資料來源于不斷地與環境進行互動，繼而用收集來的資料更新模型。是以在這個過程中有兩個部分與政策相關，一是與環境互動時需要使用政策，二是訓練時更新政策。On-policy 指的是環境互動的政策和訓練時更新的政策是同一個政策，相應地 off-policy 則是互動和更新時使用的是不同的政策。如下左圖為 on-policy，下中圖為 off-policy (下右圖為 offline 方法，後文再述 )。

On-policy 的思想比較直覺，相當于一個智能體在環境中邊試錯邊學習，但是其主要問題是樣本使用率低，進而訓練效率低。使用了一個政策與環境進行互動取得資料進而更新模型後，就産生了一個新的政策，那麼舊政策互動得來的資料可能就不服從新政策的條件分布了，是以這些資料不能再使用會被丢棄。

Off-policy 則緩解了這個問題，主要通過将之前政策收集來的資料通過一個經驗回放池 (experience replay buffer) 儲存起來，然後從中采樣資料進行訓練。那麼 off-policy 類方法為什麼能使用舊政策産生的資料進行訓練？ 既然資料分布不同導緻新舊資料不能放一起訓練，那就調整資料分布使之接近就可以了，是以 Off-policy 類的算法普遍采用了重要性采樣的思想對不同資料施加不同的權重，後文介紹 YouTube 的推薦系統時會提到，到那時再說。

那麼本篇的強化學習方法适用于哪一種呢？ 這其實不大好說。。 我沒有能互動的環境，隻有靜态資料集，是以 off-Policy 看上去更适合一些，但即使是 off-policy 的方法通常也需要與環境進行互動不斷産生新資料用于訓練。是以本篇的方法屬于 batch reinforcement learning，或稱 offline reinforcement learning，不過我傾向于使用 batch 這個詞，因為 offline 和 off-policy 很容易混淆。上右圖顯示的就是 batch (offline) reinforcement learning，其特點是一次性收集完一批資料後就隻用這批資料進行訓練，在正式部署之前不再與環境作任何互動。

我們知道深度學習近年來在圖像和 NLP 領域取得了很大的進展，一大原因是算力和資料的爆炸式增長。然而對于主流的深度強化學習算法來說，需要不斷與環境進行互動來擷取資料，這通常意味着需要邊訓練邊收集資料。然而許多領域是無法像傳統強化學習那樣有條件頻繁與環境進行互動的，存在成本太高或者安全性太低的原因，甚至會引發倫理問題，典型的例子如無人駕駛和醫療。是以這時候人們自然會去想，訓練強化學習時也收集一堆固定的資料，然後不斷重複利用，不再收集新的，仿照深度學習那樣在固定資料集上大力出奇迹，這樣是否可行呢？ 是以 batch reinforcement learning 近年來受到越來越多學術界和工業界的關注，被廣泛認為是實作強化學習大規模應用到實際的一個有效途徑。而推薦系統就很适合這種模式，因為直接線上探索互動代價太大，影響使用者體驗，但收集使用者行為日志卻相對容易且資料量大。

Flink

另一方面，推薦系統作為一個系統，光有算法肯定是不行的。上文提到 batch reinforcement learning 無需與環境互動，僅靠資料集就能訓練，那麼在訓練完模型真正上線以後就需要與環境互動了，而這個過程中需要有中間載體，用于快速獲得資訊、清洗原始資料并轉化成模型可輸入的格式。在本篇中這個前道工序我們主要使用 Flink。Flink 官網上的自我介紹是 ”資料流上的有狀态計算 (Stateful Computations over Data Streams)“：

換言之随着資料的不斷流入，其可以儲存和通路之前的資料和中間結果，當到達特定的條件後一并計算。對于我們的強化學習模型來說，需要累計一定的使用者行為才能作為模型輸入作推薦，是以需要在 Flink 中實時儲存之前的行為資料，這就要用到 Flink 強大的狀态管理功能。

另外，離線訓練使用的深度學習架構是 PyTorch，這個不像 Tensorflow 那樣部署友善，是以這裡采用近年來流行的 FastAPI 做成 api 服務，在 Flink 中擷取滿足條件的特征後直接調用服務進行推理，産生推薦後存到資料庫中，伺服器在下次使用者請求時可直接從資料庫中調用推薦結果。

整體架構見下圖， 完整代碼和流程見 FlinkRL (https://github.com/massquantity/flink-reinforcement-learning) 和 DBRL (https://github.com/massquantity/DBRL) 。

下面介紹使用的三種算法，限于篇幅，這裡僅僅大緻介紹原理，欲了解細節可參閱原論文。下面是主要符号表：

• \(s \in \mathcal{S} \;\qquad\qquad\) 狀态 (state)
• \(a \in \mathcal{A} \qquad\qquad\) 動作 (action)
• \(r \in \mathcal{R} \,\qquad\qquad\) 獎勵 (reward)
• \(P(s'\vert s, a) \;\;\;\;\qquad\) 轉移機率 (transition probability)，從狀态 \(s\) 采取動作 \(a\) 後轉移到下一個狀态 \(s'\) 的機率
• \(\tau \qquad\qquad\qquad\) 有多種名稱：軌迹 (trajectory)，回合 (episode)，試驗 (trial)
• \(R \;\;\;\;\;\;\qquad\qquad\) 總回報 (return)，\(R(\tau)\) 表示軌迹 \(\tau\) 的總回報
• \(\pi(a \vert s) \;\qquad\qquad\) 随機性政策 (stochastic policy)
• \(\mu(s) \;\;\;\qquad\qquad\) 确定性政策 (deterministic policy)
• \(\gamma \qquad\qquad\qquad\) 折扣因子 (discount factor)，\(\gamma \in [0,1]\)

YouTube Top-K (REINFORCE)

這個方法主要參考 YouTube 2018 年發表的論文 Top-K Off-Policy Correction for a REINFORCE Recommender System 。論文作者在這個視訊中宣稱這個方法取得了近兩年來的最大增長，說實話我是有點懷疑的。在論文最後的實驗部分提到，這個強化學習模型隻是作為衆多召回模型之一，然後所有的召回物品再經過一個獨立的排序子產品後推薦給使用者，文中也沒說這個排序子產品用的是什麼模型，是以這裡面的空間就比較大了。

論文中使用了 policy gradient 領域最古老的 REINFORCE 算法，并就其具體業務情形做了一些改動，這裡我們先看 REINFORCE 的基本架構。

假定執行的是随機政策，智能體在環境中互動産生的一個軌迹為 \(\tau = (s_0,a_0,s_1,a_1,r_1,\cdots,s_{T-1},a_{T-1},s_T,r_T)\) 。在深度強化學習中一般使用神經網絡來參數化政策 \(\pi\)，一般會在環境中采樣多個軌迹，那麼該政策的期望總回報為：

\[J(\pi_\theta) = \mathbb{E}_{\tau \sim \pi_\theta}[R(\tau)] = \mathbb{E}_{\tau \sim \pi_\theta}\left[\sum\limits_{t=0}^{|\tau|} r(s_t, a_t)\right] \tag{1.1}

\]

其中 \(\theta\) 是神經網絡的參數，$R(\tau) $ 為軌迹 \(\tau\) 的總回報，因為軌迹帶有随機性，是以我們希望最大化期望回報來獲得最優的政策 \(\pi ^*\)：

\[\pi^* = \arg\max_{\pi_\theta}J(\pi_\theta)

REINFORCE 的思想，或者說整個 policy gradient 的思想，和監督學習中的很多算法殊途同歸，即通過梯度上升 (下降) 法求參數 \(\theta\) ，把 \((1.1)\) 式當成目标函數，那麼一旦有了梯度，就可以用這個熟悉的式子進行優化了：

\[\theta_{t+1} = \theta_t + \alpha \nabla_\theta J(\pi_\theta)

直接求 \(J(\pi_\theta)\) 的梯度異常困難，但是通過 policy gradient 定理，我們可以得到一個近似解：

\[\nabla_{\theta}J(\pi_\theta) = \sum\limits_{\tau \sim \pi_\theta}R(\tau)\nabla_{\theta} \text{log}\,\pi_{\theta}(\tau) \approx \sum\limits_{\tau \sim \pi_\theta} \left[\sum\limits_{t=0}^{|\tau|} R_t \nabla_{\theta}\text{log}\,\pi_{\theta}(a_t|s_t) \right] \tag{1.2}

其中 \(R_t = \sum_{t'=t}^{|\tau|} \gamma^{t'-t}r(s_{t'}, a_{t'})\) ，意為 \(t\) 時刻采取的動作獲得的最終回報隻與之後獲得的獎勵有關，而與之前的獎勵無關。 關于 policy gradient 定理的證明見附錄 A 。

原始的 REINFORCE 算法是 on-policy 的，亦即線上互動和實際優化的是同一個政策，然而論文中說他們線上互動的是不同的政策，甚至是多種不同政策的混合體。這樣就導緻了資料分布不一緻，如果直接使用 REINFORCE 會産生巨大的 bias 。論文中通過重要性采樣把算法改造成 off-policy 的：

\[\sum\limits_{\tau \sim \beta} \frac{\pi_\theta(\tau)}{\beta(\tau)} \left[\sum\limits_{t=0}^{|\tau|} R_t \nabla_{\theta}\, \text{log}\,\pi_{\theta}(a_t|s_t)\right]

其中 \(\beta\) 為實際的互動政策，這個式子的推導也可以直接通過 policy gradient 得出，具體見附錄 B 。接下來經過一系列的權衡，作者認為下面這個式子比較合理地平衡了偏差與方差：

\[\sum\limits_{\tau \sim \beta} \left[\sum\limits_{t=0}^{|\tau|} \frac{\pi_\theta(a_t|s_t)}{\beta(a_t|s_t)} R_t \nabla_{\theta}\, \text{log}\,\pi_{\theta}(a_t|s_t)\right] \tag{1.3}

主要的不同就是采樣是沿着 \(\beta\) 的軌迹進行，并在每一步 \(t\) 中加了重要性權重 \(\frac{\pi_\theta(a_t|s_t)}{\beta(a_t|s_t)}\) ，而這個權重相對很容易計算。

論文中考慮的另外一個問題是，之前都是考慮的動作隻有一個，即隻推薦一個物品，但現實中往往是一次性推薦 \(k\) 個物品給使用者，如果 \(k\) 個物品同時考慮就會組合爆炸。論文中假設同時展示 \(k\) 個不重複物品的總獎勵等于每個物品的獎勵之和，這樣就可以轉化為單個物品的優化，同時作者說這個假設成立的前提是使用者對推薦清單中每個物品的觀察是獨立的。

YouTube 在 2019 年發表過另外一篇用強化學習做推薦的論文 (Reinforcement Learning for Slate-based Recommender Systems: A Tractable Decomposition and Practical Methodology) ，和 2018 年中的方法相比，主要的不同是使用了 on-policy 的 SARSA 算法，而且是用在了排序而不是召回階段。這篇論文中同樣對推薦的 \(k\) 個物品作了某種假設： 假設一個推薦清單中使用者隻會消費其中一個物品，如果使用者消費完後又傳回到這個推薦清單消費第二個物品，則這個行為會被視為另外的事件，在日志中分開記錄。 實際上這兩個假設的本質就在于使用者面對 \(k\) 個物品的清單隻會關注其中一個而不管其他，然而實際很多時候使用者會對多個感興趣，但是消費完一個後就把剩餘幾個忘了。極端情況是推薦了 10 個全部都感興趣，消費了一個後有些事離開了或者陷入不斷點選循環消費，這樣原來的另外 9 個感興趣的就都被當成負樣本處理了。。

到這裡我們可以看到，兩篇論文都必須作出一些假設的根本原因在于使用的算法輸出的都是離散型動作，即單個物品，然而推薦的場景不像一般的強化學習應用隻需要輸出一個動作就行了。是以不得不作出一些看上去很别扭的假設，而後面介紹的兩個算法輸出的都是連續型動作，則會有另外的解決辦法。

接下來依然沿着上面的假設走，\(k\) 個就轉化為單個物品了，結合重要性權重後， \((1.3)\) 式可轉化為：

\[\begin{align*}

\nabla_{\theta}J(\theta)

& \approx \sum\limits_{\tau \sim \beta} \left[\sum\limits_{t=0}^{|\tau|} \frac{\alpha_\theta (a_t|s_t)}{\beta(a_t|s_t)} R_t \nabla_{\theta}\text{log}\,\alpha_{\theta}(a_t|s_t) \right] \\[1ex]

&= \sum\limits_{\tau \sim \beta} \left[\sum\limits_{t=0}^{|\tau|} \frac{\alpha_\theta (a_t|s_t)}{\beta(a_t|s_t)} \frac{1}{\alpha_\theta(a_t|s_t)} \frac{\partial \alpha(a_t|s_t)}{\partial \pi(a_t|s_t)} R_t \nabla_{\theta}\,\pi_{\theta}(a_t|s_t) \right] \\[1ex]

&= \sum\limits_{\tau \sim \beta} \left[\sum\limits_{t=0}^{|\tau|} \frac{\pi_\theta (a_t|s_t)}{\beta(a_t|s_t)} \frac{\partial \alpha(a_t|s_t)}{\partial \pi(a_t|s_t)} R_t \frac{\nabla_{\theta}\,\pi_{\theta}(a_t|s_t)}{\pi_\theta (a_t|s_t)} \right] \\

&= \sum\limits_{\tau \sim \beta} \left[\sum\limits_{t=0}^{|\tau|} \frac{\pi_\theta (a_t|s_t)}{\beta(a_t|s_t)} \frac{\partial \alpha(a_t|s_t)}{\partial \pi(a_t|s_t)} R_t \nabla_\theta \text{log} \,\pi_\theta(a_t|s_t) \right] \tag{1.4}

\end{align*}

式中主要是用 \(\alpha_\theta(a_t|s_t)\) 代替了原來的 \(\pi_\theta (a_t|s_t)\)，因為 \(k\) 個物品是各自獨立從政策 \(\pi_\theta\) 中采樣的，則 \(\alpha_\theta(a_t|s_t) = 1 - (1 - \pi_\theta (a_t|s_t))^K\) 表示 \(t\) 時刻物品 \(a\) 出現在最終的 \(k\) 個物品的清單中的機率，因為 $(1 - \pi_\theta (a_t|s_t))^K $ 表示 \(K\) 次都沒有被采樣到的機率。

可以看到 \((1.3)\) 式和 \((1.4)\) 式的唯一差别是多了一個乘子 : \(\frac{\partial \alpha(a_t | s_t)}{\partial\pi(a_t|s_t)} = K(1 - \pi_\theta(a_t|s_t))^{K-1}\) 。是以我們隻要采樣一個軌迹，在每一步 \(t\) 由神經網絡計算出 \(\pi_\theta(a|s), \beta(a|s)\) (這兩個實際就是 softmax 輸出的機率)，再整合計算折扣回報 \(R_t = \sum_{t'=t}^{|\tau|} \gamma^{t'-t}r(s_{t'}, a_{t'})\) 後，就能相應地實作算法了，最終的代碼見 https://github.com/massquantity/DBRL/blob/master/dbrl/models/youtube_topk.py

DDPG

就推薦的場景來說，離散型動作是比較自然的想法，每個動作就對應每個物品。然而現實中物品數量可能至少有百萬級，意味着動作空間很大，用 softmax 計算複雜度很高。上面 YouTube 的論文中使用 sampled softmax 來緩解這個問題，而這裡我們可以換個思路，讓政策輸出一個連續的向量 \(a \in \mathbb{R}^d\) ，再将 \(a\) 與每個物品的 embedding 點乘再排序來獲得推薦清單，線上上則可以使用高效的最近鄰搜尋來擷取相應物品。對于連續型動作而言， DDPG 是比較通用的選擇，在我看過的推薦相關的論文裡使用 DDPG 是最多的，比如京東的兩篇[1][2]，阿裡的一篇[1]，華為的一篇[1] 。

DDPG 全稱 Deep Deterministic Policy Gradient，是一種适用于連續型動作的 off-policy 算法。不同于上文的 REINFORCE，其使用的是确定性政策，顧名思義對于相同的狀态 \(s\) 會産生唯一的動作 \(a\) ，是以這裡我們用 \(\mu(s)\) 來表示。而因為是确定性政策，不存在動作 \(a\) 的機率分布 ，也就不需要重要性采樣了。

DDPG 采用 Actor-Critic 架構，Actor 為具體的政策，其輸入為狀态 \(s\) ，輸出動作 \(a\) 。Critic 用于評估政策的好壞，其輸入為 \((s + a)\) 拼接而成的向量，輸出為一個标量。Actor 和 Critic 都可以用神經網絡來參數化，假設 Actor 網絡為 \(\mu(s|\theta^\mu)\) ，Critic 網絡為 \(Q(s,a|\theta^Q)\) ，則 Actor 和 Critic 的目标函數和梯度分别為：

\[J(\theta^\mu) = \frac{1}{N}\sum\limits_{i=1}^N Q(s,a|\theta^Q) \quad {\Longrightarrow} \quad \nabla_{\theta^u}J(\theta^\mu) = \frac{1}{N} \sum\limits_{i=1}^N\nabla_a Q(s,a|\theta^Q)|_{s=s_i,a=\mu(s_i)} \nabla_{\theta^\mu} \mu(s|\theta^\mu)|_{s=s_i}

\[L(\theta^Q) = \frac{1}{N} \sum\limits_{i=1}^N \left(r_i + \gamma\, Q'(s_{i+1}, \mu'(s_{i+1}|\theta ^{\mu'})|\theta^{Q'}) - Q(s_i,a_i|\theta^Q)\right)^2 \\

\color{blue}\Large\Downarrow \\

\nabla_{\theta^Q} L(\theta^Q) = \frac{2}{N} \sum\limits_{i=1}^N \left(r_i + \gamma\, Q'(s_{i+1}, \mu'(s_{i+1}|\theta ^{\mu'})|\theta^{Q'}) - Q(s_i,a_i|\theta^Q)\right) \nabla_{\theta^Q}Q(s_i,a_i|\theta^Q)

那麼算法的核心就是通過梯度上升 (下降) 優化這兩個目标函數來求得最終的參數，進而得到最優政策。DDPG 其他的一些實作細節如 target network、soft update 等等這裡不再贅述，由于我們使用的是固定的資料集，因而隻要将資料轉化成 DDPG 算法可以輸入的格式，再像監督學習那樣分 batch 訓練就行了，不用再與環境作互動，最終的代碼見 https://github.com/massquantity/DBRL/blob/master/dbrl/models/ddpg.py

BCQ

BCQ 算法全稱 Batch-Constrained Deep Q-Learning ，出自論文 Off-Policy Deep Reinforcement Learning without Exploration 。 BCQ 可以看作是對 DDPG 在 batch (offline) 場景的改造版本，如前文所述，batch (offline) reinforcement learning 指的是在固定的資料集上進行學習，不再與環境進行互動。論文作者指出在這種條件下目前流行的的 off-policy 算法如 DQN、DDPG 等可能效果不會很好，原因主要出在會産生 extrapolation error。

Extrapolation error 主要源于資料集中狀态 \(s\) 和動作 \(a\) 組合的分布和目前政策中狀态-動作組合分布的不一緻，即采樣的政策和目前政策差别很大，進而使得 Critic 對于值函數的估計不準，進而使得學習失效。以上文中 DDPG 的 Critic 網絡的目标函數 (改變了一些符号) 為例：

\[L(\theta^Q) = \left(r + \gamma\, Q'(s', \mu'(s' )) - Q(s,a)\right)^2

因為 \(\mu'\) 本身是一個神經網絡，如果 \(\mu'(s')\) 最終輸出了一個不在資料集内的動作，那麼很可能導緻 \(Q'(s',\mu'(s'))\) 對于該狀态-動作組合的估值不準，那麼就學不到好的政策了。如下圖(來源)就顯示了如果動作 \(a\) 在行為政策 \(\beta\) 的分布之外，會有可能對 \(Q\) 值産生過高的估計，導緻後續錯誤不斷累計。

我在實際訓練 DDPG 的時候确實碰到過類似情況，Critic 的損失有時候會到達 1e8 這樣誇張的級别，不論再怎麼調國小習率都沒用。後來發現可能的原因，最開始是将使用者之前互動過的多個物品向量平均起來作為狀态 \(s\) 的表達，然而平均過後的向量就可能不會長得和任何單個物品向量很像了，也即遠離了原來的資料分布。那麼 \(\mu’(s)\) 輸出的動作 \(a\) 自然也和資料集中的動作相去甚遠，這樣一環傳一環緻使最終 \(Q\) 值爆炸，而後來改為物品向量直接拼接後就沒這種情況了。

另外作者也提到，DQN、DDPG 這樣常見的 off-policy 算法中并沒有考慮 extrapolation error，為什麼它們在正統強化學習任務中很有效呢？ 因為是這些算法本質上采用的是 growing batch learning 的訓練方法： 在用一批資料離線訓練一段時間後，依然會用訓練好的政策去環境中收集新資料用于訓練，這樣采樣來的資料實際上和現有政策差别不大，因而 extrapolation error 可以忽略不計。但是在完全 offline 訓練的情況下，資料集很可能是使用完全不同的政策收集而來的，因而這種時候 extrapolation error 的影響就比較顯著了。

是以問題的核心是如何避免生成一個莫名其妙的狀态-動作組合進而導緻 extrapolation error？論文中的方法是用一個生成模型 (generative model) 來生成和資料集中相似的狀态-動作組合，再用一個擾動模型 (perturbation model) 對生成的動作添加一些噪聲來增加多樣性。其中生成模型使用的是變分自編碼器 (variational auto-encoder, VAE)，擾動模型就是一個普通的全連接配接網絡，輸入為生成出的動作 \(a\) ，輸出為範圍在 \([-\Phi, \Phi]\) 内的新動作，\(\Phi\) 為動作的最大值，對于連續型動作我們一般設定一個上限避免輸出太大的動作值。這兩個模型合起來可視為 BCQ 算法使用的政策，即 Actor，而 Critic 的部分和 DDPG 差别不大，完整代碼見 https://github.com/massquantity/DBRL/blob/master/dbrl/models/bcq.py

Appendix A: Policy Gradient 定理

由 \((1.1)\) 式可知目标函數為：

\[J(\pi_\theta) = \mathbb{E}_{\tau \sim \pi_\theta}[R(\tau)]

而我們想求目标函數關于政策參數 \(\theta\) 的梯度：

\nabla_{\theta} J(\pi_{\theta}) &= \nabla_\theta \,\mathbb{E}_{\tau \sim \pi_\theta}[R(\tau)] \\

&= \nabla_\theta \int P_\theta(\tau) R(\tau) \,\text{d}\tau \\

&= \int \nabla_\theta P_\theta(\tau) R(\tau) \,\text{d}\tau \\

&= \int P_\theta(\tau) \frac{\nabla_\theta P_\theta(\tau)}{P_\theta(\tau)} R(\tau) \,\text{d}\tau \tag{A.1} \\

&= \int P_\theta(\tau) \nabla_\theta \text{log}\,P_\theta(\tau) R(\tau) \,\text{d}\tau \tag{A.2} \\[1ex]

&= \mathbb{E}_{\tau \sim \pi_{\theta}} \left[\nabla_\theta \text{log}\,P_\theta(\tau) R(\tau) \right] \tag{A.3}

其中 \((\text{A.1})\) 到 \((\text{A.2})\) 步使用了

log-trick

，即 \(\nabla \text{log}\,x = \frac{\nabla x}{x}\)

對于軌迹 \(\tau\) ，沿着馬爾科夫決策過程 (Markov Decision Process, MDP) 有：

\[P_\theta(\tau) = \rho_0(s_0) \prod_{t=0}^{T-1} P(s_{t+1}|s_t,a_t)\pi_\theta(a_t|s_t)

因而 \((\text{A.3})\) 中的 \(\nabla_\theta \text{log}\,P_\theta(\tau)\) 為：

\nabla_\theta \text{log}\,P_\theta(\tau) &= \nabla_\theta \left(\text{log}\, \rho_0(s_0) + \sum\limits_{t=0}^{T-1} \left(\text{log} P(s_{t+1}|s_t,a_t) + \text{log}\, \pi_\theta (a_t|s_t) \right)\right) \\

&=\sum\limits_{t=0}^{T-1} \nabla_\theta \,\text{log}\, \pi_\theta (a_t|s_t)

\qquad\qquad \color{fuchsia}{\text{因為$\theta$ 隻與 $\pi_\theta(a_t|s_t)$ 有關}} \tag{A.4}

最後将 \((\text{A.4})\) 式代入 \((\text{A.3})\) ，就是 \((1.2)\) 式了 :

\[\nabla_{\theta} J(\pi_{\theta}) = \mathbb{E}_{\tau \sim \pi_\theta} \left[\sum\limits_{t=0}^{T-1} R(\tau) \nabla_\theta \,\text{log}\, \pi_\theta (a_t|s_t) \right]

Appendix B: 重要性采樣 (Importance Sampling)

設實際的互動政策 \(\beta\) 的軌迹分布為 \(Q_\phi(\tau)\) ，對 \(\text{(A.2)}\) 式應用重要性采樣：

\[\begin{aligned}

& \int P_\theta(\tau) \nabla_\theta \text{log}\,P_\theta(\tau) R(\tau) \,\text{d}\tau \\

=\;\; & \int Q_\phi(\tau) \frac{P_\theta(\tau)}{Q_\phi(\tau)} \nabla_\theta \text{log}\,P_\theta(\tau) R(\tau) \,\text{d}\tau \\[1ex]

= \;\; & \mathbb{E}_{\tau \sim \beta} \left[\frac{P_\theta(\tau)}{Q_\phi(\tau)} \nabla_\theta \text{log}\,P_\theta(\tau) R(\tau) \right] \\[1ex]

= \;\; & \sum\limits_{\tau \sim \beta} \frac{\pi_\theta(\tau)}{\beta(\tau)} \left[ \nabla_\theta \text{log}\,P_\theta(\tau) R(\tau) \right]

\end{aligned}

之後就和附錄 A 的推導一樣了。

References

1. Richard S Sutton, Andrew G Barto, et al. Reinforcement learning: An introduction
2. Minmin Chen, et al. Top-K Off-Policy Correction for a REINFORCE Recommender System
3. Xiangyu Zhao, et al. Deep Reinforcement Learning for List-wise Recommendations
4. Scott Fujimoto, et al. Off-Policy Deep Reinforcement Learning without Exploration

5. Sergey Levine, Aviral Kumar, et al. Offline Reinforcement Learning: Tutorial, Review,

   and Perspectives on Open Problems

6. Eugene Ie , Vihan Jain, et al. Reinforcement Learning for Slate-based Recommender Systems: A Tractable Decomposition and Practical Methodology

/