強化學習（四）：動態規劃

04-04

策略估值

給定馬爾科夫決策過程 $langle S, A, P, R, gamma angle$ 和策略 $pi$ ，有Bellman方程

$egin{align} v_pi^{k+1}(s) &:= sum_asum_{s}pi(a|s)P_{ss}^a(R_s^a+gamma v_pi^k(s))\ end{align}$

通過不斷迭代，收斂到狀態價值函數

$~\ v^1_pixrightarrow{pe} v^2_pixrightarrow{pe} v^3_pixrightarrow{pe}cdotsxrightarrow{pe} v_pi$

實現如下：

class DP(object): def __init__(self, states, actions, state_transition_table, reward_table, gamma): self.states = states self.actions = actions self.table = state_transition_table self.reward = reward_table self.gamma = gamma def policy_evaluation(self, iteration_num=None): while True: new_value_p = self.value_p.copy() for state in self.states: # 遍歷s s = 0.0 for action in self.actions: # 遍歷a for state_ in self.states: # 遍歷s sa = (state, action) target = self.reward[sa] + self.gamma * self.value_p[state_] s += self.policy[sa] * self.table[sa][state_] * target new_value_p[state] = s # 下面判斷是否已經收斂 # 如果收斂，跳出循環；如果不收斂，更新並繼續循環

在Grid World中，使用隨機策略

$pi( ext{n}|cdot) = pi( ext{e}|cdot)=pi( ext{s}|cdot)=pi( ext{w}|cdot)=0.25$

上述代碼估值如下：

策略改進

給定策略 $pi$ 及對應的狀態價值函數 $v_pi$ ，動作價值函數 $q_pi$ ，定義新策略 $pi$ 如下：

$egin{equation} pi(a|s)=left{ egin{aligned} &1-epsilon+frac{epsilon}{m} ~~~~&a=argmax_a q_pi(s, a)\ &frac{epsilon}{m} ~~~~& ext{otherwise}\ end{aligned} ight. end{equation}$

其中 $epsilonin[0,1]$ ，並記 $pi= ext{greedy}_epsilon(q_pi)$ 。

下面證明 $forall s,~v_{pi}(s)geq v_pi(s)$ 。

首先，證明事實一：

$egin{align} sum_a pi(a|s)q_pi(s,a) &=frac{epsilon}{m}sum_aq_pi(s,a)+(1-epsilon)max_aq_pi(s,a)\ &=frac{epsilon}{m}sum_aq_pi(s,a)+(1-epsilon)sum_afrac{pi(a|s)-frac{epsilon}{m}}{1-epsilon}max_aq_pi(s,a)\ &geqfrac{epsilon}{m}sum_aq_pi(s,a)+(1-epsilon)sum_afrac{pi(a|s)-frac{epsilon}{m}}{1-epsilon}q_pi(s,a)\ &=sum_api(a|s)q_pi(s,a)\ &=v_pi(s) end{align}$

其次，證明事實二：

$egin{align} sum_api(a|s)q_pi(s,a)&=sum_api(a|s)(R_s^a+gammasum_{s}v_pi(s))\ &=sum_api(a|s)R_s^a+gammasum_{s}sum_a{pi}(a|s)P_{ss}^av_pi(s)\ &=R_s^{pi}+gammasum_{s}P_{ss}^{pi}v_pi(s)\ &=mathbb{E}_{pi}[R_{t+1}|St=s]+gammasum_{s}P_{ss}^{pi}v_pi(s) end{align}$ 反覆使用上述兩個事實，

步驟一：

$v_pi(s)leqmathbb{E}_{pi}[R_{t+1}|S_t=s] + gammasum_{s}P_{ss}^{pi}v_pi(s)$

步驟二：

$egin{align} v_pi(s)&leqmathbb{E}_{pi}[R_{t+1}|S_t=s]+gammasum_{s}P_{ss}^{pi}v_pi(s)\ &=mathbb{E}_{pi}[R_{t+1}|S_t=s]+gammasum_{s}P_{ss}^{pi}(mathbb{E}_{pi}[R_{t+2}|S_{t+1}=s]+gammasum_{s}P_{ss}^pi v_pi(s))\ &=mathbb{E}_{pi}[R_{t+1}|S_t=s]+gammamathbb{E}_{pi}[R_{t+2}|S_t=s]+gamma^2sum_{s}sum_{s}P_{ss}^{pi}P_{ss}^{pi}v_pi(s)\ &=mathbb{E}_{pi}[R_{t+1}+gamma R_{t+2}|S_t=s]+gamma^2sum_{s}P_{ss}^{pi}v_pi(s)\ &=mathbb{E}_{pi}[R_{t+1}+gamma R_{t+2}|S_t=s]+gamma^2sum_{s}P_{ss}^{pi}v_pi(s) end{align}$

依此類推，

$egin{align} v_pi(s)&leqmathbb{E}_{pi}[R_{t+1}+gamma R_{t+2}+cdots|S_t=s]\ &leq v_{pi}(s) end{align}$

策略迭代

結合策略估值和策略改進，有如下過程：

$~\ v_{pi_1}^{1}xrightarrow{pe}cdotsxrightarrow{pe}v_{pi_1}xrightarrow{pi}v_{pi_2}^1xrightarrow{pe}cdotsxrightarrow{pe}v_{pi_2} ightarrowcdots ightarrow v_*$

class DP(object): def policy_iteration(self, iteration_num=None, epsilon=0): while True: self.policy_evaluation(iteration_num) new_policy = self.policy_improvement(epsilon) if _all_equal(self.policy, new_policy): break else: self.policy = new_policy

通過策略迭代計算Grid World的最優策略如下：

價值迭代

給定馬爾科夫決策過程 $langle S, A, P, R, gamma angle$ 和策略 $pi$ ，有Bellman optimality方程

$v_*^{k+1}(s) := max_asum_{s}P_{ss}^a(R_s^a+gamma v_*^k(s))$

通過不斷迭代，收斂到最優狀態價值函數

$~\ v_*^1xrightarrow{vi} v^2_*xrightarrow{vi} v^3_*xrightarrow{vi}cdotsxrightarrow{vi} v_*$

實現參見agent.py，通過價值迭代計算Grid World的最優策略如下：

總結

事實上，

可以交替使用策略迭代和價值迭代求解最優策略
可以限制策略估值和價值迭代的迭代次數

本文代碼位於dynamical programming。

參考

Planning by Dynamic Programming
無痛的機器學習