本系列文章的[2][3]我們介紹了非貝葉斯框架下bandit和更一般的RL情形下的一些演算法（貪心和UCB演算法）；系列文章[4]我們介紹了貝葉斯框架下bandit情形下的一些演算法（貪心和Thompson Sampling演算法）。本篇文章我們則考察一下在貝葉斯框架下一般情形下的一些RL演算法。

本篇文章主要的參考文獻：

Russo D J, Van Roy B, Kazerouni A, et al. A tutorial on thompson sampling[J]. Foundations and Trends? in Machine Learning, 2018, 11(1): 1-96.

Osband I, Russo D, Wen Z, et al. Deep exploration via randomized value functions[J]. arXiv preprint arXiv:1703.07608, 2017.

1. 更一般的Thompson Sampling

本節我們拓展上次文章介紹的TS演算法到更一般的情形。這裡我們認為action space mathcal{A} 可以是無限維的，然後這裡我們規定每個時刻選擇了一個action a_t 之後，會根據一個條件概率分佈 q_{ heta}(cdot|a_t) 生成一個狀態 s_t ，然後得到reward r_t=r(s_t) . 我們假設 r 函數已知但 heta 未知，也就是說演算法需要邊學習 heta 邊儘可能得到最多的reward。

那麼如果我們的state space維數有限，給定一個 heta 的估計， hat{ heta}, 我們reward的期望可以寫成

mathbb{E}_{q_{hat{ heta}}}[r(s_t)|a_t=a]=sum_{o}q_{hat{ heta}}(o|a)r(o).

假設 heta 的取值範圍有限，如果我們認為 p 是當前對 heta 的belief（後驗分佈，posterior distribution），那麼這個後驗分佈可以根據Bayes rule如此更新：

forall~u,~mathbb{P}_{p,q}( heta=u|a_t,s_t)=frac{p(u)q_u(s_t|a_t)}{sum_v p(v)q_v(s_t|a_t)}.

Algorithm 1: ext{Greedy}(mathcal{A},p,q,r)

  1. for t=1,2,ldotsdo
  2. //estimate model
  3. hat{ heta}_k leftarrow mathbb{E}_p[ heta]
  4. //select and apply action:
  5. a_tleftarrow argmax_k hat{ heta}_{ain mathcal{A}}mathbb{E}_{q_{hat{ heta}}}[r(s_t)|a_t=a]
  6. Apply a_t and observe x_t
  7. //update distribution:
  8. pleftarrow mathbb{P}_{p,q}( hetain cdot|a_t,s_t)
  9. end for

Algorithm 2: ext{TS}(mathcal{A},p,q,r)

  1. for t=1,2,ldotsdo
  2. //sample model
  3. hat{ heta}_k leftarrow hat{ heta}sim p
  4. //select and apply action:
  5. a_tleftarrow argmax_k hat{ heta}_{ain mathcal{A}}mathbb{E}_{q_{hat{ heta}}}[r(s_t)|a_t=a]
  6. Apply a_t and observe x_t
  7. //update distribution:
  8. pleftarrow mathbb{P}_{p,q}( hetain cdot|a_t,s_t)
  9. end for

然後跟上次Bernoulli Bandit的例子非常類似的我們也給出貪心演算法和一般情形的TS演算法的偽代碼（見上）。注意，這兩個演算法的流程和之前一模一樣，只是我們這邊因為是應對更一般的情形，所以偽代碼看起來可能比起之前更加抽象一些。所以，我們這邊再用在線最短路問題（online shortest path）作為例子講解一下。

考慮一個有向圖 G=(V,E) ，點集 V={1,ldots,N}, 邊集 E ，和每條邊上的平均旅行時間（mean travel time） hetain mathbb{R}^E. 方便起見，定義節點 1 為起點，節點 N 為終點。我們要在圖上找最短路，但事先不知道 heta. 我們每個epsiode的action集合 a_t 就是選擇一條從 節點1 到節點 N 的路徑，得到的反饋便是從 heta_e 的分佈中draw出來的sample， s_{t,e},ein a_t. 因為要找最短路，所以reward就可以是 r_t=-sum_{ein a_t}x_{t,e}.

