增強式學習

• 監督式學習會有一個 tutor 或判斷依據，以圍棋來說是有一個棋譜
  
• 增強式學習沒有依據，完全從行為的經驗去自行判斷，以 alpha-go 為例，是以兩台 alpha-go 多次互相對奕來訓練，用這種方式的好處是可以生成大量資料
  

• “影分身之术”！训练50亿次的AI能有多智能
  
• 讓人工智慧玩捉迷藏，最後居然發展出連人類都想不到的策略!? | 一探啾竟 第80集 | 啾啾鞋
  

使用代理人(agent)來對環境進行觀察、選擇與執行行動，藉由因行動獲取來自環境的回應（可能是rewards或penalties，奬勵或懲罰），然後自行學習最佳策略（policy），最後隨著時間取得最多的奬勵¹。

典型的增強式學習是用來訓練機器人走路，DeepMind的AlphaGo也是應用增強式學習打敗柯潔（與柯潔比賽時AlphaGo關閉了學習機制，只應用之前已學習過的policy）。

對RL稍有了解的同學都知道，Exploration是一件很重要同時也很困難的事情。與其他機器學習範式相比，RL通常只知道某個動作的能得多少分，卻不知道該動作是不是最好的——這就是基於evaluate的強化學習與基於instruct的監督學習的根本區別。

正因如此，RL的本質決定了它極其需要Exploration，我們需要通過不斷地探索來發現更好的決策，或者至少證明當前的決策是最好的——所以Exploration-Exploitation成為了強化學習領域諸個Tradeoff中最出名的一個³。

最簡單的exploration方法就是epsilon-greedy，即設置一個探索率epsilon來平衡兩者的關係——在大部分時間裡採用現階段最優策略，在少部分時間裡實現探索。Epsilon-greedy很簡單，它根本不會考慮更加有針對性的探索機制，它僅僅是在純貪心的基礎上加入了一定機率的uniform噪聲——所以epsilon-greedy又被稱為Naive Exploration³。

於本機執行至少會用到以下兩個python module，若要在遠端主機或colab上執行則要再做其他額外設定。

pip install --user gym
pip install --user pyglet==1.5.11 (或是1.5.14)

在 Gym 的仿真環境中，有運動空間 action_space 和觀測空間observation_space 兩個指標，程序中被定義爲 Space類型，用於描述有效的運動和觀測的格式和範圍。我們可以利用以下程式碼大致觀察一下這兩個Space:

import gym
env = gym.make('CartPole-v1', render_mode="human")

print(env.action_space)
print(env.observation_space)

Discrete(2)
Box([-4.8000002e+00 -3.4028235e+38 -4.1887903e-01 -3.4028235e+38], [4.8000002e+00 3.4028235e+38 4.1887903e-01 3.4028235e+38], (4,), float32)

上述程式只執行了一回合的模擬，請你修改上述程式，進行200回合的模擬，記錄每回合隨機運作的reward結果，並將結果畫成折線圖，x軸為回合數；y軸為每回合的reward，

上述程式只是簡單的依杆子角度來移動車子，你能否再想出更好的策略(即可以在結束前得到更多reward，最多到200)?請觀察observation的內容，傾全組之力想出最佳策略並實作出來，進行200次模擬，畫出模擬的rewards折線統計圖。

import numpy as np
import gym

def get_sum_reward_by_weights(env, weights):
    #測試不同權重的model所得到的奬勵
    observation, info = env.reset()

    rewards = 0
    for t in range(1000):
        env.render()
        # 依目前權值針對當前狀態來選action
        # 原來的做法為: action = env.action_space.sample()
        action = 1 if np.dot(weights[:4], observation) + weights[4] >= 0 else 0
        # 執行action, 取得下一步狀態
        observation, reward, done, info = env.step(action)
        rewards += reward
        if done:
            print(t)
            break
    return rewards

def get_best_result():
    np.random.seed(10)
    best_reward = 0 # 初始最佳奬勵
    best_weights = np.random.rand(5) # 初始權值為隨機值

    for iter in range(1000): #迭代100次
        cur_weights = None
        print("iteration:",iter)
        cur_weights = best_weights + np.random.normal(0, 0.1, 5) #在當前最佳權值加入隨機值
        # cur_weights = np.random.rand(5) #隨機猜測
        cur_sum_reward = get_sum_reward_by_weights(env, cur_weights)
        reward_rec.append(cur_sum_reward) #記錄用
        if cur_sum_reward > best_reward:
            best_reward = cur_sum_reward
            best_weights = cur_weights
        if best_reward >= 200:
            print(iter,":",best_reward)
            print("best_weight",best_weights)
            break;

env = gym.make("CartPole-v0")
reward_rec = []

print(get_best_result())
# 輸出統計
import matplotlib.pyplot as plt
plt.clf()
x = range(1, len(reward_rec)+1)
plt.plot(x, reward_rec)
env.close()

爬山算法本質是一種局部擇優的方法，效率高但因爲不是全局搜索，所以結果可能不是最優。

