强化學習初探

admin

2018年我起頭了呆板進修相干范畴的博士生活，比拟于今朝風行的深度進修和雷同的必要大量练習数据来天生模子的监視進修法子，强化進修一個首要的分歧點是操纵练習的数据去评估（evaluate）下一步的举措（action），而不是仅仅批示（instruct）出准确的举措。 导師供给了一個有趣的問题作為切入點来深刻理解“强化進修”，那就是多臂山君機問题（multi-armed bandit）。

多臂山君機實行本色上是一類简化的强化進修問题，這種問题具备非联系關系的状况（每次只從一種环境输或赢中進修），并且只钻研可评估的反馈。假如有一台N個摇臂山君機，每拉一個摇臂城市有必定的几率得到回報，如许咱们有了N種可能的举措（每一個摇臂對應一種action），而且每次举措的成果只和當前的状况联系關系而不受汗青举措的成果影响（每次拉摇臂的回報只和山君機設置的几率相干，以前胜负的成果不會影响本次举措）。咱们可以正式界說這類問题是具备单一状况的马尔科夫决议计划進程。

咱们玩了一轮後發明此中一個摇臂回報最佳，接下来该若何玩？這里也触及强化進修一個有趣的主题：“如安在摸索（exploration）和操纵（exploitation）之間找到更好的均衡”。咱们的方针是經由過程摸索和操纵使收益最大化，多年来有多種算法被利用到這種問题中，在接下来的部門我會展現几種计谋，并供给python的實現来验证每種计谋的表示。

實行部門咱们以N=3為例，而且設定山君機的回報知足伯努利散布，即回報成果為0/1. 在初始状况S0時，三個摇臂（A、B、C）每次回報為1的几率别離是30%, 50%和80%.

针對每種计谋咱们在每轮运行1000次的拉摇臂举动，一共摹拟2000轮。這里咱们用均匀回報总数来权衡操纵（exploitation）的表示，若是每轮的回報值是Rn，则均匀回報总数=(R1+R2+....+R2000)/2000。

同時咱们用實行统计的每一個摇臂的回報率與真實回報率的方均根差（RMSE）来评估摸索（exploration）的表示。

1. import numpy as np
   
2. def return_rmse(predictions, targets):
   
3. """Return the Root Mean Square error between two arrays
   
4. @param predictions an array of prediction values
   
5. @param targets an array of target values
   
6. @return the RMSE
   
7. """
   
8. return np.sqrt(((predictions - targets)**2).mean())

複製代碼

若是均匀回報总数和方均根差都很低，可以認為该计谋是侧重摸索的计谋；反之若是二者成果都很高，则是侧重操纵的计谋。

下面咱们来看几種實行的计谋：

假如你已晓得回報率80%的那台山君機，那最直接的计谋就是一向玩這一台，每轮玩1000次後回報應當是800. 這里列出该计谋也是先明白一下均匀回報总数的上界，後面的每一個计谋的摸索表示城市和這個上界值来比力。

2. 随機（Random）算法

随機计谋是最直接的一種法子，像一個蒙昧的赌徒同样每轮随機地去拉一個摇臂。

這里咱们初始化了一個 MultiArmedBandit類的實例 mybandit, 每次随機天生摇臂的编号（0/1/2），然後挪用mybandit.step(action)去摹拟拉摇臂的动作,返回這次举动的回報。

1. from multi_armed_bandit import MultiArmedBandit
   
2. import numpy as np
   
3. 
   
4. my_bandit = MultiArmedBandit(reward_probability_list=[0.3, 0.5, 0.8])
   
5. tot_arms = 3
   
6. tot_steps = 1000
   
7. cumulated_reward = 0
   
8. print("Starting random agent...")
   
9. for step in range(tot_steps):
   
10. actio日本除臭球,n = np.random.randint(low=0, high=tot_arms)
    
11. reward = my_bandit.step(action)
    
12. cumulated_reward += reward
    
13. print("Cumulated Reward: " + str(cumulated_reward))

複製代碼

以上的步伐履行了一轮的摹拟（1000次拉摇臂的举动），一轮竣事後将回報总数存到cumulatedreward中。针對随機计谋，其實是每一個摇臂都有1/3的几率當選到，以是拉1000次摇臂後理论上成果應當靠近與（300+500+800）/  3 = 533.3。每轮的统计成果可能有一些小颠簸，以是咱们运行2000轮摹拟计较均匀回報总数来中和這些颠簸。如下是2000轮以後的成果，完备代码请见github中的random_agent_bandit.py文件。

