多武裝強盜練習中的違反直覺的結果

我正在研究Sutton的第2章第7節& Barto的強化學習：介紹，它涉及多臂強盜問題中的梯度方法。（我意識到第二版是一個草案，看起來這些章節稍微有所變化，但是我的文件有第2.7節標題爲「梯度盜匪」）。我已經設法使用2.3-2.5節中的方法，沒有問題，但我始終使用令人困惑的漸變方法獲得結果。我將瀏覽我的代碼並展示一個示例。多武裝強盜練習中的違反直覺的結果

這裏只是初始化一切：

import random 
import math 
import numpy as np, numpy.random 

# number of arms (k) and step-size (alpha) 
k = 10 
alpha = 0.1 

# initialize preference function (H), and reward distribution (R) 
H = {i: 0 for i in range(k)} 
R = {i: [random.uniform(-100,100), 1] for i in range(k)}

我使用的是固定回報的分佈，而且我在使用字典來代表這些分佈。我假定由高斯描述的每個獎勵，所以我用下面的函數映射動作來獎勵：

def getReward(action, rewardDistribution): 
    return random.gauss(rewardDistribution[action][0], rewardDistribution[action][1])

所謂「偏好函數」 H，其用於確定動作的概率，是也由字典給出。我在很寬的範圍內展開選擇，因爲每個獎勵都是用高斯分佈描述的，標準偏差1位於-100和100之間。我這樣做是因爲我的直覺告訴我，它會使得它更難算法來解決次優選擇，但我發現相反的情況正在發生。

這段代碼在每次迭代選擇我的行動：

def selectAction(policy): 
    return np.random.choice(list(policy.keys()), p=list(policy.values()))

而且接下來是運行算法的迭代的代碼。請注意，pi是政策，並初始化爲給每個操作提供概率1/k。

avgReward = 0 
for i in range(100000): 
    pi = {i: math.exp(H[i])/sum([math.exp(H[j]) for j in range(k)]) for i in range(k)} 
    A = selectAction(pi) 
    R_A = getReward(A, R) 
    avgReward += (R_A - avgReward)/(i + 1) 
    H = {i: H[i] + alpha*(R_A - avgReward)*((i == A) - pi[i]) for i in range(k)}

通知我跑10萬次迭代，這對我似乎應該是矯枉過正。這是我在這個問題上的第一次嘗試，所以我的直覺可能會被忽略，但我試圖設置它以使算法易於找到最佳選擇。所以我期望的是這個過程會收斂於具有最高期望值的分佈的行爲，並且在迭代過程中將繼續觸發它。但是，當我打印出相對於由土匪每個可能的行動的結果，這是我所看到的：

for i in range(k): 
    print("Expected reward: " + str(R[i][0]) + " | Selection probability: " + str(pi[i]) + " | Preference: " + str(H[i])) 

Expected reward: -50.62506110888989 | Selection probability: 3.617077909489526e-13 | Preference: -7.82992533515 
Expected reward: 11.866419726345484 | Selection probability: 1.2337498052271344e-10 | Preference: -1.99777839484 
Expected reward: 75.41139657867947 | Selection probability: 1.5933517476231946e-09 | Preference: 0.560588358966 
Expected reward: -72.44467653824414 | Selection probability: 3.4267025247257986e-13 | Preference: -7.88399339198 
Expected reward: -43.466561447399 | Selection probability: 1.5933517476231946e-09 | Preference: 0.560588358966 
Expected reward: -75.99171566420297 | Selection probability: 1.5933517476231946e-09 | Preference: 0.560588358966 
Expected reward: -82.11920932060593 | Selection probability: 3.120658098513757e-13 | Preference: -7.97754791911 
Expected reward: 95.00643386364632 | Selection probability: 1.5933517476231946e-09 | Preference: 0.560588358966 
Expected reward: 31.384022070017835 | Selection probability: 1.2605442916195123e-08 | Preference: 2.62887724114 
Expected reward: 49.83925652065625 | Selection probability: 0.9999999808967586 | Preference: 20.8180143641

的最後一個動作有49.8的預期回報，和強盜幾乎選擇它每次。這是10個選項中的第三最佳選項，但它忽略了一個期望獎勵爲75.4的選項，另一個選項的預期獎勵爲95.0。

所以，我的問題：爲什麼這個土匪錯過了最佳選擇？這只是一個例子，當我運行該程序時，這發生在一個相當一致的基礎上。我的直覺是否與我期望的土匪行爲有關，或者我是否錯誤地編寫了這種算法？

來源

2017-01-06 Jeff Davis

問題是，許多武器（或行動;我使用武器，因爲這是MAB問題中最常見的術語）根本不會按照當前設置播放一次。您可以輕鬆驗證是否出現這種情況，方法是打印每個手臂的頻率並選擇。

發生這種情況是因爲您的獎勵具有相當高的絕對價值。在關於人與生物圈問題的文獻中，他們經常假設[0,1]或[-1,1]中的獎勵。這並不是絕對必要的（雖然這是爲了一些與算法的理論性能有關的證明......但是這對你來說可能不是很有意思）。無論如何，有幾種方法可以解決此問題：

1）將首選項列表（H）初始化爲較高值而不是0s。這與本書前面描述的樂觀初始化epsilon相似，因爲它激勵了算法在早期進行更多探索。

2）大幅降低學習率alpha的價值。試試更像0.00001，而不是0.1。該變化的影響是H中的偏好值以較小的速率從0增長，因此pi中的概率也以減少的速率從最初的1/k增長。

3）重新規模化獎勵值，例如[-1,1]（如果您不想要問題，還需要適當減少獎勵分配的標準偏差變得更加複雜

來源

2017-01-06 16:50:49

非常感謝，我會嘗試這些建議。 –

多武裝強盜練習中的違反直覺的結果

回答

相關問題