Skip to content

Latest commit

 

History

History
370 lines (271 loc) · 14.3 KB

時間差分方法.md

File metadata and controls

370 lines (271 loc) · 14.3 KB

時間差分方法

Agenda

Note

簡介

  • 蒙特卡洛方法只適用於階段性任務，在每個階段結束後，更新策略。時間差分方法可以用在階段性也可以用在連續性任務。
  • 例子: 無人車需要在每個路口能夠判斷自己是否會撞車，並且在必要時修改策略，避免發生車禍。在蒙特卡洛方法下，若想要學習某個規律，則必須每次都要撞車，才能結束這階段任務。
  • 時間差分方法，將在每個時間步都在修改預測，而不是等互動結束才更新。

OpenAI Gym-CliffWalkingEnv

  • GitHub 文件
  • 一个 4x12 的矩阵（使用 Numpy 矩阵索引）：
    • 左下角的 [3, 0] 是起点
    • 右下角的 [3, 11] 是目标
    • 底部中心的 [3, 1..10] 是悬崖
    • 每个时间步都会获得 -1 奖励，跌入悬崖会获得 -100 奖励并重置为起点。当智能体抵达目标时阶段结束。

TD 预测：TD(0)

  • 首先，還是先討論預測問題(prediction problem)。

  • 回顧: 蒙特卡洛方法是如何進行預測

    • agent以階段性的方式跟env進行互動。
    • 如果是first-visit，則計算相對應的回報，並用來更新動作值。
    • 需要注意，我們不能再每個階段之間更改策略。
    • 然後，經歷很多很多的階段，得到一個很完美的動作值函數的估計結果，來解決預測問題。

618

  • 接下來的重點: 我們要透過修改更新步驟這個函數來達到即更新的目的。
    • 不是像蒙特卡洛方法每個階段更新一次。

619

620

  • 重點: 修改流程
    • Gt: agent遵守某個policy下，在狀態s下可能會得到的預期回報。
    • 將Gt根據貝爾曼方程式進行改寫。
    • 現在，不再針對取樣回報取平均值
    • 而是 -- 下個時間步的即時獎勵 ＋ 下個時間步的折扣率 * 下個時間步的狀態值
    • 透過這樣的修改，可以讓我們在每個時間步更新狀態值。

621

  • 現在更新函數，就可以利用當下這個時間步做即時的更新。
    • 不用再等階段結束才更新。

622

  • 重新改寫一下更新函數
    • 當alpha = 1, 表示新的估計值就是TD目標。
    • 當alpha = 0, 則完全忽略TD目標，保留舊的估計值，這樣agent就無法學到規律了。
    • 當alpha越低，表示在更新時，對TD目標的信任就越低，比較依賴目前狀態的現有估值。

623

624

625

  • One-Step TD for 連續性任務
    • 每個時間步之後都更新值函數。

626

  • One-Step TD for 階段性任務
    • 多個檢查是否當下這個state是否為terminal狀態。

627

實現 - TD(0)

628

迷你项目 part0,1

from collections import defaultdict, deque
import sys

def td_prediction(env, num_episodes, policy, alpha, gamma=1.0):
    # initialize empty dictionaries of floats
    V = defaultdict(float)
    # loop over episodes
    for i_episode in range(1, num_episodes+1):        
        # episode準備開始
        state = env.reset()
        # TD for 階段性任務
        while True:
            # 根據policy選擇對應的action
            action = policy[state]
            # 根據action得到reward跟下一個state
            next_state, reward, done, info = env.step(action)
            # 執行 TD 的更新
            V[state] = V[state] + (alpha * (reward + (gamma * V[next_state]) - V[state]))
            # 更新state
            state = next_state
            # 對於階段性任務，要多檢查目前state是否為terminal狀態
            # 連續性任務就不需要這一步
            if done:
                break
                
    return V