1. Average Cumulated Reward: 533.441
   
2. Average uthelloav,ility distribution: [0.29912987  0.50015673  0.80060398]
   
3. Average utility RMSE: 0.000618189621201

複製代碼

這里的均匀回報总数已很是靠近理论上的回報值了，同時RMSE也很是的低，阐明该计谋過于侧重摸索，在操纵方面相较于最優的回報800是较着失衡的。

3. 贪心（Greedy）算法

這也是一種很直接的计谋，先把所有的摇臂都拉一次，然後選擇回報最佳的山君機一向玩下去。這類计谋很较着不鼓动勉励举行摸索，并且很轻易被每一個摇臂第一遍的回報成果误导。一样在2000轮摹拟，每轮拉1000次的步伐（greedy_agent_bandit.py）运行後，成果以下：

1. Average cumulated reward: 733.153
   
2. Average utility distribution: [0.14215225  0.2743839   0.66385142]
   
3. Average utility RMSE: 0.177346151284

複製代碼

测试成果较着高于以前的随機计谋，虽然如斯，RMSE的成果靠近0.18，阐明在摸索方面是失衡的。

4. ϵ-贪心(Epsilon-greedy)算法

该计谋連系了以前两種算法，經由過程設置一個较小的ϵ值，玩家在每次選擇摇臂時，選擇當前回報最高的摇臂去玩的几率是1-ϵ（即exploitation的几率），而随機選擇肆意一個摇臂的几率是ϵ（即exploration的几率）。ϵ的值凡是設置為0.1，摹拟步伐（epsilon_greedy_agent_bandit.py）运行的成果以下：

1. Average cumulated reward: 763.802
   
2. Average utility distribution: [0.2934227   0.49422608  0.80003897]
   
3. Average utility RMSE: 0.00505307354513

複製代碼

均匀回報的成果要高于以前的计谋，并且RMSE的值也降到了0.005，阐明在随機的摸索有用的收敛到了靠近真正的回報几率散布，该计谋保持了较好的均衡。

5. Softmax-贪心（Softmax-greedy）算法

在前一種ϵ-贪心计谋中，玩家在摸索時老是按不异的几率随機選擇一個摇臂，而利用softmax法子摸索新的摇臂時，可能获得更多回報的摇臂會有更大的几率當選中。softmax的函数實現以下：

1. def softmax(x):
   
2. 
   
3. @param x the input array with each arm's current reward高雄合法當舖， probability
   
4. @return the softmax array with each arms's possible selection probability
   
