###### tags: `reinforcement learning`
# 深度強化學習 Ch2 : 馬克夫決策過程
<br>
## **2.1 多臂拉霸機問題**
:::success
假設有10台拉霸機，每一台最高獎金為10美金，且它們的平均獎金是不同的，要如何選到平均獎金最高的拉霸機?
:::
策略：隨機選擇一台拉霸機並進行多輪遊戲，一輪遊戲拉一台拉霸一次，記錄每一輪獲得的獎金，計算每一台拉霸機的**期望獎金**(expected **reward**)
:::warning
公式
$$ Q_k(a)=\frac{r(a1)+r(a2)+...+r(an)}{n} $$
$a$：拉霸機號碼
$Q_k(a)$：a拉霸在第K次遊戲中的期望獎金
$n$：拉霸a被執行過的總次數
$r(a1)$：第一次執行拉霸a的獎金
:::
寫成程式碼
```python=
def exp_reward(a,history):
reward_a=history[a] #history[a]儲存了拉霸a每次獲得獎金的紀錄
return sum(reward_a)/len(reward_a)
```
這裡$Q_k(a)$稱**價值函數**或**動作-價值函數**也稱**Q函數**
<br>
### **2.1.1 探索與利用**
**探索**：嘗試未拉過的機台用來累積經驗
**利用**：利用已累績的經驗獲取最大的利益(獎金)
**利用平均(期望)獎金找出最佳動作**
```python=
def get_best_action(actions,history):
best_action = 0
max_action_value = 0
for i in range(len(actions)):
cur_action_value = exp_reward(actions[i],history)
if cur_action_value > max_action_value:
best_action = i #若cur_action_value比較大，即更新索引best_action的值
max_action_value = cur_action_value
return best_action
```
將每個動作帶入$Q_k(a)$，去找出能達得到最大期望獎金的動作
此種作法不會建議未玩過的機台，只使用到利用策略，稱**貪婪法**
### **2.1.2 機率值-貪婪策略**
在之前的演算法加入機率值$\mathcal{E}$，使它有$\mathcal{E}$的機率選擇一台拉霸機(探索)，其他時候則選擇表現最好的拉霸機(利用)
**設定 $\mathcal{E}$ 值及不同拉霸機的中獎率**
```python=
import numpy as np
from scipy import stats
import random
import matplotlib.pyplot as plt
n = 10 #設定拉霸機的數量
probs = np.random.rand(n) #隨機設定每台拉霸機的中獎率（0～1之間）
eps = 0.2 #設定ε為0.2
```
估算中獎率為多少中獎金額
**把中獎率轉成中獎金額**
```python=+
def get_reward(prob): #prob為單台拉霸機著中獎率
reward = 0
for i in range(10):
if random.random() < prob: #random()會產生均勻分佈的亂數，所以在10次迴圈中，產生的亂數值小於prob的次數會正比於prob的大小
reward += 1 #若隨機產生的數字小於中獎率，就把reward加1
return reward #儲存本次遊戲開出的獎金
```
使用陣列的方式來表示拉霸機的次數(n)以及平均數($\mu=\frac{1}{n}\sum_{i}{x_i}$)
<img src="https://i.imgur.com/cNdypzH.png" style="height:300px;">
-----------**n**----**$\mu$**---------------------
陣列中第0行為每一台拉霸機的遊戲次數，第一行則是拉霸機的平均獎金
更新$\mu$公式
$$ \mu(new)=\frac{n*\mu(old)+x}{n+1} $$
**更新record內容**
```python=+
def update_record(record,action,r): #action為拉霸機編號 r為拉霸機最新一次拉桿開出的獎金
r_ave = (record[action,0] * record[action,1] + r) / (record[action,0] + 1) #算出新的平均值
record[action,0] += 1 #action號機台的拉桿次數加1
record[action,1] = r_ave #更新該機台的平均獎金
return record
```
**找出最佳動作(argmax寫法)**
```python=+
def get_best_arm(record):
arm_index = np.argmax(record[:,1]) #找出陣列第一行中，值(平均獎金)最大的索引
return arm_index
```
==**拉霸機主程式**==
散佈圖設定
```python=+
fig,ax = plt.subplots(1,1)
ax.set_xlabel("Plays")
ax.set_ylabel("Average Reward")
fig.set_size_inches(9,5)
```
在迴圈中，先產生一個隨機值，如果大於$\mathcal{E}$(前面有設定$\mathcal{E}$=0.2)，找出最高平均獎金的機台號碼，小於的話，則隨機選出一個機台號碼
```python=+
record = np.zeros((n,2)) #先產生一個初始值全部為零的record陣列
probs = np.random.rand(n) #隨機決定每台拉霸機的中獎率
rewards = [0] #記錄每次拉桿後，計算出的總體平均獎金
for i in range(500):
if random.random() > eps: #利用
choice = get_best_arm(record)
else: #探索
choice = np.random.randint(10)
r = get_reward(probs[choice]) #取得此次遊戲會得到的獎金
record = update_record(record,choice,r) #更新record陣列中與該拉霸機號碼對應的遊戲次數和平均獎金
mean_reward = ((i+1) * rewards[-1] + r)/(i+2) #計算最新的總體平均獎金
rewards.append(mean_reward) #記錄到rewards串列
ax.scatter(np.arange(len(rewards)),rewards) #畫出散佈圖
```
散佈圖
<img src="https://i.imgur.com/t0vWBLN.pngN">
可以看到總體平均獎金隨著遊戲次數增加而上升
### **2.1.3 利用softmax策略**
:::success
醫師今天有10種方法治療心臟病，它需要知道成功率最高的方法，也要知道其他方法的成功率
:::
策略：使用softmax策略，它可以告訴我們每一個動作的成功率有多高
* $P(A)$分子式**指數化**動作價值陣列除以參數$\tau$，輸出與動作價值陣列相同的陣列。分母是將分子輸出的陣列數值加起來。
* 動作價值$V(A)$越高，對應機率值也越高。動作價值陣列相同，每個動作的機率值也會是相同，且總合為1。
* $\tau$能調整不同動作的機率分布狀態。$\tau$越大，動作之間的機率值差異越小。
**softmax函式**
```python=
def softmax(av, tau=1.12):#av為動作價值陣列，tau即溫度參數（預設值=1.12）
softm = ( np.exp(av / tau) / np.sum( np.exp(av / tau) ) )
return softm
```
**使用softmax解決多臂拉霸機問題**
需修改的地方只有if else，改為使用softmax函數根據每個動作價值計算相應的機率值，且使用np.random.choice()來選擇其中一台拉霸機，它會根據陣列中的機率分布來隨機選擇動作。
```python=+
for i in range(500):
p = softmax(record[:,1],tau=0.7) #根據每個動作的價值計算出相應的機率值
choice = np.random.choice(np.arange(n),p=p) #根據p陣列中的機率分佈隨機選擇一個動作
r = get_reward(probs[choice])
record = update_record(record,choice,r)
mean_reward = ((i+1) * rewards[-1] + r)/(i+2) #計算最新的總體平均獎金
rewards.append(mean_reward)
ax.scatter(np.arange(len(rewards)),rewards) #畫出散佈圖
```
<img src="https://i.imgur.com/t0vWBLN.pngN" style="height:300px">使用貪婪法
<img src="https://i.imgur.com/fUustXR.png" style="height:300px">使用softmax
使用softmax策略可以讓總體平均獎金上升更快，缺點是$\tau$的調整會導致結果變化大，需要嘗試多次才能找到適當值。
## **2.2 廣告推送策略**
:::success
今天公司經營10家電商網站，希望客戶在其中一個網站下單後，向他推送公司其他電商網站的廣告，以誘導客戶區消費。
:::
為了吸引客戶點擊，推送廣告的內容要和顧客目前位於的電商平台有關，因此了解顧客**目前所在網站**與**接下來推送支廣告**之間的關聯很重要。
### **2.2.1 狀態、動作、回饋值**
* **狀態集合(狀態空間)**：記為S，由所有可能的狀態組成的集合(空間)，可以從一個情境中得到線索。
* **動作集合(動作空間)**：記為A，由所有可能的動作組成的集合(空間)，沒有環境線索，只能靠誤試學習來找答案。
* **回饋值**：記為r，執行動作後獲得的數值。
<img src="https://i.imgur.com/l7Zdnwo.png" style="height:280px">
* **狀態-動作對(s,a**)：表示模型在狀態s下執行了動作a
由於狀態-動作-回饋值組合數資料非常大，需依靠深度學習來保留重要資訊，找出**狀態-動作對**與**回饋值**之間的關係。
### **2.2.2 解決廣告推送問題**
建立一個環境，裡面包含：**狀態**(顧客所在網站)、**回饋值**(是否點擊)、**動作**(推送什麼廣告)
**建立拉霸機的環境(contextBandit)**
```python=
import numpy as np
import random
class ContextBandit: #拉霸機環境類別
def __init__(self, arms=10):
self.arms = arms #這裡的arm代表廣告
self.init_distribution(arms)
self.update_state()
def init_distribution(self, arms):
states = arms # 讓狀態數=廣告數以方便處理
self.bandit_matrix = np.random.rand(states,arms) #隨機產生的10種狀態下的10個arms的機率分佈（10*10種機率）
def reward(self, prob): #用途與前面的程式中獎率轉換成中獎金額相同
reward = 0
for i in range(self.arms):
if random.random() < prob:
reward += 1
return reward
def update_state(self):
self.state = np.random.randint(0,self.arms) #隨機產生一個新狀態
def get_state(self): #傳回當前狀態值(顧客目前所在網站)
return self.state
def get_reward(self,arm):
return self.reward(self.bandit_matrix[self.get_state()][arm]) #根據當前狀態及選擇的arm傳回回饋值
def choose_arm(self, arm): #推送一則廣告，並傳回一個回饋值
reward = self.get_reward(arm)
self.update_state() #產生下一個狀態
return reward #傳回回饋值
```
呼叫choose_arm()時也會更新當前狀態，之後可用get_state()來讀取此狀態
**使用環境範例**
```python=+
env = ContextBandit(arms=10) #創建一個環境
state = env.get_state() #取得當前狀態
reward = env.choose_arm(1) #在目前的狀態下選擇推送1號網站的廣告，並計算其回饋值
print(state,reward)
```
==**建構神經網路及運算流程**==
廣告推送會有10種狀態(顧客目前所在的網站)，10種動作(推送不同網站的廣告)，共會有10X10的機率。
使用pytorch框架來建立神經網路
* 建構以ReLU為激活函數的雙層神經網路。第一層網路要輸入one-hot向量，最後一層輸出預測的結果。
* 神經網路預測在特定情況下，每個動作的回饋值。
* 使用softmax算出所有動作的機率分佈，根據分佈情形選擇一個廣告，選擇後收到回饋值。
<img src="https://i.imgur.com/IDCT6Jz.png" style="height:310px">
$\Theta_1$,$\Theta_2$：權重參數
$N,R,P$：自然數、實數、機率
**設定超參數**
```python=
import numpy as np
import torch
arms = 10
N, D_in, H, D_out, = 1, arms, 100, arms
```
N：批次(batch)大小、D_in：輸入資料寬度、H：隱藏層的寬度、D_out：輸出層的寬度
**建構神經網路**
```python=+
model = torch.nn.Sequential(
torch.nn.Linear(D_in, H), #隱藏層
torch.nn.ReLU(),
torch.nn.Linear(H, D_out), #輸出層
torch.nn.ReLU(),
)
loss_fn = torch.nn.MSELoss() #使用均方誤差(MSE)作為損失函數
env = ContextBandit(arms) #利用之前ContextBandit建一個新環境
```
**one-hot編碼**
```python=+
def one_hot(N, pos, val=1): #N:狀態的總數、pos：目前狀態號碼
one_hot_vec = np.zeros(N)
one_hot_vec[pos] = val
return one_hot_vec
A = one_hot(10, 4) #假設目前的狀態號碼為4
print(A)
```
output <img src="https://i.imgur.com/eAwFfr5.png" style="height:20px"> 只有4的位置為1
<img src="https://i.imgur.com/37Ps3ae.png" style="height:330px;width:1800px">
**主要訓練迴圈**
```python=+
def train(env, epochs=10000, learning_rate=1e-2): #執行10000次訓練
cur_state = torch.Tensor(one_hot(arms,env.get_state())) #取得環境目前的狀態，並將其編碼為one-hot張量
optimizer = torch.optim.Adam(model.parameters(), lr=learning_rate)
rewards = []
for i in range(epochs):
y_pred = model(cur_state) #執行神經網路並預測回饋值
av_softmax = softmax(y_pred.data.numpy(), tau=1.12) #利用先前定義的softmax()將預測結果轉換成機率分佈向量
choice = np.random.choice(arms, p=av_softmax) #依照softmax輸出的機率分佈來選取新動作
cur_reward = env.choose_arm(choice) #執行選擇的動作，並取得一個回饋值
one_hot_reward = y_pred.data.numpy().copy() #將資料型別由PyTorch張量轉換成Numpy陣列
one_hot_reward[choice] = cur_reward #更新one_hot_reward陣列的值，把它當作標籤（實際的回饋值）
reward = torch.Tensor(one_hot_reward)
rewards.append(cur_reward) #將回饋值存入rewards中，以便稍後繪製線圖
loss = loss_fn(y_pred, reward)
optimizer.zero_grad()
loss.backward()
optimizer.step()
cur_state = torch.Tensor(one_hot(arms,env.get_state())) #更新目前的環境狀態
return np.array(rewards)
rewards = train(env) #開始訓練10000次
```
**將平均回饋值隨時間變化畫成圖**
```python=+
def running_mean(x,N =100): #定義一個可以算出移動平均回饋值的函式
c = x.shape[0] - N
y = np.zeros(c)
conv = np.ones(N)
for i in range(c):
y[i] = (x[i:i+N] @ conv)/N
return y
plt.figure(figsize=(20,7))
plt.ylabel("Average reward",fontsize=14)
plt.xlabel("Training Epochs",fontsize=14)
plt.plot(running_mean(rewards,N=50))
```
<img src="https://i.imgur.com/dONp6T2.png" style="height:300px;width:1500px">
平均回饋值在訓練的過程快速上升，代表神經網路的學習很順利
## **2.3 馬可夫性質與馬可夫決策**
**馬可夫性質**：只需要當前狀態資訊，就可以選出最佳動作，過去的狀態資訊不會影響演算法做出決策。
**馬克夫決策(MDP)**：任何表現出馬可夫性質的控制任務。
* 有些問題一開始並不具備馬可夫性質，藉由將過往資訊塞入目前狀態，來賦予它馬可夫性質。
## **2.4 策略與價值函數**
在深度學習中**代理人**會與**環境**互動，目標是為了得到最多的回饋值。
:::success
$s_t$：時間點t的狀態、$a_t$：時間點t所採取的動作
**轉換機率**：某個動作促使環境將一種狀態轉變成另一種狀態的機率
:::
### **2.4.1 策略函數 Policy Function**
策略：根據目前**狀態**，決定該執行的**動作**。
:::warning
數學式：$\pi,s\rightarrow Pr(A\mid s)$，$s\in S$
解釋：策略($\pi$)可以算出在指定狀態中每個可能動作為最佳動作的機率
$Pr(A\mid s)$：s狀態下個動作的機率分布 A：動作空間 S：狀態空間
:::
### **2.4.2 最佳策略**
:::warning
數學式：$\pi^*\rightarrow argmaxE(r\mid \pi)$
解釋：能夠產生最高期望回饋值的策略
期望回饋值($E(r\mid \pi)$)：將回饋值長期觀察，並將結果進行平均計算
:::
### **2.4.3 價值函數 Value Function**
**- 狀態價值函數**
:::warning
數學式：$V^\pi：s\rightarrow E(r\mid s,\pi)$
解釋：在狀態$s$下，利用策略$\pi$所得到的期望回饋值$E(r\mid \pi)$，也稱為狀態價值。
:::
策略決定了我們能得到多少期望回饋值(可通過價值函數反映出來)
**- 動作價值函數(Q)**
:::warning
數學式：$Q^\pi：(a\mid s)\rightarrow E(r\mid a,s,\pi)$
解釋：可傳回狀-動作對$(s,a)$的期望回饋值
:::
Sign in with Wallet
Connect another wallet