狠狠干.com,污视频在线观看一区

背景

多臂老虎機(jī)是一個(gè)在探索(exploration)和開發(fā)(exploitation)過(guò)程中尋找最高收益的問(wèn)題。此類“實(shí)驗(yàn)”能力幾乎已經(jīng)成為了優(yōu)秀實(shí)驗(yàn)平臺(tái)的標(biāo)配。
本篇是閱讀《A modern Bayesian look at the multi-armed bandit》后結(jié)合個(gè)人理解的學(xué)習(xí)總結(jié)。它總結(jié)了基于貝葉斯的隨機(jī)概率匹配法和其它相關(guān)方法。

1. 隨機(jī)概率匹配（RPM）

定義 $Y_t = (y_1, ..., y_t)$ 代表t時(shí)為止的獎(jiǎng)勵(lì)序列， $a_t$ 代表t時(shí)選擇的臂，t時(shí)刻獎(jiǎng)勵(lì) $y_t \sim f_{a_t}(y|\theta)$ ， $\theta$ 是一個(gè)未知向量。

$y_t \in (0, 1)$ 情況下兩種例子：

伯努利老虎機(jī)， $\theta = (\theta_1, ...,\theta_k)$ ， $f_{a_t}(y|\theta)$ 參數(shù)為 $\theta_a$
fractional factorial bandit（本文不關(guān)注）

定義 $\mu_a(\theta) = E(y_t | \theta, a_t = a)$ 是 $f_{a}(y|\theta)$ 的期望值，最佳策略應(yīng)該一直選擇 $\mu_a(\theta)$ 最大的臂。
在伯努利分布下， $\theta_a = \mu_a(\theta)$ 。

定義 $p(\theta)$ 是 $\theta$ 的先驗(yàn)概率密度，此時(shí)以 $p(\theta)$ 產(chǎn)生 $\theta$ ， $\theta$ 產(chǎn)生y，則0時(shí)刻選擇a正確概率：

$w_{a0} = Pr(\mu_a = max\{\mu_1,... \})$ （1)

定義 $I_a(\theta)$ 為指示函數(shù)， $\mu_a = max\{\mu_1,...\mu_k\}$ 時(shí) $I_a(\theta)=1$ ：

$w_{a0} = E(I_a(\theta)) = \int I_a(\theta) p(\theta) d\theta$ （2）

一個(gè)例子，先驗(yàn)可以Beta分布，兩臂時(shí)為二元

如果沒(méi)有關(guān)于 $\theta$ 的先驗(yàn)，則先驗(yàn)視為各個(gè) $\mu$ 是一樣的， $w_{a0}$ 是均勻分布。
觀測(cè)到獎(jiǎng)勵(lì)情況后，通過(guò)貝葉斯方法進(jìn)行更新， $p(\theta | Y_t ) = \frac{p(Y_t|\theta)p(\theta)}{p(Y_t)}$ 。t時(shí)刻：

$p(\theta | Y_t ) \propto p(\theta)\prod _{\tau = 1}^t f_{a_\tau}(y|\theta)$ (3)
則此時(shí) $w_{at} = Pr(\mu_a = max\{\mu_1,...\} | Y_t ) = E(I_a(\theta) | Y_t )$ （4）

隨機(jī)概率匹配用 $w_{at}$ 來(lái)分配a的t+1時(shí)觀測(cè)值，通過(guò)一種自然平衡探索與開發(fā)的方式。

1.1 概率分配計(jì)算

如果 $\theta^{(1)},...,\theta^{(G)}$ 是來(lái)自 $p(\theta|Y_t)$ 的獨(dú)立抽樣，則基于大數(shù)定理：

$w_{at} = \lim_{g\rightarrow \infty }\frac{1}{G}\sum^G_{g=1}I_a(\theta^g).$ （5）

如果 $f_a$ 是指數(shù)族，而且 $p(\theta)$ 是它的共軛分布，則可以獨(dú)立的抽樣 $\theta$ ，否則可以用馬可夫相關(guān)的方法進(jìn)行抽樣模擬。

