前言

這篇文章主要探討強化學習的基礎，先從簡化的問題-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