獨立travel time情形：考慮 heta_e 的先驗分佈為彼此獨立的對數高斯分佈，也就是說 log( heta_e)sim N(mu_e,sigma_e^2). 然後我們令 x_{t,e}| heta 對於每條邊彼此獨立，並且 log(s_{t,e}| heta) sim N(log( heta_e)- ilde{sigma}^2/2, ilde{sigma}^2). 那麼我們就有 mathbb{E}[ heta_e]=e^{mu_e+sigma_e^2/2},mathbb{E}[s_{t,e}| heta_e]= heta_e. （所以一開始mean travel time的belief期望就等於 heta_e ）那麼利用Bayes rule我們就有如下更新後驗分佈的簡單公式： forall~ein a_t,

(mu_e,sigma_e^2)leftarrow left( frac{mu_e/sigma_e^2+(log(s_{t,e})+ ilde{sigma}^2/2)/ ilde{sigma}^2}{1/sigma^2+1/ ilde{sigma}^2},frac{1}{1/sigma^2+1/ ilde{sigma}^2} ight).

測試樣例

如上是Russo D J, Van Roy B, Kazerouni A, et al在一個六層的binomial bridge上對Algorithm 1和Algorithm 2做的測試，發現TS大法確實要好於貪心演算法。他們在tutorial中也描述了更複雜的情形：即每個邊上的travel time相關（correlated）。對此，他們引入了帶有factor的高斯貝葉斯假設，可以某種程度上刻畫邊與邊的相關性（比如在binomial bridge裏，下半部分的邊共享一個factor，上半部分的邊共享另一個factor）。這邊我就不再搬運他們的具體操作了，有興趣的同學請見他們的tutorial Example 4.2。

2. RL情形下的TS演算法

細心的同學可能注意到了，雖然第一部分裡面的TS演算法所適用的範圍（包括最短路的例子）是比之前的bandit情形更general了，但還不是一個general的MDP的情形，因此還談不上是真正具有泛用性的RL演算法。這邊主要的問題在於它沒有延遲反饋（delayed feedback），所以不需要考慮顯式的狀態轉移方程（state transition function），因此算不上是一般情形的MDP。

我這麼安排內容自然是有原因的。簡單來說，雖然TS演算法仍然可以被用於一般情形的在線MDP優化，但是卻需要最一些特殊的調整，以保證它仍然可以做到所謂的深度搜索（deep exploration）。具體來說，TS基礎上還需要追加特別的randomization的trick才能在一般情況下有好的performance。

那麼這邊先說明一下naive的使用TS演算法為什麼會fail。我們這裡考慮一個 ext{MDP}(mathcal{S},mathcal{A},H,mathbb{P},r, heta). (對MDP的介紹已經在系列文章[3]，非貝葉斯情形的UCB演算法有介紹了，這裡不多贅述)跟非貝葉斯情形不同的地方就在於這邊還有個latent variable heta 來決定不同的MDP模型。

對此有個很直觀的例子，比如上面那個圖表示的MDP，我們規定只有兩類model，要麼只有在 s_{-N} 或者只有在 s_N 上待的時候有reward 1，其它state上的reward都是0。然後我們讓每個episode的horizon大概就等於 N 。那麼這個時候naive的TS演算法就跪了，因為它在每個episode，每apply一個action（向左/向右）就要重新sample更新policy，這樣的話容易看出期望的有reward的次數是指數時間 Omega(2^N) 。相反，我們更應該做的是每個episode之前sample一次，然後在這個epsiode就fix一個policy，這樣的話如果先驗概率兩個模型一樣，期望 走2N 次我們就能得到reward。當然，這個例子比較極端，所以最優的RL策略也是比較極端的，這只是為了說明之前在最短路里的TS演算法在一般情形行不通，往往像這個例子裏這種更深的exploration是必要的。

本節最後，我們不加細節的說明TS演算法的regret分析大體可以直接從上次的bandit情形拓展過來（套路是完全一樣的，見系列文章[4]）。想研究更多證明細節的可參閱TS tutorial或者比如Russo D, Van Roy B. Learning to optimize via posterior sampling[J]. Mathematics of Operations Research, 2014, 39(4): 1221-1243. 細節有時機再補吧hoho

3. 基於TS的RL演算法：Randomized least-squares value iteration（RLSVI）