$\theta$ 的后驗(yàn)抽樣足夠?qū)Ω怕势ヅ溥M(jìn)行支持。

1.2 隱式分配

（5）可以不用顯式計(jì)算，從 $p(\theta|Y_t)$ 模擬 $\theta^{t}$ ，并選擇 $a = argmax_a\mu_a(\theta^t)$

1.3 探索(exploration)、開發(fā)(exploitation)和不確定性

隨機(jī)概率匹配自然的包含了不確定性，下圖為兩臂情況下的情況：

Figure 1. One thousand draws from the joint distribution of two independent beta distributions. In both cases, the horizontal axis represents a beta (20,30) distribution. The vertical axis is (a) beta(2,1) and (b) beta(20,10).

在(a)中，錯(cuò)誤選中概率為18%；在(b)中，錯(cuò)誤選中概率為0.8%。
這個(gè)例子說(shuō)明，隨著學(xué)習(xí)的進(jìn)行，探索的占比會(huì)減少。

2. 其它方法

2.1 The Gittins index(基廷斯指數(shù))

此方法假設(shè)單臂未來(lái)的獎(jiǎng)勵(lì)會(huì)與一個(gè)幾何分布有關(guān)： $\sum_{t = 0} ^ {\infty} \gamma ^ty_t$ ，其中 $0 \leq \gamma < 1$
基廷斯提供了一種計(jì)算各個(gè)臂價(jià)值的算法，得到的結(jié)果稱為基廷斯指數(shù)。它在前提可保證時(shí)是最優(yōu)方案。

γ為0.9時(shí)的基廷斯指數(shù)表

Brezzi and Lai’s approximation to the Gittins index for the binomial bandit problem with (a) ?γ=0.8 and (b) ?γ=0.999.

這部分的數(shù)學(xué)相關(guān)很復(fù)雜先跳過(guò)，簡(jiǎn)單了解可參考《算法之美》第二章相關(guān)部分。

對(duì)基廷斯指數(shù)的三個(gè)問(wèn)題：

不完全學(xué)習(xí)，可能最終收斂到次優(yōu)解；
各臂的參數(shù)需要是固定的；
獎(jiǎng)勵(lì)減少結(jié)構(gòu)必須是幾何分布。

2.2 UCB算法(Upper Confidence Bounds)

計(jì)算每個(gè)手臂獎(jiǎng)勵(lì)均值及置信區(qū)間上限，然后選上限最高的手臂。
值得注意的是，此上限并不是常見的置信區(qū)間算法，而且比較難計(jì)算。

2.3 啟發(fā)式策略

2.3.1 平均分配
次策略均勻的探索每個(gè)臂，直到其中一個(gè)臂獎(jiǎng)勵(lì)超過(guò)某個(gè)閾值，然后一直選擇此臂。這種方法對(duì) $\theta$ 探索效果很好，但是前期成本高，導(dǎo)致整體獎(jiǎng)勵(lì)效果較差。類似于先進(jìn)行一輪隨機(jī)實(shí)驗(yàn)評(píng)估效果，然后選擇效果最好的方案。
2.3.2 連勝就繼續(xù)，輸了就換其它
至少好于隨機(jī)選擇……當(dāng)最優(yōu)秀的策略效果也沒(méi)有特別好時(shí)，此方案會(huì)過(guò)度探索，導(dǎo)致效果很差。
2.3.3 貪心策略
簡(jiǎn)單的貪心策略效果很差，比較好的是deterministic probability matching做法。但是在批量更新場(chǎng)景，一個(gè)更新周期只能探索一種方案，所以前期會(huì)表現(xiàn)特別差。
2.3.4 混合策略
混合策略是貪心之外，強(qiáng)制進(jìn)行一定比例的探索，比如Epsilon-greedy或Epsilon-decreasing。不過(guò)上兩種方法的敏感度不夠高，因此還可以參考Softmax learning方法。

2.4 與概率匹配的對(duì)比

概率匹配結(jié)合了2.3中的多種好處。

