State Abstraction in RL

來自專欄強化學習1 人贊了文章

本文基於[1] Abstraction Selection in Model-Based Reinforcement Learning.

簡介

在機器學習中，由於特徵空間的維度往往很大，很難進行分類或回歸學習。這時候，考慮到特徵的一些冗餘性和稀疏性，人們往往先對特徵進行降維(如主要成分分析PCA)，然後在低維空間進行學習，(在樣本量不是特別大的時候)，往往會取得好的效果。

在強化學習中，類似的想法就是狀態抽象(State Abstraction)。馬爾科夫決策過程 M = <S, A, P, R, gamma> 是一個很好的序列決策框架，但是在現實問題中，由於狀態空間 S 往往很大(如32x32x3的彩色圖，其狀態空間大小為 255^{32 imes32 imes3} ）；即使是深度增強學習這樣強大的演算法也往往需要很大的樣本(往往>10k，甚至100k)才能在簡單問題上學到不錯的策略，見[2]Human Level Control Through Deep Reinforcement Learning。

如果我們將一些狀態進行「歸類」，那麼可以想到，如果 s_1, s_2 都對應新的狀態表示 s , 那麼 s_1, s_2 的樣本都可視為 s 的樣本，這樣採樣效率與樣本數量便大大增加了。同時，由於狀態空間的減小，無論是基於Tabular的方法，還是基於Approximation的方法，其學習效率也將大大提高。

由5個狀態組成的MDP可(按某種映射)抽象成只有2個狀態的MDP

作為一個例子，考慮兩種極端的情況。首先，假設原始空間 S 經過映射 h 後，新的狀態空間為 h(S) 。第一個極端的例子(coarse abstraction)，如果 h(S) 僅包含一個狀態，也就是說， h 把所有原始狀態映射為了一個狀態，那麼可想而知，狀態空間是縮小了，但在新的狀態空間 h(S) 下學習到策略 pi_h 很難在原始空間下進行應用。另一個極端的例子(finer abstraction)，如果 |h(S)| = |S| ，也就是經過抽象後，原始空間的大小不變，(在沒有額外吸引人的性質下)，學習問題的複雜度不能減小，抽象的意義也就不存在了。

問題表述

馬爾科夫決策過程用 M = <S, A, P, R, gamma> 進行表示，用 V^pi_M(s), Q^pi_M(s,a), V^*_M(s), Q^*_M(s,a) 分別表示策略 pi 的值函數，價值函數，和最優值函數，最優價值函數。

抽象映射用 h: S mapsto h(S) 進行表示。模型 M 給定的情況更容易處理，但在這裡考慮模型 M_D^h 是從固定的數據集 D={(s_i,a_i,r_i,s_i) }_{{i=1, cdots, n}} 進行極大似然後學習到的。所以抽象空間的馬爾科夫決策過程表示為 M_D^h = <h(S), A, P^h_D, R^h_D, gamma> 進行表示。

根據上面的介紹，我們想要選擇一個比較好的抽象映射 h ，使得在抽象空間學習到的最優策略 pi^*_{M^h_D} 能夠在原始模型 M 中很好的適用。所以，目標函數為：

\ min_h L(h, D) = || V^*_M(s) - V_M^{pi^*_{M^h_D}} ||_{infty}

在進行優化求解之前，根據我們對上面兩個極端的例子的思考，直覺告訴我們：如果樣本數 n 很大，我們偏向於一個finer abstraction(with low approximation error)；如果樣本數 n 較小，我們偏向於一個coarse abstraction(with low estimation error)。

理論分析

首先，根據上述符號約定，進行抽象空間下 P^h 和 R^h 的定義(省略了下標 D ）。

P^h(x, a, x) = frac{sum_{s in h^{-1}(x)} p(s,a) sum_{s in h^{-1}(x)}P(s, a, s)}{sum_{s in h^{-1}(x)} p(s,a)}

R^h(s,a) = frac{sum_{s in h^{-1}(x)} p(s,a) R(s,a)}{sum_{s in h^{-1}(x)} p(s,a)}

(簡單理解， p(s,a) 代表了 s in h^{-1}(x) 對抽象狀態 x 的貢獻比例）

下一步可以定義模型的預測誤差項(approximate homomorphism)；分為transition error和reward error。

epsilon_T^h = max_{s in S, a in A} sum_{x in h(S) }|P^h(h(s), a, x) - sum_{s in h^{-1}(s)}P(s, a, s)|

epsilon_R^h = max_{s in S, a in A} |R^h(s,a), R(s,a)|

如果 epsilon_T^h =0, epsilon_R^h=0 , 那麼 M^h 就是對 M 的一個完美的homomorphism，並且 pi^*_{M^h} 也是 M 的一個最優策略。實際情況下， epsilon_T^h, epsilon_R^h 都不會等於0，所以纔有了上面定義的目標函數。下面給出誤差函數的上限。

Theorem 1(Loss bound for a single abstraction). forall h in H, delta in (0, 1) , 以至少 1 - delta 的概率有：

Loss(h, D) leq frac{2}{(1-gamma)^2}(Appr(h) + Estm(h, D, delta))

Appr(h) = epsilon_R^h + frac{gamma R_{max} epsilon_T^h}{2(1-gamma)}

Etsm(h,D, delta) = frac{R_{max}}{1 - gamma} sqrt{frac{1}{2 n^h(D)} log frac{2 |h(S)||A|}{delta}}

n^h(D) = min_{x in h(S), a in A} |D_{x, a}|

Appr(h) 可以看出誤差項由 Appr(h) 和 Estm(h, D, delta) 兩項組成。Appr(h)與 epsilon_T^h, epsilon_R^h 有關但數據集 D 無關； Estm(h, D, delta) 與 epsilon_T^h, epsilon_R^h 無關，但與 h(S), n^h(D) 有關。對於準確的抽象( epsilon_T^h, epsilon_R^h 比較小)，Appr(h) 會比較小，；對於比較簡潔(compact)的抽象( h(S)比較小)，Estm(h, D, delta) 會比較小。

因此，在數據較小的時候，演算法應該偏向coarse abstraction(為了減小estimation error) ；隨著數據集的增大，演算法應該會偏向finer abstraction(為了減小approximation error)。

附錄

關於Theorem 1的證明，參照下一篇文章：State Abstraction in RL(Proof)。

相關文章