強化學(xué)習(xí)基礎(chǔ)篇（二十四）價值迭代之gamblers問題

該問題基于《Reinforcement Learning: An Introduction》在第四章的例4.4 gamblers問題.

1、 問題描述

一個Gamblers下注猜測一系列拋硬幣實驗的結(jié)果。如果硬幣正面朝上，他獲得這一次下注的錢；如果背面朝上則失去這一次下注的錢。這個游戲在Gamblers達到獲利目標100￥或者全部輸光時結(jié)束。每一次拋硬幣，Gamblers必須從他的資金中選取一個整數(shù)來下注?？梢詫⑦@個問題表示為一個非折扣的分幕式有限MDP。

狀態(tài)為Gamblers的資金，動作為Gamblers下注的金額。收益一般情況下均為0，只有Gamblers達到獲利100￥的終止狀態(tài)時為+1。狀態(tài)價值函數(shù)給出了在每個狀態(tài)下Gamblers獲勝的概率。這里的策略是資金到賭注的映射。最優(yōu)策略將會最大化這個概率。

令為拋硬幣正面向上的概率。如果已知，那么整個問題可以由價值迭代或其他類似的算法解決。

2、初步分析

該問題可以視為一個無折扣的有限MDP問題：

• 狀態(tài)空間：賭徒的賭資：
• 行為：下注金額：(下注金額最多不會超過距離獲勝的差距)
• 收益：贏到100￥：+1，其余：0
• 狀態(tài)價值：狀態(tài)s下獲勝的概率。
• 策略：當(dāng)前持有賭資的下注金額。

問題解決需要使用價值迭代算法：

image.png

從價值迭代算法中可以看到，其與策略評估不同之處在于：算法僅執(zhí)行一遍價值評估，通過遍歷行為空間，選取最大的狀態(tài)價值賦值。

3、代碼實現(xiàn)

導(dǎo)入庫與定義超參數(shù)

import matplotlib
import matplotlib.pyplot as plt
import numpy as np

# 目標
GOAL = 100

# 這里包括了0和100，僅僅是為了方便作圖
STATES = np.arange(GOAL + 1)

# 硬幣正面朝上的概率
HEAD_PROB = 0.4

價值更新

這里代碼按照上面的算法實現(xiàn)，并完成結(jié)果作圖。

• 策略迭代中，價值評估僅關(guān)注在當(dāng)前狀態(tài)S下執(zhí)行一個確定動作后產(chǎn)生的狀態(tài)S’，進而遍歷S’產(chǎn)生狀態(tài)價值之和決定V(S)。

• 價值迭代中，價值評估關(guān)注在當(dāng)前狀態(tài)S下，執(zhí)行全部動作空間后產(chǎn)生的狀態(tài)價值列表L(S’)，進而取L(S’)中的最大值來決定V(S)。

  image.png

def figure_4_3():
    # # state value即狀態(tài)價值：記錄狀態(tài)s下獲勝的概率。
    state_value = np.zeros(GOAL + 1)
    # goal狀態(tài)下的獲勝概率必然為1.0
    state_value[GOAL] = 1.0
    
    sweeps_history = []

    # value iteration
    while True:
        old_state_value = state_value.copy()
        sweeps_history.append(old_state_value)
       
        # 對每一個 s ∈ S循環(huán)：
        for state in STATES[1:GOAL]:
            # 當(dāng)前狀態(tài)的行為空間上界不會超過：持有金額/距離獲勝所需金額
            actions = np.arange(min(state, GOAL - state) + 1)
            # 遍歷行為空間，目的是找出max_a
            action_returns = []
            for action in actions:
                # p:HEAD_PROB、(1 - HEAD_PROB)
                # r：0
                # V'(s)：后繼狀態(tài)價值state_value[state +(贏)\-（輸） action]
                action_returns.append(
                    HEAD_PROB * state_value[state + action] + (1 - HEAD_PROB) * state_value[state - action])
            # 找出所有行為a下的max—value
            new_value = np.max(action_returns)
            state_value[state] = new_value
        # 價值收斂
        delta = abs(state_value - old_state_value).max()
        if delta < 1e-9:
            sweeps_history.append(state_value)
            break

    # 輸出最終確定的最優(yōu)策略
    policy = np.zeros(GOAL + 1)
    for state in STATES[1:GOAL]:
        actions = np.arange(min(state, GOAL - state) + 1)
        action_returns = []
        for action in actions:
            action_returns.append(
                HEAD_PROB * state_value[state + action] + (1 - HEAD_PROB) * state_value[state - action])

        # action_returns從1開始（0代表輸光），np.round保留5位小數(shù)
        # 取action_returns最大值的下標
        policy[state] = actions[np.argmax(np.round(action_returns[1:], 5)) + 1]

    plt.figure(figsize=(10, 20))

    plt.subplot(2, 1, 1)
    for sweep, state_value in enumerate(sweeps_history):
        plt.plot(state_value, label='sweep {}'.format(sweep))
    plt.xlabel('Capital')
    plt.ylabel('Value estimates')
    plt.legend(loc='best')

    plt.subplot(2, 1, 2)
    plt.scatter(STATES, policy)
    plt.xlabel('Capital')
    plt.ylabel('Final policy (stake)')

    plt.savefig('../images/figure_4_3.png')
    plt.close()

4. 測試結(jié)果

下圖顯示了在價值迭代遍歷過程中價值函數(shù)的變化，以及在時最終找到的策略，這個策略是最優(yōu)的，但并不是唯一的。事實上存在一系列的最優(yōu)策略，具體取決于在argmax函數(shù)相等時的動作選取。

image.png

這里有個問題在于為什么最優(yōu)策略看起來有點奇怪，特別是在Captial為50的時候，他會選擇全部投注，但是當(dāng)51時卻沒那么激進。

其原因應(yīng)該在于，智能體是在嘗試著盡快結(jié)束，以達到全輸完 (reward=0），或者贏得最終獎勵(reward=1)。我們注意到，在資金為25的時候，如果我們?nèi)肯伦⒖赡艿玫?0。在50的時候同樣梭哈，可以得到100，這里僅用了兩次就獲得了reward。但是如果我們在資金25的時候下注少于25，那么要達到100這個目標就必須多玩幾局。 智能體追求下注次數(shù)少的原因應(yīng)該在于，次數(shù)越少，分布越不均勻（相反，次數(shù)越多分布越均勻），智能體可以充分利用分布不均勻時候的方差來增加實現(xiàn)目標的可能性。

5、擴展分析

的測試結(jié)果

上面的結(jié)果是基于硬幣正面朝上的概率為HEAD_PROB = 0.4的結(jié)果，如果，那么經(jīng)過了1600次的掃描后結(jié)果下圖，可以看出，當(dāng)硬幣正面概率為0.55的時候，最優(yōu)策略幾乎總是下注1塊，有點匪夷所思。可能是因為概率對我們比較有利。

image.png

的測試結(jié)果

如果，那么結(jié)果為：

image.png