5. """
   
6. return np.exp(x - np.max(x)) / np.sum(np.exp(x - np.max(x)))

複製代碼

在實行中，咱们設置一個 σ 值，使玩家操纵當前回報最高的摇臂的几率是σ，而继续摸索的几率是1 - σ。在摸索時，按照當前每一個摇臂的回報率，咱们經由過程softmax函数计较出一個几率散布[p1, p2, p3], 基于此散布来拔取下一步要摸索的摇臂。這類采样方法至關于在摸索中有更高几率拔取回報率较高的摇臂，即在摸索中不忘操纵。在摹拟步伐（softmax_agent_bandit.py）中，σ = 0.1，运行的成果：

1. Average cumulated reward: 767.249
   
2. Average utility distribution: [0.29169784  0.49047397  0.79968229]
   
3. Average utility RMSE: 0.00729776356239

複製代碼

可以看出操纵的成果比前一種计谋(Epsilon-greedy)稍好一點，但摸索的毛病率却较之略高（0.007 vs 0.005）。可见摸索與操纵之間的均衡瓜葛很奥妙也很懦弱。

6. ϵ-降低(Epsilon-decreasing)算法

在Epsilon-greedy算法中咱们設置了固定的ϵ = 0.1，這不是一個抱负的選擇， 由于颠末屡次测试後，咱们已获得了所有摇臂相瞄准确的回報率的散布估量，此時咱们應當得當削减摸索，即低落epsilon的值，使得操纵當前最佳回報的摇臂的几率增长。這里咱们設置初始的ϵ = 0.1，并采纳線性降低的法子使得ϵ最後降到0.0001，使得在每轮1000次测试中，從起頭至多10%的几率去摸索到最後一次几近彻底變成操纵（此時ϵ 靠近于 0）。這類计谋下步伐（epsilon_decreasing_agent_bandit.py）运行的成果：

1. Average cumulated reward: 777.423
   
2. Average utility distribution: [0.28969042  0.48967624  0.80007298]
   
3. Average utility RMSE: 0.00842363169768

複製代碼

均匀回報略高于以前的计谋，但毛病率也變高了。如许的成果再一次印证了操纵和摸索之間奥妙的均衡瓜葛。感樂趣的读者可以测验考试更快的降低法子，如指数级的降低，如许的计谋會更多方向于操纵，理论上應當有更好的回報，但RMSE的毛病率會更高。

7. 汤普森采样（Thompson sampling）

理解该计谋必要几率论和贝叶斯统计的一些常識，特别是常见的几率散布和贝叶斯定理的基来源根基理。在本實行中，咱们經由過程拉一個摇臂赢和输的次数来评估所谓的功效函数，從统计學角度来讲该功效函数就是多臂山君機的伯努利回報散布的一個類似估量。

在频率论统计中伯努利散布是經由過程最大似然估量来计较的：

此中P(q)代表某個摇臂获得正回報的几率， s 是赢的次数，f是输的次数。這里最大似然估量有一個较着的問题就是在只有少许實行样本的時辰回報几率的成果會有很大的误差。

如许問题就酿成了基于今朝已有的實行数据，若何找到一個優化的伯努利散布的類似估量。操纵贝叶斯法子，咱们可以界說當前各摇臂的回報率散布為先验散布，進而經由過程计较下一步举措的最好後验几率去采样下一步的举措，這類法子就叫汤普森采样法， 由William Thompson在1933年颁發。下面咱们按照實行設定简略推导一下。

咱们設定實行山君機的回報知足伯努利散布（即1/0），每台摇臂获胜的几率為q，则输的几率是1-q。同時咱们界說s 和 f 别離是以前以一系列實行中采集的该摇臂获胜和输錢的次数，如许咱们關切的是每一個摇臂下一次可能获胜的後验几率散布，即P(q|s,f)。在贝叶斯定理中後验几率經由過程以下公式计较：

從這個公式中咱们必要進一步计较P(s,f|q) 和 P(q)，此中 P(s,f|q)的寄义是基于摇臂的胜率q，在s+f次實行中获胜s次的几率。這里咱们可以用二項式散布来计较一系列自力實行後获胜的次数，公式以下：

而另外一部門P(q)代表與P(q|s,f)属于共轭散布的先验散布，在伯努利散布中共轭先验散布是Beta 散布：
大理石水垢清洗，

即

這里α,β代表胜率和失败率的大于0的参数， B是Beta散布中的正则化常量，以确保总體几率為1.

如今咱们将這两部門整合到贝叶斯定理的公式中，颠末推导获得下面的成果：

该成果從情势上是一個新的Bate散布，只是参数酿成了α+s和β+f。如许經由過程Bate散布和今朝的各摇臂的输赢次数，咱们能计较出每一個摇臂當前最佳的获胜几率，從而選擇下一步的举措。咱们可以設定α=β=1，在没有先验常識的時辰（s=f=0）至關于起頭随機摸索；输赢次数积累的越多，後验胜率就會评估的越正确。

在python實現中，咱们把三個摇臂當前的获胜次数(1+s)和失败次数（1+f）作為参数傳入numpy.random.beta()法子中计较各摇臂的後验貨胜率，然後選擇當前胜率最大的摇臂去玩下一次。

1. def return_thompson_action(success_counter_array, failure_counter_array):
   
2. """Return an action using Thompson sampling
   
3. 
   
4. @param success_counter_array (alpha) success rate for each action
   
5. @param failure_counter_array (beta) failure rate for each action
   
6. @return the action selected
   
7. """
   
8. beta_sampling_array = np.random.beta(success_counter_array,
   
9. failure_counter_array)
   
10. return np.argmax(beta_sampling_array)

複製代碼

测试的成果出奇的好：

1. Average cumulated reward: 791.21
   
2. Average utility distribution: [0.39188487  0.50654831  0.80154085]
   
3. Average utility RMSE: 0.0531917417346

複製代碼

Tompson sampling计谋的均匀回報是今朝计谋中最佳的，0.05的毛病率在功效函数中算是相對于低的。從今朝的設定看Thompson應當是最佳的计谋。可是若是在更繁杂的场景下，计较後验散布的繁杂度也會响應增长。以是必要更周全的评估某一算法的利用。這里有更具體的Thompson Sampling的最新教程，我會在接下来的文章中举行更深刻的阐發。