TD 預測：動作值

  • 在上個階段，我們學會如何即時更新狀態函數的方法，
    • agent 會在S1去更新S0狀態，在St去更新St-1的狀態。

629

  • 接下來就是要如何即時更新動作函數。
    • 類似的概念，一樣在St+1, At+1去更新St, At的狀態。

630

631

TD 控制：Sarsa(0)

  • 在上面已經解決預測問題，現在要來處理控制問題，如何及時去更新策略。
    • 在每個時間步使用一個針對當前動作估值，利用Epsilon greedy policy來選擇一個動作。

632

實現 - Sarsa(0)

633

迷你项目 part2

# 先準備一些helper function

# action-value function的更新
# 利用Q+1來更新Q
def update_Q(Qsa, Qsa_next, reward, alpha, gamma):
    return Qsa + (alpha * (reward + (gamma * Qsa_next) - Qsa))

# 根據epsilon-greedy policy來決定每個state中每個action的機率
# 有一定的機率會非最高的動作值
def epsilon_greedy_probs(env, Q_s, i_episode, eps=None):
    # 隨著episode執行越多次，epsilon就越小，就越greedy
    epsilon = 1.0 / i_episode
    if eps is not None:
        epsilon = eps
    # 利用epsilon控制greedy程度， epsilon越小，越greedy
    policy_s = np.ones(env.nA) * epsilon / env.nA  # 讓每個狀態下的每個action都有機會被執行到
    policy_s[np.argmax(Q_s)] = 1 - epsilon + (epsilon / env.nA) # 進行greedy

    return policy_s
def sarsa(env, num_episodes, alpha, gamma=1.0):
    # initialize action-value function (empty dictionary of arrays)
    Q = defaultdict(lambda: np.zeros(env.nA))

    # loop over episodes
    for i_episode in range(1, num_episodes+1):           
        # 分數初始化
        score = 0
        # 狀態初始化 -- (S0)
        state = env.reset()
        # 根據epsilon-greedy獲得每個action執行的機率
        policy_s = epsilon_greedy_probs(env, Q[state], i_episode)
        # 根據機率來隨機挑選動作 -- (A0)
        action = np.random.choice(np.arange(env.nA), p=policy_s)
        # 限制每次episode最多只能進行300步
        for t_step in np.arange(300):
            # 根據action得到reward跟下一個state
            next_state, reward, done, info = env.step(action)
            # 將reward加入score -- (R1)
            score += reward
            
            if not done:
                # 再次根據epsilon-greedy獲得每個action執行的機率 -- (S1)
                policy_s = epsilon_greedy_probs(env, Q[next_state], i_episode)
                # 再次根據機率來隨機挑選動作 -- (A1)
                next_action = np.random.choice(np.arange(env.nA), p=policy_s)
                # 進行action function的更新，利用TD來更新Q
                Q[state][action] = update_Q(Q[state][action], Q[next_state][next_action], 
                                            reward, alpha, gamma)
                # 更新狀態跟動作
                state = next_state
                action = next_action
            
            if done: 
                # 進行action function的更新，利用TD來更新Q
                Q[state][action] = update_Q(Q[state][action], 0, reward, alpha, gamma)
                break                                
    return Q

TD 控制：Sarsamax

  • 回顧Sarsa(0)
    • 初始化所有狀態下動作值函數。
    • 利用Epsilon greedy policy，決定一個policy。
    • 利用這個policy來產生到A1。
    • A1出現後，再次更新動作值函數跟策略。

634

  • Sarsamax (Q-Learning)
    • 跟Sarsa(0)不同點: 在A1之前就更新策略

635

  • 直接找出最大化當下狀態的動作值的動作

636

637

  • Sarsamax, Sarsa(0)差異

638

實現 - Sarsamax

639

迷你项目 part3

