強化學習基礎篇（二十一）網格問題
該問題基于《Reinforcement Learning: An Introduction》在第三章中給出了一個簡單的例子:Gridworld, 以幫助我們理解有限MDPs串慰。
1佳鳖、網格問題描述
如下圖所示的長方形網格代表的是一個簡單的有限MDP锭魔。網格中的格子代表的是環(huán)境中的狀態(tài)您宪。在每個格子中，有四個可選的動作：東、南、西和北，每個動作都會使智能體在對應的方向上前進一格糊饱。如果采取的動作使得其不在網格內，則智能體會在原位置不移動颠黎，并且得到一個值為-1的收益另锋。除了將智能體從特定的狀態(tài)A和B中移走的動作外，其他動作的收益都是0狭归。在狀態(tài)A中夭坪，四種動作都會得到一個+10的收益，并且把智能體移動到A'过椎。在狀態(tài)B中室梅，四種動作都會得到一個+5的收益，并且把智能體移動到B‘疚宇。
2亡鼠、解析
這是一個典型的MDP問題，有限的狀態(tài)空間敷待，有限的動作空間间涵。但是，我們面臨兩個棘手的問題：
- 根據Bellman等式榜揖，當前狀態(tài)的價值依賴于下一個狀態(tài)的價值浑厚，這是一個遞歸的過程股耽。從何處開始根盒，在何處結束钳幅？對于每一個狀態(tài)都有不同的episode。
- 狀態(tài)空間和動作空間如何表達炎滞？狀態(tài)空間的表達容易想到使用格子的坐標來表示敢艰，比如格子A的狀態(tài)可表示為坐標0,10,1，那么動作空間如何表達比較合適呢册赛？
2.1钠导、Bellman等式的迭代求解
根據bellman求解MDP問題一般有兩種思路：第一，如果MDP的狀態(tài)轉移矩陣是已知的森瘪，則可以精確的數值求解：求解線性方程組而已牡属。。第二扼睬，Bellman等式本身是一個迭代公式逮栅，因此可以通過迭代的方式逐步逼近狀態(tài)價值函數。這種方式對狀態(tài)轉移矩陣不敏感窗宇，即無論是否知道狀態(tài)轉移矩陣都可以使用措伐，也非常適合于編程實現。
迭代求解狀態(tài)價值函數的基本步驟為：
- 初始化狀態(tài)價值矩陣军俊，一般初始化為0侥加。這是計算的起點，此時每個狀態(tài)的價值函數都是0粪躬。
- 根據Bellman等式担败，計算每個狀態(tài)的新的價值函數。注意這一步不是一個遞歸的過程镰官，因為上一輪的狀態(tài)價值矩陣是已知的提前，在這一輪直接可以根據上一輪的狀態(tài)價值矩陣計算新的價值函數即可，即：
其中的代表了迭代的輪次（episode）朋魔，注意不要和每個輪次（episode）中的時刻（步驟）的tt混淆了岖研。
計算每個輪次迭代的誤差，達到設定的誤差范圍即可停止迭代警检，此時即獲得了最終的狀態(tài)價值函數孙援。
這種迭代求解狀態(tài)價值函數的方法稱為”Policy Evaluation Prediction”诺核，即對于任意給定的策略侄柔，都可以通過迭代的方式逐步逼近求解狀態(tài)價值函數兵拢。但是糊啡，必須確保這種迭代求解的方法對于任意策略
都是收斂的据沈，
證明如下：
通過觀察上式是鬼，并對照Bellman等式
可以看出资铡，式1只是對式2的簡單變量替換鬼吵，由替換為
，而式2在
或者episode能夠在有限步內結束時即收斂鸽凶，因此式1在同樣的條件下也會收斂币砂，即迭代求解狀態(tài)價值函數的方法的收斂條件為：或者
，或者所解決的MDP問題的episode是有限的玻侥。這兩個條件幾乎總是能夠滿足其中之一的决摧。
2.2、動作空間的表示方式
動作對狀態(tài)的影響表現為狀態(tài)坐標的改變凑兰，因此將動作定義為對狀態(tài)坐標的偏移量是個合理的方案掌桩，這樣可以直接將狀態(tài)和動作相加即可獲得“下一個狀態(tài)”。以動作up為例姑食，其對狀態(tài)的影響為橫坐標不變波岛，縱坐標增加+1，因此可以將up定義為[0,1]音半。同理则拷，動作down可以定義為[0,-1]。
3. 實現過程
3.1祟剔、導入庫文件
import matplotlib
import matplotlib.pyplot as plt
import numpy as np
from matplotlib.table import Table
3.2隔躲、定義環(huán)境
WORLD_SIZE = 5 # 定義問題中格子的數量
# 定義問題中A,A',B,B'的位置
A_POS = [0, 1]
A_PRIME_POS = [4, 1]
B_POS = [0, 3]
B_PRIME_POS = [2, 3]
# 定義折扣參數
DISCOUNT = 0.9
# 把動作定義為對x，y坐標的增減改變
ACTIONS = [np.array([0, -1]), # 向上
np.array([-1, 0]), # 向左
np.array([0, 1]), # 向下
np.array([1, 0])] # 向右
# 定義畫圖會用到的動作
ACTIONS_FIGS=[ '←', '↑', '→', '↓']
# 該問題中每個動作選擇的概率為0.25
ACTION_PROB = 0.25
3.3物延、 定義環(huán)境轉移過程
def step(state, action):
"""每次走一步
state:當前狀態(tài)宣旱，坐標的list，比如[1,1]
action:當前采取的動作叛薯，是對狀態(tài)坐標的修正
函數返回值浑吟，下一個狀態(tài)（坐標的list）和reward
"""
# 當在A位置的時候，會轉移到A',并得到獎勵+10.
if state == A_POS:
return A_PRIME_POS, 10
# 當在B位置的時候耗溜，會轉移到B',并得到獎勵+5.
if state == B_POS:
return B_PRIME_POS, 5
# 計算下一個狀態(tài)
next_state = (np.array(state) + action).tolist()
x, y = next_state
# 當運動未知超出格子世界則在原位置不變组力，并且得到-1的收益，其他情況得到的收益都是0抖拴。
if x < 0 or x >= WORLD_SIZE or y < 0 or y >= WORLD_SIZE:
reward = -1.0
next_state = state
else:
reward = 0
return next_state, reward
3.4 燎字、繪制價值函數結果
def draw_image(image):
fig, ax = plt.subplots()
ax.set_axis_off()
tb = Table(ax, bbox=[0, 0, 1, 1])
nrows, ncols = image.shape
width, height = 1.0 / ncols, 1.0 / nrows
# Add cells
for (i, j), val in np.ndenumerate(image):
# add state labels
if [i, j] == A_POS:
val = str(val) + " (A)"
if [i, j] == A_PRIME_POS:
val = str(val) + " (A')"
if [i, j] == B_POS:
val = str(val) + " (B)"
if [i, j] == B_PRIME_POS:
val = str(val) + " (B')"
tb.add_cell(i, j, width, height, text=val,
loc='center', facecolor='white')
# Row and column labels...
for i in range(len(image)):
tb.add_cell(i, -1, width, height, text=i+1, loc='right',
edgecolor='none', facecolor='none')
tb.add_cell(-1, i, width, height/2, text=i+1, loc='center',
edgecolor='none', facecolor='none')
ax.add_table(tb)
3.5 、繪制策略圖形
def draw_policy(optimal_values):
fig, ax = plt.subplots()
ax.set_axis_off()
tb = Table(ax, bbox=[0, 0, 1, 1])
nrows, ncols = optimal_values.shape
width, height = 1.0 / ncols, 1.0 / nrows
# Add cells
for (i, j), val in np.ndenumerate(optimal_values):
next_vals=[]
for action in ACTIONS:
next_state, _ = step([i, j], action)
next_vals.append(optimal_values[next_state[0],next_state[1]])
best_actions=np.where(next_vals == np.max(next_vals))[0]
val=''
for ba in best_actions:
val+=ACTIONS_FIGS[ba]
# add state labels
if [i, j] == A_POS:
val = str(val) + " (A)"
if [i, j] == A_PRIME_POS:
val = str(val) + " (A')"
if [i, j] == B_POS:
val = str(val) + " (B)"
if [i, j] == B_PRIME_POS:
val = str(val) + " (B')"
tb.add_cell(i, j, width, height, text=val,
loc='center', facecolor='white')
# Row and column labels...
for i in range(len(optimal_values)):
tb.add_cell(i, -1, width, height, text=i+1, loc='right',
edgecolor='none', facecolor='none')
tb.add_cell(-1, i, width, height/2, text=i+1, loc='center',
edgecolor='none', facecolor='none')
ax.add_table(tb)
3.6阿宅、計算等概率隨機策略下的狀態(tài)價值函數(解貝爾曼期望方程)
貝爾曼期望方程的形式為：
def figure_3_2():
"""
計算每個單元格的狀態(tài)價值函數
"""
# 狀態(tài)價值函數的初值設置為0
value = np.zeros((WORLD_SIZE, WORLD_SIZE))
while True:
# # 每一輪迭代都會產生一個new_value候衍，直到new_value和value很接近即收斂為止
new_value = np.zeros_like(value)
# 對格子世界的每個狀態(tài)進行遍歷
for i in range(WORLD_SIZE):
for j in range(WORLD_SIZE):
# 對每個狀態(tài)的4個動作進行遍歷
for action in ACTIONS:
# 計算當前動作執(zhí)行后的下一個狀態(tài)，以及獎勵
(next_i, next_j), reward = step([i, j], action)
# 由于每個方向只有一個reward和s'的組合洒放，這里的p(s',r|s,a)=1
new_value[i, j] += ACTION_PROB * (reward + DISCOUNT * value[next_i, next_j])
# 當前new_value和value很接近蛉鹿，即error小到一定的程度則停止。
error = np.sum(np.abs(new_value - value))
if error < 1e-4:
draw_image(np.round(new_value, decimals=2))
plt.show()
break
value = new_value
figure_3_2()
輸出的測試結果如下所示：
可以看出往湿，靠近下邊的格子妖异，尤其是靠近邊界的格子的狀態(tài)價值偏小惋戏，這是因為靠近邊界的格子很容易出界，而出界的獎勵是-1他膳；格子A的價值最高响逢，這是很容易理解的，因為從A到A’的獎勵是+10矩乐。但是為什么格子A的價值<10呢龄句？這是因為從A到A’的獎勵盡管是+10，但是A’的價值卻是負值散罕，導致A的價值會跟著損失一些。格子B的價值分析方法類似傀蓉。
3.7欧漱、直接求解貝爾曼方程
下面采用代碼直接去求解貝爾曼方程。
def figure_3_2_linear_system():
'''
該函數通過直接求解線性方程組葬燎，得到貝爾曼方程的精確解误甚。
Here we solve the linear system of equations to find the exact solution.
We do this by filling the coefficients for each of the states with their respective right side constant.
'''
# 定義A矩陣，25*25大小谱净，對應著25個線性方程組
A = -1 * np.eye(WORLD_SIZE * WORLD_SIZE)
b = np.zeros(WORLD_SIZE * WORLD_SIZE)
for i in range(WORLD_SIZE):
for j in range(WORLD_SIZE):
# 當前狀態(tài)
s = [i, j]
# 該函數找到狀態(tài)s的序號窑邦，即將格子展開為5*5=25后，在這個長序列中的編號壕探。
index_s = np.ravel_multi_index(s, (WORLD_SIZE, WORLD_SIZE))
for a in ACTIONS:
# 獲取執(zhí)行動作后的下一個狀態(tài)和獎勵
s_, r = step(s, a)
# 找到下一個狀態(tài)的序號
index_s_ = np.ravel_multi_index(s_, (WORLD_SIZE, WORLD_SIZE))
# 線性方程組Ax=b的A中對應元素按照動作概率*折扣因子進行更新
A[index_s, index_s_] += ACTION_PROB * DISCOUNT
b[index_s] -= ACTION_PROB * r
# 求解Ax=b
x = np.linalg.solve(A, b)
draw_image(np.round(x.reshape(WORLD_SIZE, WORLD_SIZE), decimals=2))
plt.show()
輸出過和通過迭代方式求解出來的結果是一致的冈钦。
3.8、求解最優(yōu)價值函數（解貝爾曼最優(yōu)方程）
貝爾曼最優(yōu)方程的形式為：
def figure_3_5():
'''
求解貝爾曼最優(yōu)方程
'''
# 初始值設為0
value = np.zeros((WORLD_SIZE, WORLD_SIZE))
while True:
# keep iteration until convergence
new_value = np.zeros_like(value)
# 遍歷所有狀態(tài)
for i in range(WORLD_SIZE):
for j in range(WORLD_SIZE):
values = []
# 遍歷所有動作
for action in ACTIONS:
# 執(zhí)行動作,轉移到后繼狀態(tài),并獲得立即獎勵
(next_i, next_j), reward = step([i, j], action)
# value iteration
# 緩存動作值函數 q(s,a) = r + γv(s')
values.append(reward + DISCOUNT * value[next_i, next_j])
# 根據貝爾曼最優(yōu)方程,找出最大的動作值函數 q(s,a) 進行更新
new_value[i, j] = np.max(values)
# 迭代終止條件: 誤差小于1e-4
if np.sum(np.abs(new_value - value)) < 1e-4:
draw_image(np.round(new_value, decimals=2))
plt.show()
plt.close()
draw_policy(new_value)
plt.show()
break
value = new_value
figure_3_5()
計算得到的最優(yōu)價值函數如下所示：
從最后價值函數得到的最優(yōu)策略如下李请，圖中有很多個箭頭瞧筛，其對應的每個動作都是最優(yōu)的。