在更新 Q table 時，計算 reward 不只包含採取 action \(a\)獲得的 reward \(r\)r，還包含 \(\gamma max_{a^{'}}Q(s^{'},q^{'})\)。這個概念是，agent 不僅僅看當下採取的行動帶來的好處，他也會估計到達下一個 state \(s^{'}\) 後，最多可以有多少好處（因為在\(s^{'}\)也可以採取各種 action）。
換句話說，這個 agent 不是一個目光如豆的 agent，他會考慮未來。因為加上了\(\gamma max_{a^{'}}Q(s^{'},q^{'})\)(當然\(\gamma\)不能是 0)，讓我們的 agent 從 會立刻吃掉棉花糖的小朋友，進化成可以晚一點再吃多一點棉花糖的小朋友，是不是很有趣呢！

一個 Q-learning 非常簡單的實現法。複習一下我們在前篇提到 Q-learning，是用一個 model 來 approximate Q-value function，並藉由下面的 update rule 來訓練這個 model：
\[ Q(s_t,a_t) = Q(s_t,a_t) + \alpha(R_{t+1}) + \gamma \max_{a} Q(s_{t+1}, - Q(s_t,a_t)) \]
Q-table 是用 lookup table 來 approximate Q-value function，並用 Q-learning 訓練的一個方法。這個 lookup table 會將每個 state-action pair (s, a) 對應到 approximation Q(s, a)，一開始 table 裡的 Q-value 隨機設置，並在訓練過程中更新這些 Q-value。所以我們其實沒有在訓練一個 model 更新參數讓預測數值更接近 Q-value，而是直接用一個 table 記錄這些值並更新。

另外我們的 state 是連續值，這樣會有無限多個可能的 state-action pair，因此我們要 discretize 這些值才能建立一個 lookup table。

例如實作中我們把 state 的 4 個 feature (position, velocity, angle, rotation rate) 分別 discretize 成 (1, 1, 6, 3) 個 bucket，6 個 bucket 就代表 angle 的範圍 [-0.5, 0.5] 被切成 6 個區間，區間中的值都對應到相同的 discrete value。

1. 整個 discretization 大概是這樣：
   

   # state bucket 設定
   n_buckets = (1, 1, 6, 3)
   
   # action 已經是 discrete value
   n_actions = env.action_space.n
   
   # 建立 Q-table
   q_table = np.zeros(n_buckets + (n_actions,))
   
   # 設定好每個 state feature 的上下界
   state_bounds = list(zip(env.observation_space.low, env.observation_space.high))
   state_bounds[1] = [-0.5, 0.5]
   state_bounds[3] = [-math.radians(50), math.radians(50)]
   
   # 將 env 給的 state 轉換成 discretized state
   def get_state(observation, n_buckets, state_bounds):
       state = [0] * len(observation)
       for i, s in enumerate(observation):
           # 每個 feature 上界、下界
           l, u = state_bounds[i][0], state_bounds[i][1]
           if s <= l: # 低於下界屬於第 1 個 bucket
               state[i] = 0
           elif s >= u: # 高於下界屬於最後一個 bucket
               state[i] = n_buckets[i] - 1
           else: # 其他看你在哪個區間，決定你在哪個 bucket
               state[i] = int(((s - l) / (u - l)) * n_buckets[i])
       return tuple(state)
   

state_bounds初始內容為

[(-4.8, 4.8),
 [-0.5, 0.5],
 (-0.41887903, 0.41887903),
 [-0.8726646259971648, 0.8726646259971648]]

q_table為(1, 1, 6, 3, 2)的ndarray，初始內容為

array([[[[[0., 0.],
          [0., 0.],
          [0., 0.]],

         [[0., 0.],
          [0., 0.],
          [0., 0.]],

         [[0., 0.],
          [0., 0.],
          [0., 0.]],

         [[0., 0.],
          [0., 0.],
          [0., 0.]],

         [[0., 0.],
          [0., 0.],
          [0., 0.]],

         [[0., 0.],
          [0., 0.],
          [0., 0.]]]]])

1. 再來是\(\epsilon-greedy\)的使用，選擇 action 時，有\(\epsilon\)的機率隨機選擇以增加 exploration，其他時間照著現有 policy 選擇：
   

   def choose_action(state, q_table, action_space, epsilon):
       if np.random.random_sample() < epsilon: # 隨機
           return action_space.sample()
       else: # 根據 Q-table 選擇最大 Q-value 的 action
           return np.argmax(q_table[state])
   

2. 最後就是做出 action 收集到 observation 和 reward 後，就可以 update Q-table：
   

   # 算出下個 state
   next_state = get_state(observation, n_buckets, state_bounds)
   
   # Q-learning
   q_next_max = np.amax(q_table[next_state])
   q_table[state + (action,)] += lr * (reward + gamma * q_next_max - q_table[state + (action,)])
   
   # Transition 到下個 state
   state = next_state
   

3. 剩下就跟前面的框架差不多了。實作中，還另外加了一些方法讓訓練成果更好，例如因為訓練後期有比較好的 policy，讓 https://chart.googleapis.com/chart?cht=tx&chl=%5Cepsilon 隨著訓練降低以減少 exploration，以及讓 learning rate 降低使訓練能收斂。
   

   get_epsilon = lambda i: max(0.01, min(1, 1.0 - math.log10((i+1)/25)))
   get_lr = lambda i: max(0.01, min(0.5, 1.0 - math.log10((i+1)/25)))
   
   # 每回合更新 epsilon 和 lr
   epsilon = get_epsilon(i_episode)
   lr = get_lr(i_episode)
   

4. 成果