[Day 02] Bandit Problem


前言

這篇文章主要探討強化學習的基礎,先從簡化的問題-Bandits Problem談起。

Bandit Problem

Bandits Problem, 或稱K-armed Bandits Problem, 是強化學習的簡化版本,也是強化學習的子集。

想像現在有一位醫師要開藥給病人,有三種藥可以選擇,但是對藥的成效完全沒有知識,因此須不斷試驗後找到一個效果最好的藥(找出一個給與最大回饋的選擇)。
這個問題事實上就是一個K-armed Bandit Problem,K指的是有幾種選擇,在這個例子中K=3。
做出一個選擇後,其帶來的回饋可以用Action-Value Function來表達。其數學式子如下

假設做出選擇a後得到的回饋是一個機率分布,則Action-Value的值則是該機率分布的期望值。

但是我們要怎麼有效估計每一種選擇的Action-Value?
以下提供給種方法

Sample Average Method


這個方法大概是:
對於選擇a,在時間t的Action Value為在t-1時間到最初時間回饋的平均。
以上面的例子來說,假設要有效的回饋是1,無效是0,P要在時間12時的Action Value就會是(1+0+0+0)/4 = 0.25。

Incremental Update Rule

其實這個方法是Sample Average Method的另一種版本。

Sample Average Method是在每一個時間點的回饋都有相同的權重,而Incremental Update Rule則是越接近現今的回饋有越大的權重;越久遠的回饋有越小的權重。而權重的衰減是基於式子中的αn(0~1, 越接近0衰減越快)。

Greedy Action Selection

能夠評估每一個選擇的Action Value後,接下來就要做出選擇,而最簡單的選擇策略就是選擇擁有最大Action Value的選項(Greedy Action Selection)。
然而,這個方法會造成許多問題。

假設現在要選擇一家餐廳吃飯,套用Greedy Action Selection的選擇策略,最初每家的Action Value都為0,因此隨機選一家(選第一家),得到回饋後用Incremental Update Rule更新Action Value,假設得到的回饋為1,第一家餐廳的Action Value會更新為1。現在第一餐廳的Action Value為三個選擇中的最大,因此導致此後每一次都會選擇第一家餐廳,其他家永遠沒有被選的機會。
這個問題又被稱作Exploration-Exploitation Dilemma,Expoitation(利用)為選擇當下最有利的選擇;Exploration為不考慮當下的利益,隨機選取一個選項,以謀取長期的利益。
上面的例子從到尾只有Exploitation,因此沒辦法找到真正回饋最大的選項。(第二家餐廳)

Epsilon-Greedy Action Selection

Epsilon-Greedy Action Selection是最簡單處理Exploration-Exploitation Trade-Off的方法。
每一回合隨機選擇一個0~1的數字,如果該數字小於ε(0~1),則選擇Explore,反之,選擇具有最大Action Value的選項。

Optimistic Initial Values

這個方法另每一個選項的初始值(在餐廳的例子中,初始值為0)為一個很大的值,而這個值通常大於所有可能的回饋。
而這些很大的初始值(很樂觀的值),可以增加早期的Exploration,以至於在某些情況下能比較快找到最佳選擇。
假設套用Epsilon-Greedy Action Selection和Optimistic Initial Values,則所謂的早期Exploration會發生在Exploitation(隨機值大於ε),因為每個選項的Action Value初始值(每個選項都一樣)大於所有可能的回饋,所以能保證每個選項在早期至少會被選擇一次(前K個選擇)。

Upper-Confidence Bound

另外一種處理Exploration-Exploitation Dilemma的方法為Upper-Confidence Bound。
這個方法主要為:每一回合選擇具有最大Upper Uncertainty Bound的選項。

譬如,在上圖例子中會選擇第一個選項。

在另外一個例子中(上圖)會選擇第二個選項。

不過Uncertainty是如何定義的?

從上面式子可得知,Uncertainty()與一個選項在過去時間北被選擇的頻率相關,如果一個選項在過去被選擇的頻率越低,Uncertainty Range越大。
換句話說,Upper-Bound Confidence就是選擇較少被Explore且Action Value越大的選項。
與Epsilon-Greedy Action Selection相比,Upper-Bound Confidence在一個回合內就融入的Exploration和Exploitation的精神,執行起來更有效率。

Bandit Problem與強化學習的差異


如果把Bandit Problem和Reinforcement Learning放在光譜的兩端,在光譜中間的會是Contextual Bandit。
這三者的差異到底在哪?
現在回想選擇餐廳和配藥的例子,每回合會隨機遇到其中一個問題,但選擇方不知道自己遇到的是哪個問題。在這樣的情況下,以上談到的方法都無法有效解決這個問題。如果現在選擇方對於現在遇到的是哪一個問題有線索,則可以根據遇到的問題選擇不同的Action Value,而這就是Contextual Bandit(又稱Associative Search, Search Policy and Problem are associated)。
換句話說,Bandit和Contextual Bandit的差別在於回饋的機率分布是否是單一、靜態的。而如果在Contextual Bandit中的選擇會影響未來的回饋,這個問題就變成Reinforcement Learning Problem。

總結

這篇文章介紹簡化的強化學習問題--Bandit Problem,其架構與強化學習非常相似,包括Action和Rewar,其中最重要的是Action-Value的概念,在強化學習中相對應的概念是State-Value Function,Action-Value Function,Bellman Equation,他們是各種強化學習演算法的基礎。而會在接下來的文章中提到。

參考資料

[1] Book: Reinforcement Learning by Richrd S. Sutton
[2] Coursera: Fundamentals of Reinforcment Learning by University of Alberta

#強化學習 #人工智慧 #Bandit Problem #演算法 #理論
從不同的面向介紹強化學習與基因演算法,並在Unity平台上做一些有趣的實驗。






Related Posts

Day 16 - 了解 JavaScript Module

Day 16 - 了解 JavaScript Module

[ JavaScript 11 ] 無敵重要的 Immutable 觀念

[ JavaScript 11 ] 無敵重要的 Immutable 觀念

平滑捲動效果  Smooth Scrolling

平滑捲動效果 Smooth Scrolling



Sponsored



Comments