歡迎轉載，轉載請注明出處——知乎專欄“機器學習與控制論”。
“稀疏獎賞”(sparse reward)是強化學習應用中的經典難題。尤其是強化學習控制任務中，為了處理處理它，我打賭不少人都深受“獎賞塑形”等獎賞工程的折磨。
今天分享的這篇文獻“Hindsight Experience Replay”（HER）正是提出一種
極其簡單巧妙且易實作的方法試圖擺脫獎賞工程。現在，HER和模仿學習已經幾乎成了機器人學習控制的标配。（OpenAI的geek們也是挺有趣的，取名和寡姐的電影一樣，電影也是講人工智能。）
知乎上有過相關内容，這裡從控制的角度梳理思路和使用心得，
附以簡單的代碼實作。
先放使用心得，後續經驗還會更新：
（1）狀态（state）設計需要滿足文中兩點前提
（2）尤其适合多目标(multi goal)任務，單目标任務很可能收益有限
（3）有些情況可能獎賞塑形效果更好、更簡單
（4）主要思想并非與獎賞塑形不相容，HER+獎賞塑形可能也有效果
（5）每個episode不要太長（本質是采樣産生新goal的區間不要太長）
1.背景
強化學習（RL）直接應用，尤其應用于機器人學，往往需要精心地“獎賞塑形”(reward shaping)，進而引導政策進行優化。
獎賞塑形思想倒是不難，如下面這個任務"pushing"，推動方塊到紅點（目标）的位置。若是隻是最後達到紅點才給獎賞（即二進制獎賞，binary reward），那大多數時候都得不到獎勵。是以，可能的獎賞塑形方式是以方塊到紅點的距離平方的負數為獎賞函數。
簡單任務還好，但是遇到複雜任務，就既要求有RL知識又要有領域知識，設計起來非常不容易，甚至有論文在獎賞中設計了5個帶權項[1]。此外，許多時候，我們更關心最後的結果，而不關心、也不太好判斷中間可能的情況。
個人經驗是，如果獎賞中有多個權，往往還要防止Agent進行cheating的情況，而且許多時候，我們更關心最後的結果，而
不關心、也不太清楚中間可能的情況。是以，我們需要簡單的獎賞設計，比如說，最好就是原來RL樸素的二進制獎賞（達到目标則有，否則無）。
怎麼做呢？從錯誤中學習。拿足球射門舉例，如果你一次射門射偏到了球門右邊，樸素的RL算法可能認為這就是沒有獎賞，學到很少。而人的話卻可以從這次失敗中知道，這個射偏的落點，是我站在現在這個位置，用這樣的腳法能射達的。誇張點說，如果門右挪一點就好了。
這種思想更有效的場景是控制、規劃中常見的多目标任務，其中RL的模組化方式叫做
universal policy，最早來源于Universal Value Function Approximators[2]（UVFA），此時輸入給Agent的不僅僅有狀态，還有目前任務指定的目标（二者進行concatenate操作）。比如下面的情況，Agent被要求射第3個門，但是若射偏到了第2個門，雖然沒達到目前目标，但是達到了“射中第2個門”的目标！這就是所謂的hindsight（後見之明），是以這個經驗完全可以複用起來，采樣效率就增大了，而且可能可以用二進制獎賞。
HER的思想就是如此，回放每個episode，用新的目标（如已經達到的狀态）去替換掉經驗中原本想要去達到的目标。HER的适用範圍也就很明顯了，凡是off-policy的RL算法都可以配合适用，如DDPG和DQN等。
2.任務
翻轉硬币（toy example）：
n個硬币，每個硬币正面為1反面為0，n個硬币序列為狀态。動作是翻轉n個中的一個。目标是翻到某種狀态。
機械臂（gripper） pushing, sliding, picke-and-place：
目标紅點位置是随機放置的。
單目标任務：目标位置固定。
3.方案
前提假設：（1）對于一個目标g和一個狀态s，必須能夠計算得到該s是否能達到g。為什麼呢？
因為HER要用s和g來計算（二進制）獎賞。這個要求一般都能滿足，因為goal這個次元的實體量一般都會在狀态中。例如機器臂pushing任務中，目标是紅點的位置——以坐标的形式給出，那機械臂手指（fingrer)的實時坐标也是會納入到狀态中的，是以能計算是否滿足。
公式化如下：每一個目标
，對應一個函數
，Agent的目标就是達到某個狀态使得該函數等于1. 例如，該函數可以是
,這種情況是狀态正好等于目标的時候才為1，否則為0. 又例如
，這時候f隻與s中的一維有關。
（2）對于一個狀态s，必須要能作為一個goal。理由是HER中需要将失敗的state作為新goal用于經驗回放。這個也一般可以滿足。
公式化表述如下：對于一個狀态s有一個對應的映射
拿上面這個二維坐标x,y舉例，m可以是
.
重要元素：（1）狀态
對象仿真在Mujoco中的實體引擎實作，狀态包括機械臂各個關節和速度，以及所有對象的位置、旋轉和速度。
（2）目标
物體應該到達的位置，有一定的tolerance，比如
是三維坐标
，此時
.
（3）獎賞
主要使用二進制獎賞。後面也對比了塑形後的獎賞。
（4）觀測
政策的輸入是gripper的絕對位置，目标和物體的相對（gripper的）位置以及相對距離。Q函數的輸入額外添加了gripper和fingers的線速度以及物體的相對線速度和角速度。（限制policy是為了在實體機械臂上部署比較容易？）
（5）動作
4維，其中三維是gripper下一時間步的位置。最後一維是兩個finger之間的距離。
（6）HER采樣得到新目标的政策
采樣數目K是超參數。
final：取後1個state作為新目标
future：回放該回合中，從現在開始K個随機狀态作為新目标
episode：回放該回合中K個随機狀态作為新目标
random：回放至今為止K個随機狀态作為新目标
算法： 算法非常之簡潔，标準RL版本是一層episode次數循環内嵌一層step次數循環。但是這裡内部有三次循環，第一次照常，第二次是重點，對于剛剛得到每一個三元組(s,a,s')，除了原始的goal拼接到state再存到buffer裡，還用新goal進行改造，也放進去，
這樣做的意思就很直覺了，動态 這樣，buffer裡樣本實際上增加了（新goal數目）倍。前提假設用到的部分在圖中進行了标注。
實作的時候，個人認為把原始的reward計算以及第三個内循環optimize部分放回原來的位置（第一部分）可能會更好，每走一步更新一次，友善與baseline進行比較。
基線：四個基線，DDPG、DDPG+count-based exploration、DDPG+HER（“final”政策）和DDPG+HER（verison from Sec. 4.5，“future”政策）。
注意，它們都是用的二進制獎賞，包括前兩者。
4.結果與讨論
（1）多目标
結果是加入HER的版本更好，其中“future”政策又更好。
注意到，每個episode隻有50步，意味着采樣産生新goal的區間最多是50，實驗中發現這個數字大小很影響結果，不能太大，否則新goal和舊state仍然差很大，還是得到失敗獎賞。
（2）單目标
單目标的情況居然也是有效果的，但DDPG+HER的優勢顯然不如多目标時候優勢大，甚至sliding中不加HER更好。作者沒有解釋為什麼有效果，直覺的想是
神經網絡的泛化性能起了作用。另外，就variance（陰影）而言，DDPG更大，也可以推測出HER确實提高采樣效率，有效樣本數較多，結果較為穩定。
（3）采樣新目标的政策
縱軸上面是最高成功率，下面是平均，橫軸是采樣數目。整體來說符合直覺，random稍差，其餘三者future稍好。final隻取一個，是以是平的。采樣數目上來看，
4個到8個一般都還不錯，過多變差的原因解釋是正常樣本比例降低了。
（4）HER與獎賞塑形比較
多目标任務，獎賞塑形采用目标與物體坐标的距離平方的相反數。DDPG和HER都失敗了，文中認為結果與之前工作[2]結論一緻：如果不采用demonstration，獎賞函數會比較複雜。
失敗的原因可能是：
1）塑形後的獎賞與成功的條件不一緻。
2）塑形的獎賞懲罰了不正确的動作阻礙了探索（比如往反方向探索）。這可能使得Agent在沒能按照準确操縱物體的情況下，不再去觸碰物體。
文中談到
也許存在一個設計好的塑形後的reward會相當好，但是可能設計很麻煩，需要領域知識。是以他們堅信二進制獎賞很重要，簡單勝過複雜。
5.代碼
HER實作非常簡單，這裡介紹關鍵部分，全部代碼請見github，定期更新代碼，歡迎star :-)
簡單起見，這裡采用的環境是OpenAI gym中的pendulum，單目标任務。
state/observation一共有三維：
,
表示離垂直的角度。
action是轉矩，goal是[1.0,0,0]，即垂直位置穩定不動。
# PART II hindsight replay
for i, transition in enumerate(episode_cache):
new_goals = generate_goals(i, episode_cache, args.HER_sample_num)
for new_goal in new_goals:
reward = calcu_reward(new_goal, state, action)
state, action, new_state = gene_new_sas(new_goal, transition)
ram.add(state, action, reward, new_state)
除了将正常的rewad計算放在了第一次循環以外，和僞代碼一樣。主要涉及到goal的函數，計算獎賞，拼接新gaol三個函數。
新goal的産生采用“future”政策，限定了采樣的範圍是從第i步開始，最多50步。
def generate_goals(i, episode_cache, sample_num, sample_range = 200):
'''
Input: current steps, current episode transition's cache, sample number
Return: new goals sets
notice here only "future" sample policy
'''
end = (i+sample_range) if i+sample_range < len(episode_cache) else len(episode_cache)
epi_to_go = episode_cache[i:end]
if len(epi_to_go) < sample_num:
sample_trans = epi_to_go
else:
sample_trans = random.sample(epi_to_go, sample_num)
return [np.array(trans[3][:3]) for trans in sample_trans]
兩種計算獎賞的方式，shaping用的是差的平方的相反數，her表示二進制獎賞。裡面的tolerance參數其實也很敏感，是以還是得調，不過比起獎賞塑形的n個帶權term調起來還是輕松很多。
def calcu_reward(new_goal, state, action, mode='her'):
# direcly use observation as goal
if mode == 'shaping':
# shaping reward
goal_cos, goal_sin, goal_thdot = new_goal[0], new_goal[1], new_goal[2]
cos_th, sin_th, thdot = state[0], state[1], state[2]
costs = (goal_cos - cos_th)**2 + (goal_sin - sin_th)**2 + 0.1*(goal_thdot-thdot)**2
reward = -costs
elif mode == 'her':
# binary reward, no theta now
tolerance = 0.5
goal_cos, goal_sin, goal_thdot = new_goal[0], new_goal[1], new_goal[2]
cos_th, sin_th, thdot = state[0], state[1], state[2]
costs = (goal_cos - cos_th)**2 + (goal_sin - sin_th)**2 + 0.1*(goal_thdot-thdot)**2
reward = 0 if costs < tolerance else -1
return reward
最後就是簡單的拼接新goal得到新的s,s'
def gene_new_sas(new_goals, transition):
state, new_state = transition[0][:3], transition[3][:3]
action = transition[1]
state = np.concatenate((state, new_goals))
new_state = np.concatenate((new_state, new_goals))
return state, action, new_state
進行了一些實驗得到的小結：
1）該任務用gym中自帶的獎賞函數已經是塑形之後的，效果很不錯。
2）HER+塑形獎賞也可以取得很好的效果
3）超參數選擇：采樣goal樣本4好于8，tolerance為0.5較好，這兩個參數很敏感
參考
- ^https://arxiv.org/abs/1704.03073
- ^abhttp://proceedings.mlr.press/v37/schaul15.pdf