本文繼續(xù)講一個(gè)強(qiáng)化學(xué)習(xí)的算法，叫做Thompson抽樣算法。這個(gè)算法的數(shù)學(xué)理論基礎(chǔ)要用到的是貝葉斯推斷(Bayesian Inference)。我們先談?wù)勥@個(gè)算法的基本原理。

Thompson抽樣算法基本原理

我們依然使用之前的多臂老虎機(jī)的問題。如圖所示，橫軸代表獎(jiǎng)勵(lì)，越往右邊表示獎(jiǎng)勵(lì)越多。三條豎線代表三個(gè)不同的老虎機(jī)它們的平均獎(jiǎng)勵(lì)。

image

在算法開始前，我們是什么都不知道的，因此需要得到一些基礎(chǔ)數(shù)據(jù)。圖中有四個(gè)藍(lán)色的數(shù)據(jù)，表示按下藍(lán)色老虎機(jī)得到的獎(jiǎng)勵(lì)，根據(jù)這幾個(gè)得到的獎(jiǎng)勵(lì)，可以得到一個(gè)數(shù)學(xué)分布。同樣綠色的老虎機(jī)也能得到一個(gè)分布，黃色同理。

image

這三個(gè)分布預(yù)測的是這三個(gè)機(jī)器給我們帶來獎(jiǎng)勵(lì)實(shí)際上可能的數(shù)學(xué)期望的概率分布。接下來基于這三個(gè)隨機(jī)分布，我們得到幾個(gè)隨機(jī)抽樣，選擇獲得最大抽樣值的機(jī)器按下去。但由于是隨機(jī)的，雖然黃色的實(shí)際期望是最高的，但我們依然可能會選出一個(gè)綠色大于黃色數(shù)據(jù)結(jié)果。

image

按下去后我們會得到一個(gè)新的觀察到的獎(jiǎng)勵(lì)值，得到新的獎(jiǎng)勵(lì)值后就要調(diào)整綠色機(jī)器的分布。

image

顯然這個(gè)綠色的分布變得更高更窄了，后面的步驟和這里其實(shí)是一樣的，也是依然選擇獎(jiǎng)勵(lì)值最高的機(jī)器按下去，通過得到的結(jié)果繼續(xù)調(diào)整分布。

當(dāng)這個(gè)游戲進(jìn)行到很多步驟之后，這些分布都會變得非常窄，尤其是黃色的基本會和實(shí)際期望吻合.

image

這時(shí)由于我們一直選擇獎(jiǎng)勵(lì)值最高的機(jī)器，因此按下黃色的概率會比較高，導(dǎo)致黃色的會越來越窄，而藍(lán)色的很少玩到，因此相對要寬一點(diǎn)。

Thompson抽樣算法 vs. 置信區(qū)間上界算法

我們使用Thompson抽樣算法和ucb算法都處理了多臂老虎機(jī)問題，那么現(xiàn)在來比較下兩個(gè)算法。來看看這兩個(gè)算法的基本原理圖。

image

首先這個(gè)UCB算法，它是一個(gè)確定性算法，當(dāng)我們得到相同的獎(jiǎng)勵(lì)時(shí)，我們作出的決策時(shí)確定，因此我們每一輪的總收益和總收益都是確定的。每一輪中作出的決策只和置信區(qū)間的上界有關(guān)，而這個(gè)上界只和這個(gè)機(jī)器所有的觀察值有關(guān)。所以說當(dāng)所有機(jī)器的觀察值相同時(shí)，我們永遠(yuǎn)會做相同的決策。對于Thompson算法，它是個(gè)隨機(jī)性算法，它的某一步或者某幾步是在一個(gè)隨機(jī)函數(shù)控制下，跟運(yùn)氣是有關(guān)系的。它依賴于一些隨機(jī)事件，就像我們上面選擇點(diǎn)的時(shí)候，雖然黃色的實(shí)際期望大于綠色，但我們還是可能會選出綠色大于黃色的數(shù)據(jù)點(diǎn)。因此說它是個(gè)隨機(jī)性的算法。

那么對于UCB，它還有個(gè)特點(diǎn)，就是需要實(shí)時(shí)更新上界，這個(gè)在之前的文章描述UCB算法原理的時(shí)候可以看出來。對于Thompson抽樣算法，它是允許延遲更新甚至批量更新的，比如我們往網(wǎng)上投放一批廣告，這里是允許它得到的結(jié)果是有延遲的。最后一點(diǎn)，在近些年的實(shí)際應(yīng)用和研究中發(fā)現(xiàn)，Thompson抽樣算法相對于置信區(qū)間算法，它是有更好的實(shí)際應(yīng)用效果的。

代碼實(shí)現(xiàn)

首先看看Thompson抽樣算法的計(jì)算邏輯：

image

image

代碼這里就直接貼出來了：

import matplotlib.pyplot as plt
import pandas as pd
import random

# import the dataset
dataset = pd.read_csv('Ads_CTR_Optimisation.csv')

# Implementing Thompson Sampling
N = 10000
d = 10
ads_selected = []
numbers_of_rewards_1 = [0] * d
numbers_of_rewards_0 = [0] * d
total_reward = 0
for n in range(0, N):
    ad = 0
    max_random = 0
    for i in range(0, d):
        random_beta = random.betavariate(numbers_of_rewards_1[i] + 1, numbers_of_rewards_0[i] + 1)
        if random_beta > max_random:
            max_random = random_beta
            ad = i
    ads_selected.append(ad)
    reward = dataset.values[n, ad]
    if reward == 1:
        numbers_of_rewards_1[ad] = numbers_of_rewards_1[ad] + 1
    else:
        numbers_of_rewards_0[ad] = numbers_of_rewards_0[ad] + 1
    total_reward = total_reward + reward

# Visualising the results
plt.hist(ads_selected)
plt.title('Histogram of ads selections')
plt.xlabel('Ads')
plt.ylabel('Number of times each ad was selected')
plt.show()

最終得到總獎(jiǎng)勵(lì)數(shù)相對于之前的置信區(qū)間算法要高很多，而且得到的圖像很明顯能看到最佳的廣告是ad5，因此Thompson抽樣算法的實(shí)際效果的確要優(yōu)于置信區(qū)間算法。

以上，就是強(qiáng)化學(xué)習(xí)中的Thompson抽樣算法的基礎(chǔ)知識。