3. 伯努利老虎機(jī)上使用不同策略的對(duì)比

定義 $\theta = (\theta_1, ...,\theta_k)$ ，先驗(yàn)為 $\theta_a \sim U(0, 1)$ ，它們之間相互獨(dú)立。
$Y_{at},N_{at}$ 分別代表t時(shí)刻a的累計(jì)成功次數(shù)和觀測(cè)次數(shù)。
則 $\theta = (\theta_1, ...,\theta_k)$ 的后驗(yàn)為：

$p(\theta|Y_t) =\prod ^k_{a=1}Be(\theta_a|Y_{at}+1,N_{at} - Y_{at} + 1)$ (10)

其中 $B_e(\theta|\alpha, \beta)$ 是貝塔分布。此時(shí)最佳概率為：

$w_{at} = \int_{0}^{1}Be(\theta_a|Y_{at}+1,N_{at} - Y_{at} + 1)\prod_{j\neq a}Pr(\theta_j < \theta_a | Y_{jt} + 1 - N_{jt} - Y_{jt} + 1)d\theta_a$ (11)

驗(yàn)證主要關(guān)注regret，最佳選擇 $\mu^*(\theta) = max_a\{\mu_a(\theta) \}$ ，手臂a在t時(shí)刻的觀測(cè)次數(shù)為 $n_{at}$ ，則t時(shí)刻的regret為：

$L_t = \sum_an_{at}(\mu^*(\theta) - \mu_a(\theta))$ (12)

則T時(shí)段累計(jì)regret為 $L = \sum_{t= 1}^TL_t$ 。以下是一些模擬對(duì)比結(jié)果。

3.1 批量更新場(chǎng)景

3.1.1 RPM對(duì)比平均分配

Cumulative regret in each of 100 simulation experiments under (a) randomized probability matching and (b) equal allocation. Note that the scales differ by an order of magnitude. For comparison purposes, both panels include a rug-plot showing the regret distribution under probability matching.

Expected regret per time period under (a) randomized probability matching and (b) equal allocation. Boxplots show variation across 100 simulated experiments.

Evolution of the posterior distribution (means and upper and lower 95% credibility bounds) of under (a) randomized probability matching and (b) equal allocation. Each panel corresponds to an arm. Arms are sorted according to optimality probability when the experiment ends.

從測(cè)試數(shù)據(jù)看RPM會(huì)比后者好得多。

3.1.2 RPM對(duì)比貪心

Regret from deterministic probability matching. The first ten periods were spent learning the parameters of each arm.

(a) Stacked stripchart showing cumulative regret after excluding the first 10 test periods. Panel (b) shows means and standard deviations of the expected losses plotted in panel (a). Greedy methods have a higher chance of zero regret. Randomized probability matching has a lower variance.

可發(fā)現(xiàn)在批量更新場(chǎng)景，兩種貪心策略效果都是比RPM差的。

3.2 實(shí)時(shí)更新場(chǎng)景

(a) Expected regret under real-time sampling across 100 experiments, each simulated for 10 000 time steps and (b) mean and standard deviation of the expected losses plotted in panel (a), along with the percentage of experiments for which the optimal arm was selected at time 10 000.

平均效果來(lái)看，RPM效果最差，但是它的標(biāo)準(zhǔn)差最小，最優(yōu)解命中率最高；參數(shù)為0.999的Gittins index平均效果最好，標(biāo)準(zhǔn)差較大，且最優(yōu)解的命中率低于RPM。

后記

RPM可以用來(lái)解決多臂老虎機(jī)問(wèn)題，它基于后驗(yàn)抽樣，易于實(shí)現(xiàn)、健壯性好，且在批量更新場(chǎng)景表現(xiàn)更佳。
此外這是一篇學(xué)習(xí)記錄，個(gè)人理解可能不夠到位，任何問(wèn)題歡迎留言。

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

現(xiàn)代貝葉斯與多臂老虎機(jī)

現(xiàn)代貝葉斯與多臂老虎機(jī)

背景