嗯其實到這邊我其實還沒系統介紹過RL/DP的基礎演算法。這裡先稍微過一下一些基本的東西，比如先說說value iteration（VI）。這其實不算RL，在DP（動態規劃）裡面也是最基本的演算法了。

它的思路非常簡單，就是通過不動點迭代的方式得到最優的value function（這種演算法是無法直接算得最優的policy的，後者需要另一類叫做policy iteration的演算法，以後介紹）。具體來說，VI演算法偽代碼如下（notation不熟悉的請見系列文章[3]！）。

Algorithm 3: VI

  1. for h=0,ldots,H-1 do
  2. Compute Q_{h+1}^*(s,a)leftarrow r_h+mathbb{P}_hmax_{ain mathcal{A}}Q_h^*(s,a), forall ~ sin mathcal{S},ain mathcal{A}.
  3. end for
  4. return Q_H^*.

實際中如果問題規模較大，我們一般沒法run完整的VI，這個時候我們要對value function進一步做近似，這也是近似動態規劃（ADP）的基本技巧。我們這邊考慮最簡單的近似技巧，利用least squares regression去近似。具體來說，對一類value function mathcal{Q}={Q_ heta:mathcal{S} imesmathcal{A} ightarrow mathbb{R} ~forall heta } ，我們如果觀察到了data mathcal{D}={ (s_t,a_t,r_t,s_t,t) } ，和一個所謂的目標值 heta^-, 我們可以定義empirical temporal difference (TD) loss：

mathcal{L}( heta; heta^-;mathcal{D}):=sum_{tin mathcal{D}} left( r_t+max_{ain mathcal{A}}Q_{ heta^-}(s_t,a)-Q_ heta(s_t,a_t) ight)^2 .

注意，我們知道ADP/RL裏的一個結果，如果 mathcal{Q} spans Q^* 且 mathcal{D} 就是從MDP draw出來的，我們就知道 mathcal{L} 的minimizer就是VI(Algorithm 3)的解。詳細推導可見比如Sutton and Barto的RL書，或者我之後可能也會具體寫。

我們令 heta^p 為 heta 的一個prior（比如線性系統裏我們可以有prior hetasim N( heta^p,lambda I) ），定義一個回歸正則項 mathcal{R}( heta; heta^p):=lambda | heta^p- heta|_2^2. 然後我們就給出所謂least sqaures value iteration(LSVI)的偽代碼。

Algorithm 4: LSVI

  1. Draw ilde{mathcal{D}}sim underlying MDP
  2. Draw prior ilde{ heta}^psim prior distribution
  3. for h=0,ldots,H-1 do
  4. Compute ilde{ heta}_{h+1} leftarrow argmin_{ heta in mathbb{R}^D}left( mathcal{L}( heta; ilde{ heta}_h, ilde{D})+mathcal{R}( heta; ilde{ heta}^p) ight)
  5. end for
  6. return ilde{ heta}^H.

那麼我們就知道LSVI和VI其實非常相像。而最大的區別除了使用least squares近似value function以外，VI是需要知道MDP整體的信息的，而這邊LSVI卻只需要利用收集到的data進行演算法迭代就可以了。這也是現在所謂RL/ADP和傳統DP（動態規劃）演算法的最本質的區別。

那麼我們的RLSVI相比LSVI其實就一點區別，在draw data的時候加上了randomization。具體來說，我們現在所謂randomized的data sample就可以變成 [(s_t,a_t,r_t+z_t,s_t,t)~forall t,z_tsim N(0,v)] （人為加入了Gaussian noise）. 當然這並不是唯一一種人為randomization的方法，其它比如Boostrap也是很顯然的一種。

最後，我們不加說明的給出以下理論結果。這是目前唯一的，對一般情形的貝葉斯RL演算法（當然還是有一些assumption需要），能證明多項式regret的結果（RLSVI演算法）。

有興趣的同學可參閱本文第二篇參考文獻讀證明，這邊主要我還沒開始系統介紹RL理論所以感覺解釋它的proof目前意義還不大。可能之後再補了。

下篇文章會把MAB部分完結，最後再花幾篇文章稍微系統地講解下RL演算法的理論體系。感謝你看到最後。

推薦閱讀：

相關文章