def q_learning(env, num_episodes, alpha, gamma=1.0):
    # initialize empty dictionary of arrays
    Q = defaultdict(lambda: np.zeros(env.nA))
    tmp_scores = deque(maxlen=plot_every)
    
    # loop over episodes
    for i_episode in range(1, num_episodes+1):        
        # 分數初始化
        score = 0
        # 狀態初始化 -- (S0)
        state = env.reset()
        
        while True:
            # 根據epsilon-greedy獲得每個action執行的機率
            policy_s = epsilon_greedy_probs(env, Q[state], i_episode)
            # 根據機率來隨機挑選動作 -- (A0)
            action = np.random.choice(np.arange(env.nA), p=policy_s)
             # 根據A0獲得 R1, S1
            next_state, reward, done, info = env.step(action)
            # 將reward加入score -- (R1)
            score += reward
            # 跟Sarsa(0)不同點 -- 不利用用next_action(A1)協助更新
            Q[state][action] = update_Q(Q[state][action], np.max(Q[next_state]), \
                                                  reward, alpha, gamma)      
            # 更新狀態
            state = next_state
            
            if done: 
                # append score
                tmp_scores.append(score)
                break
                
         
    return Q

TD 控制：預期Sarsa

  • Expected Sarsa 論文

  • 根據當下狀態的每個動作的機率，進行所有不同動作值相加

    • Sarsamax: 考慮最大化的動作。
    • Expected Sarsa: 考慮所有動作。

640

實現 - 預期Sarsa

641

迷你项目 part4

def expected_sarsa(env, num_episodes, alpha, gamma=1.0):
    # initialize empty dictionary of arrays
    Q = defaultdict(lambda: np.zeros(env.nA))
    
    # initialize performance monitor
    scores = deque(maxlen=num_episodes)
    
    # loop over episodes
    for i_episode in range(1, num_episodes+1):        
        # 分數初始化
        score = 0
        # 狀態初始化 -- (S0)
        state = env.reset()
        # 不同點 -- 在greedy方式設置常數0.005
        policy_s = epsilon_greedy_probs(env, Q[state], i_episode, 0.005)
        
        while True:
            # 根據機率來隨機挑選動作 -- (A0)
            action = np.random.choice(np.arange(env.nA), p=policy_s)
            # 根據A0獲得 R1, S1
            next_state, reward, done, info = env.step(action)
            # 將reward加入score -- (R1)
            score += reward
            # 不同點 -- 先取得S1所有action的機率
            policy_s = epsilon_greedy_probs(env, Q[next_state], i_episode, 0.005)

            # 跟SarsaMax不同點 -- 不是取max, 而是利用policy_s的內積來進行更新
            Q[state][action] = update_Q(Q[state][action], np.dot(Q[next_state], policy_s), \
                                                  reward, alpha, gamma)        
            # 更新狀態
            state = next_state
            
            if done: 
                # append score
                tmp_scores.append(score)
                break
                
    return Q

分析性能

  • 我们讨论过的所有 TD 控制算法（Sarsa、Sarsamax、预期 Sarsa）都会收敛于最优动作值函数 q∗（并生成最优策略 π∗）：(1) ϵ 的值根据 GLIE 条件逐渐降低，以及 (2) 步长参数 α 足够小。

这些算法之间的区别总结如下：

  • Sarsa 和预期 Sarsa 都是异同策略 TD 控制算法。在这种情况下，我们会根据要评估和改进的相同（ ϵ 贪婪策略）策略选择动作。
    • 先進行下一步動作後，才更新策略。
  • Sarsamax 是离线策略方法，我们会评估和改进（ϵ 贪婪）策略，并根据另一个策略选择动作。
    • 先更新策略，才進行下一步動作。
  • 既定策略 TD 控制方法（例如预期 Sarsa 和 Sarsa）的在线效果比新策略 TD 控制方法（例如 Sarsamax）的要好。
  • 预期 Sarsa 通常效果比 Sarsa 的要好。
    • 簡單來說，效果由好到壞： 预期 Sarsa > Sarsa > Sarsamax

總結